A Correlation-Redundancy Guided Evolutionary Algorithm and Its Application to High-Dimensional Feature Selection in Classification

The classification of data is an indispensable subject in the domain of machine learning and data mining [1]. It serves as a pervasive technique for discerning and categorizing different system states, thereby finding extensive applications in various fields. As a pre-processing technology, feature selection (FS) is widely used for eliminating redundant and irrelevant features from the original dataset to improve the efficiency and accuracy of the classification model [2]. However, the number of measurements to measure the state of a system has increased dramatically with the development of information technology. High-dimensional datasets may contain more redundant and irrelevant features[3], which definitely puts more pressure on FS to filter out the best subset of features. Thus, it is of great significance to minimize the number of features as much as possible to enhance model efficiency for FS of high-dimensional datasets apart from ensuring classification accuracy. This makes an urgent need for designing an efficient method for solving multi-objective FS (MOFS) of high-dimensional datasets.

FS can be regarded as a problem of combinatorial optimization [4]. The exhaustive method can be employed to obtain all possible combinations of features and determine the subset that optimizes the evaluation criteria. Nevertheless, the solution space for a set of \(n\) features is \({2}^{n}-1\), and the computational time required for the exhaustive method grows exponentially with the number of feature dimensions [5]. Thus, despite its simplicity, the exhaustive method proves challenging to implement in practical applications [6]. To solve this problem, many heuristic algorithms have been proposed for solving FS problems. Among these methodologies, sequential forward selection (SFS) and sequential backward selection (SBS) [7] emerge as two prominent approaches. These methods involve initializing either an empty set or a complete set and subsequently iteratively adding or removing features to optimize the subset of features. Despite improving search efficiency relative to exhaustive search, a limitation of both SFS and SBS is that it cannot be reconsidered for further inclusion or exclusion once a feature has been included or excluded. But some features are functionally interconnected, exhibiting a correlated coupling effect. To address this drawback, a novel selection method known as the plus-l minus-r selection method [8] has been introduced. This method effectively alleviates the aforementioned concern associated with SFS and SBS, but the plus and minus of features are fixed. Based on this, the sequential floating forward selection [9] and sequential floating backward selection [10] are designed based on plus-l minus-r selection method, where the plus and minus features can change each time. Although the heuristic methods can significantly reduce the time complexity in comparison to exhaustive search, they often encounter the challenge of being susceptible to local optima due to their fixed search strategies. Thus, intelligent algorithm (IA), as an ideal method has received increasing attention in recent years for its ability to achieve near-optimal/optimal solutions within a reasonable time [11, 12].

However, IA is easy to be trapped in suboptimal solutions when handling FS in high-dimensional datasets [13, 14]. Recently, many search strategies have been designed to improve the search efficiency of the meta-heuristic algorithm. Based on the Pearson correlation coefficient, Kabir et al. [15] developed a novel local search operation that relied on the distinct and informative nature of input features, as computed through correlation information. Moradi and Gholampour [16] introduced a local search strategy that selected distinct features by considering their correlation information. However, the Pearson correlation coefficient can only measure linear relationships between variables, not non-linear relationships, and is sensitive to outliers. To overcome this shortcoming, mutual information is used to measure the correlation between variables [17]. Vinh et al. [18] introduced a correlation-redundancy metric (CRM) to characterize the correlation and redundancy of each feature, which denoted the correlation between a feature and the labels, as well as the redundancy between two features. Furthermore, Wang et al. [19, 20] designed a “relevance-redundancy index” for evaluating the feature importance based on CRM in an ant colony optimization to classification. Song et al. [21] proposed supplementary and deletion operators to enhance the local search ability. However, CRM can measure the feature when the feature has a high correlation between class labels and a low correlation with other features. When both the correlation and redundancy of a feature are high, it will cause the probability of the feature to be close to 0, which will make features with high correlation be discarded. Thus, a novel evaluation function is designed to measure the correlation-redundancy (CR) of each feature. Based on this, a novel local search strategy is proposed which considers both the search depth and the CR of features simultaneously.

