ML0062 Decision Tree

A decision tree partitions the input space into regions by recursively splitting on the feature that best separates the target variable. Each split aims to improve the “purity” of the resulting subsets, measured by criteria such as Gini impurity or entropy. Predictions follow the sequence of splits down to a leaf, returning the most common class (classification) or the average target (regression).

(1) Structure: A tree of nodes: internal nodes test a feature, branches represent the outcomes, leaves give predictions.
(2) Splitting Criterion: Choose the best feature and threshold by maximizing purity: information gain (entropy), Gini impurity, or variance reduction for regression.
(3) Recursive Growth: Starting at the root, split the data, then recurse on each subset until stopping criteria are met (max depth, min samples, or pure leaves).
(4) Prediction: A new sample travels from root to leaf following the feature tests; the leaf’s label or value is returned.

Figure 1: A decision tree from two viewpoints: on the left, the axis-aligned rectangular regions it carves into the feature space; on the right, the tree itself: each node shows its test, impurity, and class counts, and each leaf is a final answer.

Mathematical Formulation:

Where:

• is a tree node; the number of classes; the proportion of class samples in node .
• Gini = 0 means the node is pure (one class only) and grows with mixing; entropy = 0 at perfect purity and is maximal when classes are uniformly mixed.
• In the gain formula, is the parent’s sample count and child ‘s: the split chosen is the one maximizing this weighted impurity drop.

Figure 2: The two classification criteria compared for a binary node: both peak at (maximally mixed) and vanish at pure nodes; they nearly always rank candidate splits in the same order, which is why Gini (no logarithms) is the common default.