Why are Decision Trees not computationally expensive?

Question

In An Introduction to Statistical Learning with Applications in R, the authors write that fitting a decision tree is very fast, but this doesn't make sense to me. The algorithm has to go through every feature and partition it in every way possible in order to find the optimal split. For numeric features with $n$ observations, this could result in $n$ partitions for each feature.

Am I misunderstanding how the binary splitting works? Or is there a reason that this algorithm would not take long?

Answer 1

Decision trees algorithms do not compute all possible trees when they fit a tree. If they did they would be solving an NP-hard problem. Decision tree fitting algorithms typically make greedy decisions in the fitting process—at each stage they optimize the sub-problem for finding an optimal split with the data in the given node and the keep moving forward in the fitting process. Also, as you move deeper into the decision tree you have a smaller set of data that has made it to the given node so that you will be optimizing the splitting rule over a smaller subset of data. All of these choices are linear scans of the data in the given node. This is not complicated to do but can become somewhat expensive computationally if you have a large number of observations or a large number of covariates to split on. However, a lot of the work can be split up and sent off to different machines to work on so there are ways to build out your computational architecture to scale up. In general though, the method works fairly quickly on lots of the datasets you see in coursework and in many real world scenarios as well.

Answer 2

There are some differences between the CART and C4.5 algorithms for building decision trees. For instance, CART uses Gini Impurity to pick features while C.4.5 uses Shannon Entropy. I don't think the differences are relevant for the answer, so I will not differentiate between those.

What makes decision trees faster than you would think is:

1. As others have said, these algorithms are 1-lookahead algorithms. They perform local optimizations. At every branch, they choose the rule which maximizes/minimizes whatever metric they use (Gini or Entropy). This means they might miss rules where using a logical operator such as and would result in a better tree. This means you should be very careful/clever when doing feature engineering. For example, say you are trying to predict how much people drink, you might want to feature engineer things like new_feature = hour > 22 & hour < 4 & (friday_night | saturday_night). Decision trees might miss such rules, or give them less importance than they should.
2. More importantly, the metrics used by decision trees can be computed incrementally. Say that you have a feature $X_1 = \{3,1.5,2.5,2,1\}$. The decision tree does not need to compute the metric for X <= 1, then compute the metric again for X <= 1.5, then again for X <= 2, etc. Gini and Entropy were chosen because they can be computed incrementally. First of all, each feature is sorted, so that you have $X_1 = \{1,1.5,2,2.5,3\}$. Secondly, when you compute X <= 1, you can use the result to easily compute X <= 1.5. It's like doing an average. If you have an average of a sample, $\bar x$, and I give you another value $v$, you can cheaply update your average doing, $\bar x \leftarrow \frac{n\bar x+v}{n+1}$. Gini coefficient is calculated as a fraction of sums, which can be easily incrementally computed for the sample.
3. Decision trees can be parallelized. Each node is composed of two branches which are independent. Therefore, at each branch, you have the opportunity to parallelize the tree creation. Furthermore, the feature selection itself can also be parallelized. This is what makes packages like xgboost so fast. Gradient boosting is sequential and cannot be parallelized, but the trees themselves can.

Answer 3

Just to enrich the answers,

Hierarchic axis-parallel decision-trees are fast (CART, C4.5) but there are other alternatives such as non-hierarchic decision trees or those that perform oblique partitions that are not, although they can be more accurate. Check the following references if you are interested (They are not an exahustive selection).

Non-hierarchic:

Grubinger, T., Zeileis, A. and Pfeiffer, K.-., 2014. Evtree: Evolutionary learning of globally optimal classification and regression trees in R. J.Stat.Software 61 (1), 1-29.

Oblique splits:

Murthy, S.K., Kasif, S. and Salzberg, S., 1994. A system for induction of oblique decision trees. J. Artif. Intell. Res. 2 (1), 1-32. http://dx.doi.org/doi:10.1613/jair.63. Cantú-Paz, E. and Kamath, C., 2003. Inducing oblique decision trees with evolutionary algorithms. IEEE Trans. Evol. Comput. 7 (1), 54-68. http://dx.doi.org/10.1109/TEVC.2002.806857. Heath, D., Kasif, S. and Salzberg, S., 1993. Induction of oblique decision trees. J. Artif. Intell. Res. 2 (2), 1002-1007.

Good luck!