2
$\begingroup$

Assume the features in the dataframe are columns - A,B,C and my target is Y

Can my decision tree have a decision node which looks for say, if A>B then true else false?

$\endgroup$
4
$\begingroup$

Yes, but not in any implementation that I am aware of.

The idea is mentioned in Elements of Statistical Learning, near the end of section 9.2.4 under the heading "Linear Combination Splits." But this is not implemented in the popular CART or Quinlan-family of decision tree algorithms*, it is not done in sklearn's trees, and I do not know of any other python or R package that use it.

Some R packages do a more limited version, where a split can be made on two features, but these splits are of the form "$x_1>\alpha\text{ and }x_2\leq\beta$" as opposed to direct comparisons of the variables. See https://stats.stackexchange.com/questions/4356/does-rpart-use-multivariate-splits-by-default

An obvious problem is computational requirements: just checking over all pairs of features is now quadratic, and allowing arbitrary linear combinations of two features is potentially much much larger. On the other hand, if you want to restrict to direct comparisons $x_1\geq x_2$ (with no coefficients), that should be tractable (if substantially slower than CART). The Elements authors suggests Hierarchical Mixtures of Experts model instead if incorporating linear combinations is desired.

Oh, one more comment. If you really want splits like $x_1\geq x_2$, you could just generate all the features $x_i-x_j$; then a more common implementation of decision trees will be able to make your splits, when considering these new features. (Probably there will be some side effects, and still the computational problem arises: you've added $\binom{m}{2}$ features.)


* I've found a comment that suggests that CART does support multi-feature ("surrogate") splits?:
https://stackoverflow.com/a/9996741/10495893

$\endgroup$
1
  • $\begingroup$ Thank you for the detailed response. Very helpful $\endgroup$
    – Jerry
    Oct 1 '19 at 11:41

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.