Simone De Bonis
Simone De Bonis
← Back to Blog
Data ScienceJanuary 27, 2023· 5 min read

K-Nearest Neighbors (KNN): Probabilistic & Geometric Intuition

Deriving Voting KNN and Volumetric KNN from non-parametric density estimation and Bayes classification, plus practical efficiency improvements.

#Data Science#Machine Learning#Theory#Classification

“If it walks like a duck and quacks like a duck, then it is probably a duck.”

Given a local region of feature space L(X)L(X) centered on XX with volume vv, the probability mass inside L(X)L(X) is approximately p(X)vp(X)v and can be estimated non-parametrically from a sample of size NN as:

p^(X)v=k(X)N  ⟹  p^(X)=k(X)Nv\hat{p}(X)v = \frac{k(X)}{N} \implies \hat{p}(X) = \frac{k(X)}{Nv}

where k(X)k(X) is the number of training instances falling inside L(X)L(X).

A K-Nearest Neighbors (KNN) classifier requires four ingredients:

  1. A set of labeled training records;
  2. A proximity or distance metric to measure similarity between instances;
  3. The hyperparameter kk, the number of nearest neighbors;
  4. A decision rule for aggregating the class labels of the kk nearest neighbors (e.g., majority vote or inverse squared-distance weighting).

Voting KNN

Fixing the local volume vv and counting how many points of each class ωi\omega_i fall inside the region, we can plug the density estimate p^(X∣ωi)=k(X∣ωi)Niv\hat{p}(X|\omega_i) = \frac{k(X|\omega_i)}{N_i v} and the prior p(ωi)=NiNp(\omega_i) = \frac{N_i}{N} into Bayes’ decision rule:

g(X)={ω1if N1Nk(X∣ω1)N1v>N2Nk(X∣ω2)N2vω2if N1Nk(X∣ω1)N1v<N2Nk(X∣ω2)N2vg(X) = \begin{cases} \omega_1 & \text{if } \frac{N_1}{N}\frac{k(X|\omega_1)}{N_1 v} > \frac{N_2}{N}\frac{k(X|\omega_2)}{N_2 v} \\ \omega_2 & \text{if } \frac{N_1}{N}\frac{k(X|\omega_1)}{N_1 v} < \frac{N_2}{N}\frac{k(X|\omega_2)}{N_2 v} \end{cases}

Simplifying NiN⋅Niv\frac{N_i}{N \cdot N_i v} yields the classic majority vote rule:

g(X)={ω1if k(X∣ω1)>k(X∣ω2)ω2if k(X∣ω1)<k(X∣ω2)g(X) = \begin{cases} \omega_1 & \text{if } k(X|\omega_1) > k(X|\omega_2) \\ \omega_2 & \text{if } k(X|\omega_1) < k(X|\omega_2) \end{cases}

Volumetric KNN

Conversely, if we fix the number of neighbors kk per class and allow the volume vi(X)v_i(X) of the sphere enclosing the kk nearest neighbors of class ωi\omega_i to vary with XX, then p^(X∣ωi)=kNivi(X)\hat{p}(X|\omega_i) = \frac{k}{N_i v_i(X)}:

g(X)={ω1if N1NkN1v1(X)>N2NkN2v2(X)ω2if N1NkN1v1(X)<N2NkN2v2(X)g(X) = \begin{cases} \omega_1 & \text{if } \frac{N_1}{N}\frac{k}{N_1 v_1(X)} > \frac{N_2}{N}\frac{k}{N_2 v_2(X)} \\ \omega_2 & \text{if } \frac{N_1}{N}\frac{k}{N_1 v_1(X)} < \frac{N_2}{N}\frac{k}{N_2 v_2(X)} \end{cases}

Since the volume vi(X)v_i(X) of a hypersphere is monotonically proportional to its radius d(X,KNNi)d(X, \text{KNN}_i) (the distance to the kk-th nearest neighbor of class ii):

g(X)={ω1if v2(X)>v1(X)  ⟺  d(X,KNN2)>d(X,KNN1)ω2if v2(X)<v1(X)  ⟺  d(X,KNN2)<d(X,KNN1)g(X) = \begin{cases} \omega_1 & \text{if } v_2(X) > v_1(X) \iff d(X, \text{KNN}_2) > d(X, \text{KNN}_1) \\ \omega_2 & \text{if } v_2(X) < v_1(X) \iff d(X, \text{KNN}_2) < d(X, \text{KNN}_1) \end{cases}

Practical Considerations

  • Distance Metrics: For high-dimensional sparse document vectors, cosine similarity outperforms Euclidean distance or Pearson correlation.
  • Feature Scaling: Standardization (zero mean, unit standard deviation) is essential so attributes with large numerical scales do not dominate the distance calculation.
  • Choosing kk: If kk is too small, the classifier is highly sensitive to local noise points (high variance); if kk is too large, the neighborhood spills across class boundaries (high bias).
  • Local Non-Linear Boundaries: As an instance-based (lazy) learner, KNN incurs zero parametric training cost and can model arbitrary decision boundaries, but naive inference scales as O(Nd)O(Nd) with training set size.

Improving KNN Efficiency

  1. Spatial Indexing & Approximate Search: Avoid exhaustive distance calculations using multi-dimensional access trees (kk-d trees, ball trees), Fast Approximate Nearest Neighbors (ANN), or Locality-Sensitive Hashing (LSH).
  2. Condensing: Select a compact subset of prototype instances that preserves the original decision boundary.
  3. Editing: Remove noisy or overlapping boundary instances to both speed up inference and smooth the decision boundary.
← Back to Blog
Share article: