Data MiningAssoziationsanalyse

KlassifikationClustering

Data Mining 2

Literatur

• Datenbanksysteme, Kapitel 17Kemper, Eickler

• Introduction to Data MiningPang-Ning Tan et. al.

Data Mining 3

Was ist Data Mining?

• Data Mining ist der Prozess, nützliche Informationen aus großen Datenbeständen zu gewinnen.

• Hierbei werden mathematische Methoden auf den Datenbestand angewandt zur Mustererkennung.

Data Mining 4

Was ist (nicht) Data Mining?

Beispiele für Data Mining• Bestimmte Namen sind in bestimmten Gegenden

häufiger anzutreffen (z.B. Mayer besonders häufig in Baden-Württemberg, gen-evolu.de)

• Wettervorhersage

Folgendes ist NICHT Data Mining• Nachschlagen einer Telefonnummer im

Telefonverzeichnis• Webanfrage zu Informationen über Data Mining

Data Mining 5

Warum Data Mining? – betriebswirtschaftliche Sicht

• Sehr viele Daten werden gespeichert:– Einkäufe– Geldtransfer– Internet-Daten, Webshops– ...

• Computer sind preisgünstiger und schneller geworden– Speicherplatz wird immer günstiger– Daten leicht beschaffbar

• Konkurrenzdruck– Bedarf der Zielgruppenanalyse– Bedarf der Produktoptimierung

Data Mining 6

Warum Data Mining? – wissenschaftliche Sicht

• Daten werden mit großer Geschwindigkeit erzeugt und gespeichert– experimentelle Messdaten– wissenschaftliche Simulationen

• Data Mining hilft in der Wissenschaft:– Klassifikation von Daten– Formulierung und Verifikation von Hypothesen

Data Mining 7

Ursprünge des Data Mining• Verwendet Ideen des maschinellen Lernens, der

Mustererkennung, der Statistik und von Datenbanksystemen

• Traditionelle Techniken können nicht angewendet werden aufgrund– großer Datenmengen– hoher Dimensionalität der Daten– Heterogenität der Daten

Maschinelles LernenMustererkennungStatistik

Data Mining

Datenbank-Systeme

Data Mining 8

Methoden des Data MiningVorhersagende MethodenVerwendung von Variablen, um unbekannte oder zukünftige Werte anderer Variablen vorherzusagen.• Regression• Klassifikation

Beschreibende MethodenHerausfinden interpretierbarer Muster, die die Daten beschreiben• Visualisierung• Assoziationsregeln• Clustering• Aufdecken von Anomalien

Data Mining 9

Attribut-TypenQualitative (oder kategorische) Attribute • repräsentieren verschiedene Kategorien und keine Zahlen. Mathematische

Operationen nicht sinnvoll.• Beispiel: Augenfarbe, IP-Adresse, Postleitzahl• Qualitative Attribute unterteilen sich in Nominal und Ordinal

– Nominal: Attribute ohne Sortierung = ≠– Ordinal: Attribute mit einer sinnhaften Sortierung < >

Quantitative (oder numerische) Attribute• Zahlen. Mathematische Operationen möglich.• Beispiel: Temperatur, Gewicht, Anzahl • Quantitative Attribute unterteilen sich in Intervall und Ratio

– Intervall: es gibt keine echte Null, Division nicht sinnvoll + -– Rational: es gibt eine echte Null, Division möglich * ÷

Data Mining 10

diskrete / kontinuierliche Attribute

Diskrete Attribute• Anzahl der Werte endlich oder abzählbar unendlich• häufig Integer als Datentyp• z.B. Postleitzahlen, Anzahl Zeichen

Kontinuierliche Attribute• Real/Fließkomma als Datentyp• wird so genau angegeben, wie das Meßinstrument es erlaubt• dadurch zwar nur endliche Anzahl von Nachkommastellen, jedoch

Begrenzung nur durch Messinstrument• z.B. Temperatur, Höhe, Gewicht

Qualitative Attribute sind immer diskretQuantitative Attribute können diskret oder kontinuierlich sein

Data Mining 11

Visualisierung von Daten

