ID3 Algorithm

Decision Trees
 Agenda
• Decision Trees
• What is ID3?
• Entropy
• Calculating Entropy with Code
• Information Gain
• Advantages and Disadvantages
• Example
 Decision Trees
• Rules for classifying data using attributes.
• The tree consists of decision nodes and leaf
nodes.
• A decision node has two or more branches,
each representing values for the attribute tested.
• A leaf node attribute produces a homogeneous
result (all in one class), which does not require
additional classification testing.
 Decision Tree Example
Outlook

sunny rain
overcast

Humidity Yes
Windy

high normal true false

No Yes No Yes
 What is ID3?
• A mathematical algorithm for building the decision tree.
• Invented by J. Ross Quinlan in 1979.
• Uses Information Theory invented by Shannon in 1948.
• Builds the tree from the top down, with no backtracking.
• Information Gain is used to select the most useful
attribute for classification.
 Entropy
• A formula to calculate the homogeneity of a sample.
• A completely homogeneous sample has entropy of 0.
• An equally divided sample has entropy of 1.
• Entropy(s) = - p+log2 (p+) -p-log2 (p-) for a sample of
negative and positive elements.
• The formula for entropy is:
 Entropy Example
Entropy(S) =
- (9/14) Log2 (9/14) - (5/14) Log2 (5/14)
= 0.940
8
 Calculating Entropy with Code
• Most programming languages and calculators do not
have a log2 function.
• Use a conversion factor
• Take log function of 2, and divide by it.
• Example: log10(2) = .301
• Then divide to get log2(n):
• log10(3/5) / .301 = log2(3/5)
Calculating Entropy with Code (cont’d)
• Taking log10(0) produces an error.
• Substitute 0 for (0/3)log10(0/3)
• Do not try to calculate log10(0/3)
 Information Gain (IG)
• The information gain is based on the decrease in entropy after a
dataset is split on an attribute.
• Which attribute creates the most homogeneous branches?
• First the entropy of the total dataset is calculated.
• The dataset is then split on the different attributes.
• The entropy for each branch is calculated. Then it is added
proportionally, to get total entropy for the split.
• The resulting entropy is subtracted from the entropy before the split.
• The result is the Information Gain, or decrease in entropy.
• The attribute that yields the largest IG is chosen for the decision
node.
 Information Gain (cont’d)
• A branch set with entropy of 0 is a leaf node.
• Otherwise, the branch needs further splitting to classify
its dataset.
• The ID3 algorithm is run recursively on the non-leaf
branches, until all data is classified.
 Advantages of using ID3
• Understandable prediction rules are created from the
training data.
• Builds the fastest tree.
• Builds a short tree.
• Only need to test enough attributes until all data is
classified.
• Finding leaf nodes enables test data to be pruned,
reducing number of tests.
• Whole dataset is searched to create tree.
 Disadvantages of using ID3
• Data may be over-fitted or over-classified, if a small
sample is tested.
• Only one attribute at a time is tested for making a
decision.
• Classifying continuous data may be computationally
expensive, as many trees must be generated to see
where to break the continuum.
Example: The Simpsons
Person Hair Weight Age Class
Length
Homer 0” 250 36 M
Marge 10” 150 34 F
Bart 2” 90 10 M
Lisa 6” 78 8 F
Maggie 4” 20 1 F
Abe 1” 170 70 M
Selma 8” 160 41 F
Otto 10” 180 38 M
Krusty 6” 200 45 M

Comic 8” 290 38 ?
 p  p  n  n 
Entropy ( S )  log 2    log 2  
pn  p  n  pn  p  n 

Entropy(4F,5M) = -(4/9)log2(4/9) - (5/9)log2(5/9)

= 0.9911
yes no
Hair Length <= 5?

Letus
Let ustry
trysplitting
splitting
onHair
on Hairlength
length

Entrop Entro
y(1F,3 py(3F
M) = - , 2M) =
(1/4)lo -(3/5)
g2 (1/4) l og ( 3
= 0 .8 - (3/4) = 0 .9 2 / 5) - (
113 log (3/ 7 10 2/5)lo
2 4) g2 (2/5
)

