View
85
Download
1
Category
Preview:
DESCRIPTION
Wie Gruppiere ich meine Daten? Wie finde ich heraus, welche Personen, Sensorwerte, Koordinaten zusammen gehören? Dieser Vortrag behandelt vier einfache Algorithmen, die darauf Antwort geben. Im Rahmen von Jugend Hackt http://jugendhackt.de/ .
Citation preview
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