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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Why are two sequential binary splits not the same as a single 3-way split? $\endgroup$
    – Sycorax ♦
    Commented Jul 19, 2023 at 0:06
  • $\begingroup$ @Sycorax-OnStrike, the greedy learning procedures listed see them differently at least (see this answer below). Pruning procedures might care, too. $\endgroup$
    – Ben Reiniger
    Commented Jul 19, 2023 at 2:33

5 Answers 5

Reset to default
29
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jun 22, 2011 at 11:45
  • 5
    $\begingroup$ @Peter There are $\binom{1000-1}{3-1} = 999*998/2$ ternary splits, actually. $\endgroup$
    – whuber ♦
    Commented Jul 26, 2011 at 18:54
9
$\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.

Improve this answer
$\endgroup$
1
  • 5
    $\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
    Commented Jun 22, 2011 at 15:46
6
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jun 22, 2011 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
    Commented Jun 29, 2011 at 13:57
4
$\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.)

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Why is it a nice thing that they are NP-complete? $\endgroup$
    – Mehdi Charife
    Commented Jul 18, 2023 at 20:29
1
$\begingroup$

The Quinlan family of tree models (including the C4.5 you mention) makes higher-arity splits for nominal variables, one branch for each level.

Improve this answer
$\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.