Improved k-nearest neighbor classification

Yingquan Wu

doi:10.1016/S0031-3203(01)00132-7

Return

Improved k-nearest neighbor classification

2002-10-01

140

PRE

Yingquan Wu *

Govindaraju, V

DOI：10.1016/S0031-3203(01)00132-7

Original

Original request for help

Save

Abstract

En 中文

k-nearest neighbor (k-NN) classification is a well-known decision rule that is widely used in pattern classification. However, the traditional implementation of this method is computationally expensive. In this paper we develop two effective techniques, namely, template condensing and preprocessing, to significantly speed up k-NN classification 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 filters a large portion of prototypes which are unlikely to match against the unknown pattern. This again accelerates the classification 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 sacrificing accuracy. CD 2002 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.

Keywords:

k-nearest neighbor classification

pattern classification

classifier

template condensing

preprocessing

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.