1 of 17

Classification

Decision trees

2 of 17

Information gain ratio (GainRatio)

  • Intrinsic/split information = entropy of the split

​

​

​

  • Information gain ratio (GainRatio):

 

 

3 of 17

GainRatio("outlook")

Outlook

Yes

No

P(Yes)

P(No)

Entropy�(bits)

Probability

Sunny

2

3

2/5

3/5

​

​

Overcast

4

0

4/4

0/4

​

​

Rainy

3

2

3/5

2/5

​

​

0.971

0

0.971

5/14

4/14

5/14

InfoGain("outlook") = 0.940 – 0.693 = 0.247

SplitInfo("outlook") = info([5,4,5]) = entropy(5/14, 4/14, 5/14) =� = – 5/14*log2(5/14) – 4/14*log2(4/14) – 5/14*log2(5/14) = 1.577

GainRatio("outlook") = InfoGain("outlook") / SplitInfo("outlook") =

= 0.247 / 1.577 = 0.156

4 of 17

GainRatio("temperature")

Temperature

Yes

No

P(Yes)

P(No)

Entropy�(bits)

Probability

Hot

2

2

2/4

2/4

​

​

Mild

4

2

4/6

2/6

​

​

Cool

3

1

3/4

1/4

​

​

1

0.918

0.811

4/14

6/14

4/14

InfoGain("temperature") = 0.940 – 0.911 = 0.029

SplitInfo("temperature") = info([4,6,4]) = entropy(4/14, 6/14, 4/14) =� = – 4/14*log2(4/14) – 6/14*log2(6/14) – 4/14*log2(4/14) = 1.556

GainRatio("temperature") = InfoGain("temperature") / SplitInfo("temperature") =� = 0.029 / 1.556 = 0.019

5 of 17

GainRatio("humidity")

Humidity

Yes

No

P(Yes)

P(No)

Entropy�(bits)

Probability

High

3

4

3/7

4/7

​

​

Normal

6

1

6/7

1/7

​

​

0.985

0.592

7/14

7/14

InfoGain("humidity") = 0.940 – 0.789 = 0.151

​

SplitInfo("humidity") = info([7,7]) = entropy(7/14, 7/14) =� = – 7/14*log2(7/14) – 7/14*log2(7/14) = 1

GainRatio("humidity") = InfoGain("humidity") / SplitInfo("humidity") =

= 0.151 / 1 = 0.151

6 of 17

GainRatio("windy")

Windy

Yes

No

P(Yes)

P(No)

Entropy�(bits)

Probability

True

6

2

6/8

2/8

​

​

False

3

3

3/6

3/6

​

​

0.811

1

8/14

6/14

InfoGain("windy") = 0.940 – 0.892 = 0.048

SplitInfo("windy") = info([8,6]) = entropy(8/14, 6/14) =� = – 8/14*log2(8/14) – 6/14*log2(6/14) = 0.985

GainRatio("windy") = InfoGain("windy") / SplitInfo("windy") =

= 0.048 / 0.985 = 0.049

7 of 17

Choosing the "best" attribute

  • Information gain ratio (GainRatio):
    • Outlook: 0.156 bits
    • Temperature: 0.019 bits
    • Humidity: 0.152 bits
    • Windy: 0.049 bits

8 of 17

Gini index – "before split"

  •  

9 of 17

Gini index – "after split"

  • We split the set T containing N examples into subsets�T1, T2, …, Tk containing N1, N2, …, Nk examples, respectively. The information of this split is defined as:

​

​

​

​

​

  • The attribute with the lowest ginisplit(T) is chosen as the "best" attribute.

 

10 of 17

Gini("outlook")

Outlook

Yes

No

P(Yes)

P(No)

Gini

Probability

Sunny

2

3

2/5

3/5

​

​

Overcast

4

0

4/4

0/4

​

​

Rainy

3

2

3/5

2/5

​

​

Gini index:

Sunny: Gini([2/5,3/5]) = 1 – ((2/5)2 + (3/5)2) = 0.48

0.48

0

0.48

5/14

4/14

5/14

Overcast: Gini([4/4,0/4]) = 1 – ((4/4)2 + (0/4)2) = 0

Rainy: Gini([3/5,2/5]) = 1 – ((3/5)2 + (2/5)2) = 0.48

Gini("outlook") = (5/14)*0.48 + (4/14)*0 + (5/14)*0.48 = 0.342

11 of 17

Gini("temperature")

Temperature

Yes

No

P(Yes)

P(No)

Gini

Probability

Hot

2

2

2/4

2/4

​

​

Mild

4

2

4/6

2/6

​

​

Cool

3

1

3/4

1/4

​

​

