Concretely, what goes wrong with distance-based methods in high dimensions?

hard

Answer

$Distances concentrate: as dimensionality grows, the ratio between the nearest and farthest neighbour of a point tends towards one, so the very notion of a nearest neighbour loses discriminative power.$
$Volume also grows so fast that any realistic sample is sparse, meaning every point is effectively an outlier and density estimates have almost no support.$
$Irrelevant dimensions make this worse, since each contributes noise to the distance and dilutes the informative ones, which is why feature selection helps distance methods disproportionately.$
$The practical responses are to reduce dimensionality first, use a metric learned or chosen for the domain, use cosine distance where magnitude is uninformative, or switch to methods such as tree ensembles that select dimensions rather than aggregating over all of them.$

Check yourself — multiple choice

Computation simply gets slower
Distances concentrate so nearest and farthest converge, samples become sparse so densities lack support, and irrelevant dimensions dilute the signal
High dimensions improve clustering
Only memory is affected

Distance concentration and sample sparsity, worsened by irrelevant dimensions, undermine distance-based methods.

#similarity#dimensionality-reduction

214 interview questions in this topic.