Decision Trees
Hierarchical split-based classification and regression.
For a small example, classify six fruits using color and weight. Compare candidate thresholds by impurity reduction and draw the two resulting leaves.
Decision Trees
In practice
A team predicts which applications need manual review. Limit depth, validate thresholds, inspect leaf support and subgroup errors, and compare against logistic regression.
Initializing Interactive Playground...
Experiment notes
Record your experiment
Predict which feature and threshold will create the cleanest separation.
Implementation
Repair a failing Decision Trees starter
The starter deliberately follows a tempting but flawed assumption: Trusting impurity importance as causal evidence
- Run the starter once and inspect the first wrong value, failed check, or incomplete branch.
- Repair the smallest relevant part of the code. Do not rewrite the whole solution.
- Check the solution, then explain why this correction works: Use permutation or SHAP carefully and validate with domain knowledge.
Check: The browser checks pass and you can name the failure mechanism before opening the explanation.
Failing starter lab
Score a decision-tree split
Compute weighted Gini impurity for candidate thresholds and choose the best split.
Run the incomplete starter before opening hints. Use the first wrong output or failed check to form a repair hypothesis.
Knowledge check
10 questions
Explanations after each answer · 80% to pass · Decision Trees
Chapter 1 of 6 · Core
Information-Theoretic Foundations of Decision Trees
The construction of decision trees is conceptually anchored in Shannon's Information Theory. Given a dataset where each sample possesses a target label taking values in a finite set , the primary challenge is to recursively partition the feature space to maximize the homogeneity of within the partitioned regions.
We measure the impurity or uncertainty of a distribution using Shannon Entropy. For a discrete random variable with probability mass function , the entropy is defined as: where we define . Shannon entropy represents the expected number of bits required to encode the class labels of samples drawn from the distribution. It achieves its global minimum of when the distribution is degenerate (i.e., for some , representing perfect purity), and achieves its maximum of when is uniformly distributed.
When partitioning a node using a feature , we evaluate the Conditional Entropy of given . If is a discrete feature partitioning into subsets corresponding to values , the conditional entropy is: The reduction in uncertainty achieved by this partition is the Information Gain (equivalent to Mutual Information ): By the properties of mutual information, , with equality holding if and only if and are statistically independent.
The High-Cardinality Bias and Gain Ratio: Information Gain possesses a systematic bias toward features with a large number of distinct values (high cardinality). A feature such as a unique "Student ID" will partition a dataset into single-element leaves, yielding and maximizing Information Gain. However, this model has zero generalization power. To correct this, the C4.5 algorithm introduces the Gain Ratio, which normalizes the Information Gain by the Split Information (the entropy of the feature itself): This normalizer penalizes features that split the data into many small, fragmented subsets, forcing the tree to select features that provide high predictive value without excessive fragmentation.
Key equations
Video explanation
Decision and Classification Trees, Clearly Explained!
StatQuest
Follow how a tree chooses splits and where depth can turn useful structure into overfitting.
References
Primary sources and free technical reading for Decision Trees.