Concept - Decision Tree
Definition (s.297): a decision support tool that uses a tree-like model/graph of decisions and their possible consequences. Built top-down with a divide-and-conquer approach (s.298).
Examples
- “Should I do exercise today?” (s.297): root “Exercise Yesterday?” - Yes -> Don’t Go; No -> “Eat McSpicy Today?” - Yes -> Go, No -> Don’t Go.
- “Should I accept a new job offer?” (s.298): root “salary at least $50,000” (no -> decline); yes -> “commute more than 1 hour” (yes -> decline); no -> “offers free coffee” (yes -> accept, no -> decline).
Terminology (s.299)
| Term | Meaning |
|---|---|
| Root node | entire population/sample, further divided into subsets |
| Splitting | dividing a node into two or more sub-nodes |
| Decision node | sub-node that can be split further |
| Leaf / Terminal node | node that does not split |
| Branch / Sub-tree | sub-section of the entire tree |
| Pruning | removing nodes (opposite of splitting) |
| Parent / child node | a node divided into sub-nodes is the parent; the sub-nodes are its children |
Further decision-tree content (splitting criteria etc.) continues after s.300; later chunks may append below.
Source chunk: 03 Text Classification - Chunk 10 (s.271-300)
Overfitting, pruning and ensembles (s.335-337, s.350-353, 03 Text Classification - Chunk 12 (s.331-360))
A fully grown tree overfits noise; see Concept - Decision Tree Pruning (stopping criteria, post-pruning on a validation set). Trees are unstable learners (Concept - Stable and Unstable Learners); ensembles of trees: Concept - Random Forest, Concept - Boosting.
Related
Concept - ID3, Concept - Entropy, Concept - Information Gain, Concept - Gain Ratio, Concept - Gini Impurity, Concept - Overfitting, Concept - Random Forest. Up: 03 Text Classification - Index