Exhaustive Exploitation of Nature-inspired Computation for Cancer Screening in an Ensemble Manner

In this study, we present a novel nature-inspired method called EODE for rapid identification of biomarker genes for multiple cancer types in multiple cancer gene expression datasets. A schematic overview of the algorithm is provided in Figure 1. The original input gene expression data $\mathcal{D}_{or}=\{(x_{1},y_{1}),...,(x_{n},y_{n})\}$ is considered, where $x_{i}=(x_{i,1},x_{i,2},...,x_{i,dim})$ represents a sample with $dim$ genes, $y$ belongs to the set $\{1,2,...,c\}$ indicating the consensus molecular subtypes, and $n$ is the total number of samples.

In the feature selection step, we employ the GWO to extract relevant biomarker genes after training our model on the training gene expression matrix $\mathcal{D}_{tr}$. Each base classifier from the pool $\mathcal{B}$ (including Discriminant Analysis (DISCR), Decision Tree (DT), K-Nearest Neighbor (KNN), Artificial Neural Networks (ANN), Support Vector Machine (SVM), and Naive Bayes (NB)) is initially trained using the input data. The best-performing classifier is then chosen as the evaluation classifier for feature selection.

The processed data is subsequently utilized to train and optimize a diverse ensemble model. Specifically, the data undergoes five-fold cross-validation to construct the final model $\Psi$. Initially, the data is partitioned into progressive subspaces using the K-means method to form clusters. These clusters are then utilized to train base classifiers, which are subsequently incorporated into the model pool. Models in the pool with below-average performance are filtered out. After that, the GWO approach is applied to optimize the model pool and identify the best possible combination. Finally, the model $\Psi$ is evaluated on the test data using a plurality voting strategy. The overall framework of EODE is summarized in Algorithm 1.

Considering a training cancer gene expression data $\mathcal{D}_{tr}=\{(x_{1},y_{1}),...,(x_{n},y_{n})\}$, where $x_{i}=(x_{i,1},x_{i,2},...,x_{i,dim})$ represents the feature vector and $dim$ denotes the number of features, $y$ belongs to the set $\{1,2,..,c\}$ representing the class, and $n$ is the number of samples. It is important to note that the high-dimensional nature of the gene expression data may include many irrelevant genes, which can negatively impact identification accuracy while increasing computational time [7]. Therefore, performing feature selection is crucial to preprocess the data effectively.

The Grey Wolf Optimizer (GWO), initially proposed by Mirjalili [37], is a swarm intelligence algorithm inspired by the social hierarchy and hunting behavior of grey wolves in nature. GWO offers advantages such as good convergence, minimal parameter tuning, and ease of implementation [38]. The core concept of GWO revolves around three primary predation behaviors: encircling prey, hunting, and attacking prey, which are performed based on the social hierarchy among the wolves. The social hierarchy in GWO consists of four levels: $\alpha$, $\beta$, $\delta$, and $\omega$, with $\alpha$ being the dominant wolf, followed by $\beta$ and $\delta$, while the remaining wolves are labeled as $\omega$. Wolves at higher ranks exert dominance over those at lower ranks, and $\alpha$, $\beta$, and $\delta$ play key roles in the algorithm, with $\alpha$ being the wolf king and $\beta$ and $\delta$ serving as potential successors. The $\alpha$ wolf represents the fittest solution and guides the pack towards promising search areas. The second and third best fit solutions are modeled as $\beta$ and $\delta$ wolves, respectively. The $\omega$ wolves represent the remaining weaker candidate solutions that follow the guidance of the $\alpha$, $\beta$ and $\delta$ wolves. During optimization, the candidate solutions iteratively update their positions towards the best three solutions until convergence upon the global optimal value. Specifically, a schematic representation of GWO is depicted in Fig. 2.

Building upon these foundations, we propose a nature-inspired feature selection method based on GWO, which comprises six essential components: classifier selection, population initialization, encircling prey phase, hunting phase, attacking phase, and feature selection objective function.

In this section, we propose a novel nature-inspired diverse ensemble learning method to improve the performance of cancer identification using selected features obtained through nature-inspired feature selection. Our method comprises diverse subspace generation, model pool generation, and model pool optimization.

Here, we analyze the time complexity of our proposed EODE algorithm. The detailed analysis is outlined as follows:

• •

  Feature Selection: The time complexity of the feature selection process depends on the algorithm used. Since we used GWO for feature selection, the time complexity is typically $O(T\times P\times F\times C)$, where $T$ is the number of generations, $P$ is the population size, $F$ is the number of features, and $C$ is the complexity of the fitness evaluation function. Generally, the feature selection process has a polynomial time complexity.

