A generalization technique for nearest-neighbor classifiers

A new generalization algorithm suitable for k-nearest-neighbor (k-NN) classifiers which prunes the training set and improves the performance of the classifier is presented. The definition of the generalization problem for k-NN classifiers is given. The generalization algorithm is described and its computational complexity is derived. The algorithm is applied to a classifier of handwritten digits extracted from a ZIP-code database, and its performance is evaluated. The asymptotic computational cost of the proposed algorithm is a low-order polynomial of the number of elements in the training set. It is proved that given a suitable performance measure, each step of the generalization algorithm monotonically improves the performance of the classifier. Experimental results stemming from the classification of handwritten digits show that the training set provided to the classifier can be reduced by more than one order of magnitude, thus reducing the CPU time and the memory required to classify new samples