Skip to content
Sem 5 Prep
← BI & Data ScienceSection B only: decision 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 1 of 23
The ideaTheory

Section B only: twenty questions

You are guessing what somebody bought, and you may ask yes-or-no questions. You would not ask a question whose answer you can already predict. You would ask the one that splits the possibilities most cleanly.

A decision tree does exactly that, over and over. At each node it asks: of all the questions I could ask about this data, which one leaves the two groups purest?

Entropy is how it measures "pure". Check against your class slides: this topic was taught to Section B, and your section may not have covered it.

← BackContinue →