Suboptimal branch and bound algorithms for feature subset selection: A comparative study

• Suboptimal versions of four branch and bound algorithms are proposed and studied.
• Test results on real data sets are presented.
• We explore the possibility of using suboptimal branch and bound algorithm on high-dimensional data.

The branch and bound algorithm is an optimal feature selection method that is well-known for its computational efficiency. However, when the dimensionality of the original feature space is large, the computational time of the branch and bound algorithm becomes very excessive. If the optimality of the solution is allowed to be compromised, one can further improve the search speed of the branch and bound algorithm; the look-ahead search strategy can be employed to eliminate many solutions deemed to be suboptimal early in the search. In this paper, a comparative study of the look-ahead scheme in terms of the computational cost and the solution quality on four major branch and bound algorithms is carried out on real data sets. We also explore the use of suboptimal branch and bound algorithms on a high-dimensional data set and compare its performance with other well-known suboptimal feature selection algorithms.