Universität Potsdam Institut für Informatik

Lehrstuhl Maschinelles Lernen

Maschinelles Lernen II

Clustering 2

Christoph Sawade/Niels Landwehr

Tobias Scheffer

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Überblick

Zuletzt:

K-means

Mixture of Gaussians

Hierarchisches Clustern

Bottom Up

Top Down

Graphen-basiertes Clustern

Ähnlichkeitsgraph

Minimaler Schnitt

2

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Clustern

Geg.

Objekte

Distanzfunktion oder

Ähnlichkeitsfunktion

Erwartete Clusteranzahl

Ziel: Partition , wobei mit…

hoher intra-cluster-Ähnlichkeit

niedriger inter-cluster-Ähnlichkeit

3

1 nV x ,...,x

k

ij i jw sim x ,x 0

1 kP ,...Pi j i

i 1...n

P P , P V

i jdist x ,x 0

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Inter-Cluster Metriken

Einfacher Abstand

Kompletter Abstand

Durchschnittsabstand

Abstand der Zentroide

4

jmin i j v P,w Pd P ,P min dist v,w

i jmax i j v P ,w Pd P ,P max dist v,w

i

cent i j

v P v Pji j

1 1d P ,P dist v, v

P P

i

mean i j

v P w Pji j

1d P ,P dist v,w

P P

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Optimales Clustering

Berechnung des globalen Optimum bzgl. inter- und

intra-cluster-Ähnlichkeit ist nicht effizient

Vgl. k-means:

Bestimmung eines lokalen Optimums

EM-Algorithmus (siehe letzte VL)

Heuristik (Hierarchisches Clustering)

Relaxation (Spectral Clustering)

5

n k2

r ij i j

i 1 j 1

min r x

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Überblick

Hierarchisches Clustern

Bottom Up

Top Down

Graphen-basiertes Clustern

Ähnlichkeitsgraph

Minimaler Schnitt

6

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Hierarchisches Clustern

Bottom Up

Agglomerative Nesting (Agnes)

Top Down

Divisive Analysis (Diana)

7

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Hierarchisches Clustern Agnes (Algorithmus)

Geg.: Objekte , Inter-Cluster Metrik

Setze

Solange unterschiedliche Cluster existieren

berechne min. Distanz über alle

Setze

Liefere zurück

8

V d

0C x | x V

v w v w

v,w i v,ws, t argmin d c ,c ; D min d c ,c

v w

i 1c ,c C

v s t

iC c | v s, t c c

0 1C ,C ,...

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Hierarchisches Clustern Agglomerative Coefficient

Sei , wobei das Cluster ist, mit dem

im i-ten Schritt verschmolzen wurde

Agglomerative Coefficient :

Ein Maß für die Qualität eines Clusterings

Nicht geeignet um Datensätze unterschiedlicher

Größe zu vergleichen

9

v s

i kC c | v s, t c x

s

k km d c , x sc kx

n

i

i 1 final

1 mAC 1 0,1

n D

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Überblick

Hierarchisches Clustern

Bottom Up

Top Down

Graphen-basiertes Clustern

Ähnlichkeitsgraph

Minimaler Schnitt

10

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Hierarchisches Clustern Diana

Bottom up: alle möglichen Fusionen werden

betrachtet

Top down: mögliche Splits

11

n

2

n 12 1

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Hierarchisches Clustern Diana (Algorithmus)

Geg.: Objekte , Inter-Cluster Metrik

Setze

Solange mehr-elementige Cluster existieren

Bestimme Cluster mit höchsten Durchmesser

Bestimme unähnlichstes Element

und setze

Solange , wobei

Setze

Liefere zurück 12

V d

0C V

v cs argmax vd v,c

i 1c C s,t cc argmax max d s, t

c s

v c c

max D v 0

c c t

v cc

t argmax D v

0 1C ,C ,...

i i 1C C c c c c

D v d v,c cvc d ,

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Hierarchisches Clustern Divisive Coefficient

Sei , der Durchmesser des Cluster aus dem das

Objekt zu letzt herausgelöst wurde (bis es

einzeln war)

Divisive Coefficient:

Ein Maß für die Qualität eines Clusterings

Nicht geeignet um Datensätze unterschiedlicher

Größe zu vergleichen

13

n

i

i 1

1DC dia

n

idia

