Data Mining - Startseite TU Ilmenau · 1 1 Data Mining Vorlesung Stand 12.06.2013 apl. Prof. Dr.-Ing. habil. Rainer Knauf Fachgebiet Künstliche Intelligenz Fakultät für Informatik

1

1

Data MiningVorlesung

Stand 12.06.2013

apl. Prof. Dr.-Ing. habil.

Rainer KnaufFachgebiet Künstliche IntelligenzFakultät für Informatik und AutomatisierungTechnische Universität Ilmenau

[email protected], Raum 3061 (Sekretariat: 3060)Tel. 03677-69-1445, 0361-3733867, 0172-9418642

2

Motivation

In großen Datenmengen liegen oftmals “versteckte” Informationen

Manuelle Analyse verschlingt Unmassen von Ressourcen (Zeit, Geld, …)

Viele Datenbestände wurden (noch) nicht analysiert

Data Mining, d.h.

Extraktion impliziter, bislang unbekannter, potentiell nützlicher Information aus Datenbeständen

Automatische Erkundung und Analyse großer Datenmengen zwecks Aufdeckung von Mustern

0. Einführung

2

3

Der evolutionäre Stufenprozessder Modellbildung

Business Understanding Projektziele Projektanforderungen

Data UnderstandingIst die Qualität der Daten hinreichend für diese Ziele?

Data Preparation Auswahl relevanter Attribute Verknüpfung von Datenquellen Umgang mit fehlenden Daten

ModelingAuswahl & Anwendung konkreter

Verfahren des Data Mining

Evaluationa) bzgl. der Testdatenb) bzgl. der Projektziele

Deployment Interpretation der Modelle Realisierung der Projektziele

Data

4

The Aim of the Game Abstrakte Informationen (Muster, Korrelationen, …) in großen Datenmengen

erkennen Modelle bilden, welche Regularitäten, Zusammenhänge, … in großen

Datenmengen erklären

= „Knowledge Discovery in Databases“

Data00101101101101100011001001101001001100111001100110010010011101101110001100010001101110101001001100111010100011110011001110011111001001101101

DataPreprocessing Attributauswahl Reduzierung

der Dimensionen Normalisierung Auswahl von

Subsets aus Daten …

DataPostprocessing Erkennung von

Mustern Visualisierung Interpretation

der Muster …

DataMining

Knowledge

3

5

Anwendungsbereiche

Wirtschaft Analyse des Kaufverhaltens, Datenerhebung z.B. mit Kundenkarten

Medizin Erkennung von Symptomen für pathologische Erscheinungen empirische Ermittlung der Wirkung von Medikamenten

Staat Aufdeckung von Korruption und Steuerhinterziehung durch Analyse von

Geldströmen Analyse von Bevölkerungs- und Einwanderungsdaten zur Terrorabwehr

Wissenschaft Interpretation von Geodaten zur Vorhersage von Naturkatastrophen Erkennen genetischer Muster für krankhafte Veranlagungen

Energieversorgung, Transport, Mobilkommunikation, … Ermittlung des typischen Kundenverhaltens zum Ressourcen-Management Ermittlung des typischen Kundenverhaltens in außergewöhnlichen

Situationen (Stromausfall, Naturkatastrophe, ...)

6

Typische Aufgabenklassen

Vorhersagemodelle Vorhersage eines Attribut-Wertes auf der Grundlage anderer Attribut-Werte

durch Klassifikation (diskrete Werte) Regression (kontinuierliche Werte)

Analyse von Assoziationen Erkennung von assoziierten Eigenschaften in den Daten (häufig zusammen

besuchten Webseiten, häufig gemeinsam gekaufte Waren, …)

Cluster Analyse Partitionierung der Daten in Cluster mit ähnlichen Eigenschaften (ähnliches

Kaufverhalten von Kunden, ähnliches Lernverhalten, ähnliche Texte auf Webseiten …)

Erkennung von Anomalien Identifizierung von Datenobjekten, die sich signifikant von den restlichen

unterscheiden und damit auf Anomalien hinweisen: Krankheiten technische Fehler (in einem Netzwerk z.B.) Betrug (Kreditkartendaten, Bankgeschäfte, Versicherungsbetrug, …) bevorstehende Naturkatastrophen (Klimadaten), …

4

7

1. Daten1.1 Arten von Daten

Datensatz: Menge von Datenobjekten DS := DO1, DO2, …, DOn Datenobjekt: beschrieben durch Attribut-Wert Paare DOi:= [Ai

1,Wi1],[Ai

2,Wi2], …

Beispiel: Datensatz Prüfungsergebnisse Studierender der Tokyo Denki University

student ID semester course units rating

DO1 SIE0019 1 Curriculum Planning 1 A

DO2 SIE0019 1 Workshop 1 S

DO3 SIE0019 1 Speaking & Writing in English Ι 2 B

DO4 SIE0019 1 Basic Mathematics A 3 A

DO5 SIE0019 1 European, American, and Asian Studies 4 S

DO6 SIE0019 1 Architectural Design Practice 4 A

… … … … … …

DO41 SIE0019 7 Chinese I 2 C

DO42 SIE0019 7 Course Project A 4 A

DO43 SIE0019 7 Electronics B 4 A

DO44 SIE0020 1 Curriculum Planning 1 A

DO45 SIE0020 1 Computer Literacy 2 A

… … … … … …

8

Eigenschaften von Attribut-Werten

Attribut-Typen klassifiziert man bzgl.:

Unterscheidbarkeit: = Ordenbarkeit: ≤ ≥

Addierbarkeit: + -

Multiplizierbarkeit: * /

unterscheidbar ordenbar addierbar multiplizierbar

qualitativ

nominale Attribute + - - -ordinale Attribute + + - -

quantitativ

Intervall-Attribute + + + -

rationale Attribute + + + +

5

9

Attribut - Typen

Attribut-Typ Beschreibung Ope-ratio-nen

Beispiele

nominal aufzählbare Werte =, ≠ Postleitzahlen, Studenten-Matrikelnummer, Augenfarbe, Kodierungen

ordinal aufzählbare Werte mit Ordnungsrelation

obige,

≤, ≥<, >

Noten (1,..5, S, A, ...,E), verbale Beschreibungen quantitativer Merkmale (hart, mittel, weich),

Intervall numerische Werte, bei denen Summen und Differenzen eine Interpretation haben

obige,

+, -

Temperatur in °C oder °F, Kalenderdaten

rational numerische Werte, bei denen (neben Summen und Differenzen) auch Produkt und Quotienten eine Interpretation haben

obige,

/, *

Temperatur in K, Länge, Gewicht, Alter, Geldsummen, elektr. Spannung, …

Qua

litat

ivQ

uant

itativ

10

Legale Attributwert-Transformationen

Attribut-Typ Transformation Beispiel, Kommentar

Nomi-nal

Eineindeutige Abbildungen neuer Werte zu alten Werten

Neukodierung

Ordinal Reihenfolge-erhaltende Zuordnung neuer Werte zu alten Werten

NeuerWert := f (AlterWert)

f: monotone Funktion

Umrechnung eines arithmetischen Notendurchschnitts in eine verbale Leistungsbewertung („sehr gut“, „gut“, …)

Intervall NeuerWert := a * AlterWert + b

a, b: Konstanten

Umrechnung von Fahrenheit in Celsius

Ratio-nal

NeuerWert := a * AlterWert

a: Konstante

Umrechnung von Zoll in cm

Qua

litat

ivQ

uant

itativ

6

11

Diskrete Attribute

haben eine Menge aufzählbarer Werte

werden meist als integer-Variablen repräsentiert

binäre Attribute sind ein Spezialfall diskreter Attribute

Beispiele:

Postleitzahlen

Menge der Wörter eines Dokuments

Diskrete und kontinuierliche Attribute

Kontinuierliche Attribute

haben reelle Zahlen als Wertebereich

können allerdings nur mit einer endlichen Anzahl von Ziffern repräsentiert werden

werden typischerweise als Gleitkommazahl repräsentiert

Beispiele:

Temperatur

Länge

Gewicht

12

AsymmetrischeAttribute

Ein Attribut heißt asymmetrisch, wenn für selbiges nur Werte verschieden von Null von Interesse sind.

‘n Beispiel

In einem Datensatz sei jedes Datenobjekt ein Student (ähnlich wie in Folie 8) und jedes Attribut erfasst, ob ein Student einen bestimmten Kurs belegt hat.

Attribute dieser Art sind von Natur aus binär: ja oder nein, hier kodiert mit 1 (ja) oder 0 (nein).

Wollte man für jeden Studenten alle Kurse der Universität erfassen (auch solche Kurse erfassen, die er nicht belegt hat), wären bei allen Studenten die meisten Attribut-Werte Null.

Dies ist nicht nur sehr ineffizient, sondern könnte auch dazu führen, dass bei einigen Ähnlichkeitsmaßen alle Studenten als sehr ähnlich betrachtet werden.

Für dieses Attribut sind nur Werte ≠ 0 von Interesse.

7

13

1.2 Ähnlichkeitsmaße1.2.1 Ähnlichkeit zwischen Attributen

Ähnlichkeit (similarity): s(x,y)Verschiedenheit (dissimilarity): d(x,y)

Attribut-Typ Verschiedenheit

(dissimilarity)

Ähnlichkeit

(similarity)

nominal

(Aufzählungstyp ohne Ordnungsrelation)

ordinal

(Aufzählungstyp mit Ordnungsrelation)

n Werte, abgebildet auf ganze Zahlen 0, 1, …, n-1

rational

Intervall

denkbare Ansätze für Attributwerte x und y

yx

yxd

if , 1

if , 0

yx

yxs

if , 0

if , 1

1

||

n

yxd ds 1

|| yxd

dd

dds

esd

sds d

min_max_

min_1

1

1

14

1.2.2 Ähnlichkeitsmaße zwischen Datenobjekten x=[x1, …, xn] und y=[y1, …, yn]

Ähnlichkeit (similarity): s(x,y)Verschiedenheit, Abstand (dissimilarity): d(x,y)

Anforderung an Ähnlichkeitsmaße

d ist nicht negativ

• ∀x,y: d(x,y) ≥ 0

d und s sind symmetrisch

• d(x,y) = d(y,x) s(x,y) = s(y,x) Dreiecks-Ungleichung für Abstände

• d(x,z) ≤ d(x,y) + d(y,z) bei Identität gilt

• d(x,y)=0 gdw. x=y

• s(x,y)=1 gdw. x=y

8

15

Ansätze für Verschiedenheit (Abstand) zwischen [x1, …, xn] und [y1, …, yn]

)||(1

),(

1

n

kkk

ryxd yx

r

Typischerweise verwendete Spezialfälle

r = 1 Manhatten (city block) Distance (L1 norm)für bin. Attribute auch Hamming Distance genannt Summe der Abstände aller Dimensionen 1 … n misst für binäre Attribute die Anzahl der Bits, die verschieden sind

r = 2 Euclidian Distance (L2 norm) für numerische Attribute (ordinal oder rational) misst den geometrischen Abstand der Punkte im n - dim. Euklidischen Raum Normalisierung u.U. nötig, wenn die Dimensionen verschiedene Wertebereiche

haben (z.B. zum fairen Vergleich verschieden langer Dokumente in einer Dokument-Term Matrix)

r →∞ Supremum (L∞ norm) ist die größte aller Differenzen in den einzelnen Dimensionen 1 … n:

d(x,y)=maxk=1…n |xk- yk|

Minkowski Distance (Verallgemeinerung der Euclidean Distance)

16

Verschiedenheit (Abstand) zwischen [x1, …, xn] und [y1, …, yn] an Beispielen

0

1

2

3

0 1 2 3 4 5 6

p1

p2

p3 p4

Punkt x y

p1 0 2p2 2 0p3 3 1p4 5 1

L1 p1 p2 p3 p4

p1 0 4 4 6p2 4 0 2 4p3 4 2 0 2p4 6 4 2 0

L2 p1 p2 p3 p4

p1 0 2,828 3,162 5,099p2 2,828 0 1,414 3,162p3 3,162 1,414 0 2p4 5,099 3,162 2 0

L∞ p1 p2 p3 p4

p1 0 2 3 5p2 2 0 1 3p3 3 1 0 2p4 5 3 2 0

9

17

Ähnlichkeit binärer Objekte [x1, x2, …, xn] und [y1, y2, …, yn] (xi, yi 0,1 )

f00 : Anzahl von Attributen mit xi = 0 und yi = 0 f01 : Anzahl von Attributen mit xi = 0 und yi = 1 f10 : Anzahl von Attributen mit xi = 1 und yi = 0 f11 : Anzahl von Attributen mit xi = 1 und yi = 1

Ähnlichkeitsmaße Simple Matching Coefficient SMC

Nachteil:Bei Objekten mit vielen 0-wertigen Attributen wären alle einander sehr ähnlich

Jaccard Coefficient J

11100100

1100

Attributealler Anzahl

Attributeiger gleichwert Anzahl

ffff

ffSMC

111001

11

Objektebeider Attributewertiger -0nicht aller Anzahl

Objektenbeiden in Attributewertiger -1 Anzahl

fff

fJ

18

Ähnlichkeitsmaße für Vektoren [x1, x2, …, xn] und [y1, y2, …, yn] (1)

einfaches Matching Kosinus-Koeffizient

nur solche Attribute gehen ein, bei denen in x und y verschieden von 0sind

Attribute mit hohen Werten gehen stärker ein als andere

Kosinus des Winkels zwischen x und y

cos(0) = 1

für Vektoren gleicher Richtung

cos(90°) = 0

für orthogonale Vektoren

cos(180°) = -1

für entgegengesetzt gerichtete Vektoren

wirkt als normalisierter Korrelationskoeffizient

entspricht für normalisierte Vektoren dem einfachen Matching

n

kk

n

kk

n

kkk

yx

yxyxsim

1

2

1

2

1

*

),(

n

kkk yxyxsim

1

),(

10

19

Eigenschaften des einfachen Matching

Eigenschaft Verhalten Bedeutung Winkel je kleiner der Winkel zwischen

zwei Vektoren gleicher Euklidischer Länge, desto größer der Ähnlichkeitswert

Richtung („Thema“ beim Text-Mining) dominiert das Maß

Länge längerer Vektor hat größeren oder gleichen Ähnlichkeitswert

„The more, the better“

Änderung einzelner Kompo- nenten

Verstärkung einzelner Komponenten: Ähnlichkeitswert größer,

wenn die gleiche Komponente im anderen Vektor 0

sonst gleich bleibend

Einfluss von Einzel-komponenten

beliebig hoher Ähnlichkeitswert durch Veränderung eines einzelnen Wertes möglich

Einzelwerte können Ähnlichkeitswert dominieren

Objekte, die in vielen Attributen sehr unähnlich sind, können trotzdem einen sehr hohen Ähnlichkeitswert erhalten

Werte-bereich

0 ≤ sim(x,y) ≤ ∞ es gibt kein Maximum, d.h. keinen Begriff einer idealen Bewertung

20

Einfache Übereinstimmung d1 d2 d3 d4 d5 d6 d1 - 6.0 12.0 3.0 21.0 9.0 d2 6.0 - 12.0 3.0 21.0 9.0 d3 12.0 12.0 - 6.0 42.0 18.0 d4 3.0 3.0 6.0 - 9.0 9.0 d5 21.0 21.0 42.0 9.0 - 35.0 d6 9.0 9.0 18.0 9.0 35.0 -

Eigenschaften der einfachen Methode

Beispiel aus dem Text–Mining:Vorkommen von Wörtern in Dokumenten d1, d2, d3, d4, d5, d6

Erhöhung der Häufigkeit eines Terms hat proportionalen Effekt auf Ähnlichkeitswert des Dokuments Beispiel: sim(d1,d4) < sim(d1,d6)

Beiträge verschiedener Terme sind voneinander unabhängig hohe Werte für „Super“, „Diesel“ und „Akku“ in d5 sorgen für hohe

Ähnlichkeitswerte von d5 absurde Ergebnisse bei Anwendung auf nicht-normalisierte Vektoren

Beispiel: sim(d1,d3) > sim(d1,d2), obwohl d1 und d2 identisch sind

d 1 d 2 d 3 d 4 d 5 d 6Toyota 1 1 2 1 1 1 Honda 1 1 2 0 2 0 hybrid 1 1 2 1 3 3 Super 1 1 2 0 4 0 Diesel 1 1 2 1 5 5 Akku 1 1 2 0 6 0

11

21

Eigenschaften des Kosinus - Koeffizienten

Eigenschaft Verhalten Bedeutung Winkel je kleiner der Winkel zwischen zwei

Vektoren, desto größer der Ähnlichkeitswert

Länge als Folge der Normalisierung keine Veränderung des Ähnlichkeitswertes bei Veränderung des Radius

Richtung (= „Thema“ beim Text-Mining) dominiert das Cos-Maß vollständig

Änderung einzelner Kompo- nenten

Verstärkung einzelner Komponenten: Ähnlichkeitswert wird größer, wenn dadurch der

Winkel zwischen den Vektoren verkleinert wird

wird kleiner, wenn dadurch der Winkel zwischen den Vektoren vergrößert wird

Einfluss der Einzelkompo- nenten

Ähnlichkeitsmaß bestimmt durch Ähnlichkeit der Proportionen (Verhältnis der Werte in den einzelnen Vektoren)

Werte-bereich 0 ≤ sim(x,y) ≤ 1 es gibt ein Maximum, d.h. einen Idealwert

22

Eigenschaften des Kosinus-Koeffizienten: Beispiele

Ähnlichkeitswert eines Dokuments wird allein durch sein „Thema“ (Relation der Terme innerhalb des Dokuments) bestimmt

Beispiel: sim(d1,d2) = sim(d1,d3)

Termgewichtsbeziehungen zwischen den in den Dokumenten vorkommenden Termen werden möglicherweise ignoriert

Beispiel: sim(d5,d1) > sim(d5,d6)

Nullwerte haben große Auswirkung auf das Ergebnis

Beispiel: sim(d1,d5) > sim(d1,d6)

Kosinus - Koeffizient d1 d2 d3 d4 d5 d6 d1 - 1.000 1.000 0.707 0.898 0.621 d2 1.000 - 1.000 0.707 0.890 0.621 d3 1.000 1.000 - 0.707 0.898 0.621 d4 0.707 0.707 0.707 - 0.544 0.878 d5 0.898 0.898 0.898 0.544 - 0.620 d6 0.621 0.621 0.621 0.878 0.620 -


12

23

Ähnlichkeitsmaße für Vektoren [x1, x2, …, xn] und [y1, y2, …, yn] (2)

Dice-Koeffizient(erweiterter Jaccard-Koeffizient)

Tanimoto-KoeffizientOverlap-Koeffizient

Einbeziehen des Anteils gemeinsamer Einträge:

• Summe gemeinsamer Einträgen ≠ 0, relativ zu

• Summe aller Einträge ≠ 0

Multiplikation mit 2, um Wertebereich zwischen 0.0 und 1.0 zu erhalten (binäre Vektoren)

bestraft Vorhandensein einer kleinen Anzahl gemeinsamer Einträge stärker als Dice-Koeffizient:

• je weniger gemeinsame Einträge ≠ 0, desto größer der Nenner, desto kleiner der Wert des Bruches

Maß für Inklusion

erreicht 1.0, wenn jede Dimension ≠ 0 in X auch ≠ 0 in Y, und umgekehrt (binäre Vektoren)

erreicht 1.0, wenn in einem Vektor die Attribute aller Dimensionen ≤ der des anderen Vektors sind

sim(x,y)=1, if

i (xi yi) or i (yi xi)

∑ ∑

∑

1 1

1

y x

y x2

) ,( n

k

n

kkk

n

kkk

yxsim

∑∑∑

∑

11

2

1

2

1

y x-y x

yx

) ,( n

kkk

n

kk

n

kk

n

kkk

yxsim

∑ ∑

∑

1 1

1

) y , xmin(

)y ,min(x

) ,( n

k

n

kkk

n

kkk

yxsim

24

Einfaches Matching d1 d2 d3 d4 d5 d6 d1 - 6.0 12.0 3.0 21.0 9.0 d2 6.0 - 12.0 3.0 21.0 9.0 d3 12.0 12.0 - 6.0 42.0 18.0 d4 3.0 3.0 6.0 - 9.0 9.0 d5 21.0 21.0 42.0 9.0 - 35.0 d6 9.0 9.0 18.0 9.0 35.0 -

Kosinus d1 d2 d3 d4 d5 d6 d1 - 1.000 1.000 0.707 0.898 0.621 d2 1.000 - 1.000 0.707 0.890 0.621 d3 1.000 1.000 - 0.707 0.898 0.621 d4 0.707 0.707 0.707 - 0.544 0.878 d5 0.898 0.898 0.898 0.544 - 0.620 d6 0.621 0.621 0.621 0.878 0.620 -

Overlap d1 d2 d3 d4 d5 d6 d1 - 1.000 1.000 1.000 1.000 0.500 d2 1.000 - 1.000 1.000 1.000 0.500 d3 1.000 1.000 - 1.000 0.916 0.555 d4 1.000 1.000 1.000 - 1.000 1.000 d5 1.000 1.000 0.916 1.000 - 1.000 d6 0.500 0.500 0.555 1.000 1.000 -

Dice d1 d2 d3 d4 d5 d6 d1 - 1.000 1.333 0.666 1.555 1.200d2 1.000 - 1.333 0.666 1.555 1.200d3 1.333 1.333 - 0.800 2.545 1.714d4 0.666 0.666 0.800 - 0.750 1.500d5 1.555 1.555 2.545 0.750 - 2.333d6 1.200 1.200 1.714 1.500 2.333 - Tanimoto (erweiterter Jaccard) d1 d2 d3 d4 d5 d6 d1 - 1.000 2.000 0.500 3.500 1.500d2 1.000 - 2.000 0.500 3.500 1.500d3 2.000 2.000 - 0.666 -4.66 6.000d4 0.500 0.500 0.666 - 0.600 3.000d5 3.500 3.500 -4.66 0.600 - -7.00d6 1.500 1.500 6.000 3.000 -7.00 -


Ähnlichkeitsmaße im Vergleich

13

25

Korrelation (nach Pearson) [ empirischer Korr.-Koeff. (n-1) → n ]

Grad der linearen (und dieser!) Abhängigkeit 2er Attribute Wird typischerweise für Zeitreihen 2er Attribute verwendet, z.B.

• monatliche Durchschnittstemperatur über ein Kalenderjahr• stündlich ermittelter Aktienkurs über einen Börsentag

-1 ≤ corr(x,y) ≤ +1• corr(x,y) = -1 perfekte neg. lineare Abh.• corr(x,y) = 0 keine lineare Abh.• corr(x,y) = +1 perfekte pos. lineare Abh.

n

kk

n

kk

n

kkk

n

kk

n

kk

n

kkk

yx

xy

)y-(y)x-(x

)y-)(yx-(x

)y-(yn-

)x-(xn-

)y-)(yx-(xn-

ss

s

) std_abw(y) stdt_abw(x

x,y)covarianz( corr(x,y)

1

2

1

2

1

1

2

1

2

1

1

1

1

1

11

Beispiele

x=[-3,6,0,3,-6]y=[1,-2,0,-1,2] corr(x,y) = -1, denn y = - ⅓ x

x=[3,6,0,3,6]y=[1,2,0,1,2] corr(x,y) = 1, denn y= ⅓ x

26

KorrelationBeispiele: Streuungen bei Korrelationen zwischen -1 und 1

Autokorrelation

Korrelation zwischen aufeinander folgenden Intervallen innerhalb einer Serie von Messwerten.Z.B. Korrelation zwischen• stündlich

gemessenem Temperaturverlauf heute und

• stündlich gemessenem Temperaturverlauf gestern

14

27

2. Klassifikation

gegeben

Menge von Datenobjekten (DO) bekannter Klassenzugehörigkeit (Training Set)

jedes DO besteht aus Attributen

eines dieser Attribute ist die Klassenzugehörigkeit

gesucht

Modell, welches die Klassenzugehörigkeit als Funktion der (anderen) Attributwerte modelliert

Ziel

Datenobjekte, deren Klassenzugehörigkeit unbekannt ist so korrekt wie möglich klassifizieren

Evaluation des Modells

Ein Test Set (mit gleichfalls bekannter Klassenzugehörigkeit) wird verwendet

Üblicherweise wird die gegebene Datenmenge partitioniert in

• ein Training Set zur Modellbildung und

• ein Test Set zur Validierung des Modells

28

id Attribut1 Attribut2 Attribut3 Klasse

1 yes large 125 k no

2 no medium 100 k no

3 no small 70 k no

4 yes medium 120 k no

5 no large 95 k yes

6 no medium 60 k no

7 yes large 220 k no

8 no small 85 k yes

9 no medium 75 k no

10 no small 90 k yes

Training Set

Test Set

id Attribut1 Attribut2 Attribut3 Klasse

11 no small 55 k ?

12 yes medium 80 k ?

13 yes larg 110 k ?

14 no small 95 k ?

15 no large 67 k ?

Modell

Modelllernen

Modellanwenden

Induktion

Deduktion

Lern-Algorithmus

15

29

Klassifikations-Techniken Entscheidungsbäume

Regelbasierte Methoden

Nearest-Neighbor (NN) Klassifikation

Bestimmung der wahrscheinlichsten Klassenzugehörigkeit nach Bayes

Support Vector Machines

Neuronale Netze

Evaluierung des Modells Genauigkeit (Accuracy, Anteil der korrekten Ergebnisse im Test Set)

Fehlerrate (Error rate, Anteil der falschen Ergebnisse im Test Set)

ermittelte Klasse

0 1

tatsäch-liche Klasse

0 f00 f01

1 f10 f11

für binäre Klassifikation

11100100

1100

ffff

ffaccuracy

11100100

1001 ffff

ffrateerror

30

2.1 Induktion von Entscheidungsbäumen

Hunt‘s Algorithmus

1. Falls alle DO zur gleichen Klasse gehören, bilden sie ein Blatt des Entscheidungsbaumes.

2. Andenfalls wird

(1) ein Attribut gewählt,

(2) die Menge der DO entsprechend der auftretenden Attribut-Werte für dieses Attribut partitioniert, die je einen Nachfolge-Knoten bilden und

(3) der Algorithmus rekursiv auf diese Nachfolgeknoten und die verbleibenden Attribute angewandt.

16

31

Kd. Nr.

Haus-besitz

Familien-stand

jährliches Einkommen

offene Forderungen

1 yes ledig 125 k no

2 no verheiratet 100 k no

3 no ledig 75 k no

4 yes verheiratet 120 k no

5 no geschieden 95 k yes


7 yes geschieden 220 k no

8 no ledig 85 k yes


10 no ledig 90 k yes

‘n Beispiel: ausgebliebene Kredit-Tilgungen

binär diskret kontinuierlich Klassen-nominal rational zugehörigkeit

no

no

no

yes

yes

yes

vers

chie

dene

Kla

ssen

P

artit

ioni

erun

g bz

gl. e

ines

Attr

ibut

s

erstes ausgewähltes Attribut: Hausbesitz

Wertebereich: yes, no

32

Kd. Nr.

Familien-stand

jährliches Ein-

kommen

offene Forderungen

1 ledig 125 k no4 verheiratet 120 k no7 geschieden 220 k no

Hausbesitzer = yes

Kd. Nr.

Familien-stand


offene Forderungen

2 verheiratet 100 k no3 ledig 75 k no5 geschieden 95 k yes6 verheiratet 60 k no8 ledig 85 k yes9 verheiratet 75 k no

10 ledig 90 k yes

Hausbesitzer = no

Hausbesitzer

no Familienstand

yes no

no

yes

yes

yes

no

no

vers

chie

dene

Kla

ssen

P

artit

ioni

erun

g bz

gl. e

ines

Attr

ibut

s

17

33

Kd. Nr.


offene Forderungen

2 100 k no

6 60 k no

9 75 k no

Familienstand = verheiratet

Hausbesitzer

no Familienstand

yes no

Kd. Nr.


offene Forderungen

3 75 k no

8 85 k yes

10 90 k yes

Familienstand = ledig

Kd. Nr.


offene Forderungen

5 95 k yes

Familienstand = geschiedenno yes jährl. Eink.

verheiratetgeschieden

ledig

no

yes

verschiedene Klassen Partitionierung bzgl. eines AttributsAnsatz zur Behandlung des numer. Attr.: Grenze zwischen no und yes als

Mittelwert zwischen 75 und 85 schätzen

yesno

> 80 k≤ 80 k

34

Nachteile von Hunt‘s Algorithmus funktioniert nur dann mit vollständigem Ergebnis (im Sinne, dass es für jeden

neuen Fall eine Lösung liefert), wenn jede Kombination auch in den Trainingsdaten präsent ist

funktioniert nur für „scharfe“ Klassenzugehörigkeiten in den Trainingsdaten und liefert auch nur solche bei der Anwendung des Entscheidungsbaumes

Für folgende Fälle müssen zusätzliche Konstruktionsvorschriften erlassen werden:

Fall 1Für einen möglichen Attribut-Wert ist kein DO in den Trainingsdaten.

mögliche Lösung:mehrheitlich in den Trainingsdaten auftretende Klasse als Blatt an den Entscheidungsbaum anheften

Fall 2Alle DO einer Partition haben identische Attributwerte, ihre Klassen sind aber verschieden.

mögliche Lösung: mehrheitliche in dieser Partition auftretende Klasse als Blatt anheften

18

35

(1) genaue Spezifikation des Partitionierungs-Verfahrens

a) Festlegung der Attribut-Werte an den Kanten für jeden Attribut-Typ (insbes. für kontinuierliche Werte)

b) Festlegung eines „besten“ Attributs für die Partitionierung