Additionally, population initialization also significantly impacts the performance of IA. Most existing literatures use traditional random initialization (TRI) [1, 4, 16, 22] which may influence the quality of the initial population, resulting in slowing down the overall convergence rate [23]. To handle this issue, Xu et al. [24] devised a split initialization approach to enhance the diversity of the initial population, thereby amplifying the breadth of the exploration process. Xue et al. [25] introduced an interval initialization technique that constrained the selection of features to a specific number. Xue et al. [26] devised three novel warm initialization strategies, namely small, large, and mixed initialization methods. The above papers focus on the controlling the quantity of selected features to enhance diversity, disregarding the importance of the selected features themselves, such as the correlation and redundancy of each feature. To overcome this problem, Deniz et al. [27] employed an information gain technique to evaluate the significance of each feature and subsequently initialized the population based on the obtained scores. Song et al. [21] developed a swarm initialization strategy that leverages label correlation as a guiding principle. Mohsen et al. [28] employed cosine similarity in their pheromone initialization approach. Li and Ren [29] designed a swam initialization method based on the maximal information coefficient between the feature and label. Although the aforementioned studies considered the correlation between features and labels, the redundancy between features is ignored. Thus, this paper introduces a novel initialization strategy, which considers a new evaluation function for evaluating the CR of each feature and utilizes it to determine the probability of selecting a feature. This provides an efficient way to get a high-quality initial population and reduce the solution space, thereby expediting the convergence speed.

To sum up, this study proposes a correlation-redundancy guided evolutionary algorithm, named CRGEA, to solve high-dimensional MOFS. A new correlation-redundancy assessment method (CRAM) is designed for measuring the CR of each feature, which guides the entire evolutionary process. In CRGEA, a novel initialization strategy combined with a multiple threshold selection mechanism (ISMTS) is developed to produce a high-quality initial population. A local acceleration evolution strategy (LAES) based on a parallel simulated annealing algorithm and a pruning method is developed to improve the local search ability of the CRGEA. The contributions of this paper can be summarized as follows:

(1) A new correlation-redundancy assessment method is designed in this paper for measuring the CR of each feature and paying more attention to the feature with high relevance and low redundancy of high-dimensional datasets to speed up the entire evolutionary process;

(2) A correlation-redundancy guided evolutionary algorithm is designed for solving MOFS of high-dimensional datasets. In CRGEA, CRAM first evaluates the CR of each feature, and produces high-quality initial populations. LAES performs deep searches combing the annealing stage around the best solutions to improve the local search ability of the CRGEA, which facilitates individuals in escaping local optima solutions and obtaining the best features subset;

(3) Numerical experiments are conducted based on 16 high-dimensional datasets, where nine datasets contain more than 1000 dimensions, three datasets have over 6000 dimensions, and two datasets have over 10,000 dimensions. The experiment results show that CRGEA can efficiently reduce redundant features while ensuring high accuracy compared to other state-of-the-art intelligent algorithms.

The following sections of this paper are structured in the following manner: Sect. 2 provides related works about MOFS, mutual information, K-Nearest Neighbor algorithm, etc. Section 3 presents a comprehensive explanation of the designed CRGEA. Section 4 describes the results obtained from analyzing 16 publicly high-dimensional datasets. In Sect. 5, a summary and discussion are provided based on the outcomes of the three numerical experiments. Finally, Sect. 6 concludes with an overview of the findings and future research directions.

This section presents the details of CRGEA to solve the MOFS. The flowchart of the CRGEA is described in Fig. 2. Algorithm 1 describes the main procedures of the designed CRGEA.

As shown in Fig. 1, firstly, a novel initialization strategy combined with a multiple threshold selection mechanism is developed to produce a high-quality initial population. Then, the multi-point crossover operator and hybrid mutation strategy are applied to search in multiple directions to improve the search ability. Then, the potential NDSs are obtained by the genetic operations. Next, a local acceleration evolution strategy is proposed to enhance the quality of NDSs and overall population quality for the next generation, which further improves the local search ability of the CRGEA. Select superior individuals to participate in next generation evolution. Genetic operations and local search strategy are iteratively performed until the stopping criterion is met, otherwise the algorithm is stopped and the best solutions are reported. The additional details of the CRGEA are described in the following subsections.

