Nearest Local Hyperplane Rules for Pattern Classification
Gábor Takács and Béla Pataki
The 10th Congress of the Italian Association for Artificial Intelligence (AIIA 2007)
Roma, Italy, September 10-13, 2007
Abstract
Predicting the class of an observation from its nearest neighbors is one of the earliest approaches in pattern recognition. Besides simplicity, nearest neighbor rules have appealing theoretical properties, e.g. the asymptotic error probability of the plain 1-nearest-neighbor (NN) rule is at most twice the Bayes bound, which means zero asymptotic risk in the separable case. But given only a finite number of training examples, NN classifiers are often outperformed in practice. A possible modification of the NN rule to handle separable problems better is the nearest local hyperplane (NLH) approach. In this paper we introduce a new way of NLH classification that has two advantages over the original NLH algorithm. The first is that our method preserves the zero asymptotic risk property of NN classifiers in the separable case. Secondly, it usually provides better finite sample performance.