A Step By Step C4.5 Decision Tree Example

81 Comments

1. GainRatio(Decision, Humidity 65) = 0.126
   GainRatio(Decision, Humidity 80) = 0.107

   How comes you took into account a threshold of 80 when GainRatio for 65 is higher?

   1. In case of Humidity<=80, there are 2 no and 7 yes decisions. Total number of instances is 9
      Entropy(Decision|Humidity<=80) = – p(No) . log2p(No) – p(Yes) . log2p(Yes) = - (2/9) * log(2/9) - (7/9)*log(7/9) = 0.764 (BTW, log refers to the base 2)
      In case of Humidity>80, there are 3 no and 2 yes decisions. Total number of instances is 5
      Entropy(Decision|Humidity>80) = – p(No) . log2p(No) – p(Yes) . log2p(Yes) = -(3/5)*log(3/5) – (2/5)*log(2/5) = 0.971
      
      Global entropy was calculated as 0.940 in previous steps
      
      Now, it is time to calculate Gain.
      Gain(Decision, Humidity<> 80) = Entropy(Decision) – p(Humidity<=80) * Entropy(Decision|Humidity<=80) - p(Humidity>80)*Entropy(Decision|Humidity>80)
      Gain(Decision, Humidity<> 80) = 0.940 – (9/14)*0.764 – (5/14)*0.971 = 0.101
      
      Now, we can calculate GainRatio but before we need to calculate SplitInfo first.
      
      SplitInfo(Decision, Humidity<> 80) = -p(No)*log(p(No)) – p(Yes)*log(P(Yes)) = -(9/14)*log(9/14) – (5/14)*log(5/14) = 0.940
      
      GainRatio = Gain / SplitInfo = 0.101 / 0.940 = 0.107
      
      I hope this explanation is understandable.

      1. Understood, thanks

      2. I don’t understand why we choose 80 its gain ratio is only 0.107
         for 65 its 0.126
         and 0.107<0.126 ?

         1. If we would use gain ratio, then you will be right. Humidity=65 (0.126) is more dominant than Humidity=80 (0.107).
            But I use information gain instead of gain ratio here. In this case, Humidity=80 (0.101) is more dominant than Humidity= 65 (0.048).

            If you ask that why information gain is used instead of gain ratio, it is all up to you. You might want to use gain ratio, and herein 65 will be your choice.

      3. Why is humidity the best nodle if outlook=sunny? i dont get it

2. You have the following
   Gain(Decision, Humidity 70) = 0.940 – (4/14).(0.811) – (10/14).(0.970) = 0.940 – 0.231 – 0.692 = 0.014

   there are 3 values of 70 so surely P(Humidity 70) = P( No) = 3/14 not 4/14

   1. Here, 4 is the number of instances which are less than or equal to 70. Humidity of instances for day 6, 7, 9, 11 are less than or equal to 70.

      Similarly, 10 is the number of instances which are greater than 70. Number of instances greater than 70 is 10.

3. I’m sorry I posted the wrong reference. It should have been
   Gain(Decision, Humidity 70) = 0.940 – (4/14).(0.811) – (10/14).(0.970) = 0.940 – 0.231 – 0.692 = 0.014

   so,
   there are 3 values of 70 so surely P(Humidity 70) = P( No) = 3/14 not 4/14
   thanks for your attention

   1. You were right if we need Gain(Decision, Humidity = 70) but we need Gain(Decision, Humidity <= 70). Gain(Decision, Humidity ? 70) = 0.940 – (4/14).(0.811) – (10/14).(0.970) = 0.940 – 0.231 – 0.692 = 0.014 In this equation 4/14 is probability of instances less than or equal to 70, and 10/14 is probability of instances greater than 70.

      1. I do understand that but the statement is ‘not equal’ to 70, not less than or equal. If the objective is to have values less than or equal and values greater than then the calculation is that of the global entropy, i.e. all values surely.

         1. Right, cause of poor communication. Actually, I would not intent as your understanding. I should mention that in the post.

            The statement Gain(Decision, Humidity ? 70) refers to that what would be if the branch of decision tree is for less than or equal to 70, and greater than 70. All calculations made with this approach.

            I hope everything is clear now. Thank you for your attention.

            1. OK, now I get it. Thanks a lot both for your blog, attention and patience. It is much appreciated.

