variable importance in R randomForest package

I have a few questions regarding the variable importance in random forest. The importance function outputs two types of importance measures (1 = mean decrease in accuracy, 2 = mean decrease in node impurity). For the 2nd measure, the manual says:

The second measure is the total decrease in node impurities from splitting on the variable, averaged over all trees.

1. Does “over all trees” actually mean “over all trees where that predictor is used as a splitter”?

2. At each split, what’s the criteria to choose which predictor to use as a splitter? Could a predictor be used more than once as splitters in the same tree?

3. Is it guaranteed that each predictor got at least one chance to be used as splitter in the building of the forest? If not, what would be that predictor’s importance value?

1. Does “over all trees” actually mean “over all trees where that predictor is used as a splitter”?

My understanding is that the sum is over all nodes where the predictor variable is used. In fact, a predictor variable can be used more than once in a given tree to split a node or not at all.

1. At each split, what’s the criteria to choose which predictor to use as a splitter? Could a predictor be used more than once as splitters in the same tree?

My understanding is that at each node, a random subset of predictors is selected. From these predictors, the one that most reduces the impurity is then selected. Impurity'' can be quantified by different measures. Two that I have come across are the Gini impurity and the entropy measure.

1. Is it guaranteed that each predictor got at least one chance to be used as splitter in the building of the forest? If not, what would be that predictor’s importance value?

I believe that there is a chance that a predictor is never used (although very small chance if you build a lot of trees). It that case, the importance of type 2 is zero.

• Thanks for the explanation, very helpful! Just one more question regarding the 2nd point, how to break a tie, i.e. two predictors have equal impurity reduction? – blueskyddd Dec 15 '15 at 5:49
• randomForeset(R) break ties at random. I guess other algorithms would do that to. (rpart, R) break ties by the arbitrary ordering of columns in training set. stats.stackexchange.com/questions/166560/… – Soren Havelund Welling Dec 15 '15 at 9:32
• I heard that if two predictors tie for first place at a node, that is, they reduce the impurity by the same amount, which is by the way a highly unlikely event in real world applications, then one of the two is randomly selected by a "coin flip". – Babak A. Ardekani Dec 16 '15 at 14:35
1. Does “over all trees” actually mean “over all trees where that predictor is used as a splitter”?

Yes, for a single tree the decrease of impurity is computed only when that particular variable is used. From [Deng2011]: 1. At each split, what’s the criteria to choose which predictor to use as a splitter? Could a predictor be used more than once as splitters in the same tree?

A each internal node of a tree, the gain on Gini impurity (or Gini impurity decrease) is used to select the best variable to induce a split on. Have a look here. Only one variable is chosen at an internal node. A variable can induce a split in multiple internal nodes in a tree.

1. Is it guaranteed that each predictor got at least one chance to be used as splitter in the building of the forest? If not, what would be that predictor’s importance value?

If a predictor is useless this might not be used in any tree. I guess that its importance is 0 given that it is never used. Indeed, its Gini gain is 0.

• Thank you so much for the explanation and the links! Just one more question regarding the 2nd point, how to break a tie, i.e. two or more predictors have equal impurity reduction? – blueskyddd Dec 15 '15 at 5:50
• I have never seen any implementation that breaks ties for two variables that have equal impurity reduction. I guess ties can be broken at random. In practice, variable are sorted according impurity reduction in descending order. I guess whichever variable gets at the top of that this ranking is selected to split the internal node. – Simone Dec 15 '15 at 5:58
• Thanks for the quick response! If the tie-breaking is random, does it mean the unchosen one may end up with zero importance value although it's equally important? – blueskyddd Dec 15 '15 at 6:26
• Also, how is the splitting done? for example, does it cluster the observations based on that predictor using KNN? Does random forest only classify two classes? – blueskyddd Dec 15 '15 at 6:30
• If two variables are really equally important, even if the tie break is at random one variable might be selected in one tree and the other in other trees. In random forests every tree is built on a random subset of variables – Simone Dec 15 '15 at 6:30