Appears in the First International Conference on Knowledge Discovery and Data Mining (KDD-95) Feature Subset Selection Using the Wrapper Method: Over tting and Dynamic Search Space Topology

In the wrapper approach to feature subset selection, a search for an optimal set of features is made using the induction algorithm as a black box. The estimated future performance of the algorithm is the heuristic guiding the search. Statistical methods for feature subset selection including forward selection, backward elimination, and their stepwise variants can be viewed as simple hill-climbing techniques in the space of fea-ture subsets. We utilize best-rst search to nd a good feature subset and discuss overtting problems that may be associated with searching too many feature subsets. We introduce compound operators that dy-namically change the topology of the search space to better utilize the information available from the eval-uation of feature subsets. We show that compound operators unify previous approaches that deal with relevant and irrelevant features. The improved fea-ture subset selection yields signicant improvements for real-world datasets when using the ID3 and the Naive-Bayes induction algorithms.