1 INTRODUCTION↩︎

Feature selection involves discarding as many features or variables as possible without compromising classification accuracy. The removal of irrelevant and redundant information not only reduces computational requirements but also enhances the classifier’s performance by mitigating the curse of dimensionality and facilitates model interpretation [1]–[4].

In recent years, machine learning problems have expanded to include thousands, millions, or even billions of variables, making feature selection a crucial preprocessing step [3]. This practice diminishes data dimensions, simplifying tasks for classifiers and concurrently diminishing memory and computational costs in large-scale datasets. However, excessive feature elimination can lead to classification failure, presenting a delicate balance between the number of features and classification accuracy [1], [2], [5].

Feature selection finds broad applications across various domains, including machine learning and data science [6], [7], bioinformatics and computational biology [8], [9], text mining [10], image analysis and medical diagnosis [11], [12], natural language processing (NLP) [13], [14], financial analysis and economics [15], [16], and many other fields.

The mainstay of classical feature selection methods falls into three categories: wrapper, filter, and embedded methods [3], [8], [17]–[19]. Filter-based methods analyze data characteristics and assess features without engaging learning models [19]. Embedded methods incorporate variable selection into the training process, varying for each learning machine. Wrappers score variable subsets based on predictive power under the black-box of the machine [17], [18].

In the realm of multi-objective feature selection algorithms, the Non-dominated Sorting Genetic Algorithm II (NSGA-II) [20], a widely recognized algorithm, has been employed in several research studies [1], [2], [21]. This algorithm, a multi-objective scheme of the evolutionary genetic algorithm (GA), comprises three fundamental components: initialization, generating new candidate solutions, and selection. The effectiveness of population-based evolutionary algorithms heavily relies on these components, particularly in providing diverse solutions during optimization. Initialization is a critical step, as confirmed by Kazimipour et al. [22], who reviewed popular techniques introduced before 2014 and classified them based on randomness, compositionality, and generality. Rahnamayan et al. [23] proposed an opposition-based initialization method, accelerating optimizer convergence. Burke et al. [24] demonstrated that heuristic initialization methods enhance diversity and performance.

Additionally, the substitution of individuals in the population acts as a form of re-initialization, commonly employed when an evolutionary optimization method converges [25]. Ghosh et al. [25] highlighted that substituting the worst individuals, and re-entering a dropped-out individual, significantly improves population diversity and, consequently, GA performance. Cobb et al. [26] introduced Random Immigrants, replacing a fraction of the population randomly in each generation to enhance GA performance. These insights motivated our investigation into the effect of substitution in the multi-objective GA scheme, NSGA-II, applied to feature selection.

In this study, we present a strategy to augment population diversity in multi-objective feature selection algorithms. Our findings underscore a critical point: commonly used crossover and mutation operations lack the potency to generate valuable diverse individuals across the search space. Injecting random individuals from outside the population proves essential for boosting algorithm exploration. In other words, auxiliary re-initialization components are necessary to enhance population diversity.

The organization of this paper is as follows: Section II provides a detailed background review, Section III outlines our proposed method, illuminating the steps and techniques employed, Section IV presents results and analysis from our study, and Section V concludes with remarks.

2 Background Review↩︎

2.1 Multi-objective Optimization↩︎

Algorithms designed to address multi-objective problems typically navigate trade-off decisions, yielding a set of solutions rather than a singular one. This array of solutions is commonly referred to as the Pareto front or non-dominated solutions. The establishment of the Pareto front is based on the principle of dominance, a criterion used for the comparison of solutions.

Definition 1. Multi-objective Optimization [27] \[\begin{align} \begin{aligned} & Min/Max\; F(\pmb x)=[f_{1}(\pmb x),f_{2}(\pmb x),...,f_{M}(\pmb x)] \\ &s.t. \quad L_{i}\leq x_{i}\leq U_{i}, i=1,2,...,d \end{aligned} \end{align}\] Here, \(\pmb x\) represents the feature set (i.e., candidate solution), \(M\) denotes the number of objectives, \(d\) equals the number of variables (i.e., dimension), and each variable’s value, denoted as \(x_{i}\), falls within the interval \([L_{i}, U_{i}]\). However, in binary multi-objective optimization problems like feature selection, \(x_{i}\) is restricted to only two values, either from the set \(\{0, 1\}\) or \(\{True, False\}\). The objective function, denoted as \(f_{i}\), aims for either minimization or maximization [27]. In such problems, a widely adopted approach for comparing candidate solutions involves the concept of dominance.

