rpart complexity parameter confusion

Question

I'm a little bit confused on the calculation for CP in the summary of an rpart object.

Take this example

df <- data.frame(x=c(1, 2, 3, 3, 3), 
                 y=factor(c("a", "a", "b", "a", "b")),
                 method="class")
mytree<-rpart(y ~ x, data = df, minbucket = 1, minsplit=1)
summary(mytree)

Call:
rpart(formula = y ~ x, data = df, minbucket = 1, minsplit = 1)
  n= 5 

    CP nsplit rel error xerror      xstd
1 0.50      0       1.0      1 0.5477226
2 0.01      1       0.5      2 0.4472136

Variable importance
  x 
100 

Node number 1: 5 observations,    complexity param=0.5
  predicted class=a  expected loss=0.4  P(node) =1
    class counts:     3     2
   probabilities: 0.600 0.400 
  left son=2 (2 obs) right son=3 (3 obs)
  Primary splits:
      x < 2.5 to the left,  improve=1.066667, (0 missing)

For the root node, I would've thought the CP should be 0.4 since the probability of misclassifying an element in the root is 0.4 and the tree size at the root is 0. How is 0.5 the correct CP?

Answer 1

As far as I know, the complexity parameter is not the error in that particular node. It is the amount by which splitting that node improved the relative error. So in your example, splitting the original root node dropped the relative error from 1.0 to 0.5, so the CP of the root node is 0.5. The CP of the next node is only 0.01 (which is the default limit for deciding when to consider splits). So splitting that node only resulted in an improvement of 0.01, so the tree building stopped there.

Answer 2

The complexity parameter $\alpha$ specifies how the cost of a tree $C(T)$ is penalized by the number of terminal nodes $|T|$, resulting in a regularized cost $C_{\alpha}(T)$ (see http://cran.r-project.org/web/packages/rpart/vignettes/longintro.pdf, Section 4).

$C_{\alpha}(T) = C(T) + \alpha |T|$

Small $\alpha$ results in larger trees and potential overfitting, large $\alpha$ in small trees and potential underfitting.

Answer 3

It is not particularly easy to follow the rpart calculations for classification. In addition, although the 'Long Intro' suggests that gini is used for classification, it seems that cost complexity pruning (and hence the values for cp) is reported based on accuracy rather than gini. In this case, we can work through the calculations and replicate the 0.4 queried in the original question. Firstly, create the tree

df <- data.frame(x=c(1,2,3,3,3), y=factor(c("a", "a", "b", "a", "b")))
mytree <- rpart(y ~ x, data = df, minbucket = 1, minsplit=1, method="class")

and then typing

print(mytree)

we get

node), split,  n, loss, yval, (yprob)
1)     root    5   2     a (0.6000000 0.4000000)  
2)     x< 2.5  2   0     a (1.0000000 0.0000000) *
3)     x>=2.5  3   1     b (0.3333333 0.6666667) *

The 'loss' column is not gini (which you might have expected it to be). It is the number of errors made.

The point at which this one split tree collapses (based on accuracy) is when

$$ 2 + \alpha * 1 = 1 + \alpha * 2$$

(where the first 2 above is the loss in the pruned tree and the second 2 is the number of terminal nodes in the full tree).

Solving for alpha, gives an alpha of 1.

As mentioned in an answer above, in the cptable, the error in the top line is scaled to 1 and then cp is scaled by the same amount. The error in the top line is the number of errors in a tree with no splits ie 2. Hence the alpha of 1 is scaled by dividing by 2 to give 0.50.

It is hard to read the C code in rpart, but the above is what I think it is doing.

Answer 4

I write to further validate the answers of both @joran and @fernando, and help someone like myself to further clarify how to interpret the cp matrix in an rpart obejct. If you observe the following code you will find that i have fitted a classification tree with two possible outcomes introducing my own loss matrix (FN are twice the cost of the FP).

Classification tree:
rpart(formula = Result ~ ., data = data, method = "class", parms = list(loss 
= PenaltyMatrix))                 

Root node error: 174/343 = 0.50729

n= 343 

    CP     nsplit  rel error xerror   xstd
1 0.066092      0   1.00000 0.50000 0.046311
2 0.040230      2   0.86782 0.73563 0.065081
3 0.034483      4   0.78736 0.91379 0.075656
4 0.022989      5   0.75287 1.01149 0.080396
5 0.019157      7   0.70690 1.17241 0.086526
6 0.011494     10   0.64943 1.21264 0.087764
7 0.010000     12   0.62644 1.31609 0.090890

Now if you observe for example step 6 on the matrix you can see that the number of splits increased by 3 (from 7 to 10) resulting to a relative error of 0.64943. Now if you subtract this error from the respective one on the previous step you will find an improvement of 0.05747, which in turn if devided by the number of extra splits between the steps 5-6 (which is three) results to aprroximately 0.01957, which is the complexity parameter of step 5. This can be validated in between all steps!

Now if I may i have a two-fold question to address to the community.

• It still bufles me what does it mean to have the xerror to continuously increase as the tree size grows?

• If i follow the so-called rule of thumb i have to select the tree with the smallest size that has an xerror within one standard deviation of the tree with the minimum xerror across the table. This in my case would be the tree in step 2 (because this is the one with the smallest xerror and 0.73563+0.065081=0.800711, which is not met by any other tree in the table). Is this correct?