Irrelevant features and the subset selection problem

We address the problem of nding a subset of features that allows a supervised induc-tion algorithm to induce small high-accuracy concepts. We examine notions of relevance and irrelevance, and show that the denitions used in the machine learning literature do not adequately partition the features into useful categories of relevance. We present deni-tions for irrelevance and for two degrees of relevance. These denitions improve our un-derstanding of the behavior of previous sub-set selection algorithms, and help dene the subset of features that should be sought. The features selected should depend not only on the features and the target concept, but also on the induction algorithm. We describe a method for feature subset selection using cross-validation that is applicable to any in-duction algorithm, and discuss experiments conducted with ID3 and C4.5 on articial and real datasets.