4. Looks as if the editor loses the not-equal sign, hence the poor communication..
   The expression in question is
   Gain(Decision, Humidity¬= 70) = 0.940 – (4/14).(0.811) – (10/14).(0.970) = 0.940 – 0.231 – 0.692 = 0.014

   There being 3 instances of 70 so 3 instances where P(Humidity¬=70) is false, i.e. P(No) = 3/14

5. I’m sorry to have to return to the point made by Dinca Andrei but I think the confusion arises from a statement in your blog
   The value which maximizes the gain would be the threshold.

   Is it not the case that the threshold is the value that minimises Entropy(Decision|Humidity threshold)
   Here are some calculations, which if taken with the ones you perform, does show 80 as the splitting point – Entropy(Decision|Humidity 80) is the least value

   le 65 0
   > 65 0.961237
   65 0.892577
   g ratio 0.047423
   split 0.371232
   g ratio 0.127745

   le 78 0.650022
   >78 1
   78 0.85001
   g 0.08999
   split 0.985228
   g ratio 0.09134

   le 80 0.764205
   >80 0.970951
   80 0.838042
   g 0.101958
   spli 0.940286
   g ratio 0.108433

   le 85 0.881291
   >85 1
   85 0.915208
   g 0.024792
   split 0.863121
   g ratio 0.028724

   Thanks for your attention.

   1. Yes, you are absolutely right. I summarized gain and gain ratios for every possible threshold point.

      branch-> 65 70 75 78 80 85 90
      gain 0.048 0.014 0.045 0.09 0.101 0.024 0.01
      gain ratio 0.126 0.016 0.047 0.09 0.107 0.027 0.016

      I stated that “We would calculate the gain OR gain ratio for every step. The value which maximizes the gain would be the threshold.”. Now, it is all up to you to decide threshold point based on gain or gain ratio. If prefer to use gain and my threshold would be 80. If you prefer to use gain ratio metric, your threshold would be 65. The both approaches are correct.

6. HI ,, are this algorithm good for a large database , like a dataset for large manufacture
   Thank you

   1. Decision tree algorithms require high memory demand. You should look its extended version – random forests, this might be adapted better for your problem

7. why we didnt calculate the gain ratio of temperature here

   1. It’s all up to you. You can use either information gain or gain ratio. In this case, using information gain is my choice.

      1. if we use the information gain, then what’s the difference between id3 and c4.5?

         1. if you use information gain, then you will have an id3 decision tree

8. why when i tried your chefboost on github, i got an error

   File “Chefboost.py”, line 81
   print(header,end=”)
   ^
   SyntaxError: invalid syntax

   how to solve this, thanks

   1. What is your python environment? This works in python 3.X.

      1. ah sorry,i used python 2.x

         i have another question, so in the end ‘num_of_trees’ variable is not used? i thought we can use the variable for limit the number of leaf tree

         sorry if I am wrong in reading the code

         1. The variable number of trees is using in random forest. Regular tree algorithms such as id3 or c4.5 will create a single tree.

9. Hi
   Thank you for this excellent description .I just have a question , how I can calculate accuracy of training data?
   thank you

   1. When you run a decision tree algorithm, it builds decision rules. For example, I use C4.5 algorithm and the data set https://github.com/serengil/chefboost/blob/master/dataset/golf2.txt , the following rules created.

      def findDecision(Outlook,Temperature,Humidity,Wind):
      …if.Temperature<=83:
      ……if Outlook==’Rain’:
      ………if Wind==’Weak’:
      …………return ‘Yes’
      ………if Wind==’Strong’:
      …………return ‘No’
      ……if Outlook==’Overcast’:
      ………return ‘Yes’
      ……if Outlook==’Sunny’:
      ………if Humidity>65:
      …………if Wind==’Weak’:
      ……………return Yes’
      …………if Wind==’Strong’:
      ……………return ‘Yes’
      …if Temperature>83:
      ……return ‘No’

      Now, I check all instances in the same data set. Let’s focus on the first instance.

      Outlook,Temp.,Humidity,Wind,Decision
      Sunny,85,85,Weak,No

      Decision rules say that prediction is no because temperature is 85 and it is greater than 83. On the other hand, decision column says actual value and it is no, too. This instance is classified correctly. I will apply same procedures for all instances and check how many of them are classified correctly. Dividing the correctly classified instances to all instances will be the accuracy on training set.

      Similarly, if you apply these decision rules for a data set haven’t been fed to training set will be you test accuracy.

      I strongly recommend you to run this python code to understand clear: https://github.com/serengil/chefboost