• Visualisierung von Daten ist die Anzeige von Information in einer Graphik oder Tabelle.

• Erfolgreiche Visualisierung erfordert, dass – die Daten (die Information) in ein visuelles Format

konvertiert wird.– die Beziehung zwischen den Attributen in der

Visualisierung analysiert werden kann.

• Ziel ist die Interpretation der visualisierten Information durch Personen.

Data Mining 12

Box Plot• Diagrammtyp zur Darstellung

statistischer Daten• Besteht aus Box, die 50 %

der Werte aufnimmt, und zwei Linien (Whisker), die das Rechteck verlängern

• Durchgezogene Linie: Median

• Stellt die Verteilung der Werte eines Attributs gut dar

Ausreißer

10 %

25 %

75 %

50 %

90 %

Data Mining 13

Boxplot - BeispielDer Median des Attributes A ist für Männer 2 und für Frauen 4,1. Ist dies ein großer Unterschied?

Men Women

12

34

5

Attribute A

Men Women

-20

-10

010

2030

Attribute AEvt. NEIN:Evt. JA:

Data Mining 14

Karte wissenschaftlicher Zusammenarbeit 2005-2009

visualcomplexity.com

Data Mining 15

Bsp. Zeitabhängige Grafiken:Global Pulse

• Twitter-Nachrichten von und nach Japan kurz vor und nach dem Tsunami am 11.3.2011

• Untersuchter Zeitraum: 1 Stunde

• Pink: aus Japan herausgehende Nachrichten

• Gelb: nach Japan hereingehende Nachrichten

• blog.twitter.com

Data Mining 16

schlechte Diagramme• Falls eine Information in einem

Diagramm verwendet wird, darf diese nicht zu Fehlinterpretationen führen.

• Hier: 3D, Material

Data Mining 17

Data Mining 18

Data Mining 19

ASSOZIATIONSANALYSE

Data Mining 20

Assoziationsanalyse• Die Assoziationsanalyse sucht in den Daten nach Regeln, die

angeben, wie wahrscheinlich das Auftreten eines Elements gleichzeitig mit bestimmten anderen Elementen ist.

• Beispiel: PC -> Drucker (Kauf eines PCs impliziert den Kauf eines Druckers)

• Implikation bedeutet gleichzeitiges Auftreten der Elemente. Es bedeutet jedoch keine Kausalität!– Also nicht: Weil Artikel A gekauft wird, wird auch Artikel B gekauft.– Sondern: Wenn Artikel A gekauft wird, wird mit einer bestimmten

Wahrscheinlichkeit ebenfalls B gekauft.

Data Mining 21

Assoziationsregeln• Beispielregel

– Wenn jemand einen PC kauft, dann kauft er/sie auch einen Drucker

• Konfidenz– Dieser Wert legt fest, bei welchem Prozentsatz der Datenmenge,

bei der die Voraussetzung (linke Seite) erfüllt ist, die Regel (rechte Seite) auch erfüllt ist.

– Eine Konfidenz von 80% für unsere Beispielregel sagt aus, dass vier Fünftel der Leute, die einen PC gekauft haben, auch einen Drucker dazu gekauft haben.

• Support– Dieser Wert legt fest, wie viele Datensätze überhaupt gefunden

wurden, um die Gültigkeit der Regel zu verifizieren. – Bei einem Support von 1% wäre also jeder hundertste Verkauf ein

PC zusammen mit einem Drucker.

Data Mining 22

Verkaufstransaktionen Warenkörbe

• Finde alle Assoziationsregeln L R – mit einem Support größer als minsupp und – einer Konfidenz von mindestens minconf

• Dazu sucht man zunächst die sogenannten frequent itemsets (FI), also Produktmengen, die in mindestens minsupp der Einkaufswägen/ Transaktionen enthalten sind

• Der A Priori-Algorithmus basiert auf der Erkenntnis, dass alle Teilmengen eines FI auch FIs sein müssen

VerkaufsTransaktionen

TransID

Produkt

111 Drucker111 Papier111 PC111 Toner222 PC222 Scanner333 Drucker333 Papier333 Toner444 Drucker444 PC555 Drucker555 Papier555 PC555 Scanner555 Toner

