Part 3: Decision Trees

• Decision tree representation
• ID3 learning algorithm
• Entropy, information gain
• Overfitting

Supplimentary material

www

• http://dms.irb.hr/tutorial/tut_dtrees.php
• http://www.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/4_dtrees1.html

​

ICS320

2

Decision Tree for PlayTennis

• Attributes and their values:
• Outlook: Sunny, Overcast, Rain
• Humidity: High, Normal
• Wind: Strong, Weak
• Temperature: Hot, Mild, Cool

​

• Target concept - Play Tennis: Yes, No

ICS320

3

Decision Tree for PlayTennis

ICS320

4

Outlook

Sunny

Overcast

Rain

Humidity

High

Normal

Wind

Strong

Weak

No

Yes

Yes

Yes

No

Decision Tree for PlayTennis

ICS320

5

Outlook

Sunny

Overcast

Rain

Humidity

High

Normal

No

Yes

Decision Tree for PlayTennis

ICS320

6

Outlook Temperature Humidity Wind PlayTennis

Sunny Hot High Weak ?

Decision Tree for Conjunction

ICS320

7

Outlook

Sunny

Overcast

Rain

Wind

Strong

Weak

No

Yes

No

Outlook=Sunny ∧ Wind=Weak

No

Decision Tree for Disjunction

ICS320

8

Outlook

Sunny

Overcast

Rain

Yes

Outlook=Sunny ∨ Wind=Weak

Wind

Strong

Weak

No

Yes

Wind

Strong

Weak

No

Yes

Decision Tree

ICS320

9

• decision trees represent disjunctions of conjunctions

(Outlook=Sunny ∧ Humidity=Normal)

∨ (Outlook=Overcast)

∨ (Outlook=Rain ∧ Wind=Weak)

When to consider Decision Trees

• Instances describable by attribute-value pairs
• e.g Humidity: High, Normal
• Target function is discrete valued
• e.g Play tennis; Yes, No
• Disjunctive hypothesis may be required
• e.g Outlook=Sunny ∨ Wind=Weak
• Possibly noisy training data
• Missing attribute values
• Application Examples:
• Medical diagnosis
• Credit risk analysis
• Object classification for robot manipulator (Tan 1993)

ICS320

10

Top-Down Induction of Decision Trees ID3

ICS320

11

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.

Which Attribute is ”best”?

ICS320

12

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₊ log₂ p₊ - p_- log₂ p_-

ICS320

13

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

–log₂ p bits to messages having probability p.

• So the expected number of bits to encode

(+ or -) of random member of S:

-p₊ log₂ p₊ - p_- log₂ p_-

​

ICS320

14

Note that: 0Log₂0 =0

Information Gain

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

​

ICS320

15

Gain(S,A)=Entropy(S) - ∑_{v∈values(A)} |S_v|/|S| Entropy(S_v)

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

= 0.99

​

Information Gain

Entropy([21+,5-]) = 0.71

Entropy([8+,30-]) = 0.74

Gain(S,A₁)=Entropy(S)

-26/64*Entropy([21+,5-])

-38/64*Entropy([8+,30-])

=0.27

​

​

ICS320

16

Entropy([18+,33-]) = 0.94

Entropy([11+,2-]) = 0.62

Gain(S,A₂)=Entropy(S)

-51/64*Entropy([18+,33-])

-13/64*Entropy([11+,2-])

=0.12

Training Examples

ICS320

17

Selecting the Next Attribute

ICS320

18

Humidity

High

Normal

[3+, 4-]

[6+, 1-]

S=[9+,5-]

E=0.940

Gain(S,Humidity)

=0.940-(7/14)*0.985

– (7/14)*0.592

=0.151

E=0.985

E=0.592

Wind

Weak

Strong

[6+, 2-]

[3+, 3-]

S=[9+,5-]

E=0.940

E=0.811

E=1.0

Gain(S,Wind)

=0.940-(8/14)*0.811

– (6/14)*1.0

=0.048

Humidity provides greater info. gain than Wind, w.r.t target classification.

Selecting the Next Attribute

ICS320

19

Outlook

Sunny

Rain

[2+, 3-]

[3+, 2-]

S=[9+,5-]

E=0.940

Gain(S,Outlook)

=0.940-(5/14)*0.971

-(4/14)*0.0 – (5/14)*0.0971

=0.247

E=0.971

E=0.971

Over

cast

[4+, 0]

E=0.0

Selecting the Next Attribute

ICS320

20

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

Note: 0Log₂0 =0

ID3 Algorithm

ICS320

21

Outlook

Sunny

Overcast

Rain

Yes

[D1,D2,…,D14]

[9+,5-]

S_sunny=[D1,D2,D8,D9,D11]

[2+,3-]

?

?

[D3,D7,D12,D13]

[4+,0-]

[D4,D5,D6,D10,D14]

[3+,2-]

Gain(S_sunny , Humidity)=0.970-(3/5)0.0 – 2/5(0.0) = 0.970

Gain(S_sunny , Temp.)=0.970-(2/5)0.0 –2/5(1.0)-(1/5)0.0 = 0.570

Gain(S_sunny , Wind)=0.970= -(2/5)1.0 – 3/5(0.918) = 0.019

Test for this node

Note: 0Log₂0 =0

ID3 Algorithm

ICS320

22

Outlook

Sunny

Overcast

Rain

Humidity

High

Normal

Wind

Strong

Weak

No

Yes

Yes

Yes

No

[D3,D7,D12,D13]

[D8,D9,D11]

[D6,D14]

[D1,D2]

[D4,D5,D10]

Occam’s Razor

Why prefer short hypotheses?

Argument 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

Argument opposed:

• There are many ways to define small sets of hypotheses
• E.g. All trees with a prime number of nodes that use attributes beginning with ”Z”
• What is so special about small sets based on size of hypothesis

ICS320

23

Overfitting

• One of the biggest problems with decision trees is Overfitting

​

ICS320

24

Overfitting in Decision Tree Learning

ICS320

25

Avoid Overfitting

How can we avoid overfitting?

• Stop growing when data split not statistically significant
• Grow full tree then post-prune
• Minimum description length (MDL):

Minimize:

size(tree) + size(misclassifications(tree))

ICS320

26

Converting a Tree to Rules

ICS320

27

R₁: If (Outlook=Sunny) ∧ (Humidity=High) Then PlayTennis=No

R₂: If (Outlook=Sunny) ∧ (Humidity=Normal) Then PlayTennis=Yes

R₃: If (Outlook=Overcast) Then PlayTennis=Yes

R₄: If (Outlook=Rain) ∧ (Wind=Strong) Then PlayTennis=No

R₅: If (Outlook=Rain) ∧ (Wind=Weak) Then PlayTennis=Yes

Continuous Valued Attributes

Create a discrete attribute to test continuous

• Temperature = 24.5⁰C
• (Temperature > 20.0⁰C) = {true, false}

Where to set the threshold?

​

​

ICS320

28

(see paper by [Fayyad, Irani 1993]

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

ICS320

29