Definition 2. Dominance Concept
If \(\pmb x=(x_{1},x_{2},...,x_{d})\) and \(\acute{\pmb x}=(\acute{x}_{1},\acute{x}_{2},...,\acute{ x}_{d})\) are two vectors in a minimization problem search space, \(\pmb x\) dominates \(\acute{\pmb x}\) (\(\pmb x\prec\acute{\pmb x}\)) if and only if \[\begin{align} \begin{aligned} &\forall i\in{\{1,2,...,M\}}, f_i(\pmb x)\leq f_i(\acute{\pmb x}) \wedge\\ &\exists j \in{\{1,2,...,M\}}: f_j(\pmb x)<f_j(\acute{\pmb x}) \end{aligned} \end{align}\] This concept delineates the optimality of a solution within a multi-objective space. A candidate solution, \(\pmb x\), is considered superior to another solution, \(\acute{\pmb x}\), if it is not inferior in any of the objectives and, at a minimum, exhibits superior performance in one of the objectives. Solutions that are not dominated by any other form the Pareto front and are termed non-dominated solutions [28].

Another prevalent metric for comparing candidate solutions in multi-objective problems is the crowding distance. In computing the crowding distance, individuals are sorted based on each objective, and boundary individuals (minimums and maximums) receive an infinite distance assignment. Other individuals are assigned the sum of the normalized Euclidean individual distances from their neighbors with the same rank across all objectives. This assesses an individual’s importance relative to the density of surrounding individuals [20].

Multi-objective algorithms strive to identify the Pareto front through the utilization of generating strategies/operators and selection schemes. The non-dominated sorting (NDS) algorithm [20] stands out as a popular selection strategy that operates on the dominance concept. It categorizes the population’s solutions into different levels of optimality. The algorithm initiates by identifying all non-dominated solutions in the first rank. To determine the second rank of individuals, non-dominated candidates are removed, and the process repeats for the remaining ones. This iterative procedure continues until all individuals are grouped into distinct Pareto levels. Deb et al. [20] introduced the renowned multi-objective optimization method, NSGA-II, based on this concept.

2.2 Multi-objective Feature Selection↩︎

To transform feature selection into a binary optimization problem, each feature’s status is denoted by a binary variable. With the dataset’s features having the option of being retained or removed, each variable assumes only two states. Consequently, each individual, or solution, represents a distinct feature configuration. The classification accuracy, calculated by masking the dataset’s features and employing a regular classifier such as \(k\)-Nearest Neighbor (\(k\)-NN), Support Vector Machine (SVM), or Decision Tree (DT), serves as one objective value for each individual. Additionally, recognizing the significance of the remaining features, especially in large-scale databases, we define the ratio of retained features as the second objective in our optimization problem.

Jiao et al. [29] introduced a multi-objective optimization approach for feature selection in classification, named PRDH. In this work, the authors have devised a duplication handling method to augment diversity in both the objective and search spaces. Their method transforms the multi-objective feature selection problem into a constrained optimization problem, emphasizing classification performance. A novel constraint-handling method is employed to select feature subsets featuring more informative and strongly relevant features.

Cheng et al. [30] demonstrated that the variable granularity search-based multi-objective evolutionary algorithm, VGS-MOEA, significantly narrows down the search space for large-scale feature selection problems. In this method, each bit of the individuals represents a feature subset, with the subset’s granularity starting larger and gradually refining, aiming for higher-quality features. This technique markedly enhances feature selection efficiency and accuracy.

In efforts to improve the evaluation and selection of solutions for multi-objective optimization problems, [31] introduces a novel fitness evaluation mechanism (FEM) utilizing fuzzy relative entropy (FRE). To effectively tackle the problem, a hybrid genetic algorithm is employed within this framework. Deb et al. introduced NSGA-III [32] as a reference-point based many-objective optimization algorithm that prioritizes non-dominated population members in proximity to specified reference points, particularly effective when dealing with four or more objectives.

