Decision tree learning

What it is

Decision tree learning is a supervised learning method that uses a classification tree or a regression tree as its predictive model ^[1]. scikit-learn describes it as a non-parametric supervised learning method used for classification and regression ^[2]. The model predicts the value of a target variable by learning simple decision rules inferred from the features of the data, and a tree can be seen as a piecewise constant approximation ^[2].

Concretely, each internal node asks a question about one feature, each branch is an answer, and each leaf returns a prediction. The path from root to leaf is a chain of if-then rules, so the reasoning behind a single prediction can be read off the tree directly.

How the tree is grown

Trees are grown by top-down greedy recursive partitioning, choosing at each step the split that best separates the data ^[1]. The procedure is greedy because each split is judged only for the node at hand, without revisiting earlier choices, and recursive because after a split the same procedure is applied again inside each resulting subset.

What counts as "best" depends on the algorithm family. CART uses the Gini impurity, defined as 1 minus the sum of squared class probabilities; it is zero when a node is pure, meaning every training example reaching it belongs to the same class ^[1]. ID3, C4.5 and C5.0 instead use information gain, which is based on entropy ^[1]. For regression trees, where the target is a number rather than a label, variance reduction can serve as the splitting criterion ^[1].

A small example makes the mechanics concrete. Suppose the goal is to predict whether a loan applicant will repay, using two features: income and existing debt. At the root every applicant sits together. A split on income separates them somewhat; a split on debt might separate them more cleanly. The algorithm scores each candidate split by its impurity and keeps the one that reduces impurity the most. It then repeats inside each branch: the high-income group may be split again on debt, while the low-income group already falls mostly in one class, so it stops and becomes a leaf. Everyone who lands in the same leaf receives the same prediction, which is what makes the model piecewise constant.

Depth shapes the result. In scikit-learn the deeper the tree, the more complex the decision rules and the fitter the model ^[2]. A deep tree can capture finer distinctions but also follows noise in the training data, which is why pruning is used to avoid overfitting, although some algorithms such as conditional inference trees do not need it ^[1].

Where it came from

Several lines of work converged. CHAID, chi-squared automatic interaction detection, was introduced by Kass in 1980 and allows more than two splits at a node, so one node can branch into several groups rather than just two ^[1]. CART, classification and regression trees, was published by Breiman and colleagues in 1984 ^[1]. Quinlan introduced ID3 in 1986 and later C4.5 as its successor, with C5.0 following ^[1]. ID3 and CART were invented independently around the late 1970s and early 1980s ^[1].

Using trees in practice

Decision trees serve both classification and regression tasks ^[2]. Because the fitted model is a set of readable decision rules, a tree is useful when the grounds for a prediction matter as much as the prediction itself. Depth is the main dial: a shallow tree gives simple, easily explained rules, a deep one gives complex rules and a tighter fit ^[2].

Limitations

Limitations include instability under small changes to the training data, a tendency to overfit, and the fact that finding the optimal tree is NP-complete ^[1]. The last point means practical algorithms settle for greedy step-by-step splits instead of a guaranteed global optimum. Information gain is also biased towards attributes with many levels ^[1], since more levels give more opportunities to separate the training data.