Constructing Decision Trees with Gini Impurity

2.5 — Constructing Decision Trees with Gini Impurity

Recall first. A pure node contains one class only. What should its impurity be? What should happen to impurity when the classes are evenly mixed?

First correct the terminology

The Gini index/impurity used in the standard CART classification split is a measure of class mixing. For a node with class proportions p₁,...,p_K:

Gini(node) = 1 − Σₖ pₖ²

It is 0 for a pure node and largest when classes are evenly distributed. It is not only for regression. For a regression tree, “Gini” is not the usual target impurity; CART commonly uses squared-error/variance reduction. Thus, if the syllabus parenthesis says “Gini Index (Regression),” write the exam answer carefully: Gini constructs classification trees, while the same recursive-tree idea constructs regression trees with a numeric criterion.¹²

Split selection

For a candidate binary split, compute each child impurity and weight it by its fraction of samples:

I_split = (n_L/n)Gini(L) + (n_R/n)Gini(R)
Gain = Gini(parent) − I_split

The greedy CART learner chooses the candidate with the largest gain (or smallest I_split). Weighting matters: a tiny pure child should not automatically beat a useful balanced partition. Continue recursively, then stop or prune to control variance.

Worked numerical example

Parent node labels are [A,A,A,B,B,B]. Thus p_A=p_B=1/2:

Gini(parent) = 1 − (1/2)² − (1/2)² = 0.5

Candidate S₁ produces left [A,A,A] and right [B,B,B]:

Gini(L)=0, Gini(R)=0
I_S₁ = (3/6)0 + (3/6)0 = 0
Gain(S₁)=0.5

Candidate S₂ produces left [A,A,B] and right [A,B,B]. Each child has proportions 2/3 and 1/3:

Gini(child)=1−(2/3)²−(1/3)²=2/9
I_S₂=(3/6)(2/9)+(3/6)(2/9)=2/9≈0.222
Gain(S₂)=0.5−0.222≈0.278

S₁ is selected because it gives the larger impurity reduction. If a node has three classes in proportions 1/2, 1/3, 1/6, its Gini is 1−1/4−1/9−1/36 = 11/18≈0.611.

Gini versus entropy

Entropy is another classification impurity: H = −Σ pₖ log₂ pₖ. Both are 0 for purity and favor splits that make children purer. Their numerical scales differ, so compare gains within the same criterion. Gini avoids logarithms and is commonly used by CART implementations; entropy has an information-theoretic interpretation. Neither guarantees the globally optimal tree.¹

Exercise

A parent has 10 examples: 6 positive and 4 negative. A split gives left 4 positive/1 negative and right 2 positive/3 negative. Compute parent Gini, weighted child Gini, and gain.

Exam lens

Write the formula, state 0 = pure, compute parent → each child → weighted average → gain, and compare candidates. Explicitly say “classification impurity.” Add the regression contrast: numeric trees usually reduce squared error/variance.

Rapid revision checklist

• Can I calculate 1−Σp²?
• Can I explain why child impurities are weighted?
• Can I choose the larger-gain split?
• Can I distinguish classification Gini from regression variance reduction?

Key takeaways

• Gini impurity measures class mixing, not regression error.
• A split is judged by the weighted impurity of its children.
• The learner greedily maximizes impurity reduction and later needs stopping/pruning.
• Gini and entropy are alternative classification criteria, not interchangeable numeric scales.

Sources