Decision Tree

Guest Lecture by Aviva Prins

CMSC 320 - Introduction to Data Science

​

​

Follow Textbook Chapter:: https://ffalam.github.io/CMSC320TextBook/chapter14/Chapter_14_0.html

​

​

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:

• What is Decision Tree
• Common Terminology
• Concept of How to Split a Node
• Entropy
• Information Gain
• Overfitting Problem
• Pre-Pruning
• Post- Pruning

A Decision Tree

A decision tree is a popular machine learning algorithm used for both classification and regression tasks. It splits the dataset into subsets based on the most significant feature at each step.

​

​

Visually represents decisions and their possible consequences, making it easy to understand and interpret.

Terminology: Decision Tree Structure

A binary decision tree (BST) 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.

Decision Trees Terminology Example:

• Decision Tree (DT) defines a hierarchy of rules to make a prediction

​

​

​

​

​

​

​

​

​

​

Decision Tree (DT) learning is about learning such a tree from labeled data

​

​

​

​

​

5

Body

temp.

Gives

birth

Cold

Non-mammal

Yes

No

Non-mammal

Mammal

Root Node

An Internal Node

Warm

A Leaf Node

Root and internal nodes test rules

Leaf nodes make predictions

​

Output of Decision Trees

• Classification Trees: Output is a discrete category (e.g., "Yes/No", "Cat/Dog").

​

• 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.

6

Example: Decision Trees for Classification

Predict: Deciding whether to play or not to play Tennis on a Saturday.

• Each input (Saturday) has 4 categorical features: Outlook, Temp., Humidity, Wind
• A binary classification problem (play vs no-play)

Below Left: Training data, Below Right: A decision tree constructed using this data

​

​

​

​

​

​

​

​

​

​

​

​

​

7

Example credit: Tom Mitchell

• HARD TO GUESS!
• TRY TO UNDERSTAND WHEN JOHN PLAY.

Solution: Decision Tree

Decision Tree:

Divide and Conquer

Decision Tree:

Divide and Conquer

We need to figure out a way to split further in order to get pure subsets.

Resulting

Final

Decision

Tree

A logical Predicates or formula that told you in which cases John will play and vice versa.

Concept Learning in Decision Trees

Decision trees learn boolean functions (True/False outputs) from 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

Example

• IF (Outlook=Sunny AND Humidity=High) OR IF (Outlook= Rain AND Wind=Strong) THEN Play Tennis=No

​

Decision Tree Induction

The process of automatically constructing a decision tree from training data

Many Algorithms:

• ID3 (Iterative Dichotomiser 3) → We will focus only on this one
• C4.5
• Hunt’s Algorithm
• CART
• SLIQ,SPRINT

Next

Key Concepts: Entropy and Information Gain

Decision trees use entropy and information gain to decide the best feature/attribute for splitting.

Concept of “pure” vs “impure” node

​

Try:

Pure Node: All (or majority) samples belong to one class

• No further splitting needed
• Easy to make prediction

​

​

​

​

​

​

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)

Hypothesis Space & Learning Challenges

Multiple trees can fit the same data → Many possible hypotheses

Challenge: Learn the best tree from data

• Minimal tree search is NP-hard → use heuristics
• Greedy algorithms are practical but suboptimal
• Split selection is the core computational challenge

Remember: Ockham’s Razor

The goal is to have the resulting decision tree as small as possible (Occam’s Razor)

• The main decision in the algorithm is the selection of the next attribute to condition on.

22

Back to: How to Split at Internal Nodes?

Decision Tree Splitting: Purity & Entropy

Goal: Create maximally pure child nodes

• Pure = Majority of samples share same class

​

​

​

​

​

​

​

​

​

​

23

• For classification problems (discrete outputs), entropy measures “purity”.
• Low entropy (e.g., 0.0) ⇒ high purity (less uniform label distribution → labels are mostly the same)
• High entropy (e.g., 1.0) ⇒ Low purity (uniform label distribution → labels are mix)

Optimal Split: Maximizes information gain: Entropy(before) – Weighted Entropy(after)

• Key Points: Pure nodes stop further splitting; Greedily select highest IG at each step

Entropy (Measure of Impurity)

Measure of uncertainty or impurity in a dataset. In the context of classification, it quantifies how mixed the class labels are.

​

​

If a dataset S contains c classes, the entropy of S is:

Interpretation:

• Entropy = 0 → Pure (all same class).
• Entropy = 1 → Maximum impurity (equal class distribution).

Example:

• 5 "Yes", 5 "No" → Entropy = 1.
• 8 "Yes", 2 "No" → Entropy ≈ 0.72.

Example: Impurity/ Entropy

25

ENTROPY

Entropy Computing Example:

28

Entropy =

Information Gain

Measures the reduction in entropy after splitting a dataset based on a feature.

Objective: Choose the feature with the highest information gain for splitting.

At each node of the decision tree, we choose the attribute that maximizes information gain as the splitting criterion. This helps us decide how to partition the dataset into smaller, more homogeneous subsets based on the values of the chosen attribute.

From Entropy to Information Gain Formula

30

Information Gain with Formula:

32

This split has a low IG

(in fact zero IG)

This split has higher IG

Remember: goal is to

Important: Find the attribute or feature for splitting the dataset that minimizes entropy or maximizes information gain, thereby reducing the uncertainty and making the dataset more homogeneous (in terms of the target variable or class labels) after the split; in order to achieve better classification performance in decision tree algorithms.

