Concept - Gini Impurity

Gini Impurity and Gini Gain

Definition (s.322), “corresponding to entropy”: randomly pick a datapoint, randomly classify it according to the class distribution of the dataset; the probability that we classify it incorrectly is the Gini impurity.

$G={\sum }_{i=1}^{K}p(i)(1-p(i))$

$K$ = total classes; $p(i)$ = probability of picking a sample with class $i$. Example (5 blue, 5 green points): $G=0.5\cdot 0.5+0.5\cdot 0.5=0.5$.

Split impurity and Gini gain (s.323-324)

Weight each branch by its share of elements, e.g. $GI=0.4G{I}_{Left}+0.6G{I}_{Right}$. Gini Gain = original impurity − weighted branch impurities; the best split maximizes Gini gain.

• Split $x=2$: $G=0$, gain $0.5-0=0.5$.
• Split $x=1.5$: $G=0.4\cdot 0+0.6\cdot 0.278=0.167$ ($G_{right}=\frac{5}{18}=0.278$), gain $0.333$.

Exercise - Play Tennis (s.325-327)

• $G(Play)=0.4591$; sunny (5/14) $G_s=0.48$; overcast (4/14) $G_o=0$; rainy (5/14) $G_r=0.48$.
• Gini Gain(Outlook) $=0.4591-0.171-0-0.171=0.117$.
• Temperature 0.0185; Humidity 0.0916; Windy 0.0304 → Outlook best.

Related

Concept - Entropy | Concept - Information Gain | Concept - Decision Tree | Concept - ID3

Appears in

• 03 Text Classification - Chunk 11 (s.301-330)