On this page
John Ross Quinlan studied physics and computing at the University of Sydney (BSc, 1965) and earned a PhD in computer science at the University of Washington in 1968, according to his Wikipedia biography. He went on to invent ID3 and C4.5, two programs that turn a table of examples into a tree of questions. In 1997 he founded RuleQuest Research, and a commercial successor, C5.0, followed C4.5.
What problem was ID3 built to solve?
Early expert systems ran on rules drawn out of human specialists by interview. In his paper Induction of Decision Trees (Machine Learning, 1986), Quinlan notes that this ran at "a few rules per man day", while a complex system might need hundreds or thousands. Learning rules straight from examples was the way round that bottleneck.
The same paper dates ID3 to 1979 and traces it to Hunt's Concept Learning System. It was built for a task set by Donald Michie: decide from pattern-based features alone whether a King-Rook versus King-Knight chess position is lost for the Knight's side in a fixed number of ply (half-moves).
How does the ID3 algorithm choose each question?
A decision tree is a classifier whose inner nodes test one attribute, whose branches are the possible answers, and whose leaves name a class (Quinlan, 1986). ID3 builds it top down: at each node it picks the attribute that leaves the examples most sorted, splits on it, and repeats on each branch until every group holds one class.
"Most sorted" is measured with information theory. For p examples of class P and n of class N, the information needed to classify an example is I(p, n) = −(p/(p+n)) log2(p/(p+n)) − (n/(p+n)) log2(n/(p+n)) bits. ID3 computes E(A), the weighted average of I over the branches of attribute A, and chooses the attribute with the largest gain(A) = I(p, n) − E(A). The paper credits the idea to a suggestion from Peter Gacs.
Worked example: Quinlan's 14 Saturday mornings
Table 1 of the 1986 paper lists 14 mornings described by outlook, temperature, humidity and windy, with 9 labelled P (suitable for some activity) and 5 labelled N.
Start: I(9, 5) = −(9/14) log2(9/14) − (5/14) log2(5/14) = 0.940 bits.
Split on outlook: sunny has 2 P and 3 N, overcast 4 P and 0 N, rain 3 P and 2 N.
Branch information: I(2, 3) = 0.971, I(4, 0) = 0, I(3, 2) = 0.971.
Weighted average: E(outlook) = (5/14)(0.971) + (4/14)(0) + (5/14)(0.971) = 0.694 bits.
Gain: 0.940 − 0.694 = 0.246 bits.
Now try humidity: high mornings are 3 P and 4 N, normal are 6 P and 1 N. You should get E = 0.788 and a gain of about 0.152 bits; the paper prints 0.151, a rounding difference. Temperature (0.029) and windy (0.048) do worse, so outlook wins. Repeat inside each branch and you get the tree pictured above.
If the log2 step is where you stall, the Fermi Concept Library has a lesson for each concept in mathematics and computing, so you can revisit logarithms first.
Did ID3 work on real data?
In one chess domain of 715 distinct positions, trees grown from random 20% samples correctly classified over 84% of the unseen ones; in a simpler domain of 1,987 objects, the figure was 98% (Quinlan, 1986). Testing on unseen cases still catches a model that has memorised its data; see what overfitting is, with a past-paper analogy.
What did C4.5 add to ID3?
Quinlan's book C4.5: Programs for Machine Learning appeared in 1993. The survey Top 10 algorithms in data mining (Knowledge and Information Systems, 2008), which Quinlan co-wrote, lists the main changes:
Gain ratio by default, because plain information gain is heavily biased towards tests with many outcomes.
Numeric attributes split at a threshold, A ≤ h or A > h, found by sorting the values.
Pruning from the leaves upward, using a pessimistic error estimate with a default confidence of 0.25, to avoid overfitting.
Unknown values handled by sharing a case probabilistically among the branches.
Rulesets of the form "if A and B then class X", easier to read than a large tree.
The same paper reports that the IEEE International Conference on Data Mining identified its top 10 algorithms in 2006 through nominations and votes; C4.5 is named first. Leo Breiman later grew whole forests of trees; read who invented random forests.
How can you build your own ID3 tree this week?
Log 12 to 15 days of your own data: sleep (good or poor), phone in the room (yes or no), and the class "finished my target" (P or N).
Compute I(p, n) for the whole set and the gain for each attribute. Split on the winner.
Repeat inside each branch, draw the tree, and test it on three days you held back.
For a guided version with a scoring sheet, try our activity to build a decision tree on paper. If a gain calculation keeps going wrong, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
