An Adaptive Large Margin Nearest Neighbor Classification Algorithm

Although kNN has been successfully applied to pattern recognition in various areas, there is a big gap to get good performance because of the parameter k. The existing kNN-type methods have to fix k for all testing examples, which is not appropriate since the data density depends on the real applications. In order to deal with this drawback, an adaptive large margin nearest neighbor classification algorithm (ALMNN) is proposed in this paper to avoid predefining the value of k for all data points. The new method adaptively selects an optimal k for each testing example by solving an optimization problem. Finally, ALMNN assigns a proper label for the testing point based on the loss function. A series of experimental results on real world data sets (including UCI benchmark data sets, image data sets and text data sets) show that the new algorithm outperforms the existing methods. Meanwhile, ALMNN has ability to make kNN insensitive to the choice of k and the random selection of training data sets.