Overview
A Decision Tree chooses feature splits that make child nodes more homogeneous, then predicts from the leaf reached by an input.
FoundationSource checked
Decision Tree
Predicts by recursively splitting examples with feature tests into simpler subgroups.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Machine Learning
- Difficulty
- Beginner
- Family
- Tree Model
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 6
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
feature splitimpurityleaf predictionpruning
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n d log n)
Average
O(n d log n)
Worst
O(n^2 d)
Space
O(n)
When to Use
- Use it when interpretable rule-like predictions are valuable.
- Use it with tabular data containing mixed feature types.
- Use it as a base learner inside ensembles such as random forests or gradient boosting.
When Not to Use
- Avoid unpruned trees when overfitting is likely.
- Avoid expecting smooth extrapolation outside observed feature ranges.
- Avoid relying on one tree when small data changes make splits unstable.
What It Does
- Splits data by feature tests
- Predicts from leaf nodes
Use Cases
- Interpretable classification
- Rule-like prediction
- Feature interaction exploration
Inputs
- Feature matrix
- Target labels or values
Outputs
- Tree of decisions
- Predicted label or value
Key Formulas (1)
Gini impurity
gini = 1 − ∑(pclass2)
gini = 1 - sum(p_class^2)Scores how mixed a candidate split is before choosing a feature test.
Pseudocode
- 1.Start with all training examples at the root
- 2.Find a feature test that improves the split
- 3.Create child nodes for the split
- 4.Repeat recursively on each child
- 5.Stop when a node is pure or too small
Canonical Example
- Input
- examples = [[size, price], ...], target = label or value
- Output
- model predictions for new examples
- Explanation
- Decision Tree: The algorithm learns a pattern from examples and applies it to unseen data.
Implementation Notes
- Use validation data or pruning criteria to control depth and leaf size.
- Choose impurity measures and split handling consistently.
- Handle missing and categorical values explicitly.
Common Pitfalls
- Growing trees too deep for the amount of data.
- Leaking target information through split features.
- Treating split importance as causal importance.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow examples flowing through question nodes to leaves.
Step 1 of 5: Start with all training examples at the root
decision-treeNotes
Single decision trees are easy to inspect but often less accurate than tree ensembles.
Sources (1)
What each reference supports for this entry.
The Elements of Statistical Learning
BookStatistical learning reference for the model family and tradeoffs of Decision Tree.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byExtra Trees
Machine Learning · Core
Extra Trees builds an ensemble from randomized decision trees.
Compare with thisOften paired withAdaBoost
Machine Learning · Core
AdaBoost commonly uses shallow decision trees as weak learners.
Compare with thisRelationships
View full relationship pagePrerequisite ofGradient Boosting
Boosted tree models use decision trees as weak learners.
Prerequisite ofRandom Forest
Random forests are ensembles of decision trees.
Related Algorithms
Tags
Machine LearningSupervised LearningClassificationTree