18 · KNN regression + KD-tree / Ball-tree acceleration
Average the k nearest targets for regression, then use KD-trees and Ball-trees to turn O(n) lookups into O(log n) — making KNN practical on real datasets.
KNN regression averages the targets of the k nearest neighbors — and KD-trees / Ball-trees speed up O(n) lookups to O(log n).
Without this:
Without the tree-based acceleration, KNN is too slow to use on any dataset larger than a toy.
KNN regression extends the classification idea to continuous targets. For a new query point x:
- Find the K nearest training points by distance.
- Return their mean target value as the prediction: ŷ = (1/K) Σ yᵢ
No line, no polynomial, no explicit function — just local averaging. This makes KNN regression a non-parametric, piecewise-smooth estimator. The prediction curve will look like a step function (k=1) or a smoothed version thereof (larger k).
Uniform vs distance-weighted voting
With uniform weights (default), all K neighbors contribute equally. With distance-weighted voting, closer neighbors count more:
wᵢ = 1 / d(x, xᵢ) (larger weight for closer points)
ŷ = Σ wᵢ yᵢ / Σ wᵢ
Distance weighting produces a smoother, more accurate regression curve — especially near training points.
The brute-force bottleneck
Scanning all n training points for every query is O(n·d). For n = 100 000 and d = 20, a single query requires 2 million distance computations. Batch prediction over 10 000 test points requires 20 billion — impractical.
KD-trees (k-dimensional trees)
A KD-tree recursively splits the feature space along axis-aligned hyperplanes, forming a binary tree. At each node it splits along the feature with the greatest variance, at the median. Searching the tree prunes entire subtrees that can't contain any of the K nearest neighbors.
- Build time: O(n log n)
- Query time: O(log n) on average for low-dimensional data
- Degrades to O(n) when d > ~20 (the curse of dimensionality means few subtrees can be pruned)
Ball-trees
Ball-trees partition data into nested hyperspheres instead of axis-aligned boxes. They are more expensive to build but maintain their O(log n) query time on higher-dimensional or non-Euclidean data (e.g., Haversine for geo-coordinates, cosine for text).
sklearn's auto selection
KNeighborsRegressor(algorithm='auto') picks the best algorithm based on input dimensions: KD-tree below ~20 features, Ball-tree above, brute force for very small n. You rarely need to set this manually.
Python (in browser)
KNN regression with k=5 predicts the mean of the 5 nearest training targets. The result is a piecewise-smooth curve (not a parametric function). Notice it tracks the true sin(x) well in the center (dense training data) but deviates at the edges where fewer points anchor the prediction.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Distance-weighted voting (`weights='distance'`) assigns weight wᵢ = 1/dᵢ — points right next to a training sample snap exactly to that sample's target. This produces a smoother curve in dense regions. In very noisy settings, uniform weighting can be more robust because it averages out individual noisy points rather than over-weighting the noisiest nearest neighbor.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
At d=10 (well below the ~20-dimension threshold), KD-tree achieves roughly 5–15× speedup over brute force. The speedup comes from pruning subtrees: if the nearest point in a subtree's bounding box is farther than the current K-th nearest neighbor, the entire subtree is skipped. This pruning becomes ineffective as d grows.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
For online recommendation systems or semantic search at scale (n > 1M, d = 768 from embeddings), none of the sklearn algorithms are fast enough — you need approximate NN libraries like FAISS or HNSW that trade a tiny accuracy loss for 100–1000× speedup.
KNN regression with k=1 will produce predictions that are:
- KNN regression predicts ŷ = mean(y of K nearest neighbors). `weights='distance'` gives smoother predictions by up-weighting closer neighbors.
- KD-trees partition space along axis-aligned planes — O(log n) queries for d < 20. Ball-trees use hyperspheres — better for d ≥ 20 or non-Euclidean metrics.
- `algorithm='auto'` in sklearn selects the right backend automatically; you almost never need to override it.
- For production at scale (n > 100k), replace sklearn KNN with approximate NN libraries (FAISS, HNSW, Annoy) to achieve sub-millisecond inference.
Image retrieval (find similar images via FAISS, which is approximate KNN); recommendation (similar users/items); price prediction in real estate ('comparable sales' is literally KNN regression).
If you remove it: Many recommendation and retrieval systems can't be built — they're all KNN at heart.