Back to Curriculum
Basic•Machine Learning
Decision Trees
Hierarchical split-based classification and regression.
Interactive Playground
Initializing Interactive Playground...
Research-Level Deep Dive & Equations
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
Test Your Knowledge
Check whether you have mastered this concept with a quick quiz.
Was this lesson helpful?
Your feedback helps us continuously improve the curriculum and interactive visualizations.