Distance and Similarity Measures Effect on the Performance of K-Nearest Neighbor Classifier -- A Review

Abstract

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.

39 pages, 6 figures, 17 tables, revised text and added extra experiments

References in corpus (5)

• Survey of Nearest Neighbor Techniques
• Solving the Problem of the K Parameter in the KNN Classifier Using an Ensemble Learning Approach
• Content based video retrieval systems
• On Enhancing The Performance Of Nearest Neighbour Classifiers Using Hassanat Distance Metric
• Experiments of Distance Measurements in a Foliage Plant Retrieval System

Cited by in corpus (8)

• Quantum K-nearest neighbor classification algorithm based on Hamming distance
• Smart non-intrusive appliance identification using a novel local power histogramming descriptor with an improved k-nearest neighbors classifier
• Evaluation of Similarity-based Explanations
• Classification of retail products: From probabilistic ranking to neural networks
• SPINEX: Similarity-based Predictions and Explainable Neighbors Exploration for Regression and Classification Tasks in Machine Learning
• Light Curve Classification with DistClassiPy: a new distance-based classifier
• Understanding and Exploiting Dependent Variables with Deep Metric Learning
• A unified framework for divergences, free energies, and Fokker-Planck equations