Clustering

Uwe Reichel

IPS, LMU Munchen

reichelu@phonetik.uni-muenchen.de

19. Mai 2010

Inhalt

• Grundidee

• Vektoralgebra

• Distanzmaße

• Clusterreprasentation

• Flaches Clustern– Single Pass

– Reallokation

– Kmeans

– Vorabermittlung von Clusterzentren

• Hierarchisches Clustern

• Hartes vs. Weiches Clustern

• Validierung

Inhalt 1

• Praktisches Vorgehen– Wann anwendbar?

– Behandlung von Ausreißern

– Normalisierung

– Clusterzentren

– Clustering

– Validierung

– Zusammenfassung: Parameter

Inhalt 2

Grundidee

Lernen

• Trainingsobjekte anhand von Merkmalsvektoren reprasentiert, aber noch nichtklassifiziert −→ unuberwachtes Lernen notig

• Ziel: Partitionierung der Objekte (Aufteilung in Cluster) dahingehend, dasseinander ahnliche Objekte derselben Klasse zugewiesen werden und einanderunahnliche Objekte in verschiedene Klassen fallen.

Anwendung

• Zielfunktion f(x): weise einem neuen Objekt x diejenige Klasse c zu, derenVertreter die geringste Distanz d zu x haben.

f(x) = arg minc

[d(x, c)]

Grundidee 3

Vektoralgebra

• zu klassifizierende Objekte werden als Merkmalsvektoren reprasentiert

• Vektor x der Lange n in kartesischer Koordinatenform:x = [x1, x2, . . . , xn]. xk bezeichnet jeweils den Abstand (s.u.) zwischen x unddem Ursprung des Koordinatensystems in der k-ten Dimension. Im Kontextmaschinellen Lernens bezieht sich xk auf den Wert des k − ten Attributs desObjekts x.

• Vektoren sind in Polarkoordinatenform gegeben als das 2-Tupel<Betrag, Winkel>

• |x|: Betrag des Vektors x– = seine Lange (Abstand zum Ursprung)

– = Euklid’sche Distanz zum Ursprung√∑n

k=1 x2k

Vektoralgebra 4

• ||x||: Norm des Vektors x– erfullt folgende Bedingungen:

1. Positivitat: ||x|| ≥ 0, ||x|| = 0 ↔ x = 02. Homogenitat: ||c · x|| = |c| · ||x||, c ∈ R

3. Dreiecksungleichung: ||x + y|| ≤ ||x||+ ||y||– Beispiele:∗ Euklid’sche Norm (=Euklid’sche Distanz, s.o.) ||x|| =

√∑k x2

k

∗ Betragssummennorm (=Cityblock-Distanz, s.u.) ||x|| =∑

k |xk|

Vektoralgebra 5

Distanz- und Ahnlichkeitsmaße

Allgemeines

• Was bedeutet “einander ahnliche Objekte”?

• Berechnung der Distanz/Ahnlichkeit zwischen zwei Punkten imn-dimensionalen Vektorraum, also zwischen zwei n-dimensionalen(Merkmals)vektoren

• Ein Distanz- bzw. Ahnlichkeitsmaß ist eine Metrik, d.h. es erfullt diefolgenden Bedingungen:– Positivitat, Definitheit:

d(a, b) ≥ 0; d(a, b) = 0 ↔ a = b

– Symmetrie: d(a, b) = d(b, a)– Dreiecksungleichung: d(a, c) ≤ d(a, b) + d(b, c)

• haufig ist die Distanz d von einem Ahnlichkeitsmaß s abgeleitet: d = 1− s

Distanz- und Ahnlichkeitsmaße 6

Euklid’sche Distanz

de(a, b) =√∑

i

(ai − bi)2

• kurzester Weg von a nach b

Cityblock-Distanz (Manhattan-Distanz)

dc(a, b) =∑

i

|ai − bi|

• kurzester Weg von a nach b in Manhattan (oder Mannheim)

• Addition der Abstande in jeder der n Dimensionen

Distanz- und Ahnlichkeitsmaße 7

