Data Mining: Classificatie

Data Mining: Classificatie docent: dr. Toon Calders

Gebaseerd op slides van Tan, Steinbach, and Kumar. Introduction to Data Mining

Overzicht • Wat is classificatie? • Leren van een beslissingsboom. • Problemen bij classificatie • Evalueren van een model

Overzicht • Wat is classificatie? – Definitie – Soorten modellen – Voorbeelden

• Leren van een beslissingsboom. • Problemen bij classificatie • Evalueren van een model

Classificatie: Definitie • Gegeven een verzameling objecten (training set) ingedeeld in klasses. • Vind een model voor de klasse in functie van de andere attributen. • Doel: onbekende voorbeelden moeten zo accuraat mogelijk in klassen ingedeeld kunnen worden. – Accuraatheid wordt gemeten op een test set.

Illustratie van een classificatie taak Tid

Attrib1

1

Yes

Large

Attrib2

125K

Attrib3

No

Class

2

No

Medium

100K

No

3

No

Small

70K

No

4

Yes

Medium

120K

No

5

No

Large

95K

Yes

6

No

Medium

60K

No

7

Yes

Large

220K

No

8

No

Small

85K

Yes

9

No

Medium

75K

No

10

No

Small

90K

Yes

Tid

Attrib1

11

No

Small

55K

?

12

Yes

Medium

80K

?

13

Yes

Large

110K

?

14

No

Small

95K

?

15

No

Large

67K

?

Learn Model

10

Attrib2

Attrib3

Class

Apply Model

10

Voorbeelden van classificatie • Voorspellen of tumor kwaadaardig is • Classificeren van kredietkaart transacties als al dan niet fraudulent. • Classificeren van nieuwsberichten als: financieel, weersvoorspelling, entertainment, sport, etc. • Classificeren van meetingen als al dan niet foutief.

Classificatie technieken Op basis van het soort model dat geleerd wordt: • Beslissingsbomen • Classificatie-regels • Geheugen-gebaseerde methodes • Naïve-Bayes en Bayesiaanse belief netwerken • Neurale netwerken • Support Vector Machines •…

Voorbeeld van een beslissingsboom al al us ric ric uo o o n s i g g nt te te as cl ca ca co Tid Refund Marital Status

Taxable Income Cheat

1

Yes

Single

125K

No

2

No

Married

100K

No

3

No

Single

70K

No

4

Yes

Married

120K

No

5

No

Divorced 95K

Yes

6

No

Married

No

7

Yes

Divorced 220K

60K

Splitting Attributes

Refund Yes

No

NO

MarSt Single, Divorced TaxInc

No

8

No

Single

85K

Yes

9

No

Married

75K

No

10

No

Single

90K

Yes

< 80K NO

Married NO

> 80K YES

10

Training Data

Model: Beslissingsboom

Voorbeeld van een beslissingsboom al al us ric ric uo o o n s i g g nt te te as cl ca ca co Tid Refund Marital Status


1

Yes

Single

125K

No

2

No

Married

100K

No

3

No

Single

70K

No

4

Yes

Married

120K

No

5

No

Divorced 95K

Yes

6

No

Married

No

7

Yes

Divorced 220K

No

8

No

Single

85K

Yes

9

No

Married

75K

No

10

No

Single

90K

Yes

60K

Married

MarSt

NO

Single, Divorced Refund No

Yes NO

TaxInc < 80K

> 80K YES

NO

Er is mogelijk meer dan 1 boom voor dezelfde trainingset!

10

Classificeren met de beslissingsboom Tid

Attrib1

1

Yes

Large

Attrib2

125K

Attrib3

No

Class

2

No

Medium

100K

No

3

No

Small

70K

No

4

Yes

Medium

120K

No

5

No

Large

95K

Yes

6

No

Medium

60K

No

7

Yes

Large

220K

No

8

No

Small

85K

Yes

9

No

Medium

75K

No

10

No

Small

90K

Yes

Tid

Attrib1

11

No

Small

55K

?

12

Yes

Medium

80K

?

13

Yes

Large

110K

?

14

No

Small

95K

?

15

No

Large

