# Regression Tree with nested factors

I am working on a prediction model in which I have several factor variables that have many levels. These factor variables have a nested structure, in the form of a Category, a Sub-Category, and a Sub-Sub-Category. For example suppose that I had one field that was the type of device a user browsed the website with (pc, tablet, phone), which then can be sub segmented into ((Apple, windows, linux), (kindle, iOS, android), (windows, iOS, android, RIM)), and then each of those could be subdivided into version numbers.

Is there a standard way of handling nested features like this in tree models. At an intuitive level, I don't think the tree should be splitting on one of the subgroupings until it has first split on one of the major groups (since a windows phone and a windows PC are quite different). Creating a single factor that describes the full tree path would have too many possible levels.

• I'm not an expert in decision trees, but I think your intuition is right and in fact suggests that a tree is inappropriate for nested factors. The task implies fully crossed factors: among them, the strongest predictor is being searched. Imagine Win/Linux strongly differentiate people on the predictand, but can do it only in part of sample - for those using PC. But since you need all the sample to be differentiated at level 1, you have but to prioretize the PC/Phone variable instead, simply because it is the only variable relevant to everybody. The same fallacy repeats on every level. Nov 14, 2013 at 8:26
• I would recommend using a mixed linear model (like those offered in the R package lme4) for this type of problem. I've also found that straight up (regularized, if necessary) linear models work well also, even if they do ignore the hierarchical nature of the data.
– alex
Nov 19, 2013 at 20:34

In the decision tree module that you can get for SPSS, the option of forcing a primary variable is available. You can use the option for the type of device. Hopefully, forcing this structure may lend your model to being more parallel with your intuition. I am unfamiliar with techniques to achieve the same result in R. Stratifying your data into device type first and then creating individual trees (like Raff mentions) may be another avenue to approach that could reveal some useful information.

• The problem with this is that I do not "know" that these nested categories are actually important to the model, they are just a few out of a large number of covariates that I want the tree to choose between. Nov 21, 2013 at 0:40

A simple way to handle this is to make a "tree" of models. The first model (hopefully) predicts the correct Category. Then for each Category, we train a sub model for each Sub-Category that belongs to the given category. And so on. This can be used for any model building algorithm.

Another alternative would be to define your own loss function for which getting the wrong category is a bigger loss than the wrong sub-category, and so on. Then you could use SGD or some other technique to learn directly based on your desire to avoid such errors.

In a similar vein, there is a lot of research on cost sensitive classification. You could use this, where things int he same sub-categories have lower costs for miss classification than getting the wrong category.

• The variables which are divided by category, sub-category etc. are input, not output, variables. Nov 20, 2013 at 2:44

In your case (device/OS) I believe there are two reasonable splits: * split the set of devices * some OSes of one device vs everything else

Generally, monophyletic splits (one of the two subsets consists of categories of depth n which all belong to the same category of depth n-1) seem more reasonable than any other choice.

• Yes, this is my thought about what sort of splits are reasonable, but I am unsure of whether any existing tree packages allow for this sort of constraint or whether I need to code a new one myself. Nov 20, 2013 at 21:07