Abbildung 1: rot, gelb, blau: Manhattan-Distanz, grun: Euklid’sche Distanz

Distanz- und Ahnlichkeitsmaße 8

Jaccard-Distanz

• Distanzmaß fur Binar-Vektoren

dj(a, b) =n01 + n10

n01 + n10 + n11

• n11 := count(i): ai = 1 ∧ bi = 1• n10 := count(i): ai = 1 ∧ bi = 0• n01 := count(i): ai = 0 ∧ bi = 1

Skalarprodukt

• nicht normalisiertes Ahnlichkeitsmaß

• d.h. wachst mit steigender Lange von a und b

ss(a, b) =∑

i

aibi

Distanz- und Ahnlichkeitsmaße 9

Cosinus-Ahnlichkeit

• normalisiertes Ahnlichkeitsmaß: misst den Winkel zwischen den Vektoren aund b

• normalisiert auf Lange von a und b (Euklid’sche Distanzen zum Ursprung)

sc(a, b) = cos(a, b)

=ss(a, b)|a| · |b|

=∑

i aibi√∑i a

2i ·

√∑i b

2i

(1)

Divergenzmaße

• erfullen eine oder mehr der oben genannten Eigenschaften einer Metrik nicht

• z.B. Relative Entropie

Distanz- und Ahnlichkeitsmaße 10

Clusterreprasentation

• notig zur Berechnung der Distanz zwischen zwei Clustern (bzw. zwischeneinem Vektor und einem Cluster)

• Single Link: Distanz zwischen den beiden ahnlichsten Punkten der beidenCluster

• Complete Link: Distanz zwischen den beiden unahnlichsten Punkten derbeiden Cluster

• Group Average Link: mittlere Distanz zwischen zwei Clustern

• Zentroid:– Mittelwertsvektor z

– Vergleich der Zentroide zweier Cluster

Clusterreprasentation 11

• Komplexitat– O(f(n)): maximal zu erwartender Aufwand (an Rechenzeit, Speicher, etc.) O,

wenn ein Datensatz der Große n mit einem Algorithmus, der f(n) Schrittebenotigt, verarbeitet wird.

– geg. n1: Anzahl der Vektoren in Cluster c1,n2: Anzahl der Vektoren in Cluster c2

– Single Link, Complete Link: O(n1 · n2) (Vergleich jedes Objekts aus c1 mitjedem aus c2)

– Group Average Link: O((n1 · n2) + (n1 + n2)) (wie oben + Berechnung desMittelwerts)1

– Zentroid: O(n1 + n2) (Berechnung der Zentroide aus c1 und c2)

1Konstanten sind hier weggelassen.

Clusterreprasentation 12

Flaches Clustern• Entstandene Cluster werden nicht weiter zusammengefasst oder unterteilt.

Single PassX ← Menge der zu clusternden Objekte

s ← Schwellwert fur max. erlaubte Distanz

init: erstes Cluster mit einem zufallig gewahlten x ∈ X als Inhalt

foreach x ∈ X

c ← ahnlichstes Cluster

if d(c,x) ≤ s

c ← [c, x]

update Reprasentation(c)

endifif x noch nicht zugeordnet

lege ein neues Cluster mit dem Element x an

endifendforeach

Abbildung 2: Einfache Single-Pass-Methode fur hartes Clustering: einmaliges Durchlaufen der zu

clusternden Objekte.

Flaches Clustern 13

Reallokation

• Wahrend der fortschreitenden Aktualisierung der Clusterreprasentationenkommt es i.d.R. dazu, dass bereits zugeordnete Objekte fremden Clusternahnlicher werden als dem eigenen.

• Losung: Wiederhole das Durchlaufen der Objekte mit Neuzuordnung(Reallokation) jedes Objekts zum ahnlichsten Cluster, solange bis kein Objektmehr das Cluster wechselt, die Clusterreprasentationen also stabil sind.

Kmeans

• Algorithmus fur hartes, flaches Clustern (s.u.)

• zu Beginn werden k Clusterzentren festgelegt (Reprasentation: Zentroid)

• dies geschieht entweder durch zufallige Auswahl von k Vektoren, oder durchVorabermittlung potentieller Clusterzentren (s.u.)

