Neighbours

This module answers questions of the form “which training points are closest to this one, and what do they say?” It covers k-nearest-neighbour voting and averaging, a distance-weighted average, the nearest-centroid classifier, the local outlier factor (LOF) and a Gaussian kernel density estimate.

The k nearest neighbours are found without sorting. For every row of a distance matrix, each entry is compared with every other entry of the same row; an entry with fewer than \(k\) entries below it is one of the \(k\) nearest. The result is a 0/1 mask, and every definition below is built from that mask. The cost is \(m \cdot n^2\) comparisons for \(m\) queries against \(n\) training points, held in one tensor, so the module suits hundreds or a few thousand points; a million points calls for a spatial index, which this module does not provide.

Conventions. Queries z are a matrix m×p and training points x a matrix n×p, one row per point, even when there is only one feature. Labels for classification are a one-hot matrix g of shape n×C; targets for regression are a vector y of length n. Distances are squared Euclidean distances throughout, including inside the outlier factor. Ties are kept rather than broken: if several points share the k-th distance, all of them are selected, and every average divides by the number of points actually selected, not by \(k\). When a set is compared with itself, a point is never its own neighbour.

open Prelude.Neighbours

The rank of every entry within its own row

For a distance matrix \(D\) of shape m×n, the within-row rank of an entry counts the entries of the same row that are strictly smaller:

\[\operatorname{rank}_{ij} = \sum_{l} [\, D_{il} < D_{ij} \,]\]

and the neighbourhood mask is \(N_{ij} = [\operatorname{rank}_{ij} < k]\).

nearestK

nearestK(d, k) · d distance matrix m×n · k number of neighbours scalar → 0/1 mask m×n

Let \(D \in \mathbb{R}^{m \times n}\) (the argument d) be a distance matrix and \(k \in \mathbb{N}\). Then

\[\operatorname{nearestK}(D, k)_{ij} = \Big[\, \sum_{l=1}^{n} [\, D_{il} < D_{ij} \,] < k \,\Big] .\]

Marks, in each row of d, the entries that are among the k smallest. Ties at the k-th distance are all marked, so a row may hold more than k ones.

Intuition An entry is among the \(k\) smallest of its row exactly when fewer than \(k\) entries of that row are strictly smaller: a rank test that needs no sorting. Every entry tied at the boundary passes the test, so ties are kept.

Use it when you already hold a dissimilarity matrix that is not squared Euclidean (cosine distance, edit distance, travel time) and want the top-k per row. Negate a score matrix to select the k largest instead. For Euclidean data, neighboursOf and neighboursIn build the distances for you. It compares every pair within a row, m×n×n in one tensor, so keep rows to a few thousand entries. When rows and columns are the same set, push the diagonal away first, as neighboursIn does.

similarity-searchtop-k-selectionrecommendation

def nearestK(d, k)   ≔ rowBelow(d) < k

neighboursOf

neighboursOf(z, x, k) · z queries m×p · x training points n×p · k number of neighbours scalar → 0/1 mask m×n

Let \(Z \in \mathbb{R}^{m \times p}\) (the argument z) be the queries with rows \(z_i^{\top}\), \(X \in \mathbb{R}^{n \times p}\) (the argument x) the training points with rows \(x_j^{\top}\), and \(k \in \mathbb{N}\). Let \(D_{ij} = \lVert z_i - x_j \rVert^2 = \lVert z_i \rVert^2 + \lVert x_j \rVert^2 - 2\, z_i^{\top} x_j\). Then

\[\operatorname{neighboursOf}(Z, X, k)_{ij} = N_{ij} = \Big[\, \sum_{l=1}^{n} [\, D_{il} < D_{ij} \,] < k \,\Big] .\]

The neighbourhood of every query among the training points: row i marks the training points nearest to query i by squared Euclidean distance.

Intuition Row \(i\) marks the \(k\) training points closest to query \(i\) in straight-line distance: the “who is most like me” set that every k-NN prediction on this page averages over.