(2) genauere Spezifikation von Stopp-Kriterien für den Algorithmus Wenn alle DO einer Partition zur selben Klasse

gehören? Wenn alle DO einer Partition den selben Wert für

das gewählte Attribut haben? Weitere Kriterien ???

offene Fragen

36

(1 a) Festlegung der Attribut-Werte an den Kanten

binäre Attribute jeder der beiden Werte bildet eine Kante

nominale Attribute (ohne Ordnungsrelation) jede Partitionierung der Attributwerte in nichtleere Wertemengen ist denkbar

Familienstand

verheiratet geschieden ledig

Familienstand

verheiratet ledig, geschieden

Familienstand

ledig verheiratet, geschieden

Familienstand

ledig, verheiratet geschieden

19

37

nominale Attribute (ohne Ordnungsrelation)

auch jede der 2k-1-1 Kaskadierungen der k verschiedenen Werte zu k-1binären Entscheidungen ist denkbar

Familienstand

ledig

Familienstand

≠ ledig

verheiratet geschieden

Familienstand

verheiratet

Familienstand

≠ verheiratet

ledig geschieden

Familienstand

geschieden

Familienstand

≠ geschieden

verheiratet ledig

38

ordinale Attribute (mit Ordnungsrelation) jede Partitionierung der Attributwerte in nichtleere Wertemengen ist auch

hierfür denkbar

Größe

small medium large

Größe

small medium, large

Größe

large small, medium

Größe

medium small, large

20

39

ordinale Attribute (mit Ordnungsrelation)

auch jede der 2k-1-1 Kaskadierungen der k verschiedenen Werte zu k-1 binären Entscheidungen ist denkbar

Größe

small

Größe

≠ small

medium large

Größe

medium

Größe

≠ medium

small large

Größe

large

Größe

≠ large

small medium

40

kontinuierliche AttributeWertebereich wird diskretisiert

Festlegung einer Anzahl n diskreter Wertebereiche

Festlegung von n-1 „split points“ x1, …, xn-1 zwischen diesen Werten

Zuordnung der kontinuierlichen Attribute zu diskreten nach Intervall-Zugehörigkeit

(x0 , x1] , (x1 , x2] , …, (xn-1 , xn) bzw.

x0 < x ≤ x1, x1 < x ≤ x2 , …, xn-1 < x ≤ xn

wobei x0 und xn auch – ∞ bzw. + ∞ sein können

jährl. Eink.

yesno

> 90 k≤ 70 k

maybe

> 70 k,≤ 90 k

21

41

(1 b) Wie findet man „das beste“ Attribut?

‘n Beispiel: vor dem Splitting gehören 10 DO zur Klasse 0 (C0) und 10 DO zur Klasse 1 (C1) als Attribute stehen zur Verfügung

• binäres Attribut „Besitz eines Autos“, Wertebereich ja, nein • nominales Attribut „bevorzugter Auto-Typ“, Wertebereich Familienfahrzeug,

Sportwagen, Luxuswagen • nominales Attribut „Matrikel-Nummer“, Wertebereich c1 , c2 , …, c20

Welches dieser Splittings ist „das beste“?

42

Wie findet man „das beste“ Attribut?

optimal: Knoten mit einheitlicher Klassenzugehörigkeit

ein Maß der „Unreinheit“ (impurity) erzeugter Knoten wird benötigt

inhomogenhohe „Unreinheit“

homogengeringe „Unreinheit“

je „verzerrter“ die Klassenverteilung ist, desto höher ist die Homogenität

im Beispiel wäre

C0: 10, C1: 0 und C0: 0, C1: 10 optimal

C0: 5, C1: 5 der denkbar schlechteste Fall

häufig verwendete Maße für „Unreinheit“ (impurity) sind

Entropie

Gini – Index

Klassifikationsfehler

22

43

Sei pi = p(i|a) der Anteil der DO hinter dem Knoten mit dem Attribut a, welche zur Klasse i gehören

im binären Falle gibt es nur p0 und p1, es gilt p1 = 1 – p0

Maße der „Unreinheit“ (impurity) sind

Entropie

Gini-Index

Klassifikationsfehler

wobei

m die Anzahl der Klassen ist

0 ld 0 = 0 in der Entropie-Kalkulation (wegen ) ist

diese Größen Knoten-bezogen für jeden Nachfolger Knoten berechnet werden

die „Güte“ eines Attributs wird daran gemessen wird, wie weit dieses Splitting die „Unreinheit“ verbessert: Vater-Knoten vs. alle Kind-Knoten (gewichteter Durchschnitt)

die Differenz der „Unreinheiten“ zwischen Vater- und Kinder-Knoten Informationsgewinn des Attributes a genannt wird: IG(a)

m

i

