Efficient Algorithms for Identifying Relevant Features
Hussein Almuallim, Thomas G. Dietterich · 1992
This paper describes efficient methods for exact and approximate implementation of the MINFEATURES bias, which prefers consistent hypotheses definable over as few features as possible. This bias is useful for learning domains where many irrelevant features are present in the training data. We first introduce FOCUS-2, a new algorithm that exactly implements the MINFEATURES bias. This algorithm is empirically shown to be substantially faster than the FOCUS algorithm previously given in [ Almuallim and Dietterich, 1991 ] . We then introduce the Mutual-Information-Greedy, SimpleGreedy and Weighted-Greedy algorithms, which apply efficient heuristics for approximating the MIN-FEATURES bias. These algorithms employ greedy heuristics that trade optimality for computational efficiency. Experimental studies show that the learning performance of ID3 is greatly improved when these algorithms are used to preprocess the training data by eliminating the irrelevant features from ID3's consideration. I...