Decision tree without the "tree"

Question

I would like to construct something like a decision tree. However, instead of using "recursive partitioning" to build a tree, I would like to find an optimal set of "global" splits.

For example, in a normal decision tree, you might have something like this:

1) root
    2) A >= 1
        4) B >= 1
        5) B < 1
    3) A < 1
        6) C >= 1
        7) C < 1

Here, you only use variable "B" when the value of "A" is greater than 1 (but not when "A" is less than 1). However, I want to find a set of "global" variables that are not conditioned on each other. For example, these three splits would divide the feature space into 8 blocks:

1) A >= 1
2) B >= 1
3) C >= 1

In terms of a decision tree, I only want to consider decision trees that look like this (note: each path in the tree uses ALL of the splits defined above):

1) root
    2) A >= 1
        4) B >= 1
            8) C >= 1
            9) C <= 1
        5) B < 1
            10) C >= 1
            11) C <= 1
    3) A < 1
        6) B >= 1
            12) C >= 1
            13) C <= 1
        7) B < 1
            14) C >= 1
            15) C <= 1

I have done a lot of searching and I cannot figure out how to do this. If anyone can point me in the right direction, I would REALLY appreciate it.

I have looked into other approaches, like Naive Bayes and regression. Naive Bayes seems like it might be similar in concept, but it does not partition the feature space into "p-dimensional hyperblocks". I have looked into using lasso regression, but because this is multi-class classification, there is nothing constraining the model to use the same variables across the classes.

Answer 1

I am not aware of this method already existing, but assuming a continuous, or at least ordered response, this sounds like tree boosting with a learning rate of 1, maximum tree depth of 1 and a maximum of 5 iterations. (If you have a response from a different GLM family, the same applies, but obtaining the pseudo-response will involve slightly more computation). The following code does such a thing:

> airq <- airquality[complete.cases(airquality), ]
> library("partykit")
> data <- airq
> splitvars <- c() 
> partvars <- names(airq)[-1]
> trees <- list()
> for (i in 1:5) {
+   form <- as.formula(paste0("Ozone ~ ", paste(partvars, collapse = " + ")))
+   ## Find split:
+   tree <- ctree(form, data = data, maxdepth = 1)
+   if (length(tree) < 3) {
+     print(paste("Exiting: Tree of depth 0 grown in iteration", i))
+     break
+   }
+   splitvars <- c(splitvars, names(data)[tree[[1]]$node$split$varid])
+   partvars <- partvars[!partvars %in% splitvars]
+   trees[[i]] <- tree
+   ## Update response (i.e., boosting with learning rate of 1):
+   data$Ozone <- data$Ozone - predict(tree)
+ }
[1] "Exiting: Tree of depth 0 grown in iteration 3"
> ## Inspect results:
> splitvars
[1] "Temp" "Wind"
> trees
[[1]]

Model formula:
Ozone ~ Solar.R + Wind + Temp + Month + Day

Fitted party:
[1] root
|   [2] Temp <= 82: 26.779 (n = 77, err = 42143.2)
|   [3] Temp > 82: 76.794 (n = 34, err = 20659.6)

Number of inner nodes:    1
Number of terminal nodes: 2

[[2]]

Model formula:
Ozone ~ Solar.R + Wind + Month + Day

Fitted party:
[1] root
|   [2] Wind <= 5.7: 32.958 (n = 12, err = 22615.1)
|   [3] Wind > 5.7: -3.995 (n = 99, err = 25572.6)

Number of inner nodes:    1
Number of terminal nodes: 2

> ## Obtain predictions:
> preds <- rowSums(sapply(trees, predict, newdata = airq))
> cor(preds, airq$Ozone)
[1] 0.7848191

Answer 2

What you are looking for may be called regularized trees. Have a look at this paper: Feature Selection via Regularized Trees. It seems to provide a framework to do exactly what you need.