How does the complexity parameter correspond to the number of splits in cross validation in rpart?

Question

library(rpart)
tree = rpart(Kyphosis ~ ., data=kyphosis, control=rpart.control(minsplit = 1, cp = 0, xval=10))
plotcp(tree,  minline = FALSE, upper=c("splits"))

From what I understand xval=10 corresponds to 10-fold cross validation. So the rpart algorithm will build 10 different trees (not pruned and until all training examples are classified as best as possible [controlling this with minsplit=1, cp=0]... which means my tree will potentially be overfit). Then the algorithm goes through each tree and calculates its error rate on the testing set that was held out. Next it looks through all the complexity parameters (cp) and determines how the tree would have done on the testing set had that complexity parameter (cp) been used. My questions:

• How does the number of splits directly correspond to a complexity parameter? Aren't there 10 different trees being built and the complexity parameter would work differently on each?

• What is the final tree that is returned? It doesn't seem to be one of the 10 made during cross validation since it's leaves contain the total dataset?

Answer 1

There is one tree created, which is definitely overfitting the data. The specified minsplit essentially creates a tree that categorizes each terminal node into either all "present" or all "absent". rpart will not prune the tree for you, but can provide cross-validation for you to select the best subtree (i.e. select the complexity parameter $\alpha$). The best tree is any subset of the initial tree; below are a few options:

library(rpart.plot)
prp(tree,extra=1) #Initial tree with 16 splits
prp(prune(tree,cp=0.042),extra=1) #Subtree with 10 splits
prp(prune(tree,cp=0.068),extra=1) #Subtree with 5 splits
prp(prune(tree,cp=0.14),extra=1) #Subtree with 1 split

To decide which subtree is best, we have to perform cross-validation. First we have to determine the possible $\alpha$'s that would yield a subtree (from the initial tree). Then we divide the data into 10 groups and build 10 trees with the 'leave one group out' approach using a possible $\alpha$ to prune the tree. The left out group can determine which $\alpha$ worked best. The technical details can be seen in the rpart vignette

The final tree that is returned is still the initial tree. You must use the prune function using the cross-validation plot to choose the best subtree. For this dataset, I don't think CART fits the data that well. If you perform 81-fold cross-validation (i.e. leave one observation out), you'll see five splits seems like the best tree. If you're looking for a model with better prediction accuracy, perhaps you should consider building a random forest.