33

Consider, Training Examples

Example: Entropy and Information Gain

Determine the Root Attribute:

Let’s use IG based criterion to construct a DT for the Tennis example

• At root node, let’s compute IG of each of the 4 features
• Consider feature “wind”. Root contains all examples S = [9+,5-]

​

​

S_weak = [6+, 2−] ⇒ H(S_weak ) = 0.811

S_strong = [3+, 3−] ⇒ H(S_strong) = 1

​

​

​

​

​

​

​

​

​

​

35

Determine the Root Attribute:

Let’s use IG based criterion to construct a DT for the Tennis example

• At root node, let’s compute IG of each of the 4 features
• Consider feature “wind”. Root contains all examples S = [9+,5-]

​

​

S_weak = [6+, 2−] ⇒ H(S_weak ) = 0.811

S_strong = [3+, 3−] ⇒ H(S_strong) = 1

​

​

​

​

​

​

​

​

​

​

36

• Likewise, at root: IG(S, outlook) = 0.246, IG(S, humidity) = 0.151, IG(S,temp) = 0.029
• Thus we choose “outlook” feature to be tested at the root node

Now

• Now how to grow the DT, i.e., what to do at the next level? Which feature to test next?
• Rule: Iterate - for each child node, select the feature with the highest IG

​

​

​

​

​

​

​

​

​

​

​

37

Sort the Training Example and Growing the tree

S_sunny= {D1,D2,D8,D9,D11}

Gain (S_sunny, Humidity) = .970

Gain (S_sunny, Temp) = .570

Gain (S_sunny, 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−

?

?

38

Organize training data at each decision node based on the attribute that best separates the examples into distinct classes.

Growing the tree

​

​

​

​

​

​

• So, proceeding as before, for level 2, left node, we can verify that
• IG(S,temp) = 0.570, IG(S, humidity) = 0.970, IG(S, wind) = 0.019
• Thus humidity chosen as the feature to be tested at level 2, left node
• No need to expand the middle node (already “pure” - all “yes” training examples)
• Can also verify that wind has the largest IG for the right node.
• Note: If a feature has already been tested along a path earlier, we don’t consider it again

​

​

​

39

Final Decision Tree

Outlook

Sunny

Overcast

Rain

Humidity

Wind

Yes

High

Normal

Strong

Weak

No

40

Yes

Yes

No

Split vertically

Entropy

One more example: Training a Decision Tree

Information Gain

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.

​

43

45

A very deep tree required

To fit just one odd training

example

​

Overfitting

When to stop Splitting Further?

46

A very deep tree required

To fit just one odd training

example

​

• Consider adding noisy training example (should be +):

​

​

• What effect on earlier tree?

47

Overfitting in Decision Tree

48

Noise or other

coincidental regularities

Overfitting in Decision Tree - Example

When to stop growing the tree?

​

​

​

​

• Stop expanding a node further (i.e., make it a leaf node) when
• It consist of all training examples having the same label (the node becomes “pure”)
• We run out of features to test along the path to that node
• The DT starts to overfit (can be checked by monitoring

the validation set accuracy)

​

​

49

When to stop growing the tree?

​

​

​

​

​

• Important: 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, e.g., this
• Predictions at Impure Leaf Nodes: For test inputs that reach an impure leaf, we can predict probability of belonging to each class (in above example, p(red) = 3/8, p(green) = 5/8), or simply predict the majority labell, which in this case would be green.

​

50

OR

Avoiding Overfitting in DTs

• Desired: a DT that is not too big in size, yet fits the training data reasonably

​

• Mainly two approaches to prune a complex DT
• Prune while building the tree (stopping early)
• Prune after building the tree (post-pruning)

​

51

Avoiding Overfitting in DTs

• Criteria for judging which nodes could potentially be pruned
• Use a validation set (separate from the training set)
• Prune each possible node that doesn’t hurt the accuracy on the validation set
• Greedily remove the node that improves the validation accuracy the most
• Stop when the validation set accuracy starts worsening

53

54

Two basic approaches

1. Prepruning: Stop growing the tree at some point during construction when it is determined that there is not enough data to make reliable choices.

Advantages:

• Prevents overfitting early on.
• Faster computation as the tree is smaller.

Disadvantages:

• May miss important patterns if stopped too early.
• Decision to stop may be subjective.

Prepruning

55

Two basic approaches

2. Postpruning: Grow the full tree (Allow tree to grow until best fit (allow overfitting)) and then remove nodes that seem not to have sufficient evidence or or do not significantly contribute to the overall accuracy of the tree. (more popular)

​

Advantages:

• Captures all possible patterns.
• Reduces overfitting by removing unnecessary nodes.

Disadvantages:

• More computationally expensive initially.
• Risk of overfitting if not properly validated.

Postpruning

Summary: Determine when to stop splitting

Stopping Criteria:

The recursive splitting process continues until a stopping criterion is met. Common stopping criteria include

• Reaching a maximum depth (preventing it from becoming overly complex).
• Having a minimum number of samples per leaf (Splitting stops if a leaf node would contain fewer samples than a specified threshold).
• Encountering pure nodes (nodes containing only one class).

56

Scikit Learn Decision Tree

Scikit Learn: Example with Custom Parameters:

The End