Use it when you retrieve similar items for new queries (products, patients, documents represented as vectors) or build your own neighbour-based predictor. Scale the features first: distance weighs a unit of every column equally, so a column measured in thousands swamps one measured in fractions. To find neighbours inside a single set, use neighboursIn.

similarity-searchrecommendationfeature-scaling

def neighboursOf(z, x, k) ≔ nearestK(squared(z, x), k)

neighboursIn

neighboursIn(x, k) · x points n×p · k number of neighbours scalar → 0/1 mask n×n

Let \(X \in \mathbb{R}^{n \times p}\) (the argument x) be the points with rows \(x_i^{\top}\), \(k \in \mathbb{N}\), and \(A = D + 10^{300} I_n\) with \(D_{ij} = \lVert x_i - x_j \rVert^2\). Then

\[\operatorname{neighboursIn}(X, k)_{ij} = \Big[\, \sum_{l=1}^{n} [\, A_{il} < A_{ij} \,] < k \,\Big] .\]

The neighbourhood of every point within the same set. The diagonal is pushed out of reach by adding \(10^{300}\) to it, so a point is never counted as its own neighbour.

Intuition neighboursOf with a set compared against itself. The huge value added to the diagonal makes sure each point’s nearest neighbour is some other point rather than itself at distance 0.

Use it when you build a k-nearest-neighbour graph over one dataset: for outlier scores (outlierFactor), Isomap in Prelude.Manifold, leave-one-out evaluation of k-NN, or spotting near-duplicates. The mask is not symmetric: \(j\) can be one of \(i\)’s neighbours without the reverse, so take the larger of the mask and its transpose if you need an undirected graph. It holds an n×n×n comparison tensor.

similarity-searchduplicate-detectionmodel-evaluation

def neighboursIn(x, k)    ≔ nearestK(apartFrom(squared(x, x)), k)

Building blocks

rowBelow(d) — Let \(D \in \mathbb{R}^{m \times n}\). Then \(\operatorname{rowBelow}(D)_{ij} = \sum_{l=1}^{n} [\, D_{il} < D_{ij} \,]\). For each entry of a matrix, how many entries of the same row are strictly smaller.
apartFrom(d) — Let \(D \in \mathbb{R}^{n \times n}\). Then \(\operatorname{apartFrom}(D) = D + 10^{300} I_n\). Pushes the diagonal of a square distance matrix out of reach so no point is its own neighbour.
neighbourCount(m) — Let \(N \in \{0, 1\}^{m \times n}\) (the argument m) be a neighbourhood mask. Then \(\operatorname{neighbourCount}(N)_i = \sum_{j=1}^{n} N_{ij}\). How many neighbours each row actually selected.

Classification and regression

A vote is a contraction of the neighbourhood mask against the one-hot labels, \(V_{ic} = \sum_j N_{ij} G_{jc}\), so all classes are counted at once. Regression averages the targets of the selected neighbours.

knnVotes

knnVotes(z, x, g, k) · z queries m×p · x training points n×p · g one-hot labels n×C · k number of neighbours scalar → vote counts m×C

Let \(Z \in \mathbb{R}^{m \times p}\) (the argument z) be the queries with rows \(z_i^{\top}\), \(X \in \mathbb{R}^{n \times p}\) (the argument x) the training points with rows \(x_j^{\top}\), and \(k \in \mathbb{N}\), let \(G \in \{0, 1\}^{n \times C}\) (the argument g) be the one-hot labels, and \(N = \operatorname{neighboursOf}(Z, X, k)\). Then

\[\operatorname{knnVotes}(Z, X, G, k)_{ic} = V_{ic} = \sum_{j=1}^{n} N_{ij}\, G_{jc} .\]

How many of each query’s neighbours belong to each class.

Intuition For each query, a histogram of the classes found among its neighbours: the raw evidence before any decision is taken.

