Source-linked AI summary
k-Nearest Neighbour Classifiers: 2nd Edition (with Python examples)
Padraig Cunningham, Sarah Jane Delany
TL;DR
k-NN raises questions about how to measure similarity, retrieve neighbours efficiently, and reduce data dimensionality. This paper surveys distance measures, retrieval speed-up, and dimension-reduction techniques, including time-series similarity and intrinsic dimensionality. It concludes that k-NN supports diverse data and can benefit from approximate retrieval and structures such as Kd-Trees or Ball Trees, while feature-selection searches may overfit and some similarity measures lack metric properties.
Problem
k-NN requires suitable similarity measures, efficient nearest-neighbour retrieval, and dimensionality reduction because these issues shape its use with diverse and high-dimensional data.
Method
The paper reviews distance and similarity measures, retrieval speed-up techniques, feature and sample selection, intrinsic dimensionality, and time-series methods including DTW.
Results
The review concludes that k-NN can handle data without feature-vector descriptions when a similarity measure exists, while approximate retrieval and Kd-Trees or Ball Trees can improve retrieval or classifier performance in some circumstances.
Takeaways & Limitations
k-NN remains broadly applicable when an appropriate similarity measure is available, with specialized similarity methods and retrieval techniques extending its practical scope.
Takeaways & Limitations
Some similarity measures are not proper metrics, and greedy feature-selection searches are not guaranteed to find the best subset and may overfit when searches become more intensive.
Abstract
from arXiv · showhide
Perhaps the most straightforward classifier in the arsenal or machine learning techniques is the Nearest Neighbour Classifier -- classification is achieved by identifying the nearest neighbours to a query example and using those neighbours to determine the class of the query. This approach to classification is of particular importance because issues of poor run-time performance is not such a problem these days with the computational power that is available. This paper presents an overview of techniques for Nearest Neighbour classification focusing on; mechanisms for assessing similarity (distance), computational issues in identifying nearest neighbours and mechanisms for reducing the dimension of the data. This paper is the second edition of a paper previously published as a technical report. Sections on similarity measures for time-series, retrieval speed-up and intrinsic dimensionality have been added. An Appendix is included providing access to Python code for the key methods.
1 Introduction
k-NN classifies an unknown example by finding its nearest training examples and using their labels, commonly through majority or distance-weighted voting. The section introduces its two-stage workflow, distance calculations, and broader memory-based and lazy-learning characterizations.
- Characterization: k-NN is also described as memory-based, example-based, or case-based classification and as lazy learning because induction is delayed until runtime.Training examples must remain available in memory when classification is performed.
- Core idea: k-NN determines a query’s class from the labels of its k nearest training examples.Classification first identifies the nearest neighbours, then uses them to determine the query’s class.
- Core idea: The classifier has two stages: finding nearest neighbours and determining the query class from those neighbours.For a three-neighbour example, majority voting resolves a two-versus-one class split, while distance weighting can also be used.
- Similarity and distance: Distances can aggregate feature-wise differences using feature weights, with continuous attributes compared by absolute difference and discrete attributes by equality.Numeric features are normalized to [0,1] before distance calculation in the described setup.
- Voting: Majority voting assigns the query the most common class among its nearest neighbours.This is presented as the most straightforward way to convert the selected neighbours into a class prediction.
- Voting: Distance-weighted voting gives nearer neighbours more influence by weighting their votes by inverse distance.The exponent p is normally 1, while larger values further reduce the influence of distant neighbours.
- Scope: The paper focuses on similarity and distance measures, computational speed-up, and dimension reduction because these affect k-NN performance and accuracy.Dimension reduction includes selecting subsets of features or examples, while the paper also surveys more specialized similarity measures.
2 Similarity and Distance Metrics
k-NN can use a broad range of similarity and distance measures, from general Minkowski distances to measures specialized for feature vectors, images, and time-series. The choice of measure can change which example is nearest and must account for metric properties, data representation, and computational trade-offs.
- A proper metric satisfies non-negativity, identity, symmetry, and the triangle inequality, although k-NN can also use non-metric affinity measures.Some nearest-neighbour speed-up techniques require a proper metric, particularly one satisfying the triangle inequality.
- Minkowski distance generalizes common measures: L1 is Manhattan distance, L2 is Euclidean distance, and L∞ is Chebyshev distance.Increasing p can give greater weight to attributes on which examples differ most.
- For points A = (1, 1), B = (5, 1), and C = (4, 4), C becomes nearer to A when the Minkowski parameter p is 3 or greater.The reported distances from A to C are 6, 4.24, and 3.78 for p values of 1, 2, and 3, while A–B remains 4.
- Data-specific measures extend k-NN beyond standard vector distances, including Cosine Similarity and correlation for feature vectors, EMD for images, and DTW for time-series.Cosine similarity uses vector angles and is insensitive to document size, while correlation can match allocation patterns despite different magnitudes.
- Correlation compares patterns rather than raw magnitudes, with Pearson suited to normally distributed features and Spearman using ranks when features are not normally distributed.Correlation scores range from -1 to 1 and can be converted into a distance measure.
- EMD compares image signatures by minimizing the effort needed to transport mass between weighted clusters, while compression-based metrics can outperform bag-of-words distance metrics for text classification.EMD addresses problems arising from arbitrary histogram binning; compression metrics require an appropriate compression measure for the data.
3 Computational Complexity
The paper reviews exact and approximate strategies for reducing k-NN retrieval cost, including tree-based indexing and dimension-related constraints. Exact methods can speed retrieval on low-dimensional data, while approximate methods offer larger gains with limited accuracy loss but narrower applicability.
- Computational complexity: Basic k-NN distance computation is O(dn), motivating alternatives to exhaustive search and reductions in features or training samples.Here d is the number of features and n the number of data samples.
- 3.1 Kd Trees: Kd-Trees partition feature space recursively and can reduce retrieval from O(dn) to O(d log(n)) by bounding out large regions.The method relies on tree partitioning and pruning candidate regions during search.
- 3.1 Kd Trees: Kd-Tree benefits diminish in high dimensions, with the indexing advantage ceasing when d is large and retrieval potentially becoming no better than brute force.The cited discussion gives d > 20 as an example and notes that when d > log(n), O(d log(n)) is no better than O(dn).
- 3.2 Ball Trees: Ball Trees use a metric defined on pairs of samples rather than feature-space partitions and may perform better than Kd-Trees for high-dimensional data.Their construction is hierarchical, using bounding balls formed through top-down or bottom-up procedures.
- 3.3 Approximate k-NN: Approximate k-NN methods trade exact neighbour guarantees for dramatic speedups with little or no accuracy loss, but the approach is limited to feature-vector data.Random Projection Trees use curtailed backtracking and multiple randomized trees; evaluation reports almost no accuracy loss except for the Letter dataset, with a four-fold processing-time improvement when more trees are added.
- 3.4 Speed-Up Evaluation: In the speed-up evaluation, tree methods substantially outperform brute force on low-dimensional datasets, while the Credit dataset performs worse because it is high-dimensional.Kd-Trees are reported as slightly better than Ball Trees in all tested cases.
4 Dimension Reduction
Dimension reduction in k-NN targets both the feature space and the training set, because high dimensionality affects computational performance, accuracy, and similarity. The paper reviews feature selection, PCA-based intrinsic-dimension analysis, and instance-selection strategies, including their benefits and limitations.
- Dimension reduction: Feature selection and instance selection reduce different dimensions of k-NN data: features describe examples, while instances determine training-set size.Feature selection may discard or transform features; instance selection removes redundant or noisy training examples.
- 4.1 Intrinsic Dimension: PCA maps data into a lower-dimensional representation and uses the top s principal components capturing (1 − ϵ) of variance to approximate intrinsic dimension.The selected components provide a global approximation of the minimum feature count needed for a good representation.
- 4.1 Intrinsic Dimension: Four principal components capture almost all HTRU variance but less than 80% for Shuttle, indicating intrinsic dimension greater than four for Shuttle.The comparison is shown in Figure 9.
- 4.2 Feature Selection: Feature selection can improve k-NN efficiency because retrieval time increases with feature count, while irrelevant or noisy features can reduce accuracy and distinguishability.The paper discusses filters and wrappers as search-and-evaluation frameworks for choosing feature subsets.
- 4.2 Feature Selection: Information Gain significantly outperformed OR feature selection: objects lacked any selected features in 0.2% of cases for IG versus 8.8% for OR.The evaluation suggests that the top 350 IG-ranked features were adequate, with cross validation used to identify the useful cutoff.
- 4.2 Feature Selection: Greedy feature-subset searches are not guaranteed to find the best subset, while more intensive searches may be more likely to overfit training data.The strategies stop when adding or deleting a feature no longer improves cross-validated accuracy.
- 4.3 Instance Selection and Noise Reduction: Instance selection can dramatically reduce training-set size with almost no effect on generalisation accuracy when training data contains substantial redundancy.The paper also reviews CNN, CRR, ICF, and DROP3 reduction strategies, with comparative outcomes varying by algorithm and dataset.
5 Conclusion: Advantages and Disadvantages
k-NN combines simplicity, transparency, flexible similarity measures, and several options for improving accuracy or retrieval speed. Its main drawbacks are computational cost on large training sets, sensitivity to irrelevant features, and weaker performance on very difficult tasks.
- k-NN is simple to understand and implement, and its transparent process makes debugging straightforward.The classifier's interpretability is presented as a central source of its advantages.
- A similarity measure allows k-NN to classify data that cannot be represented as a feature vector.This extends k-NN to settings where other machine-learning mechanisms may not apply.
- Neighbour analysis can provide useful explanations of classifier outputs when the relevant neighbours are interpretable.
- Noise-reduction techniques can improve classifier accuracy, while Kd-Trees, Ball Trees, and approximate methods can improve retrieval times.Approximate Nearest Neighbour methods may provide large speed-ups with minimal impact on accuracy.
- k-NN may have poor run-time performance with a large training set because computation is performed at run-time.
- Irrelevant or redundant features affect similarity and classification, although feature selection or weighting can mitigate this sensitivity.
- On very difficult classification tasks, k-NN may be outperformed by Support Vector Machines or Neural Networks.
A Appendix I: Python Code
The appendix provides Python notebooks covering basic k-NN classification, alternative similarity measures, time-series classification, retrieval speed-up, intrinsic-dimension estimation, and instance selection.
- The kNN-Basic notebook implements a basic k-NN classifier in scikit-learn.
- The kNN-Correlation and kNN-Cosine notebooks demonstrate correlation and cosine similarity for k-NN, including text classification with cosine similarity.
- The kNN-DTW notebook applies Dynamic Time Warping with tslearn for time-series classification.
- The kNN-Speedup and kNN-Annoy notebooks test scikit-learn retrieval options and approximate-neighbour speed-up on datasets.
- The kNN-PCA notebook uses PCA to estimate intrinsic dimension, while kNN-InstSel evaluates CRR and CNN instance selection on training-set size and accuracy.