6.3 THE C5.0 ALGORITHM FOR BUILDING DECISION TREES
The C5.0 algorithm is J. Ross Quinlan's extension of his own C4.5 algorithm for generating decision trees.5Unlike CART, the C5.0 algorithm is not restricted to binary splits. The 5.0 algorithm uses the concept of information gain or entropy reduction to select the optimal split. Suppose that we have a variable X whose k possible values have probabilities p1, p2, …, pk. The smallest number of bits, on average per symbol, needed to transmit a stream of symbols representing the values of X observed is called the entropy of X, defined as
C5.0 uses entropy as follows. Suppose that we have a candidate split S, which partitions the training data set T into several subsets, T1, T2, …, Tk. The mean information requirement can then be calculated as the weighted sum of the entropies for the individual subsets, as follows:
where Pi represents the proportion of...