0
$\begingroup$

Following is what I learned about the process followed during building and pruning a decision tree, mathematically (from Introduction to Machine Learning by Gareth James et al.):

  1. Use recursive binary splitting to grow a large tree on the training data, stopping only when each terminal node has fewer than some minimum number of observations.
  2. Apply cost complexity pruning to the large tree in order to obtain a sequence of best subtrees, as a function of α.
  3. Use K-fold cross-validation to choose α. That is, divide the training observations into K folds. For each k = 1, . . .,K: (a) Repeat Steps 1 and 2 on all but the kth fold of the training data. (b) Evaluate the mean squared prediction error on the data in the left-out kth fold, as a function of α. Average the results for each value of α, and pick α to minimize the average error.
  4. Return the subtree from Step 2 that corresponds to the chosen value of α. Error rate vs Leafs

My question: Going through the above algorithm means we automatically choose the most optimum tree based on minimum average error. Why then, do we have to select maximum depth as the pruning parameter. Shouldn't optimum depth be decided by the algorithm itself and not us?

If anything, shouldn't we be choosing 'K' here, as in how many-fold validation would we like to do?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Can you clarify pls, where is the suggestion, that we have to select max depth for pruning? As you said it is supposed to be done automatically due to some criterion. Here is some example of post-pruning:

https://stackoverflow.com/questions/49428469/pruning-decision-trees

Yes, we should select 'K' fold to leave some data for the test of pruning efficiency. How many? It depends on your data. You can check out this Stanford lecture slides, for example, where K = 10 is suggested:

https://web.stanford.edu/class/stats202/content/lec19.pdf

as an example. Usually, the K will depend on the size of your data, based on the size of the test fold you want to leave out.

Improve this answer
$\endgroup$
7
  • $\begingroup$ When we prune using sklearn, we have to specify max_depth. A max_depth of 'None' means it produces an unpruned tree. So, shouldn't we instead be choosing 'K' as in number of folds of CV instead? And the model should have been able to get the max_depth itself using cost complexity pruning method. $\endgroup$
    – Kuljeet Keshav
    Apr 28, 2020 at 17:03
  • $\begingroup$ @KuljeetKeshav I think you just misunderstanding it a little. You are specifying max depth not for pruning, but for regressor or classifier object. Then you are building the tree. And once the tree is built you can use pruning to prune it. If you will specify max_depth - it just won't be larger than it. So the max_depth is just the parameter of a model, not the prunning. $\endgroup$
    – Igor Belkov
    Apr 29, 2020 at 5:33
  • $\begingroup$ @KuljeetKeshav Here you can check out in the docs how the pruning is calculated in sklearn: scikit-learn.org/stable/modules/… $\endgroup$
    – Igor Belkov
    Apr 29, 2020 at 5:33
  • $\begingroup$ @KuljeetKeshav The point is the post pruning is taken place after the tree is already built, so it doesn't need any max_depth or smth like this because it will prune due to some criterion, not the depth. Here you can check out a couple of examples for custom written runners if it will help: matthewmcgonagle.github.io/blog/2018/09/13/PruningDecisionTree github.com/shenwanxiang/sklearn-post-prune-tree $\endgroup$
    – Igor Belkov
    Apr 29, 2020 at 5:38
  • $\begingroup$ @KuljeetKeshav and yes, it is not possible to choose K as a number of folds for CV just because it should be done separately with sklearn.model_selection modules, like KFold or cross_validate as in the any other model $\endgroup$
    – Igor Belkov
    Apr 29, 2020 at 5:40

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.