• •

  Diverse Subspace Generation: The time complexity of the diverse subspace generation mainly depends on the clustering algorithm used. Here, we applied the K-means algorithm, the time complexity is usually $O(K\times N\times I\times d)$, where $K$ is the number of clusters, $N$ is the number of data points, $I$ is the number of iterations, and $d$ is the dimensionality of the data. The diverse subspace generation process has a polynomial time complexity.

• •

  Model Pool Generation: The model pool generation involves training multiple base classifiers on each cluster. The time complexity depends on the complexity of the base classifiers and the number of clusters. Assuming the time complexity of training a base classifier on a single cluster is $O(N\times F\times C)$, where $N$ is the number of data points, $F$ is the number of selected features, and $C$ is the complexity of the training algorithm, the overall time complexity of model pool generation is $O(L\times N\times F\times C)$, where $L$ is the number of clusters. This process also has a polynomial time complexity.

• •

  Model Pool Optimization: The time complexity of the model pool optimization stage depends on the optimization algorithm used. We employed a nature-inspired optimization algorithm named GWO, the time complexity is typically $O(T\times P\times C)$, where $T$ is the number of generations, $P$ is the population size, and $C$ is the complexity of the fitness evaluation function. Similar to the feature selection process, the model pool optimization stage generally has a polynomial time complexity.

• •

  Ensemble Classifier Prediction: The time complexity of the ensemble classifier prediction is dependent on the number of models in the ensemble and the complexity of combining their predictions. Assuming we have $M$ models in the ensemble and the complexity of combining predictions is $O(M)$, the overall time complexity is $O(M)$. This process has a linear time complexity.

In summary, the overall time complexity is: Overall Time Complexity = Feature Selection + Diverse Subspace Generation + Model Pool Generation + Model Pool Optimization + Ensemble Classifier Prediction = O(T $\times$ P $\times$ F $\times$ C) + O(K $\times$ N $\times$ I $\times$ d) + O(L $\times$ N $\times$ F $\times$ C) + O(T $\times$ P $\times$ C) + O(M)

Since all these time complexities are polynomial, we can express the overall time complexity as the highest-order term in the sum. Therefore, the overall time complexity of the EODE algorithm is:

Overall Time Complexity = $\max${T $\times$ P $\times$ F $\times$ C, K $\times$ N $\times$ I $\times$ d, L $\times$ N $\times$ F $\times$ C, T $\times$ P $\times$ C, M}

The cancer gene expression datasets were collected from [44], and can be downloaded from the website https://schlieplab.org/Static/Supplements/CompCancer/datasets.htm. The 35 datasets contain multiple types of cancers with high-dimensional features, exceeding 1000 dimensions, while having relatively small sample sizes (as shown in TABLE 1). This poses the “Curse of Dimensionality” challenge, necessitating the development of a computational model with high robustness and good generalization capabilities to address the different cancers.

To enable rigorous evaluation, the collected raw datasets have been randomly split into disjoint training and testing sets in a 80:20 ratio prior to conducting experiments. The training sets, comprising 80% of the data, have been used for model training and hyperparameter tuning. The testing sets, comprising the held-out 20% of the data, have only been used for final evaluation of the fully trained model’s performance. This ensures an unbiased estimate of generalization capability. The precise training/testing splits has been done randomly while preserving class balance in each set. Specifically, the training and testing datasets can be downloaded from the following links: https://github.com/wangxb96/EODE/tree/master/TrainData and https://github.com/wangxb96/EODE/tree/master/TestData. For model selection and hyperparameter tuning, k-fold cross-validation (k=5) was utilized during model selection and hyperparameter optimization on the training data only. By segregating the training and testing data, we prevent information leakage and overfitting to the test set. This rigorous methodology allows us to evaluate true generalization error and robustness across multiple cancer types.

To evaluate the effectiveness of our proposed method, we compared it against several existing classifiers and ensemble algorithms widely used in the literature. Firstly, we compared our model with six base classifiers: DISCR (Discriminant Analysis) [45], DT (Decision Tree) [46], KNN (K-Nearest Neighbor) [47], ANN (Artificial Neural Networks) [48], SVM (Support Vector Machine) [49], and NB (Naive Bayes) [50]. These classifiers serve as the baseline for performance comparison.

