Trace ratio criterion for feature selection

Abstract

Fisher score and Laplacian score are two popular fea-ture selection algorithms, both of which belong to the general graph-based feature selection framework. In this framework, a feature subset is selected based on the corresponding score (subset-level score), which is calculated in a trace ratio form. Since the number of all possible feature subsets is very huge, it is often pro-hibitively expensive in computational cost to search in a brute force manner for the feature subset with the maximum subset-level score. Instead of calculating the scores of all the feature subsets, traditional methods cal-culate the score for each feature, and then select the leading features based on the rank of these feature-level scores. However, selecting the feature subset based on the feature-level score cannot guarantee the optimum of the subset-level score. In this paper, we directly opti-mize the subset-level score, and propose a novel algo-rithm to efficiently find the global optimal feature subset such that the subset-level score is maximized. Exten-sive experiments demonstrate the effectiveness of our proposed algorithm in comparison with the traditional methods for feature selection.