Do Not Use Decision Tree Like This
Demonstrate the Limitation of Information Gain in ID3 and the Benefits of using C4.5
As one of the most popular classic machine learning algorithm, the Decision Tree is much more intuitive than the others for its explainability. In one of my previous article, I have introduced the basic idea and mechanism of a Decision Tree model. It demonstrated this machine learning model using an algorithm called ID3, which is one of the most classic ones for training a Decision Tree classification model.
If you are not that familiar with Decision Tree, it is highly recommended to check out the above article before reading into this one.
To intuitively understand Decision Trees, it is indeed good to start with ID3. However, it is probably not a good idea to use it in practice. In this article, I'll introduce a commonly used algorithm to build Decision Tree models - C4.5.
Drawbacks of Classic ID3 Algorithm
Before we can demonstrate the major drawbacks of the ID3 algorithm, let's have a look at what are the major building blocks of it. Basically, the important is the Entropy and Information Gain.
Recap of Entropy
Here is the formula of Entropy:
The set "X" is everything in the set of the node, and "xᵢ" refers to the specific decision of each sample. Therefore, "P(xᵢ)" is the probability of the set to be made with a certain decision.
Let's use the same training dataset as an example. Suppose that we have an internal node in our decision tree with "weather = rainy". It is can be seen that the final decisions are both "No". Then, we can easily calculate the entropy of this node as follows:
Basically, the probability of being "No" is 2/2 = 1, whereas the probability of being "Yes" is 0/2 = 0.
Recap of Information Gain
On top of the concept of Entropy, we can calculate the Information Gain, which is the basic criterion to decide whether a feature should be used as a node to be split.
For example, we have three features: "Weather", "Temperature" and "Wind Level". When we start to build our Decision Tree using ID3, how can we decide which one of them should be used as the root node?
ID3 makes use Information Gain as the criterion. The rule is that, select the feature with the maximum Information Gain among all of them. Here is the formula of calculating Information Gain:
where
"T" is the parent node and "a" is the set of attributes of "T"
The notation "|T|" means the size of the set
Using the same example, when we calculating the Information Gain for "Weather = Rainy", we also need to take its child nodes' Entropy into account. Specific derivation and calculating progress can be found in the article that was shared in the introduction.
Major Drawbacks of Using Information Gain
The major drawbacks of using Information Gain as the criterion for determining which feature to be used as the root/next node is that it tends to use the feature that has more unique values.
But why? Let me demonstrate it using an extreme scenario. Let's say, we have got the training set with one more feature: "Date".
You might say that the feature "Date" should not be considered in this case because it intuitively will not be helpful to decide whether we should go out for running or not. Yes, you're right. However, practically, we may have much more complicated dataset to be classified, and we may not be able to understand all the features. So, we may not always be able to determine whether a feature does make sense or not. In here, I will just use "Date" as an example.
Now, let's calculate the Information Gain for "Date". We can start to calculate the entropy for one of the dates, such as "2020–01–01".
Since there is only 1 row for each date, the final decision must be either "Yes" or "No". So, the entropy must be 0! In terms of the information theory, it is equivalent to say:
The date tells us nothing, because the result is just one, which is certain. So, there is no "uncertainty" at all.
Similarly, for all the other dates, their entropies are 0, too.
Now, let's calculate the entropy for the date itself.
WoW, that is a pretty large number compared to the other features. So, we can calculate the Information Gain of "Date" now.
Unsurprisingly, the Information Gain of "Date" is the entropy of itself because all its attribute having entropies that are 0.
If we calculate the Information Gain for the other three features (you can find details in the article that is linked in the introduction), they are:
Information Gain of Weather is 0.592
Information Gain of Temperature is 0.522
Information Gain of Wind Level is 0.306
Obviously, the Information Gain of Date is overwhelmingly larger than the others. Also, it can be seen that it will be even larger if the training dataset is larger. After that, don't forget that the feature "Date" actually does not make sense in deciding whether we should go out for running or not, but it is decided as the "Best" one to be the root node.
Even funnier, after we decided to use "Date" as our root node, we're done :)
We end up with a Decision Tree as shown above. This is because the feature "Date" is too good. If we use it as the root node, all its attributes will simply tell us whether we should go out for running or not. It is not necessary to have the other features.
Yes, you may have a face like this fish at the moment, so do I.
Fix the Information Gain Limitation
The easiest fix of the Information Gain limitation that exists in ID3 Algorithm is from another Decision Tree algorithm called C4.5. The basic idea of reducing this issue is to use Information Gain Ratio rather than Information Gain.
Specifically, Information Gain Ratio is simply adding a penalty on the Information Gain by dividing with the entropy of the parent node.
In other words,
Therefore, if we're using C4.5 rather than ID3, the Information Gain Ratio of the feature "Date" will be as follows.
Well, it is indeed still the largest one compared to the other features, but don't forget that we are really using an extreme example where each attribute value of the feature "Date" will have only one row. In practice, Information Gain Ratio will be quite enough to avoid most of the scenarios that Information Gain will cause bias.
Other Improvements of C4.5
In my opinion, using Information Gain Ratio is the most significant improvement from ID3 to C4.5. Nevertheless, there are more improvements in C4.5 that you should know.
PEP (Pessimistic Error Pruning)
If you are not familiar with the concept "Pruning" of Decision Tree, again, you may need to check out my previous article that is attached in the introduction of this article.
PEP is another significant improvement in C4.5. Specifically, it will prune the tree in a top-down manner. For every internal node, the algorithm will calculate its error rate. Then, try to prune this branch to compare the error rate before and after the pruning. So, it is decided whether we should reserve this branch.
Some characteristics of PEP:
It is one of the Post-Pruning methods.
It prunes the tree without the dependency of a validation dataset.
Usually quite good to avoid overfitting, and consequently improve the performance in classifying unknown data.
Discretising the Continuous Features
C4.5 supports continuous values. So, we are not limited to have "Low", "Medium" and "High" such categorical values. Instead, C4.5 will automatically detect the thresholds of the continuous value that can generate the maximum Information Gain Ratio and then split the node using this threshold.
Summary
In this article, I have illustrated why ID3 is not ideal. The major reason is that the criterion it uses - Information Gain - might be significantly bias to those features that have larger numbers of distinct values.
The solution has been given in another Decision Tree algorithm called C4.5. It evolves the Information Gain to Information Gain Ratio that will reduce the impact of large numbers of distinct values of the attributes.
Again, if you feel that you need more context and basic knowledge about Decision Trees, please check out my previous article.
If you feel my articles are helpful, please consider joining Medium Membership to support me and thousands of other writers! (Click the link above)
