Gini impurity

A decision tree splits data to make each resulting group as "pure" as possible — ideally each leaf contains only one class. Gini impurity is a number that measures how impure (mixed-up) a node is. Lower = purer.

The Core Idea

WHY this formula? (Derivation from scratch)

WHAT we want: the probability that a randomly picked item is labelled incorrectly if we assign it a random class label drawn from the node's own distribution.

HOW we build it step by step:

Pick a random item. Probability it truly belongs to class $i$ is $==p_i==$ . Why? $p_i$ is defined as that class's share of the node.
Independently pick a random label from the same distribution. Probability that label is class $i$ is also $p_i$ .
We are wrong whenever the true class ( $i$ ) and the guessed label ( $j$ ) differ: $i \neq j$ . Probability of a match on class $i$ is $p_i \cdot p_i = p_i^2$ . Why square? Two independent draws both landing on $i$ .
Total probability of a correct match (any class): $\sum_i p_i^2$ .
Therefore probability of a mistake: $G = 1 - \sum_{i=1}^{K} p_i^2$
Rewrite algebraically to see the "per-class error" view: $1 - \sum_i p_i^2 = \sum_i p_i - \sum_i p_i^2 = \sum_i p_i(1-p_i)$ Why this matters? Each term $p_i(1-p_i)$ = (chance item is class $i$ ) × (chance our guess is NOT class $i$ ). It reads as "expected misclassification per class."

Worked Examples

Worked example Example 2 — Choosing between two splits

Parent: 8 positive (+), 4 negative (−), total 12. $p=(8/12,4/12)$ . $G_{\text{parent}} = 1 - \left(\tfrac{2}{3}\right)^2 - \left(\tfrac{1}{3}\right)^2 = 1 - \tfrac49 - \tfrac19 = \tfrac49 \approx 0.444$

Split X → Left: (4+,0−)=4 items; Right: (4+,4−)=8 items.

$G_L = 1-1^2-0^2 = 0$ . Why? pure.
$G_R = 1-0.5^2-0.5^2 = 0.5$ .
$G_X = \frac{4}{12}(0) + \frac{8}{12}(0.5) = 0.333$ .

Split Y → Left: (6+,1−)=7; Right: (2+,3−)=5.

$G_L = 1-(6/7)^2-(1/7)^2 = 1 - 36/49 - 1/49 = 12/49 \approx 0.245$ .
$G_R = 1-(2/5)^2-(3/5)^2 = 1 - 0.16-0.36 = 0.48$ .
$G_Y = \frac{7}{12}(0.245)+\frac{5}{12}(0.48) = 0.143 + 0.200 = 0.343$ .

Decision: $G_X = 0.333 < G_Y = 0.343$ , so Split X wins (higher gain $0.444-0.333=0.111$ ). Why this step? A perfectly pure child (Gini 0) drags the weighted average down hard even though the other child stays mixed.

Common Mistakes

Recall Feynman: explain to a 12-year-old

You have a box of jelly beans, some red, some green. You play a game: pull one bean, hide its color, then guess its color by pulling another random bean and copying that one's color. If the box is all red, you always win. If it's half-half, you lose a lot. Gini impurity is just "how often you lose this game." A smart tree keeps splitting the box into smaller boxes so each box is nearly all one color — because then you almost never lose.

Active Recall

What is the Gini impurity formula for a node?

G = 1 - \sum_{i=1}^K p_i^2 = \sum_i p_i(1-p_i)

What does Gini impurity literally measure (probabilistic meaning)?

The probability of misclassifying a random item if you guess its class using a randomly drawn label from the node's own class distribution.

What is the Gini impurity of a perfectly pure node?

What is the maximum Gini impurity for K classes, and when?

1 - 1/K

, achieved when all classes are equally likely (uniform

p_i = 1/K

Max Gini for a 2-class node?

0.5 (at 50/50 split).

How do we score a candidate split?

Weighted average impurity of children

\sum_c \frac{N_c}{N}G_c

; the tree maximizes Gini gain =

G_{parent} - G_{split}

Why weight children by

N_c/N

instead of a plain average?

Larger children contribute more total misclassifications; unweighted sums ignore child sizes and inflate with more branches.

Why is a uniform distribution the worst (highest Gini)?

Because

\sum p_i^2

is minimized when probability is spread evenly, so

G=1-\sum p_i^2

is maximized.

Gini vs Entropy — practical difference?

Both 0 at purity, max at uniform; Gini avoids computing

\log

so it's cheaper and usually gives near-identical trees.

Does Gini=0 on training data mean a good model?

No — it often signals overfitting/memorization; purity is the split criterion, not the generalization target.

Connections

Decision Trees — Gini is the default split criterion in CART/scikit-learn.
Entropy and Information Gain — the alternative impurity measure ( $-\sum p\log p$ ).
Overfitting and Pruning — why we don't chase Gini=0.
Random Forests — average many Gini-grown trees.
Classification vs Regression Trees — regression uses variance/MSE instead of Gini.
Gini Coefficient (Economics) — different concept, same name (don't confuse).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Gini impurity ka matlab bilkul simple hai: ek node (data ka group) kitna "mixed-up" hai, yeh batata hai. Socho ek dabbe mein red aur green balls hain. Tum ek ball uthate ho, uska color chhupa dete ho, aur guess karne ke liye ek aur random ball nikaal kar uska color copy karte ho. Agar saare balls red hain to tum kabhi galat nahi honge — impurity 0. Agar aadhe-aadhe hain to bahut baar galat honge — impurity maximum (0.5 for 2 classes). Bas yehi probability of mistake hi Gini hai: $G = 1 - \sum p_i^2$ .

Formula yaad rakhne ka trick: "One minus sum of squares". Har class ka proportion $p_i$ nikaalo, square karo, sabko add karo, aur 1 se minus kardo. Jab ek hi class dominate karti hai to $\sum p_i^2$ bada ho jaata hai, isliye $G$ chhota (pure) ho jaata hai. Jab sab equal hote hain, tab $G$ sabse zyada.

Decision tree yeh karti hai: har possible split try karti hai, aur dekhti hai konsa split children ko sabse zyada pure banata hai. Isko measure karne ke liye hum children ki Gini ka weighted average lete hain — bade child ko zyada weight ( $N_c/N$ ), kyunki usme zyada data hai. Jo split $G_{split}$ ko sabse kam karta hai (yaani gain sabse zyada), wahi chunte hain.

Ek important baat: Gini ko zabardasti 0 tak le jaana hamesha accha nahi. Agar training data pe har leaf perfectly pure ho gayi, iska matlab tree ne noise rat liya (overfitting). Isliye hum depth limit karte hain ya pruning karte hain. Gini sirf split choose karne ka tool hai, final goal generalization hai — yeh farak yaad rakhna exam aur interview dono mein.

The Core Idea

WHY this formula? (Derivation from scratch)

Worked Examples

Common Mistakes

Active Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Tree-Based & Instance Methods

Connections