Gain( A) E (Current set )   E (all child sets )

Gain(Hair Length <= 5) = 0.9911 – (4/9 * 0.8113 + 5/9 * 0.9710 ) = 0.0911

 p  p  n  n 
Entropy ( S )  log 2    log 2  
pn  p  n  pn  p  n 

Entropy(4F,5M) = -(4/9)log2(4/9) - (5/9)log2(5/9)

= 0.9911
yes no
Weight <= 160?

Letus
Let ustry
trysplitting
splitting
onWeight
on Weight

Entrop Entro
y(4F,1 py(0F
M) = - , 4M) =
(4/5)lo -(0/4)
g2 (4/5) l og ( 0
= 0 .7 - (1/5) = 0 2 / 4) - (
219 log (1/ 4/4)lo
2 5) g2 (4/4
)

Gain( A) E (Current set )   E (all child sets )

Gain(Weight <= 160) = 0.9911 – (5/9 * 0.7219 + 4/9 * 0 ) = 0.5900

 p  p  n  n 
Entropy ( S )  log 2    log 2  
pn  p  n  pn  p  n 

Entropy(4F,5M) = -(4/9)log2(4/9) - (5/9)log2(5/9)

= 0.9911
yes no
age <= 40?

Letus
Let ustry
trysplitting
splitting
onAge
on Age

Entrop Entro
y(3F,3 py(1F
M) = - , 2M) =
(3/6)lo -(1/3)
g2 (3/6) l og ( 1
= 1 - (3/6) = 0 .9 2 / 3) - (
log (3/ 1 83 2/3)lo
2 6) g2 (2/3
)

Gain( A) E (Current set )   E (all child sets )

Gain(Age <= 40) = 0.9911 – (6/9 * 1 + 3/9 * 0.9183 ) = 0.0183

Of the 3 features we had, Weight
was best. But while people who
weigh over 160 are perfectly
classified (as males), the under 160
yes no
people are not perfectly Weight <= 160?
classified… So we simply recurse!
This time we find that we
can split on Hair length, and
we are done! no
yes
Hair Length <= 2?
We need don’t need to keep the data
around, just the test conditions. Weight <= 160?

yes no

How would
these people Hair Length <= 2?
Male
be classified?
yes no

Male Female
It is trivial to convert Decision
Weight <= 160?
Trees to rules…
yes no

Hair Length <= 2?

Male
yes no

Male Female

Rulesto
Rules toClassify
ClassifyMales/Females
Males/Females

IfIfWeight
Weightgreater
greaterthan
than160,
160,classify
classifyas
asMale
Male
ElseifHair
Elseif HairLength
Lengthless
lessthan
thanor
orequal
equaltoto2,2,classify
classifyas
as
Male
Male
Elseclassify
Else classifyas
asFemale
Female
 References
• Quinlan, J.R. 1986, Machine Learning, 1, 81

• [Link]

• [Link]

• [Link]
_dtrees2.html

• Professor Sin-Min Lee, SJSU.

[Link]
 Introduction

• Use a decision tree to predict categories for

new events.
• Use training data to build the decision tree.
New
Events

Training
Decision
Events and
Tree
Categories

Category

24
 Decision Tree for PlayTennis
Outlook

Sunny Overcast Rain

Humidity Each internal node tests an attribute

High Normal Each branch corresponds to an

attribute value node
No Yes Each leaf node assigns a classificatio
25
 Word Sense Disambiguation

• Given an occurrence of a word, decide which

sense, or meaning, was intended.
• Example: "run"
– run1: move swiftly (I ran to the store.)
– run2: operate (I run a store.)
– run3: flow (Water runs from the spring.)
– run4: length of torn stitches (Her stockings had a
run.)
– etc.

26
 Word Sense Disambiguation
• Categories
– Use word sense labels (run1, run2, etc.) to name the
possible categories.
• Features
– Features describe the context of the word we want to
disambiguate.
– Possible features include:
• near(w): is the given word near an occurrence of word w?
• pos: the word’s part of speech
• left(w): is the word immediately preceded by the word w?
• etc.

