1
Clustering
Gruppieren von DatenpunktenProgrammiererversion
Nicco Kunzmann nicco @gmail.comJugend Hackt 2014
kunzmann
2
Clustering
Gruppieren von DatenpunktenProgrammiererversion
Nicco Kunzmann nicco @gmail.comJugend Hackt 2014
kunzmann
3
Clustering
Gruppieren von DatenpunktenProgrammiererversion
Nicco Kunzmann nicco @gmail.comJugend Hackt 2014
kunzmann
4
● Datamining
– Unsupervised Learning● Clustering
● Statistik● Information Retrieval (Film: „Brazil“)
5
Daten
Name Alter vegetarier Geschwister
Benni 12.4 ja 1
Horst 14.2 nein 0
Irmel 16.0 nein 5
Lichtintensität
1
2
12
3
21
21
2
31
66
21
3
12
1
3
1
3
21
3
21
11
23
21
38
21
113
4 Features
6
Abstand
Wer gehört zusammen?
7
Abstand
8
Abstand
25
3
2
?
1 0
Was ist sinnvoll?
9
Abstand
Euklidischer Abstand
10
Abstand
Manhattan
11
Abstand
Manhattan
Stellt euch an dieser Stelle ein 10-Dimensionales Bild vor.
A ja ja ja ja X ja ja ja ja ja
B X ja ja ja X ja X ja X ja
C X X X X X X X X X X
12
Abstand
Maximum
13
Abstand
Cosinus
14
Abstand
Es gibt auch noch - Pearson correlation für Lineare Abhängigkeit- Jaccard similarity für Mengen (Buchstaben)
15
Algorithmen
● Single Link● Complete Link● K-Means● Mean Shift● Connected Components● Gaussian Mixture Model● DB-Scan
16
Single Link & Complete Link
➢ Jeder Punkt in einen neuen Cluster➢ Bis es wenig Cluster gibt, tue:
➢ Finde die beiden Cluster mit min. dist(c1, c2)➢ Erzeuge einen neuen Cluster aus c1 + c2
Single Link: dist(c1, c2) = min({dist(x1, x2) | x1 c1, x2 c2})∈ ∈Complete Link:dist(c1, c2) = max({dist(x1, x2) | x1 c1, x2 c2})∈ ∈
17
Single Link & Complete Link
18
Single Link
19
Complete Link
20
Complete Link & Single Link
Problem: Ich will 2 Cluster
21
K-Means
22
K-Means
23
K-Means
24
K-Means
25
K-Means
26
K-Means
➢ Platziere eine Anzahl an Mittelpunkten zufällig➢ Bis sich nichts ändert, tue:
➢ Erzeuge für jeden Mittelpunkt einen leeren Cluster
➢ Füge die Punkte in den Cluster vom nächstliegendsten Mittelpunkt
➢ Bilde die Mittelpunkte aus den Clustern
27
K-Means
● Probleme
28
Mean-Shift
Row 1 Row 2 Row 3 Row 40
2
4
6
8
10
12
Column 1
Column 2
Column 3
29
Mean-Shift
für Maxima & Minima
30
Mean-Shift
➢ Verteile zufällig Punkte➢ Solange sich was ändert, tue:
➢ Für jeden Mittelpunkt p, tue:➢ p := Durchschnitt aus allen Daten nahe p
Gewichteter Durchschnitt für Normalverteilte Daten
31
Mean-Shift
● Probleme
32
Algorithmen
● Single Link● Complete Link● K-Means● Mean Shift● Connected Components (für Bilder)● Gaussian Mixture Model (besseres K-Means)● DB-Scan
33
Featureanpassung
Beispiel: Lichtsensorwerte:
– Weiß: 1-6– Grau: 7-100– Schwarz: 101 - 10000
Feature := log(Lichtsensorwert)
Daten anpassen, da Algorithmen doofe Annahmen treffen.
34
Implementieren
● Implementierung := Algorithmus + Featureauswahl + Featureanpassung + Abstandsfunktion + Leere Cluster behandeln
35
Quellen
● Vorlesung Datamining 2013/14 am HPI– I. H. Witten, E. Frank, M. A. Hall: Data Mining - Practical
Machine Learning Tools and Techniques (Chapters 1 – 6)
– C. Bishop: Pattern Recognition and Machine Learning (Chapters 1 – 4, 8, 9)
– T. M. Mitchell: Machine Learning (Chapters 3 – 6, 8, 10)
– P. Flach: Machine Learning – The Art and Science of Algorithms that make Sense of Data (Chapters 1 – 3, 5 – 11)
– D. J. C. MacKay: Information Theory, Inference and Learning Algorithms (Chapters 1 – 6)
Recommended
