Decision Trees
A decision tree is a non-parametric supervised
learning algorithm, which is utilized for both
classification and regression tasks. It has a
hierarchical, tree structure, which consists of a
root node, branches, internal nodes and leaf nodes.
Decision Trees 1
Outline
• Decision Tree Representations
– ID3 and C4.5 learning algorithms (Quinlan
1986)
– CART learning algorithm (Breiman et al. 1985)
• Entropy, Information Gain
• Overfitting
Decision Trees 2
Training Data Example: Goal is to Predict
When This Player Will Play Tennis?
Intro AI Decision Trees 3
Intro AI Decision Trees 4
Intro AI Decision Trees 5
Intro AI Decision Trees 6
Intro AI Decision Trees 7
Learning Algorithm for Decision
Trees
x = (x1 ,..., xd )
S = {(x1 , y1 ),..., (x N , yN )}
x j , y Î {0,1}
What happens if features are not binary? What about regression?
Intro AI Decision Trees 8
Choosing the Best Attribute
A1 and A2 are “attributes” (i.e. features or inputs).
Number +
and – examples
before and after
a split.
- Many different frameworks for choosing BEST have been
proposed!
- We will look at Entropy Gain.
Intro AI Decision Trees 9
Entropy
Intro AI Decision Trees 10
Entropy is like a measure of impurity…
Intro AI Decision Trees 11
Entropy
Intro AI Decision Trees 12
Intro AI Decision Trees 13
Information Gain
Intro AI Decision Trees 14
Intro AI Decision Trees 15
Intro AI Decision Trees 16
Intro AI Decision Trees 17
Training Example
Intro AI Decision Trees 18
Selecting the Next Attribute
Intro AI Decision Trees 19
Intro AI Decision Trees 20
Non-Boolean Features
• Features with multiple discrete values
– Multi-way splits
– Test for one value versus the rest
– Group values into disjoint sets
• Real-valued features
– Use thresholds
• Regression
– Splits based on mean squared error metric
Intro AI Decision Trees 21
Hypothesis Space Search
You do not get the globally
optimal tree!
- Search space is exponential.
Intro AI Decision Trees 22
Overfitting
Intro AI Decision Trees 23
Overfitting in Decision Trees
Intro AI Decision Trees 24
Validation Data is Used to Control
Overfitting
• Prune tree to reduce error on validation set
Intro AI Decision Trees 25
Homework
• Which feature will be at the root node of the decision tree
trained for the following data? In other words which
attribute makes a person most attractive?
Height Hair Eyes Attractive?
small blonde brown No
tall dark brown No
tall blonde blue Yes
tall dark Blue No
small dark Blue No
tall red Blue Yes
tall blonde brown No
small blonde blue Yes
Intro AI Decision Trees 26
