Decision Trees

Objective

Recursively split the dataset until the tree is left with pure leaf nodes i.e. only one class in a node.

Decision trees are greedy and are supervised.

ID3 Algorithm

There are two types of nodes: decision nodes and leaf nodes.

Note

When arriving at non-pure leaf nodes e.g. likely when data becomes complex, classify based on the majority.

Measures the amount of uncertainty or impurity in the dataset.

$E = Σ - p_{i} \times l o g_{2} (p_{i})$

Measures the reduction in entropy or Gini impurity after a dataset is split on an attribute.

$I G = E (P a re n t) - Σ w_{i} \times E (C hi l d_{i})$

$M a x (I G_{St a t e_{1}}, I G_{St a t e_{2}})$
$w_{i} = \frac{Va l u es in t h e N o d e}{T o t a l Va l u es}$ e.g. $\frac{6}{20}$