Data Mining 23

A Priori Algorithmusfür alle Produkte überprüfe ob es ein frequent itemset ist, also in mindestens minsupp Einkaufswagen enthalten ist

k:=1

iteriere solange für jeden frequent itemset Ik mit k Produkten generiere alle itemsets Ik+1 mit k+1 Produkten und Ik Ik+1

lies alle Einkäufe einmal (sequentieller Scan auf der Datenbank) und überprüfe, welche der (k+1)-elementigen itemset- Kandidaten mindestens minsupp mal vorkommen

k:=k+1

bis keine neuen frequent itemsets gefunden werden

Data Mining 24

A Priori-AlgorithmusVerkaufsTransaktionen

TransID

Produkt

111 Drucker111 Papier111 PC111 Toner222 PC222 Scanner333 Drucker333 Papier333 Toner444 Drucker444 PC555 Drucker555 Papier555 PC555 Scanner555 Toner

ZwischenergebnisseFI-Kandidat Anzahl{Drucker} 4{Papier} 3{PC} 4{Scanner} 2{Toner} 3{Drucker, Papier} 3{Drucker, PC} 3{Drucker, Scanner} {Drucker, Toner} 3{Papier, PC} 2{Papier, Scanner} {Papier, Toner} 3{PC, Scanner} {PC,Toner} 2{Scanner, Toner}

Disqua-lifiziert

Minsupp=3

Data Mining 25

A Priori-AlgorithmusVerkaufsTransaktionen

TransID

Produkt

111 Drucker111 Papier111 PC111 Toner222 PC222 Scanner333 Drucker333 Papier333 Toner444 Drucker444 PC555 Drucker555 Papier555 PC555 Scanner555 Toner

ZwischenergebnisseFI-Kandidat Anzahl{Drucker, Papier} 3{Drucker, PC} 3{Drucker, Scanner} {Drucker, Toner} 3{Papier, PC} 2{Papier, Scanner} {Papier, Toner} 3{PC, Scanner} {PC,Toner} 2{Scanner, Toner} {Drucker, Papier, PC} 2{Drucker, Papier, Toner} 3{Drucker, PC, Toner} 2{Papier, PC, Toner} 2

Data Mining 26

Ableitung von Assoziationsregeln aus den frequent itemsets

• Betrachte jeden FI (diese haben hinreichend viel support)• Bilde alle nicht-leeren Teilmengen L FI und untersuche die Regel

– L FI – L – Die Konfidenz dieser Regel berechnet sich als

• Konfidenz (L FI – L) = support(FI) / support(L)• Wenn die Konfidenz ausreicht, also > minconf ist, behalte diese

Regel• Betrachte FI = {Drucker, Papier, Toner}

– Support = 3• Regel: {Drucker} {Papier, Toner}

– Konfidenz = S({Drucker, Papier, Toner}) / S({Drucker}) = (3/5) / (4/5) = ¾ = 75 %

Data Mining 27

Erhöhung der Konfidenz• Vergrößern der linken Seite (dadurch Verkleinern der rechten Seite)

führt zur Erhöhung der Konfidenz– Formal: L L+ , R- R– Konfidenz (LR) <= C(L+ R- )

• Beispiel-Regel: {Drucker} {Papier, Toner}– Konfidenz = S({Drucker, Papier, Toner}) / S({Drucker}) = (3/5) / (4/5) = ¾ = 75%

• Beispiel-Regel: {Drucker,Papier} {Toner}– Konfidenz = S({Drucker, Papier, Toner}) / S({Drucker,Papier}) = (3/5) / (3/5) = 1 = 100%

Data Mining 28

Vorsicht bei Deutung der Konfidenz

• Personen kaufen Kaffee und Tee

• Assoziationsregel Tee Kaffee wird untersucht

• Konfidenz(Tee Kaffee) = 0.75

• Konfidenz scheint hoch zu sein, dies ist jedoch irreführend:

• Konfidenz(¬Tee Kaffee) = 0.94

Kaffee ¬ Kaffee Gesamt

Tee 15 5 20¬ Tee 75 5 80

Gesamt 90 10 100

Data Mining 29

