Decision Trees

Decision trees are among the most intuitive machine learning models ever devised. A trained decision tree reads like a flowchart: ask a question about a feature, follow one branch or another based on the answer, ask another question, and eventually arrive at a prediction. A doctor diagnosing a condition by ruling out possibilities one at a time is roughly following a decision tree. That intuitive structure is both the algorithm's greatest strength and the source of its principal weakness.

Structure and Mechanics

A decision tree is a hierarchical model consisting of: - A root node: the starting point, representing the entire training set. - Internal nodes: each applies a test to one feature. For numerical features the test is of the form 'xⱼ ≤ threshold.' For categorical features it might be 'xⱼ ∈ {value_a, value_b}.' - Branches: the possible outcomes of each test. - Leaf nodes: the terminal nodes that output a prediction — a class label for classification, a numerical value for regression. A concrete worked example — classifying whether a mushroom is edible: Root: Is the cap color red? Yes → Leaf: Poisonous (prediction based on training data majority) No → Internal: Does it have an unpleasant odor? Yes → Leaf: Poisonous No → Leaf: Edible This three-node tree (one root, one internal, three leaves) represents the learned rule. Given a new mushroom — blue cap, no unpleasant odor — we follow: Is cap red? No. Unpleasant odor? No. Prediction: Edible. For numerical predictions (regression trees), leaf nodes output the mean of the training examples that reach that leaf, rather than a class label.

How does a tree decide where to split? It uses an impurity measure to quantify how mixed the classes are at each node, then chooses the split that reduces impurity the most. Gini impurity for a node with K classes: Gini = 1 - Σ pₖ² where pₖ is the fraction of examples in the node belonging to class k. A pure node (all one class) has Gini = 0. A maximally mixed two-class node (50/50) has Gini = 0.5. Information gain (entropy-based): uses entropy H = -Σ pₖ log₂(pₖ). A split is chosen to maximize the decrease in entropy. A worked example with Gini: Suppose a node contains 10 examples: 7 edible, 3 poisonous. p_edible = 0.7, p_poisonous = 0.3 Gini = 1 - (0.7² + 0.3²) = 1 - (0.49 + 0.09) = 1 - 0.58 = 0.42 After splitting on 'has ring on stem,' suppose one child has 6 edible / 0 poisonous (pure, Gini=0) and the other has 1 edible / 3 poisonous (Gini = 1-(0.25²+0.75²) = 1-0.625 = 0.375). The weighted average Gini after the split is: (6/10)(0) + (4/10)(0.375) = 0 + 0.15 = 0.15 Gini improvement = 0.42 - 0.15 = 0.27. This is the information gain of that split.

Strengths, Weaknesses, and the Overfitting Problem

Decision trees are non-parametric — they do not assume a fixed functional form for the relationship between features and target. This makes them highly flexible and capable of capturing complex, nonlinear relationships. They handle both numerical and categorical features without preprocessing, require no feature scaling, and naturally perform feature selection — splits on uninformative features are simply never chosen. Their weaknesses are equally significant: High variance: small changes in training data can produce a completely different tree structure. Two models trained on slightly different samples of the same population may arrive at opposite splitting strategies. Axis-aligned boundaries: every split is perpendicular to one feature axis. A diagonal boundary in the feature space requires many splits to approximate, making trees inefficient for that geometry. Instability: a single noisy training example near a boundary can change the root split, cascading into an entirely different tree. These weaknesses motivate ensemble methods — the insight that combining many imperfect trees produces a far more robust model. That is the topic of Lesson 7.