CART for regression: Avoid impossible combinations

I want to predict a categorical variable using also categorical predictors. Currently, I am looking at classification and regression trees (CART).

The prediction quality is "good enough", except for the presence of impossible combinations. In the following minimal example, the combination a==2, b==2 is impossible, yet the estimation decides not to use b for splitting.

> library(rpart)
> d <- data.frame(a=rep(factor(c(1,1,2)), 100000), b=factor(c(1,2,1)))
> xtabs(~., d)
b
a       1     2
1 1e+05 1e+05
2 1e+05 0e+00
> (tr <- rpart(a~b, d))
n= 300000

node), split, n, loss, yval, (yprob)
* denotes terminal node

1) root 300000 1e+05 1 (0.6666667 0.3333333) *

When simulating stochastically from this model (by choosing the leaf value by sampling using the annotated probability vector, here $(2/3, 1/3)$, as weights), the combination 2, 2 will occur:

> prob.m <- predict(tr, d, type="prob")
> d$a.sim <- apply(prob.m, 1, function(x) sample.int(length(x), size=1, prob=x)) > xtabs(~a.sim+b, d) b a.sim 1 2 1 133041 66615 2 66959 33385 Is there a way to avoid this, perhaps using another method? This is just a small example for a more general case. I have around 10 predictors, and I want to exclude all combinations of two (or perhaps three) attributes that have no observation in the sample. I am aware of the "loss matrix" that can be specified as a parameter to rpart, but this is prohibitive if many predictors are used. • What do you mean, "the combination 2, 2 will occur". Your model is just the root, so whether you try to get a predicted class from a = 1 or 2, you'll get b = 1. Aug 15, 2013 at 11:19 • @HongOoi: Not if I predict stochastically, i.e. use the vector$(2/3, 1/3)$(in the root node) as probabilites to sample from. Will update my questions. Aug 15, 2013 at 11:21 • What if you make 'b' a factor as well? Aug 15, 2013 at 11:44 • @PeterFlom: My mistake, but this doesn't change the output. Aug 15, 2013 at 11:58 • The toy example is a little silly.... and "predicting statistically" from this toy example is more silly. In your actual data, do any nodes include only impossible combinations? Aug 15, 2013 at 12:04 2 Answers Force rpart to split down to a single observation per node: rpart(a~b, d, control=rpart.control(minsplit=1, minbucket=1, cp=-1)) (The value cp=-1 means to stop splitting if the improvement in cp is less than or equal to -1. This is just a way of taking this criterion out of the picture.) • How will this affect the generalization error (see my edit, second-to-last paragraph)? I want a model after all, not a replication of the dataset... Aug 15, 2013 at 11:35 • Are you not risking generalisation error by arbitrarily excluding "impossible" response levels, without prior knowledge of what counts as impossible? Aug 15, 2013 at 11:38 • Not in this particular case. I have more than$10^5\$ observations, and if a particular combination of two or three attributes (with up to six classes in each attribute) doesn't occur, I consider it impossible. Aug 15, 2013 at 11:59
• However, cp=-1 does help indeed. Thank you! Aug 15, 2013 at 12:06
• @krlmlr I would strongly advise against doing this! With these options (as HongOoi implies) you'll be hopelessly overfitting the response. This might help the toy example fit a more complex tree, but you still need to prune it back using the cost-complexity value under crossvalidation. Aug 15, 2013 at 14:45

Thanks for updating the post to have a large sample size.

I think the 'solution' is now clear: There isn't a problem!

In one of your comments you note that with your actual data, no nodes include only impossible values. So, no problem there.

In the example with huge N, again the tree creates only a root node: That is, it performs as it should.

• I'm sorry, I should have added simulation results right from the start. See my edit. I don't expect the combination (2,2) to be generated at all. The situation in the original data is very similar. Aug 15, 2013 at 13:06