Decision Trees

Split to cut impurity — maximize information gain.

The idea

A decision tree classifies an example by asking a sequence of yes/no questions about its features, following the answers down to a leaf, and predicting the class that dominates there. Building the tree means choosing the questions.

A question is worth asking if it separates the classes: it divides the examples at a node into two groups, and we want each group closer to all-one-class than the parent. Choosing between candidate questions therefore requires a measure of how mixed a group is. Entropy supplies one: $H = -\sum_{i} p_{i}\log_{2} p_{i},$ where $p_{i}$ is the fraction of the node's examples in class $i$. Entropy is the average number of yes/no answers still needed to identify one example's class: a node holding a single class needs none, so $H = 0$, and a node split evenly between two classes needs one, so $H = 1$.

The information gain of a split is the entropy it removes: the parent's entropy minus the average of the two children's entropies, weighted by the fraction of examples each child receives.

Algorithm.

Algorithm: Tree Building Input: labelled training examples, a list of candidate yes/no questions Output: a decision tree 1. place all the examples at the root; the root is the current node 2. if the current node's examples are all one class, or no question separates them further, make it a leaf // the leaf predicts the class dominating there 3. otherwise compute each candidate question's information gain at the node 4. split on the question with the largest gain: create two children, send each example to the child its answer selects 5. apply steps 2–4 to each child in turn 6. when every branch ends in a leaf, return the tree

Ways to work on it

• Walkthrough. Purity, entropy, and information gain.
• Practice. Compute the Gini impurity of a node.
• Hardest. Information gain of a perfect split, and random forests.

Not sure where to start? Take the ten-question placement test.