aipldaipaH1

)|( )|()(

m

i

aipaGini1

2)|(1)(

)|(max1)( aipaFi

0))((lim0

pldpp

44

Entropie, Gini und Klassifikationsfehler bei binärer Klassifikation

23

45

Entropie, Gini und Klassifikationsfehler am Beispiel

NC0: 4C1: 14

N1

C0: 0C1: 6

N2

C0: 1C1: 5

N3

C0: 3C1: 3

Vater-KnotenH(N) = - 4/18*ld(4/18) - 14/18*ld(14/18) = 0.764Gini(N) = 1 - (4/18)2 – (14/18)2 = 0.346F(N) = 1 – max(4/18, 14/18) = 0.222

Kinder-KnotenH(N1) = -0/6*ld(0/6)-6/6*ld(6/6) = 0Gini(N1)= 1 – 0/62 – 6/62 = 0F(N1) = 1 – max(0/6,6/6) = 0

H(N2) = -1/6*ld(1/6)-5/6*ld(5/6) = 0.650Gini(N2)= 1 – 1/62 – 5/62 = 0.278F(N2) = 1 – max(1/6,5/6) = 0.167

H(N3) = -3/6*ld(3/6)-3/6*ld(3/6) = 1Gini(N3)= 1 – 3/62 – 3/62 = 0.5F(N3) = 1 – max(3/6,3/6) = 0.5

Knoten)-Vater demgleich ( 222.0

)(18

6)(

18

6)(

18

6 )(

Knoten)-Vater als(besser 259.0

)(18

6)(

18

6)(

18

6 )(

Knoten)-Vater als(besser 550.0

)(18

6)(

18

6)(

18

6 )(

321

321

321

NFNFNFNF

NGiniNGiniNGiniNGini

NHNHNHNH

all

all

all

gewichteter Durchschnitt aller „Kinder“

Informationsgewinn

IGH = H(N) - H( Nall ) = 0.214

IGGini= Gini(N) - Gini( Nall ) = 0.087

IGF = F(N) - F( Nall ) = 0

46

Splitting verschiedener Attribut-TypenBinäre Attribute

NC0: 6C1: 6

N1

C0: 4C1: 3

N2

C0: 2C1: 3

yes no

Split mit binärem Attribut a

NC0: 6C1: 6

N1

C0: 1C1: 4

N2

C0: 5C1: 2

yes no

Split mit binärem Attribut b

Attribut a Attribut bGini(N) 0.5Gini(N1) 0.4898 0.3200Gini(N2) 0.4800 0.4082Gini(Nall) 0.4857 0.3714IG 0.0143 0.1286

ist zu bevorzugen

24

47

Splitting verschiedener Attribut-TypenNominale Attribute

Vergleich der Partitionierungen

Wertebereich: verheiratet,ledig,geschieden

NC0: 10C1: 10

N1 N2 N1 N2 N1 N2 N1 N2 N3

Partition l v, g v l, g g l, v v l g

C0 8 2 1 9 1 9 1 8 1C1 0 10 3 7 7 3 3 0 7

Gini(N) 0.5

Gini(N1 ) 0 0.3750 0.2188 0.3750

Gini(N2 ) 0.2778 0.4922 0.3750 0

Gini(N3 ) 0.2188

Gini(Nall ) 0.1667 0.4688 0.3124 0.1625

IG 0.3333 0.0312 0.1876 0.3375

ist zu bevorzugenErgebnis ist nicht verwunderlich Die anderen Partitionierungen enthalten

Verschmelzungen von Partitionen des “Siegers“ Verschmelzungen erhöhen die „Unreinheit“

48

Splitting verschiedener Attribut-TypenKontinuierliche Attribute

Finden geeigneter Split-Werte

‘n Beispiel

Klasse No No No Yes Yes Yes No No No No

Jahres-einkommen

60 70 75 85 90 95 100 120 125 220

Variante 1 Bestimmung genau eines Split-Wertes vsplit (Gini-) Optimum der Mittelwerte zwischen den DO

vsplit 65 72.5 80 87.5 92.5 97.5 110 122.5 172.5

v ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ >

No 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1

Yes 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0

Gini 0.400 0.375 0.343 0.417 0.400 0.300 0.343 0.375 0.400

Opti-mum vsplit = 97.5

Attribut v

v > vsplitv ≤ vsplit

25

49

Splitting verschiedener Attribut-TypenKontinuierliche Attribute

Finden geeigneter Split-Werte

das gleiche Beispiel

Klasse No No No Yes Yes Yes No No No No

Jahres-einkommen

60 70 75 85 90 95 100 120 125 220

Variante 2 Bestimmung mehrerer Split-Werte v1

split , v2split , ..., vn

split Mittelwerte zwischen benachbarten DO verschiedener Klassenzugehörigkeit

v1split = 80 v2

split = 97.5

Attribut v

v>vnsplitv≤v1

split v1split<v≤v2

split

••••••

vsplit 80 97.5

v v ≤ 80 80 < v ≤ 97.5 v > 97.5

No 3 0 4

Yes 0 3 0

Gini(Ni) 0 0 0

Gini(v) 0

50

Gewinn-Verhältnis (Gain Ratio)

Reinheitsmaße wie Gini und Entropie protegieren Attribute mit vielen verschiedenen Werten

die Anzahl der DO pro Unterbaum ist dabei allerdings kleiner als bei Attributen mit wenigen Werten

Extremfall: ein DO pro Unterbaum (siehe rechten Split im Bild) – perfekter Informationsgewinn, aber untauglich als generelles Modell

Hat man zu wenig DO (oder gar nur eines), kann man daraus keine statistisch relevanten Aussagen für die Gesamtheit der Objekte ableiten.

eine Lösung ausschließlich binäre Splits (wie im Entscheidungsbaum-Algorithmus CART)

nominale und kontinuierliche Attribute notfalls kaskadieren

26

51

Gewinn-Verhältnis (Gain Ratio)

eine andere Lösung

Informationsgewinn zur Anzahl der DO in den Unterbäumen ins Verhältnis setzen (wie es z.B. der Entscheidungsbaum-Algorithmus C4.5 tut):

k

i

i

n

npipldip

aIG

1

))(()( Info-Split

with

Info-Split

)( Ratio-Gain

Menge von n DO wird in k Untermengen mit je ni DO partitioniert Informationsgewinn (Gain-Ratio) wird durch die Entropie der Partitionierung (Split-

Info) relativiert die Entropie (im Nenner) steigt

(1) mit größer werdender Anzahl von Unterbäumen und(2) kleiner werdenden Anteilen der DO des Vater-Knotens im Unterbaum

Partitionierungen mit höherer Entropie (größerer Anzahl kleinerer Partitionen) werden “bestraft”

52

Ein Algorithmus zur Konstruktion eines Entscheidungsbaumes

input Menge von DO mit bekannter Klassenzugehörigkeit (Examples) E Menge von Attributen (features) Foutput Zeiger auf einen Entscheidungsbaum root

TreeGrowth(E,F)if stopping_cond(E,F) then

leaf = create_node()leaf.label = classify(E)return leaf

elseroot = create_node()root.test_cond = find_best_split(E,F)F := F \ root.test_condValues := value: value is possible value of root.test_condfor each v ϵ Values do

Ev := example: example ϵ E, root.test_cond(example) = vchildv := TreeGrowth(Ev,F)add childv as descendent of root and label the edge root→childv as v

end forend ifreturn root

27

53

Ein Algorithmus zur Konstruktion eines Entscheidungsbaumes create_node() erweitert den Baum um einen neuen Knoten, welcher

entweder ein Attriubut (node.test_condition) oder eine Klasse (node.label) enthält (Blattknoten).

find_best split(E,F) ermittelt das beste Attribut (und ggf. die besten Splitt-Werte dieses Attributs) auf der Basis eines „Reinheitsmaßes“ (Gini, Entropie), ggf. erweitert um das Gewinn-Verhältnis

classify(E) bestimmt die Klasse, die einem Blatt t des Entscheidungsbaumes zugeordnet wird, vernünftigerweise die mehrheitlich vertretene Klasse:leaf_label := l: l ϵ Et , p(i|t): p(i|t) > p(l|t).

Zusätzlich könnte man eine geschätzte Wahrscheinlichkeit für die Korrektheit dieser Klassenzugehörigleit p(l|t) hinzufügen.

stopping_cond(E,F) beendet den rekursiven Aufbau des Entscheidungsbaumes.

Sinnvolle Stopp-Bedingungen sind:

Ein großer Anteil der DO (im „perfekten“ Fall alle) gehören zur selben Klasse.

Die Anzahl der DO hat ein gewisses Minimum unterschritten.

Algorithmen dieser Grundstruktur findet man u.a. aufhttp://www.kdnuggets.com/software/classification-decision-tree.html

54

Model Overfitting

Fehlerquellen

1. Trainingsfehler (training errors, resubstitution error, apparent error)

falsch klassifizierte Trainingsdaten

2. Generalisierungsfehler (generalization errors)

fehlerhafte Verallgemeinerung von Trainingsdaten auf neue Fälle

Trainingsfehler können beliebig weit (bis hin zu Null bei hinreichend vielen relevanten Attributen) reduziert werden

allerdings zum „Preis“ steigender Komplexität des Modells

Passt das Modell allerdings zu perfekt zu den Trainingsdaten, wird es ab einem bestimmten Punkt sogar schlechter bei der Anwendung auf Testdaten.

Diesen Effekt nennt man Model Overfitting.

Ist das Modell jedoch zu einfach, sind beide Fehlerraten (Trainings- und Generalisierungsfehler) hoch.

Diesen Effekt nennt man Model Underfitting.

28

55

Model Overfitting‘n Beispiel: 2 Klassen, 2 kontinuierliche Attribute x1, x2

Trainings - DO: siehe Abb.rote Kreise:0.5 sqrt(x1

2+x22) 1

blaue Dreiecke:sqrt(x1

2+x22) < 0.5 oder sqrt(x1

2+x22) > 1

• perfekte Modellierung (Klassifikations-fehler über den Trainingsdaten = 0)

Overfitting

Underfitting

56

Ursachen des Model Overfitting

1. Overfitting durch verrauschte Daten

verrauschte Daten

= Trainingsdaten mit falscher Klassenzugehörigkeit, z.B.

Spezies Körper-Temp.lebend gebäh-

rend

vier-beinig

hält Winter-schlaf

Säuge-tier?

Igel Warmblütler ja ja ja ja

Katze Warmblütler ja ja nein ja

Fledermaus Warmblütler ja nein ja nein

Wal Kaltblütler ja nein nein nein

Salamander Kaltblütler nein ja ja nein

Komodo-Waran Kaltblütler nein ja nein nein

Python Kaltblütler nein nein ja nein

Lachs Kaltblütler nein nein nein nein

Adler Warmblütler nein nein nein nein

Guppy Kaltblütler ja nein nein nein

29

57

„perfektes“ Modell0 Fehler bzgl. der Trainingsdaten

nicht „perfektes“ Modell10 % Fehler bzgl. der Trainingsdaten

Körper-Temp.

keinSäugetier

KaltblütlerWarmblütler

lebendgebährend

vier-beinig

keinSäugetier

keinSäugetier

Säugetier

yes

yes no

no

Körper-Temp.

keinSäugetier


lebendgebährend

keinSäugetier

Säugetier

yes no

58

Effekt beider Modelle bzgl. Testdaten

TestdatenSpezies Körper-Temp.

lebend gebäh-

rend

vier-beinig

hält Winter-schlaf

Säuge-tier?

Mensch Warmblütler ja nein nein ja

Taube Warmblütler nein nein nein nein

Elefant Warmblütler ja ja nein ja

Leoparden-Hai Kaltblütler ja nein nein nein

Schildkröte Kaltblütler nein ja nein nein

Pinguin Kaltblütler nein nein nein nein

Aal Kaltblütler nein nein nein nein

Delphin Warmblütler ja nein nein ja

Ameisen-Igel Warmblütler nein ja ja ja

Gila-Krustenechse Kaltblütler nein ja ja nein

Trainingsfehler Performance

Fehlerrate über den Testdaten

„perfektes“ Modell 0 % 30 %

nicht „perfektes“ Modell 10 % 10 %

30

59

Ursachen des Model Overfitting

2. Overfitting in Ermangelung repräsentativer Daten

zu wenig Trainingsdaten machen das Modell anfällig für Overfitting, z.B.

SpeziesKörper-Temp.

lebend gebäh-rend

vier-beinig

hält Winter-schlaf

Säu-getier?

Sala-mander

Kalt-blütler

nein ja ja nein

GuppyKalt-

blütlerja nein nein nein

AdlerWarm-blütler

nein nein nein nein

Winter-Nacht-schwal-be

Warm-blütler

nein nein nein nein

Schna-beltier

Warm-blütler

nein ja ja ja

Modell

Körper-Temp.

keinSäugetier


hältWinter-schlaf

vier-beinig

keinSäugetier

keinSäugetier

Säugetier

yes

yes no

no

Trainingsfehler PerformanceFehlerrate über den Testdaten

0 % 30 %

60

Abschätzung von Generalisierungsfehlern

1. Evaluierung über den Trainingsdaten

(Resubstitution Estimate, Optimistic Approach)

Annahme: Trainingsdaten repräsentieren alle (denkbaren) Daten gut‘n BeispielFehlerraten e 2er Modelle T1 und T2 verschiedener Komplexität generiert aus denselben Trainingsdaten Blattknoten enthalten mehrheitlich vertretene Klasse

+: 3: 0

+: 3: 1

+: 2: 1

+: 0: 2

+: 1: 2

+: 3: 1

+: 0: 5

+: 5: 2

+: 1: 4

+: 3: 0

+: 3: 6

T1 T2

e( T1 ) = 4 / 24 = 0.167

e( T2 ) = 6 / 24 = 0.25

31

61


2. Einbezug der Modell-Komplexität

2.1 Occam‘s Razor („Geiz-Prinzip“)

Hat man zwei Modelle mit demselben Generalisierungsfehler, ist das einfachere Model (mit weniger Knoten) zu bevorzugen.

2.2 Pessimistic Error Rate eg(T)

Zur Summe aller Fehlklassifikationen e( ti ) an den Blattknoten über den Trainingsdaten addiert man einen Malus („Strafe“) Ω( ti ) für jeden Blattknoten ti im Baum und bezieht das Resultat auf die Anzahl der DO in den Trainingsdaten:

tk

ii

k

iii

g N

TTe

tn

tteTe

)()(

)(

)]()([)(

1

1

62


Beispiele

+: 3: 0

+: 3: 1

+: 2: 1

+: 0: 2

+: 1: 2

+: 3: 1

+: 0: 5

+: 5: 2

+: 1: 4

+: 3: 0

+: 3: 6

T1 T2

Bei Ω(ti ) = 0.5 ist und

Bei Ω(ti ) = 1 ist und

3125.024

5.7

24

5.074)( 1

Teg 3333.0

24

8

24

5.046)( 2

Teg

458.024

11

24

174)( 1

Teg 417.0

24

10

24

146)( 2

Teg

32

63


2.3 Beschreibungskomplexität für Baum und dessen Fehlklassifikationen (Minimum Description Length Principle)

Man addiert

für jede Fehlklassifikation ein Maß zur binären Kodierung Beispiele cost( data | tree ) (z.B. für jede Fehlklassifikation einmal die Länge der Kodierung einer Beispiel-ID) ld( Anzahl der Klassen )

e.g. for 16 examples and 3 misclassifications cost(data|tree) = 3 * 4 = 12und, um Komplexität des Baumes zu „bestrafen“,

ein Maß der Länge der Beschreibung der binären Kodierung der Knoten des Baumes cost( tree ), z.B.

für Blattknoten die Länge der Kodierung der zugeordneten Klasse ld( Anzahl der Klassen )

für jeden anderen Knoten die Länge der Kodierung des dort verzeichneten Attributs ld( Anzahl der Attribute ) :

e.g. for 5 leafs denoting 2 classes, 7 non-leafs denoting 4 attributes cost(tree) = 5 * 1 + 7 * 2 = 19

cost( tree , data ) = cost ( data | tree ) + cost( tree )

64


2.4 ... durch statistische Korrektur des Trainingsfehlers

Generalisierungsfehler sind typischerweise größer als Trainingsfehler.

können auch abgeschätzt werden werden, indem man eine bestimmte Wahrscheinlichkeit der Korrektheit der Klassifizierung beim Splitten an jeder „Astgabel“ unterstellt und deren obere Schranke (durch Multiplikation dieser Wahrscheinlichkeiten eines Pfades zu einem Blatt und Ermittlung des „schlechtesten Pfades“) ermittelt.

2.5 ... durch Anwendung auf eine Validierungsmenge

Trainingsmenge wird in 2 Teilmengen partitioniert,

eine zum Bilden des Modells

eine zum Testen des Modells

typisch: 2/3 der Beispiele zum trainieren, 1/3 zum validieren

33

65

Vermeidung des Overfitting bei Entscheidungsbäumen

1. Pre-Pruning (Early Stopping Rule)

Ansatz

restriktivere Stopp-Bedingung stopping_cond(E,F)

Stopp der Baumentwicklung bevor er 100% korrekt (bzgl. der Trainingsdaten) ist.

Typische Stopp-Bedingung:

Alle DO gehören zur selben Klasse.

Alle Attribut-Werte sind identisch.

Restriktivere Stopp-Bedingung

Anzahl der DO fällt unter einen gewissen Schwellwert

Klassenverteilung ist unabhängig von Attribut-Werten (Korrelation der Klassenzugehörigkeit fällt unter einen gewissen Schwellwert für alle verbleibenden Attribute)

Reinheitsgewinn durch Splitting (z.B. Gini, Informationsgewinn) unterschreitet einen gewissen Schwellwert

Problem

Auch ein geringer Reinheitsgewinn beim Splitten kann trotzdem hohen Reinheitsgewinne bei nachfolgenden Splittings nach sich ziehen.

66

Vermeidung des Overfitting bei Entscheidungsbäumen

2. Post-Pruning Entscheidungsbaum wird maximal weit entwickelt (gleiche Klasse oder gleiche

Attribut-Werte aller Beispiele)

danach wird der Baum v.u.n.o. beschnitten, d.h Ersetzung eines Unterbaums durch

ein Blatt, dessen Klasse durch die Mehrheit der DO im Unterbaum bestimmt wird (Subtree Replacement)

den am häufigsten (im Trainingsset) benutzten Unter-Unterbaum (Subtree Raising)

..., falls sich der Generalisierungsfehler dabei verringert.

Vorteil

I.allg. bessere Ergebnisse als Pre-Pruning, da es vom voll entwickelten Baum ausgeht und daher eine ungerechtfertigt frühen Abbruch des Splittings vermeidet.

Nachteil

höhere (Zeit-, Speicher-) Komplexität, da zunächst der vollständig „korrekte“ (bzgl. der Trainingsdaten) Baum entwickelt wird

34

67

Performance-Abschätzung eines Verfahrens zur Baumkonstruktion(nicht des Baumes!)(abgeleitet aus allen verfügbaren Beispielen)

1. Holdout – Methode

Partitionierung der klassifizierten DO in Trainings- und Test Set (z.B. je zur Hälfte oder 2/3 : 1/3)

Baumkonstruktion mit Trainings-Set, Performance-Abschätzung am Test Set

Nachteile

weniger Beispiele zur Modelbildung ⇒ schlechteres Modell Verteilung der Beispiele ist ein trade-off zwischen gutem Modell und belastbarer

Performance-Aussage Abhängigkeit der beiden Sets: Über-Repräsentanz einer Klasse im Trainings-Set

führt zu Unter-Repräsentanz im Test-Set und umgekehrt

68

Performance-Abschätzung eines Verfahrens zur Baumkonstruktion

2. Zufällige Partitionierung (Random Sub-Sampling) wiederholtes Holdout mit verschiedenen Partitionierungen

Ermittlung des Durchschnitts der Performance-Werte

Vorteil

Mehrere Modelle entstehen, von denen das beste ausgewählt werden kann

Nachteile

gleiche wie beim einfachen Holdout

keine Kontrolle darüber, wie oft ein DO für Training und Test benutzt wird

manche DO könnten viel öfter zum Training als zum Test verwendet werden und umgekehrt

35

69

3. Kreuz-Validierung (Cross-Validation) jedes DO wird

gleich häufig zum Training verwendet genau einmal zum Test verwendet

Partitionierung der Menge der klassifizierten DO in k gleich große Teilmengen

in k Durchläufen wird jede Partition genau einmal zum Test verwendet, während die Vereinigung aller anderen Partitionen zur Modellbildung verwendet wird

Ermittlung des Durchschnitts der k entstandenen Performance-Werte

Spezialfall

k = | Beispielmenge | , genannt „leave one out“ Ansatz

Vorteile

nutzt so viel wie möglich Beispiele zur Modellbildung

Test Sets sind disjunkt

Nachteile

hohe Komplexität des Verfahrens | Beispielmenge | Durchläufe

Zuverlässigkeit der Performance-Aussage wird geschwächt, da diese Aussagen aus nur je einem Beispiel entstanden


70

4. Bootstrap in allen vorherigen Verfahren kam kein Beispiel mehrfach als Trainings-Beispiel (im

selben Zyklus) in Betracht

hier wird ein Trainings-Set durch zufällige Auswahl aus der gesamten Menge klassifizierter Beispiele generiert (Sampling with replacement)

d.h. ein gewähltes DO kann mit einer gewissen Wahrscheinlichkeit mehrfach im Trainings-Set vorkommen

wählt man nach dieser Methode (Auswählen und Zurücklegen) N Trainings-Beispiele aus einer Menge von N Daten aus, enthält das Trainings-Set ca. 63,2 % der Original-Menge klassifizierter Beispiele:

Wahrscheinlichkeit, gewählt zu werden ist 1-(1-1/N)N

für N →∞ konvergiert dieser Wert zu 1-1/e ≈ 0.632. DO, die auf diesem Wege nicht im Trainings-Set landen, werden ins Test-Set

aufgenommen

wiederholt man dieses Verfahren b mal und erhält jeweils eine Korrektheits-Rate ϵi

(i=1...b), lässt sich die Korrektheits-Rate accboot (bei einer tatsächlichen Korrektheit accs über allen DO, die man nur mit 1 abschätzen kann), wie folgt ermitteln:

b

isiboot acc

bacc

1

)368.0632.0(1


36

71

Entscheidungsbäume über regulären PatternsGrundidee

1. In einer großen Datenmenge sollen Muster erkannt werden

2. Unbekannte Datensätze sollen entsprechend vorgegebener, schon klassifizierter Beispiele klassifiziert werden

Ziel

Finden eines Algorithmus, der dies leistet

Formal

Gegeben: Große Menge W von Daten (Wörtern über einen Alphabet)

Gesucht: Muster p, das den Daten zugrunde liegt (Wörter variablen Teilen)

Gibt es ein Lernverfahren zur Lösung des Problems?

WBeispielHypothese

Beispiel passt nicht Neue Hypothese generieren, bis Beispiel passt

Beispiel passt Hypothese beibehalten, nächstes Beispiel wählen

72

Alle Proteine setzen sich aus Aminosäuren zusammen (20 verschiedene)

Darstellung als Ketten über dem Alphabet

Aas = A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y

Protein = nichtleeres Wort über Aas (z.B. DKLMPQSST), aus bis zu 1000 Aminosäuren

Membran-Proteine

Bestimmte Proteine werden innerhalb einer Zelle hergestellt

Sie verlassen danach die Zelle, um an anderer Stelle des Körpers verwertet zu werden oder zur Kommunikation mit anderen Zellen beizutragen

Zellwand/Membran ist nur durchlässig für kleine Moleküle und Ionen

Proteine können die Zelle nur verlassen, wenn sie eine Art „Kennwort“ (Signalpeptid) besitzen, eine bestimmte Abfolge von Aminosäuren am Ende der Aminosäurekette; das Signalpeptid weist sich an einem Membrankanal aus und darf passieren; dabei zieht es das Protein hinter sich her

Membran-Proteine besitzen außerdem mehrere Teilketten von Aminosäuren, die bei Nicht-Membran-Proteinen nur ganz selten vorkommen (Teilketten = Transmembran-Domänen)

Beispiel aus der Biologie:Lernverfahren am Beispiel der Analyse von Aminosäuresequenzen in Proteinen

37

73

ZieleAnhand einer großen Menge von Membran-Proteinen sollen die genauen Aminosäure-Zusammensetzungen der Signalpeptide bestimmt

werden die Transmembran-Domänen bestimmt werdenZiel ist es, neue Proteinstrukturen als Membran-Proteine oder Nicht-Membran-

Proteine zu klassifizieren

Anwendungsbereiche auf dem Gebiet der Medizin Korrektur von Erbkrankheiten

Erbkrankheiten können mit fehlerhaften Transportsignalen verbunden sein Früherkennung, Behandlung

Diagnose von Virenkrankheiten Viren können Kanäle in den Zellmembranen manipulieren, so dass sie nur noch von

Virenbausteinen passiert werden können.

Krebserkennung Störung von Transportwegen kann zu unkontrollierter Zellvermehrung führen

Bildung von Tumoren

Identifikation von Signalpeptiden und Transmembran-Domänen durch das Lernen von Entscheidungsbäumen über regulären Patterns

Beispiel aus der Biologie (2)

74

Beispiel:

A =a,b,c

p =aabx1cx2x3bax4

aabaaacbbcbaac,aabcccbbcbacc,aabbccaabaa,aabacbbbab L(p)

cab, aab , aabcaabab, aabbcbbba L(p)

Bemerkung: Ketten von Variablen

Ketten von Variablen sind nur dann sinnvoll, wenn

dargestellt werden soll, dass eine Mindestanzahl von Symbolen (mindestens so viele wie Variablen in der Kette stehen) an dieser Stelle erforderlich ist

Muster bzw. Regularitäten ausgedrückt werden sollen, z.B. x1x2 x1x2

Ein Pattern ist eine Zeichenkette über einem gegebenen Alphabet A und

einer Menge von Variablen X=x1,...,xn, die ein Muster beschreibt. Die

Variablen stehen für beliebige Zeichenfolgen über A (nicht für das leere Wort!).

Alle Wörter, die von einem Pattern p beschrieben werden, gehören zur von p

erzeugten Pattern-Sprache L(p).

Definition „Pattern“

38

75

Gegeben:

Endliches Alphabet A

Datenmenge W von Wörtern über A

Gesucht:

Möglichst einfaches Pattern p, so dass W eine möglichst große Teilmenge der von p erzeugten Pattern-Sprache L(p) ist

Probleme bei der Darstellung von Beispieldaten:

Beispieldaten können so unterschiedlich sein, dass sich nur eine Kette von Variablen (z.B. x1x2x3x4) zur Beschreibung eignet, d.h. kein konkretes Muster ist in den Beispieldaten erkennbar

„rein intuitiv“ könnte ein spezielleres Pattern die Daten besser beschreiben als eine Kette von Variablen, obwohl es nicht alle gegebenen Daten erzeugen kann

ein einziger Ausreißer kann schon verhindern, dass ein Pattern für die gegebenen Beispieldaten gefunden wird (schlecht z.B. bei fehlerhaften Daten)

ein Pattern könnte nicht ausreichen, um die Daten zu beschreiben, sondern erst zwei oder drei oder noch mehr verschiedene

Neuformulierung der Aufgabe:

76

Zwei Beispiele

Beispiel 1:A =a, b, cMenge der positiven Daten: P =aaabc, aaacbbaab, aaacabcabb, aaaabc, aaabbcbcc, aaabba, aaab, aaac, cbcabbc

Bis auf das letzte Wort beginnen alle Wörter in P mit aaa. Ein Pattern, das alle Wörter in W erzeugt, würde die Gestalt x1x2x3x4 haben. Wir würden aber sagen – vor allem wenn W sehr groß ist – dass aaax1 die Menge P viel besser beschreibt. cbcabbc könnte in der Praxis z.B. durch einen Übertragungsfehler entstanden sein, ist also ein Ausreißer Inkonsistenz des Modells mit zu den Beispielen ist mitunter sinnvoll

Beispiel 2:A =a, b, cMenge der positiven Daten: P =ab, aa, ac, aaa, abc, bb, bc, bac, bbbc

Das Pattern p1=x1x2 erzeugt P. Gleichzeitig werden alle Wörter aber auch entweder von dem Pattern p2=ax1 oder von p3=bx1 erzeugt. D.h. P L(p2) L(p3). P kann also besser als Vereinigung von endlich vielen konkreten Pattern-Sprachen dargestellt werden anstatt von einer Kette von Variablen. Beschreibung durch mehrere Patterns ist mitunter sinnvoll

39

77

Fehlerhafte, verrauschte Daten Daten enthalten Fehler (z.B. durch falsche Übermittlung oder fehlerhafte Datenträger)

Vermischte Daten Daten sind durch Mischen mehrerer Datenmengen entstanden, wobei jede Menge ihr

eigenes Muster enthält

Kompliziertes Regelsystem in den Daten Daten folgen nicht alle einer festen Regel, sondern einer Verknüpfung von Regeln, die

auf einer Menge von Pattern-Sprachen aufbauenz.B seien p1, p2, p3, p4 Patterns, und es gelten die folgenden Regeln:w L(p1) w Ww L(p1) und w L(p2) w Ww L(p1) und w (L(p2) L(p3) L(p4)) w WSonst w WMit einem Pattern kann man diese Wortmenge W nicht darstellen

Mutierte Daten Daten folgten ursprünglich einem festen Muster, sind aber durch individuelle Mutationen

von einem gemeinsamen Muster abgewichen (z.B. DNS-Teilsequenzen, in denen einzelne Aminosäuren ausgetauscht wurden)

Warum sind Inkonsistenz und/oder multiple Patterns in Praxi sinnvoll?

78

Ein Entscheidungsbaum über regulären Patterns ist ein Binärbaum T mit:

Jedes Blatt u in T ist mit einem Wert value(u) ϵ 0,1 versehen.

Jeder innere Knoten v in T ist mit einem regulären Pattern q(v) versehen.

Zu einem inneren Knoten v aus T bezeichne

left(v) den linken Sohn von v (nein-Zweig).

right(v) den rechten Sohn von v (ja-Zweig).

root(T) bezeichne den Wurzelknoten von T.

Entscheidungsbäume über regulären Patterns

Entscheidungsbäume dieser Art können zur binären Klassifikation von Wörtern (Entscheidung über die Zugehörigkeit zu einer Sprache) eingesetzt werden.

Was hat das mit „Data Mining zu tun?

Die Konstruktion eines solchen Entscheidungsbaumes aus (positiven und negativen) Beispielen ist Modellbildung im Sinne des Data Mining.

40

79

´n Beispiel...

A = a, b

Sprache L = ambna| m,n 1, m+n 3 z.B. aaba, abba, aaaaabbba, abbbbba,... P (= positive Beispiele)

z.B. aba, ababab, abab, aa, bba... N (= negative Beispiele)

Charakteristisch für alle Wörter in L ist: Sie fangen mit a an und hören mit ba auf

Folgt irgendwo im Wort ein a auf ein b außer ganz am Schluss, kann das Wort nicht zur Sprache gehören

w ϵ L(ax1ba)

w ϵ L(x1bax2) w ϵ N

w ϵ P w ϵ N

nein ja

nein ja

Notwendig: Wort fängt mit a an und hört mit ba auf

Falls irgendwo in der Mitte des Wortes hinter einem b ein a steht, gehört das Wort nicht zur Sprache (x2 darf nicht leer sein)

1 0

0

80

Gesucht: Möglichst einfacher Entscheidungsbaum über regulären Patterns, welcher die Zugehörigkeit eines Wortes zu einer Pattern-Sprache entscheidet

‘n Beispiel:A = a,b,cP = abbaccba, cabbabccac, aac, babacN = cbba, acbbca, aabbb

abx1

x1abx2 1

x1bx1bbx2

x1a 1 01

1 0

nein ja

x1bbx2

1 x1ccx2

0 1

janein

Was bedeutet „möglichst einfach“?

Beide Bäume klassifizieren o.g. Beispiele korrekt, aber der linke Baum einfacher.Das liegt daran, dass die Patterns im linken Baum für die Gestalt der Beispiele „relevanter“ sind als die im rechten Baum. nötig:

Def. der „Relevanz“ eines Patterns speziellstes Pattern, welches möglichst viele Elemente aus P und möglichst

wenige Elemente aus N abdeckt.

41

81

Warum Entscheidungsbäume über regulären Patterns?

Robust gegenüber verrauschten Daten (mehrere verschiedene Patterns werden zur Klassifikation genutzt)

für Probleme in der Praxis gut geeignet

Positive und negative Beispiele werden im Lernverfahren in Betracht gezogen

Verschachtelte Zusammenhänge können in Baumform dargestellt werden

Regeln lassen sich präziser formulieren

z.B.: w L(p1) und w (L(p2) L(p3) L(p4)) w W

zunächst gesucht:

Sprache, die von gegebenem Entscheidungsbaum dargestellt wird

82

Gegeben: Alphabet Aas = A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y Entscheidungsbaum T

Gesucht: Sprache, die von T dargestellt wird, d.h. Sprache der Membran-Proteine

x1Dx2

x1Ex2 0

x1Px2

1 0

1

P N[10,9%, 76,5%]

P N[4,4%, 13,0%]

P N[6,6%, 3,9%]

P N[78,1%, 6,6%]

nein ja

84,7%

89,5%

Beispiel: zurück zu den Membran-Proteinen

Fast alle Proteine, welche die Aminosäuren E und P, aber nicht D enthalten, gehören zu den Transmembran-Proteinen.

L(T) enthält genau die Wörter über Aas , die nicht in L(x1Dx2 ), und entweder nicht in L(x1Ex2 ) oder in L(x1Ex2 ) , aber nicht in L(x1Px2 ) liegen:L(T)=w: (wL(x1Dx2)) ⋀ ((wL(x1Ex2))⋁((wL(x1Ex2))⋀(wL(x1Px2))))

Insgesamt wurden 84,7% der positiven und 89,5% der negativen Testbeispiele durch diesen Entscheidungsbaum korrekt klassifiziert.

42

Wie erzeugt man nun einen Entscheidungsbaum aus (positiven

und negativen) Beispielen?

P

N

q1

q2

q4

q3?

84

Idee

Ziel:

Aus positiven und negativen Beispielen einen möglichst einfachen Entscheidungsbaum generieren

Gesucht sind möglichst „gute“ Patterns

In jedem Knoten sollte möglichst viel Information über den Knoten gewonnen werden

Idee:

Entscheidungsbaum anhand des maximalen Informationsgewinnes in jedem Knoten gewinnen

Ansatz zur Ermittlung des Informationsgewinns: Entropie

43

85

Informationsgewinn bei regulären Patterns

Seien w ein (beliebiges) Wort, q ein Pattern

seien A, B Ereignisse:

B0,1 mit B=1 wP und B=0 wN

A0,1 mit A=1 wL(q), A=0 sonst

Gesucht ist ein Pattern q, das den Informationsgewinn maximiert, d.h.

möglichst viele Beispiele aus P und möglichst wenige aus N oder

möglichst viele Beispiele aus N und möglichst wenige Beispiele aus P

abdeckt:

IG(A,B) = H(B)-HA(B) max

B=0

P

N

)(qL

B=1

A=1

A=0

B ist nicht von q abhängig, es reicht also HA(B) min

HA=1(B) ist die Entropie von B unter der Bedingung dass ein Wort w zur Sprache L(q) des Patterns q gehört

HA=0(B) ist die Entropie von B unter der Bedingung dass ein Wort w nicht zur Sprache L(q) des Patterns q gehört

HA(B) = Hq(B) = p(A=1)HA=1(B) + p(A=0)HA=0(B)

86

NqLPqL

NqLqLwNwp

)()(

)())(|( Analog

zu denGleichungenoben

Herleitung von Hq(B)NwBPwBqLwA 0;1);(1 :Erinnerung

NP

NqLPqL

NP

NPqLqLwp

)()()()())(( PqL )(

NqL )(

P

N

)(qL)(\ qLN

)(\ qLP

)(\)(\

)(\))(|(

qLNqLP

qLNqLwNwp

)(\)(\

)(\))(|(

qLNqLP

qLPqLwPwp

NqLPqL

PqLqLwPwp

)()(

)())(|(

)))(|(())(|(

)))(|(())(|()()(

qLwNwpldqLwNwp

qLwPwpldqLwPwpBH qLw

)))(|(())(|(

)))(|(())(|()()(

qLwNwpldqLwNwp


)())(()())(()( )()( BHqLwpBHqLwpBH qLwqLwq

))((1)(\)(\)(\)(

))(( qLwpNP

qLNqLP

NP

qLNPqLwp

44

87

Ergebnis der Herleitung von Hq(B)

|)(\||)(\|

)(\

|)(\||)(\|

)(\

|)(\||)(\|

|)(\|

|)(\||)(\|

|)(\|

||||

|)(\||)(\|

|)(||)(|

)(

|)(||)(|

)(

|)(||)(|

|)(|

|)(||)(|

|)(|

||||

|)(||)(|

)(

qLNqLP

qLNld

qLNqLP

qLN

qLNqLP

qLPld

qLNqLP

qLP

NP

qLNqLP

NqLPqL

NqLld

NqLPqL

NqL

NqLPqL

PqLld

NqLPqL

PqL

NP

NqLPqL

BHq

88

Algorithmus

1. Konstruiere ein Blatt mit 0 bzw. 1, wenn P bzw. N die leere Menge ist

2. Wähle das Pattern q, welches die Entropie Hq(B) minimiert (d.h. den Informationsgewinn maximiert)

3. Schreibe q in die Wurzel des Baumes

4. Für den rechten Sohn des Knotens ermittle

- Pneu = L(q) ∩ P ,Nneu = L(q) ∩ N, also alle übrigen Worte in P bzw. N, die bereits mit dem Pattern q abgedeckt werden („Ja-Zweig“)

- Rufe den Algorithmus rekursiv mit Pneu und Nneu auf

5. Für den linken Sohn des Knotens wähle

- Pneu = P \ L(q) ,Nneu = N \ L(q), also alle übrigen Worte in P bzw. N, die nicht durch das Pattern q abgedeckt werden („Nein-Zweig“)

- Rufe den Algorithmus rekursiv mit Pneu und Nneu auf

P

N )(qL

45

89

Welche Patterns kommen für Schritt 2 in Frage?

nur solche Patterns, die mindestens ein Wort aus P oder N, d.h. aus M = P ∪ N erzeugen (alle anderen sind nutzlos)

aufeinander folgende Variablen werden zu einer einzigen Variablen zusammengefasst (z.B. abx1x2ba wird zu abx1ba)

macht das Pattern einfacher

verschlechtert die Güte der Lösung nicht wesentlich (da z.B. abx1ba alle Wörter, die sich aus abx1x2ba bilden lassen, einschließt)

Die Menge der „Kandidaten“ RPat(M), welche o.g. Bedingungen erfüllt, kann aus M systematisch erzeugt werden, indem man aus jedem Wort in w ∈ M alle dieses Wort erzeugende Patterns, welche o.g. Bedingungen erfüllen, konstruiert.

Die Anzahl dieser Patterns ist endlich, da w von endlicher Länge ist.

Wir wählen das Element aus RPat(M), welches den größten Informationsgewinn bringt.

Gibt es deren mehrere, wählen wir das kürzeste von denen.

90

Algorithmus zur Erzeugung von RPat(M)

1. Initialisiere RPat(M) := P N

2. für jedes Wort w ∈ P N führe folgende rekursive Funktion aus:

input: RPat(M)alt, ein Wort w oder ein Pattern q

output: RPat(M)neu

für alle n = 1 ... (laenge(w)-1):

für jedes n-elementige Teilwort t in w:

erzeuge ein Pattern q, indem t durch eine Variable ersetzt wird, wenn es nicht bereits an eine Variable grenzt oder eine Variable enthält

füge das so erzeugte Pattern q zu RPat(M) hinzu:

RPat(M)neu := RPat(M)alt q

Rufe die Funktion rekursiv mit RPat(M)neu auf

‘n Beispiel

Sei M = P N = aab , bb

Alle Patterns, welche die Worte aab und bb erzeugen, können nach o.g. Algorithmus systematisch konstruiert werden.

Dies ergibt RPat(M) = aab, x1ab, x1ax2,, ax1b, aax1, x1b, ax1, bb, bx1

46

91

Algorithmus zur Generierung eines Entscheidungsbaums

input: P, N

output: baum(Wurzel, linker_UB, rechter_UB)

function EBaum(P,N);

begin

if N = then EBaum := baum(1,nil,nil)

if P = then EBaum := baum(0,nil, nil)

if N ≠ and P ≠ then begin

Q:=q: q∈RPat(P∪ N), ∀ q‘∈RPat(P∪N): Hq(B) ≤Hq‘(B));

q := kürzestes Element aus Q;

Pr := L(q) ∩ P;

Nr := L(q) ∩ N;

Pl := P \ L(q);

Nl := N \ L(q);

EBaum := baum(q,EBaum(Pl,Nl), EBaum(Pr,Nr))

end

end;

92

‘n Beispiel

Sei P=aab , N=bb

RPat(P ∪ N) =aab, x1ab, ax1b, aax1, ax1, x1b, x1ax2, bb, bx1

Man berechne die Entropien Hq(B) für jedes Element q in RPat(P ∪ N)

Die Hq(B) verschiedener Patterns sind gleich, wenn diese Patterns in beiden entstehenden Unterbäumen gleiche Verhältnisse zwischen Beispielen aus P und N erzeugen, d.h. jeweils gleich viele Beispiele aus Pund N erzeugen

Beispiel: x1ab, ax1b sind gleichwertig, da sie genau ein Element in P und keines in N erzeugen

Gleiche Entropien ergeben sich also für

aab, x1ab, ax1b, aax1, ax1, x1ax2 (1 aus P, 0 aus N)

bb, bx1(0 aus P, 1 aus N)

x1b, (1 aus P, 1 aus N)

Die Berechnung gestaltet sich wie folgt:

47

93

PqL )(

NqL )(

P

N

)(qL)(\ qLN

)(\ qLP

aab

bb

Berechnung von Hq(B) mit q=x1ab

2

1

11

01)()())((

NP

NqLPqLqLwp

001

0

)()(

)())(|(

NqLPqL

NqLqLwNwp

110

1

)(\)(\

)(\))(|(

qLNqLP

qLNqLwNwp

01

0

)(\)(\

)(\))(|(

qLNqLP

qLPqLwPwp

101

1

)()(

)())(|(

NqLPqL

PqLqLwPwp

0)))(|(())(|(

)))(|(())(|()()(

qLwNwpldqLwNwp


0)0(0)1(1)))(|(())(|(

)))(|(())(|()()(

ldldqLwNwpldqLwNwp


x1ab

00)2

11(0

2

1)())(()())(( )()( BHqLwpBHqLwpH qLwqLwq

94

PqL )(

NqL )(

P

N

)(qL)(\ qLN

)(\ qLP

aab

bb

Berechnung von Hq(B) mit q=x1b

111

11)()())((

NP

NqLPqLqLwp

2

1

11

1

)()(

)())(|(

NqLPqL

NqLqLwNwp

000

0

)(\)(\

)(\))(|(

qLNqLP

qLNqLNwp

00

0

)(\)(\

)(\))(|(

qLNqLP

qLPqLwPwp

2

1

11

1

)()(

)())(|(

NqLPqL

PqLqLwPwp

0)))(|(())(|(

)))(|(())(|()()(

qLwNwpldqLwNwp


x1b

2

1

2

1)11(

2


2

10)

2

1(

2

1)))(|(())(|(

)))(|(())(|()()(

ldqLwNwpldqLwNwp


48

95

PqL )(

NqL )(

P

N

)(qL)(\ qLN

)(\ qLP

aab

bb

Berechnung von Hq(B) mit q=bx1

2

1

11

10)()())((

NP

NqLPqLqLwp

110

1

)()(

)())(|(

NqLPqL

NqLqLwNwp

001

0

)(\)(\

)(\))(|(

qLNqLP

qLNqLwNwp

101

1

)(\)(\

)(\))(|(

qLNqLP

qLPqLwPwp

010

0

)()(

)())(|(

NqLPqL

PqLqLwPwp

0)))(|(())(|(

)))(|(())(|()()(

qLwNwpldqLwNwp


0)1(1)0(0)))(|(())(|(

)))(|(())(|()()(

ldldqLwNwpldqLwNwp


bx1

00)2

11(0

2


96

Anwendung des Algorithmus

Beim ersten Aufruf des Algorithmus kommen wir in den else-Zweig wo wir alle Patterns mit minimaler Entropie auswählen

Knoten* EBaum(Menge P, Menge N)

if(N = )return [1,null,null];

else if(P = )return [0,null, null];

else

)];,(),,(,[return

;)(:

;)(:

;)(:

;)(:

);Längekürzester mit ausElement (:

));()(:)(()(|: ,,

rrll

l

l

r

r

qq

NPEBaumNPEBaumq

NqLN

PqLP

NqLN

PqLP

Qq

BHBHNPRPatqNPRPatqqQ

RPat(M) = aab, x1ab, ax1b, aax1, ax1, x1b, x1ax2, x1, bb, bx1Hq(B)= 0, 0, 0, 0, 0, ½, 0, ½, 0, 0

49

97



Dann wählen wir das kürzeste Element (bzw. davon das erste)




else

)];,(),,(,[return

;)(:

;)(:

;)(:

;)(:


));()(:)(()(|: ,,

rrll

l

l

r

r

qq

NPEBaumNPEBaumq

NqLN

PqLP

NqLN

PqLP

Qq



98



Dann wählen wir das kürzeste Element (bzw. davon das erste)

Es ergeben sich folgende Mengen:

Pr = aab = P

Nr = Pl = Nl = bb = N

Rekursion aufrufen für Pl

mit Nl und für Pr mit Nr




else

)];,(),,(,[return

;)(:

;)(:

;)(:

;)(:


));()(:)(()(|: ,,

rrll

l

l

r

r

qq

NPEBaumNPEBaumq

NqLN

PqLP

NqLN

PqLP

Qq



50

99

In der Rekursion

In der ersten Rekursion für den linken Sohn kommen wir in den Zweig mit P =

Wir erhalten also ein Blatt mit dem Wert 0




else

)];,(),,(,[return

;)(:

;)(:

;)(:

;)(:


));()(:)(()(|: ,,

rrll

l

l

r

r

qq

NPEBaumNPEBaumq

NqLN

PqLP

NqLN

PqLP

Qq


Pl = Nl = bb = N Pr = aab = P

Nr = 0

ax1

100

1

In der Rekursion

In der ersten Rekursion für den linken Sohn kommen wir in den Zweig mit P =


Durch Rückkehr kommen wir in die zweite Rekursion (die für den rechten Sohn)

Dort erreichen wir den Zweig für N =


Der Baum ist fertig!

Klar: das war ein Trivialfall




else

)];,(),,(,[return

;)(:

;)(:

;)(:

;)(:


));()(:)(()(|: ,,

rrll

l

l

r

r

qq

NPEBaumNPEBaumq

NqLN

PqLP

NqLN

PqLP

Qq


Pl = Nl = bb = N Pr = aab = P

Nr = 0

ax1

51

101

Verbesserung der Ergebnisse

Ideal: möglichst deutliche/„einfache“ Muster in Beispielmengen P und N

Verbesserungsmöglichkeiten:

die zugrundeliegenden Daten anders messen, z.B.:

das Datenformat ändern: (Monat[1..12],Tag[1..31],Jahr[00..99]) zu (Tag im Jahr[0..365], Jahr[00..99])

die Datenreihenfolge ändern: (T1T1T1T2T2T2J1J1J2J2...) zu (T1T1T1J1J1T2T2T2J2J2...)

andere Daten von der gleichen Quelle messen, z.B.:

nicht Datum und IP-Adresse speichern, sondern Datum und Kundennummer

vorhandene Daten vorklassifizieren, z.B.:

alle Einkäufe von Kunden erst in deren Altersgruppen zerlegen und dann nach Mustern suchen

entspricht einer Alphabetreduzierung, da weniger „Buchstaben“ (im Beispiel das Alter) in der Sprache vorkommen

102

2.2 Regelbasierte Klassifikatoren gegeben Datensatz

gesucht Regelwerk,welches die Daten möglichstkorrekt klassifiziert

R1: (lebend gebärend = nein) (kann fliegen = ja) VogelR2: (lebend gebärend = nein) (Wasserbewohner = ja) FischR3: (lebend gebärend = ja) (Blut Typ = warm) SäugerR4: (lebend gebärend = nein) (kann fliegen = nein) ReptilR5: (Wasserbewohner = halb) Amphibie

DO SpeziesBlut-Typ

Haut-struktur

lebend gebärend

Wasser-bewohner

kann fliegen

hat Beine

hält Winter-schlaf

Klasse

1 Mensch warm Haar ja nein nein ja nein Säuger2 Python kalt Schuppen nein nein nein nein ja Reptil

3 Lachs kalt Schuppen nein ja nein nein nein Fisch

4 Wal warm Haar ja ja nein nein nein Säuger5 Frosch kalt keine nein halb nein ja ja Amphibie

6 Waran kalt Schuppen nein nein nein ja nein Reptil

7 Fledermaus warm Haar ja nein ja ja ja Säuger8 Taube warm Federn nein nein ja ja nein Vogel

9 Katze warm Fell ja nein nein ja nein Säuger10 Guppy kalt Schuppen ja ja nein nein nein Fisch

11 Alligator kalt Schuppen nein halb nein ja nein Reptil

12 Pinguin warm Federn nein halb nein ja nein Vogel13 Igel warm Stacheln ja nein nein ja ja Säuger

14 Aal kalt Schuppen nein ja nein nein nein Fisch15 Salamander kalt keine nein halb nein ja ja Amphibie

52

103

Regel ri: Praemissei → Konklusioni

Coverage( ri )= Anz. DO mit wahrer Prämisse / Anz. aller DO

Accuracy( ri ) = Anz. DO mit wahrer Prämisse und wahrer Konlusion / Anz. DO mit wahrer Prämisse

Eine Regelmenge ist gegenseitig ausschließend, wenn es zu jedem DO höchstens eine Regel mit wahrer Prämisse gibt.

Nicht gegenseitig ausschließende Regelmengen können zu Klassenzugehörigkeits-Konflikten führen, welche wie folgt behandelt werden können:

Geordnete Regeln: Regeln werden nach Prioritäten (z.B. nach Accuracyoder Coverage) geordnet. Die höchste Priorität entscheidet die aus der Konfliktmenge anzuwendende Regel.

Ungeordnete Regeln: Alle Regeln der Konfliktmenge werden angewandt. Die Häufigkeit der Konklusionen (ggf. gewichtet mit den Regel-Accuracies) entscheidet die zuzuordnende Konklusion.

104

Ordnungs-Schemata geordneter Regeln

Regelbasierte Ordnung:

Ordnung nach einem Regel-Qualitätsmaß (z.B. Accuracy)

Klassenbasierte Ordnung:

Regeln gleicher Konklusion (Klasse) werden gruppiert.

Gruppen werden nach Konklusionen geordnet.

Innerhalb einer Gruppe ist die Reihenfolge dann unwichtig, weil ohnehin die gleiche Konklusion zugeordnet wird.

Eine Regelmenge ist vollständig, wenn jede Kombination von Attributwerten mindestens eine Regelprämisse wahr macht.

Unvollständige Regelmengen werden oft durch eine Default-Regel mit leerer Prämisse („wahr“, wenn keine andere Prämisse wahr ist) und einer Default-Konklusion ergänzt.

Die meisten Regelgenerierungs-Algorithmen verwenden klassenbasierte Ordnung.

53

105

Regelgenerierungsverfahren: direkte / indirekte Regelextraktion

Direkte Regelextraktion

Reihenfolge der Behandlung der Klassen kann abhängig sein von Anzahl zugehöriger DO Kosten einer Fehlklassifikation für jede Klasse Häufigkeit des Auftretens dieser Klasse (unabh. vom Trainings-Set)

Für eine Klasse DO dieser Klasse: positive Beispiele DO anderer Klassen: negative Beispiele

Algorithmus

E: Trainings SetY = y1 , y2 , ... , yk : geordnete Menge (Liste) aller KlassenR := (initiale) Liste der Regelnfor y = y1, ..., yk-1 do

while Stopp Bedingung nicht zutreffend dor ← LearnOneRule( E , y )entferne DO aus E, für welche die Prämisse von r wahr istfüge r der Regelmenge (am Ende) hinzu: R ← R ∪ r

end whileend forfüge Default Regel true → yk ans Ende der Liste hinzu

106

Eine Regel (für die betrachtete Klasse) ist gut, wenn sie• alle (oder die meisten) positiven und• (fast) keine negativenBeispiele für diese Klasse abdeckt.

Nachdem eine solche Regel gefunden wurde, werden die von ihr abgedeckten Beispiele aus dem Trainings-Datensatz entfernt:

(ii) Step 1 (iii) Step 2

R1

(iv) Step 3

R1

R2

54

107

Regelgenerierungsstrategien• top down (konklusionsgetrieben, general-to-specific)• bottom up (prämissengetrieben, specific-to-general)

top down Regelgenerierung• initiale Regel für eine Klasse yi: leere Liste (konjunktiv verknüpfter) Prämissen• der Prämissenliste werden systematisch neue Prämissen hinzugefügt• nächste Prämisse könnte z.B. ein Attribut sein, welches bei einem Wert

• eine max. Anzahl DO der betrachteten Klasse und• eine min. Anzahl DO anderer Klassen abdeckt.

bottom up Regelgenerierung• initiale Regel für eine Klasse yi wird aus einem DO dieser Klasse rekrutiert• Regel wird systematisch generalisiert durch Entfernung von Prämissen• Es werden solche Prämissen bevorzugt entfernt, durch deren Entfernung

• eine max. Anzahl DO dieser Klasse und• eine min. Anz. DO anderer Klassenzusätzlich abgedeckt wird

108

55

109

Regel-Evaluierungzwecks Ermittlung geeigneter Attribute zum Hinzufügen / Entfernen

Accuracy(r) zu verwenden ...

... ist nur auf den ersten Blick eine gute Idee, weil Coverage(r) unberücksichtigt bleibt:

Betrachten wir einen Datensatz mit 60 positiven und 100 negativen DO.

• Sei r1 eine Regel, welche 50 positive und 5 negative DO abdeckt.

• Sei r2 eine Regel, welche 2 positive und kein negatives DO abdeckt.

r2 hat die bessere Accuracy, aber r1 ist sicher die bessere Regel.

110

Betrachten erneut den Datensatz mit 60 positiven und 100 negativen DO.• Sei r1 eine Regel, welche 50 positive und 5 negative DO abdeckt.• Sei r2 eine Regel, welche 2 positive und kein negatives DO abdeckt.

Regel-Evaluierungzwecks Ermittlung geeigneter Attribute zum Hinzufügen / Entfernen

1. Statistischer TestErmittlung des Wahrscheinlichkeitsverhältnisses

i

ik

ii e

fldf R

1

2

k Anz. der Klassenfi Anz. der DO aus Klasse i, welche durch die Regel abgedeckt werdenei Anz. von DO aus Klasse i, welche durch eine beliebige Regel mit gleicher

Coverage abgedeckt würden,

99.9 34.375

5ld5

20.625

50ld502 )R(r

34.375160

10055e 20.625

160

6055e

5f 50f :r

1

-

-1

5.66 1.250

0ld0

0.750

2ld22 )R(r

1.250160

1002e 0.750

160

602e

0f 2f :r

2

-

-2

56

111

Regel-Evaluierung zwecks Ermittlung geeigneter Attribute zum Hinzufügen / Entfernen2. LAPLACE, m-estimatebeziehen die Coverage einer Regel mit ein

kn

frLaplace

1)( kn

pkfrestimatem

)(

n Anz. der DO, welche durch die Regel abgedeckt werdenf+ Anz. der pos. DO, welche durch die Regel abgedeckt werdenk Anz. der Klassenp+ Anteil der pos. DO im gesamten Trainings-Datensatz

Für p+=1/k ist Laplace(r) = m-estimate(r).

Betrachten erneut den Datensatz mit 60 positiven und 100 negativen DO.• Sei r1 eine Regel, welche 50 positive und 5 negative DO abdeckt.• Sei r2 eine Regel, welche 2 positive und kein negatives DO abdeckt.

8947.0255

150)( 1

rLaplace

8904.025516060

250)( 1

restimatem

75.022

12)( 2

rLaplace

6875.02216060

22)( 2

restimatem

112

Regel-Evaluierung zwecks Ermittlung geeigneter Attribute zum Hinzufügen / Entfernen3. FOIL‘s information gain

kombiniert den Informationsgewinn einer Regelmodifikation mit der Coverage nach der Modifikation

00

0

11

11 gain n informatio sFOIL'

np

pld

np

pldp

Erweitert man eine Regel von r: A → + zu r´: A ∧ B → + , so ist

p0 Anz. der pos. DO, welche durch r abgedeckt werden

n0 Anz. der neg. DO, welche durch r abgedeckt werden

p1 Anz. der pos DO, welche durch r´ abgedeckt werden

n1 Anz. der neg. DO, welche durch r´ abgedeckt werden

Betrachten erneut den Datensatz mit 60 positiven und 100 negativen DO.• Initial sei r: true +• Sei r1´ eine Regel, welche 50 positive und 5 negative DO abdeckt.• Sei r2´ eine Regel, welche 2 positive und kein negatives DO abdeckt.

83.2160

60

2

22)'(

87.63160

60

55

5050)'(

2

1

ldldrFOIL

ldldrFOIL

57

113

• Stopp-Kriterium des Regelgenerierungs-Algorithmus (page 105)• Berechne den Gewinn einer neuen Regel (statistisch, Laplace, m-estimate,

FOIL‘s information gain)

• Ist der Gewinn nicht signifikant, verwirf die neue Regel und stoppe den Algorithmus

• Regel Pruning• Analog zu den Entscheidungsbaum-Generierungs-Methoden neigen auch

Regelgenerierungs-Methoden zum Overfitting (siehe page 54 ff) und bedürfen ähnlicher Pruning Methoden (siehe page 60 ff).

• Algorithmische Aspekte• Der Regel – Generierungs - Algorithmus (siehe page 105) sieht ein

Entfernen derjenigen DO vor, die durch die gerade generierte Regel bereits abgedeckt werden.

• Solche Abdeckungen können sich auch überschneiden.

• Die Bewertung der inkrementellen Verbesserung durch eine neue Regel ist daher nur auf der Basis des Datensatzes nach der Entfernung bereits abgedeckter DO realistisch.

114

RIPPER Algorithmus

• weit verbreitet

• geeignet für unbalancierte Klassenverteilung der DO

• geeignet für verrauschte Daten

• Overfitting wird durch ein Validation Set vermieden

• 2-Klassen Problem

• mehrheitl. Klasse wird als default gesetzt

• Regeln für die Minderheits - Klasse werden generiert

• Multi-Klassen Problem

• Klassen werden nach steigender Häufigkeit sortiert: [y1 , y2 , ..., yc ]

• RIPPER beginnt mit der seltensten Klasse y1

• im i-ten Durchlauf werden Regeln für yi generiert, wobei

• DO für yi als pos. DO und

• alle anderen (yi+1, yi+2 ... yc) als neg. DO

eines 2-Klassen Problems behandelt werden

• es gibt c-1 Durchläufe, yc ist dann die default Klasse

58

115

RIPPER Algorithmus• top-down Regelgenerierung (siehe page 107)• FOIL‘s information gain wird genutzt, um die beste Prämisse zur weiteren

Verfeinerung der Regel auszuwählen• stoppt, wenn eine neue Prämisse auch neg. DO abdecken würde• nach Generierung einer Regel wird diese geprunt (s.u.), danach die durch sie

abgedeckten DO entfernt und die Regel hinzugefügt• Generierung neuer Regeln stoppt, wenn

1. eine hinzuzufügende Regel eine Description Length (ähnlich der bei Entscheidungsbäumen, siehe page 63) der Regelmenge um mind. d Bits erhöht (default: d = 64) oder

2. die Fehlklassifikations-Rate einer generierten Regel im Validation Set 50 % überschreitet

• post-Pruning jeder neuen Regel r ϵ R mit Hilfe eines Validation Sets• Metrik: vripper = (p-n)/(p+n) mit p = Anz. der pos. DO und n = Anz. der neg.

DO (≈ accuracy im Validation Set)• verbessert (vergrößert) sich diese Metrik durch Entfernung einer Prämisse,

wird diese auch entfernt• Pruning beginnt mit der letzten Prämisse und prüft Prämissen von hinten

nach vorn (von der letzten bis zur ersten)• während r vor dem Pruning nur pos. DO abdeckt, deckt r nach dem Pruning

pos. und neg. DO des Trainings-Sets ab.

116

Regelgenerierungsverfahren: direkte / indirekte Regelextraktion

Indirekte Regelextraktion

Es wird zunächst ein Entscheidungsbaum generiert, welcher dann zu Regeln transformiert wird.

einfacher Ansatz: aus jedem Pfad eine Regel generieren:

59

117

Indirekte Regelextraktion

Dieser Ansatz lässt sich optimieren, z.B.

r2 (P=no) (Q=yes) → +r3 (P=yes) (R=no) → +r5 (P=yes) (R=yes) (Q=yes) → +

zu

r2‘ (Q=yes) → +r3 (P=yes) (R=no) → +

beide Regel-mengenbeschreiben dieselbeBOOLEsche Funktion:

P Q R

no no no

no no yes

no yes no +

no yes yes +

yes no no +

yes no yes

yes yes no +

yes yes yes +

118

Indirekte RegelextraktionAnsatz des C4.5 Regelgenerierungs-Algorithmus

Regelgenerierung

• Es wird zunächst aus jedem Pfad des Entscheidungsbaums eine Regel generiert.

• Für die Entfernung jeder Konjunktion in der Prämisse wird die Pessimistic Error Rate (ähnlich der für Bäume, siehe Folie 61 f.: Anz. fehlklassifizierter DO + Malus für jede Prämisse) ermittelt.

• Diejenige Regel-Verkürzung, die zur kleinsten Pessimistic Error Rate führt, wird genommen, falls sich dadurch eine bessere Error Rate (über dem Validation Set) als die der Original-Regel ergibt.

• Die so entstandene verkürzte Regel wird demselben Verfahren unterzogen usw., bis sich in einem Durchlauf bei keiner Verkürzung eine Verbesserung ergibt.

• Dabei können Regeln identisch werden. Deshalb werden mehrfach vorkommende Regeln entfernt.

60

119

Indirekte RegelextraktionAnsatz des C4.5 Regelgenerierungs-Algorithmus

Regelsortierung

• klassenbasiert, Regeln derselben Klasse werden gruppiert

• Gruppen werden nach steigender Total Description Length (ähnlich wie bei Bäumen, siehe Folie 63) sortiert

• Description Length = Lexception + g * Lmodel mit

• Lexception Anz. Bits, die man zum Kodieren der fehlklassifizierten DO braucht

• Lmodel Anz. Bits, die man zur Kodierung des Modells (der Regeln) benötigt (viele und/oder lange Regeln führen zu hohen Werten)

• g Tuning-Parameter, welcher um so kleiner ist, je mehr redundante Attribute im Modell enthalten sind, default Wert: 0.5

120

Beispiel zum Vergleich von indirekter (C 4.5) und direkter (RIPPER) Methode

Name Give Birth Lay Eggs Can Fly Live in Water Have Legs Class

human yes no no no yes mammalspython no yes no no no reptilessalmon no yes no yes no fisheswhale yes no no yes no mammalsfrog no yes no sometimes yes amphibianskomodo no yes no no yes reptilesbat yes no yes no yes mammalspigeon no yes yes no yes birdscat yes no no no yes mammalsleopard shark yes no no yes no fishesturtle no yes no sometimes yes reptilespenguin no yes no sometimes yes birdsporcupine yes no no no yes mammalseel no yes no yes no fishessalamander no yes no sometimes yes amphibiansgila monster no yes no no yes reptilesplatypus no yes no no yes mammalsowl no yes yes no yes birdsdolphin yes no no yes no mammalseagle no yes yes no yes birds

61

121

Entscheidungsbaum

C4.5 Regeln(aus Entscheidungsbaum und anschl. Pruning):

(Give Birth=No) (Can Fly=Yes) Birds

(Give Birth=No) (Live in Water=Yes) Fishes(Give Birth=Yes) Mammals

(Give Birth=No) (Can Fly=No) (Live in Water=No) Reptiles( ) AmphibiansGive

Birth?

Live InWater?

CanFly?

Mammals

Fishes Amphibians

Birds Reptiles

Yes No

Yes

Sometimes

No

Yes No

RIPPER Regeln(dirkekt top down aus Trainings-DOs generiert)(Live in Water=Yes) Fishes(Have Legs=No) Reptiles

(Give Birth=No) (Can Fly=No) (Live In Water=No) Reptiles

(Can Fly=Yes) (Give Birth=No) Birds() Mammals

Ergebnis

122

C4.5 Regeln versus RIPPER Regelnkorrekte - vs. Fehliklassifikationen (über dem Trainings-Set)

ermittelte Klasse Amphibians Fishes Reptiles Birds Mammalstat- Amphibians 0 0 0 0 2säch- Fishes 0 3 0 0 0liche Reptiles 0 0 3 0 1Klasse Birds 0 0 1 2 1

Mammals 0 2 1 0 4

ermittelte Klasse Amphibians Fishes Reptiles Birds Mammalstat- Amphibians 2 0 0 0 0säch- Fishes 0 2 0 0 1liche Reptiles 1 0 3 0 0Klasse Birds 1 0 0 3 0

Mammals 0 0 1 0 6

C4.5 Regeln:

RIPPER Regeln:

62

123

Vorteile regelbasierter Klassifikatoren

bzgl. Ausdruckfähigkeit gleich gut wie Entscheidungsbäume

leicht interpretierbar

leicht zu generieren

können neue DO schnell klassifizieren (geringe Zeitkomplexität)

Performance vergleichbar mit Entscheidungsbäumen

124

2.3 Nearest Neighbour Klassifikation (kNN) „eifrige“ Lerner lernen ein Modell (Entscheidungsbaum, Regel-Set, …), sobald die

Trainings-DO verfügbar sind „faule“ Lerner modellieren die Trainingsdaten erst dann, wenn eine Klassifikations-

Aufgabe ansteht - so auch kNN

Idee Klasse ergibt sich aus den Klassen der nächsten Nachbarn im Trainings Set, z.B.

mehrheitlich vertretene Klasse (ggf. mit der Ähnlichkeit gewichtete) Durchschnitts - Klasse

Ansatz

jedes Trainings-DO repräsentiert einen Punkt im d-dimensionalen Raum (d: Anz. der Attribute)

für jedes neue DO wird eine Ähnlichkeit zu allen Trainings-DO ermittelt

die k ähnlichsten DO des Trainings-DO bestimmen die Klasse des neuen DO

Ähnlichkeitsmaße (siehe Folie 13 ff): Distanzmaße im Euklidischen Raum (Manhattan City Block Distance L1, Euclidian

Distance L2, Supremum L∞) Übereinstimmungsmaße bei binären Attributen (Simple Matching Coefficient, Jaccard

Coefficient) Richtungsmaße im Euklidischen Raum (Kosinus-, Dice-, Tanimoto-, Overlap-Koeffizient) lineare Abhängigkeit zwischen Attribut-Werten 2er DO (Korrelation)

63

125

Beispiel

2 reell- wertige Attribute x1, x2

2 rational – wertige Klassen Klasse = 1 und Klasse = 2 Ähnlichkeitsmaß: Euklidische Distanz (L2 – norm)

x1

neues DO

Trainings-DO

k = 1

k = 5

Klasse = 1

Klasse = 2

1,0

1,6

x2

126

noch ein Beispiel

2 reell- wertige Attribute x1, x2

2 binäre Klassen + und - Ähnlichkeitsmaß: Euklidische Distanz (L2 – norm)

X X X

(a) 1-nearest neighbor (b) 2-nearest neighbor (c) 3-nearest neighbor

64

127

Wie wählt man ein passendes k ?

k zu klein ⇒ anfällig für Overfittingk= 1 könnte z.B. genau einen „Ausreißer“ erwischen, obwohl alle anderen Trainings-DO der Umgebung eine andere Klassenzugehörigkeit haben

k zu groß ⇒ anfällig für Underfitting:

in der Praxis: 2 ≤ k ≤ 6

128

Jedes Element der Menge kNN(x‘) der k nächsten Nachbarn eines zu

klassifizierenden DO z = [x‘, y‘] hat den gleichen Einfluss auf die

Klassenzugehörigkeit y‘

⇒ hohe Sensibilität bzgl. k

⇒ Verringerung dieser Sensibilität durch Wichtung jedes der k Nachbarn ximit seiner inversen quadratischen Distanz zum (der Ähnlichkeit mit dem) zu klassifizierenden DO x‘ und Ermittlung derjenigen Klasse y‘∈ v, welche dabei die höchste Summe aller Gewichte erhält:

falseprop

trueproppropord

yvordxxd

yxkNNyx

iiv

ii

falls ,0

falls ,1)(

mit

)(),'(

