Optimal feature selection for nonlinear data using branch-and-bound in kernel space

• Branch-and-bound feature selection is performed in kernel space.
• Optimal feature subsets are found without the enormous effort of an exhaustive search.
• Classification accuracy is competitive to the popular wrapper approach.

Branch-and-bound (B&B) feature selection finds optimal feature subsets without performing an exhaustive search. However, the classification accuracy achievable with optimal B&B feature subsets is often inferior compared to the accuracy achievable with other algorithms that guarantee optimality. We argue this is due to the existing criterion functions that define the optimal feature subset but may not conceive inherent nonlinear data structures. Therefore, we propose B&B feature selection in Reproducing Kernel Hilbert Space (B&B-RKHS). This algorithm employs two existing criterion functions (Bhattacharyya distance, Kullback–Leibler divergence) and one new criterion function (mean class distance), however, all computed in RKHS. This enables B&B-RKHS to conceive inherent nonlinear data structures. The algorithm was experimentally compared to the popular wrapper approach that has to use an exhaustive search to guarantee optimality. The classification accuracy achieved with both methods was comparable. However, runtime of B&B-RKHS was superior using the two existing criterion functions and even completely out of reach using the new criterion function (about 60 times faster on average). Therefore, this paper proposes an efficient algorithm if feature subsets that guarantee optimality have to be selected in data sets with inherent nonlinear structures.