Decision Trees

Entropy and Information Gain

Entropy = −Σpₖ·log₂(pₖ) measures node impurity in bits. Information gain = entropy(parent) − weighted average of child entropies for a proposed split. Three inline counting loops compute each entropy. Library: NumPy helper ent() to confirm. RESULT: information gain (rounded).

By hand

parent=['A','A','B','B'] (n=4, balanced): H=1.0 bit. left=['A','A','B'] (n=3, 2A 1B): H=0.9183. right=['B'] (n=1, pure): H=0. IG = 1.0 − (3/4)·0.9183 − (1/4)·0 = 0.3113 bits.

naive.py
Replay: real traced execution (multi-file project)
import math
parent = ['A', 'A', 'B', 'B']
left   = ['A', 'A', 'B']
right  = ['B']
n_p = len(parent)
cnt_p = {}
for lbl in parent:
    cnt_p[lbl] = cnt_p.get(lbl, 0) + 1
h_p = 0.0
for lbl in cnt_p:
    p = cnt_p[lbl] / n_p
    h_p = h_p - p * math.log2(p)
n_l = len(left)
cnt_l = {}
for lbl in left:
    cnt_l[lbl] = cnt_l.get(lbl, 0) + 1
h_l = 0.0
for lbl in cnt_l:
    p = cnt_l[lbl] / n_l
    h_l = h_l - p * math.log2(p)
n_r = len(right)
cnt_r = {}
for lbl in right:
    cnt_r[lbl] = cnt_r.get(lbl, 0) + 1
h_r = 0.0
for lbl in cnt_r:
    p = cnt_r[lbl] / n_r
    h_r = h_r - p * math.log2(p)
ig = h_p - (n_l / n_p) * h_l - (n_r / n_p) * h_r
print('RESULT:', round(ig, 4))

  1. import math

    1import math2parent = ['A', 'A', 'B', 'B']

  2. parent ← ['A', 'A', 'B', 'B']

    1import math2parent = ['A', 'A', 'B', 'B']3left   = ['A', 'A', 'B']
    values this step['A', 'A', 'B', 'B']parent

  3. left ← ['A', 'A', 'B']

    2parent = ['A', 'A', 'B', 'B']3left   = ['A', 'A', 'B']4right  = ['B']
    values this step['A', 'A', 'B']left

  4. right ← ['B']

    3left   = ['A', 'A', 'B']4right  = ['B']5n_p = len(parent)
    values this step['B']right

  5. n_p ← 4

    4right  = ['B']5n_p = len(parent)6cnt_p = {}
    values this step4n_p

  6. cnt_p ← {}

    5n_p = len(parent)6cnt_p = {}7for lbl in parent:
    values this step{}cnt_p

  7. lbl ← 'A', cnt_p ← {'A': 1}

    pass 1 of 4
    6cnt_p = {}7for lbl in parent:8    cnt_p[lbl] = cnt_p.get(lbl, 0) + 19h_p = 0.0
    values this step'A'lbl{} → {'A': 1}cnt_p
    All 4 passes — pass 1 is the card above
    passlblcnt_p
    1'A'{} → {'A': 1}
    2—{'A': 1} → {'A': 2}
    3'A' → 'B'{'A': 2} → {'A': 2, 'B': 1}
    4—{'A': 2, 'B': 1} → {'A': 2, 'B': 2}

  8. for lbl in parent:

    6cnt_p = {}7for lbl in parent:8    cnt_p[lbl] = cnt_p.get(lbl, 0) + 1

  9. h_p ← 0.0

    8    cnt_p[lbl] = cnt_p.get(lbl, 0) + 19h_p = 0.010for lbl in cnt_p:
    values this step0.0h_p

  10. lbl ← 'A', p ← 0.5, h_p ← 0.5

    pass 1 of 2
    9h_p = 0.010for lbl in cnt_p:11    p = cnt_p[lbl] / n_p12    h_p = h_p - p * math.log2(p)13n_l = len(left)
    values this step'B' → 'A'lbl0.5p0.0 → 0.5h_p

  11. lbl ← 'B', h_p ← 1.0

    pass 2 of 2
    9h_p = 0.010for lbl in cnt_p:11    p = cnt_p[lbl] / n_p12    h_p = h_p - p * math.log2(p)13n_l = len(left)
    values this step'A' → 'B'lbl0.5 → 1.0h_p

  12. for lbl in cnt_p:

    9h_p = 0.010for lbl in cnt_p:11    p = cnt_p[lbl] / n_p

  13. n_l ← 3

    12    h_p = h_p - p * math.log2(p)13n_l = len(left)14cnt_l = {}
    values this step3n_l

  14. cnt_l ← {}

    13n_l = len(left)14cnt_l = {}15for lbl in left:
    values this step{}cnt_l

  15. lbl ← 'A', cnt_l ← {'A': 1}

    pass 1 of 3
    14cnt_l = {}15for lbl in left:16    cnt_l[lbl] = cnt_l.get(lbl, 0) + 117h_l = 0.0
    values this step'B' → 'A'lbl{} → {'A': 1}cnt_l
    All 3 passes — pass 1 is the card above
    passlblcnt_l
    1'B' → 'A'{} → {'A': 1}
    2—{'A': 1} → {'A': 2}
    3'A' → 'B'{'A': 2} → {'A': 2, 'B': 1}

  16. for lbl in left:

    14cnt_l = {}15for lbl in left:16    cnt_l[lbl] = cnt_l.get(lbl, 0) + 1

  17. h_l ← 0.0

    16    cnt_l[lbl] = cnt_l.get(lbl, 0) + 117h_l = 0.018for lbl in cnt_l:
    values this step0.0h_l

  18. lbl ← 'A', p ← 0.6666666666666666, h_l ← 0.38997500048077083

    pass 1 of 2
    17h_l = 0.018for lbl in cnt_l:19    p = cnt_l[lbl] / n_l20    h_l = h_l - p * math.log2(p)21n_r = len(right)
    values this step'B' → 'A'lbl0.5 → 0.6666666666666666p0.0 → 0.38997500048077083h_l

  19. lbl ← 'B', p ← 0.3333333333333333, h_l ← 0.9182958340544896

    pass 2 of 2
    17h_l = 0.018for lbl in cnt_l:19    p = cnt_l[lbl] / n_l20    h_l = h_l - p * math.log2(p)21n_r = len(right)
    values this step'A' → 'B'lbl0.6666666666666666 → 0.3333333333333333p0.38997500048077083 → 0.9182958340544896h_l

  20. for lbl in cnt_l:

    17h_l = 0.018for lbl in cnt_l:19    p = cnt_l[lbl] / n_l

  21. n_r ← 1

    20    h_l = h_l - p * math.log2(p)21n_r = len(right)22cnt_r = {}
    values this step1n_r

  22. cnt_r ← {}

    21n_r = len(right)22cnt_r = {}23for lbl in right:
    values this step{}cnt_r

  23. for lbl in right:

    22cnt_r = {}23for lbl in right:24    cnt_r[lbl] = cnt_r.get(lbl, 0) + 1

  24. cnt_r ← {'B': 1}

    23for lbl in right:24    cnt_r[lbl] = cnt_r.get(lbl, 0) + 125h_r = 0.0
    values this step{} → {'B': 1}cnt_r

  25. for lbl in right:

    22cnt_r = {}23for lbl in right:24    cnt_r[lbl] = cnt_r.get(lbl, 0) + 1

  26. h_r ← 0.0

    24    cnt_r[lbl] = cnt_r.get(lbl, 0) + 125h_r = 0.026for lbl in cnt_r:
    values this step0.0h_r

  27. for lbl in cnt_r:

    25h_r = 0.026for lbl in cnt_r:27    p = cnt_r[lbl] / n_r

  28. p ← 1.0

    26for lbl in cnt_r:27    p = cnt_r[lbl] / n_r28    h_r = h_r - p * math.log2(p)
    values this step0.3333333333333333 → 1.0p

  29. h_r = h_r - p * math.log2(p)

    27    p = cnt_r[lbl] / n_r28    h_r = h_r - p * math.log2(p)29ig = h_p - (n_l / n_p) * h_l - (n_r / n_p) * h_r

  30. for lbl in cnt_r:

    25h_r = 0.026for lbl in cnt_r:27    p = cnt_r[lbl] / n_r

  31. ig ← 0.31127812445913283

    28    h_r = h_r - p * math.log2(p)29ig = h_p - (n_l / n_p) * h_l - (n_r / n_p) * h_r30print('RESULT:', round(ig, 4))
    values this step0.31127812445913283ig

  32. stdout ← RESULT: 0.3113

    29ig = h_p - (n_l / n_p) * h_l - (n_r / n_p) * h_r30print('RESULT:', round(ig, 4))
    values this stepRESULT: 0.3113stdout

