A Feature Selection Algorithm Based On Minimum Upper Bound Of Bayes Error

This paper presents a novel feature selection scheme based on the minimum upper bound of Bayes error. Theoretically, the minimum Bayes error is the best criterion to evaluate feature effectiveness for classification. However, it is too complicated to be expressed in an analytical way. Under normal distribution, the upper bound of the Bayes error can be obtained by the Bhattacharyya distance, so this paper utilizes the upper bound of Bayes error as the criterion. Our proposed feature selection method can obtain very effective classification features and is better than those which are being commonly used today such as LDA feature selection, PCA feature selection and Mahalanobis distance feature selection, since those methods have no direct relationship with Bayes Error.In this paper, we successfully solve the multi-class problems. The upper bound of Bayes error for multi-class can be represented by the sum of the upper bound of Bayes error of every two-class pair, and this is a novelty in this paper.The formula of upper bound of Bayes error is too complex to get the solution directly, in order to obtain an accurate solution of the feature selection transform matrix, we utilize a recursive algorithm. Comparing with the other methods, the recursive algorithm can get a highly accurate solution.This paper also presents a fast algorithm based on PCA pre-processing, this is another novelty. In real situations, the dimension of the original feature space is so large that using recursive algorithm directly is quite time-consuming. So we develop the PCA pre-processing to reduce the calculation burden. At first, PCA pre-processing is used to reduce the original space into a middle space. Then, the recursive method is used to obtain the resultant features. It is concluded by the experiments that PCA pre-processing can speed up the recursive algorithm without sacrificing the high classification performance.In this paper, a method named Within-Class and Between-Class Distribution Graph (B-W Distribution Graph) is proposed. This is the third novelty in the paper. Itcan illustrate the samples by a graph in a simple, accurate and practical way. In pattern recognition problems, analyzing the classify ability of features is an important issue. Classification error rate is an important overall performance measurement. However, it cannot measure the individual performance of each of the samples. In B-W distribution graph, the horizontal axis denotes the between-class distribution or between-class distance (usually the discriminant function), which provides the main information for classification;while the vertical axis denotes the with-in distribution or with-in distance, which provides some supplementary information. B-W distribution graph can be used to evaluate the individual performance of every sample, provide information about the classify ability of features and hence assist in feature selection and classifier design.We apply our proposed method into the MNIST[7J database in the experiments. In these experiments, we investigate the performance of our proposed method and other methods such as PCA, LDA. The results show that: first, our proposed method is better than PCA and LDA in terms of both the upper bound of Bayes error and correct probability in practice. Second, the fast algorithm is very effective and makes our method more practical. Third, although the samples in MNIST database do not completely satisfy the normal distribution assumption, out proposed method also outperform LDA and PCA.