Gini index:

Hot: Gini(2/4,2/4) = 1 – ((2/4)2 + (2/4)2) = 0.5

0.5

0.444

0.375

4/14

6/14

4/14

Mild: Gini(4/6,2/6) = 1 – ((4/6)2 + (2/6)2) = 0.444

Cool: Gini(3/4,1/4) = 1 – ((3/4)2 + (1/4)2) = 0.375

Gini("temperature") = (4/14)*0.5 + (6/14)*0.444 + (4/14)*0.375 = 0.440

12 of 17

Gini("humidity")

Humidity

Yes

No

P(Yes)

P(No)

Gini

Probability

High

3

4

3/7

4/7

​

​

Normal

6

1

6/7

1/7

​

​

Gini index:

High: Gini(3/7,4/7) = 1 – ((3/7)2 + (4/7)2) = 0.490

0.490

0.245

7/14

7/14

Normal: Gini(6/7,1/7) = 1 – ((6/7)2 + (1/7)2) = 0.245

Gini("humidity") = (7/14)*0.490 + (7/14)*0.245 = 0.368

13 of 17

Gini("windy")

Windy

Yes

No

P(Yes)

P(No)

Gini

Probability

True

6

2

6/8

2/8

​

​

False

3

3

3/6

3/6

​

​

Gini index:

True: Gini(6/8,2/8) = 1 – ((6/8)2 + (2/8)2) = 0.375

0.375

0.5

8/14

6/14

False: Gini(3/6,3/6) = 1 – ((3/6)2 + (3/6)2) = 0.5

Gini("windy") = (8/14)*0.375 + (6/14)*0.5 = 0.429

14 of 17

Choosing the "best" attribute

  • Gini index:
    • Outlook: 0.342
    • Temperature: 0.440
    • Humidity: 0.368
    • Windy: 0.429

15 of 17

How to classify new examples?

Outlook

Temperature

Humidity

Windy

Play

Overcast

Hot

High

False

​

Sunny

Cool

High

True

​

Rainy

Mild

High

False

​

Yes

No

Yes

16 of 17

I

D

A

B

E

F

C

438

12.03.2040

5

3.49

14

good

y

450

24.04.1934

3

58.48

32

bad

z

461

05.01.1989

5

47.23

12

bad

y

466

07.08.1945

1

31.40

21

good

y

467

21.07.2028

5

79.60

20

bad

y

469

30.04.1966

3

19.88

3

bad

w

485

28.02.2015

5

59.13

4

bad

w

514

19.03.2033

3

27.05

2

bad

x

522

13.03.2022

2

80.14

16

good

y

529

28.07.2037

4

65.02

20

bad

z

534

05.10.1986

2

99.17

13

good

z

​

​

​

​

​

​

​

And for slightly different data?

17 of 17

InfoGain("A")

A

w

x

y

z

P(w)

P(x)

P(y)

P(z)

entropy

probabilities

1

0

0

1

0

0/1

0/1

1/1

0/1

0

1/11

2

0

0

1

1

0/2

0/2

1/2

1/2

1

2/11

3

1

1

0

1

1/3

1/3

0/3

1/3

1.585

3/11

4

0

0

0

1

0/1

0/1

0/1

1/1

0

1/11

5

1

0

3

0

1/4

0/4

3/4

0/4

0.811

4/11

​

​

​

​

​

​

​

​

​

​

​

Info("A") = 1/11*0 + 2/11*1 + 3/11*1.585 + 1/11*0 + 4/11*0.811 = 0.909

InfoGain("A") = 1.79 – 0.909 = 0.881

1: info([0,0,1,0]) = entropy(0,0,1,0) = – 3*0/1*log2(0/1) – 1/1*log2(1/1) = 0

2: info([0,0,1,1]) = entropy(0,0,1/2,1/2) = – 2*0/2*log2(0/2) – 2*1/2*log2(1/2) = 1

3: info([1,1,0,1]) = entropy(1/3,1/3,0,1/3) = – 0/3*log2(0/3) – 3*1/3*log2(1/3) = 1.585

4: info([0,0,0,1]) = entropy(0,0,0,1) = – 3*0/1*log2(0/1) – 1/1*log2(1/1) = 0

5: info([1,0,3,0]) = entropy(1/4,0,3/4,0) = – 2*0/4*log2(0/4) – 1/4*log2(1/4) – 3/4*log2(3/4) = 0.811

IBS = info([2,1,5,3]) = entropy(2/11,1/11,5/11,3/11) =

= – 2/11*log2(2/11) – 1/11*log2(1/11) – 5/11*log2(5/11) – 3/11*log2(3/11) = 1.79

The "rest" … for homework ☺