Improved k-nearest neighbor classification

✍ Scribed by Yingquan Wu; Krassimir Ianakiev; Venu Govindaraju

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 113 KB
• Volume: 35
• Category: Article
• ISSN: 0031-3203
• DOI: 10.1016/s0031-3203(01)00132-7

✦ Synopsis

k-nearest neighbor (k-NN) classiÿcation is a well-known decision rule that is widely used in pattern classiÿcation. However, the traditional implementation of this method is computationally expensive. In this paper we develop two e ective techniques, namely, template condensing and preprocessing, to signiÿcantly speed up k-NN classiÿcation while maintaining the level of accuracy. Our template condensing technique aims at "sparsifying" dense homogeneous clusters of prototypes of any single class. This is implemented by iteratively eliminating patterns which exhibit high attractive capacities. Our preprocessing technique ÿlters a large portion of prototypes which are unlikely to match against the unknown pattern. This again accelerates the classiÿcation procedure considerably, especially in cases where the dimensionality of the feature space is high. One of our case studies shows that the incorporation of these two techniques to k-NN rule achieves a seven-fold speed-up without sacriÿcing accuracy.