k-NN & Why Distance Gets Weird
One of the simplest ideas in machine learning is also one of the most useful: to label a new case, find the few training points nearest to it and let them vote. There is no equation, no training step and no coefficients, only the question "who are my neighbors, and what are they?" It works surprisingly well, but two things can break it: 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 separate model to fit: the stored 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 it can follow a curved boundary that a linear model cannot.
Choosing k
The main choice is k, and it sets the bias–variance balance directly. At k = 1 each training point decides the prediction in a small region around itself, so the boundary wraps around individual points, including noisy, mislabeled ones. That is low bias but high variance: the model has memorized the training set. Increase k and each prediction averages over a wider neighborhood, so the boundary becomes smoother. At k = n every point gets the same prediction, the overall majority class. The best k lies somewhere in between, 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, and the rating contributes almost nothing, however predictive it is. So you must standardize every feature to a comparable range first. The widget below has a switch that leaves one feature unscaled. Switch it on and a good boundary becomes meaningless stripes.
📍 k-NN boundary explorer
Two classes (indigo and orange). The shaded regions are what k-NN would predict everywhere. Move k from jagged (k = 1, memorizing) to smooth. Then turn on the unscaled feature switch (one feature multiplied by 100): neighbors are chosen by that axis alone, and the boundary breaks down.
The curse of dimensionality
k-NN depends on "near" meaning something. In two or three dimensions it does. As you add features, volume grows so fast that the data become very sparse, and every point becomes almost equally far from every other: the nearest neighbor is barely nearer than the farthest. When all distances are alike, "nearest" tells you nothing, and distance-based methods fail without any warning.
A simple calculation shows how strange this is. 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. Nearly all the volume is in the cube's corners, outside the ball:
🫥 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). By d = 100 it is effectively zero.
So more features do not automatically help k-NN. Past a point, extra dimensions dilute the signal until the nearest neighbors are no more similar than any other points. The remedies are feature selection, dimensionality reduction, or a distance measure better suited to your data: anything that gets you back to a space where "close" means "similar."
Which distance?
"Nearest" depends on how you measure distance, and straight-line Euclidean distance is only the default. Change the measure 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, without squaring them. Squaring lets a single feature with a very large difference dominate the total, so Manhattan is the steadier choice when a few of your features are noisy. Cosine distance ignores magnitude and compares direction only, so two cases with the same profile at different intensities count as identical. That suits text, and questionnaire profiles where one person simply uses the top of every scale.
The two measures can disagree completely. Take a five-item profile of (5, 4, 5, 4, 5) and compare it with two others. One has exactly the same shape at a fifth of the intensity, (1, 0.8, 1, 0.8, 1). The other has a clearly 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 that case differs in level on every item. Cosine gives the opposite answer: the same-shape case has a perfect similarity of 1.000, the other 0.843.
Gower distance handles a case none of these can: a table that mixes numbers, categories and yes/no flags. It scores each column with a rule suited to that column's type and averages the results. It is the usual choice when your data look like a typical research spreadsheet and not a tidy matrix of measurements.
The choice of distance also weakens the curse slightly, but does not remove it. Repeat the nearest-versus-farthest comparison on uniform random points: the farthest of 500 points is 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 distance keeps slightly more of that contrast than Euclidean at every dimension (1.20 against 1.16 at 500 features), so L1 is often recommended for data with many features. The gain is small, so treat it as a tie-breaker, not a solution.
Why it matters: k-NN shows two problems that affect all of machine learning. First, a distance-based model is only as sensible as your feature scaling, so standardize before you compute a single neighbor. Second, high-dimensional space is nothing like the 2-D pictures in your head. As dimensions increase, the data thin out and "nearest" loses its meaning, so reducing the number of dimensions often decides whether the model works at all.
Common questions
How do I choose k in k-NN?
Tune it with cross-validation rather than a rule of thumb, because k sets the balance between bias and variance. 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 runs from a few up to roughly the square root of the sample size. Use odd k for two-class problems to avoid tied votes. The best k depends on how noisy your data are, so no fixed formula can give it.
Does k-NN need normally distributed data?
No. k-NN is nonparametric: it makes no assumption about the shape of the distribution, so it needs neither normality nor linearity. It does need sensible feature scaling, because it ranks neighbors by distance and distance depends on scale. 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. The small-scale one is then 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 faster hardware will not fix the cause. 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 takes roughly n × d arithmetic operations, and the whole training set has to stay in memory. Spatial indexes (KD-trees and ball trees, both built into scikit-learn's KNeighborsClassifier) speed this up by ruling out whole regions without measuring them, cutting a typical query to something closer to log n. But they depend on the same geometry that the curse of dimensionality destroys, so their advantage fades as features are added, and past roughly 20 features they do little better than brute force. Then reduce the dimensions first, use fewer training cases, or switch to an approximate nearest-neighbor library, which gives up exactness for speed.