A method to speed up the Bayes classifier

Abstract

A method is proposed to combine the branch-and-bound (BAB) algorithm with the Bayes classifier. Given the input feature vector from an unknown class, the BAB algorithm is efficient for searching for the nearest neighbor (NN) from among the set of reference vectors. Hence BAB is often used to implement the k-NN classifier. However, it is known that the k-NN classifier is not as accurate as the Bayes classifier, which has the highest recognition rate provided the class statistics are known. Hence it is attractive to combine the BAB algorithm with the Bayes classifier so that the resulting system will inherit improved speed and accuracy. In this article, an extension of the BAB algorithm is proposed so that it can be used to implement the Bayes classifier. Gaussian statistics are assumed in modeling the class conditional densities. A system for recognizing printed Chinese characters is implemented, and satisfactory results are obtained. © 1998 Elsevier Science Ltd. All rights reserved.