Induction of decision trees

Inside the paper

The problem

Expert systems need explicit knowledge, but extracting rules from specialists can be slow. Learning a decision tree from classified examples offers a way to build a classifier that can be inspected as a sequence of tests.

The idea

Build the tree from the top down by choosing an attribute that separates the examples well, then repeat the choice within each resulting group. The paper also considers how to adapt the procedure to noisy and incomplete data.

How it works

• At a node, assess candidate attributes by how much their tests reduce uncertainty about the examples' classes.
• Split the examples by the selected attribute's values, and recursively construct a subtree for each resulting group.
• Stop when the examples reaching a node belong to a single class, making that node a leaf.
• For unknown attribute values, distribute affected examples across branches according to the frequencies of known values rather than treating unknown as an ordinary value.

What it showed

The paper describes ID3 and presents experiments on noise, missing values and attribute selection. In its missing-value experiment, classification performance degrades gradually as more values are hidden.

Read it for

Section 4 walks through ID3 and information gain, while Sections 5 and 6 examine noise and missing values. Section 7 considers a bias in the selection criterion; skim its comparison on a first pass and return when choosing attributes matters.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.