67K

?

Learn Model

10

10

Attrib2

Attrib3

Class

Apply Model

Decision Tree

Toepassen van het model op de nieuwe data Nieuwe data

Start vanaf de root van de boom.

Refund Yes

No

NO

MarSt Single, Divorced TaxInc < 80K

Refund Marital Status


No

80K

Married

?

10

Married NO

> 80K YES

NO


Refund Yes

No

NO

MarSt Single, Divorced TaxInc < 80K NO

10

Married NO

> 80K YES



No

80K

Married

?


Refund Yes

No

NO




No

80K

Married

?

10

Married NO

> 80K YES

NO


Refund Yes

No

NO


10

Married NO

> 80K YES



No

80K

Married

?


Refund Yes

No

NO




No

80K

Married

?

10

Married NO

> 80K YES

NO


Refund Yes

No

NO


YES


No

80K

Married

NO

10

Married NO

> 80K


Ken klasse “No” toe

Overzicht • Wat is classificatie? • Leren van een beslissingsboom – Algoritme van Hunt. – Hoe vinden we de beste split? – Wanneer stoppen?

• Problemen bij classificatie • Evalueren van een model

Leren van een beslissingsboom Tid

Attrib1

1

Yes

Large

Attrib2

125K

Attrib3

No

Class

2

No

Medium

100K

No

3

No

Small

70K

No

4

Yes

Medium

120K

No

5

No

Large

95K

Yes

6

No

Medium

60K

No

7

Yes

Large

220K

No

8

No

Small

85K

Yes

9

No

Medium

75K

No

10

No

Small

90K

Yes

Tid

Attrib1

11

No

Small

55K

?

12

Yes

Medium

80K

?

13

Yes

Large

110K

?

14

No

Small

95K

?

15

No

Large

67K

?

Learn Model

10

10

Attrib2

Attrib3

Class

Apply Model

Beslissingsboom

Algoritmes voor beslissingsbomen • Vinden van de beste beslissingsboom is niet wenselijk – Hoge complexiteit – Beste boom voor trainingdata is daarom nog niet de beste boom voor nieuwe data (cfr. Later: overfitting)

• Daarom: heuristieken – Meeste algoritmes optimaliseren lokale criteria. – Meeste algoritmes vinden sub-optimale oplossingen.

Inductie van een Beslissingsboom • Vele algoritmes: – Algoritme van Hunt (een van de eerste) – CART – ID3, C4.5 – SLIQ, SPRINT

Algoritme van Hunt • Zoek de beste split voor D – B.v.b.

A ≤5

>5

• Splits D volgens dit criterium in D1, …, Dk – Hier dus:

D1 = records met A≤5 D2 = records met A>5

• Werk recursief verder op de delen D1, …, Dk – Vind boom voor D1, boom voor D2, …

• Combineer de bomen

Algoritme van Hunt • Zoek de beste split voor D • Splits D volgens dit criterium in D1, …, Dk • Werk recursief verder op de delen D1, …, Dk – Vind boom voor D1, boom voor D2, …

• Combineer de bomen: A ≤5 >5 T1

T2

Algoritme van Hunt (Binaire attributen) Algoritme: Hunt(dataset D(A1, …, Ak, class)) – Maak een nieuwe node root – If ( Stopconditie(D) ) • Label root met de grootste klasse in D • Return root

– Else • Selecteer het attribuut A dat Split_Kwaliteit( D0, D1 ) maximaliseert, waarbij Dj = {t in D | t.A = j} • T0 = Hunt(D0); T1 = Hunt(D1) • Label root met A, Voeg edges van de root naar T0.root, resp. T1.root met label 0, resp. 1. • Return root

Beslissingsboom Induction •Greedy strategie. – Splits de nodes gebaseerd op een lokaal criterium: slechts 1 attribuut tegelijk.

•Nog te bepalen/generisch – Hoe splitsen we? • Niet-binaire attributen

– Hoe meten we de kwaliteit van een split? • Split_Kwaliteit( D0, D1 )

– Wanneer moeten we stoppen? • Stopconditie(D)

