An Instance Selection Assisted Evolutionary Method for High-Dimensional Feature Selection

Evolutionary algorithms (EAs) have shown their competitiveness in solving feature selection (FS) problem. However, when facing high-dimensional data with a number of instances, there are two challenges for the existing EAs. (1) The increasing number of features causes the search space of EAs to grow exponentially, which is known as the “curse of dimensionality". (2) The increasing number of instances not only increases the evaluation cost of EAs, but also may degrade the quality of obtained feature subsets. To tackle the two challenges simultaneously, this paper proposes an instance selection (IS) assisted evolutionary FS algorithm, named ISA-EFS. In ISA-EFS, a complementary feature grouping strategy is first suggested, with which the search is performed on the feature group level instead of the single feature level, and the “curse of dimensionality" can be solved effectively. Based on the grouping strategy, two new evolutionary (grouping-oriented crossover and mutation) operators are designed, which achieve the feature subsets with good quality. Then, a novel instance selection algorithm is developed to select a small number of “representative" instances and used for high-dimensional feature selection (HDFS). In ISA-EFS, the suggested IS and FS algorithms are carried on alternately. Meanwhile, since IS is designed to assist FS, the computational resources are gradually removed from IS to FS, with which the quality of feature subsets obtained by ISA-EFS is continuously improved. Experimental results on 12 high-dimensional datasets with a number of instances demonstrate the effectiveness and efficiency of the proposed ISA-EFS, when compared with six state-of-the-art FS algorithms.