1maxarg'

)'( ],[2

65

129

Darstellung der Klassenzuordnung im d-dimensionalen Raum

Voronoi-Diagramm

Beispiel k = 3 drei Klassen: 1,2, 3 Ähnlichkeitsmaß:

Euklidische Distanz (L2 Norm)

einfache Mehrheit entscheidet die Klassen-zugehörigkeit

keine Gewichtung der k ähnlichsten DO

grauer Bereich: keine Mehrheit

130

Darstellung der Klassenverteilung im d-dimensionalen Raum

Voronoi-Diagramm

noch ein Beispiel (gleiche Trainings - DO) k = 3 drei Klassen: 1,2, 3 Ähnlichkeitsmaß:

Euklidische Distanz (L2 Norm)

größte Summe der Klassengewichte entscheidet die Klassen-zugehörigkeit

Gewichtung der kähnlichsten DO mit ihrer inversen quadratischen Distanz

66

131

geg.• Menge von DO I• k-dimensionaler Raum von Attributen, in welchem jedem DO i I ein Punkt

zugeordnet werden kann • Partitionierung von I in disjunkte Objektklassen C = c1 , ... , cn • Trainings Set E I : DO mit bekannter Klassenzugehörigkeit

ges.• wahrscheinlichste Klassenzugehörigkeit für ein neues DO (ohne ein Modell

zu bilden)

