trouble in computing generalization error rate of the decision tree

Question

This is a picture from the book introduction to data mining.

I cannot understand this decision tree. Why the label in leaf node where A=1 && C=0 is '+' instead of '-'. From the table, it is clearly that there are 3 '-' and 2 '+'.
Besides, I think that generalization error rate equals (0 + 1 + 2 + 1) / 10 = 0.4. Is it correct? Thanks.

Answer 1

I would guess that this is either part of the exercise (i.e., to figure out that the tree is not optimal) or a typo (i.e., the labels should be -/+ rather than +/- after the split in C).

To be able to play around with the data more easily I encoded the tree in R using the partykit package. First, I set up the tree as shown in Figure 4.30. Then I turn the tree into a constant-fit tree(a constparty object) where the predictions in each leaf are re-computed based on the observed responses. Finally, I obtain the confusion matrices on the training and validation data, respectively.

The complete data is:

Exercise8 <- data.frame(
  A = factor(c(0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1)),
  B = factor(c(0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0)),
  C = factor(c(0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0)),
  Class = factor(c("+", "+", "+", "-", "+", "+", "-", "+",
    "-", "-", "+", "+", "+", "-", "+"))
)

This can be split up into training and validation data:

Training <- Exercise8[1:10, ]
Validation <- Exercise8[11:15, ]

Then we set up the tree as shown in the picture

library("partykit")
Tree <- party(
  partynode(1L,
    split = partysplit(varid = 1L, index = 1:2),
    kids = list(
      partynode(2L,
        split = partysplit(varid = 2L, index = 1:2),
        kids = list(
          partynode(3L, info = "+"),
          partynode(4L, info = "-"))),
      partynode(5L,
        split = partysplit(varid = 3L, index = 1:2),
        kids = list(
          partynode(6L, info = "+"),
          partynode(7L, info = "-"))))),
  data = Training,
  terms = terms(Class ~ A + B + C)
)
plot(Tree)

When we turn the tree into a constparty tree, the predictions are re-computed from the observed responses and the visualization can also show the full distribution:

Tree$fitted[["(response)"]] <- Training$Class
Tree <- as.constparty(Tree)
plot(Tree, tp_args = list(beside = TRUE))

This shows that the tree printed in the book is clearly not the optimal one. (As I said above, this may be the point of the exercise...)

The in-sample (training) and out-of-sample (validation) confusion matrices are given below. Then, misclassification rates etc. can be easily computed by hand:

table(True = Training$Class, Predict = predict(Tree, Training))
##     Predict
## True + -
##    + 4 2
##    - 1 3
table(True = Validation$Class, Predict = predict(Tree, Validation))
##     Predict
## True + -
##    + 2 2
##    - 1 0