{"course":{"slug":"machine-learning-foundations","title":"Machine Learning, Foundations","url":"https://addaly.com/learn/machine-learning-foundations","level":"intermediate","track":"start"},"lesson":{"slug":"how-a-tree-chooses-a-split","title":"How a tree chooses where to cut","url":"https://addaly.com/learn/machine-learning-foundations/how-a-tree-chooses-a-split","position":54,"of":92,"minutes":9,"answer":"A tree scores every candidate threshold by the weighted drop in impurity and takes the best one greedily.","keyIdea":"A tree scores every candidate threshold by the weighted drop in impurity and takes the best one greedily, which gives it interactions for free but leaves it unable to express a diagonal boundary or extrapolate beyond the training range."},"body":{"format":"markdown","text":"## Twenty loans\n\nTwenty applications, six of which defaulted. The tree has to pick one feature and one threshold to split on. How does it decide?\n\nIt tries every threshold on every feature and scores each one by how much purer the two resulting groups are than the parent.\n\n## Impurity, measured\n\n**Gini impurity** for a node is `1 - sum of p_k^2` over the classes. It is the probability that two items drawn at random from the node have different labels.\n\nThe parent: 6 defaults in 20, so p = 0.3.\n\n```text\nGini(parent) = 1 - (0.3^2 + 0.7^2) = 1 - (0.09 + 0.49) = 0.42\n```\n\nNow try the split `income < 300000`. It sends 8 rows left, of which 5 defaulted, and 12 right, of which 1 defaulted.\n\n```text\nGini(left)  = 1 - (0.625^2 + 0.375^2) = 0.469\nGini(right) = 1 - (0.083^2 + 0.917^2) = 0.153\nweighted    = (8/20)*0.469 + (12/20)*0.153 = 0.188 + 0.092 = 0.280\ngain        = 0.42 - 0.280 = 0.14\n```\n\nTry `age < 30`: 9 left with 3 defaults, 11 right with 3 defaults.\n\n```text\nGini(left)  = 1 - (0.333^2 + 0.667^2) = 0.444\nGini(right) = 1 - (0.273^2 + 0.727^2) = 0.397\nweighted    = 0.45*0.444 + 0.55*0.397 = 0.418\ngain        = 0.42 - 0.418 = 0.002\n```\n\nIncome wins, decisively. The tree takes it, then repeats the whole procedure inside each child.\n\nThat is the entire algorithm. Try everything, take the best local gain, recurse. It is greedy (it never reconsiders an earlier split in light of a later one) which means a tree can miss a combination that a two-step lookahead would have found. Nobody does the lookahead, because it is exponentially expensive and the greedy version works well enough.\n\n## Entropy, and whether it matters\n\nThe alternative impurity measure is entropy, `-sum of p_k * log2(p_k)`, borrowed from information theory. The gain is then called information gain.\n\nIn practice the two produce nearly identical trees. Entropy is slightly more expensive because of the logarithm, and its differences from Gini show up mainly in how they treat very unbalanced nodes. Gini is the default in scikit-learn, and the choice is not worth an experiment.\n\nFor regression the criterion is different: minimise the variance within each child, which is the same as minimising squared error. Each leaf predicts the mean of its training rows.\n\n## What a tree can and cannot represent\n\nWorth being concrete, because it explains most of the algorithm's behaviour.\n\n**Can:** any axis-aligned region. Interactions of any order, for free: split on income, then on age inside that branch, and you have expressed \"young people with low income\" without anyone specifying an interaction term. Non-monotonic relationships. Missing values as their own branch.\n\n**Cannot, without difficulty:** a diagonal boundary. If the true rule is `income > 3 * expenses`, a tree approximates it with a staircase and needs many splits to do badly what one ratio does exactly. This is why the engineered-ratio advice in module 3 helps trees too.\n\n**Cannot, at all:** extrapolate. Every prediction is a leaf mean computed from training rows, so a tree's output is bounded by the range of the training targets. Ask a tree trained on houses up to 130 square metres about a 400 square metre house and it returns the mean of its rightmost leaf. That is arguably safer than a linear model's confident extrapolation, and it is definitely different: know which failure mode you prefer.\n\n## A single tree overfits, spectacularly\n\nGrown without limits, a tree keeps splitting until every leaf is pure, which usually means one training row per leaf. Training accuracy 100%, validation accuracy poor, and the tree is a lookup table.\n\nThe controls:\n\n```python\nDecisionTreeClassifier(\n    max_depth=5,             # hard cap on levels\n    min_samples_leaf=20,     # the most useful one\n    min_samples_split=50,\n    max_features=\"sqrt\",     # consider a subset at each split\n    ccp_alpha=0.01,          # cost-complexity pruning\n)\n```\n\n`min_samples_leaf` is the one to reach for first. It directly says \"do not make a claim based on fewer than 20 examples\", which is the honest version of what you want.\n\n## Why a single tree is rarely the answer\n\nThe fatal property is instability. Change 5% of the training rows and the top split may change, which changes every split beneath it, and you get a structurally different tree. Two trees fitted on 95% overlapping data can look nothing alike.\n\nThat is high variance in the module 4 sense, and it has a direct remedy: fit many trees and average them. Which is the next lesson, and the reason single trees are used today mostly for explanation rather than prediction: a depth-3 tree that a manager can read is worth something even when a forest predicts better."},"check":{"question":"A regression tree trained on house sizes from 50 to 130 square metres is asked to price a 400 square metre house. What does it return, and why?","options":[{"text":"The mean target of its rightmost leaf, because every prediction is a leaf average computed from training rows and no leaf covers sizes above 130.","correct":true},{"text":"An extrapolated value following the slope implied by its deepest splits.","correct":false,"tempting":"Attributes a slope to a tree; trees produce piecewise-constant outputs and hold no notion of a trend to continue."},{"text":"An error, since the input falls outside the range of every split threshold.","correct":false,"tempting":"Out-of-range inputs route down the appropriate branch without difficulty; no error is raised."},{"text":"The overall training mean, because the input matches no leaf's conditions.","correct":false,"tempting":"Every input reaches exactly one leaf by following the splits, so the global mean is never what comes back."}]},"prev":{"slug":"the-classic-algorithms","title":"The classic algorithms, and when each is right","url":"https://addaly.com/learn/machine-learning-foundations/the-classic-algorithms"},"next":{"slug":"from-one-tree-to-a-forest","title":"Bagging: many unstable models, averaged","url":"https://addaly.com/learn/machine-learning-foundations/from-one-tree-to-a-forest"},"authorship":"Founder and series editor: Dr Mustafa Mun. Written by AI models to a written standard. Exam keys checked blind by a second model: 3,665 of 3,666 agreed. Academic review invited.","review":{"status":"Draft, open for academic review"},"cite":"Addaly (2026) 'How a tree chooses where to cut', in Machine Learning, Foundations. Edited by M. Mun. Addaly. Available at: https://addaly.com/learn/machine-learning-foundations/how-a-tree-chooses-a-split (Accessed: 13 October 2026).","licence":{"name":"CC BY-NC-SA 4.0","url":"https://creativecommons.org/licenses/by-nc-sa/4.0/"},"reader":{"schema":1,"title":"How a tree chooses where to cut","courseTitle":"Machine Learning, Foundations","module":{"index":6,"slug":"trees-and-ensembles","title":"Trees, ensembles, and the algorithms that win on tables"},"answer":null,"keyIdea":"A tree scores every candidate threshold by the weighted drop in impurity and takes the best one greedily, which gives it interactions for free but leaves it unable to express a diagonal boundary or extrapolate beyond the training range.","hero":{"kind":"plate","image":null,"alt":null,"caption":null},"blocks":[{"t":"h2","id":"twenty-loans","runs":[{"text":"Twenty loans"}]},{"t":"p","runs":[{"text":"Twenty applications, six of which defaulted. The tree has to pick one feature and one threshold to split on. How does it decide?"}]},{"t":"p","runs":[{"text":"It tries every threshold on every feature and scores each one by how much purer the two resulting groups are than the parent."}]},{"t":"h2","id":"impurity-measured","runs":[{"text":"Impurity, measured"}]},{"t":"p","runs":[{"text":"Gini impurity","b":true},{"text":" for a node is "},{"text":"1 - sum of p_k^2","code":true},{"text":" over the classes. It is the probability that two items drawn at random from the node have different labels."}]},{"t":"p","runs":[{"text":"The parent: 6 defaults in 20, so p = 0.3."}]},{"t":"code","lang":"text","label":"Text","text":"Gini(parent) = 1 - (0.3^2 + 0.7^2) = 1 - (0.09 + 0.49) = 0.42"},{"t":"p","runs":[{"text":"Now try the split "},{"text":"income < 300000","code":true},{"text":". It sends 8 rows left, of which 5 defaulted, and 12 right, of which 1 defaulted."}]},{"t":"code","lang":"text","label":"Text","text":"Gini(left)  = 1 - (0.625^2 + 0.375^2) = 0.469\nGini(right) = 1 - (0.083^2 + 0.917^2) = 0.153\nweighted    = (8/20)*0.469 + (12/20)*0.153 = 0.188 + 0.092 = 0.280\ngain        = 0.42 - 0.280 = 0.14"},{"t":"p","runs":[{"text":"Try "},{"text":"age < 30","code":true},{"text":": 9 left with 3 defaults, 11 right with 3 defaults."}]},{"t":"code","lang":"text","label":"Text","text":"Gini(left)  = 1 - (0.333^2 + 0.667^2) = 0.444\nGini(right) = 1 - (0.273^2 + 0.727^2) = 0.397\nweighted    = 0.45*0.444 + 0.55*0.397 = 0.418\ngain        = 0.42 - 0.418 = 0.002"},{"t":"p","runs":[{"text":"Income wins, decisively. The tree takes it, then repeats the whole procedure inside each child."}]},{"t":"p","runs":[{"text":"That is the entire algorithm. Try everything, take the best local gain, recurse. It is greedy (it never reconsiders an earlier split in light of a later one) which means a tree can miss a combination that a two-step lookahead would have found. Nobody does the lookahead, because it is exponentially expensive and the greedy version works well enough."}]},{"t":"h2","id":"entropy-and-whether-it-matters","runs":[{"text":"Entropy, and whether it matters"}]},{"t":"p","runs":[{"text":"The alternative impurity measure is entropy, "},{"text":"-sum of p_k * log2(p_k)","code":true},{"text":", borrowed from information theory. The gain is then called information gain."}]},{"t":"p","runs":[{"text":"In practice the two produce nearly identical trees. Entropy is slightly more expensive because of the logarithm, and its differences from Gini show up mainly in how they treat very unbalanced nodes. Gini is the default in scikit-learn, and the choice is not worth an experiment."}]},{"t":"p","runs":[{"text":"For regression the criterion is different: minimise the variance within each child, which is the same as minimising squared error. Each leaf predicts the mean of its training rows."}]},{"t":"h2","id":"what-a-tree-can-and-cannot-represent","runs":[{"text":"What a tree can and cannot represent"}]},{"t":"p","runs":[{"text":"Worth being concrete, because it explains most of the algorithm’s behaviour."}]},{"t":"p","runs":[{"text":"Can:","b":true},{"text":" any axis-aligned region. Interactions of any order, for free: split on income, then on age inside that branch, and you have expressed “young people with low income” without anyone specifying an interaction term. Non-monotonic relationships. Missing values as their own branch."}]},{"t":"p","runs":[{"text":"Cannot, without difficulty:","b":true},{"text":" a diagonal boundary. If the true rule is "},{"text":"income > 3 * expenses","code":true},{"text":", a tree approximates it with a staircase and needs many splits to do badly what one ratio does exactly. This is why the engineered-ratio advice in module 3 helps trees too."}]},{"t":"p","runs":[{"text":"Cannot, at all:","b":true},{"text":" extrapolate. Every prediction is a leaf mean computed from training rows, so a tree’s output is bounded by the range of the training targets. Ask a tree trained on houses up to 130 square metres about a 400 square metre house and it returns the mean of its rightmost leaf. That is arguably safer than a linear model’s confident extrapolation, and it is definitely different: know which failure mode you prefer."}]},{"t":"h2","id":"a-single-tree-overfits-spectacularly","runs":[{"text":"A single tree overfits, spectacularly"}]},{"t":"p","runs":[{"text":"Grown without limits, a tree keeps splitting until every leaf is pure, which usually means one training row per leaf. Training accuracy 100%, validation accuracy poor, and the tree is a lookup table."}]},{"t":"p","runs":[{"text":"The controls:"}]},{"t":"code","lang":"python","label":"Python","text":"DecisionTreeClassifier(\n    max_depth=5,             # hard cap on levels\n    min_samples_leaf=20,     # the most useful one\n    min_samples_split=50,\n    max_features=\"sqrt\",     # consider a subset at each split\n    ccp_alpha=0.01,          # cost-complexity pruning\n)"},{"t":"p","runs":[{"text":"min_samples_leaf","code":true},{"text":" is the one to reach for first. It directly says “do not make a claim based on fewer than 20 examples”, which is the honest version of what you want."}]},{"t":"h2","id":"why-a-single-tree-is-rarely-the-answer","runs":[{"text":"Why a single tree is rarely the answer"}]},{"t":"p","runs":[{"text":"The fatal property is instability. Change 5% of the training rows and the top split may change, which changes every split beneath it, and you get a structurally different tree. Two trees fitted on 95% overlapping data can look nothing alike."}]},{"t":"p","runs":[{"text":"That is high variance in the module 4 sense, and it has a direct remedy: fit many trees and average them. Which is the next lesson, and the reason single trees are used today mostly for explanation rather than prediction: a depth-3 tree that a manager can read is worth something even when a forest predicts better."}]}],"check":{"question":[{"text":"A regression tree trained on house sizes from 50 to 130 square metres is asked to price a 400 square metre house. What does it return, and why?"}],"options":[{"text":[{"text":"The mean target of its rightmost leaf, because every prediction is a leaf average computed from training rows and no leaf covers sizes above 130."}],"correct":true,"tempting":null},{"text":[{"text":"An extrapolated value following the slope implied by its deepest splits."}],"correct":false,"tempting":[{"text":"Attributes a slope to a tree; trees produce piecewise-constant outputs and hold no notion of a trend to continue."}]},{"text":[{"text":"An error, since the input falls outside the range of every split threshold."}],"correct":false,"tempting":[{"text":"Out-of-range inputs route down the appropriate branch without difficulty; no error is raised."}]},{"text":[{"text":"The overall training mean, because the input matches no leaf’s conditions."}],"correct":false,"tempting":[{"text":"Every input reaches exactly one leaf by following the splits, so the global mean is never what comes back."}]}],"order":[3,1,0,2],"why":null},"prev":{"slug":"the-classic-algorithms","title":"The classic algorithms, and when each is right","minutes":10},"next":{"slug":"from-one-tree-to-a-forest","title":"Bagging: many unstable models, averaged","minutes":9}}}