Decision Trees

The previous three families used the columns together: the sum of distances, the product of probabilities and the inner product all brought all twelve columns into every decision. The decision tree does the opposite; at each step it chooses a single column and a single threshold, splits the set in two and repeats the same work on the two parts.

The tree itself is not new in this curriculum: a tree with a fixed depth of 6 was used throughout the Introduction to Machine Learning and Data Preparation and Feature Engineering courses, and the divergence of the two numbers as capacity grows and the effect of the leaf minimum were measured in the generalization topic of the Introduction to Machine Learning course. Those measurements are not repeated here. Two things have not been asked: which criterion chooses the split, and what pruning a grown tree takes back, instead of limiting the depth in advance.

• NM24. The set, the split and the baseline do not change: a fictional table of 1,260 subscribers, seed 20260218, split 756/252/252, baseline 0.7579 on the test set and 0.8135 on validation. The feature set is the twelve columns that come from the Data Preparation and Feature Engineering course. Since the tree looks at the ordering, no scaling is applied; the Data Preparation and Feature Engineering course measured the contribution of that step to the tree to be exactly zero.
• NM25. The split criterion is the function that measures how much a split gains. Three are compared: impurity, entropy and the misclassification rate. The gain is the value before the split minus the value of the two parts weighted by their row counts.
• NM26. At most ten candidate thresholds are tried for each column and at least two rows stay in each leaf. The depth sweep, the learning curve and the leaf minimum were measured in the Introduction to Machine Learning course and are not repeated; the depth 6 here is the constant from that course and the depth 12 is the equivalent of “let it grow without limit”.
• NM27. Pruning is turning a node of the grown tree into a leaf. The decision is read from the validation set: a node is turned into a leaf if, once turned, its error on the validation set does not increase. The pruning threshold is how much of an increase in error is tolerated and is the tuning variable.
• NM28. The number of leaves and the depth of the leaves are the size measures of the tree; the two are printed separately.
• NM29. The choice is read from the validation set; in a tie the tree with fewer leaves is chosen.
• NM30. In the fragility measurement, 90% of the training set is drawn eight times with separate seeds; the validation and test sets do not change.

What the Split Criterion Chooses

The setup generates the set, writes the three criteria and prints the root split and the depth 6 trees.

# tree.py — MODEL: the FICTIONAL subscriber table of the Introduction to Machine Learning course is rebuilt with the same seed;
# the feature set comes from the Data Preparation and Feature Engineering course and is fixed throughout the course.
import math



SEED, RAW, M32 = 20260218, 1400, 0xFFFFFFFF
REGION = [("north", 0.28, 21, 0.00), ("south", 0.22, 17, -0.10),
          ("east", 0.18, 26, 0.30), ("west", 0.14, 14, -0.05),
          ("central", 0.18, 23, 0.05)]


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


def pick(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


SUBSCRIBERS, DATA = [], []
for i in range(RAW):
    r = rng(SEED + i)
    b = REGION[pick(r(), [x[1] for x in REGION])]
    household = 1 + pick(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05])
    rating = 1 + pick(r(), [0.08, 0.14, 0.27, 0.34, 0.17])
    if r() >= 0.046:
        SUBSCRIBERS.append({"id": 10001 + i, "region": b, "household": household,
                            "satisfaction": rating})
