Variable importance for C5.0 boosted trees

Question

I use function C5imp() to analyze the variable importance of a C5.0 model built with package {C5.0}, which is a wrapper around the original C-code by Quinlan. The (unscaled) importance scores for one tree report the "percentage of training set samples that fall into all the terminal nodes after the split". While different from mean decrease in the split criterion typically used for gradient boosted trees (see nice discussion here), this seems to be the same as the "cover" importance metric reported by the xgboost package.

However, for the boosted model (i.e. trials>1), the output suggests that the importance reports the maximum percentage for any tree, rather than an average over all trees. This results in a lot of variables having an importance score of 100 when the number of trials grows, since many variables end up at the top of a tree at some point.

library(C50)
# Experiment with n = 1 and n = 5
n <- 5
C5boosted <- C5.0(x = iris[, 1:4], y = iris$Species, trials = n) 
# Plot importance
# Variable importance for sepal.width is 25...
C5imp(C5boosted, pct = FALSE)
# Plot each of the trees
# ... but sepal.width is only used in one tree
for(i in 0:(n-1)){
  plot(C5boosted, trial = i)
}

n <- 20
C5boosted <- C5.0(x = iris[, 1:4], y = iris$Species, trials = n) 
C5imp(C5boosted, pct = FALSE)
#             Overall
#Sepal.Width   100.00
#Petal.Length  100.00
#Petal.Width   100.00
#Sepal.Length   82.67

Even at 20 trials, the importance for most variables is close to 100, so there is no clear indication that sepal.width is in fact much more important in the trees.

Is there a reason why C5.0 would not average over boosted trees but rather take the maximum coverage to calculate the coverage importance score?

Answer 1

Hastie (2013) (citing Breiman (1984)) discuss relative importance measures for decision trees and additive tree expansions in Chapter 10.13.1 (p.368). A quick summary is given in Louppe et al. (2013) with a generalization for any splitting criterion:

[Breiman] proposed to evaluate the importance of a variable $X_m$ for predicting $Y$ by adding up the weighted impurity decreases $p(t)\Delta i(split_t, t)$ for all nodes $t$ where $X_m$ is used, averaged over all $N_T$ trees in the forest:

$Importance(X_m) = \frac{1}{N_T} \sum_T \sum_{t\in T: variable(split_t)=X_m} p(t) \Delta i(split_t, t)$

where [$i$ is the splitting criterion, $t$ are the nodes of tree $T$], $p(t)$ is the proportion $N_t/N$ of samples reaching [node] t and [$variable(split_t)$] is the variable used in $split_t$. (My changes in notation in brackets)

In the case of the C4.5 and C5 tree, the splitting criterion $i$ is entropy. So I think that we should calculate the variable importance for a single tree by calculating the difference in entropy $\Delta i$, weight it by the ratio of observation in the node and sum it this up over all splits on a variable. We then average these importance scores over all trees.

I've added a (slow) prototype to my Github repository that

1. walks through the trees to extract
   • the decrease in entropy weighted by number of observations of each split summed for each variable
   • number of times the tree splits on the variable relative to number of splits in the tree
2. averages the two metrics over all trees for each variable

For the example above, the unstandardized output is

       variable_id meanDecreaseEntropy meanSplits     variable
1:           3          1.30278545     0.5298810    Petal.Length
2:           4          0.63319241     0.3330688    Petal.Width
3:           1          0.07160452     0.1753968    Sepal.Length
4:           2          0.08423547     0.1828571    Sepal.Width

where meanDecreaseEntropy corresponds to Gain (xgboost) or meanDecreaseGini (caret: randomForest). meanSplits corresponds to Frequency (xgboost), i.e. the relative number of splits in the tree in which the variable is used.

We see that Petal.Length, which is the top split in most single trees, has a relatively high importance, while Sepal.Length and Sepal.Width, which do not occur in most trees, have very low scores. This is much more in line with eyeballing the tree structures.

References:

Hastie et al. (2013). The Elements of Statistical Learning.

Louppe, G., Wehenkel, L., Sutera, A., & Geurts, P. (2013). Understanding variable importances in forests of randomized trees. In Advances in neural information processing systems (pp. 431-439).