Data Mining

Instance-based learning [1] is an important learning paradigm. The k-Nearest-Neighbor (abbr. k-NN) [2] is a representative instance-based classifier that assigns an unlabeled instance with the most common class among its k nearest neighbors. Due to its simplicity and effectiveness, k- NN classifiers have been widely employed in pattern classification field. Most of the instance-based classifiers use a given metric to measure the similarity between the unlabeled instance and its neighbors. When attributes are numerical, the normalized Euclidean distance is a natural metric to measure the similarity between instances. However, there may not exist some natural notion of metric for many applications. In this case, many instance-based classifiers that are designed to handle numerical attributes will be confronted with difficulty and typically use much simpler metrics to measure the distance between values of categorical attributes. Although those simpler metrics perform well in some cases, they may fail to capture the inherent complexity of the problem domains, and as a result may perform badly [3].