Fast multistage algorithm for K-NN classifiers

In this paper we present a way to reduce the computational cost of k-NN classifiers without losing classification power. Hierarchical or multistage classifiers have been built with this purpose. These classifiers are designed putting incrementally trained classifiers into a hierarchy and using rejection techniques in all the levels of the hierarchy apart from the last. Results are presented for different benchmark data sets: some standard data sets taken from the UCI Repository and the Statlog Project, and NIST Special Databases (digits and upper-case and lower-case letters). In all the cases a computational cost reduction is obtained maintaining the recognition rate of the best individual classifier obtained.