Ensemble methods of rank-based trees for single sample classification with gene expression profiles

In this section, we introduce a general framework for rank-based trees using pairwise gene comparisons among a number of gene expressions. Let \({{\textbf {X}}}=(X_1,X_2,\dots ,X_P)\) denote the expression values of P genes on an expression matrix, which could be generated from different platforms (see Fig. 1 subfigures A and B for conceptual illustration). Our objective is to use \({{\textbf {X}}}\) to distinguish among K phenotypes for the cells in the tissue, denoted as \(Y\in \{1,\dots ,K\}\). (Since the boosting algorithm only accommodates binary outcomes, we denote \(Y\in \{-1,1\}\) for the boosting case.) A tree classifier is inferred from training data \(\mathcal {L}=\{({{\textbf {X}}}^{(1)},Y^{(1)}),\dots ,({{\textbf {X}}}^{(N)},Y^{(N)})\}\), where \(({{\textbf {X}}}_i,Y_i)\) are independently distributed. For a given expression vector \({{\textbf {x}}}\), a classifier h associates it with a label \(h({{\textbf {X}}})\in \{-1,1\}\). We denote the tree predictor of \(h({{\textbf {x}}})\) as \(h({{\textbf {x}}},\Theta ,\mathcal {L})\), where a parameter vector \(\Theta =(\theta _1,\theta _2,\dots ,\theta _T)\) associates the parameter \(\theta _t\) with the t-th terminal nodes and T denotes the total number of terminal nodes.

