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$
7
  • 1
    $\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$ Commented Oct 3, 2018 at 15:27
  • 1
    $\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
    Commented Oct 3, 2018 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$ Commented Oct 3, 2018 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
    Commented Oct 3, 2018 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
    Commented Oct 3, 2018 at 22:24

2 Answers 2

3
$\begingroup$

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
$\endgroup$
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 and acknowledge you have read our privacy policy.

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