Decision Trees

Best Split (Gini Scan)

Find the best 1-feature split by scanning candidate thresholds and choosing the lowest weighted Gini impurity. For each threshold t: split into left (X<t) and right (X≥t), compute weighted Gini. Library: DecisionTreeClassifier(max_depth=1) reads tree_.threshold[0]. RESULT: best threshold.

By hand

X=[1,2,3,5,7,8], y=[0,0,0,1,1,1]. Candidates: t=2.5→wg=0.25, t=4.0→wg=0.0 (perfect split), t=6.0→wg=0.25. Best: 4.0.

naive.py
Replay: real traced execution (multi-file project)
X = [1, 2, 3, 5, 7, 8]
y = [0, 0, 0, 1, 1, 1]
n = len(X)
thresholds = [2.5, 4.0, 6.0]
best_t = None
best_wg = 1.0
for t in thresholds:
    left_y  = [y[i] for i in range(n) if X[i] <  t]
    right_y = [y[i] for i in range(n) if X[i] >= t]
    nl = len(left_y)
    nr = len(right_y)
    c0l = left_y.count(0)
    gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 2
    c0r = right_y.count(0)
    gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 2
    wg = (nl / n) * gl + (nr / n) * gr
    if wg < best_wg:
        best_wg = wg
        best_t = t
print('RESULT:', best_t)

  1. X ← [1, 2, 3, 5, 7, 8]

    1X = [1, 2, 3, 5, 7, 8]2y = [0, 0, 0, 1, 1, 1]
    values this step[1, 2, 3, 5, 7, 8]X

  2. y ← [0, 0, 0, 1, 1, 1]

    1X = [1, 2, 3, 5, 7, 8]2y = [0, 0, 0, 1, 1, 1]3n = len(X)
    values this step[0, 0, 0, 1, 1, 1]y

  3. n ← 6

    2y = [0, 0, 0, 1, 1, 1]3n = len(X)4thresholds = [2.5, 4.0, 6.0]
    values this step6n

  4. thresholds ← [2.5, 4.0, 6.0]

    3n = len(X)4thresholds = [2.5, 4.0, 6.0]5best_t = None
    values this step[2.5, 4.0, 6.0]thresholds

  5. best_t ← None

    4thresholds = [2.5, 4.0, 6.0]5best_t = None6best_wg = 1.0
    values this stepNonebest_t

  6. best_wg ← 1.0

    5best_t = None6best_wg = 1.07for t in thresholds:
    values this step1.0best_wg

  7. t ← 2.5

    6best_wg = 1.07for t in thresholds:8    left_y  = [y[i] for i in range(n) if X[i] <  t]
    values this step2.5t

  8. left_y ← [0, 0]

    7for t in thresholds:8    left_y  = [y[i] for i in range(n) if X[i] <  t]9    right_y = [y[i] for i in range(n) if X[i] >= t]
    values this step[0, 0]left_y

  9. right_y ← [0, 1, 1, 1]

    8left_y  = [y[i] for i in range(n) if X[i] <  t]9right_y = [y[i] for i in range(n) if X[i] >= t]10nl = len(left_y)
    values this step[0, 1, 1, 1]right_y

  10. nl ← 2

    9right_y = [y[i] for i in range(n) if X[i] >= t]10nl = len(left_y)11nr = len(right_y)
    values this step2nl

  11. nr ← 4

    10nl = len(left_y)11nr = len(right_y)12c0l = left_y.count(0)
    values this step4nr

  12. c0l ← 2

    11nr = len(right_y)12c0l = left_y.count(0)13gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 2
    values this step2c0l

  13. gl ← 0.0

    12c0l = left_y.count(0)13gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 214c0r = right_y.count(0)
    values this step0.0gl

  14. c0r ← 1

    13gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 214c0r = right_y.count(0)15gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 2
    values this step1c0r

  15. gr ← 0.375

    14c0r = right_y.count(0)15gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 216wg = (nl / n) * gl + (nr / n) * gr
    values this step0.375gr

  16. wg ← 0.25

    15gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 216wg = (nl / n) * gl + (nr / n) * gr17if wg < best_wg:
    values this step0.25wg

  17. if wg < best_wg:

    16wg = (nl / n) * gl + (nr / n) * gr17if wg < best_wg:18    best_wg = wg

  18. best_wg ← 0.25

    17if wg < best_wg:18    best_wg = wg19    best_t = t
    values this step1.0 → 0.25best_wg

  19. best_t ← 2.5

    18        best_wg = wg19        best_t = t20print('RESULT:', best_t)
    values this stepNone → 2.5best_t

  20. t ← 4.0

    6best_wg = 1.07for t in thresholds:8    left_y  = [y[i] for i in range(n) if X[i] <  t]
    values this step2.5 → 4.0t

  21. left_y ← [0, 0, 0]

    7for t in thresholds:8    left_y  = [y[i] for i in range(n) if X[i] <  t]9    right_y = [y[i] for i in range(n) if X[i] >= t]
    values this step[0, 0] → [0, 0, 0]left_y

  22. right_y ← [1, 1, 1]

    8left_y  = [y[i] for i in range(n) if X[i] <  t]9right_y = [y[i] for i in range(n) if X[i] >= t]10nl = len(left_y)
    values this step[0, 1, 1, 1] → [1, 1, 1]right_y

  23. nl ← 3

    9right_y = [y[i] for i in range(n) if X[i] >= t]10nl = len(left_y)11nr = len(right_y)
    values this step2 → 3nl

  24. nr ← 3

    10nl = len(left_y)11nr = len(right_y)12c0l = left_y.count(0)
    values this step4 → 3nr

  25. c0l ← 3

    11nr = len(right_y)12c0l = left_y.count(0)13gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 2
    values this step2 → 3c0l

  26. gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 2

    12c0l = left_y.count(0)13gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 214c0r = right_y.count(0)

  27. c0r ← 0

    13gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 214c0r = right_y.count(0)15gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 2
    values this step1 → 0c0r

  28. gr ← 0.0

    14c0r = right_y.count(0)15gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 216wg = (nl / n) * gl + (nr / n) * gr
    values this step0.375 → 0.0gr

  29. wg ← 0.0

    15gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 216wg = (nl / n) * gl + (nr / n) * gr17if wg < best_wg:
    values this step0.25 → 0.0wg

  30. if wg < best_wg:

    16wg = (nl / n) * gl + (nr / n) * gr17if wg < best_wg:18    best_wg = wg

  31. best_wg ← 0.0

    17if wg < best_wg:18    best_wg = wg19    best_t = t
    values this step0.25 → 0.0best_wg

  32. best_t ← 4.0

    18        best_wg = wg19        best_t = t20print('RESULT:', best_t)
    values this step2.5 → 4.0best_t

  33. t ← 6.0

    6best_wg = 1.07for t in thresholds:8    left_y  = [y[i] for i in range(n) if X[i] <  t]
    values this step4.0 → 6.0t

  34. left_y ← [0, 0, 0, 1]

    7for t in thresholds:8    left_y  = [y[i] for i in range(n) if X[i] <  t]9    right_y = [y[i] for i in range(n) if X[i] >= t]
    values this step[0, 0, 0] → [0, 0, 0, 1]left_y

  35. right_y ← [1, 1]

    8left_y  = [y[i] for i in range(n) if X[i] <  t]9right_y = [y[i] for i in range(n) if X[i] >= t]10nl = len(left_y)
    values this step[1, 1, 1] → [1, 1]right_y

  36. nl ← 4

    9right_y = [y[i] for i in range(n) if X[i] >= t]10nl = len(left_y)11nr = len(right_y)
    values this step3 → 4nl

  37. nr ← 2

    10nl = len(left_y)11nr = len(right_y)12c0l = left_y.count(0)
    values this step3 → 2nr

  38. c0l = left_y.count(0)

    11nr = len(right_y)12c0l = left_y.count(0)13gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 2

  39. gl ← 0.375

    12c0l = left_y.count(0)13gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 214c0r = right_y.count(0)
    values this step0.0 → 0.375gl

  40. c0r = right_y.count(0)

    13gl = 1 - (c0l / nl) ** 2 - ((nl - c0l) / nl) ** 214c0r = right_y.count(0)15gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 2

  41. gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 2

    14c0r = right_y.count(0)15gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 216wg = (nl / n) * gl + (nr / n) * gr

  42. wg ← 0.25

    15gr = 1 - (c0r / nr) ** 2 - ((nr - c0r) / nr) ** 216wg = (nl / n) * gl + (nr / n) * gr17if wg < best_wg:
    values this step0.0 → 0.25wg

  43. if wg < best_wg:

    16wg = (nl / n) * gl + (nr / n) * gr17if wg < best_wg:18    best_wg = wg

  44. for t in thresholds:

    6best_wg = 1.07for t in thresholds:8    left_y  = [y[i] for i in range(n) if X[i] <  t]

  45. stdout ← RESULT: 4.0

    19        best_t = t20print('RESULT:', best_t)
    values this stepRESULT: 4.0stdout