To grow a rank-based classification tree, the splitting rule can be described as follows. If \({{\textbf {p}}}=(p_1,\dots ,p_K)\) are the class proportions of outcome Y for classes 1 through K, the Gini index of impurity is defined asAs shown in Fig. 1C, by splitting features recursively into left and right daughter nodes, a tree is grown by minimizing tree impurity. The Gini index split statistic for a split on node s on a pair of features \(X_i\) and \(X_j\) at a given tree node iswhere the subscripts \(l=\{X_j\le X_k\}\) and \(r=\{X_j> X_k\}\) denote the left and right daughter nodes formed by the split at s and \(n_l\) and \(n_r\) are the sample sizes of the two daughter nodes; \(n=n_l+n_r\) is the parent sample size. With some algebra, this is equivalent to maximizing the split statisticwhere \(n_{k,l}\) is the number of cases of class k in the left daughter node and \(n_k\) is the number of cases of class k; \(n=\sum _{k=1}^{K}n_k\) is the total sample size. At tree node s, we randomly select a set of candidate features \({{\textbf {X}}}^{(s)}=\{X_{1'},\dots ,X_{Q'}\}\), \(Q'\le P\), and the pair of variables with indices \((i_s,j_s)\) will be split ifWe partition the expression values into a set of gene pairs for constructing splits in the tree nodes and trees are built in a binary fashion: each internal node has an associated splitting rule that uses two predictors, \(X_i\) and \(X_j\), to assign a observation k to either its left or right child nodes, \(\{X^{(k)}_i\le X^{(k)}_j\}\) or \(\{X^{(k)}_i> X^{(k)}_j\}\). The terminal nodes thus identify a partition of the observation space according to the subdivision defined by a series of splitting rules. For each terminal node t, we can arrange the variable indices in pairs \(\{(i_1,j_1),\dots ,(i_t,j_t)\}\), \(t=1,\dots ,T-1\), such that \(\theta _t=\{{{\textbf {x}}}: x_{i_1}<x_{j_1}, \dots , x_{i_t}<x_{j_t}\}\). For a binary outcome \(Y\in \{-1,1\}\), we calculate the estimated probability for a given \({{\textbf {x}}}\) as the proportion of class label 1 at the corresponding terminal node \(\theta _t\), \(p({{\textbf {x}}}) = \mathbb {P}(Y=1|{{\textbf {x}}}\in \theta _t)\) and estimate \(\mathbb {E}[Y|{{\textbf {x}}}]\) as \(f({{\textbf {x}}})=2p({{\textbf {x}}})-1\). The estimator for a multi-class outcome of K labels can be calculated as the proportion of the corresponding class label, \(p_k({{\textbf {x}}}) = \mathbb {P}(Y=k|{{\textbf {x}}}\in \theta _t)\) and the tree takes a Bayes classifier \(h({{\textbf {x}}})=\mathop {\mathrm {arg\,max}}\limits _{k\in \{1,\dots ,K\}}\mathbb {P}(Y=k|{{\textbf {x}}}\in \theta _s)\).

The rank-based trees could be of low accuracy with high variance. To prevent overfitting, we first ensemble these trees in a fashion of random forest [28, 29]. As in [28], we define a collection of randomized tree predictors \(\{h(\cdot ,\Theta _m,\mathcal {L}), m =1,\dots ,M\}\). We denote the mth tree predictor of \(h({{\textbf {x}}})\) as \(h({{\textbf {x}}},\Theta _m,\mathcal {L})\), \(m=1,\dots ,M\), where \(\{\Theta _m\}\) are independent identically distributed random quantities encoding the randomization needed for constructing a tree, which are selected prior to grow the tree. These pre-selected parameters are refered to as tuning parameters and discussed in the Discussion section. The tree predictors are combined to form the finite forest estimator of \(h({{\textbf {x}}})\) asand \(h({{\textbf {x}}})=\mathop {\mathrm {arg\,max}}\limits _{k\in \{1,\dots ,K\}}\hat{p}_k({{\textbf {x}}})\).

Although random forest offers the advantage of achieving high levels of accuracy, the decision rules become extremely complex after averaging the rank based trees, which motivates us to extract information from the blackbox to increase interpretability. Since each terminal node of a tree can be viewed as a classification rule from multiple TSPs, we propose the Algorithm 1 to identify some importance classification rules. Note that each tree in a random forest algorithm is fitted from a bootstrap sample of the original data, leaving approximately 1− 0.632 = 0.368 out-of-sample data for each tree which is called out-of-bag (OOB). This data can be utilized to estimate the prediction performance and obtain an OOB prediction error without the need for an additional cross-validation step to evaluate the prediction error. Here we calculate the OOB prediction error for each terminal node for selecting rules in Algorithm 1.

As another ensemble technique, boosting [30, 31] has been used as a powerful tool for classification, especially in high-dimensional settings. As weak learners, random rank trees are ensembled according to a LogitBoost cost function [32] \(C(y_i,F({{\textbf {x}}}_i))=\log (1+\exp (-2y_iF({{\textbf {x}}}_i)))\) with \(y_i\in \{-1,1\}\), where \(F({{\textbf {x}}}_i)=\frac{1}{2}\log (\frac{p({{\textbf {x}}}_i)}{1-p({{\textbf {x}}}_i)})\) and \(p({{\textbf {x}}}_i)=\mathbb {P}(y_i|{{\textbf {x}}}_i)\). In each iteration m, a regression tree is fit using the negative gradient of \(C(y_i,F({{\textbf {x}}}_i))\) as working responsesFor a tree with S terminal nodes, the update uses a refined optimization with unique estimates for each terminal node:whereNote that unlike Eq. (1) for a classification tree, the splitting rule for partition \(\theta _{s,m}\) is similar to a regression tree [33], which maximizeswhere the subscripts \(l=\{X_j\le X_k\}\) and \(r=\{X_j> X_k\}\) denote the left and right daughter nodes for s; \(\bar{z}_l\) and \(\bar{z}_r\) denote the average of \(z_m({{\textbf {x}}}_i)\) in the corresponding daughter nodes. After M iterations from Eq. (4), the final predictor \(F_M({{\textbf {x}}}_i)\) is converted into a probability estimateFor an outcome with K class labels, we encode the data into K “one against all” datasets with the outcomes \(\{Y=k\}\) and \(\{Y\ne k\}\) to compute \(\hat{p}_k({{\textbf {x}}})\).

The challenge of rank-based tree method is high dimensionality. When we have p genes, there are \(O(p^2)\) calculations involved in Eq. (2) for constructing tree nodes. As a solution, we propose a two-step ensemble algorithm, in which the first ensemble step is to reduce dimensionality and the second ensemble step is to predict the outcome.

For variable selection, we have to construct a variable importance (VIMP) measurement based on a loss function. For classification problems, measures of performance used are the misclassification error or the Brier score [34‐36]. For the latter, we have \(L(Y,\hat{p})=(1/K)\sum _{k=1}^K\left( \mathbb {1}_{\{Y=k\}}-\hat{p}_k\right) ^2\). To measure VIMP, we grow each tree using a bootstrap sample of the original data and the previously mentioned OOB data is used to calculate the loss function under the original OOB data and the permuted OOB data. Let \(\mathcal {L}^{\text {OOB}}\) be the OOB data and let \(\hat{p}_k(\tilde{{{\textbf {x}}}}^{(ij)})\) be the estimator for permuted \({{\textbf {x}}}\) where the relationship of \(X_i\) and \(X_j\) is swapped in all the rank-based trees, which can be achieved by permuting the ith and jth columns in \(\mathcal {L}^{\text {OOB}}\). The VIMP for gene pairs \(X_i\) and \(X_j\) is defined asUtilizing VIMP, the two-step ensemble algorithm is described in Algorithm 2.

Beside the k-TSP method, we also compared our methods with the nearest template prediction (NTP) method, which compares the gene expression profile of a single sample to a pre-defined set of gene expression profiles, known as templates. The subclass label can be determined using a distance metric (e.g. cosine distance, Euclidean distance, etc.) as the similarity to each template [14]. In our comparison, k-TSP was implemented from the “switchbox” R package [52], in which the optimal number of gene pairs was selected from a range of values from 2 to 10 with fivefold cross-validation. For multi-class classification, a one-vs-one scheme was used and a classifier was trained for each pair of subclasses [53]. To avoid ties in majority voting, only odd numbers were considered during training. We implemented the NTP method with the “CMScaller” package [54], which was originally created for classifying colorectal cancer pre-clinical models [4, 55]. The prediction for each sample was determined using the sample’s closest cosine distance to each template. We utilized the “gbm” R package [56] for implementing our boosting algorithm and the “randomForestSRC” R package for our random forest algorithm [57]. For the random forest implementation, we adopted the multi-class tree with class-balanced sampling instead of fitting separate one-versus-rest models for each class [27] to improve computational efficiency and prediction performance. We noticed that there are other classical methods available, such as k-nearest neighbor (KNN) and support vector machines (SVM). We did not present the results in Section 4 because the comparison was already presented in Tan et al. [21] and showed that k-TSP works superior or comparable to KNN and SVM (see Tables 3 and 4 in Tan et al. [21], and we have the same conclusion with them). We also tried random forest/boosted trees using single gene features, the results of which are similar to SVM, and we did not include the results due to limited space.

Given a dataset with sample size N and an outcome of K classes, let \(c_{ij}\) be the number of samples belonging to class i that are predicted to the jth class and the sample size for class i is denoted as \(n_i=\sum _{j=1}^{K}c_{ij}\) (see Fig. 2). The performance measure is defined as accuracy (ACC):Note that ACC is highly influenced by the imbalanced sample sizes among different classes. Therefore, we subsample or bootstrap the data such that \(n_i/N\approx 1/K\). All datasets were randomly divided into class-balanced training (70%), validation (15%), and test data (15%). To evaluate the robustness and assess the performance of the methods, we fitted the four models on the training data, used the validation data for tuning parameters, and compared the ACC values on the corresponding test data. We replicated this procedure 50 times to compare the ACC values.

The learning rate in boosting algorithms shown in Eq. (4) determines the contribution of each weak learner (e.g., rank-based tree) to the final ensemble model. It controls the amount by which the weights of misclassified samples are adjusted in each iteration of boosting. The learning rate influences boosting via the speed of convergence, model complexity, model accuracy and robustness to noise and outliers. Figure 4 demonstrates the effect of the learning rate on the classification of the Liver dataset. Overall, the model is robust to learning rates in a wide range. It’s important to note that the optimal learning rate for boosting depends on the specific dataset and problem at hand. We used cross-validation to determine the learning rate that achieves the best balance between convergence speed, accuracy, and robustness for a given dataset.

The number of trees is an important parameter in both boosting algorithms and random forests. Increasing the number of trees tends to improve the model’s performance since as more trees are added, the boosting model can better capture complex patterns and reduce both bias and variance errors; with more trees, the random forest ensemble becomes more robust and stable as it aggregates predictions from a larger number of diverse decision trees. Figure 5 demonstrates the influence of iteration/tree number on model performance for the Liver dataset, where a number of 250 seems sufficient for both random forest and boosting. For all the datasets, adding too many trees is unlikely to increase the risk of overfitting; however, increasing the number of trees also increases the computational cost of training and inference. Therefore, there is a trade-off between model performance and computational resources. From our empirical experimentation, an iteration number of 500 is sufficient for most datasets in both random forests and boosting and increasing the number larger than 1000 is unlikely to make any difference.

The depth of trees, also known as the tree’s maximum depth or tree size, plays a crucial role in growing rank-based trees. It has a similar influence as terminal node size since the deeper the tree is, the smaller the terminal node size is. In boosting algorithms, shallow trees (limited depth) are commonly used to prevent overfitting and improve the model’s generalization ability. By limiting the complexity of individual trees, boosting focuses on learning simple rules or patterns, which can be combined to form a powerful ensemble. On the other hand, random forests typically use deep trees to achieve higher accuracy and capture more complex relationships in the data. Deeper trees can capture intricate patterns and interactions among features, which can improve the model’s predictive power. Random forests overcome overfitting caused by deep trees via averaging across a large number of trees. As shown in Figs. 6 and 7 for the Liver dataset, it is crucial to strike a balance between the tree depth and the model’s generalization ability in both boosting and random forests. The optimal tree depth depends on the dataset characteristics, and we used cross-validation to determine the appropriate tree depth without a specific constraint on the terminal node size.

Note that the tree depth of 1 in the first column of Fig. 6 for random forest is roughly equivalent to the k-TSP method since a tree of one split is equivalent to a top scoring pair. Figure 6 demonstrates that extending the k-TSP method via growing deeper trees and ensemble methods can achieve higher accuracy in prediction.

The number of competing gene pairs at each split, also known as feature subspace size, is defined in Eq. (2) denoted as q. A larger q will increase the computational cost. However, it does not hold much significance in boosting algorithms nor random forests. Boosting algorithms typically do not involve explicit feature subsampling at each split. Instead, they focus on sequentially adjusting the weights of training examples to improve the model’s performance. Therefore, the number of competing variables at each split does not directly impact boosting. In random forests, the number of competing variables at each split determines the randomness and diversity among decision trees in the ensemble. A smaller number of competing features at each split helps to decorrelate the trees in the random forest ensemble and prevents a few dominant features from overshadowing others. It promotes diversity among the trees, leading to a more robust and accurate ensemble. However, as shown in Fig. 8, random forest is also robust to the number of competing variables since the total number of variables is large in genetic datasets. In other words, when \(q<<p\), the influence of q is small.