for k in SUBSCRIBERS:
    r, v = rng(SEED + 7000 + k["id"]), []
    for n in range(pick(r(), [0.05, 0.12, 0.21, 0.62])):
        v.append(0.0 if r() < 0.038 else math.floor(
            k["region"][2] * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - n * 0.05) * 100 + 0.5) / 100)
        r()
    if not v:
        continue
    mean, vol, r = sum(v) / len(v), max(v) - min(v), rng(SEED + 51000 + k["id"])
    z = (0.052 * (mean - 20) + 0.85 * (min(v) == 0.0) + 0.026 * vol
         + 0.24 * (k["household"] >= 5) - 0.20 * (k["satisfaction"] >= 4) + k["region"][3]
         + 0.9 * (k["id"] - 10001) / 1399 + (r() + r() + r() - 1.5) * 1.30)
    x = {"household": k["household"], "satisfaction": k["satisfaction"],
         "period": len(v), "mean_consumption": round(mean, 2), "volatility": round(vol, 2),
         "zero_readings": int(min(v) == 0.0), "suspicious": int(z > 1.35)}
    for b in REGION:
        x["area_" + b[0]] = int(k["region"][0] == b[0])
    x["per_person"] = round(x["mean_consumption"] / x["household"], 3)
    DATA.append(x)


FIELDS = ["mean_consumption", "volatility", "household", "satisfaction", "period", "per_person",
          "zero_readings", "area_north", "area_south", "area_east", "area_west", "area_central"]


def shuffle(data, seed):
    r, s = rng(seed), list(range(len(data)))
    for i in range(len(s) - 1, 0, -1):
        j = int(r() * (i + 1))
        s[i], s[j] = s[j], s[i]
    return [data[i] for i in s]


K = shuffle(DATA, SEED + 90000)
TRAIN, VAL, TEST = K[:756], K[756:1008], K[1008:]
BASELINE_TEST = sum(x["suspicious"] == 0 for x in TEST) / len(TEST)


def share(s):
    return sum(x["suspicious"] for x in s) / len(s) if s else 0.0


def impurity(s):
    p = share(s)
    return 2 * p * (1 - p)


def entropy(s):
    p = share(s)
    return 0.0 if p <= 0.0 or p >= 1.0 else -(p * math.log2(p) + (1 - p) * math.log2(1 - p))


def misclass_rate(s):                       # misclassification rate
    p = share(s)
    return min(p, 1 - p)


CRITERIA = [("impurity", impurity), ("entropy", entropy),
            ("misclass rate", misclass_rate)]


def best_split(s, f, least=2):
    best = None
    for a in FIELDS:
        d = sorted({x[a] for x in s})
        for v in (d[1:] if len(d) < 10 else [d[int(i * len(d) / 10)] for i in range(1, 10)]):
            left = [x for x in s if x[a] < v]
            right = [x for x in s if x[a] >= v]
            if min(len(left), len(right)) < least:
                continue
            k = f(s) - (len(left) * f(left) + len(right) * f(right)) / len(s)
            if best is None or k > best[0]:
                best = (k, a, v, left, right)
    return best


def tree(s, depth, f, least=2):             # MODEL: decision tree
    p, pos = share(s), sum(x["suspicious"] for x in s)
    best = best_split(s, f, least) if depth and len(s) >= 2 * least and 0.0 < p < 1.0 else None
    if best is None or best[0] <= 1e-9:
        return {"prediction": int(p > 0.5), "n": len(s), "pos": pos}
    return {"field": best[1], "threshold": best[2], "n": len(s), "pos": pos,
            "left": tree(best[3], depth - 1, f, least),
            "right": tree(best[4], depth - 1, f, least)}


def predict(d, x):
    while "prediction" not in d:
        d = d["left"] if x[d["field"]] < d["threshold"] else d["right"]
    return d["prediction"]


def accuracy(d, s):
    return sum(predict(d, x) == x["suspicious"] for x in s) / len(s)


def splits(d, path=()):                     # (position, column, threshold) triples
    if "prediction" in d:
        return []
    return ([(path, d["field"], round(d["threshold"], 3))]
            + splits(d["left"], path + ("l",)) + splits(d["right"], path + ("r",)))


print(f"baseline on test {BASELINE_TEST:.4f}; training {len(TRAIN)} rows")
print(f"{'criterion':<14}{'root column':>11}{'threshold':>10}{'gain':>9}{'left/right':>12}")
for name, f in CRITERIA:
    best = best_split(TRAIN, f)
    print(f"{name:<14}{best[1]:>11}{best[2]:>10.2f}{best[0]:>9.5f}"
          f"{str(len(best[3])) + '/' + str(len(best[4])):>12}")
