Classification Trees

Definition A classification tree predicts a categorical target with classes $1, \dots, K$ from a feature vector $\mathbf{x}$ with features $x_1, \dots, x_p$. It is a rooted binary tree. Each internal node holds a test on one feature, on this page of the form $x_j \le t$ for a numerical feature $x_j$ and a threshold $t$, and sends an input to its left child when the test holds and to its right child otherwise. Each leaf holds a predicted class, usually together with estimated class probabilities. Following the tests from the root, every input reaches exactly one leaf, so the leaves divide feature space into disjoint regions $R_1, \dots, R_M$ that together cover it, and the tree gives the same prediction to all inputs in one region. The tests may use only features that are available when the prediction is made. Decision tree is the general name, and a classification tree is a decision tree for a categorical target.

Definition Consider a node reached by $n_m \ge 1$ training rows, of which $n_{mk}$ belong to class $k$, and let $p_k = n_{mk}/n_m$ be the class proportions, with every row counted once. The Gini impurity of the node is

For two classes with positive proportion $p$ it reduces to $G = 2p(1 - p)$. It is $0$ exactly when the node is pure, meaning all its rows share one class, and it is largest, with value $1 - 1/K$, exactly when every class has proportion $1/K$, which gives $1/2$ for two classes. If two labels are drawn independently and with replacement from the node’s rows, the probability that they differ is $G$. The proportions need at least one row, so an empty node has no Gini impurity. Gini impurity describes how mixed the training labels are, and it says nothing about what a false positive or a false negative costs.

Definition For a node with at least one row and class proportions $p_1, \dots, p_K$, the entropy is

with the convention $0 \log_2 0 = 0$, the limit of $q \log_2 q$ as $q \to 0^{+}$. With base-2 logarithms it is measured in bits. It is $0$ exactly when the node is pure, and it is largest, with value $\log_2 K$, exactly when every class has proportion $1/K$, so two balanced classes give $1$ bit. Suppose a split sends the $n$ rows of a node to children with $n_1, \dots, n_J$ rows, each at least $1$. The information gain of the split is the entropy of the parent minus the size-weighted entropy of the children,

The children’s class proportions, weighted by $n_j/n$, average to the parent’s, and entropy and Gini impurity are strictly concave functions of the proportions. So the information gain and the Gini decrease of the next card are never negative, and each is $0$ exactly when every child has the same class proportions as the parent. Some authors use the name information gain for a decrease in any impurity, so a reported gain should name its impurity.

Definition Let $I$ be an impurity function such as Gini impurity or entropy, and let a candidate split send the $n$ training rows of a node to a left child with $n_L$ rows and a right child with $n_R$ rows, where $n_L + n_R = n$. The split is valid only if $n_L \ge 1$ and $n_R \ge 1$. A child with no rows has no class proportions, so its impurity is undefined, and a split that sends every row the same way does not divide the node at all. For a valid split, the weighted child impurity is

and the impurity decrease is $\Delta I = I(\text{parent}) - I_{\text{split}}$. The weights are the children’s shares of the rows at the node. With sample weights, every count becomes a sum of weights. Some software multiplies every decrease at a node by the node’s share of all training rows, which changes the numbers but not which split wins at that node.

Definition Greedy splitting grows a tree from the root by repeating one step at each node. First collect the valid candidate splits. For a numerical feature $x_j$, sort the distinct values of $x_j$ among the node’s rows and use the midpoints between consecutive values as thresholds, so every candidate has two nonempty children. Then choose the candidate with the largest impurity decrease, using a fixed rule to break ties, split the node, and repeat the step in each child. A node becomes a leaf when a stopping rule applies, for example when it is pure, when every feature is constant on its rows so that no valid split exists, when it reaches a maximum depth, when every split would leave a child with fewer than a minimum number of rows, or when the best decrease is below a set amount. Each choice looks only one split ahead, so greedy splitting is not guaranteed to find the best tree of a given size or depth. Searching all trees for the best one is a hard combinatorial problem in general, which is why the greedy method is the standard one.

Definition Suppose leaf $\ell$ is reached by $n_\ell \ge 1$ training rows, $n_{\ell k}$ of them in class $k$. Counting every row once, the leaf probability of class $k$ is

and the tree gives this same estimate to every input in the region $R_\ell$. The predicted class is the most frequent class in the leaf, with a fixed rule for ties, or, with two classes, the result of comparing $\hat{P}(Y = 1 \mid \mathbf{x})$ with a decision threshold. A leaf probability is an estimate from the training rows of one region. It can be far off when the leaf holds few rows, and leaves grown until they are pure report $0$ or $1$, which is usually overconfident on new data. Smoothing changes the estimate, for example the Laplace rule $(n_{\ell k} + 1)/(n_\ell + K)$, and weighted rows give weighted proportions, so either choice should be stated when it is used. Whether the probabilities are calibrated has to be checked on held-out data.