A Nearest Neighbor Convex Hull Classifier with Sample Selection
基于样本选择的最近邻凸包分类器

The nearest neighbor convex hull(NNCH) classification algorithm is a kind of nearest neighbor classification method, which takes the approximation errors of the convex hulls of all members of every class to the test point as the discriminant measures. However, the higher computation costs of quadratic optimization problems of the algorithm limit its applications on large data sets. So a sample selection method for NNCH named subclass convex hull growth is proposed in this paper. For one class data, the farthest two points are selected first as the initial chosen set. Then, the distances of others to the convex hull of the chosen set are computed respectively. We choose the farthest one and add it into the chosen set. This procedure is repeated until the end conditions. The convex hull of selected samples is taken as the approximation of all. The more samples are selected the less approximation error is achieved, so the valid estimation of sample distribution is realized. Experiments on the ORL database and the MIT-CBCL face recognition training-synthetic database show the abilities of this method to reduce the training data and accelerate the computation while maintaining the generalization performance of NNCH.