TREE6 = {}
print(f"\n{'criterion (depth 6)':<20}{'leaves':>7}{'validation':>11}{'test':>8}")
for name, f in CRITERIA:
    TREE6[name] = tree(TRAIN, 6, f)
    print(f"{name:<20}{len(splits(TREE6[name])) + 1:>7}"
          f"{accuracy(TREE6[name], VAL):>11.4f}{accuracy(TREE6[name], TEST):>8.4f}")
B = {name: set(splits(t)) for name, t in TREE6.items()}
print(f"common splits of the impurity and entropy trees "
      f"{len(B['impurity'] & B['entropy'])}, "
      f"common splits with misclassification rate {len(B['impurity'] & B['misclass rate'])}")

baseline on test 0.7579; training 756 rows
criterion     root column threshold     gain  left/right
impurity       volatility     11.69  0.03923     511/245
entropy        volatility     11.69  0.07761     511/245
misclass rate  volatility     23.15  0.01984      695/61

criterion (depth 6)  leaves validation    test
impurity                 48     0.8016  0.7897
entropy                  38     0.7778  0.7897
misclass rate             8     0.7937  0.7698
common splits of the impurity and entropy trees 18, common splits with misclassification rate 0

Impurity and entropy agree on the root split: both choose the volatility column and the threshold 11.69 and divide the set 511/245. The gain numbers differ — 0.03923 and 0.07761 — because the two criteria do not measure the same magnitude; the split they choose is the same. The misclassification rate, on the same set, chooses an entirely different 695/61 split.

The difference comes from the shape of the criterion. The misclassification rate is a function of the class share made of linear pieces: if the majority class of both parts stays the same, the gain is exactly zero, however much the split purifies the parts. Impurity and entropy are strictly concave and reward purification even when the majority class does not change. This is why the misclassification rate criterion sees only the splits that flip a majority and stops the tree at eight leaves; its test number also stays at 0.7698, below the 0.7897 of the others.

The same root does not mean the same tree. The impurity tree carries forty-seven splits, the entropy tree thirty-seven, and only eighteen of them are shared as both column and threshold. Even when the criteria do not diverge at the root split, they diverge in the lower floors of the tree; while the two trees give the same number on the test set, they ask different questions.

How Pruning Differs from a Depth Limit

A depth limit cuts the tree at the same level in every branch. Pruning first lets the tree go free and then takes back only the branches that do not pay; whether they pay is measured on the held-out set.

def error(d, s, as_leaf):
    if as_leaf:
        t = int(d["pos"] / d["n"] > 0.5)
        return sum(1 for x in s if x["suspicious"] != t)
    return sum(1 for x in s if predict(d, x) != x["suspicious"])


def prune(d, s, threshold, n):              # pruning read from the held-out set
    if "prediction" in d:
        return d
    d = dict(d, left=prune(d["left"], [x for x in s if x[d["field"]] < d["threshold"]], threshold, n),
             right=prune(d["right"], [x for x in s if x[d["field"]] >= d["threshold"]], threshold, n))
    if error(d, s, True) <= error(d, s, False) + threshold * n:
        return {"prediction": int(d["pos"] / d["n"] > 0.5), "n": d["n"], "pos": d["pos"]}
    return d


def leaf_depths(d, k=0):
    if "prediction" in d:
        return [k]
    return leaf_depths(d["left"], k + 1) + leaf_depths(d["right"], k + 1)