Next, we compared our approach with seven evolutionary algorithms: ACO [51], CS [52], DE [53], GA [54], GWO [37], PSO [55], and ABC [56]. These algorithms are widely used for optimization problems. Furthermore, we evaluated our approach against four novel ensemble methods: PSOEL [27], EAEL [57], FESM [58], and GA-Bagging-SVM [59]. These methods were selected to demonstrate the effectiveness of our proposed approach in comparison to recent advancements in ensemble learning.

In addition, we compared our ensemble algorithm with six state-of-the-art ensemble classifiers: Random Forests (RF) [60], ADABOOST [22], RUSBOOST [61], SUBSPACE [62], TOTALBOOST [63], and LPBOOST [64]. Random Forests is a well-known bagging method [60], while ADABOOST is a popular boosting method [22]. RUSBOOST is a random undersampling boosting method designed to address class imbalance [61]. SUBSPACE trains random feature subsets to reduce estimator correlation [62]. TOTALBOOST and LPBOOST aim to maximize the minimal margin of learned ensembles and have the ability to self-terminate [63] [64].

By comparing our method against these diverse algorithms, we aim to showcase its superiority and effectiveness in addressing the cancer gene expression data classification problem. Moreover, we have opened all computational model for public accessibility at “https://github.com/wangxb96/EODE/tree/master/ComparisonAlgorithms”.

Our experiments were conducted on a desktop computer with the following specifications: an Intel(R) Core(TM) i7-10700KF CPU @3.80GHz, 32GB of RAM, and a 64-bit Windows 10 operating system using Matlab 2021a. We utilized six base classifiers, namely DISCR, DT, KNN, ANN, SVM, and NB, to construct the ensemble. The parameters for DISCR, KNN, SVM, and NB are summarized in TABLE II, while the rest of the classifiers were used with their default settings. Additionally, Random Forest (RF) [60], ADABOOST [22], RUSBOOST [61], SUBSPACE [62], TOTALBOOST [63], and LPBOOST [64] were employed with their default parameter values. Furthermore, the parameters for four novel ensemble classifier methods, namely PSOEL [27], EAEL [57], FESM [58], and GA-Bagging-SVM [59], were set to be consistent with the original papers.

In our experiments, the original data was randomly divided into training and test datasets with an 8:2 ratio. The five-fold cross-validation method was used for training the data. For the GWO algorithm in feature selection and ensemble optimization, the population size ($P$) was set to 100, the number of iterations was set to 50, and the threshold ($\theta$) was set to 0.5. Specifically, the threshold value $\theta$ in our study is utilized as a criterion within the Grey Wolf Optimizer algorithm to determine feature selection, and is not directly related to actual gene expression values themselves. In the clustering phase, the parameter $t$ was set to $\sqrt[5]{m}$. The detailed parameters of seven classical evolutionary algorithms, including ACO [51], CS [52], DE [53], GA [54], GWO [37], PSO [55], and ABC [56], are summarized in TABLE III, where the population size ($P$) and the maximum iteration ($max_{t}$) are set to the same values.

For ACO, ”tau” denotes the pheromone value, ”eta” denotes the heuristic desirability, ”alpha” denotes the control pheromone, ”beta” denotes the control heuristic, and ”rho” denotes the pheromone trail decay coefficient, which is set to 0.2. For CS, ”Pa” denotes the discovery rate, ”alpha” denotes the constant, and ”beta” denotes the Levy component. For DE, ”CR” denotes the crossover rate, and ”F” denotes the scale factor. For GA, ”CR” denotes the crossover rate, and ”MR” denotes the mutation rate. For PSO, ”c1” denotes the cognitive factor, ”c2” denotes the social factor, ”w” denotes the inertia weight, and ”Vmax” denotes the maximum velocity.

In our study, we conducted performance comparisons of EODE with several other nature-inspired ensemble learning algorithms, namely PSOEL, EAEL, FESM, and GA-Bagging-SVM. The experimental results are summarized in Figure 3, where Figure 3(A) presents detailed classification results, Figure 3(B) illustrates the performance comparisons of EODE against the other ensemble methods, and Figure 3(C) showcases the average performance values of these methods.

