An improved branch and bound algorithm for feature selection.pdfVIP

An Improved Branch and Bound Algorithm for Feature Selection Xue-wen Chen* Department of Electrical and Computer Engineering, California State University, 18111 Nordhoff Street, Northridge, CA 91330-8346 Abstract Feature selection plays an important role in pattern classification. In this paper, we present an improved Branch and Bound algorithm for optimal feature subset selection. This algorithm searches for an optimal solution in a large solution tree in an efficient manner by cutting unnecessary paths which are guaranteed not to contain the optimal solution. Our experimental results demonstrate the effectiveness of the new algorithm. Keywords – Branch and Bound algorithm, solution tree, feature selection, classification I. INTRODUCTION Feature selection plays an important rule in pattern recognition applications. For example, in medical diagnosis, we need to evaluate the effectiveness of various feature combinations and select effective ones for classification. By using a subset of features, the processing time required by the classification process is reduced. Feature selection is to select a subset of m features from a larger set of n features to optimize the value of a criterion function J over all subsets of the size m. There are many different feature selection algorithms used in the literature. Sequential forward selection (SFS) and sequential backward selection (SBS) (e.g., Fukunaga (1992)) are two widely used sequential feature selection methods. The SFS method first selects the best single feature and then adds one * Corresponding author. Tel.: 818-677-4755, Fax: 818-677-7062, Email: xwchen@ 2 feature at a time which in combination with the selected features maximizes the criterion function J; the SBS method starts with all input features and successively deletes one feature at a time. Both SFS and SBS methods are computationally attractive. By dynamically controlling the number of forward and backtracking steps, floa