2.4 Bayes’sche Klassifikation

Bayes’sche Klassifikation ist auch eine “fauler“ Lerner (wie kNN)

Parallelen zum Case Based Reasoning (CBR)

CBR basiert auf einer Fallbasis, in welcher (a) der “ähnlichste Fall” ermittelt wird und (b) dessen Lösung zur Lösung des neuen Falles adaptiert wird

Hier degeneriert (a) zum “wahrscheinlichsten” Fall und (b) zur Kopie von dessen Lösung

132

Gegeben sei

• eine Menge von DO: Bewohner der Stadt Ilmenau

• ein 3-dimensionaler Raum von Attributen: Abbildung Merkmalsraum

• 4 disjunkte Klassen: Bewohner mit einem täglichen Fernsehkonsum von

(1) weniger als 1 Stunde

(2) >1 – 2 Stunden

(3) >2 – 3 Stunden und

(4) mehr als 3 Stunden

• Trainings Set mit 20 Beispielen: Tabelle Beispielmenge

Gesucht ist

• die wahrscheinlichste Klassenzugehörigkeit eines 25-jährigen berufstätigen Bewohners mit mittlerem Einkommen

Ein Beispiel

Attributsraum:

18-40 >40-60 >60

berufstätigarbeitslos

pensioniertgering

mittel

hoch

Alter

Berufsstand

Einkommen

67

133

Training Set

Al-ter

Einkommen Berufsstand Klasse

22 durchschnittlich berufstätig >1 – 2 h

43 hoch berufstätig >1 – 2 h

45 gering berufstätig >1 – 2 h

76 durchschnittlich pensioniert >3 h

34 gering arbeitslos >1 – 2 h


56 hoch berufstätig >3 h



65 durchschnittlich pensioniert >2 – 3 h

Al-ter

Einkommen Berufsstand Klasse

33 gering arbeitslos >3 h


25 gering arbeitslos 1 h

47 durchschnittlich berufstätig 1 h


63 durchschnittlich pensioniert >3 h

51 hoch berufstätig >1 - 2 h

60 durchschnittlich pensioniert >1 – 2 h



134

BAYES‘sche Formel

BAYES‘sche Formel (hier: logisch interpretiert, Literatur: mengenalgebraisch notiert)

1. Seien A und B Aussagen über das Eintreffen von (nicht unmöglichen) Ereignissen sowie p(A) und p(B) Wahrscheinlichkeiten des Eintreffens mit 0 < p(A),p(B) 1 .

)(

)()|(

Bp

BApBAp

2. Die bedingte Wahrscheinlichkeit von A unter der Bedingung B ist

3. Sei = B1 ... Bn ein sicheres Ereignis, bestehend aus paarweise unvereinbaren

Ereignissen B1, ..., Bn : jiBBpBpBBp ji

n

iin

für 0)( , 1)()...(1

1

4. Für ein zufälliges Ereignis A gilt: )...( 21 nBBBAAA

)|()()()()()()(111

n

iii

n

ii

n

ii BApBpBApBpApApAp5. Lt. 2. ist

Fragt man nach der Wahrscheinlichkeit eines Ereignisses Bi unter der Bedingung, dass A bereits eintrat (Wahrscheinlichkeit a posteriori), ergibt sich

n

iii

iiiiii

BApBp

BApBp

Ap

BApBp

Ap

ABpABp

1

)|()(

)|()(

)(

)|()(

)(

)()|(

68

135

2.4.1 Naïve BAYES Klassifikation

geg.• Beispiele, d.h. DO mit bekannten

Werten für alle Attribute Ai (i=1,..,n)und bekannter KlassenzugehörigkeitBj (j=1,..,k)

ges.• wahrscheinlichste Klasse C B1,...,Bk

für ein neues DO mit bekannten Werten für alle Attribute Ai

C ),...,|(max: 1 njj AABpB

),...,(

)()|,...,(max:

1

1

n

jjnj AAp

BpBAApB

)()|,...,(max: 1 jjnj BpBAApB

)()|(max:1

jji

n

ij BpBApB

lt. BAYES‘sche Formel

Vernachlässigung der Division wegengleichen Nenners

Unterstellung der Unabhängigkeit der Attribute, so dass deren UND-Verknüpfung die Wahrscheinlichkeiten multipliziert

136

Klassen• B1: 1 h tgl. TV Konsum

• B2: >1-2 h tgl. TV Konsum

• B3: >2-3 h tgl. TV Konsum

• B4: > 3 h tgl. TV Konsum

Attribute• Alter 18-40 , >40-60 , >60

• Einkommen gering , durchschnittlich , hoch

• Berufsstand berufstätig , pensioniert , arbeitslos

zurück zum Beispiel

Beipiele siehe Folie 133

Wahrscheinlichkeiten, geschätzt als relative Häufigkeit im Trainings Set

ges.: wahrscheinlichste Klassenzugehörigkeit eines Bewohners mit den Attributwerten

A1: Alter = 25 A2: Einkommen = durchschnittlich A3: Berufsstand = berufstätig

Zeilenprodukt

P(A1|B1): 1/2 P(A2|B1): 1/2 P(A3|B1): 1/2 P(B1): 2/20 0,01250

P(A1|B2): 5/9 P(A2|B2): 3/9 P(A3|B2): 6/9 P(B2): 9/20 0,05556

P(A1|B3): 3/5 P(A2|B3): 3/5 P(A3|B3): 3/5 P(B3): 5/20 0,05400

P(A1|B4): 1/4 P(A2|B4): 2/4 P(A3|B4): 1/4 P(B4): 4/20 0,00625

Maximum aller Produkte 0,05556 (aus B2)

Der Bewohner gehört am wahrscheinlichsten zur Klasse B2 (>1-2 h tgl. TV Konsum).

69

137

Verfeinerung für zu kleine Trainings-Sets:m-estimate Schätzung der Wahrscheinlichkeiten statt relative Häufigkeit

geschätzte Wahrscheinlichkeit, zur Klasse Bi zu gehören, für welche es ni (von n) DO im Trainings Set gibt, wird um eine gewichtete a priori (z.B. aus

vorherigen Beobachtungen/Messreihen) geschätzte Wahrscheinlichkeit p’ergänzt

Als Wichtung dient eine sog. “equivalent sample size” m Im Extremfall eines leeren Trainings Sets, ni = 0 and n = 0 und somit p = p’

n

np i

mn

pmnp i

'

• ni Anzahl der DO, die zur Klasse i gehören• n Gesamtzahl der DO• m equivalent sample size, Wichtung von p’• p’ a priori (z.B. von vorherigen Beobachtungen) geschätzte Wahrscheinlichkeit

- könnte notfalls auch als Gleichverteilung aller Klassen geschätzt werden

138

Problem mit Naïve Bayes: korrelierende AttributeBetrachten wir ein 2-Klassen Problem (+ und -) mit 2 binären Attributen A und B mit p(A=0|-) = 0.4 , p(A=1|-) = 0.6 p(A=0|+) = 0.6 , p(A=1|+) = 0.4 Möge B in der Klasse - perfekt mit A korrelieren (B=A), aber in der Klasse + immer

entgegengesetzt zu A sein Der Einfachheit halber gelte

p(+) = p(-) B hat die selben bedingten Wahrscheinlichkeiten wie A (siehe oben):

p(B=0|-) = 0.4 , p(B=1|-) = 0.6, p(B=0|+) = 0.6 , p(B=1|+) = 0.4

Im naïve Bayes Ansatz ist dann p(-|A=0,B=0) = p(A=0|-) p(B=0|-) * p(-) / p(A=0, B=0) = 0.16 * p(-) / p(A=0, B=0) p(+|A=0,B=0) = p(A=0|+) p(B=0|+) * p(+) / p(A=0, B=0) = 0.36 * p(+) / p(A=0, B=0)und + würde als die wahrscheinlichste Klassenzugehörigkeit ermittelt werden.

Die Wirklichkeit sieht jedoch anders aus: p(A=0,B=0|-) = p(A=0|-) = 0.4, weil B in Klasse – stets den gleichen Wert wie A hatDemnach ist p(-|A=0,B=0) = p(A=0,B=0|-) p(-) / p(A=0,B=0)= 0.4* p(-) / p(A=0, B=0)(und nicht 0.16 wie im naïve Bayes kalkuliert) und – ist die wahrscheinlichste Klasse

Lösung dieses Problems:Analyse der Abhängigkeiten zwischen Attributen Bayesian Belief Networks

70

139

2.4.2 Bayesian Belief Network (BBN)

= gerichteter Graph

Knoten repräsentieren Attribute A1, A2, ..., An

Kante von Ai nach Aj bedeutet (Aj ist abhängig von Ai)

Knoten sind Wahrscheinlichkeitstabellen zugeordnet:

• Knoten ohne Vorgänger: a priori Wahrscheinlichkeiten für die verschiedenen Ausprägungen des Attributs

• Knoten mit Vorgänger: bedingte Wahrscheinlichkeiten

- Bedingungen beziehen sich auf die verschiedenen Werte der Attribute der Vorgänger-Knoten

• binäre Attribute

- Tabelle enthält meist nur (bedingte) Wahrscheinlichkeit p(x) für eine der beiden Werte x, die Wahrscheinlichkeit für den Alternativwert ergibt sich aus )(1)( xpxp

140

‘n Beispiel (alle Attribute binär)

Blut-druck

DiätSport

Herz-krankheit

Brust-schmerz

Sod-brennen

RR=high

Hk=yes 0.85

Hk=no 0.2

Bs=yes

Hk=yesSb=yes

0.8

HK=yesSb=no

0.6

HK=noSb=yes

0.4

HK=noSb=no

0.1

Sb=high

D=healthy 0.2

D=unhealthy 0.85

Hk=yes

S=yesD=healthy

0.25

S=yesD=unhealthy

0.45

S=noD=healthy

0.55

S=noD=unhealthy

0.75

D=healthy0.25

S=yes0.7

Beispielep(S=no) = 0.3

p(Sb=high|D=healthy) = 0.2

p(Sb=low|D=unhaelthy) = 0.15

p(Hk=yes|(S=no)(D=healthy)) = 0.55

p(Bs=no|(Hk=yes)(Sb=no)) = 0.4

71

141

‘n Algorithmus zur Konstruktion eines BBN

A := [X1, X2, …, Xn] sei eine (anwendungs-spezfisch) sortierte Liste v. Attributenfor i=1 to n do

XA(i) sei das i-te Attribut in A(XA(i)) = XA(1) , XA(2) , …, XA(i-1) sei die Menge der XA(i) vorangestellten Attributeentferne Attribute aus (XA(i)), die (in der Anwendung) keinen Einfluss auf Ai habenfüge je eine Kante von den verbleibenden Variablen in (XA(i)) zu XA(i) hinzu

end (for)

Sortiert man für‘s o.g. Beispiel im Schritt 1 die Attribute zu [S, D, Hk, Sb, Bs, RR] , so vereinfacht sich in der for - Schleife p(D | S) zu p(D) p(Hk | S D) nicht p(Sb | Hk SD) zu p(Sb | D) p(Bs | SbHkSD) zu p(Bs | SbHk) p(RR | BsSbHkSD) zu p(RR | Hk)

142

2.5 Support Vector Machines

ZielFinden einer Hyperebene, welche DO verschiedener Klassen voneinander separiertBeispiel: 2 Klassen, 2 Attribute

72

143

eine Lösung noch eine Lösung weitere Lösungen

Welche dieser beiden Lösungen ist besser, B1 oder B2?

144

Eine Hyperebene (Klassengrenze), welche den Abstand zum nächstgelegenen DO in jeder der beiden Klassen maximiert, ist optimal.

B1 ist besser als B2

73

145

0 bxw

1 bxw 1 bxw

1bxw if1

1bxw if1)(

xf

2

21

2 Abstand

2||||

2)(

||w||d

dw

xxw

Lineare SVM, DO linear separierbar

Beispiel 2 Klassen: -1 (Quadrate), +1 (Kreise), n Attribute Beschreibung der Klassengrenze im Rn

Funktion, welche dieKlasse f(x) für ein DOx berechnet:

146

zu maximieren:

äquivalent zur Minimierung von

unter den Randbedingungen:

= Optimierungsproblem (quadratische Optimierung)

2||||

2 Abstand

w

1bxw if1

1bxw if1)(

i

i

ixf

2

||||)(

2wwL

74

147

Was kann man tun, wenn die DO nicht linear separierbar sind?

Man bindet so genannte Slack-Variablen ξ in die Optimierung ein

ξ ist der maximaler Abstand eines falsch klassifizierten DO

= Abschätzung des Fehlers der Hyperebene über den Trainingsdaten

zu minimieren:

N

iiC

wwL

1

2

2

||||)(

unter den Randbedingungen

ii

ii

1bxw if1

-1bxw if1)(

ixf

C ist anwendungs-spezifisch:Maß der Bestrafung von Fehlklassifikationen über den Trainingsdaten

148

Was kann man tun, wenn die Hyperebene nicht linear ist?

Man wendet eine nicht lineare Variablen - Transformation Φan, durch welche die Hyperebene linear wird

)2,2,2,,(),(: 212122

2121 xxxxxxxx

ergibt sich im transformierten 5-dimensionalen Raum ein Linearkoeffizient w=[w0 ,w1 ,w2 ,w3 ,w4 ,w5 ] so dass

0222 02112213224

215 wxxwxwxwxwxw

transformiert man z.B. einen 2-dimensionalen Raum in einen 5-dimensionalen Raum mit

75

149

( )

( )

( )( )( )

( )

( )( )

(.) ( )

( )

( )

( )( )

( )

( )

( )( )

( )

transformierter Raumtatsächlicher Raum

Variablen - Transformationzwecks Linearisierung der trennenden Hyperebenen

150

‘n Beispiel zur „Ebnung“ einer Hyperebene

Rxccc

cx

ccc

c

cccxcxc

cccxxcxxc

cxxcxxc

Rcxcxc t

im Ellipse 1)2

1(

41

41

)2

1(

41

41

4

1

4

1)

2

1()

2

1(

4

1

4

1)

4

1()

4

1(

0)()(

im Gerade 0

21

210

122

210

2

2102

112

22

21012112

222

012112

222

01122

Die Ellipse in R hat demnach den Mittelpunkt (-0.5,-0.5) und die Achsen in x1 – und x2– Richtung haben die Durchmesser

2

210

21

210

141

41

2 41

41

2c

cccd

c

cccd

Die TransformationΦ: (x1 , x2 ) → ( x1´, x2´) mit x1´ =x1

2-x1 und x2´= x22-x2

macht aus elliptisch (quadratisch beschreibbaren) verlaufenden Klassengrenzen im Raum R linear beschreibbare Klassengrenzen im transformierten Raum Rt

76

151

n‘ Beispiel zur „Ebnung einer Ellipse“ durch Variablen - Transformationaus Tan/Steinbach/Kumar: Introduction to Data Mining. Pearson Education Inc.

152

2.6 Ensemble MethodenIdee mehrere Modelle über dem Trainings Set bilden deren Ergebnissen zu einem Klassifikationsergebnis kombinieren

D

D1 D2 Dt-1 Dt

C1 C2 Ct-1 Ct

C*

neues DO

originaleTrainingsdaten Schritt 1

mehrereDatensätzeerzeugen

Schritt 2mehrereModelleerzeugen

Schritt 3Ergebnisseeinholen und kombinieren

77

153

Vorteilbessere Performance als jedes einzelne Modell

Beispiel man bilde 25 binäre Klassifikatoren C1, ..., C25

jedes dieser Modelle habe eine (relativ hohe) Fehler-Rate von e( Ci )=0.35 C* ermittelt die Mehrheit der Entscheidungen maximal 12 Modelle haben eine andere Klasse ermittelt

Die max. Fehler-Rate von C* ist dann 35.0 06.0))(1()(25

*)( 2525

13

i

ii

ii

CeCei

Ce

Verhältnis zwischen den Fehler-Raten e(Ci ) und e(C*)bei verschiedenen e(Ci ) „Ensembeln“

lohnt

154

Generierung der Trainingsdaten Di für die Modelle Ci

Bagging = „Bootstrap aggegation“, d.h. zufälliges Ziehen mit Zurücklegen

kann für die Di parallel durchgeführt werden

jedes DO kann mit einer Wahrscheinlichkeit von (1-1/n)n gezogen werden

BoostingIdee: vorrangig solche DO als Trainings-DO nehmen, welche schwer zu klassifizieren sind wichtet die Trainings-DO und zieht vorzugsweise solche DO mit hoher Wichtung;

initial sind alle DO gleich gewichtet arbeitet sequentiell, nach jeder Runde wird neu gewichtet und das nächste Trainings-

Set Di generiert Gewichte für korrekt klassifizierte DO werden verringert; Gewichte für falsch

klassifizierte DO erhöht

nach der letzen Boosting Runde wird C* ermittelt; diverse Methoden der Ermittlung von C* : Mehrheit gewichtete Mehrheit, Wichtung nach ...

dem Gewicht der am Modell Ci beteiligten DO Sequenz (zuletzt kreierte Modelle sind u.U. besser, weil sie sich zielgerichtet

den Schwächen vorheriger Runden zuwenden)

Performance der Modelle Ci über dem Test-Datensatz

78

155

2.7 Das Class Imbalance ProblemAnwendungen mit sehr unbalancierten Klassenzugeörigkeiten:

Qualitätskontrolle: defekte vs. intakte Produkte

Kreditkarten Transaktionen: Betrug vs. rechtmäßige Transaktionen

HIV-Test: positiv vs. negativ

…

korrekte Klassifikation der seltenen Klasse ist wichtiger als bei der häufigen Klasse

ein Klassifikator, welcher z.B. einfach alle DO der häufigen Klasse zuordnet, hätte eine u.U. eine sehr hohe Genauigkeit (Accuracy)

Performance-Metriken müssen das berücksichtigen alternative Metriken (2.7.1)

graphische Methoden für das trade-off zwischen den Korrektheitsraten beider Klassen (2.7.2)

die seltene Klasse wird meist sehr spezialisiert beschrieben

lange Regeln mit vielen Prämissen, große Tiefe in einem Entscheidungsbaum, …

diese spezialisierte Modellierung ist anfällig gegenüber verrauschten Trainingsdaten

Erkennung der seltenen Klasse muss verbessert werden Cost-Sensitive Learning (2.7.3)

Sampling – basierte Ansätze (2.7.4)

156

2.7.1 Alternative Metriken

Termini für binäre Klassifikation: seltene Klasse: positive Klasse (+) häufige Klasse: negative Klasse (-) Anzahl korrekt klassifizierter positiver DO: true positive (TP) f+ +

Anzahl der als negativ klassifizierten positiven DO: false negative (FN) f+ -

Anzahl der als negativ klassifizierten positiven DO: false positive (FP) f- +

Anzahl korrekt klassifizierter negativer DO: true negative (TN) f- - Konfusionsmatrix: Klassifizierung durch das Modell

+ -tatsäch-liche Klasse

+ f+ + (TP) f+ - (FN)

- f- + (FP) f- - (TN)

mitunter auch als relative Werte angegeben:

Anteil korrekt klassifizierter pos. DO: true positive rate (TPR), sensitivity: TPR = TP / (TP+FN)

Anteil der als neg. klassifizierten pos. DO: false negative rate (FNR): FNR = FN / (TP+FN)

Anteil der als pos. klassifizierten neg. DO: false positive rate (FPR):FPR = FP / (TN+FP)

Anteil korrekt klassifizierter neg. DO: true negative rate (TNR), specificity: TNR = TN / (TN+FP)

79

157


Metriken

Precision Anteil der wirklich pos. DO an den als pos. klassifizierten DO

p = TP / (TP + FP)

Recall Anteil der als pos. klassifizierten DO an den wirklich pos. DO (= TPR)

r = TP / (TP + FN)

wünschenswert: hohe Precision + hohes Recall

Recall erscheint auf den ersten Blick für viele Anwendungen wichtiger, aber ...

... der „Preis“ dafür ist eine geringe Precision (hohe Anzahl „falscher Alarme“)

Kompromiss: F1 – Metrik

entspr. harmon. Mittelwert zw. r und p: μh = 2 / (1/r + 1/p)

≤ geometrisches Mittel μg=√rp ≤ arithmet. Mittel μa =(r+p)/2 tendenziell näher am kleineren der beiden Werte r oder p als μg und μa

FNFPTP

TP

pr

rp

pr

F

2

2211

21

158


Kompromiss, abstrakter: Fβ – Metrik

β=0 → Precisionβ=1 → harmon. Mittel, F1 - Metrikβ=∞ → Recall

FNFPTP

TP

pr

rpF

22

2

2

2

)1(

)1()1(

Kompromiss, noch abstrakter: weighted accuracy WA

TNwFMwFPwTPw

TNwTPwWA

4321

41

Gewicht w1 w2 w3 w4

Recall 1 1 0 0

Precision 1 0 1 0

Fβ β2 + 1 β2 1 0

F1 2 1 1 0

Accuracy 1 1 1 1

80

159

2.7.2 Receiver Operating Characteristic (ROC) Kurvegraph. Veranschaulichung des „trade – off“ zwischen FPR (x-Achse) und TPR (y-Achse)Extremwerte: FPR = 0, TPR = 0: das Modell ordnet jedem DO die negative Klasse (-) zu FPR = 1, TPR = 1: das Modell ordnet jedem DO die positive Klasse (+) zu FPR = 0, TPR = 1: ideales Modell TPR = FPR (Diagonale in graph. Darstellung): zufälliges Zuordnung einer Klasse

… mit einer festen Wahrscheinlichkeit p, bei n+ pos. und n- neg. DO:

FPRTPR

pn

npFPR

pn

npTPR

‘n Beispiel:

je weiter links (nahe FPR=0) und

je weiter oben (nahe TPR=1)

die Kurve liegt,desto besser istdas Modell

für FPR ≤ 0,36: M1 ist besser als M2

für FPR > 0,36: M2 ist besser als M1

Fläche unter-halb der ROC-Kurve ist einMaß der durch-schnittlichenPerformanceeines Modells

160

2.7.2 Receiver Operating Characteristic (ROC) Kurve

Man braucht ein reell-wertiges „Ranking“ der Wahrscheinlichkeiten, als pos. DO klassifiziert zu werden, welches man z.B. durch einen anderen Data Mining Klassifikator (z.B. Bayes) oder durch Anwendung des Modells auf Testdaten ermitteln kann.

Wie zeichne ich eine ROC Kurve?

1. Sortiere die DO nach aufsteigender Wahrscheinlichkeit.

2. Unterstelle pos. Klassifizierung aller DO: a) Zähle die dabei richtig klassifizierten DO (= TP) und die dabei falsch

klassifizierten DO (= FP)b) Setze TN:=0 und FN:=0 sowie TPR=TP/(TP+FN):=1 und FPR=FP/(FP+TN):=1c) Zeichne den Punkt [ FPR=1 , TPR=1 ] in das ROC Diagramm ein