Flaches Clustern 14

• alle anderen Punkte werden sukzessive einem der k Cluster zugewiesen, wobeidie Clusterreprasentation nach jeder Zuweisung neu ermittelt wird.

• Objekte werden solange realloziert, bis die Cluster stabil sind.

• anders als beim oben beschriebenen Single-Pass-Verfahren werden nach derInitialisierung keine neuen Cluster mehr angelegt.

X ← Menge der zu clusternden Objekte

k ← Anzahl der zu gewinnenden Cluster

init: bestimme k Clusterzentren

until alle Cluster stabil

foreach x ∈ X

c ← ahnlichstes Cluster

c ← [c, x]

update Clusterzentrum(c)

endforeachenduntil

Abbildung 3: Kmeans.

Flaches Clustern 15

Vorabermittlung von Clusterzentren

• z.B. mittels Mountain Clustering oder subtraktivem Clustern

• subtraktives Clustern:– Clusterzentren: Punkte x mit hoher Nachbarn-Dichte

– Nachbarn-Dichte Di fur Punkt xi in Abhangigkeit der Abstande zu allenbenachbarten Punkten xj innerhalb eines Unkreises mit Radius ra:

Di =∑

j

e−||xi−xj||(ra/2)2 (2)

– Di nimmt umso hohere Werte an, je großer die Anzahl der xj, die sichinnerhalb des durch ra festgelegten Umkreises befinden, und je kleiner dieDistanzen zwischen xi und diesen xj.

Flaches Clustern 16

– Der Punkt xcz mit der hochsten Dichte Dcz wird als Clusterzentrumgewahlt und entfernt.

– Die Dk aller in einem Umkreis mit Radius rb verbleibenden Punkte xk

werden folgendermaßen neu berechnet:

Dk = Dk −Dcz · e−||xk−xcz||

(rb/2)2 (3)

– Dieses Update fuhrt dazu, dass die Dichte eines Punktes xk umso mehrreduziert wird, je naher er am gerade ermittelten Clusterzentrum liegt.Dadurch wird verhindert, dass Zentren zu nah beieinander liegen.

– durch iteratives Anwenden der Gleichungen 2 und 3 werden solangeClusterzentren erzeugt, bis ein Abbruchkriterium erfullt ist.

– Abbruchkriterium(geg. Iterationsschritt j und festzulegenden Schwellwert c): z.B.Dj

cz/D1cz < c, d.h. das aktuell gefundene Dichtemaximum ist gegenuber

dem zu Beginn gefundenen klein.

• beim Mountain Clustering wird ein Gitter in den Vektorraum gelegt und diedie Nachbarn-Dichte anstatt fur gegebene Datenpunkte fur dieGitterschnittpunkte ermittelt (rechenaufwandiger).

Flaches Clustern 17

Hierarchisches Clustern

Bottom-up

• sukzessive Verbindung von Objekt-, bzw. Clusterpaaren, bis alle Objekte ineinem Cluster (auf der obersten Hierarchieebene) enthalten sind

Top-Down

• Ausgehend von einem Cluster werden die Objekte rekursiv in Subclusterpartitioniert2 , bis sie alle voneinander getrennt sind.

2rekursiv: Anwendung eines Verfahrens V auf das Ergebnis von V . Hier: Partitioniere entstandene Subclustererneut in Subcluster bis keine weitere Partitionierung mehr moglich ist.

Hierarchisches Clustern 18

Dendrogramm

Abbildung 4: Dendrogramm

• Kantenlange: Distanzen zwischen den Objekten im Teilbaum unter der Kante

Hierarchisches Clustern 19

• Pruning: Bestimmung der Hierarchieebenen, ab denen eine feinere Einteilungder Objekte nicht mehr gerechtfertigt ist: Inkonsistenz-Koeffizient– fur jede Kante: Messung der Distanzen zwischen den Objekte in dem

Teilbaum unterhalb der Kante relativ zur durchschnittlichen Distanz in allenTeilbaumen, die von derselben Hierarchieebene abgehen