Simpson-Paradoxon• Beispiel: Zwei Personen A und B spielen Basketball und zählen den

Erfolg ihrer Korbwürfe:

• Wer ist der bessere Spieler?• Wer ist der bessere Spieler, wenn die Wurfweite berücksichtigt wird?

A B

getroffen 10 8

nicht getroffen 10 12

Gesamt 20 20

A Bkurz weit Gesamt kurz weit Gesamt

getroffen 9 1 10 3 5 8

nicht getroffen 7 3 10 2 10 12

Gesamt 16 4 20 5 15 20

Data Mining 30

Simpson-Paradoxon

Eine dritte (evtl. versteckte) Variable bewirkt, dass eine beobachtete Beziehung zwischen zwei Variablen verschwindet oder in entgegengesetzte Richtung läuft.

Data Mining 31

Simpson-Paradoxon: Univ. BerkeleyBewerber Zugelassen

Männer 8442 44%

Frauen 4321 35%

Department Männer FrauenBewerber Zugelassen Bewerber Zugelassen

A 825 62 % 108 82 %B 560 63 % 25 68 %C 325 37 % 593 34 %D 417 33 % 357 35 %E 191 28 % 393 24 %F 272 6 % 341 7 %

Ist die Universität Berkeley in ihren Studenten-Zulassungen frauenfeindlich? (Zahlen von 1973)

Nur zwei von sechs Departments haben bei Frauen eine niedrigere Zulassungsrate.Frauen bewerben sich tendenziell häufiger in Departments mit einer niedrigen Zulassungs-Rate, Männer dagegen häufiger in Departments mit hoher Zulassungs-Rate.

Data Mining 32

Arbeitsblatt Aufgabe 3

KundenNr TransaktionsNr Einkauf

1 0001 {a,d,e}1 0024 {a,b,c,e}2 0012 {a,b,d,e}2 0031 {a,c,d,e}3 0015 {b,c,e}3 0022 {b,d,e}4 0029 {c,d}4 0040 {a,b,c}5 0033 {a,d,e}5 0038 {a,b,e}

Data Mining 33

Arbeitsblatt Aufgabe 4TransaktionsNr Einkauf

1 {Milch, Bier, Windeln}2 {Brot, Butter, Milch}3 {Milch, Windeln, Kekse}4 {Brot, Butter, Kekse}5 {Bier, Kekse, Windeln}6 {Milch, Windeln, Brot, Butter}7 {Brot, Butter, Windeln}8 {Bier, Windeln}9 {Milch, Windeln, Brot, Butter}

10 {Bier, Kekse}

Data Mining 34

Stichprobe• Eine Stichprobe ist eine kleinere Teilmenge einer Datenmenge.• Stichproben sind notwendig, wenn die Analyse der gesamten

Datenmenge zu aufwendig ist.• Stichproben müssen repräsentativ für die gesamte Datenmenge sein. • Eine Stichprobe ist dann repräsentativ, wenn sie annähernd die

selben Eigenschaften hat wie die gesamte Datenmenge.

• Beispiel zur Erzeugung einer Stichprobe:– Einfache Zufallsauswahl. Die Wahrscheinlichkeit für die Auswahl eines

Datensatzes aus der Originalmenge in die Stichprobe ist gleich.

• Je größer die Stichprobe, je kleiner Median-Abstand zwischen Stichprobe und Datenmenge: ~ (Unabhängig von Größe der Datenmenge!)

Data Mining 35

KLASSIFIKATION

Data Mining 36

Klassifikation

Apply Model

Induction

Deduction

Model

Tid Attrib1 Attrib2 Attrib3 Class

11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ?

14 No Small 95K ?

15 No Large 67K ? 10

Test Set

Learningalgorithm

Training SetTrainingsmenge

Apply Model

Induction

Deduction

Model

Tid Attrib1 Attrib2 Attrib3 Class

1 Yes Large 125K No

2 No Medium 100K No

3 No Small 70K No

4 Yes Medium 120K No

5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No

8 No Small 85K Yes

9 No Medium 75K No

10 No Small 90K Yes 10

Test Set

Learningalgorithm

Training Set

Tupelmenge