10. sir, I need a clarification when to use info gain and gain ratio?

    1. ID3 uses information gain whereas C4.5 uses gain ratio in most cases.

11. i drew decision tree using info gain…it came perfectly… branches were more. while I drew decision tree using gain ratio… the tree is pruned and I cannot solve it further because I get gain ratio either more than 1.0 or in -ve. while splitting, one I got [0,0,2](classified as III class) and another is [0,49,3] (not classified fully, can I finalize the branch as II class). is it correct to stop abruptly, telling class-II as a leaf node?

    1. Sorry but I do not understand your case. Please explain it more clear.

       1. for a particular dataset i got different decision tree for id3 and c4.5(output of both id3 and c4.5 decision tree are not the same);
          while using c4.5, i calculated a gain ratio, i draw decision tree using it, but suddenly i started to get gain ratio values either more than 1.0 or in -ve. can i stop drawing decision tree while i get values of gain ratio like that?

          1. It makes sense if you shared your data set.

             1. How to cross validate decision tree midels using chefboost?

             2. Cross validation is not currently supported in chefboost. I plan to add this feature in the next release.

12. Why you didn’t calculate Temp. attribute ?

    1. I did actually

       1. I mean you didn’t calculate Entropy, Gain, Split Info, and Gain Ratio for Temp. attribute. In summarize calculated Gain and Gain Ratios table you only provide Wind, Outlook, and Humidity 80 attributes. I confused because i have calculated all attributes and i found Gain = 0.113401 and Gain Ratio = 0.305472 for Temp. 83 which makes Temp. 83 comes with both maximized Gain and Gain Ratio and should be the root node ?

          1. Right, temp is missing and I’ve added it to summary table. But in this post I check gain instead of gain ratio and outlook’s gain is 0.246 and it is greater than the gain of temperature – it was 0.113 as you mentioned.

             1. Just to make sure is the exact rule are use max Gain to choose continuous attribute value from binary split process and then use max Gain Ratio for determine the root and branches ?

             2. Nope, you can either choose max gain or gain ratio to determine the root node. Both are true but you should choose one.

             3. So if i choose to use Gain i should use Gain to choose continuous attribute value from binary split process and use Gain too for determine the root node but, if choose to use Gain Ratio i should use Gain Ratio in choose continuous attribute value from binary split and determine the root node ?

             4. Exactly!

             5. One more question sir, which one should i choose when there is duplicate Gain or Gain Ratio, in this case i try use Gain Ratio metric and max Gain Ratio for Humidity is 0.128515 where it’s in Humidity 65 and Humidity 95

             6. Interesting case. I haven’t have a similar case before. You might try to find max gain ratio, if there is a duplicate record, then you might find the highest gain in this case. Because, both metrics are meaningful. If duplication still appears, then you might choose the first one.

          2. Additionally, I’ve put what would built decision tree look like if we use gain ratio metric. As you mentioned, temperature would be in the root node in this case.

13. Thanks for the post.
    I don’t understand one thing – you have calculated the best split for continuous values (humidity and temperature) globally. However, when the root node is Outlook, shouldn’t you calculate the best split again for the part of the tree we are already in?

    For example, in Figure 1, I think we should calculate the optimal split for the Humidity assuming that Outlook == Sunny, because we are already in a subspace defined by Outlook | Sunny.

    I’ve implemented your algorithm in my version and got the same tree apart from the value that Humidity should be splat on 🙂

    1. Hello, we already calculated the best splits again when outlook is the root node.

14. 1. if parent entropy is less than child entropy can we split the child node (can child node become subtree)?
    2. if one branch is pure set(4 yes/ 0 no) and another branch
    impure(3 yes / 3 no). what should we do now. can we split the impure node(3 yes/3no) when the parent entropy is less than child entropy?

    1. 2- I mostly return the first class for impure branches.
       1- Parent and child nodes are totally different. You should not split child node.

       1. Thank you so much for your immediate response. still more i shall ask question later. i just need some confirmation. so that i need to ask question. Thank you for your reply in advance.