Use it when you want your own decision rule: demand a clear majority, weight classes by the cost of getting them wrong, or abstain when the vote is split. knnClassify takes the largest count and knnShares turns counts into fractions. With ties at the k-th distance a row’s counts can add up to more than k.

classificationcost-sensitive-decisions

def knnVotes(z, x, g, k)   ≔ einsum("ij,jc->ic", neighboursOf(z, x, k), g)

knnClassify

knnClassify(z, x, g, k) · z queries m×p · x training points n×p · g one-hot labels n×C · k number of neighbours scalar → 0/1 mask m×C

Let \(Z\), \(X\), \(G\), \(k\) be as in knnVotes and \(V = \operatorname{knnVotes}(Z, X, G, k)\). Then

\[\operatorname{knnClassify}(Z, X, G, k)_{ic} = [\, V_{ic} = \max_{c'} V_{ic'} \,] .\]

Hilbert returns a mask, not a class index.

The majority class of each query’s neighbours, as a one-hot row. A tied vote marks every class that shares the highest count.

Intuition “You are what your neighbours are”: a query takes the class most common among its \(k\) nearest training points. Nothing is fitted; the training data is the model, so class boundaries can take any shape.

Use it when classes occupy irregular regions of a low-dimensional, scaled feature space and the training set is modest: small diagnostic or recommendation datasets, digits after dimensionality reduction. Choose k by validation: small k follows noise, large k blurs boundaries, and an odd k avoids two-class ties. In many dimensions distances stop being informative, so reduce dimensions first. For a much cheaper classifier use centroidPredict.

classificationpattern-recognition

def knnClassify(z, x, g, k) ≔ highest(knnVotes(z, x, g, k))

knnShares

knnShares(z, x, g, k) · z queries m×p · x training points n×p · g one-hot labels n×C · k number of neighbours scalar → class fractions m×C

Let \(Z\), \(X\), \(G\), \(k\), \(N\) and \(V\) be as in knnVotes, and \(c_i = \sum_j N_{ij}\). Then

\[\operatorname{knnShares}(Z, X, G, k)_{ic} = \frac{V_{ic}}{c_i + [\, c_i = 0 \,]} .\]

The fraction of each query’s neighbours in each class; every row sums to one. It divides by the number of neighbours actually selected, which exceeds k when there are ties.

Intuition The fraction of the neighbourhood in each class: a local estimate of the class probabilities around the query.

Use it when you need soft outputs: ranking cases by likelihood, a threshold other than the majority, or averaging with other models. With small k the shares are coarse (with 5 neighbours they move in steps of 0.2) and often exactly 0 or 1, so do not read them as calibrated probabilities.

probability-calibrationrisk-scoringclassification

def knnShares(z, x, g, k)  ≔ knnVotes(z, x, g, k) / safe(lifted(knnVotes(z, x, g, k), neighbourCount(neighboursOf(z, x, k))))

knnRegress

knnRegress(z, x, y, k) · z queries m×p · x training points n×p · y targets n · k number of neighbours scalar → predictions m

Let \(Z \in \mathbb{R}^{m \times p}\) (the argument z) be the queries with rows \(z_i^{\top}\), \(X \in \mathbb{R}^{n \times p}\) (the argument x) the training points with rows \(x_j^{\top}\), and \(k \in \mathbb{N}\), let \(y \in \mathbb{R}^n\) be the targets, \(N = \operatorname{neighboursOf}(Z, X, k)\) and \(c_i = \sum_j N_{ij}\). Then

\[\operatorname{knnRegress}(Z, X, y, k)_i = \frac{\sum_{j=1}^{n} N_{ij}\, y_j}{c_i + [\, c_i = 0 \,]} .\]

The plain average of the neighbours’ targets:

\[\hat y_i = \frac{\sum_j N_{ij}\, y_j}{\sum_j N_{ij}}\]

