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

Section B only: what a decision tree is

Decision treeA supervised classifier that repeatedly splits the data on one attribute at a time, forming a tree whose internal nodes are tests, whose branches are answers, and whose leaves are predicted classes.

Its great virtue is that the fitted model reads as plain rules: "if income is low then yes; if income is high and age is young then no". Nothing else in this course produces an explanation a manager can repeat.

Section A's own list of classifiers does name decision trees and random forest, so the vocabulary is fair game even though the arithmetic was Section B's.

← BackContinue →