7
$\begingroup$

I am using scikit learn to build a Random Forest classifier. I have heard that it might be possible to build a single decision tree from a Random Forest. The suggestion is that although the decision tree may not be as good a classifier as the Random Forest it may be better than the decision tree you would get by using the standard method.

However I haven't been able to find this method online. Does it exist?


My question is not about extracting one of the decision trees from a Random Forest. It is asking about a method to construct a new decision tree from the whole Random Forest, perhaps by combining the trees in the Random Forest somehow.

$\endgroup$
  • $\begingroup$ It makes even less sense. Why would you construct a single tree from a RF, when you already have a RF? Just use the RF. By the way, RF already combines the decision trees (by averaging their predictions). But maybe you're still being unclear, so do you have a reference for what you've heard? That would help you getting answers that are relevant to what you really want. $\endgroup$ – Antoine Sep 14 '15 at 10:23
  • 1
    $\begingroup$ The key term you need is Combined Multiple Models (CMM). Domingos 1997 describes this for bagging C4.5 rules: homes.cs.washington.edu/~pedrod/papers/mlc97.pdf It would be fun to have an example of doing this with Random Forests in sklearn. $\endgroup$ – Abraham D Flaxman Sep 16 '15 at 14:37
  • 1
    $\begingroup$ Antoine, to be clear, most decision tree building algorithms are greedy algorithms that do not find the optimal decision tree. The OP is suggesting that, after training an RF, one could gain insights into assembling a tree that is more powerful than the one you would obtain from the typical greedy algorithms. As he mentions, his motivations are interpretability and speed. $\endgroup$ – jlimahaverford Sep 16 '15 at 21:07
  • 2
    $\begingroup$ My opinion: A random forest fit, can be seen as a large set of rules which can be reduced to a smaller set of simpler rules accepting a given increase in bias as in this article[10]. ncbi.nlm.nih.gov/pmc/articles/PMC4243592 But.. if a minimal set of rules remains to be a large number, this reduction is still incomprehensible. Often if you can reduce the forest to a small tree with little bias, you should be able to use a simpler model in the first place. $\endgroup$ – Soren Havelund Welling Sep 20 '15 at 14:08
  • 1
    $\begingroup$ I disagree that Decision Trees are straightforward to interpret -- at least if they are of a realistic size. Leaves four or five levels down are extremely hard to explain because each decision is conditional on all higher-level decisions. +1 to Soren's comment. $\endgroup$ – Wayne Aug 26 '16 at 20:00
5
$\begingroup$

Perhaps what you are looking for is the Combining Multiple Models (CMM) approach developed by Domingos in the 90s. Details for using this with a bagged ensemble of C4.5 rules is described in his ICML paper

Domingos, Pedro. "Knowledge Acquisition from Examples Via Multiple Models." In Proceedings of the Fourteenth International Conference on Machine Learning. 1997.

The pseudocode in Table 1 is not specific to bagged C4.5, however: enter image description here

To apply this to Random Forests, the key issue seems to be how to generate the randomly generated example $\overrightarrow{x}$. Here is a notebook showing one way to do it with sklearn.

This has got me wondering what follow-up work has been doing on CMM, and if anyone has come up with a better way to generate $\overrightarrow{x}$. I've created a new questions about it here.

$\endgroup$
8
+25
$\begingroup$

Trees in RF and single trees are built using the same algorithm (usually CART). The only minor difference is that a single tree tries all predictors at each split, whereas trees in RF only try a random subset of the predictors at each split (this creates independent trees). Also, each tree in a RF is built on a bootstrap sample of the original training data, rather than on the full training set. This makes each tree in the forest an expert on some domains of the data space, and bad elsewhere.

So, for these reasons, it makes no sense to extract a single tree from a Random Forest in order to use it as a classifier. Depending on its domains of expertise, it could give you better results than a traditional tree built with CART on the full dataset, or much worse. The thing that allows a RF to be much better than a single tree is that it grows many decorrelated trees and averages their output. Only when the committee of experts comprises enough members (usually between 200 and 2000) is variance reduced. But individually, each tree of a RF would be weaker than a single tree built via traditional CART.

