Random forests are said to reduce variance in relation to bagging trees, because of its random selection of features - it reduces correlation between trees. My question is - how we define correlation between decision trees?

  • 1
    $\begingroup$ I don't think there is a specific correlation metric, they just mean the trees will look different. For example, if we use the entire learning sample and consider all features, each tree will be identical (perfectly correlated). By bootstrapping the learning sample, the trees will be slightly different. By adding the random selecton of features, the trees will look even more different. We could even go further by randomly selecting cutpoints for each variable selected (see Extremely Randomized Trees). The goal is to obtain uncorrelated trees while forming good splits. $\endgroup$ – Peter Calhoun Dec 7 '16 at 22:25

This is an important measure for decision trees in a random forest and is a component of the generalization error of the random forest.

Please read Breiman's original paper(page 6) where he defines correlation as $\bar{\rho}=\mathbf{E}_{\Theta, \Theta^\prime}[\rho(h(\cdot,\Theta), h(\cdot,\Theta^\prime)]$. So that $\bar{\rho}$ is the correlation between two different members of the forest averaged over the $\Theta, \Theta^\prime$ distribution.

A second paper a bit more readable, describes correlation between trees to be the correlation between their raw margin function. The margin function is the extent to which average number of votes for class exceeds the average number of votes for the next-best class. See Slides.

Finally, another way of evaluating the correlation would be consider correlation between the prediction errors between decision tree pairs, though this would not be the same term in the generalization error PE$^\ast$ in Breiman's paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.