Intuition Predicts the average target of the most similar training points: a local mean that follows any shape of relationship without a formula.

Use it when the target changes smoothly but non-linearly with a few scaled features, as in pricing a house from location and size, or when filling a missing value from similar rows. k trades noise (small) against blur (large). Predictions never leave the range of the training targets, so it cannot extrapolate a trend. When nearer neighbours should count for more, use knnWeighted.

nonlinear-regressionmissing-data

def knnRegress(z, x, y, k) ≔ einsum("ij,j->i", neighboursOf(z, x, k), y) / safe(neighbourCount(neighboursOf(z, x, k)))

knnWeighted

knnWeighted(z, x, y, k) · z queries m×p · x training points n×p · y targets n · k number of neighbours scalar → predictions m

Let \(Z \in \mathbb{R}^{m \times p}\) (the argument z) be the queries with rows \(z_i^{\top}\), \(X \in \mathbb{R}^{n \times p}\) (the argument x) the training points with rows \(x_j^{\top}\), and \(k \in \mathbb{N}\), let \(y \in \mathbb{R}^n\) be the targets, \(D_{ij} = \lVert z_i - x_j \rVert^2\), \(N = \operatorname{neighboursOf}(Z, X, k)\), \(W_{ij} = N_{ij} / \max(D_{ij}, 10^{-12})\) and \(w_i = \sum_j W_{ij}\). Then

\[\operatorname{knnWeighted}(Z, X, y, k)_i = \frac{\sum_{j=1}^{n} W_{ij}\, y_j}{w_i + [\, w_i = 0 \,]} .\]

The same average with each neighbour weighted by the inverse of its squared distance, \(w_{ij} = N_{ij} / \max(D_{ij}, 10^{-12})\). The floor prevents a division by zero when a query sits exactly on a training point; that point then takes almost all of the weight.

Intuition Neighbours count in proportion to one over their squared distance, so halving the distance quadruples the weight. The prediction hugs the closest point and nearly reproduces a training target when the query sits on it.

Use it when the selected neighbours lie at very different distances, as in sparse regions or spatial interpolation (inverse-distance weighting of sensor readings, with power 2). The sharp weights make it sensitive to a single noisy training point close to the query; knnRegress is the smoother choice.

interpolationnonlinear-regression

def knnWeighted(z, x, y, k) ≔ einsum("ij,j->i", knnCloseness(z, x, k), y) / safe(einsum("ij->i", knnCloseness(z, x, k)))

Building blocks

knnCloseness(z, x, k) — Let \(Z \in \mathbb{R}^{m \times p}\) with rows \(z_i^{\top}\), \(X \in \mathbb{R}^{n \times p}\) with rows \(x_j^{\top}\), \(k \in \mathbb{N}\), \(D_{ij} = \lVert z_i - x_j \rVert^2\) and \(N = \operatorname{neighboursOf}(Z, X, k)\). Then \(\operatorname{knnCloseness}(Z, X, k)_{ij} = N_{ij} / \max(D_{ij}, 10^{-12})\). The weights used by knnWeighted.

The nearest centroid

The cheapest classifier: compute the mean of each class and assign each query to the closest one. The class means are classMeans from Prelude.Bayes.

centroidPredict

centroidPredict(z, x, g) · z queries m×p · x training points n×p · g one-hot labels n×C → 0/1 mask m×C

Let \(Z \in \mathbb{R}^{m \times p}\) (the argument z) be the queries with rows \(z_i^{\top}\), \(X \in \mathbb{R}^{n \times p}\) (the argument x) the training points, \(G \in \{0,1\}^{n \times C}\) (the argument g) the one-hot labels, and \(\mu_c^{\top}\) the rows of \(\operatorname{classMeans}(G, X)\). Let \(E_{ic} = \lVert z_i - \mu_c \rVert^2\). Then

\[\operatorname{centroidPredict}(Z, X, G)_{ic} = [\, E_{ic} = \min_{c'} E_{ic'} \,] .\]

