# Decision tree without the "tree"

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.

• Do you need to determine the order of each decision (in your example: A then B then C) or the optimal threshold for each feature? Or both? Do you need your tree to perform only one test for each feature (i.e. can your tree look like: A $\rightarrow$ B $\rightarrow$ A $\rightarrow$ C $\rightarrow$ B)? Commented Oct 3, 2018 at 15:27
• Also: are you sure you want to build trees with all variables only? Those trees are likely to show a higher variance than smaller trees.
– jank
Commented Oct 3, 2018 at 19:22
• Decision tree with a single split is called stump. An ensemble of such stumps can be used in random forest. Commented Oct 3, 2018 at 20:20
• @RomainReboulleau I would like to constrain the tree so that it is only k levels deep. I would like to find the best order of features, and their optimal thresholds. I also need to perform only one test per feature. Commented Oct 3, 2018 at 22:21
• @jank I want to use a small subset of the total features. I anticipate I will need to do a greedy search? For example, my total dataset contains 1000 features, but I would like to constrain it to use only 5 features (i.e. splitting the feature space into 32 hyperblocks) Commented Oct 3, 2018 at 22:24

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


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.