Modell: Entscheidungsbaum

Anwenden des Modells

Induktion des Entscheidungsbaums

Lern-Algorithmus, z.B. HuntKontrolle: Fehlerrate, Entropie...

Data Mining 37

Beispiele für Klassifikation

• Tumorzellen als gut- oder bösartig vorhersagen

• Kreditkarten-Transaktionen als rechtmäßig oder als Betrug klassifizieren

• Klassifikation von Adressdaten für Direktmailings

• Kategorisieren von Nachrichten in Finanzen, Wetter, Unterhaltung, Sport etc.

Data Mining 38

Klassifikationsregeln• Vorhersageattribute

– V1, V2, ..., Vn• Vorhergesagtes Attribut A• Klassifikationsregel

– P1(V1) P2(V2) ... Pn(Vn) A = c– Prädikate P1, P2, .., Pn– Konstante c

• Beispielregel (wieAlt>35) (Geschlecht =`m´) (Autotyp=`Coupé´) (Risiko=´hoch´)

Data Mining 39

Klassifikations-/Entscheidungsbaum

Data Mining 40

Klassifikations-/Entscheidungsbaum

Geschlecht

wiealt

Autotyp

geringesRisiko

m

>35

w

<=35

hohesRisiko

geringesRisiko

hohesRisiko

Coupe Van

Data Mining 41

Klassifikations-/Entscheidungsbaum

Geschlecht

wiealt

Autotyp

geringesRisiko

m

>35

w

<=35

hohesRisiko

geringesRisiko

hohesRisiko

Coupe Van

(wieAlt>35) (Geschlecht =`m´) (Autotyp=`Coupé´) (Risiko=´hoch´)

Data Mining 42

Erstellen von Entscheidungs-/ Klassifikationsbäumen

• Trainingsmenge– Große Zahl von Datensätzen, die in der Vergangenheit gesammelt

wurden– Sie dient als Grundlage für die Vorhersage von „neu ankommenden“

Objekten– ist Stichprobe: die Daten müssen repräsentativ für die gesamte

Datenmenge sein. Kann durch Zufallsauswahl gewonnen werden.– Beispiel: neuer Versicherungskunde wird gemäß dem Verhalten seiner

„Artgenossen“ eingestuft• Rekursives Partitionieren

– Fange mit einem Attribut an und spalte die Tupelmenge – Jede dieser Teilmengen wird rekursiv weiter partitioniert– Bis nur noch gleichartige Objekte in der jeweiligen Partition sind

Data Mining 43

Hunt-Algorithmus• = Top-Down-Algorithmus

• Dt ist die Menge der Trainingsdatensätze am Knoten t

• Falls die Datensätze in Dt nur einer Klasse yt angehören, dann ist t ein yt-Blatt.

• Falls die Datensätze in Dt zu mehr als einer Klasse angehören, wird ein Attribut-Test durchgeführt, welches Attribut am geeignetsten ist, um die Daten in kleinere Untermengen zu teilen.

• Dieser Algorithmus wird rekursiv auf jede Untermenge angewandt.

Hunt-Algorithmus Bsp.

Data Mining 45

Entscheidungen im Hunt-Algorithmus

• Welche Testbedingungen für Attribute sollen möglich sein?– z.B nur binäre Aufteilungen, sowohl für numerische als

auch kategorische Daten• Nach welchem Kriterium wird entschieden, welches

die beste Datenaufteilung ist?– Klassifikations-Fehlerrate, Gini-Index, Entropie

• An welcher Stelle muss die Aufteilung beendet werden?– Wenn alle Attribute gleich oder ähnlich (Kriterium ?) sind.

Data Mining 46

Testbedingungen für Attribute

• Abhängig vom Attributtyp– Kategorisch– Numerisch– Kontinuierlich

• Abhängig von der Anzahl der Aufteilungen– 2-fache Aufteilungen– mehrfache Aufteilungen

Data Mining 47

Aufteilung bei kategorischen Attributen

• Mehrfache Aufteilungen: Anzahl Teile = Anzahl unterschiedlicher Werte

• Binäre Aufteilung. Aufteilung in zwei Untermengen. Optimale Aufteilung muss gefunden werden.

