Fast implementations of nearest neighbor classifiers

✍ Scribed by Patrick J. Grother; Gerald T. Candela; James L. Blue

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 641 KB
• Volume: 30
• Category: Article
• ISSN: 0031-3203
• DOI: 10.1016/s0031-3203(96)00098-2

✦ Synopsis

Standard implementations of non-parametric classifiers have large computational requirements. Parzen classifiers use the distances of an unknown vector to all N prototype samples, and consequently exhibit O(N) behavior in both memory and time. We describe four techniques for expediting the nearest neighbor methods: replacing the linear search with a new kd tree method, exhibiting approximately O(N t/2) behavior; employing an L~ instead of L2 distance metric; using variance-ordered features; and rejecting prototypes by evaluating distances in low dimensionality subspaces. We demonstrate that variance-ordered features yield significant efficiency gains over the same features linearly transformed to have uniform variance. We give results for a large OCR problem, but note that the techniques expedite recognition for arbitrary applications. Three of four techniques preserve recognition accuracy.