“If it walks like a duck and quacks like a duck, then it is probably a duck.”
Given a local region of feature space centered on with volume , the probability mass inside is approximately and can be estimated non-parametrically from a sample of size as:
where is the number of training instances falling inside .
A K-Nearest Neighbors (KNN) classifier requires four ingredients:
- A set of labeled training records;
- A proximity or distance metric to measure similarity between instances;
- The hyperparameter , the number of nearest neighbors;
- A decision rule for aggregating the class labels of the nearest neighbors (e.g., majority vote or inverse squared-distance weighting).
Voting KNN
Fixing the local volume and counting how many points of each class fall inside the region, we can plug the density estimate and the prior into Bayes’ decision rule:
Simplifying yields the classic majority vote rule:
Volumetric KNN
Conversely, if we fix the number of neighbors per class and allow the volume of the sphere enclosing the nearest neighbors of class to vary with , then :
Since the volume of a hypersphere is monotonically proportional to its radius (the distance to the -th nearest neighbor of class ):
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 : If is too small, the classifier is highly sensitive to local noise points (high variance); if 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 with training set size.
Improving KNN Efficiency
- Spatial Indexing & Approximate Search: Avoid exhaustive distance calculations using multi-dimensional access trees (-d trees, ball trees), Fast Approximate Nearest Neighbors (ANN), or Locality-Sensitive Hashing (LSH).
- Condensing: Select a compact subset of prototype instances that preserves the original decision boundary.
- Editing: Remove noisy or overlapping boundary instances to both speed up inference and smooth the decision boundary.