Nearest neighbors

Problem

Most models compress the training set into parameters: a line, a tree, a network. That compression is an assumption about the shape of the answer. Sometimes we would rather not assume a shape at all and just say "points that look alike should get alike labels". Nearest neighbors does exactly that. It needs a way to say what "look alike" means (a distance), a rule to turn nearby labels into a prediction, and a way to find nearby points fast once the training set has millions of rows.

Intuition

To label a new point, find the k training points closest to it and let them vote. With k = 1 the prediction copies the single closest point, so the decision boundary bends around every training example, noise included. Larger k averages over a wider neighborhood, giving smoother boundaries but blurring small regions of the other class. This is the bias-variance tradeoff with one knob. Training is free (store the data); all the work happens at prediction time.

The diagram shows 16 training points in two classes and a query at (4.8, 5.0). Each dashed circle encloses the k nearest points for one value of k, and the vote changes as the circle grows.

Mechanics

Distance

Almost everything uses the Minkowski distance with exponent p:

d_p(a, b) = (Σ_j |a_j − b_j|^p)^1/p

p = 2 is Euclidean distance (scikit-learn's default, metric="minkowski", p=2), p = 1 is Manhattan distance, and p → ∞ is Chebyshev distance, the largest single-coordinate gap. For p ≥ 1 these are true metrics (the triangle inequality holds), which is what lets trees prune. Each coordinate contributes on its own scale, so a feature measured in thousands swamps one measured in fractions. That is why k-NN almost always sits behind standardization. For text and embeddings, cosine distance on normalized vectors is more common. It ranks neighbors the same way as Euclidean distance on unit vectors (see vectors and dot products).

Vote and weights

Given the k nearest training points with labels y_i and distances d_i, a classifier returns the label with the largest total weight, and a regressor returns the weighted mean:

ŷ = argmax_c Σ_i w_i·[y_i = c]     ŷ = Σ_i w_i y_i / Σ_i w_i

With weights="uniform", every w_i = 1. With weights="distance", scikit-learn's _get_weights sets w_i = 1/d_i. If the query lands exactly on one or more training points, those points get weight 1 and the rest get 0, which avoids dividing by zero. predict_proba returns each class's share of the total weight. When two labels tie on uniform votes, predict takes the mode, which picks the class that sorts first. The docstring also warns that when neighbors k and k+1 are equally far away but have different labels, the result depends on the order of the training data.

Finding the neighbors

Brute force measures the query against all n training points: O(n·d) per query, and trivially parallel. Trees spend O(n log n) once, at fit time, so that most queries can skip most of the data.

• A KD tree splits the node's points at the median of the dimension with the largest spread (find_node_split_dim, then partition_node_indices), and stores each node's bounding box. Nodes live in a flat array, and node i's children are 2i+1 and 2i+2.
• A ball tree uses the same splitting, but each node stores a centroid and a radius, the largest distance from the centroid to any of the node's points. Its lower bound, max(0, d(q, centroid) − radius), works for any true metric, not just axis-aligned ones.

Before building, the tree fixes its depth: n_levels = int(log2(max(1, (n − 1) / leaf_size)) + 1) and n_nodes = 2**n_levels − 1. Splitting at the median then leaves every leaf with between leaf_size and 2·leaf_size points. The query is depth-first with a max-heap of the best k distances so far. A node whose lower bound already exceeds the k-th best distance is trimmed with all its points. A leaf is scanned point by point. Otherwise the query visits the nearer child first, so the heap tightens early and prunes more. Internally the KD tree compares "reduced" distances (squared Euclidean, which keeps the same order) to skip square roots.

The left half splits on y at 4 and the right half at 7, so each leaf box shown here is the tight box around its own four points, which is what init_node stores and min_rdist measures against.

Worked example

Implementation

from sklearn.model_selection import GridSearchCV
from sklearn.neighbors import KNeighborsClassifier, KDTree
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

# Scale first: every feature contributes to the distance on its own scale.
model = make_pipeline(StandardScaler(), KNeighborsClassifier())
search = GridSearchCV(
    model,
    {"kneighborsclassifier__n_neighbors": [1, 3, 5, 7, 9, 15],
     "kneighborsclassifier__weights": ["uniform", "distance"]},
    cv=5,
)
search.fit(X_train, y_train)
proba = search.predict_proba(X_test)        # (m, n_classes), vote shares

# The tree on its own, for retrieval.
tree = KDTree(X_train, leaf_size=30)
dist, ind = tree.query(X_test[:3], k=5)     # each (3, 5), nearest first

Fitting the scaler inside the pipeline keeps the test folds out of the means and variances (see data leakage). The tree is pure Cython with no learned parameters. Its only choices are the metric and leaf_size, which trades tree depth against per-leaf brute force. Larger leaf_size means a shallower tree and more scanning, smaller means more pruning overhead. Results are identical either way.

Tradeoffs

• No training, slow prediction. Fit is cheap, but the model is the data: memory grows with n, and each query costs anywhere from O(log n) (a tree in low dimension) to O(n·d) (brute force).
• Flexible boundaries. k-NN can draw any shape of class region and adapts as data is added, but small k memorizes noise (overfitting) and large k washes out minority regions.
• Everything rides on the distance. Unscaled or irrelevant features distort neighborhoods. k-NN has no built-in feature selection, so one noisy column hurts every prediction.
• Exact trees fade with dimension. As distances concentrate, box and ball bounds stop ruling nodes out, which is why "auto" switches to brute force above 15 features. Embedding search at hundreds of dimensions and millions of vectors uses approximate indexes instead. They trade a little recall for orders of magnitude in speed.
• Calibration. predict_proba can only take values j/k with uniform weights, so with k = 5 every probability is a multiple of 0.2.

Connections

References

• Cover and Hart. Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 1967.
• Bentley. Multidimensional Binary Search Trees Used for Associative Searching. Communications of the ACM, 1975 (the KD tree).
• Friedman, Bentley and Finkel. An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software, 1977.
• Omohundro. Five Balltree Construction Algorithms. ICSI Technical Report, 1989.
• Beyer, Goldstein, Ramakrishnan and Shaft. When Is "Nearest Neighbor" Meaningful? ICDT, 1999.
• Hastie, Tibshirani and Friedman. The Elements of Statistical Learning, 2nd ed., Springer, 2009: section 2.5 (local methods in high dimensions) and chapter 13.
• scikit-learn 1.9.1: KNeighborsClassifier, KNeighborsRegressor, NearestNeighbors, _binary_tree.pxi.tp.