What is the Difference between TDIDT, ID3, CART, and C4.5?

My main concern is about TDIDT, Is it first ever algorithm that came with Decision trees?

Is it predecessor or successor of ID3, CART, and C4.5?

What are the differences to others(ID3, CART, and C4.5?)?


TDIDT stands for "top-down induction of decision trees"; I haven't found evidence that it refers to a specific algorithm, rather just to the greedy top-down construction method. Therefore (seemingly) all the other algorithms you mention are implementations of TDIDT. The first iteration is due to Hunt, the "Concept Learning System" in 1966.

ID3 is due to Quinlan in 1979, improving upon the CLS. (Fun fact: it was originally designed to tackle the problem of deciding winnability of King-rook vs king-knight chess endgames.) This was further improved to C4.5, then to C5.0. This branch only works for classification.

CART ("classification and regression trees") was developed roughly in parallel with ID3, by Breiman, Friedman, Stone and Olshen in 1984. As the name suggests, this branch allows prediction of continuous variables.

The main differences between branches is how splits are determined, using different metrics. Early on it seems there were differences in handling missing data and such, but these appear to have mostly been included in all the more recent iterations.

Of course, there have been numerous other improvements or variations. Some (historical?) tree building algorithms generate nonbinary trees, some make splits on linear combinations of features instead of just one at a time, some try to reduce the greedy nature of the algorithm by looking ahead, some produce regression models in each leaf instead of constant functions, ...

W-Y Loh, "A Brief History of Classification and Regression Trees" (slides)
Lecture slides (Aida Nordman?)
Quinlan's 1986 paper
similar question on Quora
similar SO question
C5.0 introduction


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.