C4.5 Algorithm - Algorithm

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 of already classified samples. Each sample is a vector where represent attributes or features of the sample. The training data is augmented with a vector where represent the class to which each sample belongs.

At each node of the tree, C4.5 chooses one attribute of the data that most effectively splits its set of samples into subsets enriched in one class or the other. Its criterion is the normalized information gain (difference in entropy) that results from choosing an attribute for splitting the data. The attribute with the highest normalized information gain is chosen to make the decision. The C4.5 algorithm then recurses on the smaller 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.