k-Nearest Neighbors › Disadvantages

The same flexibility that makes kNN effective also creates weaknesses. First, kNN does not tell us which features matter. If a feature is irrelevant but has a large numeric range, its contribution to the distance can dominate the calculation and produce neighborhoods that are essentially determined by noise. Choose feature scales deliberately, as discussed in the earlier standardization chapter. Unintended unit differences can reshape neighborhoods even when the underlying observations are unchanged.

Second, kNN is computationally expensive at prediction time. The training set must be stored. With brute-force search, each query computes the distance to every stored point, a cost that grows linearly with the number of training samples and the number of features. For a small dataset this is trivial; for millions of points in dozens of dimensions, brute-force kNN can become the bottleneck. Exact spatial indexes can reduce distance calculations while preserving the nearest neighbors, at the cost of building and storing the index, plus tuning it. Approximate search introduces a separate speed–recall tradeoff and may return a different neighbor set.

Third, kNN can suffer from the curse of dimensionality. With many noise features, the relative contrast between nearest and farthest distances can shrink, making it harder to identify a useful local neighborhood. We quantify this under an independent Gaussian feature model later in the chapter. This motivates using informative features or a suitable low-dimensional representation; high dimension alone does not determine how kNN will perform.