Decision Trees

Decision trees are widely used models for classification and regression tasks. A decision tree learns a hierarchy of if/else questions, and the answers to those questions lead to a decision. This article starts from that everyday intuition and works toward the code you can use to test it.

Imagine you need to tell apart four animals: bears, hawks, penguins, and dolphins. Your goal is to reach the right answer by asking as few if/else questions as possible. The game is a useful model because every question you ask has one of two answers, and the answer you get determines what you ask next.

Follow the questions for one animal. If the answer to the feathers question is yes, you ask whether the animal can fly, which separates hawks from penguins. If the answer is no, the remaining choices are dolphins and bears, and you ask whether the animal has fins to tell them apart. Each path through the questions ends at a final answer.

Each question in this structure is a node, and the answers are the edges that connect a node to the next question. A node that holds the final answer is called a terminal node, or a leaf. The sequence of questions can be written as a decision tree, which is a model that distinguishes four classes using three features: has feathers, can fly, and has fins.

A decision tree model does not need a person to write these questions by hand. Learning from data means learning the sequence of if/else questions that reaches the true answer most quickly. In machine learning these questions are called tests. Real data is usually made of continuous features rather than yes/no features, so the tests usually take the form 'Is feature i larger than value a?'

To build a tree, the algorithm searches over all possible tests and finds the one that is most informative about the target variable. The source illustrates this with a two-dimensional dataset of two half-moon shapes, called two_moons, containing 75 points per class. For that dataset, the first chosen test is x[1] <= 0.0596, which best separates the points of class 1 from the points of class 2.

The top node, called the root, represents the whole dataset: 75 points of class 0 and 75 points of class 1. After the first split, the left node holds 2 points of class 0 and 32 of class 1, and the right node holds 48 points of class 0 and 18 of class 1. The first split separates the classes well, but each side still contains some points of the other class. The algorithm therefore repeats the search for the best test inside each region. For the two-moons data, the most informative next split for both the left and right regions is based on x[0].

This recursive process yields a binary tree of decisions, with each node containing a test. Each test splits the part of the data under consideration along one axis. Because each test concerns only a single feature, the regions of the resulting partition always have axis-parallel boundaries. The recursion stops when each region, which is each leaf, contains only a single target value. A leaf whose data points all share the same target value is called pure.

To predict for a new point, start at the root and go left or right depending on whether each test is fulfilled, until a leaf is reached. The prediction is the majority target in that region, or the single target when the leaf is pure. For regression, the traversal is the same, but the output is the mean target of the training points in the leaf the point falls into.

If you keep building the tree until all leaves are pure, the model becomes very complex and highly overfit to the training data. Pure leaves mean the tree is 100 percent accurate on the training set, because each training point sits in a leaf whose majority class is correct. The source shows that the decision boundary of such a tree focuses heavily on single outlier points that lie far from the other points of their class. That is not how one would expect a useful boundary to look.

The source gives two common strategies to prevent this. The first is to stop creating the tree early, which is called pre-pruning. The second is to build the full tree and then remove or collapse nodes that contain little information, which is called post-pruning, or just pruning.

The source examines pre-pruning on the Breast Cancer dataset. It first builds a tree with the default setting, which grows the tree until all leaves are pure, and it fixes random_state so that internal tie-breaking is repeatable. The code below is a generated sketch in that same style. It loads the data, splits it, and compares a shallow tree with a deep one. Run it, then read the two printed numbers for each depth.

The source reports that the default tree reaches a training accuracy of 1.000, which is what you should expect for a tree grown deep enough to memorize all the training labels. Its test accuracy is 0.937, slightly worse than the linear models the source examined earlier, which reached around 95 percent. The gap between those two numbers is the signature of overfitting.

When a result differs from what you expected, check the training and test accuracy lines separately. A high training score alongside a lower test score points to overfitting in the tree's structure. The depth limit is the setting that changed between runs, so it is the first place to look.

A random forest is not one tree. It is a collection of decision trees, and the trees are stored in the estimator_ attribute of the fitted model. Each tree is trained on its own bootstrap sample of the training points, and at each split only a random subset of the features is considered. Each tree therefore learns a somewhat different decision boundary. The forest combines them by averaging their predicted probabilities, and that combined prediction is what you get from predict or score.

The parameter n_estimators sets the number of trees in the forest. For random forests, larger is always better, because averaging more trees yields a more robust ensemble and reduces overfitting. The catch is that the returns diminish, and each extra tree costs more memory and training time. The practical rule is to build as many trees as your time and memory budget allow. When you compare settings, the jump from one tree to five should typically be larger than the change from twenty to one hundred.

The parameter max_features controls how random each tree is. At every split, a tree considers only a subset of the features, and max_features sets the size of that subset. A smaller value makes each tree more different from the others, and the source says a smaller max_features reduces overfitting. The defaults are good starting points: the square root of the number of features for classification, and log base 2 of the number of features for regression.

The parameter max_depth still applies pre-pruning inside a forest, limiting how complex each individual tree becomes. The source is explicit, though, that a forest gets its robustness from averaging many trees, not from making each tree tiny. Adding max_features or max_leaf_nodes can sometimes improve performance and can drastically reduce the space and time needed for training and prediction. Often the defaults already work well, so these settings are worth adjusting only after you have a baseline score to compare against.

A forest also reports feature importances, computed by aggregating importances over all its trees. The source considers these more reliable than the importances of a single tree. Because each feature is judged across many trees, a feature ranked highly is useful across many trees, while a feature that appears in only a few trees receives little weight. Read the plot as a summary of many trees rather than a full explanation of each prediction.

Gradient boosted trees are a different ensemble. Instead of building trees independently, they are built one after another, and each new tree tries to correct the mistakes of the previous one. The individual trees are usually shallow, with depth between one and five in the source's description. The main idea is to combine many simple weak learners, and the parameters therefore behave differently from the random forest case.

In gradient boosting, learning_rate controls how strongly each tree corrects its predecessors. A higher learning rate lets each tree make stronger corrections, which allows more complex models. Increasing n_estimators also raises complexity, because the model has more chances to correct training mistakes. The two parameters are linked: a lower learning rate needs more trees to reach a model of similar complexity. This is the opposite of the random forest case, where a higher n_estimators is always better.

For boosting, the source suggests fixing n_estimators according to your time and memory budget, then searching over learning rates. The clearest demonstration in the source uses gradient boosting because it overfits badly until its depth is restricted. The default boosted model reaches a training accuracy of 1.000, which the source reads as a sign of likely overfitting. Two remedies are offered: a smaller maximum depth, or a lower learning rate.