Why do a k-NN model's nearest and farthest neighbours become nearly equidistant as features are added?
answer
- every feature adds one more distance term
- mean grows with d, spread with sqrt(d)
- relative spread shrinks like 1 over sqrt(d)
- far-over-near contrast collapses toward zero
- intrinsic dimension, not column count
basics
~20 sEuclidean distance sums one term per feature, so its typical size grows with the number of features while its spread grows only like the square root. The relative gap between the nearest and the farthest point therefore shrinks toward zero.
solid answer
~50 sThe Euclidean distance between two rows is the square root of a sum with one term per feature. Add features and the expected value of that sum grows roughly in proportion to the number of features, while its standard deviation grows only like the square root — so every pairwise distance piles up around the same typical value. The practical diagnostic is the ratio `(farthest - nearest) / nearest`: in two dimensions it is large, and by a few hundred dimensions it can drop below 0.2, meaning the most distant row is barely further away than the closest one. Once that contrast is gone the `k` nearest neighbours are close to an arbitrary sample of the data, distance-weighted voting stops discriminating, and any fixed-radius rule returns either nothing or everything. What matters is the number of *informative* directions, not the raw column count — noise features add distance without adding signal.
code
python · 15 linesimport random, math
def contrast(d, n=500, seed=0):
rng = random.Random(seed)
q = [rng.random() for _ in range(d)]
dists = []
for _ in range(n):
p = [rng.random() for _ in range(d)]
dists.append(math.sqrt(sum((a - b) ** 2 for a, b in zip(q, p))))
lo, hi = min(dists), max(dists)
return lo, hi, (hi - lo) / lo
for d in (2, 10, 100, 1000):
lo, hi, c = contrast(d)
print(f"d={d:5d} nearest={lo:.3f} farthest={hi:.3f} contrast={c:.2f}")go deeper
Be ready to say that adding features makes every point look about equally far away, so nearest neighbours stop being meaningfully near. Knowing the phrase distance concentration and that it hurts distance-based models is enough here.
Explain the mechanics: distance is a sum over features, its mean grows with the feature count while its spread grows like the square root, so relative contrast falls like one over the square root of the dimension. Name the near/far contrast ratio as the way to measure it.
Show you would measure the contrast ratio on real data before blaming the curse, and that you distinguish ambient columns from intrinsic dimension. Explain which downstream pieces break first — distance weighting, radius rules, neighbour stability.
Own the call about model family. If the feature space is inherently wide and the informative directions are few, argue for a family that selects features internally rather than funding an ever-larger data-collection effort that exponential sample requirements will defeat.
## The mechanism Take two rows `x` and `y` with `d` features each. Their squared Euclidean distance is ``` D2 = (x1 - y1)^2 + (x2 - y2)^2 + ... + (xd - yd)^2 ``` That is a sum of `d` non-negative terms. If the features are on comparable scales and are not strongly redundant, each term contributes about the same expected amount, so `E[D2]` grows roughly in proportion to `d`. The *variability* of the sum behaves differently: adding independent-ish terms makes the standard deviation grow only like `sqrt(d)`, because the fluctuations partly cancel. Put those together and the relative spread of distances — standard deviation divided by mean — shrinks like `1 / sqrt(d)`. The consequence has a name: **distance concentration**. Every pair of points ends up at nearly the same distance from every other pair. The usual way to quantify it on a real dataset is the near/far contrast for a query point `q`: ``` contrast = (max_i dist(q, x_i) - min_i dist(q, x_i)) / min_i dist(q, x_i) ``` With 500 uniformly-drawn points, that number is in the tens for two features, close to 2 for ten features, under 0.5 for a hundred, and around 0.1 for a thousand. At `contrast = 0.1` the farthest row in your training set is only ten percent further from the query than the closest one. "Nearest neighbour" is still well-defined arithmetically, but it has stopped meaning "similar". ## Why it hurts a k-NN model specifically k-NN has no learned parameters — the distance function *is* the model. Three things degrade at once: - **The neighbour set becomes near-arbitrary.** When all candidates sit inside a thin shell of distances, tiny amounts of measurement noise reshuffle which `k` rows win, so the prediction is unstable from run to run and from row to row. - **Distance weighting loses its grip.** Weighting a neighbour's vote by `1/dist` only helps if distances differ; when they are all within a few percent of each other, every neighbour gets essentially the same weight. - **Radius rules break.** Any threshold — "predict only if a neighbour is within `r`" — either captures nothing or the whole dataset, because the distance distribution is a narrow spike rather than a spread. ## The companion problem: sample sparsity Concentration is about geometry and holds even with unlimited data. Alongside it runs a data-volume problem: to keep the same density of points per region of space, the row count has to grow exponentially with `d`. Chop each feature into ten bins and two features give 100 cells while ten features give ten billion; the same number of rows per cell would need a hundred million times more data. Real datasets are therefore *empty* in high dimensions, and a "local" neighbourhood that contains `k` points is not local at all — it spans most of the range of every feature. ## When the ambient dimension is not the real dimension A dataset with 900 columns is not automatically cursed. What governs concentration is the **intrinsic dimension** — the number of genuinely independent directions the data varies along. Highly correlated columns, data lying on a curved low-dimensional surface, or a handful of dominant features all keep the effective dimension well below the column count, and k-NN can work fine. Conversely, a 900-gene expression panel measured on 200 patients, where most genes vary independently of the outcome, is the bad case: the nearest and farthest patient sit at almost the same distance, and the neighbour ranking is decided by accumulated noise across hundreds of irrelevant genes. That also tells you which features do the damage. An added feature that separates the classes increases the numerator and denominator of the contrast unequally and can *help*. An added feature that is pure noise adds variance to every distance and dilutes the informative ones. Concentration is really the symptom; **signal dilution** is the disease. ## What you can do about it In rough order of effect: cut the number of columns down to the informative ones, or project the data onto fewer dimensions before measuring distance; restrict the distance to a domain-chosen subset of features; weight features by how much they matter rather than treating all of them alike; or drop distance-based prediction for a model family that selects features internally, such as a regularised linear model or a tree ensemble. Collecting more rows is the option that does *not* work — you would need exponentially many. ## How to check it before you argue about it Sample a few hundred query points, compute their nearest and farthest distances against the training set, and look at the distribution of the contrast ratio. If the median contrast is small — well under 1 — your feature space is too wide for the metric, and no amount of tuning `k` will fix it. Repeating that measurement after a dimensionality cut is also how you prove the cut helped.
- Does collecting more training rows fix distance concentration?Not in any practical sense. More rows do pull the nearest neighbour closer and restore some contrast, but the number needed to keep a fixed density grows exponentially with the feature count, so past a few dozen informative dimensions the required dataset is unreachable. Concentration is a property of the geometry, not of the sample size, so the fix is fewer dimensions rather than more rows.
- Which features make the problem worse — noisy ones or informative ones?Uninformative ones. Every feature adds a term to the distance sum, but only a feature related to the target adds separation between the classes. A noise feature adds variance to every pairwise distance and dilutes the contribution of the informative ones, so a model that was fine on six good columns can degrade badly once you bolt on two hundred irrelevant ones.
- When does a dataset with hundreds of columns still work fine with k-NN?When its intrinsic dimension is low: columns that are strongly correlated, data lying on a curved low-dimensional surface, or a handful of dominant features all mean the data occupies far fewer effective directions than the column count suggests. Measure the contrast ratio rather than counting columns — the ambient dimension is a poor predictor of whether distances still discriminate.
Averaging more and more noisy measurements makes every average look alike. High-dimensional distance is that average, so every pair of points ends up looking equally far apart.
saying these in an interview costs you the question
- Says more training data always fixes the curse of dimensionality
- Claims all distances become literally identical rather than relatively similar
- Thinks standardising the columns removes distance concentration
- Assumes any dataset with many columns is automatically cursed
- Confuses the number of columns with the intrinsic dimension