With NumPy

Helper ent() uses np.unique for counts and −np.sum(p·np.log2(p)) for entropy in bits. abs() guards against −0.0 on pure (single-class) nodes.

library.py 
import numpy as np
from dalib.display import set_display
set_display()

def ent(labels):
    n = len(labels)
    _, counts = np.unique(labels, return_counts=True)
    p = counts / n
    return abs(float(-np.sum(p * np.log2(p))))

parent = ['A', 'A', 'B', 'B']
left   = ['A', 'A', 'B']
right  = ['B']
h_p = ent(parent)
h_l = ent(left)
h_r = ent(right)
ig = h_p - (len(left) / len(parent)) * h_l - (len(right) / len(parent)) * h_r
print('h_parent:', round(h_p, 4))
print('h_left:', round(h_l, 4))
print('h_right:', round(h_r, 4))
print('RESULT:', round(ig, 4))

h_parent: 1.0
h_left: 0.9183
h_right: 0.0
RESULT: 0.3113

Implementation notes

  • Entropy=0 → pure node; entropy=log₂(k) → maximally mixed k equal classes. Binary maximum = 1 bit at 50/50; parent here is 50/50 → H=1.0.
  • IG=0.3113 means this split removes 0.3113 bits of impurity. The right child is pure (H=0) but has only 1 sample, so its weight (1/4) is small.
  • log₂(1)=0 in the pure child: the h_r loop computes −1·log₂(1)=0 correctly without a special-case branch.
  • Weights (n_left/n, n_right/n) penalise unequal splits — a large impure child contributes more to the weighted average than a small pure one.
  • Cross-reference: gini-impurity (this chapter) for the log-free impurity alternative; the split-selection logic is the same, only the measure differs.