Format

Send to

Choose Destination
Big Data. 2019 Dec;7(4):221-248. doi: 10.1089/big.2018.0175. Epub 2019 Aug 14.

Effects of Distance Measure Choice on K-Nearest Neighbor Classifier Performance: A Review.

Author information

1
Department of Computer Science, Faculty of Information Technology, Mutah University, Karak, Jordan.
2
Department of Algorithm and Their Applications, Eötvös Loránd University, Budapest, Hungary.
3
Department of Geomatics, Faculty of Environmental Design, King Abdulaziz University, Jeddah, Saudi Arabia.
4
Department of Civil Engineering, Faculty of Engineering, Al-Hussein Bin Talal University, Maan, Jordan.
5
Department of Pediatrics, Division of Biomedical Informatics, Cincinnati Children's Hospital Medical Center, Cincinnati, Ohio.
6
Department of Pediatrics, College of Medicine, University of Cincinnati, Cincinnati, Ohio.
7
Department of Biomedical Informatics, College of Medicine, University of Cincinnati, Cincinnati, Ohio.
8
Department of Electrical Engineering and Computer Science, University of Cincinnati, Cincinnati, Ohio.

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 data sets, 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 nonconvex distance performed the best when applied on most data sets comparing with the other tested distances. In addition, the performance of the KNN with this top performing distance degraded only ∼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 tolerates noise to a certain degree. Moreover, the results show that some distances are less affected by the added noise comparing with other distances.

KEYWORDS:

K-nearest neighbor; big data; machine learning; noise; supervised learning

PMID:
31411491
DOI:
10.1089/big.2018.0175

Supplemental Content

Full text links

Icon for Atypon
Loading ...
Support Center