Universität PotsdamInstitut für Informatik

Lehrstuhl Maschinelles Lernen

Maschinelles Lernen IIClustering 2

Christoph Sawade/Niels LandwehrTobias Scheffer

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Überblick

Zuletzt: K-means Mixture of Gaussians

Hierarchisches Clustern Bottom Up Top Down

Graphen-basiertes Clustern Ähnlichkeitsgraph Minimaler Schnitt

2

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

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 ,...P i j ii 1...n

P P , P V=

∩ = ∅ =

( )i jdist x ,x 0≥

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

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 jv P v Pji j

1 1d P ,P dist v, vP P∈ ∈

=

∑ ∑

( ) ( )i

mean i jv P w Pji j

1d P ,P dist v,wP P ∈ ∈

= ∑ ∑

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

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 k 2

r ij i ji 1 j 1

min r x= =

− µ∑∑

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Überblick

Hierarchisches Clustern Bottom Up Top Down

Graphen-basiertes Clustern Ähnlichkeitsgraph Minimaler Schnitt

6

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Hierarchisches Clustern

Bottom Up Agglomerative Nesting (Agnes)

Top Down Divisive Analysis (Diana)

7

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Hierarchisches ClusternAgnes (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 wv,w i v,ws, t arg min d c ,c ; D min d c ,c= =

v wi 1c ,c C −∈

{ } { }v s tiC c | v s, t c c= ∀ ≠ ∪ ∪

0 1C ,C ,...

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Hierarchisches ClusternAgglomerative 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 si kC c | v s, t c x= ∀ ≠ ∪ ∪

{ }( )sk km d c , x= sc kx

[ ]n

i

i 1 final

1 mAC 1 0,1n D=

= − ∈

∑

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Überblick

Hierarchisches Clustern Bottom Up Top Down

Graphen-basiertes Clustern Ähnlichkeitsgraph Minimaler Schnitt

10

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Hierarchisches ClusternDiana

Bottom up: alle möglichen Fusionen werden betrachtet

Top down: mögliche Splits

11

n2

n 12 1− −

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Hierarchisches ClusternDiana (Algorithmus)

Geg.: Objekte , Inter-Cluster Metrik Setze Solange mehr-elementige Cluster existieren

Bestimme Cluster mit höchsten Durchmesser

Bestimme unähnlichstes Elementund setze

Solange , wobei

Setze Liefere zurück

12

V d

{ }0C V=

{ }( )v cs arg max vd v,c∈=

( )i 1c C s, t cc arg max max d s, t−∈ ∈=

{ }c s=

( )v c cmax D v 0∈

>

{ }c c t= ∪( )v cct arg max D v

∈=

0 1C ,C ,...

{ }( ) { } { }i i 1C C c c c c−= ∪ ∪

( ) ( ) ( )D v d v,c cvc d ,= −

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Hierarchisches ClusternDivisive 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

ii 1

1DC dian =

= ∑

idiaiv

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Überblick

Hierarchisches Clustern Bottom Up Top Down

Graphen-basiertes Clustern Ähnlichkeitsgraph Minimaler Schnitt

14

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Graphen-basiertes ClusternÄhnlichkeitsgraph

Ähnlichkeit zwischen Datenpunkten (Knoten) bilden gewichtete Kanten:

15

V

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

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 knächsten Nachbarn von j (bzw. i)

-Nachbarschaftsgraph:Kante, wenn

16

V

ε( )i jdist v ,v < ε

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Graphen-basiertes Clustern Definitionen

Gewichtete Adjazenzmatrix

Knotengrad-Matrix

Laplace-Matrix unnormalisiert Symmetrisch normalisiert

17

1

1

0

0 =

= =

∑

n

i ijj

n

dd w

dD

11 1n

1n nn

w w

w wW

=

un1/ 2 1/ 2

sym

L D W

L I D WD− −

= −

= −

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

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

2

3

0u 1,...1,0,...0,0,...0

u 0,...0,1,...1,0,...0

u 0,...0,0,...0,1,...1

λ = λ = λ =

=

=

=

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Betrachten Ähnlichkeitsgraphen mit zwei unterschiedlichen ausgezeichneten Knoten

Ein s-t-Schnitt ist eine Partitionierung der Knoten, wobei und mit

Minimaler SchnittSpezialfall k=2

19

s P∈ t P V P∈ =

s t

s, t V∈

i j

s, tij

v P,v Ps P,t P

Cut (P) w∈ ∈∈ ∈

= ∑

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Der minimale s-t-Schnittist Problem ist in polynomieller

Laufzeit lösbar (Ford/Fulkerson; Dinic)

Der minimale Schnitt ist der minimales-t-Schnitt über alle s-t-Schnitte: Problem ist in polynomieller Laufzeit lösbar

Minimaler SchnittSpezialfall k=2

20

( )2nm n log n+

* s, tP VP arg min Cut (P)⊂=

s t

i jijv P,v P

Cut(P) w∈ ∈

= ∑

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Minimaler SchnittBalanzierung

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

21

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Minimaler SchnittBalanzierung

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

iv P

vol P d∈

= ∑

P P

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Minimaler SchnittBalanzierung

Lemma 1: Sei dann gilt

Lemma 2: Sei dann gilt

23

( ) TunV RatioCut P f L f⋅ =

( ) Tsymvol(V) NCut P f L f⋅ =

i2i

P / P , wenn v P

P / P , sonsf

t

∈

−=

( ) ( )( ) ( )

i2i

vol P / vol P , wenn v P

vol P / vol P , sonstf

∈=

−

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Spectral-Clustering (unnormalisiert) Relaxation

RatioCut

24

n nT 2

i iP V i 1 i 1min f Lf , wobei f 0, f n⊂

= =

= =∑ ∑

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Spectral-Clustering (unnormalisiert) Relaxation

RatioCut

25

n nT 2

i iP V i 1 i 1min f Lf , wobei f 0, f n⊂

= =

= =∑ ∑

kann nur 2 Werte annehmenif

i2i

P / P , wenn v P

P / P , sonsf

t

∈

−=

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Spectral-Clustering (unnormalisiert) Relaxation

RatioCut

(Unnormalisiertes) Spectral-Clustering

26

n nT 2

i iP V i 1 i 1min f Lf , wobei f 0, f n⊂

= =

= =∑ ∑

n

n nT 2

i if i 1 i 1min f Lf , wobei f 0, f n∈ = =

= =∑ ∑

NP-hart

Eigenwertproblem

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Spectral-Clustering (unnormalisiert) Relaxation

RatioCut

(Unnormalisiertes) Spectral-Clustering

Diskretisierung:

27

n nT 2

i iP V i 1 i 1min f Lf , wobei f 0, f n⊂

= =

= =∑ ∑

n

n nT 2

i if i 1 i 1min f Lf , wobei f 0, f n∈ = =

= =∑ ∑

isign(f )

NP-hart

Eigenwertproblem

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Spectral-Clustering (unnormalisiert)Verallgemeinerung auf k>2

28

( )1 k ii 1...k

1Cut(P ,...P ) Cut P2 =

= ∑

( )1 k ii 1...k

1RatioCut(P ,...P ) RatioCut P2 =

= ∑

( )1 k ii 1...k

1Ncut(P ,...P ) Ncut P2 =

= ∑

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Spectral-Clustering (unnormalisiert)Verallgemeinerung auf k>2

29

( )1 k ii 1...k

1Cut(P ,...P ) Cut P2 =

= ∑

( )1 k ii 1...k

1RatioCut(P ,...P ) RatioCut P2 =

= ∑

( )1 k ii 1...k

1Ncut(P ,...P ) Ncut P2 =

= ∑

j2ij

i j

j

1 / P , wenn v P

1 / P , sonstF

=

∈−

i2i

P / P , wenn v P

P / P , sonsf

t

∈

−=

( )T1 kRatioCut(P ,...P ) Tr F LF=

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

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

Fmin Tr F LF , wobei F F I

×∈=

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

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

Fmin Tr F LF , wobei F F I

×∈=

iF

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Spectral-ClusteringBeispiel

Daten: Mixture of gaussian

32

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Spectral-ClusteringBeispiel

sim: RBF mit

Eigenwerte der zugehörigen Laplacematrix (fully connected Graph)

33

1σ =

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Spectral-ClusteringBeispiel

34

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

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 n0W ×

≥∈ k

unL

kunL

niu ∈

1

1 k

n

x | |u ... u

x | |

− − = − −

jCixjC

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

ApproximationsgüteBalanzierte 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/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

ApproximationsgüteBalanzierte 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/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Anmerkungen

Ncut führt zum verallgemeinerten Eigenvektorproblem (norm. Spectral clustering)

Probabilistische Motivation…

38

Saw

ade/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

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/Landwehr/P

rasse/Scheffer, M

aschinelles Lernen

Evaluation von Clusterings

Unüberwacht (nur heuristisch): z.B. Agglomerativer Koeffizient, Divisive Coefficient

Überwacht: Evaluationsdaten sind mit Clusterzugehörigkeit markiert Relative Entropie

… Anzahl Objekte markiert als in Cluster Durchschnittliches F-measure / Recall / Precision Rand-Index

40

jPkj

i| j i| jj 1 i

PH log

n=

=− δ δ∑ ∑

i| jδ i j