2. Classification - Decision Trees

Decision Trees

A decision tree is a popular classifier:

• nodes represent decisions
• arcs represent possible answers
• terminal nodes represent class labels

We can think of these are if-else statements. Rules can be used to query a relational database.

Link to original

Strengths and Limitations

Strengths	Limitations
Can be easily interpreted	Classifiers can create complex trees that do not generalise well to new data (overfitting)
Can handle both categorical and numerical variables	Sensitive to even small changes in data
Shows the most important features in a data set
Not sensitive to outliers or missing data

Algorithms

There are a bunch of different algorithms we can use:

• Hunt’s Algorithm (earliest, basis for most existing algorithms)
• CART
• IDE3, C4.5
• SLIQ, SPRINT

Hunt’s Algorithm

Often known as rule induction, nodes are repeatedly split until all elements represented belong to one class. Nodes then become terminal nodes.

1. Let the set of training data be $S$.
2. Put all $S$ into a single tree node; if some attributes are continuous-valued, make them discrete. For example, age ranges can be binned into categories (u18, 18-40, 41-65, ..)
3. If all instances in $S$ are in the same class, then stop
4. Split the next node by selecting an attribute $A$ from your list of attributes that best splits the objects in the node, and create a node.
5. Split the node according to the values of $A$.
6. Stop if either of the following conditions is met otherwise continue with $3$:
   1. This partition divides the data into subsets that belong to a single class and no other node needs splitting.
   2. There are no remaining attributes on which the sample can be further divided.

Determining best splits

Commonly used measures to determine the best split include: GINI index, entropy (information theory)

We want to take a greedy approach that gives us homogeneous, pure classes.

• In a 2-class situation with 10 records, we split using attribute X and 10 records go to Class0 and 0 to Class1. This has 0 impurity and is ideal.
• If we split by X and half the records go to Class0 and the other to Class1, then we have an impurity of 0.5 which is the worst.

We need to determine a good measure of node impurity.

Gini Ratio

Gini Ratio

The Gini Ratio (Gini Impurity) is a measure of statistical dispersion, i.e. a measure of inequality (probability of this classification mislabelling a randomly selected example):

$$\text{G}(S)=1-\sum _{i=1}^c{p}_i^2$$

Where $c$ is the number of classes.

Link to original

Example Gini Ratios

$P(C_1)=\frac{0}{6}=0$	$P(C_1)=\frac{1}{6}$	$P(C_1)=\frac{2}{6}$
$P(C_2)=\frac{6}{6}=1$	$P(C_2)=\frac{5}{6}$	$P(C_2)=\frac{4}{6}$
$\text{GINI}=1-(0^2+1^2)=0$	$\text{GINI}=1-({\frac{1}{6}}^2+{\frac{5}{6}}^2)=0.278$	$\text{GINI}=1-({\frac{2}{6}}^2+{\frac{4}{6}}^2)=0.444$

GINI Split

GINI Split

We use the GINI Split to find which variable to split on, we use the attribute with the lowest index according to the following formula:

$${\text{GINI}}_{\text{split}}=\sum _{i=1}^k\frac{n_i}{n}\text{GINI}(t)$$

• Where $n_i$ is the occurrences of $t$
• Where $n$ is total number of entries

Link to original

Example Best Split