Fast Implementations of Nearest Neighbor Classifiers

Statistical classifiers for OCR have been widely investigated. Using Karhunen-Loève (KL) transforms of normalized binary images it has been found that the non-parametric classifiers work better than many commonly used neural networks [1]. Indeed the simplicity and efficacy of the KNN method [2] has made it the algorithm of choice for prototyping pattern recognition tasks. However non-parametric classifiers in on-line recognition systems are expensive: the space and speed requirements rise linearly with the number of known samples, and that number is often necessarily large. Although extensive literature on faster methods exists, for example the papers in Dasarathy’s volume [3], speed and memory requirements have historically mitigated against the practical use of non-parametric classifiers. However older research [4] recently applied to high dimensional searches has shown the aversion to non-parametric to often have been unjustified. The techniques we describe are unrelated to the traditional and very effective methods of condensing the sample sets (through deletion [5] or clustering [6]), which may still be applied in conjunction with our procedures