You can certainly extract a tree from a RF to get a feel for what's going on in the forest (see the link that I provided in my comment above). Just don't use this single tree as a classifier.

$\endgroup$
  • $\begingroup$ Sorry I think my question wasn't 100% clear. I am not asking about extracting one of the decision trees from the RF. But rather about constructing a single decision tree from the RF by some method . I imagine this would involve combining the decision trees in RF somehow but how this is done is the point of my question. $\endgroup$ – Lembik Sep 14 '15 at 10:09
  • $\begingroup$ The main motivation is interpretability. A decision tree tells you something simple and easily understandable about your data. Also, decision trees that are of reasonable size are extremely fast to run on massive data. $\endgroup$ – Lembik Sep 14 '15 at 10:23
  • $\begingroup$ Once the RF is trained, using it to make predictions is also very fast. And if your decision tree is built through combining the decision trees in RF somehow, that would require building the RF in the first place anyway, right? $\endgroup$ – Antoine Sep 14 '15 at 10:28
  • $\begingroup$ It is true that making predictions with a RF is fast although not quite a fast if you are counting the microseconds. In my situation I would make the RF on some training data and then run it on future data which may be much larger. But as I say, interpretability is a very attractive property of decision trees for my situation. $\endgroup$ – Lembik Sep 14 '15 at 10:41
  • $\begingroup$ You can extract the variable importance from a random forest that shows you how "important" your variables are for making predictions. That is the first step in trying to squeeze some interpretation from a RF. $\endgroup$ – Gumeo Sep 14 '15 at 10:49
4
$\begingroup$

Except for very unlikely scenarios, a random forest prediction cannot be represented by a single tree. This is because they learn predictors in different hypothesis classes: a random forest learns predictors over the space of linear combinations of trees, which includes predictors that are not trees. Put differently- forests learn predictors in the span of the space of trees.

That said, there is the hope that there exists a tree that is a good approximation of the forest predictor. A quick and dirty way of finding this tree, is fitting a tree to the predictions of the forest. The quality of its predictions will depend on the "distance" from the best forest predictor, to its best tree approximation.

$\endgroup$
2
$\begingroup$

It looks like you're looking to address two concerns - 1. interpretability and 2. efficiency of prediction. As already mentioned in the comments above, you can extract variable importance in Python, so that addresses point 1.

To address point 2, if you are concerned with the efficiency down to microseconds, then you may want to explore other algorithms, such as logistic regression, and compare the out-of-sample performance to that generated by Random Forest; if the performance is nearly equivalent but logistic regression is much faster, then you can make the decision to go with logistic regression.

If you are set on using Random Forest, the short answer is that you technically could build one random tree by setting ntree=1 and it might produce a decent prediction, but a collection of trees will be much better than a single tree. So it doesn't make sense to build just one tree from the subset of trees unless you are will to trade off out-of-sample performance for efficiency.

Additionally, you could also speed up the predictions by a factor of 10 or more by only using a subset of the trees in the final prediction. If you train 1500 trees, then you could select the subset that best contributes to the final prediction. I'm thinking of something along the lines of Ensemble Selection from a Model of Libraries, where each tree in your forest would be the model in your ensemble.

$\endgroup$
1
$\begingroup$

One of the classic on combining such functions is "Graph-based algorithms for boolean function manipulation". It has over 3,000 citations. You can treat the trees just as a special case of Boolean functions.

Please note that if your random forest model is large, the single tree model is likely to be large also.

$\endgroup$
0
$\begingroup$

Just as JohnRos says above, you can indeed look for global single tree approximation of Random Forest by trying to fit a single tree to the prediction of the Random forest on a (very) large number of points. It may work for other black box model. It's called the "oracle" approach to global single tree approximation by [1] (because the black box is used as an oracle to fit the single tree). If I dare, I've loaded a couple of exemples and more explanation on Github here : https://github.com/ljmdeb/GSTA

[1] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. 2018. A Survey of Methods for Explaining Black Box Models. ACM Comput. Surv. 51, 5, Article 93 (August 2018), 42 pages. (especialy the table on page 93:26)

$\endgroup$

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.