Decision Trees

Gini Impurity

Measure node impurity: Gini = 1 − Σpₖ² where pₖ = count_k/n per class. A counting loop tallies labels into a dict; a second loop sums squared proportions. Library: NumPy 1 − np.sum((counts/n)²) to confirm. RESULT: Gini impurity (rounded).

By hand

labels=['A','A','B','A','B','B'], n=6. Counts: A=3, B=3. p_A=p_B=0.5. Gini = 1 − (0.5² + 0.5²) = 1 − 0.5 = 0.5.

naive.py
Replay: real traced execution (multi-file project)
labels = ['A', 'A', 'B', 'A', 'B', 'B']
n = len(labels)
counts = {}
for lbl in labels:
    counts[lbl] = counts.get(lbl, 0) + 1
sq_sum = 0.0
for lbl in counts:
    p = counts[lbl] / n
    sq_sum = sq_sum + p * p
gini = round(1 - sq_sum, 4)
print('RESULT:', gini)

  1. labels ← ['A', 'A', 'B', 'A', 'B', 'B']

    1labels = ['A', 'A', 'B', 'A', 'B', 'B']2n = len(labels)
    values this step['A', 'A', 'B', 'A', 'B', 'B']labels

  2. n ← 6

    1labels = ['A', 'A', 'B', 'A', 'B', 'B']2n = len(labels)3counts = {}
    values this step6n

  3. counts ← {}

    2n = len(labels)3counts = {}4for lbl in labels:
    values this step{}counts

  4. lbl ← 'A'

    3counts = {}4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 1
    values this step'A'lbl

  5. counts ← {'A': 1}

    4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 16sq_sum = 0.0
    values this step{} → {'A': 1}counts

  6. for lbl in labels:

    3counts = {}4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 1

  7. counts ← {'A': 2}

    4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 16sq_sum = 0.0
    values this step{'A': 1} → {'A': 2}counts

  8. lbl ← 'B'

    3counts = {}4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 1
    values this step'A' → 'B'lbl

  9. counts ← {'A': 2, 'B': 1}

    4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 16sq_sum = 0.0
    values this step{'A': 2} → {'A': 2, 'B': 1}counts

  10. lbl ← 'A'

    3counts = {}4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 1
    values this step'B' → 'A'lbl

  11. counts ← {'A': 3, 'B': 1}

    4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 16sq_sum = 0.0
    values this step{'A': 2, 'B': 1} → {'A': 3, 'B': 1}counts

  12. lbl ← 'B'

    3counts = {}4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 1
    values this step'A' → 'B'lbl

  13. counts ← {'A': 3, 'B': 2}

    4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 16sq_sum = 0.0
    values this step{'A': 3, 'B': 1} → {'A': 3, 'B': 2}counts

  14. for lbl in labels:

    3counts = {}4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 1

  15. counts ← {'A': 3, 'B': 3}

    4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 16sq_sum = 0.0
    values this step{'A': 3, 'B': 2} → {'A': 3, 'B': 3}counts

  16. for lbl in labels:

    3counts = {}4for lbl in labels:5    counts[lbl] = counts.get(lbl, 0) + 1

  17. sq_sum ← 0.0

    5    counts[lbl] = counts.get(lbl, 0) + 16sq_sum = 0.07for lbl in counts:
    values this step0.0sq_sum

  18. lbl ← 'A'

    6sq_sum = 0.07for lbl in counts:8    p = counts[lbl] / n
    values this step'B' → 'A'lbl

  19. p ← 0.5

    7for lbl in counts:8    p = counts[lbl] / n9    sq_sum = sq_sum + p * p
    values this step0.5p

  20. sq_sum ← 0.25

    8    p = counts[lbl] / n9    sq_sum = sq_sum + p * p10gini = round(1 - sq_sum, 4)
    values this step0.0 → 0.25sq_sum

  21. lbl ← 'B'

    6sq_sum = 0.07for lbl in counts:8    p = counts[lbl] / n
    values this step'A' → 'B'lbl

  22. p = counts[lbl] / n

    7for lbl in counts:8    p = counts[lbl] / n9    sq_sum = sq_sum + p * p

  23. sq_sum ← 0.5

    8    p = counts[lbl] / n9    sq_sum = sq_sum + p * p10gini = round(1 - sq_sum, 4)
    values this step0.25 → 0.5sq_sum

  24. for lbl in counts:

    6sq_sum = 0.07for lbl in counts:8    p = counts[lbl] / n

  25. gini ← 0.5

    9    sq_sum = sq_sum + p * p10gini = round(1 - sq_sum, 4)11print('RESULT:', gini)
    values this step0.5gini

  26. stdout ← RESULT: 0.5

    10gini = round(1 - sq_sum, 4)11print('RESULT:', gini)
    values this stepRESULT: 0.5stdout

With NumPy

np.unique(labels, return_counts=True) returns sorted unique labels and their counts in one call. 1 - np.sum((counts/n)**2) applies the formula.

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

labels = ['A', 'A', 'B', 'A', 'B', 'B']
n = len(labels)
_, counts = np.unique(labels, return_counts=True)
gini = round(float(1 - np.sum((counts / n) ** 2)), 4)
print('counts:', counts.tolist())
print('RESULT:', gini)

counts: [3, 3]
RESULT: 0.5

Implementation notes

  • Gini=0 means a pure node (one class only); maximum is 1−1/k for k equally represented classes. For binary: max=0.5 at a 50/50 split — this example.
  • Decision trees choose the split that most reduces Gini from parent to the weighted average of child Ginis (Gini gain).
  • Gini uses no logarithm, making it cheaper to compute than entropy. Cross-reference: entropy-information-gain (this chapter) for the log-based alternative; both drive the same split-selection logic.
  • Cross-reference: threshold-probabilities (ch04) for how class counts relate to predicted probabilities.