Back to Study Material Machine Learning

Decision tree entropy

Entropy in the context of decision trees is a measure borrowed from information theory that quantifies the impurity or disorder in a set of labels. A node ...

Decision tree entropy

Measuring Disorder to Guide Splits

Entropy in the context of decision trees is a measure borrowed from information theory that quantifies the impurity or disorder in a set of labels. A node where all examples belong to the same class has zero entropy — perfectly pure. A node split evenly between two classes has maximum entropy of one bit — maximum disorder. The decision tree algorithm uses entropy to decide which feature and threshold to split on at each node.

The formula for binary entropy is negative p-positive times log base two of p-positive minus p-negative times log base two of p-negative, where p-positive and p-negative are the proportions of the two classes. For multi-class problems the formula sums the same term over all classes. The logarithm base two means the result is measured in bits, which connects naturally to information theory.

At each node the algorithm evaluates every possible split and picks the one that produces the greatest drop in entropy, weighted by the sizes of the resulting child nodes. This drop is called information gain and is the guiding criterion for the ID3 and C4.5 family of decision tree algorithms.

Pure splits are preferred because a pure node makes a confident prediction: all examples in it belong to the same class. A split that leaves both children with mixed classes has achieved little and will require further splitting, making the tree deeper and harder to interpret.

A concrete example: a node with 40 spam emails and 40 legitimate emails has entropy of 1.0 bit. After splitting on the presence of the word "prize," one child contains 38 spam and 2 legitimate, entropy roughly 0.19 bits, and the other contains 38 legitimate and 2 spam, also roughly 0.19 bits. The weighted average entropy of the children is much lower than 1.0, so information gain is high.

Exam tip: be ready to compute entropy by hand for simple two-class distributions and explain that information gain equals parent entropy minus the weighted average entropy of the children.