GINI INDEX

GINI

Used by CART (Classification and Regression Trees). Measures how often a randomly chosen sample would be misclassified if we labeled it according to the distribution of classes in that node. A pure node (all samples in one class) has a Gini score of 0.The closer the score is to 0, the purer the node.

The formula is:

$$Gini(node) = 1 - \sum_{c=1}^{C} \big( p(c \mid node) \big)^2$$

Where:

• $C$ = number of classes

• $p(c \mid node)$ = proportion (frequency) of class $c$ among the data at that node

Interpretation:

• If all samples at the node belong to one class → $Gini = 0$ (pure node).

• The higher the Gini value, the more mixed the classes are at that node.

Example:
Suppose a node has 10 samples: 7 positive and 3 negative.

$$p(positive)=0.7,p(negative)=0.3\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}$$$$Gini=1-({0.7}^2+{0.3}^2)=1-(0.49+0.09)=0.42$$

This shows the node is somewhat impure, since both classes are present.

Toy dataset

We’ll predict Play (Yes/No) from three features: Outlook, Humidity, Wind.

ID	Outlook	Humidity	Wind	Play
1	Sunny	High	Weak	No
2	Sunny	High	Strong	No
3	Overcast	High	Weak	Yes
4	Rain	High	Weak	Yes
5	Rain	Normal	Weak	Yes
6	Rain	Normal	Strong	No
7	Overcast	Normal	Strong	Yes
8	Sunny	Normal	Weak	Yes
9	Sunny	Normal	Strong	Yes
10	Overcast	High	Strong	Yes

Totals: Yes = 7, No = 3.

Gini(node) = $1 - \sum_c p(c|node)^2$

Root Gini = $1 - (0.7^2 + 0.3^2) = 0.42$

---

Step 1 — Evaluate first split (try every feature)

We compute the weighted Gini after splitting on each feature and pick the smallest.

Split by Outlook (Sunny / Overcast / Rain)

• Sunny: {1,2,8,9} → Yes=2, No=2 → Gini = $1- ({0.5}^{\mathrm{2 }}+ {0.5}^2) =$

• Overcast: {3,7,10} → Yes=3, No=0 → Gini = 0

• Rain: {4,5,6} → Yes=2, No=1 → Gini = $1$

Weighted Gini = $(4\mathrm{/}10)\ast \mathrm{0.50 }+ (3\mathrm{/}10)\ast \mathrm{0 }+ (3\mathrm{/}10)\ast \mathrm{0.444 }\approx 0.20+0+\mathrm{0.133 }= 0.333$

Impurity reduction = $0.42 − 0.333 = 0.087$

Split by Humidity (High / Normal)

• High: {1,2,3,4,10} → Yes=3, No=2 → Gini = $1 − (0.6^2 + 0.4^2) = 0.48$
  

• Normal: {5,6,7,8,9} → Yes=4, No=1 → Gini = $1-({0.8}^2+{0.2}^2)=0.32$

Weighted Gini = $0.5*0.48 + 0.5*0.32 = 0.40$
Reduction = $0.42 − 0.40 = 0.02$

Split by Wind (Weak / Strong)

• Weak: {1,3,4,5,8} → Yes=4, No=1 → Gini = 0.32

• Strong: {2,6,7,9,10} → Yes=3, No=2 → Gini = 0.48

Weighted Gini = $0.5*0.32 + 0.5*0.48 = 0.40$
Reduction = $0.42 − 0.40 = 0.02$

Best first split: Outlook (lowest weighted Gini ≈ 0.333).

Current (partial) tree:

• Root: Outlook

  • Overcast → leaf Yes (pure)

  • Sunny → mixed (needs splitting)

  • Rain → mixed (needs splitting)

Step 2 — Split the Rain branch

Rain subset: {4,5,6} → Yes=2, No=1 → Gini ≈ 0.444

Try Humidity within Rain:

• High: {4} → Yes=1 → Gini = 0

• Normal: {5,6} → Yes=1, No=1 → Gini = 0.5
  Weighted = $(1/3)*0 + (2/3)*0.5 = 1/3 ≈ 0.333$

Try Wind within Rain:

• Weak: {4,5} → Yes=2 → Gini = 0

• Strong: {6} → No=1 → Gini = 0
  Weighted = 0

Best split for Rain: Wind (perfectly pure).

Rain branch becomes:

• Rain → Wind

  • Weak → Yes

  • Strong → No

Step 3 — Split the Sunny branch

Sunny subset: {1,2,8,9} → Yes=2, No=2 → Gini = 0.5

Try Humidity within Sunny:

• High: {1,2} → No=2 → Gini = 0

• Normal: {8,9} → Yes=2 → Gini = 0
  Weighted = 0

(Any other Sunny split won’t beat 0.)

Best split for Sunny: Humidity (perfectly pure).

Sunny branch becomes:

• Sunny → Humidity

  • High → No

  • Normal → Yes

Final Tree