As shown in Figure 3(A), EODE achieved the best results among all methods on 26 out of the 35 datasets. Specifically, EODE attained 100% classification accuracy on 7 datasets and achieved over 90% accuracy on more than half of the datasets. These results highlight the robustness of EODE in handling various types of cancers and its ability to provide highly accurate classifications. From Figure 3(B), it is evident that EODE outperformed the other nature-inspired ensemble learning algorithms. The performance comparisons clearly demonstrate the superiority of EODE in terms of test accuracy. To provide a comprehensive performance overview, we present the average performance across all 35 cancer gene expression datasets in Figure 3(C). The results indicate that EODE outperformed PSOEL by 6% and exhibited more than a 10% improvement compared to the other methods. These findings strongly support the conclusion that EODE performs better than other nature-inspired ensemble methods in the context of cancer gene expression classification.

In our study, we conducted a comprehensive analysis and comparison of the performance between our proposed ensemble approach, EODE, and single classifier approaches. The experimental results, as shown in Figure 4, clearly demonstrate the superiority of EODE in terms of classification accuracy for cancer gene expression datasets. EODE achieved the best classification accuracy for over 55% of the datasets, surpassing all single classifiers. This indicates the effectiveness and robustness of our ensemble approach in handling cancer gene expression classification tasks. Moreover, when considering the average performance across all 35 cancer gene expression datasets, EODE consistently outperformed all single classifiers. Specifically, our ensemble approach exhibited remarkable improvements compared to the worst classifier, with an increase in performance of nearly 33%. Furthermore, EODE consistently achieved performance improvements of more than 10% compared to the majority of the base classifiers.

These findings clearly highlight the advantages of our ensemble approach over traditional single classifier methods. By leveraging the collective wisdom of multiple classifiers, EODE effectively addresses the challenges posed by cancer gene expression classification, resulting in superior classification accuracy and overall performance. Figure 4 provides a visual representation of the experimental results, further supporting the conclusions drawn from our performance comparisons. The results validate the effectiveness of our proposed ensemble approach, highlighting its potential as a valuable tool in the field of cancer gene expression analysis.

To further evaluate the performance of the proposed EODE method, we compared it against other state-of-the-art evolutionary algorithms, including: Ant Colony Optimization (ACO), Cuckoo Search (CS), Differential Evolution (DE), Genetic Algorithm (GA), Grey Wolf Optimizer (GWO), Particle Swarm Optimization (PSO), and Artificial Bee Colony (ABC).

The experimental results are summarized in supplementary Figures 1 and 2. Supplementary Figure 1 shows the classification accuracy of different methods on each of the 35 cancer gene expression datasets, with the first 7 sub-figures presenting results on individual datasets and the last sub-figure reporting the average performance across all datasets. As seen in supplementary Figure 1, EODE obtains the best classification accuracy on over 60% of the datasets. Notably, there is an improvement of 5-8% in average classification accuracy achieved by EODE compared to other evolutionary algorithms. Supplementary Figure 2 depicts the number of features (i.e. biomarker genes) selected by each method on each dataset. We can observe that EODE selects the smallest feature subset in nearly 60% of datasets, indicating its ability to identify the most informative genes.

Overall, from both supplementary Figures 1 and 2, we can deduce that EODE consistently demonstrates the best average performance across all 35 cancer gene expression datasets, outperforming other state-of-the-art evolutionary methods. This validates the effectiveness and robustness of the proposed EODE approach in discovering critical biomarker genes for cancer classification.

To further validate the effectiveness of the proposed EODE method, we conducted experiments comparing its performance to other state-of-the-art ensemble learning classifiers on the 35 cancer gene expression datasets. The methods considered for comparison include: Random Forest (RF) [60], ADABOOST [22], RUSBOOST [61], SUBSPACE [62], TOTALBOOST [63] and LPBOOST [64].

The results are shown in Figure 5. Figure 5(A) depicts a heat map of the classification accuracy of different methods on each of the 35 datasets, where darker colors indicate better performance. This heat map visualization allows us to qualitatively compare the performance of models across various cancer types. Figure 5(B) summarizes the mean classification accuracy of each method averaged over the 35 datasets. The proposed EODE method achieves 6-32% better performance compared to other ensemble learning classifiers, demonstrating its superior predictive ability. Figure 5(C) presents box plots to compare the distribution of classification accuracies obtained by each method on different datasets. We can observe that the median accuracy of EODE is higher than all other methods, indicating its stable and robust performance. Moreover, the box plot of EODE is more narrow compared to others, showing the consistency of results obtained.

Overall, these quantitative and qualitative comparisons presented in Figure 5 validate that the proposed EODE method achieves the best classification accuracy on over 70% of the cancer gene expression datasets, outperforming other state-of-the-art ensemble classifiers. This clearly demonstrates the effectiveness and robustness of the EODE approach for cancer classification using gene expression data.