KNN 算法详解

Why is it the default? Euclidean distance is the mathematical formalization of the intuitive "straight-line distance." It is rotationally invariant -- the distance between two points remains the same regardless of how the coordinate system is rotated. This means it has no directional bias and treats all dimensions equally. When features are on the same scale and equally important, Euclidean distance is the most natural choice.

Proposed by: Based on Euclidean geometry (circa 300 BC), adopted as the default in modern KNN by Cover & Hart (1967).

Best for: Continuous numerical features, standardized features, low-to-medium dimensionality.

Why does it exist? In high-dimensional sparse data, Euclidean distance suffers from "distance concentration" -- all pairwise distances converge to similar values, destroying discriminative power. Aggarwal, Hinneburg, and Keim proved in their 2001 paper "On the Surprising Behavior of Distance Metrics in High Dimensional Space" that as dimensionality increases, L1 (Manhattan) distance preserves better contrast than L2 (Euclidean). The mathematical reason is that L1 has more uniform sensitivity to per-dimension differences, unlike L2 where a few large differences dominate due to squaring.

Best for: High-dimensional sparse data, grid-like path problems, features with large value ranges where squaring amplification is undesirable.

Why does it exist? Minkowski distance is the unified generalization of L1 and L2, proposed by Hermann Minkowski (1896). The parameter p provides a continuous knob to adjust between L1 and L2 behavior. Smaller p values are more "democratic" across dimensions (each contributes similarly), while larger p values let the dimension with the largest difference dominate. Choosing the optimal p via cross-validation can tailor the metric to the specific data distribution.

Best for: When you are unsure whether L1 or L2 is better -- treat p as a tunable hyperparameter.

Why does it exist? In text classification (TF-IDF vectors) and recommendation systems, what matters is the direction of two vectors, not their magnitude. For example, a document mentioning "machine learning" 10 times and another mentioning it 100 times may have the same topic -- they just differ in length. Cosine distance ignores vector magnitude (it is magnitude-invariant), comparing only direction. This captures "topic similarity" rather than "quantity similarity," which is why cosine distance is the standard choice in NLP.

Proposed by: Developed in the information retrieval field, popularized by Gerard Salton (1971) in the vector space model.

Best for: Text classification, document similarity, recommendation systems, high-dimensional sparse vectors.

Small K (e.g., K=1) -- Low bias / High variance: The decision boundary tightly follows every training point, capturing fine local patterns. Why low bias? Because the model almost perfectly fits the training data (1-NN has zero training error). Why high variance? Because a small perturbation in the data (adding or removing one sample) can significantly change the decision boundary. The model is oversensitive to noise and prone to overfitting.

Large K (e.g., K=n) -- High bias / Low variance: The decision boundary becomes extremely smooth. Why high bias? Because the model over-averages, ignoring local structure (in the extreme case K=n, every query predicts the same class -- the majority class). Why low variance? Because voting over many neighbors makes predictions very stable, unaffected by individual samples.

In binary classification, if K is even (e.g., K=4), you may get a 2-vs-2 tie, forcing the algorithm to use a tiebreaker rule (such as random selection or nearest-neighbor preference), which introduces nondeterminism. Using odd K mathematically guarantees no ties (since an odd number cannot be evenly split), making predictions deterministic.

Note: In multiclass problems, ties can still occur with odd K (e.g., 3 classes each receiving 1 vote with K=3), so the odd-K recommendation applies primarily to binary classification.

The most reliable approach in practice is to use k-fold cross-validation (note: lowercase k here differs from the KNN parameter K) to select the optimal K. A common procedure is to test odd values in the range K = 1, 3, 5, 7, ..., sqrt(n), selecting the K with the highest validation accuracy.

Rule of thumb: sqrt(n) is a reasonable upper bound for K (where n is the number of training samples). Why? Because if K is much larger than sqrt(n), the neighborhood spans too much of the data space, destroying locality.

Core problem: As dimensionality d increases, distances between data points converge to similar values, making the difference between "nearest neighbor" and "farthest neighbor" negligible. Why does this happen?

Mathematical explanation: Consider n points uniformly distributed in a d-dimensional unit hypercube [0,1]^d. The expected Euclidean distance between two random points is E[d] ~ sqrt(d/6), while the standard deviation is Std[d] ~ O(1). Therefore:

When nearest and farthest neighbors are nearly equidistant, the concept of "neighbor" based on distance loses meaning -- KNN's core assumption (nearby points share labels) no longer holds.

Gordon Hughes (1968) discovered a counterintuitive phenomenon in his paper "On the Mean Accuracy of Statistical Pattern Recognizers": with a fixed number of training samples, classifier performance first improves then degrades as feature dimensionality increases. Why?

Adding dimensions initially provides more information, but beyond a critical point the high-dimensional space becomes extremely sparse (data points cannot adequately cover the feature space), and the model begins fitting noise dimensions rather than useful signal. The required number of training samples grows exponentially with dimensionality -- to maintain the same data density in d dimensions, you need n^(d/d_0) times more samples than in lower dimensions.

PCA (Principal Component Analysis) + KNN is the classic combination strategy. Why does PCA help? PCA projects data onto the directions of maximum variance via linear transformation, eliminating redundant and noisy dimensions while preserving the most informative components. After reduction, data density increases and distance metrics become meaningful again.

Other reduction methods: t-SNE (visualization only, not suitable for KNN prediction), UMAP (faster and preserves global structure), feature selection (e.g., mutual information, L1 regularization).

Core reason: KNN is distance-based, and differing scales across features cause some features to unfairly dominate the distance calculation. For example, "age" ranges [0, 100] while "annual income" ranges [0, 1,000,000] -- without scaling, Euclidean distance is almost entirely determined by income, and age has negligible influence.

The following code demonstrates the core logic of a KNN classifier, helping you understand each step of the algorithm:

Why is weighting needed? In standard KNN, all K neighbors vote with equal weight -- a neighbor at distance 0.1 has the same influence as one at distance 9.9. This is intuitively wrong: closer neighbors should be more trustworthy (because the closer the distance, the higher the probability of sharing the same label).

Weighting scheme: The most common weight function is the inverse of distance: w_i = 1/d(x_q, x_i). This way, a neighbor at distance 0.1 has 100 times the weight of one at distance 10.

Benefits of weighted KNN: (1) More robust to K selection -- even if some distant neighbors are included, their low weights limit their impact; (2) smoother decision boundaries; (3) in sklearn, simply set weights='distance'.