PKW-TypKombi

Sport

Limousine

PKW-Typ{Sport,

Limusine} {Kombi}PKW-Typ

{Kombi, Limusine} {Sport}

Data Mining 48

Aufteilung bei kontinuierlichen Daten

TaxableIncome> 80K?

Yes No

TaxableIncome?

(i) Binary split (ii) Multi-way split

< 10K

[10K,25K) [25K,50K) [50K,80K)

> 80K

49

Wie findet man die beste Aufteilung?

• Knoten mit homogener Klassenverteilung werden bevorzugt.

• Benötigt wird ein Maß für Homogenität:

Data Mining

C0: 5C1: 5

C0: 9C1: 1

Inhomogen Homogen

Data Mining 50

Klassifikations-Fehlerrate

• p(i|t) ist der Prozentsatz der Datensätze, die an einem Knoten t zur Klasse i gehören.

• Gibt es nur zwei Klassen, so ist p(1|t) = 1 – p(0|t)

• Schreibweise ohne Angaben des Knotens: pi

• Fehlerrate: Error(t) = 1 – maxi[p(i|t)]• = Prozentsatz der falsch klassifizierten Fälle• (1 - Fehlerrate) = Genauigkeit

Data Mining 51

Gini-Index• Gini-Index ist Maß für Ungleichverteilungen• Zahl zwischen 0 und 0.5 (bei binären Klassen)• Maximum 0,5, wenn die Datensätze auf alle Klassen

gleich verteilt sind. Keine Information.• Minimum 0, wenn alle Datensätze einer Klasse

angehören. Maximum an Information. • Gini-Index an einem Knoten t für eine Menge T von

Trainingsobjekten:Gini(T) = 1 –

• Gini-Index für Partitionierung von T in T1, T2, .. Tm:Gini(T1,..Tm)=

• wird von rpart() in R verwendet

52

Beispiel Gini-Index / Fehlerrate

Data Mining

C1 0C2 6Gini=0.000

C1 1C2 5Gini=0.278

C1 2C2 4Gini=0.444

C1 3C2 3Gini=0.500

P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Gini = 1 – P(C1)2 – P(C2)2 = 1 – (0/6)2 – (6/6)2 = 0 (ideal)Fehlerrate = 1 – max(0/6 | 6/6) = 0 P(C1) = 1/6 P(C2) = 5/6Gini = 1 – (1/6)2 – (5/6)2 = 0.278Fehlerrate = 1 – max(1/6 | 5/6) = 0.167

P(C1) = 2/6 P(C2) = 4/6Gini = 1 – (2/6)2 – (4/6)2 = 0.444Fehlerrate = 1 – max(2/6 | 4/6) = 0.333

P(C1) = 3/6 P(C2) = 3/6Gini = 1 – (3/6)2 – (3/6)2 = 0.5 (schlecht)Fehlerrate = 1 – max(3/6 | 3/6) = 0.5

A?

Ja Nein

C1 C2

Data Mining 53

Vergleich Gini-Index / Fehlerrate

Data Mining 54

Aufgabe Gini-Index / FehlerrateSollte zunächst nach a1 oder zunächst nach a2 aufgeteilt werden? Berechnen Sie dazu• den Gini-Index für a1 und für a2.• die Fehlerrate für a1 und für a2.

Data Mining 55

CLUSTERING

Data Mining 56

Clustering

Alter der Fahrer

Schadens-höhe Outlier

Data Mining 57

Was ist Clustering?

Clusterabständeuntereinander maximal

Abstände innerhalb der

Cluster minimal

Finden von Gruppen von Objekten, wobei die Objekte einer Gruppe einander ähneln und sich unterscheiden von Objekten anderer Gruppen.

Data Mining 58

Beispiele für Cluster

• Biologie: Reich, Stamm, Ordnung, Klasse, Familie, Gattung...

• Klimazonen: Tropen, Subtropen, gemäßigte Zone, Subpolargebiete, Polargebiete

• Medizin: ähnliche Muster von Symptomen werden zu Krankheiten zusammengefasst

Data Mining 59

Gründe für Clustering

