kNN and the Curse of Dimensionality
You have spent the last courses predicting numbers with regression. Classification is the other half of supervised learning: instead of "how much?", it answers "which kind?". And the most intuitive classifier ever invented needs no equation at all. It just looks at who you sit next to.
Picture a music app that has labeled thousands of past tracks as chill or workout. A brand-new song arrives with no label. To guess its vibe, the app finds the handful of past songs most similar to it and lets them vote. That is k-nearest neighbors, and it is what this lesson builds, then breaks.
By the end you will be able to:
- Explain how kNN labels a new case by the majority vote of its nearest neighbors
- Measure "nearest" with a distance metric, choose k, and run the whole thing in R
- Say why you must scale your features, and why piling on more of them eventually backfires
Prerequisites: you can run R and read its output, and you know what a training set is and what a classifier does (the ML Workflow course).
Known by the company it keeps
Here is the entire idea of kNN in one sentence: to label a new point, find the k training points closest to it and take the majority vote of their labels. No model is fit, no curve is drawn. The training data is the model.
In the chart, each dot is a past song the app already labeled. The red dots (class A) are chill tracks, clustered at low tempo and low energy in the lower left. The blue dots (class B) are workout tracks, up at high tempo and high energy. The square is our new, unlabeled track.
Click anywhere to move the new track around, and slide k. Watch the k closest dots light up, cast their votes, and color the square with whichever class wins. Drop it deep in the red cluster and it is confidently chill; drag it into the blue and it flips to workout; park it on the border and the vote gets interesting.
Distance is just a ruler
"Closest" only means something once we put a number on it. With two features, tempo and energy, every song is a point on a plane, and the natural ruler between two points is the straight-line Euclidean distance, the length of the line you would draw between them.
For a new track \(\mathbf{q}\) and a known song \(\mathbf{x}\), each described by \(p\) features, that distance is
\[ d(\mathbf{x}, \mathbf{q}) = \sqrt{\sum_{j=1}^{p} (x_j - q_j)^2} \]
where \(p\) is the number of features (here \(p = 2\)), \(x_j\) is the \(j\)-th feature of the known song, and \(q_j\) is the same feature of the new track. Subtract feature by feature, square each gap so positives and negatives both count, add them up, take the square root. With \(p = 2\) this is exactly the Pythagorean theorem.
Each lesson runs in a fresh R session, so we build a small labeled playlist right here, then measure the distance from one new track to every song:
The five closest songs are all chill. So this new track's neighborhood votes chill, unanimously.
What does kNN actually do?
You hand a trained kNN classifier a brand-new track and ask for its label. What does it do at that moment?
Count the votes in R
The hard part, the distances, is already done and stored in songs$dist. Finishing kNN is just two moves: sort the songs from nearest to farthest, keep the first k, and tally their moods. Fill in the blank so it takes the k nearest.
Show answer
k <- 5
ordered <- order(songs$dist) # row indices, nearest first
nearest <- songs$mood[ordered[1:k]] # the moods of the k nearest songs
table(nearest) # tally the votes
names(which.max(table(nearest))) # the winning class
#> nearest
#> chill
#> 5
#> [1] "chill"Choosing k: jagged versus smooth
kNN has essentially one dial: k, how many neighbors get a vote. It matters more than it looks.
- Small k (k = 1) trusts the single closest song. The boundary between classes becomes jagged and twitchy, because one mislabeled or oddball track in a region flips every prediction near it. Highly flexible, easily fooled by noise.
- Large k averages over many neighbors. The boundary smooths out and steadies, but push k too high and you start dragging in songs from the other cluster, blurring real distinctions and dulling local detail.
This is the same bias-variance tradeoff that runs through all of machine learning: tiny k is low bias and high variance (it overfits the noise), big k is high bias and low variance (it oversmooths). The sweet spot is in between and is usually found by trying several values and checking which generalizes best, the subject of cross-validation later in this track.
Slide k in the widget below. At k = 1 the prediction snaps to the nearest single dot; crank k up and the vote becomes a steadier consensus of the whole neighborhood.
Why not always k = 1?
A teammate argues: "The single closest song is the most similar one, so k = 1 must be the most accurate choice." Where does that reasoning go wrong?
Distance has units: scale your features
Euclidean distance adds up feature gaps, but our two features live on wildly different scales. Tempo ranges across dozens of BPM; energy ranges from 0 to 1. In the raw sum, a 30 BPM gap contributes \(30^2 = 900\) while a huge 0.5 energy gap contributes only \(0.5^2 = 0.25\). Tempo drowns energy out completely, so kNN is secretly classifying on tempo alone.
Watch it bite. Here is a different new track at 120 BPM but high energy 0.85, a track that clearly feels like a workout:
Raw kNN calls this high-energy track chill (4 votes to 1), purely because its tempo of 120 happens to sit near a few mid-tempo chill songs. The energy reading, the very thing that screams "workout", barely moved the distance. Now put both features on equal footing by standardizing them (subtract the mean, divide by the standard deviation, turning each into a z-score) and recompute:
After scaling, the five nearest songs are all workout, and the prediction flips to the right answer. Same data, same k, same query: the only change was giving energy a fair say.
The curse of dimensionality
So far so good in two dimensions. Surely adding more features can only help kNN see finer similarities? This is where intuition fails, and the failure has a name: the curse of dimensionality.
The trouble is geometric. As you add features, the space inflates so fast that your training points spread thin, and a strange thing happens to distance itself: in high dimensions, the nearest point and the farthest point end up almost the same distance away. Formally, the ratio of the smallest distance to the largest distance creeps toward 1,
\[ \frac{d_{\min}}{d_{\max}} \longrightarrow 1 \quad \text{as } p \to \infty \]
and once that ratio is near 1, "nearest neighbor" no longer picks out anything special: everything is roughly equidistant, so the vote is barely better than guessing. We can watch it happen. The code below scatters random points in spaces of growing dimension and measures, on average, how the nearest point compares with the farthest:
At 2 features the nearest point is much closer than the farthest (ratio 0.03), exactly the contrast kNN relies on. By 500 features the nearest is 87% as far as the farthest: the neighborhood has dissolved. This is why kNN, so natural in low dimensions, struggles on raw high-dimensional data. Three practical responses:
- Use fewer, better features. Drop noise; keep the handful that actually separate the classes. Quality beats quantity for kNN.
- Reduce dimensions first. Project the data into a few informative directions with something like PCA before measuring distance.
- Get more data, or change tools. Denser data slows the curse; and in genuinely high-dimensional problems, models that ignore irrelevant features (trees, regularized linear models) often beat kNN outright.
Diagnose the drop
Your kNN model works well on tempo and energy. You add 200 more audio features, most of them noise, and accuracy gets worse. A teammate says, "Just standardize all the features and it will be fine." Are they right?
References
A few authoritative places to take this further:
- Cover and Hart (1967), "Nearest Neighbor Pattern Classification" (IEEE) - the original paper that put kNN on a formal footing.
- An Introduction to Statistical Learning, ch. 2 and 4 (free PDF) - the gentlest treatment of kNN, k, and the bias-variance picture, with R labs.
- Beyer et al. (1999), "When Is Nearest Neighbor Meaningful?" - the paper that proved distances concentrate in high dimensions.
- The Elements of Statistical Learning, ch. 13 (free PDF) - prototype and nearest-neighbor methods, with the full math.
Lesson 1 complete
You can now classify a new case by the majority vote of its nearest neighbors, measure "nearest" with a scaled distance, choose k with the bias-variance tradeoff in mind, and explain why heaping on features eventually makes "nearest" meaningless.
Next, Lesson 2: Naive Bayes for tabular and text. Instead of measuring distance, it reasons with probabilities, asking which class makes the evidence most likely, and it shrugs off the high-dimensional data that just sank kNN.