1
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Penalizing as you would in l1 regression is difficult to reconcile with simple algorithms for greedy tree growth. You'd need to do some sort of global optimization of the tree which becomes unwieldy.

Pruning is the a common approach in single-decisiont-tree analysis but is rarely used in ensemble-of-tree methods like Random Forest (which this question is tagged with) where overfitting can be combated by either increasing the randomization of the models (via bagging, decreasing the number of features examined for each split or reducing the number of potential splits examined for each tree as in Extremely Randomized Trees).

You can also limit the complexity of the tree with a max depth or leaf size parameter.

In a Random Forest model I would do a parameter sweep of the number of in bag cases, the number of features examined and the leaf size or max tree depth and see if that achieves what you want.

Improve this answer
$\endgroup$
1
$\begingroup$

There are many such techniques, and they go by the name decision tree pruning. Some techniques I've seen are:

  • Prune a split if the change in class frequencies from the parent node is not statistically significant

  • Prune a split if pruning results in lower error on an independent test set

You can find lots more by searching.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But what would one do if: (1) the the statistical change is significant (going from 90% to 100%) but the confidence in that statistic is diminished (going form 10 samples to 2 samples) (2) and the lower error rate on the test set is dependent on the test set. One one test set, the 100% accuracy of the terminal node might be correct, but on a different test set it might not be? With classifiers such as SVM there is a penalizing variable, I am wondering if there is something like that for decision tree that calculates a tradeof between confidence and accuracy $\endgroup$
    – user3256725
    Jan 18, 2015 at 17:42
  • $\begingroup$ If you go from 1 out of 10 samples to 0 out of 2 samples, this is not statistically significant. $\endgroup$
    – Ben Kuhn
    Jan 18, 2015 at 17:46
  • $\begingroup$ The error-based pruning is dependent on the test set to some extent, but with a test set of reasonable size, it will average out statistically. If you're worried about this perhaps you can use bootstrap samples of the test set and see how much the pruning changes or something. $\endgroup$
    – Ben Kuhn
    Jan 18, 2015 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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