• Verstehen von Zusammenhängen– Dateneigenschaften und deren Verteilung

erkennen• Zusammenfassen von Daten

– Verkleinern von großen Datenmengen– dadurch schnellere Prozesse auf den Daten– „Teile und beherrsche“

Data Mining 60

Mehrdeutigkeit bei Clusterbestimmung

Wie viele Cluster sind das?

4 Cluster 2 Cluster

6 Cluster

Data Mining 61

Clustertypen: Deutlich getrennte Cluster

Ein Cluster ist eine Punktmenge, wobei jeder Punkt des Clusters näher jedem anderen Punkt des eigenen Clusters ist als zu irgendeinem Punkt eines andern Clusters.

Data Mining 62

Clustertypen: Zentriert

• Ein Cluster ist eine Punktmenge, wobei jeder Punkt des Clusters näher dem Mittelpunkt des eigenen Clusters ist als zu dem Mittelpunkt eines andern Clusters.

• Der Mittelpunkt ist häufig ein Mittelwert aus allen Punkten des Clusters.

Data Mining 63

Clustertypen: nächste Nachbarn

Ein Cluster ist eine Punktmenge, wobei jeder Punkt des Clusters näher einem oder mehreren Punkten des eigenen Clusters ist als zu irgendeinem Punkt eines andern Clusters.

Data Mining 64

Clustertypen: Dichtigkeit

• Ein Cluster ist eine dichte Punktmenge, die durch Bereiche geringer Dichte von anderen Regionen mit hoher Dichte abgegrenzt sind.

• Wird verwendet, wenn Cluster unregelmäßig oder ineinander verschlungen sind und wenn Störungen und Ausreißer vorhanden sind.

Data Mining 65

Kombination aus nächste Nachbarn und Dichtigkeit

• Bsp.: Optical Character Recognition

Data Mining 66

Clustertypen: Konzeptionell

Cluster teilen sich eine gemeinsame Eigenschaft oder repräsentieren ein spezielles Konzept.

Data Mining 67

k-Means-Algorithmus

• k-Means ist ein häufig genutzter Algorithmus zur Clusterbildung.

• Zu jedem Cluster gibt es einen Mittelpunkt. • Jeder Datenpunkt ist mit dem Cluster verbunden,

dessen Mittelpunkt am nächsten liegt.• Der Mittelpunkt wird häufig über einen Mittelwert

(engl. mean) der Datenpunkte eines Clusters gebildet. • Die Anzahl k der Cluster muss vor Ausführung des

Algorithmus festgelegt werden.

Data Mining 68

k-Means-Algorithmus

1. Zufällige Wahl der Clusterzentren

a. Jedes Objekt wird dem Cluster zugeordnet, dessen Clusterzentrum am nächsten liegt -> Cluster

b. Von diesen Clustern wird das neue Clusterzentrum berechnet

wiederhole:

bis sich die Clusterzentren nicht mehr verschieben

Data Mining 69

k-Means-Algorithmus

-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

Data Mining 70

Gleiche Datenmenge – unterschiedliche Startzentren

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0

0.5

1

1.5

2

2.5

3

x

yIteration 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

Data Mining 71

Grenzen von k-Means: unterschiedliche Clustergrößen

Original Points K-means (3 Clusters)

Data Mining 72

Grenzen von k-Means:unterschiedliche Punktdichte

Original Points K-means (3 Clusters)

Data Mining 73

alternativer Clustering-Algorithmus• Greedy Heuristik• Lese sequentiell alle Datensätze • Für den nächsten Datensatz r bestimme

– Für alle bisher existierenden Cluster denjenigen c, dessen Zentrum den kürzesten Abstand zu r hat

– Wenn Abstand(r,Zentrum(c)) <= epsilon• Füger r in c ein

– Anderenfalls lege einen neuen Cluster c` an, der zunächst nur r enthält

• Funktioniert solange ganz gut, wie die Cluster in den Hauptspeicher passen

• Hier im Gegensatz zu k-Means keine vorherige Angabe der Clusteranzahl

Data Mining 74

alternativer Clustering-Algorithmus

Original-Werte alternativer Clustering-Algorithmus