Marks, for each query, the class whose centroid is nearest in squared Euclidean distance. A tie between centroids marks every tied class.

Intuition Each class is reduced to its mean point, and a query goes to the closest one. The boundary between two classes is the flat surface halfway between their centroids.

Use it when you need a tiny, fast classifier: matching a query costs C distances instead of n. It works when classes are compact blobs of similar spread and fails for elongated, multi-modal or unequally spread classes, where knnClassify or gaussianPredict in Prelude.Bayes (per-class variances) do better. Scale features first.

classificationbaseline-comparison

def centroidPredict(z, x, g) ≔ lowest(squared(z, classMeans(g, x)))

The local outlier factor

An outlier, in this sense, is a point whose neighbours are denser than it is. This makes LOF a local statistic: a point lying loose next to a tight cluster is caught, even when a global measure such as the Mahalanobis distance would not flag it. All quantities are computed within a single set x, and distances are squared Euclidean distances (the textbook LOF uses unsquared distances, so the factors are not numerically the same as those of other libraries).

With \(N_k(i)\) the neighbours of point \(i\), the reachability distance and local density are

\[\operatorname{reach}(i, j) = \max\big(k\text{-dist}(j),\, D_{ij}\big), \qquad \operatorname{lrd}(i) = \frac{|N_k(i)|}{\sum_{j \in N_k(i)} \operatorname{reach}(i, j)}\]

kDistance

kDistance(x, k) · x points n×p · k number of neighbours scalar → distances n

Let \(X \in \mathbb{R}^{n \times p}\) (the argument x) be the points with rows \(x_i^{\top}\) and \(k \in \mathbb{N}\), \(k < n\). Let \(D_{ij} = \lVert x_i - x_j \rVert^2\), \(A = D + 10^{300} I_n\), \(N = \operatorname{neighboursIn}(X, k)\) and \(c_i = \sum_j N_{ij}\). Then

\[\operatorname{kDistance}(X, k)_i = \kappa_i = \max_{j} \big( A_{ij} N_{ij} - 10^{300} (1 - N_{ij}) \big) = \max_{j \,:\, N_{ij} = 1} D_{ij} .\]

For each point, the largest squared distance among its k nearest neighbours (excluding itself).

Intuition How far a point must reach to collect \(k\) neighbours: small inside dense regions, large in sparse ones. It is a local length scale around each point, in squared units here.

Use it when you choose DBSCAN’s radius: sort the values of kDistance(x, m − 1) for m points per neighbourhood (DBSCAN counts the point itself, this does not), find the elbow, and take its square root as eps for dbscan in Prelude.Clustering. It is also a simple isolation score (large means isolated) and the ingredient of localDensity.

anomaly-detectionhyperparameter-choice

def kDistance(x, k)   ≔ rowMost(apartFrom(squared(x, x)) · neighboursIn(x, k) − (1 − neighboursIn(x, k)) · 1e300)

localDensity

localDensity(x, k) · x points n×p · k number of neighbours scalar → densities n

\[\operatorname{localDensity}(X, k)_i = \rho_i = \frac{c_i}{\sum_j N_{ij} R_{ij} + [\, \sum_j N_{ij} R_{ij} = 0 \,]} .\]

The local reachability density of each point: the number of its neighbours divided by the sum of its reachability distances to them.

Intuition Neighbours per unit of reachability distance: high in tight clusters, low in sparse regions. Reachability raises each distance to at least the neighbour’s own k-distance, so a few near-duplicate points cannot make a region look infinitely dense.

Use it when you compare how crowded each point’s surroundings are, mainly as the input to outlierFactor. Its absolute value depends on the data’s scale and on k, so compare it between points of one dataset, never across datasets.

density-estimationanomaly-detection

def localDensity(x, k) ≔ neighbourCount(neighboursIn(x, k)) / safe(einsum("ij,ij->i", neighboursIn(x, k), reachFrom(x, k)))

