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_17 analyzed the impact of five distance metrics, namely Euclidean, Manhattan, Canberra, Chebychev and Minkowsky in instance-based learning algorithms. Particularly, 1-NN Classifier and the Incremental Hypersphere Classifier (IHC) Classifier, they reported the results of their empirical evaluation on fifteen datasets with different sizes showing that the Euclidean and Manhattan metrics significantly yield good results comparing to the other tested distances.
@cite_17
1146581459 2288452560 2808979505 2165533158
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 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. Abstract Distance metric learning has been a hot research spot recently due to its high effectiveness and efficiency in improving the performance of distance related methods, such as k nearest neighbors ( k NN). Metric learning aims to learn a data-dependent metric to make intra-class distance smaller and inter-class larger. A large number of methods have been proposed for various applications and a survey to evaluate and compare these methods is imperative. The existing surveys just analyze the algorithms theoretically or compare them experimentally with a narrow time scope. Therefore, the paper reviews classical and influential methods that were proposed between 2003 and 2017 and presents a taxonomy based on the most distinct character of each method. All the methods are categorized into five classes, including pairwise cost, probabilistic framework, boost-like approaches, advantageous variants and specific applications. A comprehensive experimental study is made to compare all the selected methods, exploring the ability in improving accuracy, the relation between distance change and accuracy, the relation between accuracy and k NN neighbor size. In recent years, the effect of the curse of high dimensionality has been studied in great detail on several problems such as clustering, nearest neighbor search, and indexing. In high dimensional space the data becomes sparse, and traditional indexing and algorithmic techniques fail from a efficiency and or effectiveness perspective. Recent research results show that in high dimensional space, the concept of proximity, distance or nearest neighbor may not even be qualitatively meaningful. In this paper, we view the dimensionality curse from the point of view of the distance metrics which are used to measure the similarity between objects. We specifically examine the behavior of the commonly used Lk norm and show that the problem of meaningfulness in high dimensionality is sensitive to the value of k. For example, this means that the Manhattan distance metric (L1 norm) is consistently more preferable than the Euclidean distance metric (L2 norm) for high dimensional data mining applications. Using the intuition derived from our analysis, we introduce and examine a natural extension of the Lk norm to fractional distance metrics. We show that the fractional distance metric provides more meaningful results both from the theoretical and empirical perspective. The results show that fractional distance metrics can significantly improve the effectiveness of standard clustering algorithms such as the k-means algorithm.