Hoe splitsen we? • Hangt af van het attribuut-type … – Nominaal – Ordinaal – Continu

… en het aantal vertakkingen dat is toegestaan – 2-way split – Multi-way split

Splitsen op basis van nominale attributen

• Multi-way: Gebruik zoveel vertakkingen als er waarden zijn. CarType Family

Luxury Sports

• Binaire split: Verdeel de waarden in twee verzamelingen. Zoek een optimale opdeling. {Sports, Luxury}

CarType {Family}

OF

{Family, Luxury}

CarType {Sports}

Splitsen op basis van een continu attribuut •Different ways of handling – Discretiseren ordinale attributen – Binaire split: splits op in (A < v) en (A ≥ v) • Beschouw alle mogelijke split-punten • Mogelijk computationeel erg complex

Splitsen op basis van een continu attribuut





Welke split heeft jouw voorkeur? Vooraf:

10 records met klasse “0” 10 records met klasse “1”

Welke split heeft jouw voorkeur? Vooraf:

10 records met klasse “0” 10 records met klasse “1”

Niet homogeen

“Vrij” homogeen

Meest homogeen Te veel splits!

Hoe bepalen we de kwaliteit van een split?

• We willen nodes met een homogene klasse distributie • We hebben een maat van homogeniteit nodig:

Niet homogeen

Homogeen

Maten van homogeniteit • Dataset D: – k klassen, n records – dj records met klasse j, j=1..k

• Gini Index dj GINI ( D ) = 1 − ∑  j =1  n k

  

2

Vraag • Dataset D heeft slechts 2 klassen, 0 en 1

dj GINI ( D ) = 1 − ∑  j =1  n k

Bij welke verdeling tussen de klassen is de GINI-index maximaal? Minimaal?

  

2

Vraag • Dataset D heeft slechts 2 klassen, 0 en 1

dj GINI ( D ) = 1 − ∑  j =1  n k

Bij welke verdeling tussen de klassen is de GINIindex maximaal? Minimaal? d1 = n.x d2 = n.(1-x) Gini(x) = 1 – (x2) – (1-x)2 = 2x -2x2 (Gini(x))’ = 2-4x nulpunt op 0.5 (Gini(x))’’ = -4 < 0 maximum

  

2

GINI: algemeen • k klassen • Maximum 1-1/k wordt bereikt als de klassen elk een relatieve frequentie van 1/k hebben – Minst interessante geval

• Minimum 0 wordt bereikt als alle records tot 1 klasse behoren – Meest interessante geval. C1 0 C2 6 Gini=0.000

C1 1 C2 5 Gini=0.278

C1 2 C2 4 Gini=0.444

C1 3 C2 3 Gini=0.500

Voorbeelden berekening GINI dj GINI ( D ) = 1 − ∑  j =1  n k

C1 C2

0 6

C1 C2

1 5

C1 C2

2 4

  

2

Voorbeelden berekening GINI dj GINI ( D ) = 1 − ∑  j =1  n k

C1 C2

0 6

C1 C2

1 5

d1 = 1/6

C1 C2

2 4

d1 = 2/6

d1 = 0/6 = 0

d2 = 6/6 = 1

Gini = 1 – d12 – d22 = 1 – 0 – 1 = 0

d2 = 5/6

Gini = 1 – (1/6)2 – (5/6)2 = 0.278 d2 = 4/6

Gini = 1 – (2/6)2 – (4/6)2 = 0.444

Splitsen gebaseerd op GINI • Gebruikt in CART, SLIQ, SPRINT. • Kwaliteit van een split is het gewogen gemiddelde over alle kinderen: k

GINI split = ∑ i =1

met,

ni GINI (i ) n

ni = aantal records voor het kind ci, n = totale aantal nodes in p.

  

2

Voorbeeld N00 N01

C0 C1

Voor split:

M0

A?

B?

Yes

No

Node N1

Node N2

N10 N11

C0 C1

Yes Node N3 C0 C1

N20 N21

C0 C1

M2

M1

No Node N4

N30 N31

N40 N41

C0 C1

M3

M4

M12

M34 Gain = M0 – M12 vs M0 – M34

