Feature selection using graph cuts based on relevance and redundancy

In this paper, we propose a feature selection method that uses graph cuts based on both relevance and redundancy of features. The feature subset is derived by an optimization using a novel criterion which consists of two terms: relevance and redundancy. This kind of criterion has been proposed elsewhere, but previously proposed criteria are hard to optimize. In contrast, our criterion is designed to satisfy submodularity so that we can obtain a globally optimal feature subset in polynomial time using graph cuts. Experimental results show that the proposed method works well, especially in the case of a medium-size subset where existing approaches are weak because of the many possible feature combinations.