Entropy of a node
Entropy = -SUM p_i log2(p_i)
Excel: =-p1*LOG(p1,2) - p2*LOG(p2+0.000001,2)
Pure node 0; two-class 50/50 node 1
At every node of a tree, and for every candidate branch. The 0.000001 nudge avoids #NUM! when a branch has a zero-probability class.
- p_i
- Proportion of the node's observations in class i
- log2
- Logarithm to base 2, so entropy is in bits
Weighted entropy and information gain
Weighted entropy = SUM ( n_branch / n_parent ) x Entropy(branch)
Information gain = Entropy(parent) - Weighted entropy
Choose the split with the lowest weighted entropy
Choosing which attribute to split on. Both rules pick the same attribute, because the parent entropy is a constant across candidates.
- n_branch
- Observations sent to that branch
- n_parent
- Observations at the node being split
Gini impurity
Gini = 1 - SUM (p_i)^2
Pure node 0; two-class 50/50 node 0.5
The alternative to entropy, used where logarithms are inconvenient. Usually picks the same split; on the class data both choose Income.
- p_i
- Proportion of the node's observations in class i