C4.5 algorithm

In 2011, authors of the Weka machine learning software described the C4.5 algorithm as "a landmark decision tree program that is probably the machine learning workhorse most widely used in practice to date". It became quite popular after ranking #1 in the Top 10 Algorithms in Data Mining pre-eminent paper published by Springer LNCS in 2008.

Algorithm

C4.5 builds decision trees from a set of training data in the same way as ID3, using the concept of information entropy. The training data is a set ${\displaystyle S=s_1,s_2,...}$ of already classified samples. Each sample ${\displaystyle s_i}$ consists of a p-dimensional vector ${\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}$, where the ${\displaystyle x_j}$ represent attribute values or features of the sample, as well as the class in which ${\displaystyle s_i}$ falls.

At each node of the tree, C4.5 chooses the attribute of the data that most effectively splits its set of samples into subsets enriched in one class or the other. The splitting criterion is the normalized information gain (difference in entropy). The attribute with the highest normalized information gain is chosen to make the decision. The C4.5 algorithm then recurses on the partitioned sublists.

This algorithm has a few base cases.

• All the samples in the list belong to the same class. When this happens, it simply creates a leaf node for the decision tree saying to choose that class.
• None of the features provide any information gain. In this case, C4.5 creates a decision node higher up the tree using the expected value of the class.
• Instance of previously unseen class encountered. Again, C4.5 creates a decision node higher up the tree using the expected value.

Pseudocode

In pseudocode, the general algorithm for building decision trees is:

1. Check for the above base cases.
2. For each attribute a, find the normalized information gain ratio from splitting on a.
3. Let a_best be the attribute with the highest normalized information gain.
4. Create a decision node that splits on a_best.
5. Recurse on the sublists obtained by splitting on a_best, and add those nodes as children of node.