15. after selecting outlook attribute as root node..
    we have three branches from outlook that is “sunny” ,” overcast” and “Rain” right…
    After this the next step you do, when you consider “outlook=sunny” then how table becomes short??? I cannot understand?

    1. I filtered the raw data set satisfying outlook==sunny instances. Then, I will calculate gain / gain ratio pair for this filtered data set.

16. Sir, can your library combine C4.5 and adaboost?
    Thanks

    1. No, it should not. Because adaboost uses a weak classifier (decision stamps) but C4.5 is strong enough.

17. How does the algorithm deal with missing values ‘?’ ??
    Please help!

    1. Suppose that your column has values in scale of [0, +∞]. If you set -1 to missing values, then the algorithm can handle to build decision trees now. To sum up, find the minimum value in that column, and set a smaller value to missing ones.

       1. Is such workaround the way the original C4.5 handles missing values?

          1. yes, the algorithm handles missing values by assigning some values such as avg

18. In the Gain ratio based C4.5 decision tree in the ‘Bonus’ section, I think the tree is wrong. In “outlook=sunny” -> “humidity>65” -> “wind=strong” -> “return no”, and also in “outlook=sunny” -> “humidity>65” -> “wind=weak” -> “return no”, I would like to tell you that there is 1 ‘yes’ decision each for wind=strong and wind=weak.

    Please have a look at the dataset and let me know if the decision tree given in ‘Bonus’ section perfectly works for the given dataset or not.

    1. The tree in the bonus section was built with information gain instead of gain ratio. It is all up to you choosing the metric. I mean that your tree is valid as well.

19. Thank you for your quick response of my previous question. I want to apply chefboost for analysis of different algorithms, how to apply it for confusion matrix with training and testing dataset?

    1. You need to call its prediction function extract confusion matrix by yourself. As I mentioned, I should add this feature in the next release.

       1. Thank you very much, waiting your next release….

20. May I know how the decision tree would look like if gain ratio metric is used? Temperature would be the root node because it has the highest gain ratio metric but how does it proceed from there?

    1. Actually, that tree is mentioned in the bonus section.

21. What i don’t realize is in truth how you’re now not actually much more well-appreciated than you may be right now. You are so intelligent. You know thus considerably in relation to this subject, produced me personally imagine it from numerous numerous angles. Its like women and men aren’t involved except it’s one thing to accomplish with Girl gaga! Your own stuffs nice. Always deal with it up!|

22. Hey Sefik, I really appreciate your effort on this wonderful library. Anyway, Is there any walkaround when testing using a raw, undiscritized test data? I’ve constructed the decision tree using a discritized train data (using Fayyad-Irani’s EBB) and when I tried to run a test on it, I got some error message instead.

    PS: For your information, I’m using traffic flow data so it’s all number.

    Thank you

    1. Could you share the dataset? I need it to understand the error.

       1. I’ve sent you an email with the dataset attached to it

23. Sir, I have a doubt regarding continuous dataset [Iris dataset], threshold value is found for continuous dataset. Then, based on the threshold value, which gives the highest gain ratio, the decision node is selected and the branches hold the value of threshold ‘less than or equal to [svalue]’ and ‘ greater than [svalue]’. My question is should we remove the best_attribute once selected or can we have that same attribute for next iteration also. [In ID3 we have to remove the best attribute once selected as decision node but in C4.5 algorithm that too in continuous dataset; what should we do sir?]

    1. you should remove that feature if it has the highest gain ratio value once

24. Thank you for your immediate response sir.

25. Feeling gratitude for your immediate response sir.

26. Sir, I am not good in Coding specially in Python . I don’t even know which code i need to write to get Split Info and Gain Ratio as well as Max Gain ratio.I tried non-numerical values dataset to implement C4.5 Algorithm. Can you please help this out. 🙏

27. Pingback: CSE1015 Machine Learning Essentials – Articles on NLP, Speech and Data Analytics

28. Hi, I have a question. If say the rules.py file is very large then do you have any method from which I can get a decision tree. as in any packages which can directly give the decision tree.

    1. rules.py is the decision tree itself

29. If gain ratio are same in all atributes then what we select for root node?

    1. You can select a random one in that case

Comments are closed.