Decision Tree
CMSC 320 - Introduction to Data Science
Fardina F. Alam
Before We Start, Remember:
No free lunch theorem
Much of ML is concerned with devising different models and different
algorithms to fit them. However, there’s no single best model that works optimally for all ends of problems.
2
Topics to cover today:
Machine Learning Fundamentals
What Is a Decision Tree?
Decision Tree: Learning Through Questions
Example Scenario
Example: Will a customer buy a product?
“Think of a decision tree as a flowchart. Depending on the answer, we follow a different branch until we reach a final prediction. Unlike KNN, which compares distances between points, a decision tree learns decision rules from the training data.”
Terminology: Decision Tree Structure
A binary decision tree is a decision tree in which each node has two branches.
Starting point�(does not have any incoming branches)
Terminal points�(represent all the possible outcomes within the dataset.)
Root Node: The top decision node (starting point for decision making).
Decision/Internal Node: Tests a feature and splits into branches.
Leaf/ Terminal Node: Final node with a prediction (no further splits).
Branch/Sub-Tree: A connection between nodes, representing a possible outcome based on a feature test.
Layer: Nodes at the same depth from the root.
Depth: The maximum number of layers from root to farthest leaf.
Output of Decision Trees
8
1. Classification Trees
Output is a discrete category (e.g., "Yes/No", "Cat/Dog").
2. Regression Trees
Predict a continuous numerical value (e.g., house price, temperature).
Decision Rules
Each path from root to leaf represents an IF-THEN rule.
Example: Decision Trees for Classification
Below Left: Training Data | Below Right: Decision Tree constructed using this data
9
Predict: Deciding whether to play or not to play Tennis on a Saturday.
• 4 Categorical Features: Outlook, Temp., Humidity, Wind• Target: Binary classification (Play vs. No-Play)
Example credit: Tom Mitchell
Slide by Tom Mitchell and Victor Lavrenko
Decision Tree:
Divide and Conquer
Start with: outlook feature
Decision Tree:
Divide and Conquer
Start with: outlook feature
Next:
split further in order to get pure subsets
Start with: Let’s consider “Humid”
Next:
split further in order to get pure subsets
Start with: Let’s consider “Wind”
Resulting
Final
Decision
Tree
A logical Predicates or formula that told you in which cases John will play and vice versa.
How Do We Choose the Best Split?
Goal: Create groups that are as pure as possible.
Concept Learning in Decision Trees
Key Concept: Decision trees learn boolean functions (True/False outputs) from training examples.
REPRESENTATION
• Learn True/False (Yes/No) outputs
• Tree = OR of AND rules
- Each Path → AND (conjunction)
- Full Tree → OR (disjunction)
EXPRESSIVITY
• Can represent any Boolean function (AND, OR, XOR)
• Some functions → very large (exponential) trees
• Produces human-interpretable rules
DESIGN PRINCIPLE
• Prefer simpler trees (Occam's Razor)
• Fewer splits → better generalization
• Easier to interpret & explain
DECISION TREE DIAGRAM
RULE FORMULA EXAMPLE
IF (Outlook=Sunny AND Humidity=High)
OR IF (Outlook=Rain AND Wind=Strong)
THEN Play Tennis = No
Decision Tree Induction
Overview: The process of automatically constructing a decision tree from training data
ALGORITHMS OVERVIEW
• Many Algorithms: C4.5, Hunt’s Algorithm, CART, SLIQ, SPRINT
TARGET FOCUS
ID3 (Iterative Dichotomiser 3)
➔ We will focus only on this algorithm
HISTORICAL MILESTONES
• Ross Quinlan: ID3 (1986), C4.5 (1993)
• Breiman et al.: CART (1984) from statistics
ALGORITHM PSEUDOCODE (ID3)
Concept of “pure” vs “impure” node
Try:
Pure Node: All (or majority) samples belong to one class
Impure Node: Contains mixed classes. Requires further splitting
Example “Sunny”, “Rain” → Impure nodes (need splitting)
Here, “Overcast” is a pure node
Purity Goal: Seek splits that create subsets that are: Either all positive (e.g., 4Y/0N) Or all negative (e.g., 0Y/4N)
How Does a Decision Tree Choose a Split?
Goal: Create groups that are as pure as possible.
Key takeaway: A good split reduces impurity.
Entropy: Measuring Impurity
Entropy measures how mixed or uncertain the class labels are in a dataset.
Key Characteristics
Entropy = 0 (Pure)
All samples belong to a single class. Zero uncertainty.
Entropy = 1 (Maximum Impurity)
Classes are equally represented (e.g., 50/50 binary split).
Higher Entropy → Greater Uncertainty
As class mixing increases, entropy rises toward its peak.
Binary Entropy Curve
p_i = proportion of samples in class i; 0 log₂ 0 is treated as 0.
ENTROPY
Entropy Computing Example:
24
Entropy =
From Entropy to Information Gain
How Does a Decision Tree Choose the Best Split?
We know that lower entropy means a purer node.
But what if we have multiple ways to split the data?
Information Gain measures how much a split reduces entropy.
Calculating Information Gain
Information Gain = Entropy Before − Weighted Entropy After
FORMAL DEFINITION & NOTATION
COMPONENT BREAKDOWN
Key takeaway: Higher Information Gain = Greater reduction in impurity = Better split.
Information Gain with Formula:
28
This split has a low IG
(in fact zero IG)
This split has higher IG
Consider, Training Examples
Example: Entropy and Information Gain
Day | Outlook | Temp | Humidity | Wind | Tennis? |
D1 | Sunny | Hot | High | Weak | No |
D2 | Sunny | Hot | High | Strong | No |
D3 | Overcast | Hot | High | Weak | Yes |
D4 | Rain | Mild | High | Weak | Yes |
D5 | Rain | Cool | Normal | Weak | Yes |
D6 | Rain | Cool | Normal | Strong | No |
D7 | Overcast | Cool | Normal | Strong | Yes |
D8 | Sunny | Mild | High | Weak | No |
D9 | Sunny | Cool | Normal | Weak | Yes |
D10 | Rain | Mild | Normal | Weak | Yes |
D11 | Sunny | Mild | Normal | Strong | Yes |
D12 | Overcast | Mild | High | Strong | Yes |
D13 | Overcast | Hot | Normal | Weak | Yes |
D14 | Rain | Mild | High | Strong | No |
Determine the Root Attribute:
Let’s use IG based criterion to construct a DT for the Tennis example
Sweak = [6+, 2−] ⇒ H(Sweak ) = 0.811
Sstrong = [3+, 3−] ⇒ H(Sstrong) = 1
31
Wind
Weak
Strong
6+, 2−�Ε=0.811
3+, 3−�Ε=1.000
9+, 5− Ε=0.940
Determine the Root Attribute:
Let’s use IG based criterion to construct a DT for the Tennis example
Sweak = [6+, 2−] ⇒ H(Sweak ) = 0.811
Sstrong = [3+, 3−] ⇒ H(Sstrong) = 1
32
Now
33
Sort the Training Example and Growing the tree
Ssunny= {D1,D2,D8,D9,D11}
Gain (Ssunny, Humidity) = .970
Gain (Ssunny, Temp) = .570
Gain (Ssunny, Wind) = .019
Outlook
Sunny
Overcast
9+, 5− {D1,…,D14}
Rain
{D3,D7,D12,D13}� 4+, 0−
Yes
{D4,D5,D6,D10,D15}� 3+, 2−
{D1,D2,D8,D9,D11}� 2+, 3−
?
?
34
Organize training data at each decision node based on the attribute that best separates the examples into distinct classes.
Growing the tree
35
Final Decision Tree
Outlook
Sunny
Overcast
Rain
Humidity
Wind
Yes
High
Normal
Strong
Weak
No
36
Yes
Yes
No
One more example: Training a Decision Tree
Split horizontally
Split vertically
Final decision tree!
What about? If features are continuous:
Internal nodes can test the value of a feature against a threshold.
38
39
+ + + +
+ + - +
+ + + +
+ + + +
+ + + +
+ + + +
+ + + +
+ + + +
+ + + +
Attribute 1
Attribute 2
A very deep tree required
To fit just one odd training
example
Overfitting
Overfitting: When to stop Splitting Further?
40
+ + + +
+ + - +
+ + + +
+ + + +
+ + + +
+ + + +
+ + + +
+ + + +
+ + + +
Attribute 1
Attribute 2
A very deep tree required
To fit just one odd training
example
Day | Outlook | Temp | Humidity | Wind | Tennis? |
D15 | Sunny | Hot | Normal | Strong | No |
41
Overfitting in Decision Tree
42
Outlook
Overcast
Rain
3,7,12,13
4,5,6,10,14
3+,2-
Sunny
1,2,8,9,11
4+,0-
2+,3-
Yes
Humidity
Wind
Normal
High
No
Weak
Strong
No
Yes
Weak
Strong
No
Yes
Wind
Noise or other
coincidental regularities
Overfitting in Decision Tree - Example
When to Stop Growing the Decision Tree?
Goal: Avoid overfitting while keeping the tree useful.
When to Stop Splitting
No Need to Obsess Too Much for Purity
(To help prevent the tree from growing too much!)
• It is okay to have a leaf node that is not fully pure.
Predictions at Impure Leaf Nodes:
For test inputs reaching an impure leaf, predict probability of each class (e.g. p(green) = 80%), or simply predict the majority label (Green).
Avoiding Overfitting in DTs
44
Goal: Keep the tree simple while maintaining good prediction accuracy.
Two main approaches:
Pre-pruning:
Stop the tree from growing too much.
Post-pruning:
Grow the tree first, then remove unnecessary branches.
How do we decide what to prune?
Key takeaway: Pruning reduces unnecessary complexity and helps prevent overfitting.
Scikit Learn Decision Tree
Scikit Learn: Example with Custom Parameters:
The End