A multi-objective evolutionary algorithm based on length reduction for large-scale instance selection

Abstract Instance selection, as an important data pre-processing task, is widely used in supervised classification . Recently, a series of instance selection algorithms with different techniques have been suggested. Among them, evolutionary algorithms (EAs) have shown competitive performance. However, when the size of instance set is large, these EA-based algorithms may face great challenges on search efficiency and computational cost. To this end, in this paper, a multi-objective evolutionary algorithm based on length reduction, termed as LRIS, is proposed for large-scale instance selection, where a length reduction strategy is suggested to recursively shorten the length of each individual in the population, and improve the computational efficiency of LRIS greatly. Specifically, in the proposed length reduction strategy of LRIS, each gene in the individuals has a probability of being deleted, whose probability is obtained according to the importance of the corresponding instance in the instance set and the importance of the corresponding gene in the population. Then, two evolutionary operators (e.g. crossover and mutation) based on the length reduction strategy are developed to generate offspring population from the reduced population. In addition, an individual repairing operator is also designed to repair the length of over-reduced individuals. Experimental results on 12 large-scale data sets have demonstrated the efficiency and the effectiveness of the proposed LRIS in comparison with the state-of-the-art EA-based instance selection algorithms.