A Fast Algorithm for a k-NN Classifier Based on Branch and Bound
Method and Computational Quantity Estimation
Shin'ichiro Omachi and Hirotomo Aso
Systems and Computers in Japan, vol.31, no.6, pp.1-9, May 2000
Abstract
Nearest neighbor rule or k-nearest neighbor rule is a technique
of nonparametric pattern recognition.
Its algorithm is simple and error is smaller than twice the Bayes error
if there are enough training samples.
However, it requires enormous computational quantities that is proportional to
the number of samples and the number of dimensions of feature vector.
In this paper, a fast algorithm for k-nearest neighbor rule based on
branch and bound method is proposed.
Moreover, a new training algorithm for constructing a search tree that
can reduce the computational quantity is proposed.
Experimental results show the effectiveness of the proposed algorithms.
Keywords
pattern recognition, nearest neighbor rule, k-nearest neighbor rule,
branch and bound method, character recognition
Full paper
PDF
Gzipped Postscript