ID3 algorithm

In decision tree learning, ID3 (Iterative Dichotomiser 3) is an algorithm invented by Ross Quinlan[1] used to generate a decision tree from a dataset. ID3 is the precursor to the C4.5 algorithm, and is typically used in the machine learning and natural language processing domains.

Algorithm

The ID3 algorithm begins with the original set ${\displaystyle S}$ as the root node. On each iteration of the algorithm, it iterates through every unused attribute of the set ${\displaystyle S}$ and calculates the entropy ${\displaystyle H(S)}$ (or information gain ${\displaystyle IG(A)}$) of that attribute. It then selects the attribute which has the smallest entropy (or largest information gain) value. The set ${\displaystyle S}$ is then split by the selected attribute (e.g. age < 50, 50 <= age < 100, age >= 100) to produce subsets of the data. The algorithm continues to recur on each subset, considering only attributes never selected before.
Recursion on a subset may stop in one of these cases:

• every element in the subset belongs to the same class (+ or -), then the node is turned into a leaf and labelled with the class of the examples
• there are no more attributes to be selected, but the examples still do not belong to the same class (some are + and some are -), then the node is turned into a leaf and labelled with the most common class of the examples in the subset
• there are no examples in the subset, this happens when no example in the parent set was found to be matching a specific value of the selected attribute, for example if there was no example with age >= 100. Then a leaf is created, and labelled with the most common class of the examples in the parent set.

Throughout the algorithm, the decision tree is constructed with each non-terminal node representing the selected attribute on which the data was split, and terminal nodes representing the class label of the final subset of this branch.

Summary

1. Calculate the entropy of every attribute using the data set ${\displaystyle S}$
2. Split the set ${\displaystyle S}$ into subsets using the attribute for which entropy is minimum (or, equivalently, information gain is maximum)
3. Make a decision tree node containing that attribute
4. Recur on subsets using remaining attributes.

Properties

ID3 does not guarantee an optimal solution; it can get stuck in local optimums. It uses a greedy approach by selecting the best attribute to split the dataset on each iteration. One improvement that can be made on the algorithm can be to use backtracking during the search for the optimal decision tree.

ID3 can overfit to the training data, to avoid overfitting, smaller decision trees should be preferred over larger ones. This algorithm usually produces small trees, but it does not always produce the smallest possible tree.

ID3 is harder to use on continuous data. If the values of any given attribute is continuous, then there are many more places to split the data on this attribute, and searching for the best value to split by can be time consuming.

Usage

The ID3 algorithm is used by training on a dataset ${\displaystyle S}$ to produce a decision tree which is stored in memory. At runtime, this decision tree is used to classify new unseen test cases by working down the decision tree using the values of this test case to arrive at a terminal node that tells you what class this test case belongs to.

The ID3 metrics

Entropy

Entropy ${\displaystyle H(S)}$ is a measure of the amount of uncertainty in the (data) set ${\displaystyle S}$ (i.e. entropy characterizes the (data) set ${\displaystyle S}$).

${\displaystyle H(S)=-\sum _{x\in X}p(x)\log _{2}p(x)}$

Where,

When ${\displaystyle H(S)=0}$, the set ${\displaystyle S}$ is perfectly classified (i.e. all elements in ${\displaystyle S}$ are of the same class).

In ID3, entropy is calculated for each remaining attribute. The attribute with the smallest entropy is used to split the set ${\displaystyle S}$ on this iteration. The higher the entropy, the higher the potential to improve the classification here.

Information Gain

Information gain ${\displaystyle IG(A)}$ is the measure of the difference in entropy from before to after the set ${\displaystyle S}$ is split on an attribute ${\displaystyle A}$. In other words, how much uncertainty in ${\displaystyle S}$ was reduced after splitting set ${\displaystyle S}$ on attribute ${\displaystyle A}$.

${\displaystyle IG(A,S)=H(S)-\sum _{t\in T}p(t)H(t)}$

Where,

In ID3, information gain can be calculated (instead of entropy) for each remaining attribute. The attribute with the largest information gain is used to split the set ${\displaystyle S}$ on this iteration.