1. Introduction
The study of tumor genes based on microarray data has always been the focus of current cancer research microarray gene expression profile data extracted using biochip technology can be used to study the causes of tumors. By analyzing of microarray gene expression profile data, we can explore which tumor genes are related to cancer development and develop specific prevention mechanisms and treatment methods. However, the high-dimensional characteristics of gene expression profile data and many redundant and noisy genes pose significant challenges to gene data analysis. Therefore, selecting genes most associated with cancer, based on microarray gene expression data, is the key to improving tumor classification performance. Recently, many methods for gene selection for tumors have been proposed. Hybrid gene selection methods have attracted increasing attention recently.
Because the training process of tree modeling has the advantage of built-in feature selection processing, which can prevent overfitting, gene selection methods based on tree models have gained attention and research. For example, Rao et al. [1] proposed a hybrid feature-selection method based on bee colonies and gradient boosting trees. Horng et al. [2] proposed resampling to avoid overfitting and used decision rules in decision trees to select a set of reliable genes. Xiong and Wang [3] proposed a hybrid gene selection algorithm based on improved ant colony optimization and a random forest. Dagnew and Shekar [4] proposed a feature selection algorithm based on random forest trees and an integrated classification method based on hard and soft voting. Recently, Deng et al. [5] proposed a gene selection method based on extreme gradient boosting (XGBoost) [6] and a multi-objective genetic algorithm.
The afore-mentioned methods use a single-tree model for gene selection to improve tumor classification performance. However, gene selection based on a single-tree model often exhibits poor robustness for super-high-dimensional and small-sample microarray datasets, leading to the loss of useful information, and the final classification result is not ideal. The fundamental reason for this is the bias of the single-tree model learning algorithm. A good classification result of a tree model for one microarray dataset does not indicate good classification performance for other microarray datasets.
Motivated by the afore-mentioned limitations, in this study, ensemble gene selection methods based on multiple-tree models were investigated to improve the classification performance of tumor identification based on microarray gene data. We selected the three most representative tree models: ID3 [7], random forest [8], and gradient boosting decision tree (GBDT) [9]. Each tree model selects the top-n genes from the microarray dataset based on its intrinsic mechanism. The final subset of genes was selected using the intersection, union, and cross-union operations. The ensemble gene selection algorithms corresponding to the three different operations are respectively named multiple-tree model intersection (MTMI), multiple-tree module union (MTMU), and multiple-tree module cross-union (MTMCU). The effectiveness of the proposed gene selection method was evaluated using support vector machine (SVM) [10] and naïve Bayes [11] on five public microarray gene expression datasets. The experimental results demonstrated that MTMU is significantly superior to gene selection based on a single-tree model and other competitive gene selection algorithms in terms of classification accuracy.
The remainder of this study is organized as follows. Section 2 provides preliminary information on the techniques used in our study. In Section 3, we present three methods for gene selection based on integrated-tree models. Section 4 presents the experimental results and an analysis of the proposed algorithms, and other related methods, on five public benchmark gene expression datasets. Finally, Section 5 presents the conclusions and future work.
2. Related Works
2.1 ID3 Decision Tree
A decision tree is a tree structure comprising multiple branch nodes and branches. The decision tree algorithm is an important algorithm in machine learning classification methods. ID3 [7], C4.5 [12], and the classification and regression tree (CRAT) [13] are the most commonly used decision tree algorithms. The ID3 algorithm is a classical decision tree algorithm. Many other decision tree algorithms can be generated based on the ID3 algorithm through extension and improvement.
The ID3 algorithm was proposed by Quinlan [
7] in 1986, and its basic theory is information entropy. The ID3 algorithm tree judges the attribute-based information gain of each internal node, divides the criteria according to judgment, and outputs the judgment results for each branch.
The core of the ID3 algorithm uses information entropy to determine the attributes used for node segmentation. Entropy is defined as follows:
where [TeX:] $$P\left(x_i\right)$$ is probability of the value of [TeX:] $$x_i$$ for feature X, and C denotes the number of categories. ID3 is determined based on the information gain and the calculation method is as follows:
where the
[TeX:] $$E(X)$$ is the entropy of feature X, and
[TeX:] $$E(X \mid Y)$$ is the entropy of feature X under the condition of feature Y, which is defined as
2.2 Random Forest
Random forest [8] is a classical ensemble learning algorithm that processes sample data by combining multiple decision trees to form an ensemble classifier. In 2001, Breiman [8] proposed a random forest algorithm in Machine Learning, which uses the CART tree as the base learner to solve the overfitting problem that may occur during classification and regression. Fig. 1 shows the steps of random forest training sample data.
Training process of random forest.
The random forest method scores the importance of each feature of the dataset and then selects the important features based on the score. The Gini coefficient was used as the evaluation index, calculated as follows:
where D is the sample set and
[TeX:] $$p_i$$ is the probability of occurrence of each category.
2.3 Gradient Boosting Decision Tree
The GBDT [
9], also known as the multiple additive regression tree (MART), is an iterative machine learning algorithm [
9,
14]. The gradient boosting decision tree uses the residual gradient to optimize the regression tree and combines several weak learners into strong learner in a certain manner. The GBDT is a boosting model and its training process is shown in Fig. 2.
Training process of GBDT.
The principle of GBDT is to optimize the residual so that the residual after each iteration is gradually reduced. After several iterations of GBDT, the output results are not different from the actual results, the GBD training model reaches the optimal value, and the loss function value reaches the minimum or remains unchanged. GBDT algorithm builds a model in the optimal descent direction based on the loss function, which is embodied as follows. Assuming
[TeX:] $$\left\{x_i, y_i\right\}_{i=1}^n$$ is the original data, softmax is the loss function of GDBT,
[TeX:] $$h(x)$$ is the base learner, where
[TeX:] $$x_i=\left(x_{1 i}, x_{2 i}, \ldots, x_{p i}\right)$$, p is the number of features, and
[TeX:] $$y_i$$ is the prediction label. For model β, the initialization estimate is
Next, the gradient direction of residuals is calculated through iterations:
where [TeX:] $$i=\{1,2, \ldots N\}, m=1: M \text {. }$$ The base learner was then used to train the sampled data and obtain the initialization model. According to the least-squares method, the parameter [TeX:] $$a_m$$ of the model can be obtained as:
To minimize the loss function, a new step size of the model was calculated using the formula:
Finally, the new model is updated according to Formula (9):
3. Integrated Gene Selection Method based on Tree Model
Feature selection is at the core of the tree model construction. Node generation and branch processing of the tree model preferentially select features that can better distinguish the training dataset. This improves the training efficiency of the decision tree, and accelerates its convergence. However, selecting the optimal features in the tree model construction process is an open problem. There is uncertainty regarding the selection of gene features, specifically for high-dimensional microarray datasets. Therefore, we adopted an integration strategy to eliminate the inaccuracy caused by a single-tree model in selecting the optimal gene by constructing multiple tree models. In contrast to the single-gene selection tree model, the integrated gene selection tree model based on an integration strategy can select the optimal feature subset with strong robustness. This study used the three most representative tree models for gene selection: decision tree, random forest, and GBDT. Fig. 3 demonstrates the gene selection based on the three tree models’ intersection, union, and intersection-union operations. Each tree model calculates the importance score of each gene according to its criteria and ranks these genes in descending order. The top-n genes were then selected for each tree model, and three final gene subsets were obtained using intersection, union, and intersection-union operations. The ensemble gene selection algorithms corresponding to the three different operations are respectively, called MTMI, MTMU, and MTMCU. The formal definitions of the three methods are expressed by formulas (10)–(12), where [TeX:] $$M_{D T}^n, M_{R F}^n, \text{ and } M_{G B D T}^n$$ represent the sets of top-n genes selected by each method.
Three types of ensemble gene selection based on multiple tree models.
4. Experimental Results and Analysis
4.1 Datasets
Five publicly available microarray gene-expression profile datasets were used to evaluate the performance of the proposed algorithm. The basic information on these datasets is listed in Table 1 [
15-
19]. From Table 1, ultra-high dimensionality and a small number of samples are common characteristics of these datasets.
4.2 Compared Algorithms
The experiments were conducted in two stages. First, three related tree models, the decision tree, random forest, and GBDT algorithms, were selected for comparison. Secondly, we selected some of the most advanced gene selection methods published recently, such as BGWOPSO [20], FCSVM-RFE [21], KDI [22], and MultiSURF [23], for experimental comparison.
To verify the effectiveness of the proposed integrated-tree model gene selection method, we compared it with three single-tree models: decision tree, random forest, and GBDT. These algorithms were used to select the top-n genes (5, 10, 20, 50, 100). Two standard classifiers, SVM and naïve Bayes, were used to evaluate the classification performance of selected gene subsets. To ensure the reliability of the experimental results, a 10-fold cross-validation method was used to evaluate the accuracy of each selected gene subset. The classification algorithms used in this study were implemented from the Python sklearn library.
4.3 Comparison with Single Tree Model-based Methods
Fig. 4 shows the accuracy comparison of MTMI, MTMU, and MTMCU, and the other three singletree models using SVM and naïve Bayes classifiers for the five microarray datasets listed in Table 1. The original method is results obtained without gene selection. The left column in Fig. 4 shows the results of the SVM classification after selecting the top 5, 10, 20, 50, and 100 genes using all comparison algorithms. Accordingly, the right column shows the results of the naïve Bayes classification after selecting the top 5, 10, 20, 50, and 100 genes using all comparison algorithms.
As shown in Fig. 4, if the selected top number of genes was less than 100, there was no intersection of the genes selected by the decision tree, random forest, and GBDT in the HD dataset. This shows that the sorting results of the gene scores obtained by the three single-tree model algorithms differed significantly.
Average accuracy of top-n genes on five datasets
The best results are highlighted in bold.
Table 2 lists the average classification accuracy of the top-n (5, 10, 20, 50, 100) genes selected by each method on five datasets. As observed from Table 2, for the SVM classifier, the MTMU algorithm is superior to other algorithms if top-5, top-10, top-20, and top-50 genes are selected respectively, and only slightly worse than RF if top-100 genes are selected. The hat MTMU algorithm achieves optimal average classification accuracy if top-50 genes are selected, which is higher than any average classification accuracy of other algorithms. Table 2 also shows that MTMI obtains the worst result because the Intersection cannot be formed when the number of genes selected by a single tree model is less than 100, thus reducing the average classification accuracy. In addition, similar comparison results can be obtained for naïve Bayes classifiers.
According to Fig. 4 and Table 2, the MTMU gene selection method was more effective than the singletree model-based gene selection method.
4.4 Comparison with State-of-the-Art Methods
In this section, four of the most advanced gene selection methods published recently, namely BGWOPSO [20], FCSVM-RFE [21], KDI [22], and MultiSURF [23], were selected for experimental comparison. For a fair comparison, the size of the gene subsets selected by all compared algorithms was set to 50.
Tables 3 and 4 compares the classification accuracy between the proposed ensemble tree model gene selection methods and the four latest proposed methods using SVM and naïve Bayes classifiers, respectively.
Because no intersection of genes selected by DT, RF, and GBDT in the HD dataset when the top 50 genes were selected, the MTMI algorithm obtained no genes. As observed from Tables 3 and 4, the MTMU integrated tree model method achieved better results overall. The proportions of optimal values obtained by the MTMU on the SVM and naïve Bayes classifiers were 5/5 and 4/5, respectively.
The last columns in Tables 3 and 4 show each algorithm’s mean classification accuracy for the five datasets. In the case of SVM, MTMU obtained a first mean classification accuracy of 0.9921 and MTMCU obtained a second classification accuracy of 0.9773. Similarly, using the naïve Bayes classifier, MTMU obtained the first mean classification accuracy of 0.9883, and MTMCU obtained the second mean classification accuracy of 0.9658.
From the above results, the integrated tree model gene selection method (MTMU) proposed in this study has an advantage in terms of classification accuracy compared to other methods. We believe that this is because the MTMU algorithm integrates multiple genes selected from different single-tree models, thus avoiding the bias of a single model and enhancing the robustness of gene selection.
Accuracy comparison based on selecting the top-n genes.
Results of all compared methods based on the SVM classifier
Results of all compared methods based on naïve Bayes classifier
5. Conclusion
Gene selection based on tree models is both simple and efficient. This study analyzes the shortcomings of gene selection based on a single tree model and proposes ensemble gene selection methods based on multiple tree models, which solves the bias of the gene selection algorithm based on a single tree model and improves the robustness and stability of the gene selection algorithm. Specifically, we used three single tree models, ID3, random forest, and GBDT, to select the top-n genes. Subsequently, we conducted intersection, union, and cross-union operations to obtain three gene subsets. The ensemble gene selection algorithms corresponding to the three operations were named MTMI, MTMU, and MTMCU. Experimental results on five publicly available microarray gene expression datasets demonstrate that MTMU is significantly superior to other methods in classification accuracy. Further studies may involve the application of other tree models and more complex fusion mechanisms to improve the performance of the gene selection algorithm based on the integrated-tree model.