PRUNED, THRESHOLDS = {}, (0.0, 0.004, 0.012)
print(f"{'criterion':<14}{'pruning':>8}{'leaves':>8}{'depth':>9}{'validation':>11}{'test':>8}")
for name, f in CRITERIA:
    grown = tree(TRAIN, 12, f)
    ld = leaf_depths(grown)
    print(f"{name:<14}{'none':>8}{len(ld):>8}{max(ld):>9}"
          f"{accuracy(grown, VAL):>11.4f}{accuracy(grown, TEST):>8.4f}")
    for threshold in THRESHOLDS:
        b = prune(grown, VAL, threshold, len(VAL))
        ld = leaf_depths(b)
        PRUNED[(name, threshold)] = (accuracy(b, VAL), accuracy(b, TEST), len(ld), max(ld))
        print(f"{name:<14}{threshold:>8}{len(ld):>8}{max(ld):>9}"
              f"{PRUNED[(name, threshold)][0]:>11.4f}{PRUNED[(name, threshold)][1]:>8.4f}")
pick_ = max(PRUNED, key=lambda a: (PRUNED[a][0], PRUNED[a][2]))
print(f"\ncandidates tried {len(CRITERIA) + len(PRUNED)} (criterion {len(CRITERIA)} + pruning {len(PRUNED)})")
print(f"chosen on validation: {pick_[0]}, pruning threshold {pick_[1]} -> test "
      f"{PRUNED[pick_][1]:.4f}, {PRUNED[pick_][1] - BASELINE_TEST:+.4f} above the baseline")
b = prune(tree(TRAIN, 12, impurity), VAL, 0.004, len(VAL))
print(f"depth limit 6: {len(splits(TREE6['impurity'])) + 1} leaves, test "
      f"{accuracy(TREE6['impurity'], TEST):.4f}")
print(f"pruning threshold 0.004: {len(leaf_depths(b))} leaves, test "
      f"{accuracy(b, TEST):.4f}, leaves deeper than 6 "
      f"{sum(1 for k in leaf_depths(b) if k > 6)}")

criterion      pruning  leaves    depth validation    test
impurity          none     127       12     0.7619  0.7341
impurity           0.0      20        8     0.8413  0.7857
impurity         0.004      11        8     0.8294  0.7857
impurity         0.012       1        0     0.8135  0.7579
entropy           none     122       12     0.7381  0.7460
entropy            0.0      22       12     0.8373  0.7817
entropy          0.004       3        2     0.8214  0.7857
entropy          0.012       1        0     0.8135  0.7579
misclass rate     none       8        4     0.7937  0.7698
misclass rate      0.0       1        0     0.8135  0.7579
misclass rate    0.004       1        0     0.8135  0.7579
misclass rate    0.012       1        0     0.8135  0.7579

candidates tried 12 (criterion 3 + pruning 9)
chosen on validation: impurity, pruning threshold 0.0 -> test 0.7857, +0.0278 above the baseline
depth limit 6: 48 leaves, test 0.7897
pruning threshold 0.004: 11 leaves, test 0.7857, leaves deeper than 6 4

The unpruned tree is bad across the board: with 127 leaves it reads 0.7341 on the test set, that is, 0.0238 below the baseline. When the same tree is pruned it goes down to 20 leaves and up to 0.7857; the validation number goes from 0.7619 to 0.8413. The family number is 0.7857, it beats the baseline by 0.0278 and was found by trying 12 candidates.

The last three lines give how pruning differs from a depth limit. The depth 6 tree reads 0.7897 with 48 leaves, the pruned tree 0.7857 with 11 leaves: the difference in the number is one subscriber, the difference in leaves is more than fourfold. More important is that the pruned tree’s depth is 8 and four of its leaves are deeper than the sixth level. The depth limit would have cut those four leaves without looking at whether they pay; pruning kept them and threw away thirty-seven leaves elsewhere. What the two steps take back is not the same: one looks at the level, the other at the contribution.

The rows of the misclassification rate criterion say something separate: at all three pruning thresholds the tree goes down to a single leaf and the model falls to the baseline. Not one split of its eight-leaf tree pays for itself on the validation set.