27
 Word Sense Disambiguation
• Example decision tree:
pos
nou verb
n

near(stocking) near(race)
yes no yes no

run4 run1 near(river)

yes no

run3
(Note: Decision trees for WSD tend to be quite large)

28
 WSD: Sample Training Data

Features Word
pos near(race) near(river) near(stockings Sense
)
noun no no no run4
verb no no no run1
verb no yes no run3
noun yes yes yes run4
verb no no yes run1
verb yes yes no run2
verb no yes yes run3

29
 Decision Tree for Conjunction
Outlook=Sunny  Wind=Weak

Outlook

Sunny Overcast Rain

Wind No No

Strong Weak

No Yes
30
Decision Tree for Disjunction
Outlook=Sunny  Wind=Weak
Outlook

Sunny Overcast Rain

Yes Wind Wind

Strong Weak Strong Weak

No Yes No Yes
31
 Decision Tree for XOR
Outlook=Sunny XOR Wind=Weak

Outlook

Sunny Overcast Rain

Wind Wind Wind

Strong Weak Strong Weak Strong Weak

Yes No No Yes No Yes

32
 Decision Tree
• decision trees represent disjunctions of conjunctions
Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes

(Outlook=Sunny  Humidity=Normal)
 (Outlook=Overcast)
 (Outlook=Rain  Wind=Weak)
33
 When to consider Decision Trees
• Instances describable by attribute-value pairs
• Target function is discrete valued
• Disjunctive hypothesis may be required
• Possibly noisy training data
• Missing attribute values
• Examples:
– Medical diagnosis
– Credit risk analysis
– Object classification for robot manipulator (Tan 1993)

34
 Top-Down Induction of Decision Trees
ID3

1. A  the “best” decision attribute for next

node
2. Assign A as decision attribute for node
3. For each value of A create new
descendant
4. Sort training examples to leaf node
according to
the attribute value of the branch
5. If all training examples are perfectly
classified (same value of target attribute)
stop, else iterate over new leaf nodes. 35
 Which attribute is best?

[29+,35-] A1=? A2=? [29+,35-]

G H L M

