Rules generation using ID3

A decision tree built by ID3 can be converted into IF-THEN classification rules. Each path from the root to a leaf gives one rule: the attribute tests along the path are joined by AND to form the condition (antecedent), and the leaf class is the consequent. The rules are mutually exclusive and exhaustive, and are easier for humans to read than a large tree.

Procedure

1. Build the tree using ID3: at each node pick the attribute with maximum information gain.
2. Traverse each root-to-leaf path.
3. Write IF (test1) AND (test2) ... THEN class = leaf.
4. Optionally simplify: drop a condition if accuracy does not fall (pruning of rules), and remove duplicate rules.

Example (Play Golf data, 14 records, 9 Yes, 5 No)

Entropy of the data = 0.940. Gains: Outlook 0.247, Humidity 0.152, Windy 0.048, Temperature 0.029. So Outlook is the root.

Outlook
 |-- Overcast --> Yes
 |-- Sunny    --> Humidity
 |                 |-- High   --> No
 |                 |-- Normal --> Yes
 |-- Rainy    --> Windy
                   |-- False --> Yes
                   |-- True  --> No

Rules generated

1. IF Outlook = Overcast THEN Play = Yes
2. IF Outlook = Sunny AND Humidity = High THEN Play = No
3. IF Outlook = Sunny AND Humidity = Normal THEN Play = Yes
4. IF Outlook = Rainy AND Windy = False THEN Play = Yes
5. IF Outlook = Rainy AND Windy = True THEN Play = No

Number of rules = number of leaves (5 here). A new tuple is classified by the first rule whose condition it satisfies.