How to measure/rank "variable importance" when using CART? (specifically using {rpart} from R)

Question

When building a CART model (specifically classification tree) using rpart (in R), it is often interesting to know what is the importance of the various variables introduced to the model.

Thus, my question is: What common measures exists for ranking/measuring variable importance of participating variables in a CART model? And how can this be computed using R (for example, when using the rpart package)

For example, here is some dummy code, created so you might show your solutions on it. This example is structured so that it is clear that variable x1 and x2 are "important" while (in some sense) x1 is more important then x2 (since x1 should apply to more cases, thus make more influence on the structure of the data, then x2).

set.seed(31431)
n <- 400
x1 <- rnorm(n)
x2 <- rnorm(n)
x3 <- rnorm(n)
x4 <- rnorm(n)
x5 <- rnorm(n)

X <- data.frame(x1,x2,x3,x4,x5)

y <- sample(letters[1:4], n, T)
y <- ifelse(X[,2] < -1 , "b", y)
y <- ifelse(X[,1] < 0 , "a", y)

require(rpart)
fit <- rpart(y~., X)
plot(fit); text(fit)

info.gain.rpart(fit) # your function - telling us on each variable how important it is

(references are always welcomed)

Answer 1

Variable importance might generally be computed based on the corresponding reduction of predictive accuracy when the predictor of interest is removed (with a permutation technique, like in Random Forest) or some measure of decrease of node impurity, but see (1) for an overview of available methods. An obvious alternative to CART is RF of course (randomForest, but see also party). With RF, the Gini importance index is defined as the averaged Gini decrease in node impurities over all trees in the forest (it follows from the fact that the Gini impurity index for a given parent node is larger than the value of that measure for its two daughter nodes, see e.g. (2)).

I know that Carolin Strobl and coll. have contributed a lot of simulation and experimental studies on (conditional) variable importance in RFs and CARTs (e.g., (3-4), but there are many other ones, or her thesis, Statistical Issues in Machine Learning – Towards Reliable Split Selection and Variable Importance Measures).

To my knowledge, the caret package (5) only considers a loss function for the regression case (i.e., mean squared error). Maybe it will be added in the near future (anyway, an example with a classification case by k-NN is available in the on-line help for dotPlot).

However, Noel M O'Boyle seems to have some R code for Variable importance in CART.

References

1. Sandri and Zuccolotto. A bias correction algorithm for the Gini variable importance measure in classification trees. 2008
2. Izenman. Modern Multivariate Statistical Techniques. Springer 2008
3. Strobl, Hothorn, and Zeilis. Party on!. R Journal 2009 1/2
4. Strobl, Boulesteix, Kneib, Augustin, and Zeilis. Conditional variable importance for random forests. BMC Bioinformatics 2008, 9:307
5. Kuhn. Building Predictive Models in R Using the caret Package. JSS 2008 28(5)

Answer 2

The following function(from Caret package) can be used for evaluating variable importance in rpart trees. I corrected a bug in the Caret function when this only root node in the tree.

varImp <- function(object, surrogates = FALSE, competes = TRUE, ...)
  {
tmp <- rownames(object$splits)

 allVars <- colnames(attributes(object$terms)$factors)
if(is.null(tmp))
  {
  out<-NULL
    zeros <- data.frame(x = rep(0, length(allVars)),
                        Variable = allVars)
    out <- rbind(out, zeros)
  }

else {

rownames(object$splits) <- 1:nrow(object$splits)
splits <- data.frame(object$splits)
    splits$var <- tmp
splits$type <- ""

frame <- as.data.frame(object$frame)
    index <- 0
    for(i in 1:nrow(frame))
      {
        if(frame$var[i] != "<leaf>")
          {
            index <- index + 1
            splits$type[index] <- "primary"
            if(frame$ncompete[i] > 0)
              {
                for(j in 1:frame$ncompete[i])
                  {
                    index <- index + 1
                    splits$type[index] <- "competing"
                  }
              }
            if(frame$nsurrogate[i] > 0)
              {
                for(j in 1:frame$nsurrogate[i])
                  {
                    index <- index + 1
                    splits$type[index] <- "surrogate"
                  }
              }
          }
      }
    splits$var <- factor(as.character(splits$var))
    if(!surrogates) splits <- subset(splits, type != "surrogate")
    if(!competes) splits <- subset(splits, type != "competing")
    out <- aggregate(splits$improve,
                 list(Variable = splits$var),
                 sum,
                 na.rm = TRUE)

allVars <- colnames(attributes(object$terms)$factors)
if(!all(allVars %in% out$Variable))
      {
        missingVars <- allVars[!(allVars %in% out$Variable)]
        zeros <- data.frame(x = rep(0, length(missingVars)),
                            Variable = missingVars)
        out <- rbind(out, zeros)
      }
    }
    out2 <- data.frame(Overall = out$x)
rownames(out2) <- out$Variable
out2

}

The following r code will produce importance scores for a rpart tree "fit"

 varImp(fit)

Answer 3

I think chl has pretty much answered the first part:

What common measures exists for ranking/measuring variable importance of participating variables in a CART model?

With respect to the second part of your question:

And how can this be computed using R (for example, when using the rpart package)

You can find the variable importance using rpart by using summary(fit). This outputs the variable importance among several other things. You can read more about it here: https://cran.r-project.org/web/packages/rpart/rpart.pdf. Refer page 25.

Answer 4

names(result) shows variable.importance

result$variable.importance should help?

Answer 5

The caret package and the rpart package each have ways to list the variables and rank their importance, but generate different results from each other when calculating variable importance.

fit$variable.importance
## shows different results than
caret::varImp(fit)

The list of variables used is the same, but the scale is different, and even the order of importance is different for the dataset I'm using.