More recently, Nikbakhtsarvestani [33] proposed a multi-objective coordinate search optimization, outperforming NSGA-II, especially in computationally expensive applications with a limited number of function calls. Zanjani et al. [1] introduced a method for binary multi-objective optimization using coordinate search for feature selection. In this approach, a variable of each individual on the Pareto front is flipped to generate new individuals in each generation. The presented results markedly surpass those of NSGA-II. They also proposed binary Compact NSGA-II [2], employing Probability Vectors (PVs) to preserve the distribution of solutions, alongside the Pareto front, instead of maintaining two populations during the process.

3 PROPOSED METHOD↩︎

3.1 Objectives↩︎

Enhancing classification accuracy and minimizing data dimensionality constitute the primary objectives of feature selection. Consequently, the calculation of two objectives for each candidate solution (or feature set) becomes imperative. The first objective function computes the classification accuracy, achieved through the utilization of a \(k\)-NN classifier to assess both the training set (during the optimization phase) and the test set (post-optimization for the evaluation of final solutions).

Given that our optimization problem is of a minimization nature, we calculate the classification error as the first objective, relying on the predictions made by the \(k\)-NN model:

\[\label{f1} \mathit{Classification \:Error}= 1 - \frac{\# Correct\: Predictions}{Total \:\# Predictions}\tag{1}\]

The second objective is the diminution of the selected features ratio. Its computation involves tallying the count of features with a value of 1 (or True) for each feature set, followed by dividing this count by the total number of features:

\[\label{f2} \mathit{Ratio\: of\: Selected\: Features}=\frac{Number \:of \: Trues }{Total \:\# Features }\tag{2}\]

Both of these objectives possess real values within the interval \([0, 1]\). Prior research has indicated their inherent conflict, so they are suitable candidates for multi-objective optimization, as highlighted in [5].

3.2 Proposed Algorithm: Binary Diverse NSGA-II↩︎

Despite the effectiveness of NSGA-II, it frequently becomes stuck in local optima and prematurely converges. Our observations suggest that the average pairwise distance among individuals in the feature space is notably low, and as the algorithm progresses, this value declines rapidly. Therefore, a plausible reason for the algorithm’s failure to discover the global optimum lies in its insufficient exploration of the search space and the production of diverse solutions.

Based on our experiments and literature findings, the most effective technique for population initialization to enhance diversity and explore the search space is genuine uniform initialization [5], [34]. The commonly used Bit-string Uniform (BU) binary population initialization method fails to provide chromosome-wise uniformity in the population, impacting the quality of the population in the long run. In contrast, the genuine uniform approach or Uniform Covering (UC) binary initialization results in a more diverse population, featuring individuals from various regions of the search space with both chromosome-wise and gene-wise uniformity. In this method, instead of having 50% True variables in nearly all individuals containing a substantial number of variables, the number of True variables is uniformly distributed across feature sets.

Subsequently, the objective values of each individual are calculated based on the utilized classifier and Equations 1 , 2 . Following this, a non-domination sorting determines the rank of each solution in the population. After generating new individuals - children - through crossover and mutation operations, a non-dominated sorting is executed, and the best individuals survive based on their ranking and crowding distance, akin to the original NSGA-II algorithm.

To address diversity degradation, the proposed idea involves replacing the worst-ranked candidate solutions with newly-generated solutions. At the end of each generation, we replace the last front with new random subsets. These new individuals are generated using the UC initialization method [34], and the number of selected features (i.e., True variables) falls within the range of the size of the smallest and largest feature subsets in the current population.

Suppose the size of the smallest (individual with the lowest number of True variables) and largest (individual with the highest number of True variables) feature subsets in the population is given by \(\alpha\) and \(\beta\), respectively. \([\alpha, \beta]\) determines the range of sizes for reinitialized individuals in the population. For each individual on the last front that must be replaced, a random integer (e.g., \(TrueIndices\)) within the range of \([\alpha, \beta]\), representing the number of features in the new individual, is generated. Then, \(TrueIndices\) number of variables of the new individual are randomly set to True, while the others are set to False. This constraint, applied to the number of selected features of the new solutions, enhances the algorithm’s performance by incorporating prior knowledge from the population and the process, avoiding the generation of entirely random candidate solutions.

Note that in any generation where the entire population is located on a single front, the reinitialization process is bypassed for that generation.

In contrast to the members generated using crossover and mutation operators, which are in the neighborhood of the previous members and have a small distance from their parents, the new random individuals potentially originate from unseen parts of the landscape and aid in exploring and discovering new areas. A sufficient diversity of members and exploration is particularly critical in vast search spaces.

The termination condition is defined based on the total number of function calls (i.e., evaluations) so that in problems with a demanding evaluation function, such as classification, algorithms can be compared fairly within a specific number of function calls. The number of generations is not an appropriate termination condition because the proposed method’s number of evaluations and computations may vary based on the number of individuals on the last front in each generation.

The pseudocode of the proposed binary diverse NSGA-II is presented in Algorithm [alg-one]. Additionally, Algorithm [alg-two] provides details on the genuine initialization method or UC.

4 EXPERIMENTAL RESULTS AND ANALYSIS↩︎

4.1 Datasets↩︎

We have evaluated the efficacy of our proposed approach (i.e., diverse NSGA-II), NSGA-II, and the genuinely initialized version of NSGA-II, across twelve extensive datasets within the domains of microarray and image analysis. The objective is to identify the optimal feature set. These datasets are characterized by a substantial number of features paired with a relatively limited number of instances. Consequently, the reduction of features is imperative to enhance classification accuracy. The properties of the employed datasets are outlined in Table 1.

4.2 Experimental Settings↩︎

We conducted multiple runs of the algorithms, repeating the process 31 times with different seeds to mitigate the impact of stochasticity. In each iteration, a distinct twenty percent of instances from each dataset were randomly chosen as a test set. So, the method of validation is Repeated Random Subsampling validation or Monte Carlo Cross-Validation. Recognizing the computational expense associated with feature selection on large-scale datasets, we maintained a fixed number of function calls at 15,000 for the mentioned algorithms, ensuring a fair comparison. Our experiments primarily rely on the pymoo framework [40]. Further details on hyperparameter settings can be found in Table 2.

Our objective is to minimize both the classification error and the ratio of selected features to all features, both of which fall within the real value interval [0,1]. A suitable multi-objective evaluation metric for comparing algorithm performance is hypervolume (HV), with the reference point set at \((1, 1)\). Furthermore, to calculate the classification error, we utilize the \(k\)-NN classifier with a fixed parameter \(k\) set to 5 across all datasets and experiments.

4.3 Numerical Results and Analysis↩︎

Table 3 shows that across all datasets, our method notably surpasses regular NSGA-II in terms of the HV performance metric. Average HV values during optimization for NSGA-II with genuine initialization (red) and the proposed binary diverse NSGA-II method (blue) for sample datasets are depicted in Fig. 1. The genuine initialization establishes a markedly superior starting point for the HV value compared to the regular NSGA-II, and the substitution of low-ranked individuals accelerates HV growth by promoting exploration of the search space. The combination of these techniques facilitates a rapid HV increase, resulting in an average value of 0.97, as shown in Table 3. Notably, for half of the datasets, the mean train HV exceeds 0.99, with none falling below 0.89. Conversely, NSGA-II fails to attain a train HV of 0.67 or higher for any dataset.

Furthermore, we observed that, in most cases, the diverse NSGA-II generates a greater number of candidate solutions on the Pareto front, all featuring fewer features compared to solutions on NSGA-II’s Pareto front. Table 3, which includes the average final HV values for the train and test Pareto fronts after 15,000 function calls, confirms the statistically significant superiority of the proposed method’s numerical results against NSGA-II across all cases. These results have been validated using a statistical t-test at a 95% confidence level. Notably, the HV value on the test set consistently exceeds 0.70 for all datasets when employing our proposed method, while the maximum test HV value for the regular NSGA-II is 0.58. Moreover, in 9 out of 12 cases, the test HV values obtained from our proposed method surpasses that of the genuinely initialized NSGA-II, and we see three statistical ties.

This table also underscores the substantial impact of the initialization approach on the final HV value, surpassing the effect of solution substitution. Specifically, employing the genuine initialization enhances the train set HV by approximately 0.42 and the test set HV by about 0.34. The addition of a straightforward method to diversify the population further, such as the replacement technique, yields an average improvement of approximately 0.04 on the test set HV.

Fig. 2 illustrates the average pairwise Hamming distance plots obtained during optimization using NSGA-II with and without the substitution component. The plots highlight that substituting low-ranked individuals significantly increases the distance between individuals during the process, thereby enhancing diversity. Both methods employed random BU initialization for a fair comparison in this experiment.

Table 4 presents the average of the maximum accuracy over the 31 runs and the ratio of the features selected in the most accurate solutions. These results have also been validated using a statistical t-test at 95% confidence level. Across all datasets, except for LUNG and pixraw10P (D3 and D8), our method significantly enhances the classifier’s accuracy compared to the regular NSGA-II. For the mentioned two datasets, we see statistical ties. In essence, looking at it from a singular objective perspective, diverse NSGA-II method consistently achieves superior accuracy as well. This heightened accuracy is accomplished using less than 1% of the total features, a substantial reduction compared to the number of features selected by NSGA-II. The average number of selected features in the most accurate solution found by NSGA-II across various datasets is approximately 5508, whereas the improved scheme identifies better solutions with about 164 times less memory requirement, averaging 33.5 variables. Consequently, we benefit from both improved accuracy and reduced memory consumption, potentially expediting pipelined processes.

Furthermore, Table 4 illustrates that the impact of substitution in improving algorithm performance to find a more accurate solution is almost comparable to the initialization method. On average, it elevates maximum accuracy by over 3% compared to NSGA-II with genuine initialization, concurrently reducing the number of features by over three times.

Table 5 displays the 95% confidence intervals for the number of selected features for the solutions on the Pareto front. According to these results, the average value of the interval for the second objective obtained from the proposed method is significantly superior to that of the other models. This finding further confirms the effectiveness of both employed techniques in enhancing feature reduction.

2.5pt

The average ratio of replaced solutions over the generations in the proposed method is also presented in Table 6. On average, 11% of the solutions are positioned on the last front and replaced in each generation. Remarkably, this percentage remains almost consistent across all twelve datasets, showing no significant variations. Fig. 3 includes several sample plots depicting the ratio of replaced solutions over the generations. As shown in the plots, the number of solutions on the last front exhibits no discernible correlation with the generation number or the dataset overall, with the curve fluctuating throughout the generations. However, the initial points of the curves are generally lower, indicating higher diversity in the initial population. The curve occasionally drops to zero when all solutions are concentrated on a single front, resulting in no solution replacements in that generation.

5 CONCLUSION REMARKS↩︎

With the growing importance of feature selection in large-scale real-world datasets, there’s an increasing demand for efficient binary multi-objective optimization algorithms. These algorithms should not only minimize memory and computational demands but also reduce classification errors or enhance other processing tasks. In this research, we improved the population diversity of the NSGA-II algorithm through a novel approach, resulting in enhanced performance. Our method replaced the Bit-string Uniform binary population initialization with a more effective genuine initialization strategy, significantly increasing population diversity. Additionally, we proposed substituting candidate solutions on the last front in each generation to further diversify the population and efficiently explore the search space. Our findings demonstrated that these techniques not only substantially reduce the number of selected features but also maintain or boost classification accuracy, thereby increasing the Hypervolume (HV) of both train and test sets. The complexity of this method matches that of NSGA-II. One drawback of replacing solutions is that we may lose some information and potentially beneficial solutions.

Our proposed method is tailored for binary multi-objective optimization in general, with feature selection serving as a specific case study. However, its utility extends far beyond feature selection to address a wide range of binary optimization challenges. Moreover, the demonstrated benefits of dimension reduction observed in this study, particularly in enhancing classification and \(k\)-NN performance, can also be harnessed to improve efficiency and effectiveness across various other processing tasks. Furthermore, given that crossover and mutation operations in genetic algorithms like NSGA-II do not generate new individuals from diverse parts of the landscape, we recommend exploring alternative techniques to enhance population diversity as a promising avenue for future research.

References↩︎