Decision Trees: Shannon Entropy, Information Gain & Gini Index
“Impurity splitting metrics, ID3 vs CART, continuous feature thresholds, and cost-complexity pruning.”
1.The Mathematics of Tree Splitting Criteria
§ 3.1.Decision trees recursively partition input feature space into orthogonal hyper-rectangles using greedy impurity reduction.
Entropy vs Gini Impurity:
Both measure the impurity of a node. Gini impurity is computationally faster because it avoids logarithmic evaluations (log_2). For a binary classification task:
- Entropy = - [ p log_2(p) + (1-p) log_2(1-p) ] (peaks at 1.0 bit when p=0.5).
- Gini = 1 - [ p^2 + (1-p)^2 ] = 2p(1-p) (peaks at 0.5 when p=0.5).
2. Worked Practice Problem: Information Gain on Discrete Features
Remember to weight each child entropy by its proportion |S_v| / |S|.
Problem: A dataset of 10 samples has 6 Positive (+) and 4 Negative (-) instances. A feature splits it into Left (4+, 1-) and Right (2+, 3-). Compute the Information Gain.
Step 1: Compute Parent Entropy H(S):
p+ = 6/10 = 0.6, p- = 4/10 = 0.4
H(S) = - [ 0.6 log2(0.6) + 0.4 log2(0.4) ] = - [ 0.6(-0.737) + 0.4(-1.322) ] = 0.442 + 0.529 = 0.971 bits.
Step 2: Compute Left Child Entropy H(S_L) [4+, 1-]:
p+ = 4/5 = 0.8, p- = 1/5 = 0.2
H(S_L) = - [ 0.8log2(0.8) + 0.2log2(0.2) ] = - [ 0.8(-0.322) + 0.2(-2.322) ] = 0.258 + 0.464 = 0.722 bits.
Step 3: Compute Right Child Entropy H(S_R) [2+, 3-]:
p+ = 2/5 = 0.4, p- = 3/5 = 0.6
H(S_R) = 0.971 bits (same distribution as parent).
Step 4: Compute Weighted Child Entropy:
E[H] = (5/10) H(S_L) + (5/10) H(S_R) = 0.5 (0.722 + 0.971) = 0.5 1.693 = 0.8465 bits.
Step 5: Compute Information Gain:
Gain = H(S) - E[H] = 0.971 - 0.8465 = 0.1245 bits.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.