A Fast Algorithm for a k-NN Classifier Based on the Branch and Bound Method and Computational Quantity Estimation

摘要

The nearest neighbor the rule or k-nearest neighbor rule is a technique of nonparametric pattern recognition. Its algorithm is simple and the error is smaller than twice the Bayes error if there are enough training samples. However, It requires an enormous amount of computation, propor- Tional to the number of samples and the number of dimen- Sions of the feature vector. In this paper, a fast algorithm for The k-nearest neighbor rule based on the brand and bound Method is proposed.