How does Cross Validation work in decision trees (or tree ensembles)

Question

I've been working with tree-based models for a long time and I never really asked myself how cross-validation would work when building a tree.

For the sake of this question, suppose I've split my training dataset into four folds. Wouldn't each set of folds result in a different tree? If so, wouldn't you be averaging the testing error of K different models instead of estimating K instances of the test error of the same model?

For example, let's say I have 10,000 observations in my training dataset and I'm using four-fold cross-validation. If I train with folds 1, 2 and 3, I'll get a different model than if I train with folds 2, 3 and 4 because:

1. The features selected at each split will be different;
2. The cutoff points will be different even if the same features are selected; and
3. The trees will have different depths.

How do you interpret a cross-validated accuracy metric? The only thing that would make sense to me is to keep the same tree structure (features, order of features and cutoff values) and evaluate the model on the four folds. However, which of the four possible datasets is used to create the model's structure?

Answer 1

Requested from comments:

Cross-validation is the step for selecting the model including setting its hyperparameters: it is not about training the final model. So it could include the decision tree rather than some other method, and then for example deciding the maximum depth of the tree (as too shallow a tree could cause underfitting and too deep a tree cause overfitting).

Once you have decided the depth using cross-validation, you can train a tree to that depth using the whole training data, and that is your final model.

The cross-validation aims to tell you how good that choice of hyperparameters is on what aims to be unseen data (averaged over the folds) and you want to optimise that.

It is not perfect, partly because this optimisation can contaminate the process, which is why you may have held out a test set away from your training/cross-validation data to perform a final test on your final model (too late to make any changes).