This section conducts three experiments to validate the effectiveness of the designed CRGEA and search strategies for solving MOFS. The first experiment is to compare the CRGEA with using all features to indicate the necessity of performing FS in classification. The second experiment is to verify the effectiveness and superiority compared with the other five well-known algorithms. In the last experiment, an ablation experiments and statistical analysis are used to prove that the designed strategies are effective. The KNN is used as the classifier to evaluate the selected feature subsets, and K-fold (\(K=5\)) cross-validation is introduced to assess the classification accuracy of KNN. All experiments in this study are coded in MATLAB R2018a and run on a PC with an Intel (R) Core (TM) i5-12400F CPU and 16G of RAM. The remaining parameters of the have been experimentally determined and set as follows: the population size equals 60, the maximum iteration equals 200, the crossover probability equals 0.9, the mutation probability equals 0.2, the initial temperature equals 10, the final temperature equals 1, the cooling coefficient equals 0.7, the number of cycles at each temperature level equals 3.

All experiments are based on 16 well-regarded high-dimensional datasets involving different domains from the research repository. The first five datasets are sourced from research [21], datasets 6–8 are sourced from research [1], and the last nine datasets are sourced from research [63]. Note that we preprocess the data at first, i.e., remove missing data and features with a constant value to reduce search space. Table 1 presents the details of the dataset, including the varying numbers of features, samples, and classes across different datasets. Unlike many existing studies, the cases in this paper are high-dimensional datasets.

In Sect. 4.1, the CRGEA is compared with without FS which demonstrates the necessity for performing MOFS in high-dimensional datasets. In Sect. 4.2, we analyze the \({f}_{1}\),\({f}_{2}\),IGD and HV metrics between each comparison algorithm, and perform a statistical analysis employing the Wilcoxon test. The performance superiority of CRGEA in tackling high-dimensional MOFS problems has been unequivocally demonstrated. Furthermore, we present the final Pareto frontier of all algorithms, which demonstrates that the Pareto frontier obtained by CRGEA exhibits greater diversity and convergence efficacy in comparison to the comparison algorithms. In Sect. 4.3, an ablation experiment is performed to prove the effectiveness of the designed ISMTS and LAES, and reveal that they both affect the performance of CRGEA. Among them, the designed initialization method can significantly improve the performance of CRGEA in solving high-dimensional MOFS problems. The local acceleration strategy can further improve the search ability and help the individuals jump out of the local optimal solutions. Then, we compare the distribution within the solutions space of the designed ISMTS with that of the TRI. The findings indicate that the proposed ISMTS method exhibits superior convergence and diversity characteristics. Finally, we compare the performance of the CRGEA using two different methods for evaluating the CR of each feature on 16 high-dimensional datasets, and the results demonstrate the effectiveness of the proposed novel correlation-redundancy assessment method.

Most of the literature on FS of high-dimensional datasets focuses on improvements in search strategies, ignoring the characteristics of the dataset itself such as the correlation and redundancy of each feature. This could potentially degrade the algorithm's search effectiveness. Thus, a correlation-redundancy guided evolutionary algorithm is designed to address high-dimensional FS with the objective of optimizing classification accuracy and the number of features simultaneously. A new correlation-redundancy assessment method is proposed to select the features with high relevance and low redundancy to speed up the entire evolutionary process. A novel initialization strategy combined with a multiple threshold selection mechanism is developed to produce a high-quality initial population. A local acceleration evolution strategy based on a parallel simulated annealing algorithm and a pruning method is developed to improve the local search ability of the CRGEA. Numerical experiments are conducted by comparing CRGEA with state-of-the-art algorithms on 16 high-dimensional datasets to demonstrate the superiority of CRGEA in solving MOFS of high-dimensional datasets. The results show that CRGEA outperforms the other comparative algorithms in \({f}_{1}\),\({f}_{2}\), IGD and HV metrics on all datasets. As the dimensionality of the data increases, this advantage becomes increasingly evident. The results of the statistical analysis support the conclusions. Additionally, an ablation experiment was performed to evaluate the potential impact of the proposed ISMTS and LAES on the algorithm's performance. The results demonstrate a significant enhancement in both the convergence speed and search capability of CRGEA when incorporating these proposed techniques. In addition, we also compare the performance of the algorithm using two different methods for evaluating the CR of each feature on 16 high-dimensional datasets. The results indicate that the proposed evaluation function can better evaluate the correlation and redundancy of each feature.

Despite the results from the aforementioned series of experiments highlighting the exceptional performance of the proposed CRGEA for solving MOFS of high-dimensional datasets. However, we mainly focus on the effect of correlation and redundancy of features on classification. The interactions between features are disregarded in this paper, which is common in biology [68‐70]. In the future, we will improve the proposed algorithm for solving interactions between features on biological datasets.