outlierFactor

outlierFactor(x, k) · x points n×p · k number of neighbours scalar → factors n

\[\operatorname{outlierFactor}(X, k)_i = \frac{\sum_{j=1}^{n} N_{ij}\, \rho_j}{c_i \rho_i + [\, c_i \rho_i = 0 \,]} .\]

The mean local density of each point’s neighbours divided by the point’s own density. Values near one mean the point sits inside a cluster of uniform density; values well above one mark outliers.

\[\operatorname{LOF}(i) = \frac{\sum_{j \in N_k(i)} \operatorname{lrd}(j)}{|N_k(i)| \cdot \operatorname{lrd}(i)}\]

Intuition Compares a point’s density with the density of its neighbours. Near 1 the point is as crowded as they are; well above 1 it is much sparser, so it sits outside their cluster. Because the comparison is local, it flags a point loose beside a dense cluster and leaves alone points in a cluster that is uniformly sparse.

Use it when you screen for anomalies without labels (fraud, sensor faults, data cleaning) and clusters have different densities, which defeats a single global distance threshold. k between about 10 and 20 is a common start, and it must be less than n. Scores use squared distances, so they differ from other libraries’ LOF: rank by them rather than reuse outside thresholds. It holds n×n×n comparisons.

anomaly-detectionfraud-detectiondata-cleaning

def outlierFactor(x, k) ≔ einsum("ij,j->i", neighboursIn(x, k), localDensity(x, k)) / safe(neighbourCount(neighboursIn(x, k)) · localDensity(x, k))

Building blocks

reachFrom(x, k) — Let \(X \in \mathbb{R}^{n \times p}\) with rows \(x_i^{\top}\), \(k \in \mathbb{N}\), \(A = D + 10^{300} I_n\) with \(D_{ij} = \lVert x_i - x_j \rVert^2\), and \(\kappa = \operatorname{kDistance}(X, k)\). Then \(\operatorname{reachFrom}(X, k)_{ij} = \max(\kappa_j, A_{ij})\). The n×n reachability distances: each squared distance raised to at least the target point’s k-distance (the diagonal stays out of reach).

Kernel density

A density estimate with no model: every observation contributes a Gaussian bump of width h, and the bumps are averaged. The bandwidth is the only choice, and it is the caller’s.

kernelDensity

kernelDensity(z, x, h) · z evaluation points m×p · x observations n×p · h bandwidth scalar → densities m

Let \(Z \in \mathbb{R}^{m \times p}\) (the argument z) be the evaluation points with rows \(z_i^{\top}\), \(X \in \mathbb{R}^{n \times p}\) (the argument x) the observations with rows \(x_j^{\top}\), and \(h > 0\) the bandwidth. Then

\[\operatorname{kernelDensity}(Z, X, h)_i = \frac{1}{n\,(2\pi h^2)^{p/2}} \sum_{j=1}^{n} \exp\!\left(-\frac{\lVert z_i - x_j \rVert^2}{2h^2}\right) .\]

The Gaussian kernel density estimate at each row of z, normalised so that it integrates to one over \(p\) dimensions:

\[\hat f(z_i) = \frac{1}{n\,(2\pi h^2)^{p/2}} \sum_{j} \exp\!\left(-\frac{\lVert z_i - x_j \rVert^2}{2h^2}\right)\]

Intuition Place a Gaussian bump of width h on every observation and average them: a smooth histogram that does not depend on where bin edges fall. h is the smoothing: too small gives a spike at each point, too large blurs real peaks together.

Use it when you need a density without assuming a distribution: showing the shape of data, scoring how unusual a new point is (low density means unusual), or class-conditional densities for a classifier. In one dimension Silverman’s rule \(h \approx 1.06\,\hat\sigma\, n^{-1/5}\) is a common start. One h serves every feature, so standardise them first. The data needed grows fast with dimension; beyond a handful of features the estimate degrades.

