I was reading about decision trees and this is what I understood:

We build decision trees by choosing an attribute and building subtrees (which are also decision trees) as children of the node representing that attribute. This means that as we go down, in building a decision tree, the no. of training instances that we use to build a subtree decreases. This is because when we build a subtree, we only have to train it using a subset of the original data consisting of instances which satisfy the conditions on the path towards the root node of the subtree.

Now here's the question: We usually believe that if training data is not enough, the model built is incorrect. This would mean that the subtrees down in a decision tree may not be good models (as they were trained using much less data than its ancestors in the tree) and if they are not, how can they be recursively combined to give a full tree which may give a good model? Where is the fault in my reasoning?

  • $\begingroup$ Can you specify exactly which decision tree learning algorithm you are using. It is hard to answer a question like this. $\endgroup$ – InformedA Aug 7 '14 at 10:19
  • 1
    $\begingroup$ Its the C4.5 algorithm which I was reading about. $\endgroup$ – swanar Aug 7 '14 at 10:26
  • 1
    $\begingroup$ The very quick and simple answer is that every time you go further into a subtree, the set of attributes you will need to learn is reduced. You need to learn a simpler subtree. Therefore, the reduction in the number of test cases for the simpler subtree is normal. $\endgroup$ – InformedA Aug 7 '14 at 10:39
  • $\begingroup$ So from the above, is it safe to assume that if the number of attributes is less, the statement that "we require high amounts of training instances to build a good classifier" does no longer hold true? Infact, does it mean that the statement, "we require higher amounts of data to build a good classifer", is a false one, in general? $\endgroup$ – swanar Aug 7 '14 at 11:47
  • $\begingroup$ No, not in the way you word it. It means that if the number of attributes is less (than some other situation) then you need less data (than the data you need in the other situation). Here the other situation is the situation where we learn the bigger upper tree. $\endgroup$ – InformedA Aug 7 '14 at 12:09

Your question is a good one and note that in the extreme case, if every leaf node contains only one data point then you are almost certainly over-fitting and/or missing the "true" dimensions that separate the two points above. One way around this problem is to not split at a node (make it a leaf) if it contains fewer than C points, where C is something like 10. Also, a decision tree in the Brieman/Cutler framework uses $\sqrt{N}$ randomly chosen dimensions to try to split on, at a node with N points. Thus you are somewhat avoiding over-fitting because of this (but it's random so it's not very reassuring). The best solution is to create many (like 100 or more) bootstrap replicates of your data and build a decision tree for each bootstrap replicate. Then for prediction, you run the point through all 100 trees and take the average of the prediction indicator vectors to get predicted class probabilities. You can take the highest probability to be the predicted class. This strategy is much more robust to over-fitting because splits with low data support in one tree will only appear in the majority of trees (either exactly or approximately) if they have higher overall data support.

| cite | improve this answer | |
  • $\begingroup$ Interesting, do you know a table or paper that rank all the methods for learning decision trees? $\endgroup$ – InformedA Aug 8 '14 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.