0
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.