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)? – Romain Reboulleau Oct 3 '18 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 Oct 3 '18 at 19:22
• Decision tree with a single split is called stump. An ensemble of such stumps can be used in random forest. – Jan Kukacka Oct 3 '18 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. – adn bps Oct 3 '18 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) – adn bps Oct 3 '18 at 22:24