With scikit-learn

DecisionTreeClassifier(max_depth=1) fits a single split and stores the chosen threshold in clf.tree_.threshold[0].

library.py 
from sklearn.tree import DecisionTreeClassifier
from dalib.display import set_display
set_display()

X = [[1], [2], [3], [5], [7], [8]]
y = [0, 0, 0, 1, 1, 1]
clf = DecisionTreeClassifier(max_depth=1, random_state=0)
clf.fit(X, y)
threshold = round(float(clf.tree_.threshold[0]), 4)
print('sklearn threshold:', threshold)
print('RESULT:', threshold)

sklearn threshold: 4.0
RESULT: 4.0

Implementation notes

  • sklearn's split condition is feature ≤ threshold (left), > threshold (right). The naive uses strict < — equivalent here because no training sample equals 4.0 (the midpoint (3+5)/2=4.0 lies between feature values).
  • Candidate thresholds are midpoints between adjacent sorted feature values. Three candidates [2.5, 4.0, 6.0] cover the informative region; symmetric outer candidates give higher impurity and are omitted.
  • Weighted Gini = (n_left/n)·Gini_left + (n_right/n)·Gini_right. At t=4.0 both children are pure (Gini=0) so weighted Gini=0 — the global minimum.
  • Cross-reference: gini-impurity (this chapter) for the per-node formula; decision-stump-predict (this chapter) applies the found threshold.