How Sturdy a Single Tree’s Decision Is

The selected tree gave a number. How much of that number comes from the training set being exactly these 756 rows is measured separately.

def subsample(s, seed, share=0.9):          # 90% of the training set
    r, k = rng(seed), list(s)
    for i in range(len(k) - 1, 0, -1):
        j = int(r() * (i + 1))
        k[i], k[j] = k[j], k[i]
    return k[:int(len(k) * share)]


COMMON, NUMBERS = None, []
print(f"{'sample':>9}{'root split':>26}{'leaves':>8}{'test':>8}")
for i in range(8):
    sub = subsample(TRAIN, SEED + 820000 + i * 13)
    t = prune(tree(sub, 12, impurity), VAL, 0.004, len(VAL))
    best = best_split(sub, impurity)
    b = set(splits(t))
    COMMON = b if COMMON is None else COMMON & b
    NUMBERS.append(accuracy(t, TEST))
    print(f"{i + 1:>9}{best[1] + ' < ' + format(best[2], '.2f'):>26}"
          f"{len(leaf_depths(t)):>8}{NUMBERS[-1]:>8.4f}")
print(f"splits found in all eight trees (column and threshold together) {len(COMMON)}")
print(f"test numbers between {min(NUMBERS):.4f} and {max(NUMBERS):.4f}, "
      f"range {max(NUMBERS) - min(NUMBERS):.4f}")

   sample                root split  leaves    test
        1        volatility < 13.99       3  0.7897
        2        volatility < 13.88      10  0.7897
        3        volatility < 13.80      13  0.7817
        4        volatility < 14.12       3  0.7897
        5        volatility < 11.41       8  0.7817
        6        volatility < 13.60       5  0.7619
        7        volatility < 13.91       6  0.7897
        8        volatility < 14.12      10  0.7857
splits found in all eight trees (column and threshold together) 0
test numbers between 0.7619 and 0.7897, range 0.0278

The root column stays the same in all eight samples: volatility. The threshold wanders between 11.41 and 14.12 and the number of leaves varies between 3 and 13 — same procedure, same settings, only a tenth of the training set changed. The number of splits found in all eight trees is zero: taking the column and the threshold together, there is not a single common split.

The test numbers are between 0.7619 and 0.7897, a range of 0.0278. This number is equal to the whole of the family’s difference above the baseline. The measured difference can be erased entirely, depending on which 90% of the training set is drawn.

Summary

• Impurity and entropy choose the same root split (volatility, 11.69, 511/245); the misclassification rate chooses a different 695/61 split, because it gives exactly zero gain to splits that do not flip the majority.
• Two trees growing from the same root carry forty-seven and thirty-seven splits and agree on only eighteen of them.
• The unpruned depth-12 tree reads 0.7341 with 127 leaves, 0.0238 below the baseline; pruning takes the same tree down to 20 leaves and up to 0.7857.
• The family number is 0.7857, it beats the baseline by 0.0278 and was found by trying 12 candidates.
• Unlike a depth limit, pruning looks at the contribution: four leaves of the 11-leaf pruned tree are deeper than the sixth level and a depth limit would have cut them without measuring.
• The trees of eight 90% subsamples share not a single split; the test numbers wander within a range of 0.0278.

Next Step

A single tree was pruned, the number left over beat the baseline by 0.0278 and twelve candidates were tried. But the last table undermines this number: the same procedure chooses entirely different splits when a tenth of the training set is changed, and the number it gives wanders as much as the whole of the difference above the baseline. The decision of a single tree is fragile and fragility is not a defect of the tree but a consequence of its definition: a single threshold is chosen at each node, and if that threshold is separated from its nearest rival by only a few rows, the choice changes when a few rows change. The next lesson, instead of correcting this fragility as a defect, uses it: it runs the same procedure many times on different training samples and combines the decisions. What is to be measured is the held-out number settling and the variability falling as the number of trees grows.