– je hoher die Werte, die der Koeffizient annimmt, desto unahnlicher sind sichdie Objekte in dem Teilbaum unterhalb der Kante und desto eher sind siesomit noch weiter partitionierbar

– Unterschreitet der Koeffizient einen festzulegenden Schwellwert, so werden dieObjekte im zugehorigen Teilbaum zu einem Cluster zusammengefasst.

Hierarchisches Clustern 20

Hartes vs. Weiches Clustern

• beim harten Clustern wird ein Objekt x genau einem Cluster zugeordnet

• alle bislang vorgestellten Methoden sind Verfahren fur hartes Clustering

• beim weichen Clustern kann x mehreren Clustern zugeordnet werden

• Fur den oben angegebenen Single-Pass-Algorithmus ergeben sich somitfolgende Anderungen:

Hartes vs. Weiches Clustern 21

X ← Menge der zu clusternden Objekte

s ← Schwellwert fur max. erlaubte Distanz

init: erstes Cluster mit einem zufallig gewahltem Objekt als Inhalt

foreach x ∈ X

foreach Cluster c

if d(c,x) ≤ s

c ← [c, x]

update Reprasentation(c)

endifendforeachif x noch nicht zugeordnet

lege ein neues Cluster mit dem Element x an

endifendforeach

Abbildung 5: Single-Pass-Methode fur weiches Clustering.

Fuzzy-Clustering:

• Jedem Objekt x wird fur jede Clusterzugehorigkeit noch ein Wahrheitswert wzwischen 0 und 1 zugewiesen, der die Starke der Objektzugehorigkeit angibt.

• z.B. w(x ∈ c1) = 0.3, w(x ∈ c2) = 0.7. x gehort also starker zu c2 als zu c1.

Hartes vs. Weiches Clustern 22

Validierung

Gutekriterien

• Kompaktheit

• Separierbarkeit

• Anpassungsgute des Dendrogramms

Validierung 23

Validierungsmaße

• Dunn-Index DI (fur hartes Clustering, nicht-hierarchische Clusterergebnisse)

DI =arg mini,j

[d(ci, cj)

]arg maxk

[diam(ck)

],d(ci, cj): Single-Link-Distanz zwischen Clustern ci und cj

diam(ck): Durchmesser des Clusters ck = Distanz der am weitestenvoneinander entfernten Punkte in ck

– gesucht wird also das am schlechtesten separierbare Clusterpaar ci, cj

(Zahler) und das am wenigsten kompakte Cluster ck (Nenner)

– je separierbarer das Paar ci, cj und je kompakter ck, je besser also dasClusteringergebnis, desto hoher DI

Validierung 24

• Cophenet Korrelationskoeffizient C (fur hartes Clustering, hierarchischeClusterergebnisse)– misst die Korrelation zwischen der Distanz zweier Objekte xi und xj im

Dendrogramm und ihrer tatsachlichen Distanz, misst also die Prazision, mitder das Dendrogramm die tatsachlichen Verhaltnisse wiederspiegelt

– tatsachliche Distanz: Euklid’sche Distanz d(i, j) im Vektorraum

– Distanz im Dendrogramm: Hierarchiebene t(i, j) im Dendrogramm, in der xi

und xj zusammengefasst werden

C =

∑i,j(d(i, j)− µd)(t(i, j)− µt)√∑

i,j(d(i, j)− µd)2 ·∑

i,j(t(i, j)− µt)2,

µd: arithmetisches Mittel aller d(i, j)µt: arithmetisches Mittel aller t(i, j)

– c nimmt Werte zwischen 0 und 1 an, je hoher, desto besser die Anpassung desDendrogramms an die Daten.

Validierung 25

Praktisches Vorgehen

Wann anwendbar?

• wenn unuberwachtes Lernen notig ist

• wenn folgende Variablentypen vorliegen– unabhangige Variablen: kontinuierlich oder kategorial

– abhangige Variable: kategorial

Praktisches Vorgehen 26

Behandlung von Ausreißern

• Ausreißer konnen das Clusterergebnis stark verzerren (v.a. bei Kmeans) undsollten daher vorab aus den Daten entfernt werden.

