When we wanted to describe the technical aspects of the C5.0 and cubist models, the main source of information on these models was the raw C source code from the RuleQuest website. For many years, both of these models were proprietary commercial products and we only recently open-sourced. Our intuition is that Quinlan quietly evolved these models from the versions described in the most recent publications to what they are today. For example, it would not be unreasonable to assume that C5.0 uses AdaBoost. From the sources, a similar reweighting scheme is used but it does not appear to be the same.
For classifying new samples, the C sources have
ClassNo PredictTreeClassify(DataRec Case, Tree DecisionTree)
/* ------------ */
ClassNo c, C;
/* Save total leaf count in ClassSum */
ForEach(c, 0, MaxClass)
ClassSum[c] = 0;
PredictFindLeaf(Case, DecisionTree, Nil, 1.0);
C = SelectClassGen(DecisionTree->Leaf, (Boolean)(MCost != Nil), ClassSum);
/* Set all confidence values in ClassSum */
ForEach(c, 1, MaxClass)
Prior = DecisionTree->ClassDist[c] / DecisionTree->Cases;
ClassSum[c] = (ClassSum * ClassSum[c] + Prior) / (ClassSum + 1);
Confidence = ClassSum[C];
- The predicted probability is the "confidence" value
- The prior is the class probabilities from the training set. For the iris data, this value is 1/3 for each of the classes
- The array
ClassSum is the probabilities of each class in the terminal node although
ClassSum is the number of samples in the terminal node (which, if there are missing values, can be fractional).
For sample 130, the virginica values are:
(ClassSum * ClassSum[c] + Prior) / (ClassSum + 1)
= ( 6 * (4/6) + (1/3)) / ( 6 + 1)
Why is it doing this? This will tend to avoid class predictions that are absolute zero or one.
Basically, it can be viewed to be similar to how Bayesian methods operate where the simple probability estimates are "shrunken" towards the prior probabilities. Note that, as the number of samples in the terminal nodes (
ClassSum) becomes large, this operation has less effect on the final results. Suppose
ClassSum = 10000, then the predicted virginica probability would be 0.6663337, which is closer to the simple estimate.
This is very much related to the Laplace Correction. Traditionally, we would add a value of one to the denominator of the simple estimate and add the number of classes to the bottom, resulting in
(4+1)/(6+3) = 0.5555556. C5.0 is substituting the prior probabilities and their sum (always one) into this equation instead.
To be fair, there are well known Bayesian estimates of the sample proportions under different prior distributions for the two class case. For example, if there were two classes, the estimate of the class probability under a uniform prior would be the same as the basic Laplace correction (using the integers and not the fractions). A more flexible Bayesian approach is the Beta-Binomial model, which uses a Beta prior instead of the uniform. The downside here is that two extra parameters need to be estimated (and it only is defined for two classes)