k-NN & Why Distance Gets Weird
Here is the laziest idea in machine learning, and one of the most useful: to label a new case, find the handful of training points nearest to it and let them vote. No equation, no training step, no coefficients — just "who are my neighbors, and what are they?" It works surprisingly well, right up until two things bite: the scale of your features, and the strange geometry of high-dimensional space.
Prediction by neighborhood
k-nearest-neighbors (k-NN) stores the training data and does all its work at prediction time. For a new point, it measures the distance to every training point, keeps the k closest, and predicts the majority class among them (or, for regression, their average). There is no model to fit — the data is the model. That makes k-NN a nonparametric method: it assumes nothing about the shape of the data (no normality, no straight-line boundary) and can trace a wiggly boundary that a linear model never could.
k is the smoothness dial
The one real choice is k, and it sets the bias–variance balance directly. At k = 1 every point rules its own tiny territory, so the boundary wraps around individual points, including noisy, mislabeled ones. That's low bias but high variance: the model has essentially memorized the training set. Crank k up and each prediction averages over a wider neighborhood, so the boundary smooths out; push it toward k = n and every point gets the same prediction — the overall majority class. Somewhere in between is the sweet spot, and you find it with cross-validation, not a formula.
Scaling is not optional
Because k-NN ranks neighbors by distance, the scale of each feature decides how much it counts. Put income (0–100,000) next to a 1–5 rating and the Euclidean distance is essentially just the income difference — the rating contributes nothing, however predictive it is. Standardizing every feature to a comparable range first is mandatory, not a nicety. The interactive below has a switch that "forgets" to scale one feature; flip it and watch a good boundary collapse into meaningless stripes.
📍 k-NN boundary explorer
Two classes (indigo and orange). The shaded regions are what k-NN would predict everywhere. Slide k from jagged (k = 1, memorizing) to smooth. Then hit the unscaled feature switch (one feature blown up ×100) and watch neighbors get chosen by that axis alone, wrecking the boundary.
The curse of dimensionality
k-NN leans entirely on "near" meaning something. In two or three dimensions it does. Add features, and geometry turns treacherous: volume grows so fast that data becomes hopelessly sparse, and every point drifts toward being equally far from every other — the nearest neighbor is barely nearer than the farthest. When all distances are alike, "nearest" carries no information, and distance-based methods fail without warning.
One exact picture makes it vivid. Take the ball that just fits inside a unit cube (radius ½, touching each face). What fraction of the cube's volume does it fill? In 2-D, most of it; by 10-D, almost none — the volume has fled into the cube's corners, where the ball can't reach:
🫥 Share of a unit cube within distance ½ of its center
Computed exactly as the volume of a d-dimensional ball of radius ½ (via the gamma function). It doesn't shrink so much as vanish.
That is why more features is not automatically better for k-NN: past a point, extra dimensions dilute the signal until neighbors are meaningless. The escapes are feature selection, dimensionality reduction, or a ruler better matched to your data — anything that gets you back to a space where "close" means "similar."
Which distance?
"Nearest" presumes a ruler, and straight-line Euclidean distance is only the default one. Swap it and you change who your neighbors are.
Manhattan distance (also called L1, or city-block) adds up the absolute differences one feature at a time instead of squaring them. Squaring lets a single wildly discrepant feature dominate the total, so Manhattan is the steadier choice when a few of your features are noisy. Cosine distance throws away magnitude and compares direction alone, so two cases with the same profile at different intensities count as identical. That is what you want for text, and for questionnaire profiles where one person simply uses the top of every scale.
The two rulers can disagree completely. Take a five-item profile of (5, 4, 5, 4, 5) and compare it with two others: one of exactly the same shape at a fifth of the intensity, (1, 0.8, 1, 0.8, 1), and one of a genuinely different shape at a similar intensity, (5, 4, 1, 4, 1). Euclidean distance puts the same-shape case farther away, 8.28 against 5.66, because all it sees is the size gap. Cosine reverses the verdict, scoring the same-shape case a perfect 1.000 similarity against 0.843.
Gower distance covers the case none of these handles: a table mixing numbers, categories, and yes/no flags. It scores each column by a rule suited to that column's type and averages the results, which is the usual answer when your data look like a real research spreadsheet rather than a tidy matrix of measurements.
Choosing the metric also softens the curse a little, without lifting it. Repeat the nearest-versus-farthest comparison on uniform random points and the farthest of 500 points sits about 47 times as far away as the nearest in 2 dimensions, 3.4 times in 10, and only 1.16 times in 500. Manhattan holds slightly more of that contrast than Euclidean at every dimension (1.20 against 1.16 at 500 features), which is why L1 is often recommended for wide data. Slightly more of almost nothing is still almost nothing, so treat it as a tie-breaker and not a rescue.
Why it matters: k-NN is the clearest window onto two ideas that haunt all of machine learning. First, distance-based models are only as sensible as your feature scaling — standardize before you compute a single neighbor. Second, high-dimensional space is nothing like the 2-D pictures in your head: as dimensions climb, data thins out and "nearest" loses meaning, so reducing dimensions is often the difference between a model that works and one that only looks like it should.
Common questions
How do I choose k in k-NN?
Tune it with cross-validation rather than a rule of thumb, because k is the bias–variance dial. A small k (k = 1 at the extreme) follows every point, giving a jagged boundary that memorizes noise — low bias, high variance. A large k averages over many neighbors, giving a smooth, stable boundary that can wash out real structure (high bias, low variance). Try a range of k on held-out data and pick where accuracy peaks; a common practical range is a few up to roughly the square root of the sample size. Use odd k for two-class problems to avoid tied votes, and remember the best k depends on how noisy your data are, not on any fixed formula.
Does k-NN need normally distributed data?
No. k-NN is nonparametric: it makes no assumption about the shape of the distribution, no normality, no linearity. What it absolutely does need is sensible feature scaling, because it ranks neighbors by distance and distance is scale-sensitive. If one variable is measured in thousands (say annual income) and another from 1 to 5 (a Likert item), the large-scale variable dominates the distance and the small-scale one is effectively ignored, no matter how predictive it is. Standardize or normalize every feature to a comparable range first. Beyond scaling, k-NN also struggles as the number of features grows, because of the curse of dimensionality.
My training set has 200,000 rows. Will k-NN still work?
It will work, but it may be too slow to be practical, and the reason is structural rather than fixable by faster hardware. k-NN does no work at training time and all of it at prediction time: every new case is compared against every stored case, so one prediction costs roughly n × d arithmetic, and the whole training set has to stay in memory. Spatial indexes (KD-trees and ball trees, both built into scikit-learn's KNeighborsClassifier) fix this by ruling out whole regions without measuring them, cutting a typical query to something closer to log n. The catch is that they rely on the same geometry the curse destroys, so their advantage fades as features accumulate and past roughly 20 features they perform little better than brute force. In that situation reduce the dimensions first, thin the training set, or switch to an approximate nearest-neighbor library that trades exactness for speed.