[21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

36
 Entropy

• S is a sample of training examples

• p+ is the proportion of positive examples
• p- is the proportion of negative examples
• Entropy measures the impurity of S
Entropy(S) = -p+ log2 p+ - p- log2 p- 37
 Entropy
• Entropy(S)= expected number of bits needed to encode class
(+ or -) of randomly drawn members of S (under the optimal,
shortest length-code)
Why?
• Information theory optimal length code assign
–log2 p bits to messages having probability p.
• So the expected number of bits to encode
(+ or -) of random member of S:
-p+ log2 p+ - p- log2 p-

38
 Information Gain (S=E)
• Gain(S,A): expected reduction in entropy due to sorting S on
attribute A

Entropy([29+,35-]) = -29/64 log2 29/64 – 35/64 log2 35/64

= 0.99
[29+,35-] A1=? A2=? [29+,35-]

G H True False

[21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

39
 Information Gain
Entropy([21+,5-]) = 0.71 Entropy([18+,33-]) = 0.94
Entropy([8+,30-]) = 0.74 Entropy([11+,2-]) = 0.62
Gain(S,A1)=Entropy(S) Gain(S,A2)=Entropy(S)
-26/64*Entropy([21+,5-]) -51/64*Entropy([18+,33-])
-38/64*Entropy([8+,30-]) -13/64*Entropy([11+,2-])
=0.12
=0.27

[29+,35-] A1=? A2=? [29+,35-]

True False True False

[21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

40
 Training Examples
Day Outlook Temp. Humidity Wind Play 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 Weak Yes
D8 Sunny Mild High Weak No
D9 Sunny Cold Normal Weak Yes
D10 Rain Mild Normal Strong 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
41
 Selecting the Next Attribute
S=[9+,5-] S=[9+,5-]
E=0.940 E=0.940
Humidity Wind

High Normal Weak Strong

[3+, 4-] [6+, 1-] [6+, 2-] [3+, 3-]

E=0.985 E=0.592 E=0.811 E=1.0
Gain(S,Humidity) Gain(S,Wind)
=0.940-(7/14)*0.985 =0.940-(8/14)*0.811
– (7/14)*0.592 – (6/14)*1.0
=0.151 =0.048
42
Humidity provides greater info. gain than Wind, w.r.t target classification.
Selecting the Next Attribute
S=[9+,5-]
E=0.940
Outlook

Over
Sunny Rain
cast

[2+, 3-] [4+, 0] [3+, 2-]

E=0.97 E=0.0 E=0.97
1 1
Gain(S,Outlook)
=0.940-(5/14)*0.971
-(4/14)*0.0 – (5/14)*0.0971
=0.247
43
 Selecting the Next Attribute
The information gain values for the 4
attributes are:
• Gain(S,Outlook) =0.247
• Gain(S,Humidity) =0.151
• Gain(S,Wind) =0.048
• Gain(S,Temperature) =0.029

where S denotes the collection of training

examples

44
 ID3 Algorithm
[D1,D2,…,D14] Outlook
[9+,5-]

Sunny Overcast Rain

Ssunny =[D1,D2,D8,D9,D11]
[D3,D7,D12,D13]
[D4,D5,D6,D10,D14]
[2+,3-] [4+,0-] [3+,2-]
? Yes ?
Gain(Ssunny, Humidity)=0.970-(3/5)0.0 – 2/5(0.0) = 0.970
Gain(Ssunny, Temp.)=0.970-(2/5)0.0 –2/5(1.0)-(1/5)0.0 =
0.570
Gain(Ssunny, Wind)=0.970= -(2/5)1.0 – 3/5(0.918) = 0.019
45
 ID3 Algorithm
Outlook

Sunny Overcast Rain

Humidity Yes Wind

[D3,D7,D12,D1
3]
High Normal Strong Weak

No Yes No Yes

[D1,D2] [D8,D9,D11] [D6,D14] [D4,D5,D10

46
[mistake]
 Occam’s Razor
”If two theories explain the facts equally weel, then the simpler
theory is to be preferred”
Arguments in favor:
– Fewer short hypotheses than long hypotheses
– A short hypothesis that fits the data is unlikely to be a
coincidence
– A long hypothesis that fits the data might be a coincidence
Arguments opposed:
– There are many ways to define small sets of hypotheses

47
 Overfitting
• One of the biggest problems with decision trees is
Overfitting

48
 Avoid Overfitting
• stop growing when split not statistically
significant
• grow full tree, then post-prune

Select “best” tree:

• measure performance over training data
• measure performance over separate
validation data set
• min( |tree|+|misclassifications(tree)|)

49
Effect of Reduced Error Pruning

50
 Converting a Tree to Rules
Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes

R1: If (Outlook=Sunny)  (Humidity=High) Then

PlayTennis=No
R2: If (Outlook=Sunny)  (Humidity=Normal) Then
PlayTennis=Yes
R3: If (Outlook=Overcast) Then PlayTennis=Yes 51
 Continuous Valued Attributes
Create a discrete attribute to test continuous
• Temperature = 24.50C
• (Temperature > 20.00C) = {true, false}
Where to set the threshold?

Temperature 150C 180C 190C 220C 240C 270C

PlayTennis No No Yes Yes Yes No

52
 Unknown Attribute Values
What if some examples have missing values of A?
Use training example anyway sort through tree
• If node n tests A, assign most common value of A among
other examples sorted to node n.
• Assign most common value of A among other examples
with same target value
• Assign probability pi to each possible value vi of A
– Assign fraction pi of example to each descendant in tree

Classify new examples in the same fashion

53
 Cross-Validation
• Estimate the accuracy of an hypothesis
induced by a supervised learning algorithm
• Predict the accuracy of an hypothesis over
future unseen instances
• Select the optimal hypothesis from a given
set of alternative hypotheses
– Pruning decision trees
– Model selection
– Feature selection
• Combining multiple classifiers (boosting)
54