--- title: 'Decision Trees' source: 'https://academia.sh/en/courses/supervised-learning/decision-trees' course: 'Supervised Learning' language: en updated: '2026-10-21T05:03:31+00:00' license: 'CC BY-SA 4.0' objectives: - 'Counts which split the three split criteria choose on the same set and on how many splits the trees diverge' - 'Measures how pruning differs from a depth limit through the number of leaves, the depth of the leaves and the held-out numbers' - 'Counts how sensitive a single tree is to small changes in the training set through the root split and the test number' --- # Decision Trees Measuring the split chosen by the split criterion and how pruning differs from a depth limit: impurity and entropy choose the same root split but agree on only eighteen of forty-seven splits, while the misclassification rate chooses an entirely different 695/61 split. The unpruned depth-12 tree with 127 leaves gives 0.7341 on the test set, below the baseline; pruning brings the same tree down to 20 leaves and up to 0.7857. The depth limit gives 0.7897 with 48 leaves while pruning gives 0.7857 with 11 leaves, and four of those are deeper than the sixth level. The trees of eight 90% subsamples share not a single split. 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. ```python # 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. ```python 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. ```python 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.