Incremental Wrapper-based subset Selection with replacement: An advantageous alternative to sequential forward selection

This paper deals with the problem of wrapper-based feature subset selection in classification oriented datasets with a (very) large number of attributes. In such datasets sophisticated search algorithms like beam search, branch and bound, best first, genetic algorithms, etc., become intractable in the wrapper approach due to the high number of wrapper evaluations to be carried out. One way to alleviate this problem is to use the so-called filter-wrapper approach or Incremental Wrapper-based Subset Selection (IWSS), which consists in the construction of a ranking among the predictive attributes by using a filter measure, and then a wrapper approach is used guided by the rank. In this way the number of wrapper evaluations is linear with the number of predictive attributes. In this paper we present a contribution to the IWSS approach which helps it to obtain more compact subsets, and consists into allow not only the addition of new attributes but also the interchange with some of the already included in the selected subset. The disadvantage of this novelty is that it grows up the worst-case complexity of IWSS up to O(n²), however, as in the case of the well known sequential forward selection (SFS) the actual number of wrapper evaluations is considerably smaller. Empirical tests over 7 (biological) datasets with a large number of attributes demonstrate the success of the proposed approach when comparing with both IWSS and SFS.