Waarom gewogen gemiddelde? • Effect van het wegen: – Grotere partities worden gezocht. Parent

B? Yes

No

C1

6

C2

6

Gini = 0.500

Gini(N1) = 1 – (5/6)2 – (2/6)2 = 0.194 Gini(N2) = 1 – (1/6)2 – (4/6)2 = 0.528

Node N1

Node N2

C1 C2

N1 5 2

N2 1 4

Gini=0.333

Gini(Children) = 7/12 * 0.194 + 5/12 * 0.528 = 0.333





Stop criteria voor beslissingsbomen • Verschillende mogelijkheden:

Stop criteria voor beslissingsbomen • Verschillende mogelijkheden: – Stop als alle nodes tot dezelfde klasse behoren. – Stop als GINI-index beneden bepaalde waarde komt. – Stop als aantal objecten te klein wordt. – Stop als alle attributen ongeveer dezelfde waarde hebben.

• Early termination (zie later)

Overzich beslissingsbomen • Voordelen: – Weinig tijd nodig om te berekenen – Classificeren van nieuwe voorbeelden is erg snel – Makkelijk te interpreteren modellen (indien niet te veel nodes) – Voor vele datasets scoren beslissingsbomen meer dan behoorlijk

• Nadelen: – In detail …

Overzicht • Wat is classificatie? • Leren van een beslissingsboom. • Problemen bij classificatie • Evalueren van een model

Practische problemen bij classificatie • Sommige functies zijn moeilijk uit te drukken m.b.v. beslissingsbomen – Parity (Is het aantal binaire attributen die True zijn, even?)

• Lager in de boom = minder trainingvoorbeelden = minder statistische relevantie •Underfitting en Overfitting – Gerelateerd aan de vraag: wanneer stoppen?

Moeilijk uit te drukken … • Hoe zien de beslissingbomen die door het algoritme van Hunt gegenereerd worden er uit voor de volgende dataset? +

B -

+

+ + + + + + + + + + + + + + + + + + - + A +


B -

+

+ + + + + + + + + + + + + + + ++ + - -- - + A +


B -

+

+ + + + + + + + + + + + + + + + + + - + A +


B -

+

+ + + + + + + + + + + + + + + ++ + - -- - + A +


B -

+

+ + + + + + + + + + + + + + + + + + - + A +


B -

+

+ + + + + + + + + + + + + + + ++ + - -- - + A +

Typische grafiek. Wat gebeurt er hier?

Underfitting

Overfitting

Underfitting: Als het model te simpel is; de boom is nog te eenvoudig Overfitting: Het model is zo gedetailleerd dat het zelfs de ruis uit de input heeft geleerd

Overfitting door ruis • Goed model B

+ + + + + + + + - -+ + - + -- A --

-

Overfitting door ruis • Slecht model, toch kleinere error op trainingsset B

+ + + + + + + + - -+ + - + -- A --

-

Bemerkingen over overfitting • Resulteert in complexere bomen dan noodzakelijk. • Training error is niet langer een goede maat om te meten hoe de classifier zal presteren op nieuwe data. • Betere manieren nodig om fouten te meten.

Hoe gaan we overfitting tegen? • Pre-Pruning (Early Stopping) – Stop voordat de volledige boom gemaakt is. • Stop indien het aantal instanties te klein wordt • Stop als de klasdistributie onafhankelijk is van de afzonderlijke features (gebruik bvb. χ 2 test) • Stop indien er geen split is die resulteert in een positive gain

Hoe gaan we overfitting tegen? • Post-pruning – Maak de volledige beslissingsboom – Behandel de splits bottom-up • Als de generalization error verkleint door het wegnemen van een split: haal de split weg en vervang door een blad. • Label wordt de grootste klasse in het nieuwe blad.

Vraag: Hoe meten we generalization error?

Vraag: Hoe meten we generalization error?

• Splits D vooraf in twee delen: D1 en D2 • Leer de boom op D1 • Evalueer de generalization errors op D2

Overzicht • Wat is classificatie? • Leren van een beslissingsboom. • Evalueren van een model – Volgende les

Data Mining: Classificatie

Recommend Documents