19
$\begingroup$

Nearly every decision tree example I've come across happens to be a binary tree. Is this pretty much universal? Do most of the standard algorithms (C4.5, CART, etc.) only support binary trees? From what I gather, CHAID is not limited to binary trees, but that seems to be an exception.

A two-way split followed by another two-way split on one of the children is not the same thing as a single three-way split. This might be an academic point, but I'm trying to make sure I understand the most common use-cases.

$\endgroup$
16
$\begingroup$

This is mainly a technical issue: if you don't restrict to binary choices, there are simply too many possibilities for the next split in the tree. So you are definitely right in all the points made in your question.

Be aware that most tree-type algorithms work stepwise and are even as such not guaranteed to give the best possible result. This is just one extra caveat.

For most practical purposes, though not during the building/pruning of the tree, the two kinds of splits are equivalent, though, given that they appear immediately after each other.

$\endgroup$
  • $\begingroup$ Just to amplify on your first point: The number of possible splits goes up exponentially. If you are splitting on a continuous variable that has 1000 distinct values, there are 999 binary splits, but 999*998 trinary splits. $\endgroup$ – Peter Flom Jun 22 '11 at 11:45
  • 2
    $\begingroup$ @Peter There are $\binom{1000-1}{3-1} = 999*998/2$ ternary splits, actually. $\endgroup$ – whuber Jul 26 '11 at 18:54
4
$\begingroup$

A two-way split followed by another two-way split on one of the children is not the same thing as a single three-way split

I'm not sure what you mean here. Any multi-way split can be represented as a series of two-way splits. For a three-way split, you can split into A, B, and C by first splitting into A&B versus C and then splitting out A from B.

A given algorithm might not choose that particular sequence (especially if, like most algorithms, it's greedy), but it certainly could. And if any randomization or stagewise procedures are done like in random forests or boosted trees, the chances of finding the right sequence of splits goes up. As others have pointed out, multi-way splits are computationally costly, so given these alternatives, most researchers seem to have chosen binary splits.

Hope this helps

$\endgroup$
  • 3
    $\begingroup$ Yes I understand that A, B, and C can be achieved by first splitting into A&B vs. C and then splitting A from B. My point was indeed that a given algorithm might not choose that particular sequence. $\endgroup$ – Michael McGowan Jun 22 '11 at 15:46
2
$\begingroup$

Regarding uses of decision tree and splitting (binary versus otherwise), I only know of CHAID that has non-binary splits but there are likely others. For me, the main use of a non binary split is in data mining exercises where I am looking at how to optimally bin a nominal variable with many levels. A series of binary splits is not as useful as a grouping done by CHAID.

$\endgroup$
  • $\begingroup$ It's funny that you mentioned binning, because thinking about binning is what made me start wondering about this question (although I was thinking about binning numeric variables rather than nominal variables). $\endgroup$ – Michael McGowan Jun 22 '11 at 15:54
  • $\begingroup$ @Michael, Yes that works too but you throw away information. I use it when i need to combine sparse levels of a nominal variable - when the ultimate modeling will be done without a tree type approach (say logistic regression or SVM and many sparse dummy variables causes issues) $\endgroup$ – B_Miner Jun 29 '11 at 13:57
0
$\begingroup$

Please read this

For practical reasons (combinatorial explosion) most libraries implement decision trees with binary splits. The nice thing is that they are NP-complete (Hyafil, Laurent, and Ronald L. Rivest. "Constructing optimal binary decision trees is NP-complete." Information Processing Letters 5.1 (1976): 15-17.)

$\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.