Decision tree
Topic of Classification trees, part of Statistical learning
Decision tree
| Type | Topic |
| Taught in | Classification trees |
| Part | Statistical learning |
| Questions using it | 3 |
A predictor that partitions the input space by a sequence of binary splits on single variables and predicts a constant in each final region: a class for a classification tree, a mean for a regression tree. It is grown greedily, one split at a time, and then pruned.
In Classification trees
From Classification trees
At a node, compare possible splits and choose one that makes the children purer according to a stated criterion. Repeat inside each child. This is a greedy search: a split is judged by its immediate improvement, not by every tree that could eventually grow beneath it. Stopping rules and pruning control the size. Contradictory labels at identical predictor values cannot be separated by further predictor-based splits.
After the tree is built, each training case is passed from the root along the branch its measurements select, until it reaches a leaf. The class proportions in that leaf are recorded, and the leaf is labelled with its majority class. A new x follows the same questions and receives the label of the leaf it reaches. The proportions in the leaf are a crude local estimate of the posterior \tau_g(x), constant on the rectangle the leaf owns. The Bayes rule would use the true posterior. The tree uses the majority in the rectangle that contains x.
The geometry is a partition of the predictor space by thresholds on single coordinates. The same partition reads as a nested list of rules. Four questions organise the rest of the page: which impurity a split should reduce, how the best split of a given variable is found, when splitting stops, and what a fitted tree can and cannot be trusted to mean.
Used in
- Taught in Classification trees
- Also used in Ensembles, random forests, and boosting
- Questions that use it (3) — Tuning a nearest-neighbour classifier · Decision trees and validation · Why an ensemble might improve a tree
- All 7 questions on Classification trees
See also
Regression tree · Decision stump · Surrogate split · Node impurity · Building a classification tree · Choosing a split · Invariance to a change of units · Multi-way splits and missing values