vizlearn
Home / Machine Learning

Decision Tree (ID3)

A supervised learning algorithm that recursively splits data based on attributes yielding the highest Information Gain to form a predictive tree.

Node Data

Subset: Root

Splitting Actions

Decision Arena

Active Selected Leaf
Click a node to inspect its data or use the controls to split the active node.

Building a Decision Tree (ID3)

A Decision Tree is one of the most intuitive and interpretable models in machine learning. It makes predictions by learning a series of simple "if-then-else" rules from the data, forming a tree-like structure. This lab visualizes the ID3 (Iterative Dichotomiser 3) algorithm, which builds the tree by asking one simple question at each step: "Which feature gives me the most information to help classify my data?"

The Core Idea: Maximizing Information Gain

The goal of the ID3 algorithm is to build a tree that separates the data into pure groups (i.e., groups containing only a single class) as efficiently as possible. It does this by choosing the best feature to split on at each node. The "best" feature is the one that results in the most significant reduction in uncertainty, a concept measured by Information Gain.

Entropy: A Measure of Impurity

First, we measure the "impurity" or "randomness" of a set of data using a metric called Entropy. A dataset with a perfect mix of all classes (e.g., 50% 'Yes', 50% 'No') has the highest entropy (maximum uncertainty). A dataset with only one class (e.g., 100% 'Yes') has zero entropy (perfect certainty).

Information Gain: The Reduction in Entropy

For each feature, the algorithm calculates what the entropy would be after splitting the data based on that feature's values. Information Gain is simply the initial entropy minus the weighted average entropy after the split. The feature with the highest information gain is chosen for the split because it does the best job of creating purer, more organized subgroups.

How to Use the Interactive Lab

This lab lets you manually build a decision tree step-by-step to understand the ID3 algorithm's logic.

  • The Data: The table on the left shows the dataset for the currently selected node (initially, the whole dataset). The goal is to predict whether to 'Play' based on 'Outlook', 'Temp', 'Humidity', and 'Wind'.
  • Splitting Actions: The buttons under "Splitting Actions" correspond to the available features you can use to split the current node. Clicking one will show you the Information Gain for that split.
  • Building the Tree: When you click a split button (e.g., "Split on Outlook"), the tree in the "Decision Arena" expands. New child nodes are created, each containing the subset of data corresponding to a value of that feature (e.g., 'Sunny', 'Overcast', 'Rain').
  • Leaf Nodes: The process stops at a node when all data points in it belong to the same class. This is a "pure" node and becomes a leaf node (colored green), which makes the final prediction.

Guided Experiments

Follow these steps to see the algorithm in action.

  1. Find the Best First Split: Start with the root node selected. Click each of the four split buttons ('Outlook', 'Temp', etc.). Observe the Information Gain value displayed for each. You'll notice that 'Outlook' provides the highest gain. This is the split the ID3 algorithm would choose automatically. Click the "Best Split" button to confirm this.
  2. Follow a Path to a Leaf Node: After splitting on 'Outlook', the tree has three new nodes. Click on the 'Overcast' node. Look at the data table on the left. You'll see that all four data points in this subset have a 'Play' value of 'Yes'. This is a pure node! The algorithm stops here and creates a leaf node that predicts 'Yes'.
  3. Perform a Recursive Split: Now, select the 'Sunny' node. The data subset for this node is still impure (it contains both 'Yes' and 'No' values). You can split it again! Check the Information Gain for the remaining features ('Temp', 'Humidity', 'Wind'). Find the best feature to split the 'Sunny' node and continue the process until all branches end in pure leaf nodes.

Key Takeaways

  • Greedy Algorithm: ID3 is a "greedy" algorithm. At each step, it picks the split that looks best at that moment (the one with the highest Information Gain) without looking ahead to see if a different choice might lead to a better overall tree.
  • Interpretability is a Superpower: The final tree structure is easy for humans to read and understand. You can trace the path for any new data point to see exactly how the model arrived at its prediction.
  • Foundation for Advanced Models: While simple, decision trees are the building blocks for more powerful ensemble models like Random Forests and Gradient Boosted Trees (like XGBoost).
  • Overfitting Risk: If a decision tree is grown too deep, it can perfectly memorize the training data, including its noise. This leads to overfitting. Techniques like pruning or setting a maximum depth are used to combat this.
Cheat sheet

Decision Tree Analysis

A supervised learning algorithm that recursively splits data based on attributes yielding the highest Information Gain to form a predictive tree.

MACHINE LEARNING · vizlearn.in/machine_learning/decision_tree.html

More in Machine Learning

Machine LearningK-Means ClusteringMachine LearningK-Nearest Neighbors"Red"0"Blue"1Machine LearningLabel Encoding ProcessMachine LearningLinear Regression with OLS