3. Betrachte das nächst wahrscheinlicher als pos. klassifizierte DO und alle noch wahrscheinlicheren:a) Zähle die darunter richtig (TP) und falsch (FP) klassifizierten DOb) Inkrementiere FN (falls es ein pos. DO ggü. der vorherigen Spalte ein DO

weniger wurde) oder TN (falls es ein neg. DO weniger wurde)c) Ermittle TPR=TP/(TP+FN) und FPR=FP/(FP+TN) entsprechend der aktuellen

Werte von TP, FP, FN und TNd) Zeichne den ermittelten Punkt [FPR,TPR] in das ROC Diagramm ein

4. Wiederhole 3. bis zum am wahrscheinlichsten als pos. klassifizierten DO

5. Ergänze den Punkt [0,0] im ROC Diagramm

81

161

geg.: 10 DO (5 pos., 5 neg.) mit folgenden Wahrscheinlichkeiten einer pos. Klassifikation:

+ - + - - - + - + +

0.25 0.43 0.53 0.65 0.71 0,77 0,82 0.85 0.91 0.95

1. Spalte: TP:=5 FP:=5 TN:=0 FN:=0 TPR=TP/(TP+FN):=1 FPR=FP/(FP+TN):=1

Klasse + - + - - - + - + +

0.25 0.43 0.53 0.65 0.71 0,77 0,82 0.85 0.91 0.95

TP 5

FP 5

TN 0

FN 0

TPR 1

FPR 1

2. Spalte: TP:=4 FP:=5 TN:=0 FN:=1 TPR=TP/(TP+FN):=0.8 FPR=FP/(FP+TN):=1

Klasse + - + - - - + - + +

0.25 0.43 0.53 0.65 0.71 0,77 0,82 0.85 0.91 0.95

TP 5 4

FP 5 5

TN 0 0

FN 0 1

TPR 1 0.8

FPR 1 1

3. Spalte: TP:=4 FP:=4 TN:=1 FN:=1 TPR=TP/(TP+FN):=0.8 FPR=FP/(FP+TN):=0.8

Klasse + - + - - - + - + +

0.25 0.43 0.53 0.65 0.71 0,77 0,82 0.85 0.91 0.95

TP 5 4

FP 5 4

TN 0 1

FN 0 1

TPR 1 0.8

FPR 1 0.8

Klasse + - + - - - + - + +

0.25 0.43 0.53 0.65 0.71 0,77 0,82 0.85 0.91 0.95

TP 5 3 3 3 3 2 2 1 0

FP 5 4 3 2 1 1 0 0 0

TN 0 1 2 3 4 4 5 5 5

FN 0 2 2 2 2 3 3 4 5

TPR 1 0.6 0.6 0.6 0.6 0.4 0.4 0.2 0

FPR 1 0.8 0.6 0.4 0.2 0.2 0 0 0

… restliche Spalten und [0,0] - Punkt

2.7.2 Receiver Operating Characteristic (ROC) Kurve ‘n Beispiel:

162

2.7.2 Receiver Operating Characteristic (ROC) Kurve ‘n Beispiel:

0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

FPR

TPR

82

163

2.7.3 Cost-Sensitive Learning

Klassifizierung durch das Modell


+ C(+,+) C(+,-)

- C(-,+) C(-,-)

Idee: Quantifizierung des Schadens C(i,j) für eine Fehlklassifizierung eines DO der Klasse i als ein DO der

Klasse j bzw. im binären Fall C(+,-) der Fehlklassifizierungen f+- (FN) und C (-,+) der Fehrklasifizierungen f- + (FP)

des Nutzens C(i,i) einer korrekten Klassifizierung eines DO der Klasse i bzw. im binären Fall C(+,+) der korrekten Klassifizierungen f++ (TP) und C(-,-) der korrekten Klassifizierungen f- - (TN)

einer Kostenmatrix:

positive Werte beziffern einen Schaden (Malus) negative Werte beziffern einen Nutzen (Bonus)Bei n DO belaufen sich die Gesamtkosten Ct(M) eines Modells (Klassifikators) M auf

),(),(),(),()( CfCfCfCfMCtIn einer 0/1 Kostenmatrix ist C(+,+) = C(-,-) = 0 („kostet nichts“) C(+,-) = C(-,+) = 1 („kostet etwas“)und Ct(M) ist die Anzahl der Fehlklassifikationen des Modells M.

164

2.7.3 Cost-Sensitive Learning



+ -1 100

- 1 0

‘n Beispiel: Kostenmatrix einer Anwendung

Konfusionsmatrizen 2er Modelle:

39100250100401601150)( 1 MCt

Model M1



+ 150 40

- 60 250

Model M2



+ 250 45

- 5 200

4255020010045151250)( 2 MCt

Obwohl M2 sehr viel mehr DO richtig klassifiziert als M1, schneidet es bei den Gesamtkosten schlechter ab als M1 , weil die „Bestrafung“ für die Fehlklassifizierung C(+,-) sehr viel höher ist als die

Bestrafung für die Fehlklassifizierung C(-,+) und dies die marginale „Belohung“ für das bessere f++ nicht zu kompensieren vermag.

83

165

2.7.3 Cost-Sensitive LearningAnwendung bei der Modellbildung: statt hohe Häufigkeiten von Klassenzugehörigkeiten (hohe Klassenreinheit) werden geringe mit Kosten gewichtete Häufigkeiten verwendet

1. bei der Auswahl eines geeigneten Splitting – Attributs2. beim Pruning3. bei der Klassenzuordnung an Blättern eines Entscheidungsbaumes oder DANN-

Teilen von Entscheidungsregeln: statt Maxima von Wahrscheinlichkeiten

p(+) > 0.5 → + p(+) ≤ 0,5 → –

nimmt man Minima der kosten-gewichteten Wahrscheinlichkeiten

p(+)*C(+,-) + p(-)*C(-,-) > p(+)*C(+,+) + p(-)*C(-,+) → + , ansonsten –

Für C(+,+) = C(-,-) = 0 wird demnach die Klasse + zugeordnet, falls:

p(+)*C(+,-) > p(-)*C(-,+)p(+)*C(+,-) > (1 - p(+))*C(-,+)p(+)*C(+,-) > C(-,+) - p(+)*C(-,+)p(+)*C(+,-) + p(+)*C(-,+) > C(-,+)p(+)*(C(+,-) + C(-,+)) > C(-,+)p(+) > C(-,+) / (C(+,-) + C(-,+))

und anderenfalls die Klasse –

166

2.7.4 Sampling-basiete Ansätze

Idee: die „rare Klasse“ soll im Trainingsdatensatz nicht „rar“ seinBeispiel: Datensatz mit 100 pos. und 1000 neg. DO

Trainingsdatensatz bei

1. Undersampling: alle (100) pos. und nur ein kleiner Teil (z.B. 100) der neg. DO Nachteil: nützliche neg. DO werden u.U. nicht zur Modellbildung genommen Methoden zur Milderung dieses Nachteils:

mehrfach undersamplen und Ensemble-Methode auf die entstandenen Modelle anwenden

„focused“ undersampling: „informierte“ Auswahl der neg. DO (z.B. nach Abstand zur „Grenze“ zwischen + und - , wenn falls solche Information habhaft ist)

2. Oversampling: pos. DO mehrfach (hier 10-fach) verwenden, so dass deren Anzahl der Anzahl der neg. DO gleich wird bringt zwar keine neue Information in den Datensatz, aber verhindert ein Pruning von

Teilen des Modells, welche nur wenige Trainings-DO abdecken Vorteil: auch „einsame“ pos. DO (umringt von neg. DO) werden mitmodelliert. Nachteil: Model Overfitting, falls verrauschte Daten mehrfach dupliziert werden

3. hybriden Ansätzen: Kombination des undersamplens der mehrheitlichen Klasse und oversamplen der raren Klasse

84

167

2.8 Mehrklassen-Problem

die meisten o.g. Techniken machen binäre Klassifikation und müssen erweitert werden, wenn es eine Menge Y = y1 , …, yk von mehr als zwei Klassen gibt

1. one-against-rest (1-r) Ansatz k binäre Klassifikatoren (i-te Klasse vs. andere Klassen) bilden

2. one-against-one (1-1) Ansatz für jedes Paar von Klassen [yi, yj] einen binären Klassifikator erzeugen (k*(k-1) / 2 Stück)

dabei DO, die weder zu yi noch zu yj gehören, bei der Modellbildung ignorieren

Alle gebildeten Modelle werden benutzt. (1-r) Ansatz: wenn das für yi konstruierte Modell ein DO als pos. einstuft und alle

anderen Modelle dieses DO als neg. einstufen, wird es der Klasse i zugeordnet (1-1) Ansatz:

jedes Modell, welches für eine binäre [yi, yj] – Entscheidung gebildet wurde, liefert ein Votum entweder für yi oder für yj

Voten für jede Klasse werden addiert und eine Mehrheitsentscheidung getroffen

Beide Ansätze [(1-r) mehr noch als (1-1)] bergen die Gefahr, dass es keine klare Zuordnung gibt.Dies kann man durch zusätzliche Informationen (Zugehörigkeitswahrscheinlichkeiten u.ä.) lösen …

… oder durch Error-Correcting Output Coding entschärfen

168

Error-Correcting Output Coding

k Klassen werden mit n > k Bits derart kodiert, dass die Hamming-Distanzen (Anzahl der verschiedenartigen Bits) zwischen jedem Paar von Klassen möglichst groß sind

für jedes Bit wird ein Modell gebildet als Klassifikationsergebnis wird diejenige Klasse zugeornet, welche die geringste

Hamming-Distanz zum bitweisen Klassifikationsregebnis hat

Beispiel: Y = y1, y2, y3, y4

Klasse Code

y1 1 1 1 1 1 1 1

y2 0 0 0 0 1 1 1

y3 0 0 1 1 0 0 1

y4 0 1 0 1 0 1 0

die sieben Modelle brachten das Ergebnis [0,1,1,1,1,1,1]

die Hamming-Distanz zu y1 ist 1

y2 ist 3

y3 ist 3

y4 ist 3

y1 ist demnach die wahrscheinlichste Klasse

Wenn die Minimum Hamming-Distanz zwischen jedem Paar von Codes d ist, kann diese Methode (d-1)/2 fehlerhafte Klassenzuordnungen bei den n Bits tolerieren

Beispiel oben: min. Hamming-Distanz zwischen 2 Codes ist 4

3/2 = 1 , d.h. bis zu eine Fehrklassifizierung unter den 7 Klassifikatoren kann toleriert werden

85

169

3 Assoziations-AnalyseZiel: Assoziationen innerhalb einer Menge von Objekten analysierengegeben

Transaktionen (= Menge von Objekten, Itemsets)

gesucht

Assoziations-Regeln (Objekte, die typischerweise gemeinsam in Itemsets sind)

Beispiel

Transaktion ID Itemset

1 Brot, Milch

2 Brot, Windeln, Bier, Eier

3 Milch, Windeln, Bier, Cola

4 Brot, Milch, Windeln, Bier

5 Brot, Milch, Windeln, Cola

Assoziations - Regeln

Windeln Bier,Milch, Brot Eier, Cola,Bier, Brot Milch

Anwendungen

Warenkorbanalyse

Klassifikation

Clustering

Cross Marketing

Bioinformatik

medizinische Diagnose

Web Mining (Suchmaschinen)

Analyse wissenschaftlicher Daten (z.B. Klimaforschung)

170

Repräsentation von Transaktionen

als DO mit binären Variablen (asymmetrisch, d.h. Werte 0 sind von Interesse) TID Brot Milch Windeln Bier Eier Cola

1 1 1 0 0 0 0

2 1 0 1 1 1 0

3 0 1 1 1 0 1

4 1 1 1 1 0 0

5 1 1 1 0 0 1

Menge aller Items: I = i1 , i2 , ..., id

Menge aller Transaktionen: T = t1 , t2 , ..., tn mit ti 2I

Itemset: Menge von Items aus I: X 2I

k – Itemset: Menge von Items aus I mit k Elementen: X 2I , |X|=k

Eine Transaktion tj enthält ein Itemset X, gdw. X tj

Support count σ(X) : Anzahl von Transaktionen, welche X enthalten:

σ(X) = |ti : ti T , X ti |

Support s(X): Anteil von Transaktionen ti T, welche X enthalten: s(X) = σ(X) / |T|

Assoziationsregel X → Y : Implikation mit Itemsets X und Y, X Y =

86

171

Metriken zur Evaluierung von Assoziations-Regeln

Support s( X → Y )

Anteil von Transaktionen, welche ( X Y ) enthalten:s( X → Y ) = | ti : ti T , ( X Y ) ti | / | T | = σ( X Y ) / n

Confidence c( X → Y )

Anteil von Transaktionen, die (auch) Y enthalten an denen, die X enthalten= bedingte Wahrscheinlichkeit von Y unter der Bedingung Xc( X → Y ) = σ( X Y ) / σ(X)

häufiges Itemset X

Itemset, dessen Support einen Mindestwert minsup aufweist: s(X) MinSup

Beispiel r: Milch, Windeln → Bier

TID Brot Milch Windeln Bier Eier Cola

1 1 1 0 0 0 0

2 1 0 1 1 1 0

3 0 1 1 1 0 1

4 1 1 1 1 0 0

5 1 1 1 0 0 13

2)(

5

2)(

rc

rs

172

Wie kann man das Ziel des Data Mining über Transaktionen formal definieren?

Über einer gegebenen Menge T von Transaktionen suchen wir Assoziations – Regeln X→Y mit

einem Support s(X→Y ) MinSup und

einer Confidence c(X→Y ) MinConf

Problem: kombinatorische ExplosionÜber d Items kann man

verschiedene Regeln bilden.Für d=6 (siehe Beispiel auf vorheriger Seite) sind das bereits 602 Regeln.Fordert man MinSup = 0.2 und MinConf = 0.5 , bleiben davon nur ca. 120 Regeln.

Regel-Pruning vor der Berechnung der Confidence-Werte sinnvoll!

123 1

11

dd

kd

i

d

k i

kd

k

d

87

173

Assoziations-Regel - Mining

2 Schritte:

1. Ermittlung häufiger Item-Sets

= solche, die einen Mindest-Support minsup aufweisen

2. Generierung „starker“ Regeln aus den häufigen Item-Sets

= solche „Verteilungen“ der Items auf Prämisse und Konklusion, für welche eine hoher Confidence – Wert entsteht

3.1 Ermittlung häufiger Item – Sets

Die Halbordnung definiert einen Verband über der Menge M := X: X I = 2I

aller Itemsets aus I

Beispiel:I = a, b, c

a, b, c

a, b a, c b, c

c b a

Jedes dieser 2|I| Kandidat-Itemset gegen jede Transaktiont T (die längsten Transaktion habe w Items) bzgl. Support zu vergleichen kostet

o( |T| (2|I| -1) w )

Vergleiche!

untauglich!

174

Reduzierung der Komplexität bei der Generierung häufiger Itemsets

1. Effiziente Generierung von Kandidat - Itemsets

Anwendung des „a priori“ Prinzips

2. Effiziente Repräsentation der Kandidat - Itemsets

kompaktere Repräsentation der Kandidaten-Sets als Hash-Baum

3. Effizientes Vergleichen der Kandidaten mit den Transaktionen

effiziente Traversierung des Hash-Baumes

3.1.1 Effektive Erzeugung von Itemsets, a priori Prinzip

A Priori Prinzip

Wenn ein Itemset häufig (selten) ist, dann sind auch alle seine Teilmengen(Super-Mengen) häufig (selten).

Logisch, denn Teilmengen-Relation und Support-Wert verhält sich anti-monoton, d.h.

XY : ( X Y ) → s( X ) s( Y ) , m.a.W.

die Verkleinerung eines Itemsets kann nur zu einer Erhöhung seines Support-Wertes führen

die Vergrößerung eines Itemsets kann nur zu einer Verringerung seines Support-Wertes führen

88

175

seltenes Itemset

entfernbare Super-Mengen

AB AC AD AE BC BD BE CD CE DE

A B C D E

ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE

ABCD ABCE ABDE ACDE BCDE

ABCDE

A priori – Prinzip

unterschreitet ein Itemset minsup, kann eine

Untersuchung aller seiner Super-Sets unterbleiben

176

A priori – Algorithmus

k := 1

Fk := i: i I, σ(i)/N minsup ; alle 1-elementigen Sets mit support minsup

repeat

k:= k+1

Ck:=apriori_gen(Fk-1) ; bilde alle k-elementigen Kandidaten aus den (k-1) elementigen

for each transaction t T do

Ct:=subset(Ck,t) ; filtere Kandidaten, die t sind (in Transaktionen vorkommen)

for each c Ct do ; ermittle den Support count jedes Kandidaten

σ(c) := σ(c) + 1 for each time c t was foundend (for)

end(for)

Fk:=c: c Ck, σ(c)/N minsup ; filtere Kandidaten mit support minsup

until Fk =

result := ⋃ Fk

89

177

‘n Beispiel minsup = 0.6, d.h. σmin=3 TID Itemset

1 Brot, Milch

2 Brot, Windeln, Bier, Eier

3 Milch, Windeln, Bier, Cola

4 Brot, Milch, Windeln, Bier

5 Brot, Milch, Windeln, Cola

Itemsets F1 σ

Bier 3

Brot 4

Cola 2

Eier 1

Milch 4

Windeln 4

Entfall wegen nicht hinreichendem Support

2-el. Itemsets F2 σ

Bier, Brot 2

Bier, Milch 2

Bier, Windeln 3

Brot, Milch 3

Brot, Windeln 3

Milch, Windeln 3

3-el. Itemsets F3 σ

Brot, Milch, Windeln 2

Ergebnis

6+6+1 = 13 Kandidaten wurden gebildet

ohne Pruning der support-armen Itemsets wären es 6 + 15 + 20 = 41 (für bis zu 3-elementige Itemsets) gewesen

178

Ck:=apriori_gen(Fk-1)Prozedur zur Erzeugung k-elementiger Itemsets durch

1. Generierung einer Menge von Kandidaten-Sets

anhand der (k-1)-elementigen häufigen Itemsets aus der vorherigen Iteration

2. Pruning (Reduzierung) dieser Menge

durch Anwendung der Support-Wert – gestützten Pruning-Strategie

Generierung von Kandidaten - Itemsets

einfache Variante

Zusammenstellen aller Kombinationen von k Items aus dem gesamten Itemset I (|I|=d)

Das sind

k

dKandidaten, von denen jeder mit einem Aufwand von

d

k

k1

beim Pruning auf hinreichendem Support untersucht werden muss.

Gesamtkosten: untauglich)2()( 1

1

d

d

k

dok

dko

90

179

bessere Variante: Fk-1 x F1 Verschmelzung

Kandidaten der vorherigen Iteration werden mit den (initial gebildeten) 1-elementigen häufigen Itemsets verschmolzen.

Komplexität:

liefert auch garantiert alle häufigen k- Itemsets, weil sie aus häufigen (k-1)- Itemsets und häufigen 1-Itemsets entsteht

effizienzsteigernd können Permutationen bereits gebildeter Itemsets vermieden werden, indem

alle Itemsets lexikographisch sortiert werden und

nur Erweiterungen der (k-1)-Itemsets um ein lexiko-graphisch größeres Item aus F1 vorgenommen werden

)||||( 11 k

k FFko viel besser!

2-el. häufige Itemsets F2

Bier, Windeln

Brot, Windeln

Brot, Milch

Milch, Windeln

häufige Itemsets F1

Bier

Brot

Milch

Windeln

3-el. Kandidaten Itemsets C3 F2

Brot, Milch, Windeln

Beispiel

180

in a priori-gen genutzte Variante: Fk-1 x Fk-1 Verschmelzung

2 (sortierte) Itemsets aus Fk-1 werden genau dann verschmolzen, falls die ersten k-2 Items identisch sind

zusätzlicher Pruning-Schritt nach dem Verschmelzen notwendig: Test, ob alle (k-1)- elementigen Untermengen des entstandenen k- Itemsets

auch häufig (m.a.W. Fk-1) sind. liefert auch garantiert alle häufigen k- Itemsets, weil sie aus häufigen (k-1)-

Itemsets und häufigen 1-Itemsets entsteht

F2

Bier, Windeln

Brot, Milch

Brot, Windeln

Milch, Windeln

F2

Bier, Windeln

Brot, Milch

Brot, Windeln

Milch, Windeln

3-el. Itemsets C3


3-el. Itemsets F3


Kandidaten-Generierung

Kandidaten - Pruning:Entfernung derjenigen, bei denen nichtjede 2-elementige Teilmenge F2

91

181

3.1.2 Repräsentation der Kandidaten in einem Hash-Baum

generierte (sortierte) Kandidaten k-Itemsets werden zur effektiven Ermittlung ihres Supports in einen Hash - Baum eingeordnet

benötigt wird

1. eine Hash - Funktion, welche einem Itemset in jedem (nicht Blatt -) Knoten einen Unterbaum zuweist

für Baum des Grades g wäre für die i-te Ebene wäre sinnvoll:

<Ordnungszahl des i-ten Elements im Itemset> mod g

2. eine maximale Anzahl von Itemsets, die in einem Blatt sein dürfen (um die Komplexität des Vergleichens zu begrenzen)

falls diese überschritten wird, werden Unterbäume generiert und die Itemsets gemäß der o.g. Hash - Funktion diesen zugeordnet

182

‘n Beispiel

2 3 45 6 7

1 4 51 3 6

1 2 44 5 7 1 2 5

4 5 81 5 9

3 4 5 3 5 63 5 76 8 9

3 6 73 6 8

1,4,7

2,5,8

3,6,9Hash - Funktion

15 3-Itemsets:

1, 4, 5, 1, 2, 4, 4, 5, 7, 1, 2, 5, 4, 5, 8, 1, 5, 9, 1, 3, 6, 2, 3, 4,

5, 6, 7, 3, 4, 5, 3, 5, 6, 3, 5, 7, 6, 8, 9, 3, 6, 7, 3, 6, 8

Grad des Baumes: g := 3

Hash - Funktion für die i-te Ebene: <Ordnungszahl des i-ten Elements> mod 3

Hash - Baum

92

183

Kandidaten - Hash-Baumlinke Unterbäume bei Hash-Wert 1

1 5 9

1 4 5 1 3 63 4 5 3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 71 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash Funktion Kandidaten – Hash-Baum

Hash mit 1, 4 oder 7

184

1 5 9

1 4 5 1 3 63 4 5 3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 71 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash mit 2, 5 oder 8

Kandidaten - Hash-Baummittlere Unterbäume bei Hash-Wert 2


93

185

1 5 9

1 4 5 1 3 63 4 5 3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 71 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash mit 3, 6 or 9

Kandidaten - Hash-Baumrechte Unterbäume bei Hash-Wert 0


186

3.1.3 Traversierung des Hash - Baumes mit einer Transaktion

Auch k-Untermengen einer (sortierten) Transaktion können in einen Baum eingeordnet werden

zunächst Bildung möglicher k - Subsets Einordnung in einen Unterbaum auf i-ten Ebene entsprechende dem i-ten

Element des k-Itemsets

‘n Beispiel

für die Bildung

aller 3 – Subsets

Transaktion t = 1, 2, 3, 5, 6

k = 3

1 2 3 5 6

Transaktion t

2 3 5 61 3 5 62

5 61 33 5 61 2 61 5 5 62 3 62 5

5 63

123 125 126 135 136 156 235 236 256 356

Ebene 1

Ebene 2

Ebene 3: Blätter enthalten sortierte 3-Itemsets der Transaktion t

63 5

94

187

1 5 9

1 4 5 1 3 63 4 5 3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1 2 3 5 6

1 + 2 3 5 63 5 62 +

5 63 +

1,4,7

2,5,8

3,6,9

Hash-FunktionTransaktion

Matching des Transaktions-Baumes mit dem Hash-Baum der Kandidaten-Itemsets

Mit jedem Blatt des Transaktions-Baumes (s.o.) wird der Hash-Baum traversiert Im Blatt des Hash-Baumes angekommen, wird das k-Itemset aus dem

Transaktions-Baum mit den Kandidaten im Blatt des Hash-Baumes verglichen

188

1 5 9

1 4 5 1 3 63 4 5 3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash-Funktion1 2 3 5 6

3 5 61 2 +

5 61 3 +

61 5 +

3 5 62 +

5 63 +

1 + 2 3 5 6

Transaktion


95

189

1 5 9

1 4 5 1 3 63 4 5 3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash-Funktion1 2 3 5 6

3 5 61 2 +

5 61 3 +

61 5 +

3 5 62 +

5 63 +

1 + 2 3 5 6

Transaktion


1 2 6

1 5 6

1 2 5

1 2 3

190

1 5 9

1 4 5 1 3 63 4 5 3 6 7

3 6 8

3 5 6

3 5 7

6 8 9

2 3 4

5 6 7

1 2 4

4 5 7

1 2 5

4 5 8

1,4,7

2,5,8

3,6,9

Hash-Funktion

1 2 3 5 6

3 5 61 2 +

5 61 3 +

61 5 +

3 5 62 +

5 63 +

1 + 2 3 5 6

Transaktion


1 2 6

1 5 6

1 2 5

1 2 3

nur mit diesen (rot um-randeten) 3-Itemsetsmusste die Transaktion ver-glichen werden, um das Vor-handensein der Itemsets des Hash - Baumes in der Trans-aktion zu ent-scheiden.

96

191

Die Hash-Technik beschränkt die Anzahl der Vergleiche in o.g. Beispiel von 150 (10 3-elementige Itemsets in t=1, 2, 3, 5, 6 mit 15 Kandidaten-Itemsets) auf 16:

1,2,3 wird mit 1 Kandidaten des Hash - Baums verglichen

1,2,5 wird mit 2 Kandidaten des Hash - Baums verglichen und im Baum gefunden









Nach dem Matching bleiben 3 häufige 3-Itemsets F3 aus dieser Transaktion übrig.

Aus jedem der 3 häufigen Itemsets kann man je 23 – 2 Assoziationsregeln bilden:

Es gibt 23 denkbare Partitionierungen in Prämisse und Konklusion einer Regel

→F3 und F3→ sind nicht sinnvoll und werden abgezogen

192

3.2 Effiziente Repräsentation von Itemsets

Anzahl häufiger Itemsets kann in Praxi sehr hoch werden

Idee: nur eine Teil repräsentieren, aus welcher alle häufigen Itemsets ableitbar sind

3.2.1 Maximale häufige Itemsets

Definition

Ein Itemset ist maximal häufig, wenn keiner seiner direkten (um 1 Element reicheren) Super-Sets häufig ist.

Alle häufigen Itemsets kann man aus den maximal häufigen Itemsets generieren, indem man alle Teilmengen der maximal häufigen Itemsets zu selbigen hinzufügt.

97

193


A B C D E



ABCDE

‘n BeispielItemsets aus A, B, C, D, E

häufigeItemsets

nicht häufigeItemsets

AD

ACE

BCDE maximalehäufigeItemsets

194

3.2.1 Maximale häufige Itemsets

Vorteil

außerordentlich kompakte Repräsentation

siehe Beispiel: 3 von 20 Itemsets müssen gespeichert werden

Nachteil

maximale häufige Itemsets enthalten keine Support – Informationen über ihre Teilmengen (außer der, dass dieser größer minsup ist)

benötigt man den Support – Wert der Teilmengen, ist ein zusätzlicher Lauf über die Transaktions-Daten nötig

in einigen Fälle benötigt man eine minimale Darstellung häufiger Itemsets, welche die Support – Information aller häufigen Itemsets enthält

geschlossene häufige Itemsets

98

195

3.2.2 Geschlossene häufige Itemsets

Definition

Ein Itemset X ist geschlossen, wenn keiner seiner direkten (um 1 Element reicheren) Super-Sets einen gleich hohen Support hat.

Für den Support eines Super-Sets X‘ X gilt ohnehin s(X‘) s(X).

Wenn der Support für jedes Super-Set X‘ X schlechter wird, ist X geschlossen.

Gibt es (mind.) ein Superset X‘ X mit s(X‘) = s(X), kann man das

Itemset X auch ohne Support-Verlust noch vergrößern, weshalb es nicht als „geschlossen“ gilt.

Definition

Ein Itemset X ist ein geschlossenes häufiges Itemset, wenn es

geschlossen ist und einen Mindestwert minsup an Support aufweist.

196


A B C D E



ABCDE

‘n Beispiel Itemsets aus A, B, C, D, E , minsup=0.4TID Items

1 ABC

2 ABCD

3 BCE

4 ACDE

5 DE

Support

0.6 0.6 0.8 0.6 0.6

0.4 0.6 0.4 0.2 0.6 0.2 0.2 0.4 0.4 0.4

0.4 0.2 0 0.4 0.2 0.2 0.2 0.2 0 0.2

0.2 0.2 000

0

geschlossenehäufigeItemsets

C D E

AC BC CE DE

ABC ACD

99

197


A B C D E



ABCDE

gleiches Beispiel - maximal häufig vs. geschlossen häufig, minsup=0.4TID Items

1 ABC

2 ABCD

3 BCE

4 ACDE

5 DE0.6 0.6 0.8 0.6 0.6

0.4 0.6 0.4 0.2 0.6 0.2 0.2 0.4 0.4 0.4

0.4 0.2 0 0.4 0.2 0.2 0.2 0.2 0 0.2

0.2 0.2 000

0

geschlossenehäufigeItemsets

C D E

AC BC CE DE

ABC ACD

maximalehäufigeItemsets

CE DE

ABC ACD

nicht häufigeItemsets

198

Vorteil geschlossener häufiger Itemsets

Itemsets sind redundant, wenn sie gleichen Support mit deren Super-Sets haben, z.B. inTID A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 C1 C2 C3 C4 C5 C6 C7 C8 C9 C101 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 02 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 03 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 04 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 05 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 06 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 07 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 08 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 09 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 010 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 011 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 112 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 113 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 114 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 115 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1

für minsup = 0.2 gibt es 3*(210-1) = 3069 häufige Itemsets

Warengruppen A, B und C werden aber stets zusammen gekauft

Teilmengen innerhalb dieser Warengruppen zu analysieren, führt zu redundanten Assoziationsregeln Eine Assoziationsregel XY ist redundant, wenn es bereits eine Regel X‘Y‘ mit

XX‘ und YY‘ gibt. Redundanz meint hier, dass immer, wenn X (bzw. Y) im Warenkorb liegt, ohnehin

auch X‘\X (bzw. Y‘\Y) auch im Warenkorb liegt.

Es gibt nur 3 geschlossene häufige Itemsets: A1, …, A10, B1, …, B10 und C1, …, C10

Mitunter ist es sinnvoll, Analysten nur geschlossene häufige Itemsets zu präsentieren

100

199

3.3 Regelgenerierung

Nach der Support – basierten Ermittlung häufiger Itemsets erfolgt eine Confidence –basierte Extraktion von Regeln aus diesen Itemsets.

Für jedes häufige k - Itemset Fk kann man 2k – 2 Assoziationsregeln X →Fk \ X bilden, welche auf hinreichende Confidence

c( X →Fk \ X ) = σ(Fk ) / σ(X)

überprüft werden.

Theorem

Wenn eine Regel X → Fk \ X nicht die nötige Mindest - Confidence

c = σ(Fk ) / σ(X)

aufweist, dann wird auch jede Regel X' → Fk \ X ' mit X ' X mit ihrer Confidence

c' = σ(Fk ) / σ(X')

