Skip to content
Sem 5 Prep
← BI & Data ScienceDecision trees, entropy and information gain

Formulas for this chapter

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
Step 4 of 23
The real wordsTheory

Entropy

EntropyA measure of impurity in bits. For a node whose classes have proportions p1, p2, ..., entropy = minus the sum of p_i times log base 2 of p_i.
Entropy = -p1 log2(p1) - p2 log2(p2) Excel: =-I4*LOG(I4,2) - I5*LOG(I5,2)

Read the scale. A node all of one class has entropy 0: perfectly pure, nothing left to learn. A node split exactly 50/50 has entropy 1: maximally impure. Everything else lies between.

← BackContinue →