A Consistency-Constrained Feature Selection Algorithm with the Steepest Descent Method

This paper proposes a new consistency-based feature selection algorithm, which presents a new balance to the fundamental tradeoff between the quality of outputs of feature selection algorithms and their efficiency. Consistency represents the extent of corrective relevance of features to classification, and hence, consistency-based feature selection algorithms such as INTERACT, LCC and CCC can select relevant features more correctly by taking interaction among features into account. INTERACT and LCC are fast by employing the linear search strategy. By contrast, CCC is slow, since it is based on the complete search strategy, but can output feature subsets of higher quality. The algorithm that we propose in this paper, on the other hand, takes the steepest descent method as the search strategy. Consequently, it can find better solutions than INTERACT and LCC, and simultaneously restrains the increase in computational complexity within a reasonable level: it evaluates

$(|{\mathcal F}| + |{\tilde {\mathcal F}}|)(|{\mathcal F}| - |{\tilde {\mathcal F}}| + 1)/2$

feature subsets to output

${\tilde {\mathcal F}}$

. We prove effectiveness of the new algorithm through experiments.