iv

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Überblick

Hierarchisches Clustern

Bottom Up

Top Down

Graphen-basiertes Clustern

Ähnlichkeitsgraph

Minimaler Schnitt

14

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Graphen-basiertes Clustern Ähnlichkeitsgraph

Ähnlichkeit zwischen Datenpunkten

(Knoten) bilden gewichtete Kanten:

15

V

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Graphen-basiertes Clustern Ähnlichkeitsgraph

Ähnlichkeit zwischen Datenpunkten

(Knoten) bilden gewichtete Kanten:

Vollständiger Graph: Kantengewichte = Ähnlichkeit

knn-Graph: Kante, wenn

Knoten i (oder j) einer der k

nächsten Nachbarn von j (bzw. i)

-Nachbarschaftsgraph:

Kante, wenn

16

V

i jdist v ,v

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Graphen-basiertes Clustern Definitionen

Gewichtete Adjazenzmatrix

Knotengrad-Matrix

Laplace-Matrix

unnormalisiert

Symmetrisch normalisiert

17

1

1

0

0

n

i ij

j

n

d

d w

d

D

11 1n

1n nn

w w

w w

W

un

1/2 1/2

sym

L D W

L I D WD

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Beobachtung

Zusammenhängende Teilgraphen…

entspricht Anzahl Eigenwerte von L mit Wert 0.

zugehörige (unnormierte) Eigenvektoren enthalten

Indikatorvektoren der Teilgraphen.

Erkenntnis für schwach zusammenhäng. Teilgraphen?

18

1 2

3

1

3

2

3

2

1

0

f 1,...1,0,...0,0,...0 /

f 0,...0,1,.

#Bsp. in C

#Bsp. in..1,0,...0 /

f 0,...0,0,...0,1,.

C

#Bsp...1 n C/ i

n

2T T T

un i, j i j

i, j 1

1f L f f Df f Wf w f f

2

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Betrachten Ähnlichkeitsgraphen mit zwei

unterschiedlichen ausgezeichneten Knoten

Ein s-t-Schnitt ist eine Partitionierung der Knoten,

wobei und mit

Minimaler Schnitt Spezialfall k=2

19

s P t P V P

st

s, t V

i j

s,t

ij

v P,v P

s P,t P

Cut (P) w

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Der minimale s-t-Schnitt

ist

Problem ist in polynomieller

Laufzeit lösbar (Ford/Fulkerson; Dinic)

Der minimale Schnitt ist der minimale

s-t-Schnitt über alle s-t-Schnitte:

Problem ist in polynomieller Laufzeit lösbar

Minimaler Schnitt Spezialfall k=2

20

2nm n logn

* s,t

P VP argmin Cut (P)s

t

i jijv P,v P

Cut(P) w

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Minimaler Schnitt Balanzierung

Problem: MinCut-Lösung separiert häufig einzelne

Knoten

21

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Minimaler Schnitt Balanzierung

Problem: MinCut-Lösung separiert häufig einzelne

Knoten

Balanzierung:

wobei Anzahl der Knoten in

, wobei

Balanziertes MinCut-Problem ist NP-hart

22

Cut(P)

RatioCut PP

Cut(P)

Ncut Pvol(P)

i

i

v P

vol P d

P P

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Minimaler Schnitt Balanzierung

Lemma 1: Sei

dann gilt

Lemma 2: Sei

dann gilt

23

T

unV RatioCut P f L f

T

symvol(V) NCut P f L f

i

i

P / P , wenn v P

P / P , sons

f

t

i

i

vol P / vol P , wenn v P

vol P / vol P , sonst

f

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering (unnormalisiert) Relaxation

RatioCut

24

n nT 2

i iP V

i 1 i 1

minf Lf , wobei f 0, f n

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering (unnormalisiert) Relaxation

RatioCut

25

n nT 2

i iP V

i 1 i 1

minf Lf , wobei f 0, f n

kann nur 2 Werte annehmen if

i

i

P / P , wenn v P

P / P , sons

f

t

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering (unnormalisiert) Relaxation

RatioCut

(Unnormalisiertes) Spectral-Clustering

26

n nT 2

i iP V

i 1 i 1

minf Lf , wobei f 0, f n

n

n nT 2

i if

i 1 i 1

minf Lf , wobei f 0, f n

NP-hart