diesem Schwellwert nicht erreichen.

… logisch, da σ(X') σ(X) für X ' X .

200


erweist sich eine aus Fk bildbare Regel als inkonfident, ist jede andere aus Fkbildbare Regel mit kürzerer Prämisse (und längerer Konklusion) erst recht inkonfident

die im prämissenbasiert gebildeten Verband „darunter“ liegenden Regeln müssen nicht auf Konfidenz untersucht werden

Beispiel:

abcd→

abc→d abd→c acd→b bcd→a

ab→cd ac→bd ad→bc bc→ad bd→ac cd→ab

a→bcd c→abdb→acd d→abc

c < cmin

Regel-Pruning

101

201


Effektive Generierung von Regeln für ein gegebenes Itemset

Verschmelzung 2er als „konfident“ erwiesener Regeln zu einer (im Verband darunter liegenden) neuen Regel mit einer um 1 Item längeren Konklusion

Redundanzfreie Auswahl von Regelpaaren zur Verschmelzung:

Regeln der Ebene k des Verbandes haben k Items in ihrer Konklusion

Es werden nur solche Regelpaare verschmolzen, welche eine in den ersten k-1 Items gleiche Konklusion haben, z.B.

• bd ac und cd ab zu d abc• ae bcd und ad bce zu a bcde

Voraussetzung: sortierte Itemlisten (zumindest) in der Konklusion

Pruning

Ist eine so erzeugte Regel nicht hinreichend konfident, wird sie nicht in die Ebene k+1 aufgenommen und somit nicht für weitere Verschmelzungen herangezogen.

202


Redundanzfreie Regel-Verschelzungen im konklusionenbasiert gebildeten Verband

abcd→

abc→d abd→c acd→b bcd→a

ab→cd ac→bd bc→ad ad→bc bd→ac cd→ab

a→bcd c→abdb→acd d→abc

→abcd

102

203

3.4 Evaluierung von Assoziations-Patterns

Maße für

“Interessantheit”

Feature

Prod

uctP

roduct

Prod

uctP

roduct

Prod

uctP

roduct

Prod

uctP

rod

uctP

rod

uctP

rod

uct

FeatureFeatureFeatureFeatureFeatureFeatureFeatureFeatureFeature

Datenauswahl

Vorverarbeitung

Mining

Nachbearbeitung

Daten

ausgewählteDaten

vorverarbeiteteDaten

Patterns

Wissen

204

3.4 Evaluierung von Assoziations-Patterns

Assoziations-Pattern

= Paar [Prämisse, Konklusion] einer Assoziationsregel Prämisse Konklusion

Wie „interessant“ ein Pattern [A, B] ist, wird anhand der Häufigkeiten des (nicht-) Auf-tretens der verschiedenen Kombinationen aus A, B, ¬A, ¬B in den Transaktionen ermittelt

Häufigkeiten werden in einer Kontingents –Tabelle repräsentiert:

B ¬B

A f11 f10 f1+

¬A f01 f00 f0+

f+1 f+0 N

Mit Kontingents-Tabellen können div. „Interessantheits-Maße“ ermittelt werden, z.B.:

(1) Konfidenz

(2) Lift-Maß

(3) Interest Faktor

(4) Korrelation (φ – Koeffizient)

(5) Interest Ssupport (IS-Maß)

(6) Odds Ratio (α – Koeffizient)

103

205

(1) Konfidenz - basierte Evaluierung

Konfidenz: c( A → B ) = σ( A B ) / σ(A) = (f11 /N)/ (f1+ /N)= f 11 / f1+

Analyse des Zusammenhangs zwischen Kaffee- und Teetrinkern, 1000 Leute:

Kaffee ¬ Kaffee

Tee 150 50 200

¬Tee 650 150 800

800 200 1000

r: Tee Kaffee ist sehr konfident: 150/200 = 0.75

allerdings trinken ohnehin fast alle Leute (unabhängig vom Tee trinken) Kaffee: 80% Anteil der Kaffee-Trinker unter den Tee-Trinkern ist sogar noch geringer als unter

allen Befragten: 75%

Regel r: Tee Kaffee ist trotz hoher Konfidenz irreführend!

Nachteil:

Support der Regelkonklusion bleibt unberücksichtigt

‘n Beispiel

206

(2) Lift - basierte Evaluierung

relativiert Konfidenz mit dem Support der Konklusion.

Damit wird ausgedrückt, um welchen Faktor B wahrscheinlicher wird, wenn A auftrat ggü. der absoluten Wahrscheinlichkeit von B.

Dieses Maß ist für binäre Variablen (was auf die Aussagen rechts und links von „→“ zutrifft) symmetrisch:

Lift(A,B) = Lift(B,A)

Sind A und B unabhängig s(AB) = s(A) s(B) Lift(A→B) = 1

Korrelieren A und B positiv s(AB) > s(A) s(B) Lift(A→B) > 1

Korrelieren A und B negativ s(AB) < s(A) s(B) Lift(A→B) < 1

11

11

)()(

)(

)()(

)(

)(

)()(

ff

Nf

BsAs

BAs

BsAs

BAs

Bs

BAcBALift

104

207

(3) Interest-Faktor - basierte Evaluierung

wichtet Konfidenz mit dem Support der Konklusion.

Damit wird die Konfidenz einer Regel mit ihrer „Interessantheit“ (der Wahrscheinlichkeit des Auftretens) der Konklusion gewichtet.

Nf

ff

N

B

A

BABsBAcBAI

1

111)(

)(

)()()()(

208

Nachteil der Lift (Interest-Faktor) - basierten Evaluierug

Beispiel Text-Mining: gemeinsames Auftreten von Wort-Paaren p, q und r, s

p ¬p

q 880 50 930

¬q 50 20 70

930 70 1000

r ¬r

s 20 50 70

¬s 50 880 930

70 930 1000

Durch die Relativierung auf (bzw. Wichtung mit) den Support der Konklusion wird der offensichtlich stärkere Zusammenhang von p, q ggü. r, s verschleiert:

018.1930930

1000880)(

qpLift 082.47070

100020)(

srLift

Hier wäre die Konfidenz-basierte Evaluierung besser:

946.0930

880)( qpc 286.0

70

20)( src

105

209

(4) Korrelation (φ – Koeffizient) - basierte Evaluierung

n

k

n

k

n

k

yx

xy

ss

s

) std_abw(y) stdt_abw(x

x,y)covarianz(corr(x,y)

1

2k

1

2k

1kk

)y-(y)x-(x

)y-)(yx-(x

Für numerische Variablen haben wir Korrelation so definiert (siehe Folie 25):

Für binäre Variablen entspricht dies dem φ – Koeffizienten:

0011

10010011

ffff

ffff

Nachteil der Korrelations (φ – Koeffizient) - basierten Evaluierung

Co-Präsenz und Co-Absenz werden gleich bewertet

• für o.g. Beispiel aus dem Text – Mining ist φ(p,q)= φ (r,s)=0.232, obwohl der Zusammenhang von p, q signifikanter als bei r, s ist

φ – Koeffizient ist besser für symmetrische Variablen geeignet

210

(5) IS (Interest-Support)- basierte Evaluierung

speziell für asymmetrische Attribute (solche, bei denen es nur auf Werte ≠ 0 ankommt) entwickelt

Entspricht Kosinus-Koeffizienten für binäre Variablen:

11

1111

11

1111

11

11

)()(

),(),(

)()(

),(

),(),(),(

ff

f

N

f

ff

fN

N

f

Nf

Nf

Nf

BsAs

BAsBAs

BsAs

BAs

BAsBAIBAIS

n

kk

n

kk

n

kkk

yx

yxyxsim

1

2

1

2

1

*

),(

106

211


Für unser Beispiel aus dem Text Mining

p ¬p

q 880 50 930

¬q 50 20 70

930 70 1000

r ¬r

s 20 50 70

¬s 50 880 930

70 930 1000

…ist IS deutlich besser als Interest-Faktor (Lift-Maß) oder Korrelation (φ – Koeffizient):

IS(p,q) = 0.946

IS(r,s) = 0.286

Dies trifft unsere (intuitive) Erwartung.

212


für statistisch unabhängige Items ist s(A,B) = s(A) s(B) bzw. f11/N = f1+/N f+1 /N

IS entartet dann zu

N

f

N

fBsAsBAISindep

11)()(),(

Unabhängigkeit äußert sich in Praxi darin, dass die Häufigkeit, dass die Items zusammen oder nicht zusammen im Warenkorb liegen, gleich hoch ist

Beispiel:

p ¬p

q 250 250 500

¬q 250 250 500

500 500 1000

In der Tat ist hier

IS(p,q) = ISindep(p,q) = 0.5

(6) Odds Ratio (α – Koeffizient) - basierte Evaluierung

… ist das Verhältnis zwischen Co-Präsenz oder Co-Absenz zu allen anderen Fällen:

0110

0011

),(1

),(1

),(1

),(1

),(),(

),(),(),(

ff

ff

BAN

BAN

BAN

BAN

BAsBAs

BAsBAsBA

107

213

Zusammenfassung „Interessantheits-Maße“ von Assoziationspatterns

Es gibt zwei Kategorien von Metriken M(AB):

Symmetrische Metriken: M(AB) = M(BA) (deshalb oft M(A,B) geschrieben)

Asymmetrische Metriken: M(AB) ≠ M(AB)

N

f

f

fAV

Nf

Nf

ff

F

fNffV

ffL

N

f

f

f

f

f

N

f

N

f

f

f

f

f

N

fG

ff

fN

N

f

ff

fN

N

fJ

1

1

)()(

)2()1(

loglog

1

11

11

1

11

1001

111

2

0

2

0

00

2

0

010

2

1

2

1

10

2

1

111

01

1010

11

1111

Symmetrisch sind außer dem Konfidenz-Maß alle hier behandelten Metriken: Lift, Korrelation (φ – Koeffizient), IS-Maß, Odds Ratio (α – Koeffizient)

Asymmetrisch sind neben dem Konfidenz-Maß (c) auch J-Maß (J) (Entropie-ähnlich), Gini Index (G), Laplace (L), Cobnviction(V), Certainty factor (F), Addad value (AV):

214

4 Cluster-Analyse

Ziel

Einteilung der DO eines Datensatzes in Gruppen (Cluster), welche

„sinnstiftend“ (die natürliche Struktur der DO widerspiegelnd, um diese zu verstehen) oder

„nützlich“ (für andere Zwecke, z.B. einer Zusammenfassung von DO-Eigenschaften)

sind.

Inter-Cluster Abstände maximal

Intra-Cluster Abstände minimal

108

215

Biologie

Erarbeitung einer Taxonomie über Species: Art, Familie, Ordnung, Klasse, Stamm, Reich

Clustern von Genen mit jeweils ähnlichen Funktionen

Information Retrieval

effizientes Suchen im WWW durch Clustern der Suchbegriffe, z.B. Film in die Cluster Reviews, Trailer und Stars

Klimaforschung

durch Cluster-Analyse wurde der Einfluss der Luftdruckverhältnisse in den Polarregionen und über den Weltmeeren auf das Klima an Land aufgedeckt

Medizin und Psychologie

pathologische Erscheinungen haben gewöhnlich mehrere Ausprägungen, solche Sub-Kategorien (z.B. Typen von Depressionen) sind durch Cluster-Analyse identifiziert worden

Wirtschaft

Kunden können durch Cluster-Analyse partitioniert werden in Gruppen mit ähnlichen Interessen, um das Marketing kundenspezifischer (und damit effektiver) zu machen

Beispiele für „sinnstiftendes“ Clustering

216

Zusammenfassungen (effiziente Datenverarbeitung)

Viele Analysetechniken haben eine Komplexität o(n2) oder schlimmer. Clustert man die Daten zuvor und wendet diese Techniken dann nur noch auf Cluster-Prototypen an, werden sie effizienter

Datenkompression

Ähnliches geschieht bei der Vektor-Quantisierung von Bild-, Ton- oder Videodaten. Für jedes Cluster wird nur ein Repräsentant nebst seinen Positionen im Datenstrom abgelegt

effiziente Ermittlung nächstliegender Nachbarn

Der paarweise Vergleich von Abstandsmaßen mach die Ermittlung nächster Nachbarn in großen Datenmengen sehr komplex. Macht man das nur mit Cluster-Prototypen, wird die Ermittlung effizienter

Beispiele für „nützliches“ Clustering

109

217

Ziel: Finden von Clustern, welche

sich signifikant voneinander unterscheiden, d.h. welche einen maximalen Abstand voneinander haben, und

innerhalb derer sich die DO nicht signifikant unterscheiden („dicht beieinander“ sind), d.h. einen minimalen Abstand voneinander haben.

Clustering-Aufgaben haben keine eindeutige Lösung, Beispiel:

4.1 Überblick

Wie viele Cluster?

4 Cluster2 Cluster

6 Cluster

218

(1) hierarchisch versus Partitionierung

Partitionierung

Einteilen der DO in disjunkte Teilmengen (Cluster), so dass jedes DO zu genau einem Cluster gehört (wie im Beispiel der vorherigen Folie)

hierarchisches Clustern Ermittlung einer baumförmigen Cluster-Hierarchie jede Astgabel des Baumes ist eine (weitere) Partitionierung jeder Knoten (Cluster) im Baum (mit Ausnahme der Blätter) enthält die

DO, die sich aus der Vereinigung der DO seiner Unterbäume ergibt im Beispiel könnte man die Einteilung in 2, 4 und 6 Cluster als auch

baumförmige Cluster-Hierarchie organisieren traditionell (constrained Clustering): binärer Baum, jede Astgabel

des Baumes identifiziert ein (fertiges) Cluster (Blattknoten) in einem Unterbaum und die restlichen im anderen Unterbaum

Clustering = Aufteilung von DO in Cluster

4.1.1 Typen von Clusterings

110

219

Partitionierendes Clustering

Original DO Partitionierendes Clustering

220

hierarchisches Clustering

p4p1

p3

p2

„traditionelles“ hierarchisches Clustering

Repräsentationim „traditionellen“ Dendrogramm

p4 p1

p3

p2

hierarchisches constrained Clustering

Repräsentationim constrained Clustering

Dendrogramm

111

221

(2) exklusiv versus überlappend

exklusive: jedes DO gehört zu genau einem Cluster

überlappend: ein DO kann zu mehreren Clustern gehören

(3) fuzzy versus scharf

fuzzy jedes DO gehört zu jedem Cluster mit einem Gewicht g, 0 ≤ g ≤ 1 Summer aller Gewichte für ein DO = 1

scharf: scharfe Zugehörigkeiten (0 oder 1)

(4) partiell versus total

partiell: einige DO bleiben clusterfrei

total: jedes DO gehört zu (mindestens) einem Cluster

(5) heterogen versus homogen

heterogen: die Cluster haben verschiedene Größen, Formen und Dichten

homogen: die Cluster sind gleich in Größe, Form oder Dichte

Typen von Clusterings

222

4.1.2 Typen von Clustern

(1) wohl – separierte Cluster

jedes DO eines Clusters ist näher (ähnlicher) zu jedem anderen DO innerhalb des Clusters als zu allen DO außerhalb des Clusters

m.a.W., jeder Punkt außerhalb des Clusters ist ferner (verschiedener) als der fernste Punkt innerhalb des Clusters

Beispiel: 3 wohl-separierte Cluster

112

223


(2) Prototyp – basierte Cluster (center-based cluster)

jedes DO eines Clusters ist näher (ähnlicher) dem Zentrum (zum Prototyp – DO) seines Clusters als zum Zentrum jedes anderen Clusters

tendieren zur Kugelförmigkeit

Zentrum des Clusters wird häufig

Centroid genannt, wenn es für jedes Attribut den Durchschnitt der Werte aller DO des Clusters hat

Medoid genannt, wenn es das „repräsentativste“ DO des Clusters bildet

Ein Centroid ist nicht zwangsläufig ein reales DO, ein Medoid hingegen ist eines der DO.

Beispiel: 4 Prototyp-basierte Cluster

224


(3) zusammenhängende Cluster (contiguity-based cluster)

jedes DO eines Clusters ist zu mindestens einem DO seines Clusters näher (ähnlicher), als zu jeden DO außerhalb des Clusters

Beispiel: 8 zusammenhängende Cluster

113

225


(4) Dichte - basierte Cluster (density-based cluster)

ein Cluster ist eine Region, die sich von angrenzenden Gebieten des „Raumes“ durch eine hohe Dichte von DO auszeichnet

Cluster sind von anderen Clustern durch „Gebiete geringer Dichte“ separiert.

werden typischerweise verwendet, wenn

Cluster irreguläre Formen haben

Cluster ineinander verflochten sind

verrauschte Daten oder „Außenseiter“ im Datensatz sind

Beispiel: 6 Dichte-basierte Cluster

226


(5) konzeptuelle Cluster (conceptual cluster, shared-property cluster)

Umfasst alle anderen o.g. Typen

Cluster werden als Menge von DO mit einer gemeinsamen Eigenschaft, die nicht als Attribut definiert ist, definiert und nicht durch die Verteilung der DO im Attribut-Raum

können nichtleere Schnittmengen haben

Beispiel: 2 konzeptuelle Cluster

im Weiteren vorgestellte Clustering Verfahren

• K - means / K - medoid (4.2)

• hierarchisches Clustering (4.3)

• dichtebasiertes Clustering mit DBSCAN (4.4)

114

227

4.2 K – means (K - medoid)

= Prototyp – basiert, partitionierend, nicht hierarchisch

4.2.1 Grundlegender K – means (K - medoid) Algorithmus

initial werden (mehr oder weniger willkürlich) K Centroiden (Medoiden) festgelegt (K: gewünschte Anzahl von Clustern)

zyklisch wird

1. Jedes DO wird dem nächstgelegenen Centroiden (Medoiden) zugeordnet „nächstgelegen“: Euklidischer Abstand, Kosinus-Koeffizient,

Korrelation, …

2. und der Centroid (Medoid) eines jeden Clusters danach neu berechnet

… solange, bis sich keiner Centroiden (Medoiden) durch die Neuberechnung mehr ändert, d.h. kein DO die Clusterzugehörigkeit ändert

konvergiert typischerweise schnell (nach wenigen Zyklen)

Falls nicht, weicht man mitunter das Stopp-Kriterium auf:„solange, bis sich nur wenige Centroiden (Medoiden) mehr ändern“

Komplexität o( n K I d ) n: Anz. d. DO, K: Anz. d. Centroiden (Medoiden), I: Anz. d. Iterationen, d: Anz. d. Attribute

228

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

y

Iteration 1

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

y

Iteration 2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

y

Iteration 3

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

y

Iteration 4

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

y

Iteration 5

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

y

Iteration 6

Beispiel2 Attribute, Euklidisches Abstandsmaß, 3 Centroiden ( + )

Zuordnung zum nächstgelegenen Centroiden: häufigste Ähnlichkeitsmaße

Euklidischer (L2) oder Manhatten (L1) Abstand im Euklidischen Raum

Kosinus-Koeffizient oder Jaccard Koeffizient für Dokumente

115

229

Zielfunktion

(bei Auswahl des besten Clusterings nach mehrfacher Anwendung der Technik)

Im Euklidischen Raum mit L2-Distanzmaß:

sum of the squared error SSE

i

i

Cxii

K

i Cxi

xm

c

xcdistSSE

1

mit

),(1

2 • x DO• Ci i -tes Cluster• ci Centroid des Clusters Ci

• mi Anz. d. DO im i –ten Cluster

• m Gesamtzahl der DO• K Anz. d. Cluster

‘n Beispiel für die Centroiden - Berechnung

Cluster Ci im 2-dim. Raum habe die DO Ci= [1,1] , [2,3] , [6,2]

⇒ ci = [ (1+2+6)/3 , (1+3+2)/3 ] = [9,2]

230

Zielfunktion (Auswahl des besten Clusterings nach mehrfacher Anwendung der Technik)

für Dokumente repräsentiert durch eine Dokument – Term – Matrix: Zeilen: Dokumente, Spalten: Begriffe, Einträge: Anzahl des Auftretens des Begriffes Ähnlichkeitsmaß: Kosinus-Koeffizient Zielfunktion: Ähnlichkeit der Dokumente eines Clusters zu maximieren

Kohäsion (Cohesion) des Clusters total_cohesion

],1

,,1

,1

[

),cos(_

112

11

1

1

2

1

2

1

1

)t"ttsdokumenDurchschni dem(" Centroiden demmit

iii

ii

m

jnj

i

m

jj

i

m

jj

ii

K

i Cxn

kki

n

kkj

n

kkikjK

i Cxij

em

em

em

c

ce

cecxcohesiontotal

mit• xj Dokument (j - te Matrix-Zeile)• Ci i -tes Cluster• ci Centroid des Clusters Ci

• mi Anz. d. DO im i –ten Cluster• m Gesamtzahl der DO• ekj Eintrag in der Matrix:

Anz. d. Terme tk im Dokument dj

• n Anz. d. Terme• K Anz. d. Cluster

d1 d2 d3 d4 d5 d6 c Toyota 1 1 2 1 1 1 7/6Honda 1 1 2 0 2 0 6/6hybrid 1 1 2 1 3 3 11/6Super 1 1 2 0 4 0 8/6Diesel 1 1 2 1 5 5 15/6Akku 1 1 2 0 6 0 10/6

‘n Beispiel für dieBerechnung einesCentroiden c

116

231

Auswahl von Initial - Centroiden

Davon hängt ab, ob das Verfahren in das globale oder in ein lokales Minimum des SSE(sum of the squared error) konvergiert.

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

y

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

y

sub-optimales Clustering(lokales Minimum des SSE)

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

y

optimales Clustering(globales Minimum des SSE)

Originalpunkte

232

noch ein Beispiel (aus Tan/Steinbach/Kumar):

identische DO, optimale vs. schlechte Initial-Centroiden (hier: Kreuze)

117

233

und noch ein Beispiel (aus Tan/Steinbach/Kumar): Cluster-Paare (rechts/links) werden gefunden, wenn in jedem Paar 2 Initial-Centroide sind

234

und noch ein Beispiel (aus Tan/Steinbach/Kumar): Cluster-Paare (rechts/links) werden nicht gefunden, wenn in einem Paar 1 und im anderen Paar 3 Initial-Centroide sind: 2 wirkliche Cluster werden verschmolzen und ein wirkliches Cluster wird geteilt:

118

235

ein Ansatz zur Vermeidung lokaler SSE Minima

wähle den ersten Centroid zufällig oder verwende den Centroiden aller DO

für alle weiteren Centroiden wähle jeweils einen Punkt, der am weitesten entfernt von allen bisher gewählten Centroiden ist

Vorteil: Initial-Centroiden sind wohl separiert

Nachteil: ggf. werden „Ausreißer“ zu Clustern erhoben (statt Regionen mit hoher Dichte)

noch ein Ansatz

führe zunächst ein hierarchisches Clustering durch

verwende die Centroiden der dabei entstehenden K Cluster and Initial-Centroide des partitionierenden Clusterings

Komplexität

)( ))((( nmKIOtimenKmOspace mit m Anzahl der DO

n Anzahl der Attribute

K Anzahl der gewünschten Cluster

I Anzahl der Iterationen (gewöhnlich gering, konvergiert recht schnell)

236

4.2.2 Weiterführende Aspekte

Vermeidung leerer Clusterbleibt ein Cluster leer, ersetzt man dessen Centroid durch einen neuen Centroiden, z.B. das DO, welches am weitesten von allen bisherigen Centroiden entfernt ist oder ein DO, welches in demjenigen Cluster liegt, welches am meisten zum Sum of

Squared Error (SSE) beiträgt (den größten Cluster-SSE hat) und splittet dieses damit in 2 Cluster

Ausreißer führen dazu, dass Centroiden nicht wirklich repräsentativ für ihr Cluster sind oder Mini-Cluster von Ausreißer-Gruppen entstehen Indiz zur Identifikation: DO eines Clusters, die extrem zum SSE dieses Clusters

beitragen, stehen im Verdacht „Ausreißer“ zu sein

Optimierung durch Nachbearbeitung (Post Processing) Splitting eines Clusters mit besonders großem Culster-SSE in 2 Cluster Einführung eines neuen Clusters mit dem DO, welches am weitesten von allen

Centroiden entfernt ist, als neues Centroiden (s.o.) Entfernung der Centroiden solcher Clustern, deren Entfernung die geringste SSE-

Erhöhung nach sich zieht und Zuordnung der betroffenen DO zu anderen Clustern Verschmelzung 2er Cluster, deren Centroiden am dichtesten beieinander liegen oder

deren Verschmelzung die geringste SSE Erhöhung nach sich zieht

119

237

4.2.3 Bisecting K – means

beginnend mit genau 2 Clustern in jedem Zyklus ein Cluster ein Cluster ausgewählt, welches in 2 neue Cluster gesplittet wird …

…bis die gewünschte Anzahl von K Clustern entstanden ist

Mögl. Auswahlkriterien:

größtes Cluster (bzgl. Anz. d. DO)

Cluster mit größtem SSE

macht K - means weniger anfällig ggü. Initialisierungsproblemen (Finden guter Initial-Centroiden):

zunächst bisecting K – means anwenden

dann die resultierenden Centroiden als Initial – Centroiden für klassisches K –means verwenden

⇒Vermeidet lokale SSE – Minima, weil SSE Minima gezielt in Teilmengen der DO gesucht werden: Das Optimum für jede Teilmenge hat bessere „Chancen“, auch global das Optimum zu sein

238

4.2.4 Probleme mit K - means bei verschiedenen Clustertypen

4.2.4.1 Cluster verschiedener Größe

größere natürliche Cluster tendieren dazu, durch K-Means aufgeteilt zu werden

Originale DO Ergebnis von K-means (3 Cluster)

120

239

4.2.4 Verhalten von K - Means bei verschiedenen Clustertypen

4.2.4.2 Cluster verschiedener Dichte

natürliche Cluster werden aufgrund unterschiedlicher Dichte mitunter nicht gefunden


240

4.2.4 Verhalten von K - Means bei verschiedenen Clustertypen

4.2.4.3 Nicht globulare Cluster

Ineinander „verwundene“ und nicht-konvexe Cluster werden nicht gefunden

Aufgrund des Zuordnungs-Kriteriums „Abstand zum Centroiden“ werden nicht globulare natürliche Cluster nicht identifiziert.


121

241

4.3 Hierarchisches Clustering

produziert eine Menge baumartig geschachtelter Cluster

kann im bottom-up oder top-down Verfahren durchgeführt werden:

Agglomeratives Clustering (bottom-up)

beginnt mit einzelnen DO als Clustern

in jedem Schritt wird dasjenige Paar von Clustern verschmolzen, welches am dichtesten beieinander liegt

Divisives Clustering (top down)

beginnt mit einem alle DO enthaltenden Cluster

in jedem Schritt ein Cluster in zwei neue Cluster gesplittet, bis die gewünschte Anzahl von Clustern erreicht wird

Auswahl des zu splittenden Clusters: größtes Cluster Cluster mit größtem SSE … wird kaum verwendet

242

4.3 Hierarchisches Clustering

Veranschaulichung der Cluster-Hierarchie

Dendrogramm Cluster Diagramm

Höhe der Gabelungen= Abstand der verschmolzenen Cluster

1 3 2 5 4 60

0.05

0.1

0.15

0.2

1

2

3

4

5

6

1

23 4

5

Jede gewünschte Anzahl von Clustern kann erzeugt werden, indem man das Dendrogramm auf der entsprechenden Höhe schneidet

122

243

4.3.1 Hierarchischer Clustering Grund-Algorithmus

Beginnend mit den DO als jeweils ein Cluster werden die beiden am nächsten beieinander liegenden Cluster verschmolzen, bis nur noch ein Cluster verbleibt:

1. errechne eine Distanz-Matrix zwischen den Clustern

2. repeat

verschmelze die beiden Cluster, die am nächsten beieinander liegen

aktualisiere die Distanz-Matrix entsprechend (in der Zeile und/oder Spalte des neuen Clusters)

3. until nur noch ein Cluster verfügbar

244

Startsituation

Start mit DO als individuelle Cluster und einer Distanz-Matrix

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

. Distanz Matrix

123

245

Situation nach einer Anzahl von Durchläufen

nach einigen Verschmelzungsschritten liegen einige Cluster vor

C1

C4

C2 C5

C3

C2C1

C1

C3

C5

C4

C2

C3 C4 C5

Distanz-Matrix

246

Situation nach einer Anzahl von Durchläufen

die 2 nächstgelegenen Cluster (C2 and C5) werden verschmolzen und die Distenz-Matrix aktualisiert

C1

C4

C2 C5

C3

C2C1

C1

C3

C5

C4

C2

C3 C4 C5

Distanz-Matrix

124

247

nach der Verschmelzung

Wie ist die Distanz-Matrix zu aktualisieren?

C1

C4

C2 U C5

C3? ? ? ?

?

?

?

C2 U C5C1

C1

C3

C4

C2 U C5

C3 C4

Distanz-Matrix

248

Ansätze zur Distanzermittlung zwischen 2 Clustern aus dem Distanzmaß zwischen 2 DO

1. MIN: Abstand zw. den einander nächstgelegenen DO der beiden Cluster

2. MAX: Abstand zw. den einander entferntesten DO der beiden Cluster

3. AVERAGE: Durchschnitt der Abstände jedes Paars von DO aus je einem der beiden Cluster

4. Abstand der Cetroiden

5. Ward‘s Methode: Centroid-basiert, Abstand ist def. durch die Verschlechterung des SSE (Sum of Squared Error)-Verbesserung beim Verschmelzen des Cluster-Paars

Ansätze zur Distanzermittlung zwischen 2 Clustern aus dem Distanzmaß zwischen 2 DO

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

Distanz ?

Distanz-Matrix

125

249

Ansätze zur Bestimmung der Cluster Abstände

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

Distanz-Matrix

1. MIN (single link)

2. MAX (complete link)

3. AVERAGE (group average)

4. Abstand der Centroiden

5. Zielfunktions – orientierte Methoden

Ward’s Clustering Methode

Es wird diejenige Verschmelzung durchgeführt, welche die geringste Verschlechterung des SSE (sum of squared error) zur Folge hat.

250

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

Distanz-Matrix









126

251

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

Distanz-Matrix









252

p1

p3

p5

p4

p2

p1 p2 p3 p4 p5 . . .

.

.

.

Distanz-Matrix









127

253

Beispiel-Datensatz

DO x y

p1 0.4005 0.5306

p2 0.2148 0.3854

p3 0.3457 0.3156

p4 0.2652 0.1875

p5 0.0789 0.4139

p6 0.4548 0.3022

Datenobjekte

0

0,1

0,2

0,3

0,4

0,5

0,6

0 0,1 0,2 0,3 0,4 0,5

x

y

p1 p2 p3 p4 p5 p6

p1 0 0.2357 0.2218 0.3688 0.3421 0.2347

p2 0.2357 0 0.1483 0.2042 0.1388 0.2540

p3 0.2218 0.1483 0 0.1513 0.2843 0.1100

p4 0.3688 0.2042 0.1513 0 0.2932 0.2216

p5 0.3421 0.1388 0.2843 0.2932 0 0.3921

p6 0.2347 0.2540 0.1100 0.2216 0.3921 0

Distanz-Matrix(Euklidischer Abstand)

254

3 6 2 5 4 10

0.05

0.1

0.15

0.2

Cluster nach MIN-Ansatz (single link approach)

kleinster Abstand zwischen p3 und p6:• d(p3,p6) = 0.1100 erste Dendrogramm-Gabelung bei y = 0.1100

weiteres Beispiel• dist(p3,p6,p2,p5) = min(d(p3,p2), d(p3,p5) , d(p6,p2) , d(p6,p5) )

= min( 0.1483, 0.2843, 0.2540, 0.3921)= 0.1483

Dendrogramm-Gabelung bei y = 0.1483

1

2

3

4

5

6

1

2

3

4

5

128

255

Cluster nach MAX-Ansatz (complete link approach)

kleinster Abstand zwischen p3 und p6:• d(p3,p6) = 0.1100 erste Dendrogramm-Gabelung bei y = 0.1100

weiteres Beispiel• dist(p2,p5,p1) = max(d(p2,p1), d(p5,p1))

= max( 0.2357, 0.3421) = 0.3421 Dendrogramm-Gabelung bei y = 0.3421

3 6 4 2 5 10

0.05

0.1

0.15

0.2

1

2

3

4

5

6

1

2 5

3

4 0.3

0.4

0.25

0.35

256

Cluster nach AVERAGE-Ansatz (group average approach = Abstand der Centroiden) kleinster Abstand zwischen p3 und p6:

• d(p3,p6) = 0.1100 erste Dendrogramm-Gabelung bei y = 0.1100 weiteres Beispiel

• dist(p3,p6, p4,p2,p5)= d(p3,p2)+d(p3,p5)+d(p6,p2)+d(p6,p5)+d(p4,p2)+d(p4,p5) / 6= 0.1483+0.2843+0.2540+0.3921+0.2042+0.2932 / 6 = 0,2627 Dendrogramm-Gabelung bei y = 0.2627

1

2

3

4

5

6

1

2

5

3

4

3 6 4 2 5 10

0.05

0.1

0.15

0.2

0.25

0.3

129

257

Cluster nach WARD‘s Methode


1

2

3

4

5

61

2

5

3

4

3 6 4 1 2 50

0.05

0.1

0.15

0.2

0.25

0.3

258

Group Average

Ward’s Method

1

2

3

4

5

61

2

5

3

4

MIN MAX

1

2

3

4

5

61

2

5

34

1

2

3

4

5

61

2 5

3

41

2

3

4

5

6

12

3

4

5

Vergleich aller Methoden

130

259

Vorteile Nachteile

MIN erkennt auch nicht-elliptische Cluster-Formen gut

anfällig gegen verrauschte Daten und „Ausreißer“ tendiert zur Bildung „kettenförmiger“

Clustergebilde (chaining effect), in welchem sich DO befinden, die zueinander geringere Ähnlichkeit aufweisen als zu DO anderer Cluster

MAX weniger anfällig gegen verrauschte Daten und Ausreißer

tendiert dazu, große Cluster zu splitten bildet vorzugsweise gleich große Cluster bildet vorzugsweise kugelförmige Cluster erkennt nicht – konvexe Cluster oft nicht

AVERAGE weniger empfindlich gegen verrauschte Daten und Ausreißern

bildet vorzugsweise gleich große Clusterbildet vorzugsweise kugelförmige Clustererkennt nicht – konvexe Cluster oft nicht

WARD weniger anfällig gegen verrauschte Daten und Ausreißer

eignet sich gut zur Ermittlung geeigneter Initial - Centroiden für K - means

bildet vorzugsweise kugelförmige Cluster

Nachteile aller hierarchischen Verfahren Gebildetes Cluster werden nie wieder “angefaßt”. Eine einmal vollzogene

Verschmelzung kann nicht wieder rückgängig gemacht werden Die Zielfunktion wird meist nicht direkt minimiert (Ausnahme: Ward) diverse Cluster – Abstandsmaße haben spezifische Nachteile (s.o.)

260

4.4 Dichtebasiertes Clustering mit DBSCAN

Dichte eines Punktes = Anzahl d. DO innerhalb eines Radius Eps (inkl. des Punktes)

Core PointDO, in deren Eps - Umgebung ein Minimum MinPts weiterer DO ist

Border PointDO, in deren Eps - Umgebung dieses Minimum nicht erreicht wird, aber ein Core Point in der Eps - Umgebung liegt

Noise point:DO, die weder Core Pointnoch Border Point sind

131

261

In einem Cluster zusammengefasst werden:

Core Points, welche einen Abstand von höchstens Eps zueinender haben

Border Points, in deren Eps - Umgebung einer der o.g. Core points liegt⇒ Für den Fall, dass mehrere Core Points in der Eps – Umgebung eines Border

Points liegen, müssen Regeln für eine eindeutige Zuordnung getroffen werden.

Algorithmus DBSCAN1. klassifiziere alle DO als Core - , Border- oder Noise

Point2. entferne alle Noise Points3. verbinde alle Core Points, deren Entfernung ≤ Eps ist

4. fasse alle verbundenen DO zu einem Cluster zusammen

5. ordne alle Border Points zu einem der Cluster seiner Core Points zu

262

Wie findet man geeignete Parameter Eps und MinPts ?

Idee

In allen Clustern sollte die Distanz eines DO zu seinem k -t nächsten Nachbarn etwa gleich sein.

Noise Points sollten ihren k -t nächsten Nachbarn in einer deutlich weiteren Entfernung haben als Cluster Points

Ansatz

Ermittle für alle DO die Distanzihrem k -t nächsten Nachbarnfür verschiedene k

Zeichne für jedes k einDiagramm, in dem für jede Distanz die Anzahl der in diese Distanz hinein fallenden DO abgetragen ist.

Ab einer gewissen Distanz steigt diese Anzahl sprunghaft; dort ist der für dieses k (alsMinPts) geeignete Wert für Eps

132

263

‘n Beispiel (aus dem das Diagramm der vorigen Folie gewonnen wurde)

3000 DO im R2

MitPts = 4 Eps = 10 (siehe Diagramm)

Original - DO

• Core Points• Border Points• Noise Points

264

‘n Beispiel (aus dem das Diagramm der vorigen Folie gewonnen wurde)

3000 DO im R2

MitPts = 4 Eps = 10 (siehe Diagramm)

Original - DO Cluster

133

265

Stärken und Schwächen von DBSCAN

wenig anfällig ggü. verrauschten Datan kann verschiedene Clusterformen und –größen erkennen (und ist in

dieser Frake z.B. K – means weit überlegen)

kann Cluster mit sehr verschiedenen Dichten schlecht erkennen ist schwer anwendbar bei viel - dimensionalen Daten (schwer zu

definierendes Dichte – Maß) hohe Zeitkomplexität, insbesondere bei der paarweisen Ermittlung eines

k –t nächsten Nachbarn bei viel – dimensionalen Daten

Documents

Data Mining - Startseite TU Ilmenau · 1 1 Data Mining Vorlesung Stand 12.06.2013 apl. Prof. Dr.-Ing. habil. Rainer Knauf Fachgebiet Künstliche Intelligenz Fakultät für Informatik