Notes
🔍

ID3

ID3 is one of the earliest “recipe-style” methods for building a decision tree classifier. It turns a labeled dataset into a flowchart of questions—each question splits the data to make the final class label as easy to predict as possible.

How ID3 builds a tree

ID3 (Iterative Dichotomiser 3) grows a tree top-down. At each node, it chooses the feature that best separates the classes, creates branches for that feature’s values, and repeats on each branch until the data is “pure” (mostly one class) or no useful splits remain. The key scoring idea is information gain, which measures how much a split reduces entropy (uncertainty) in the class labels. In plain terms: ID3 picks the question that most reduces confusion about the answer.

What it’s used for (and a concrete example)

Imagine a spam detector with features like “contains the word ‘free’?”, “sender in contacts?”, and “has an attachment?”. ID3 evaluates each candidate split and might start with the feature that most cleanly separates spam from not-spam. The resulting tree is easy to interpret: follow the branches and you can explain why an email was flagged. Similar setups appear in credit approval rules, churn prediction (“contract type?”, “late payments?”), or simple medical triage classifiers.

Why it matters and common limitations

  • ID3 popularized the modern decision-tree training loop: greedy splitting using an impurity measure.
  • It mainly targets categorical features; continuous features require extra handling (later algorithms formalized this).
  • Information gain can favor features with many distinct values, which can lead to overfitting.
  • Later tree learners like C4.5 and CART add stronger pruning and split rules; in scikit-learn, DecisionTreeClassifier follows the CART style rather than ID3.

ID3 (Iterative Dichotomiser 3) is a classic decision tree induction algorithm for classification that builds a tree top-down by selecting, at each node, the feature that maximizes information gain (entropy reduction) and splitting the data accordingly. It matters because it formalized entropy-based split selection, shaping later tree learners (e.g., C4.5/CART) and providing a clear baseline for interpretable, rule-based supervised models.

Think of a game of “20 Questions,” where each question is chosen to narrow down the answer as fast as possible. ID3 is an early method for building a decision tree that works in a similar way: it picks the next question (like “Is the email from someone you know?”) that best separates the examples into clear groups.

In supervised learning, you give the system many labeled examples (like emails marked “spam” or “not spam”). ID3 uses those examples to grow a tree of simple yes/no-style choices, so new cases can be classified by following the branches to a final decision.