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 example 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? This review attempts to answer the previous 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, 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 degraded only about @math while the noise level reaches @math , this is true for all the distances used. This means that the KNN classifier using any of the top @math 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.
@cite_1 investigated the effect of Euclidean, Manhattan and Hassanat distance metrics on the performance of the KNN classifier, with K ranging from @math to the square root of the size of the training set, considering only the odd K's. In addition to experimenting on other classifiers such as the Ensemble Nearest Neighbor classifier (ENN) , and the Inverted Indexes of Neighbors Classifier (IINC) . Their experiments were conducted on @math datasets taken from the UCI machine learning repository, the reported results show that Hassanat distance outperformed both of Manhattan and Euclidean distances in most of the tested datasets using the three investigated classifiers.
@cite_1
2288452560 2106053110 1146581459 2130556178
We showed in this work how the Hassanat distance metric enhances the performance of the nearest neighb our classifiers. The results demonstrate the superiority of this distanc e metric over the traditional and most-used distanc es, such as Manhattan distance and Euclidian distance. Moreover, we prove d that the Hassanat distance metric is invariant to data scale, noise and outliers. Throughout this work, it is clearly notab le that both ENN and IINC performed very well with the distance investigated, as their accuracy increased significantly by 3.3 a nd 3.1 respectively, with no significant advantage of the ENN over the IINC in terms of accuracy. Correspondingly, it can be no ted from our results that there is no optimal algor ithm that can solve all reallife problems perfectly; this is supported by the n o-free-lunch theorem. The accuracy of k-nearest neighbor (kNN) classification depends significantly on the metric used to compute distances between different examples. In this paper, we show how to learn a Mahalanobis distance metric for kNN classification from labeled examples. The Mahalanobis metric can equivalently be viewed as a global linear transformation of the input space that precedes kNN classification using Euclidean distances. In our approach, the metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. As in support vector machines (SVMs), the margin criterion leads to a convex optimization based on the hinge loss. Unlike learning in SVMs, however, our approach requires no modification or extension for problems in multiway (as opposed to binary) classification. In our framework, the Mahalanobis distance metric is obtained as the solution to a semidefinite program. On several data sets of varying size and difficulty, we find that metrics trained in this way lead to significant improvements in kNN classification. Sometimes these results can be further improved by clustering the training examples and learning an individual metric within each cluster. We show how to learn and combine these local metrics in a globally integrated manner. In this paper we analyze the impact of distinct distance metrics in instance-based learning algorithms. In particular, we look at the well-known 1-Nearest Neighbor (NN) algorithm and the Incremental Hypersphere Classifier (IHC) algorithm, which proved to be efficient in large-scale recognition problems and online learning. We provide a detailed empirical evaluation on fifteen datasets with several sizes and dimensionality. We then statistically show that the Euclidean and Manhattan metrics significantly yield good results in a wide range of problems. However, grid-search like methods are often desirable to determine the best matching metric depending on the problem and algorithm. We show how to learn a Mahanalobis distance metric for k-nearest neighbor (kNN) classification by semidefinite programming. The metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. On seven data sets of varying size and difficulty, we find that metrics trained in this way lead to significant improvements in kNN classification—for example, achieving a test error rate of 1.3 on the MNIST handwritten digits. As in support vector machines (SVMs), the learning problem reduces to a convex optimization based on the hinge loss. Unlike learning in SVMs, however, our framework requires no modification or extension for problems in multiway (as opposed to binary) classification.