Eigenwertproblem

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering (unnormalisiert) Relaxation

RatioCut

(Unnormalisiertes) Spectral-Clustering

Diskretisierung:

27

n nT 2

i iP V

i 1 i 1

minf Lf , wobei f 0, f n

n

n nT 2

i if

i 1 i 1

minf Lf , wobei f 0, f n

isign(f )

NP-hart

Eigenwertproblem

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering (unnormalisiert) Verallgemeinerung auf k>2

28

1 k i

i 1...k

1Cut(P ,...P ) Cut P

2

1 k i

i 1...k

1RatioCut(P ,...P ) RatioCut P

2

1 k i

i 1...k

1Ncut(P ,...P ) Ncut P

2

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering (unnormalisiert) Verallgemeinerung auf k>2

29

1 k i

i 1...k

1Cut(P ,...P ) Cut P

2

1 k i

i 1...k

1RatioCut(P ,...P ) RatioCut P

2

1 k i

i 1...k

1Ncut(P ,...P ) Ncut P

2

j i j

ij

j

1/ P , wenn v P

1/ P , sonst

F

i

i

P / P , wenn v P

P / P , sons

f

t

T

1 kRatioCut(P ,...P ) Tr F LF

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering (unnormalisiert) Relaxierung (k>2)

RatioCut

(Unnormalisiertes) Spectral-Clustering

30

1 k

T T

P ,...,Pmin Tr F LF , wobei F F I

NP-hart

Eigenwertproblem

n k

T T

F

min Tr F LF , wobei F F I

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering (unnormalisiert) Relaxierung (k>2)

RatioCut

(Unnormalisiertes) Spectral-Clustering

Diskretisierung: k-means auf

31

1 k

T T

P ,...,Pmin Tr F LF , wobei F F I

NP-hart

Eigenwertproblem

n k

T T

F

min Tr F LF , wobei F F I

iF

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering Beispiel

Daten: Mixture of gaussian

32

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering Beispiel

sim: RBF mit

Eigenwerte der zugehörigen

Laplacematrix (fully connected Graph)

33

1

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering Beispiel

34

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Spectral-Clustering (unnormalisiert) Algorithmus

Geg.: Adjazenzmatrix , Clusteranzahl

Berechne zugehörige Laplacematrix

Berechne die kleinsten Eigenvektoren

von

Setze

Berechne Cluster aus Datenpunkte

Liefere zurück

35

n n

0W

k

unL

k

unL

n

iu

1

1 k

n

x | |

u ... u

x | |

jC

ixjC

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Approximationsgüte Balanzierte Schnitte

Polynomieller Algorithmus mit konstanter

Approximationsgüte existiert nicht

Cockroach Graph (Guattery & Miller 1998)

36

| P | | P | 2k

cut P,P 2

optimal

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Approximationsgüte Balanzierte Schnitte

Polynomieller Algorithmus mit konstanter

Approximationsgüte existiert nicht

Cockroach Graph (Guattery & Miller 1998)

37

| P | | P | 2k

cut P,P k

Un. Spectral Clustering

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Anmerkungen

Ncut führt zum verallgemeinerten Eigenvektorproblem

(norm. Spectral clustering)

Probabilistische Motivation…

38

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Anmerkungen

Ncut führt zum verallgemeinerten Eigenvektorproblem

(norm. Spectral clustering)

Probabilistische Motivation…

Page-Rank: Sortieren der Beispiele nach

entsprechendem Eintrag des größten Eigenvektors

(bzgl. Eigenwert)

Quelle:

U. von Luxburg: A Tutorial on Spectral Clustering; 2007

39

Saw

ade/L

andw

ehr/S

cheffe

r, Maschin

elle

s L

ern

en II

Evaluation von Clusterings

Unüberwacht (nur heuristisch):

z.B. Agglomerativer Koeffizient, Divisive Coefficient

Überwacht: Evaluationsdaten gegeben

Relative Entropie

Durchschnittliches F-measure / Recall / Precision

Rand-Index

40

* *

c '

* *

2*c

' H

c c ' c1

Hc '

c 'n

c 'c '

c ' c 'loH log

g

* *

1 1

* *

i j i

l

j

k,C ,

x i, j : x C x C x i, j :

R C , , C , C

x, | x x C x C, x, x, | x, x,

n

2

*