Decision Trees

A decision tree is a predictive model that maps input features to an output (class label or numeric value) by repeatedly asking binary questions about the data. Despite their simplicity, decision trees are the atomic unit of the most powerful ML algorithms in production today — gradient boosting models like LightGBM and XGBoost are ensembles of hundreds or thousands of decision trees.

Understanding how a single tree thinks is the prerequisite for understanding why ensemble methods work.

How a Tree Makes a Prediction

A trained decision tree is a directed binary tree of decision nodes and leaf nodes.

                    [Debt-to-Income Ratio > 0.43?]
                         /               \
                       Yes                No
                        |                  |
          [Credit Score < 620?]    [Loan Amount > $500k?]
               /        \                /          \
             Yes          No            Yes           No
              |            |             |             |
          DENY         APPROVE        REVIEW        APPROVE

At each decision node, the tree applies a threshold test on one feature (feature_j <= threshold). A sample travels left if true, right if false, until it reaches a leaf node which returns the prediction.

At prediction time: O(depth) — extremely fast even with millions of samples.

How Splits Are Chosen: Impurity Measures

During training, the algorithm must decide: which feature and which threshold to split on at each node? The answer is: the split that most reduces impurity — a measure of class mixing in a node.

Gini Impurity

Gini measures the probability that a randomly chosen sample would be misclassified if labeled according to the class distribution at that node.

Where p_k is the fraction of samples in class k in set S.

A node with Gini = 0 is a pure leaf — every sample belongs to the same class. Gini is the default in scikit-learn's DecisionTreeClassifier.

Entropy (Information Gain)

Entropy measures the average information content (uncertainty) of the class distribution, borrowed from information theory.

The information gain of a split is:

We choose the split that maximizes information gain (equivalently, minimizes weighted child entropy).

Gini vs Entropy in practice: Both produce nearly identical trees. Gini is slightly faster to compute (no logarithm). Entropy is marginally more likely to produce balanced splits in edge cases. For most problems, the difference is negligible.

Variance Reduction (Regression Trees)

For regression, impurity is measured by variance. The split that maximally reduces variance in the target variable is chosen:

The leaf prediction is the mean of target values in that leaf.