density-estimationanomaly-detectionvisualisation

def kernelDensity(z, x, h) ≔ einsum("ij->i", rbf(z, x, 1 / (2 · h · h))) / (rows(x) · (2 · π · h · h)^(columns(x) / 2))

Examples

The examples below share one file, Nearby.hb:

open Prelude.Neighbours

fn voteClass(z, x, g, k) ↦ knnClassify(z, x, g, k)
fn voteShares(z, x, g, k) ↦ knnShares(z, x, g, k)
fn nearestCentre(z, x, g) ↦ centroidPredict(z, x, g)
fn averageNearby(z, x, y, k) ↦ knnRegress(z, x, y, k)
fn weightedNearby(z, x, y, k) ↦ knnWeighted(z, x, y, k)
fn outlierScores(x, k) ↦ outlierFactor(x, k)
fn densityAt(z, x, h) ↦ kernelDensity(z, x, h)

Classify two queries by their three nearest neighbours

Six one-dimensional training points form two classes, {0, 1, 2} and {10, 11, 12}. The query 1.5 has all three neighbours in the first class. The query 6.4 is nearest to 10, 2 and 11, so it goes to the second class by two votes to one. The nearest centroid (1 or 11) agrees.

using MLambda.Hilbert.Runtime;
using Examples;

var x = (Tensor)new double[,] { { 0 }, { 1 }, { 2 }, { 10 }, { 11 }, { 12 } };
var g = (Tensor)new double[,] { { 1, 0 }, { 1, 0 }, { 1, 0 }, { 0, 1 }, { 0, 1 }, { 0, 1 } };
var z = (Tensor)new double[,] { { 1.5 }, { 6.4 } };

var classes  = Nearby.VoteClass(z, x, g, 3.0);
var shares   = Nearby.VoteShares(z, x, g, 3.0);
var centroid = Nearby.NearestCentre(z, x, g);

Output (verified; each tensor is shape [2, 2], listed row by row):

classify = [[1, 0], [0, 1]]
shares   = [[1, 0], [0.333333, 0.666667]]
centroid = [[1, 0], [0, 1]]

Average the neighbours’ targets, and see ties at work

With targets y = [0, 1, 2, 10, 11, 12] and a query at 1.5, the points 1 and 2 are equally close. Asking for one neighbour selects both, so the prediction is their average, 1.5. With three neighbours the point 0 joins and the plain average is 1. The distance-weighted average uses weights 4, 4 and 1/2.25, giving \(12 / 8.444 = 1.4211\).

var y = (Tensor)new[] { 0d, 1d, 2d, 10d, 11d, 12d };
var q = (Tensor)new double[,] { { 1.5 } };

var k1       = Nearby.AverageNearby(q, x, y, 1.0);
var k3       = Nearby.AverageNearby(q, x, y, 3.0);
var weighted = Nearby.WeightedNearby(q, x, y, 3.0);

Output (verified):

regress k1 = [1.5]
regress k3 = [1]
weighted k3 = [1.421053]

Find the outlier in a small set

Four evenly spaced points and one far away. With two neighbours each, the four evenly spaced points have a factor of 1 and the distant point stands out.

var pts = (Tensor)new double[,] { { 0 }, { 1 }, { 2 }, { 3 }, { 20 } };
var lof = Nearby.OutlierScores(pts, 2.0);

Output (verified):

[1, 1, 1, 1, 122.6]

Estimate a density from one observation

With a single observation at 0 and bandwidth 1, the estimate is the standard normal density: \(1/\sqrt{2\pi} = 0.398942\) at 0 and \(e^{-1/2}/\sqrt{2\pi} = 0.241971\) at 1.

var observed = (Tensor)new double[,] { { 0 } };
var at       = (Tensor)new double[,] { { 0 }, { 1 } };
var density  = Nearby.DensityAt(at, observed, 1.0);

Output (verified):

[0.398942, 0.241971]