DECISION TREE
A flowchart grown from data — ask the questions that separate classes fastest.
01 Overview
02 The Problem
A loan officer faces a stack of applications and must decide approve or reject each. The reasons are not a single number — credit score, income, debt ratio, employment length — and the rule people actually follow is a chain of if-then questions: “if income > $50k and debt ratio < 0.3, then approve.” The problem is learning that chain of splits from labelled examples, and being able to explain every decision.
03 Why It Matters
Trees mirror human decision-making: a readable set of binary questions ending in a verdict. They need no feature scaling, they ignore useless columns automatically, and a stakeholder can audit a single prediction by just following the path — the reason they anchor every credit-scorecard and medical checklist.
04 Intuition
Start with all applicants in one bucket. Ask the single question that splits them most cleanly — the one that separates approves from rejects most decisively. Then, inside each child bucket, ask the same question again, recursively, until buckets are pure (or nearly so). Each leaf is a verdict; each internal node is a test on one feature.
05 Mathematical Foundation
A split is good if it makes children purer than the parent. Purity is measured by entropy \(H=-p_+\log_2 p_+ - p_-\log_2 p_-\) — 0 when the bucket is all one class, 1 at a 50/50 toss. The quality of a split is its information gain: how much entropy it buys. A cheaper alternative is the Gini impurity \(G=1-p_+^2-p_-^2\), which picks almost the same split.
06 The Equation
- \(H(S)\) entropy of the parent set before the split
- \(S_v\) the subset reaching child \(v\) after testing \(A\)
- \(|S_v|/|S|\) fraction of rows sent down that branch
07 How It Learns
- For every candidate split (feature × threshold), measure how much purer the two children are.
- Keep the best — the split with the highest information gain (or lowest Gini).
- Recurse on each child until a stopping rule (depth, min samples, or purity) is met.
- Label the leaves by majority class.
08 Algorithm
09 Visual Explanation
A quick visual summary of how this model sees data and makes its prediction.
10 Worked Example
Parent 8 “yes”, 4 “no”: \(H=0.985\). Split on \(x_1\leq 32\): left \(3y,1n\) (\(H=0.811\)), right \(5y,3n\) (\(H=0.954\)). Gain = \(0.985-\tfrac{4}{12}0.811-\tfrac{8}{12}0.954=0.13\) bits. That is the feature chosen; recurse on each child. A path like \(x_1\leq32 \to x_2>50 \to\) leaf is exactly the “if-then” rule a loan officer can explain.