• Identifizierung unter Annahme normalverteilter Daten– Test auf Normalverteilung multivariater Daten: z.B. Royston Test

– univariat (Merkmalsvektorlange = 1): Grubb-Test,Chauvenet-Kriterium, Peirce-Kriterium

– multivariat (Merkmalsvektorlange > 1): z.B. Wilk-Methode, getrennteAnwendung univariater Tests fur jede Dimension

– Ausreißer sind diejenigen Vektoren, die sich an den außersten Randern derNormalverteilung (multivariat: der mehrdimensionalen Gaußglocke)befinden, also diejenigen Vektoren, die mit einer sehr geringenIrrtumswahrscheinlichkeit als nicht zugehorig betrachtet werden konnen.

– bei Test anzugeben: Signifikanzniveau (hochste akzeptierteIrrtumswahrscheinlichkeit) α

– α = 0.05 bedeutet: identifiziere nur Vektoren als Ausreißer, bei denen eineIrrtumswahrscheinlichkeit von maximal 5 % besteht. Das gilt fur Vektoren,die mindestens zwei Standardabweichungen vom Zentroid entfernt liegen.

Praktisches Vorgehen 27

• Identifizierung ohne Annahme einer bestimmten Verteilung– univariat: Ausreißer := Wert > oberes Quartil +1.5 Interquartilabstande ∨

< unteres Quartil −1.5 Interquartilabstande

Abbildung 6: Boxplot. Waagrechte Linien von unten nach oben: Minimum, unteres Quartil

(Wert großer-gleich 25% der Messwerte), Median (≥ 50%), oberes Quartil (≥ 75%),

Maximum. Interquartilabstand = oberes Quartil - unteres Quartil.

– multivariat: getrennte Anwendung univariater verteilungsfreier Tests furjede Dimension

Praktisches Vorgehen 28

Normalisierung

• Attribute mit einem großen Definitionsbereich gehen ungleich starker in dieAbstandsmessung ein als Attribute mit einem kleinen Definitionsbereich (vgl.Folien zu KNN)

• Normalisierung der Werte, um Vergleichbarkeit zu gewahrleisten

• z-Transformation: ∀x ∈ X : x −→ x−mean(X)

std(X)fuhrt zu

Standardnormalverteilung mit Mittelwert 0 und Standardabweichung 1.

• Normalisierung auf Intervall [0 1]: ∀x ∈ X : x −→ x−min(X)max(X)−min(X)

Bestimmung von Clusterzentren

• z.B. mittels subtraktiven Clusterns

• um zu verhindern, dass Clusterzentren zu nah beieinander liegen wird in denGleichungen 2 und 3 rb großer als ra gesetzt, i.d.R. rb = 1.5 · ra

Praktisches Vorgehen 29

Clustering

• Methoden– Kmeans: niedrigste Komplexitat O(n), aber anfallig gegenuber Ausreißern

• festzulegende Parameter– bei Kmeans: u.a. Anzahl der Cluster

– bei subtraktivem Clustern: u.a. ra und rb

– bei hierarchischem Clustern: u.a. Schwellwert des Inkonsistenzkoeffizienten

– dazu: Distanzmaß, Clusterreprasentation

• Clusterreprasentationen:– Single link fuhrt zu langgezogenen Clustern

– Complete link fuhrt zu kompakten Clustern

– Zentroid-Clustering am wenigsten rechenaufwandig

Praktisches Vorgehen 30

Validierung

• Clusteringalgorithmen garantieren nur lokale Optima

• optimale Parameterkombinationen (s.o.) sind i.d.R. nicht bekannt

• aus diesen beiden Grunden sind Wiederholungen mit unterschiedlichenInitialisierungen notig

• Ziel: finde das bestvalidierte Modell

Zusammenfassung: einzustellende Parameter

• Features

• Clusterverfahren

• Anzahl der Cluster bzw. Distanzschwellwerte

• Clusterinitialisierung

• Clusterreprasentation

• Validierungsmaß

• Darbietungsreihenfolge der Objekte

Praktisches Vorgehen 31