I am currently working on a decision tree algorithm. As you might know, decision trees, as you add more inputs/nodes can get very specific, which although makes them good classifiers, also gives them the tendency to overfit.
To illustrate the point, say I have 3 features, each of which can take on 2 different values. I'f I'm not mistaken, on this simple tree, there would be 8 leaves (terminal nodes). Furthermore, let's say (1) the size of the training set is 100 samples, (2) this is a binary classification problem and (3) at the end of one of the leaves 100% of the samples end up in category 1, but this particular leaf only has 2 samples in it. I assume that one's confidence in the accuracy of this leaf dwindles when one takes into account that it only has 2% of the population in it. Therefore, I am curious to if there is any penalizing heuristic pertinent to decision tree that take sparsity of data into account?
To rephrase the question: Is there some heuristic that is used to calculate confidence based on diminished sample size? If for example this leaf is 100% accurate but only contains 2% of the population, but one level up is a node with 90% accuracy which contains 10% of the population, the algorithm would see the node with the higher population as the optimal node to base it's decision on?
Please let me know if my question needs revising or clarification of any kind. Thanks