Decision-tree impurity, entropy, and split selection

A decision tree needs a rule for choosing between possible feature tests. Impurity measures quantify how mixed the class labels are at a node. A split is useful when its child nodes are collectively less mixed than the parent.

Gini impurity #

If class proportions are p₁, p₂, ..., Gini impurity is 1 - Σpᵢ². A node containing only one class has impurity zero. For two equally common classes, impurity is 1 - 0.5² - 0.5² = 0.5.^[1]

For eight examples containing six of class A and two of class B, the proportions are 0.75 and 0.25. Gini impurity is 1 - 0.75² - 0.25² = 0.375. The result measures mixture, not an error count or a probability that a particular future prediction is wrong.

Weighting the children #

Child impurities must be weighted by their sizes. Suppose a split puts four examples in a pure node and four in an evenly mixed node. The weighted impurity is (4/8) × 0 + (4/8) × 0.5 = 0.25. Compared with the parent impurity of 0.375, the decrease is 0.125.

Averaging the child values without weights gives the wrong comparison when the child sizes differ. The size weighting keeps every training observation represented in the calculation.

Entropy and information gain #

Entropy is -Σpᵢ log₂(pᵢ), with a zero-proportion contribution interpreted as zero. It is zero for a pure node and one bit for two equally common classes. Information gain is parent entropy minus weighted child entropy. Gini decrease and information gain share an objective but can rank candidate splits differently.^[1]

Interpreting a selected tree #

A locally favorable split does not guarantee the globally best tree or reliable future performance. Small leaves can capture noise. Inspect held-out predictions and class-specific errors rather than relying only on training purity.