A Minimum Risk Metric for Nearest Neighbor Classification

Abstract

Nearest Neighbor is a well-known algorithm extensively studied by the Pattern Recognition and Machine Learning communities and widely exploited in Case Based Reasoning applications. The notion of metric is central to Nearest Neighbor's working and different feature weighting metrics have been proposed in order to increase its performance. In this work we present an original Probability Based Metric, i.e. a metric for classification tasks that relies on estimates of the posterior probabilities, called Minimum Risk Metric (MRM). MRM is optimal but it optimizes directly the finite misclassification risk whereas the Short and Fukunaga Metric minimize the difference between finite risk and asymptotic risk. An experimental comparison of MRM with Short and Fukunaga Metric, Value Difference Metric, and Euclidean-Hamming metrics on benchmark datasets shows that MRM outperforms the other metrics and performs comparably to the Bayes Classifier based on the same probability estimates. The results suggests that MRM can be useful in applications were the retrieval of a nearest neighbor is required (e.g. Case Based Reasoning).