Source-linked AI summary
Distance and Similarity Measures Effect on the Performance of K-Nearest Neighbor Classifier -- A Review
V. B. Surya Prasath, Haneen Arafat Abu Alfeilat, Ahmad B. A. Hassanat, Omar Lasassmeh, Ahmad S. Tarawneh, Mahmoud Bashir Alhasanat, Hamzeh S. Eyal Salman
TL;DR
The paper examines which distance measures best support KNN classification, especially when data contain noise. It reviews and experimentally evaluates many measures across real-world datasets using accuracy, precision, and recall. Hassanat distance performed best on most datasets, while performance generally degraded only about 20% at 90% noise, although no single metric was optimal for every dataset.
Problem
The review addresses which distance metric gives KNN the best performance overall and under noise, because prior studies tested relatively few distances, datasets, or both.
Method
The study evaluates many KNN distance measures on real-world datasets with and without added noise, using accuracy, precision, and recall.
Results
Hassanat distance performed best on most datasets, while its performance degraded about 20% when noise reached 90%; average precision ranked HasD first from 10% through 70% noise.
Takeaways & Limitations
KNN performance depends significantly on the distance used, and the top 10 distances tolerate noise to a certain degree, although no metric is optimal for all datasets.
Takeaways & Limitations
Choosing the optimal K is outside the review’s scope, and the 28 tested datasets may be insufficient for significant conclusions across varied data types.
Abstract
from arXiv · showhide
The K-nearest neighbor (KNN) classifier is one of the simplest and most common classifiers, yet its performance competes with the most complex classifiers in the literature. The core of this classifier depends mainly on measuring the distance or similarity between the tested examples and the training examples. This raises a major question about which distance measures to be used for the KNN classifier among a large number of distance and similarity measures available? This review attempts to answer this question through evaluating the performance (measured by accuracy, precision and recall) of the KNN using a large number of distance measures, tested on a number of real-world datasets, with and without adding different levels of noise. The experimental results show that the performance of KNN classifier depends significantly on the distance used, and the results showed large gaps between the performances of different distances. We found that a recently proposed non-convex distance performed the best when applied on most datasets comparing to the other tested distances. In addition, the performance of the KNN with this top performing distance degraded only about $20\%$ while the noise level reaches $90\%$, this is true for most of the distances used as well. This means that the KNN classifier using any of the top $10$ distances tolerate noise to a certain degree. Moreover, the results show that some distances are less affected by the added noise comparing to other distances.
1. Introduction
KNN is widely used, but its performance depends on the distance or similarity measure selected. This review addresses limited prior comparisons by evaluating many measures across datasets and noise conditions.
- Background: KNN is a widely applied, non-parametric classifier used for pattern classification and regression despite computational slowness.Its simplicity and reasonable accuracy support applications across pattern recognition, text categorization, ranking, object recognition, and event recognition.
- Research problem: Distance selection is a central KNN problem because classifier performance depends on the chosen distance or similarity measure.The paper focuses on identifying measures that provide the highest possible classification performance.
- Related work: Prior studies typically evaluated only 3–18 distance measures, a small number of datasets, or both.Earlier work reported different best-performing distances across datasets, including Manhattan, Chi square, Euclidean, and Hassanat distances.
- Contribution: The review tests a relatively large number of distance measures on many datasets, evaluating accuracy, precision, and recall with and without noise.The study aims to address which distance is best overall and which is best when noise is present.
2. KNN and distance measures
KNN classifies test samples by selecting the nearest training examples according to a distance or similarity measure and assigning the majority class. Its main practical challenges include choosing K and the distance function, computational cost, memory requirements, and sensitivity to noisy data.
- KNN limitations: KNN requires O(nm) time per test example and O(nm) storage, where n is the number of training examples and m is the number of features.The time cost comes from computing distances to every training sample, while the memory requirement comes from storing all training samples.
- KNN limitations: Choosing the optimum K and determining the distance function remain central issues, alongside KNN's computational time and memory requirements.The reviewed work focuses especially on the distance function, which is described as the core of the study.
- KNN classifier: The basic KNN algorithm computes distances, selects K nearest training samples, and assigns the test sample their majority class.The algorithm takes training samples D, a test sample d, and K as input, and outputs the test sample's class label.
- KNN classifier: KNN stores labeled training samples and classifies each test sample by majority vote among its K nearest neighbors.Distances from the test sample to all stored training samples are computed, the K closest samples are selected, and the most frequent class is assigned.
- Noisy data: Noise can affect attributes, class labels, training data, or test data, with its impact varying by distribution and magnitude.The paper distinguishes class noise from attribute noise and describes noise by where it is introduced, how it is distributed, and how strongly it changes values.
- Noisy data: The study adds different noise levels to datasets to identify distance metrics least affected in KNN performance.The stated objective is to find the optimal distance metric under added noise.
- Distance measures: A distance function d(x, y) returns a non-negative real number, while a metric additionally satisfies identity, symmetry, and triangle inequality properties.The paper lists non-negativity, identity of indiscernibles, symmetry, and triangle inequality as metric properties.
- Distance measures: The paper reviews 54 distance measures organized into eight major distance families for measuring closeness between numeric vectors.The review defines distances between vectors x and y and provides mathematical formulations and example calculations.
3. Experimental framework
The experiments evaluate KNN with multiple distance and similarity measures using accuracy, precision, and recall, then compare their performance across datasets. Results show that performance varies substantially by distance family and dataset, with several measures achieving dataset-specific advantages.
- Evaluation measures: Accuracy, precision, and recall were calculated for KNN across all tested distance metrics and similarity measures.These measures were used to compare classifier performance across the datasets.
- Overall comparison: HasD achieved the highest overall average across the 54 tested distances.The reported averages were computed over 10 runs for each distance and dataset.
- Recall results: The L1 family led recall on seven datasets, including CanD on Australian and Wine and LD on Glass, Ionosphere, Vehicle, and Vowel.CanD achieved 81.83% and 73.94% average recall on Australian and Wine, while LD achieved 51.15%, 61.52%, 54.85%, and 97.68% on Glass, Ionosphere, Vehicle, and Vowel.
- Dataset-specific results: Distance-family leaders differed by dataset, including Inner Product on selected Heberman and Banknote results and Squared L2 on Vote, Wholesale, and German results.Banknote reached 100% average recall and precision for CD, JacD, and DicD; Vote reached 91.03% recall and 92.11% precision with the reported family members.
- Recall and precision results: The Vicissitude family led recall on six datasets and precision on four datasets, with VSDF1 strongest on several Liver, Parkinson, and Phoneme evaluations.VSDF1 achieved 43.65%, 99.97%, and 88.13% average recall, and 43.24%, 99.97%, and 87.23% average precision, on those three datasets.
4. Conclusions and Future Perspectives
The review finds that KNN performance varies substantially with the distance measure, while the top distances retain some noise tolerance. It also identifies dataset, noise-model, distance-coverage, and classifier-scope limitations for future work.
- KNN performance depends significantly on the distance measure, with large performance gaps between different distances.
- Hassanat distance performed best on most datasets, including under different levels of heavy noise.
- KNN performance degraded only about 20% when noise reached 90%, and the top 10 distances tolerated noise to a certain degree.
- No single distance metric was optimal for every dataset; each dataset favored a specific metric.
- The review tested many measures, but other distance and similarity measures, KNN variants, and larger datasets with varied data types remain to be evaluated.
- Replacing 10%–90% of examples with completely random attribute values may not simulate other real-world noise types.