SS 2009Maschinelles Lernen und Neural Computation 107 Kapitel 6: Unüberwachtes Lernen

SS 2009 Maschinelles Lernen und Neural Computation

1

Kapitel 6: Unüberwachtes Lernen

SS 2009 Maschinelles Lernen und Neural Computation

2

Clustering

• Gegeben: eine Menge von Punkten (Beispielen), „ungelabelt“ (i.e. Klasse unbekannt)

• Gesucht: eine Menge von Clustern (Cluster-Zentren), die die Daten möglichst gut beschreiben („Vektorquantisierung“)

minimiere

(Summe der Abstände zu allen Zentren, quadratischer Quantisierungsfehler)

k

i Cxjij

ij

D1 :

2wx

SS 2009 Maschinelles Lernen und Neural Computation

3

K-means Clustering

• Gradientenverfahren

• Neues Cluster-Zentrum ist Mittelwert der Punkte im Cluster

• Mehrere Iterationen notwendig

n

jji

i nD

1

new 10 xww

SS 2009 Maschinelles Lernen und Neural Computation

4

Clustering als NC: Competitive Learning

• Architektur wie Perceptron

n

iijij wxfx

1

2

f ... Gauss; wie RBFN

Wähle „Gewinner“(am stärksten aktivierte Unit)

Setze „Gewinner“ auf 1,alle anderen auf 0

• „winner-take-all“• Gewinner lernt (Instar Regel): ijiij wxw

SS 2009 Maschinelles Lernen und Neural Computation

5

Geometrische Interpretation• Gewichtsvektoren

und Inputs sind Punkte im Raum

Input• Gewinner wählen = finde nähesten Gewichstvektor

• Resultat: Gruppen in den Daten werden gefunden

• Instar: Ziehe Gewichtsvektor zu Input hin

• stochastische Variante von k-means!

Matlab>demos>neural networks>other demos>chapter 14>competitive learning

SS 2009 Maschinelles Lernen und Neural Computation

6

Eigenschaften

• Clustering nach k-means ist Gauss‘sches Clustering (symmetrische Streuung)

• Aufteilung des Raumes: Voronoi Tesselation

• Mögliche Probleme:– Lokale Minima

(bei schlechter Initialisierung)

– Verzerrung durch Ausreisser

SS 2009 Maschinelles Lernen und Neural Computation

7

Gaussian Mixtures als Clustering• Clustering wird als Dichteschätzung betrachtet

• Anschreibbar wie Klassifikationsproblem:

• EM-Algorithmus (max. Likelihood):

j

iijji xp

PpP

||

xx

Posterior des Clusters iGaussverteilung Prior (i)

Dichte (GMM)

k

i i

ij

i

ij

xxp

12

2

2exp

2

n

kiki

n

kkiki

i

xP

xxP

1

1new

,|

,|

Gewichteter Mittelwert, analog zu k-means

Netlab>demgmm1.m

SS 2009 Maschinelles Lernen und Neural Computation

8

Vorteile der GMM

• Vorteile:– Probabilitischer Rahmen– Zugehörigkeit zu Clustern angebbar

(Posterior)– Ausgeprägtheit von

Clustern bestimmbar– Modellauswahl möglich

(anhand der Likelihood)k-means: optimale Anzahl der Clusters nicht leicht bestimmbar

SS 2009 Maschinelles Lernen und Neural Computation

9

Erweiterungen

• Erweiterung auf beliebige Gauss-Verteilungen möglich

• K-means: entspricht „Mahalonobis Distanz“(berücksichtigt Varianzen innerhalb der Cluster)

Netlab>demgmm3.m, demgmm4.m

Gewöhnliche (sphärische) Gauss-FunktionenBeliebige Gauss-Funktionen

SS 2009 Maschinelles Lernen und Neural Computation

10

Nicht-Gauss‘sches Clustering

• Nur als Mixture von Gauss‘schen Zentren beschreibbar

• Wenn „natürliche“ Cluster gefunden werden sollen: Nur parametrisch möglich (d.h. Form der Cluster bekannt)

• Ansonsten: Identifikationsproblem

SS 2009 Maschinelles Lernen und Neural Computation

11

Andere Formen des Clustering

• Andere Distanz-(Ähnlichkeits-)Maßez.B. Manhattan-Distanz, Ranking

• Andere Fehler-(Kriteriums-)Funktionenz.B. Kohäsion innerhalb des Clusters, Entropie

• Hierarchisches Clustering– Dendrogramme– ART mit verschiedenen

Vigilanzen

SS 2009 Maschinelles Lernen und Neural Computation

12

Selforganizing Maps (SOM)

• Kohonen (1981, 1990)

• Nachbarschaft definiert• Wie CL: winner-take-all, Instar• Aber Nachbarn lernen mit

ijijij wxxxnw win,

Nachbarschaftsfunktion,wird im Laufe des TrainingsKleiner (Stabilisierung)

SS 2009 Maschinelles Lernen und Neural Computation

13

SOM: Geometrische Interpretation

• Topologische Beziehung der Clusters bleibt weitgehend bestehen

• Benachbarte Units entsprechen benachbarten Clustern

• Datenraum wird auf die 2-dim. Struktur abgebildet („Karte“)

• Dient zur Visualisierung hochdimensionaler Daten

• 2-dim. Struktur wird in den hochdimensionalen Raum eingepasst - Projektion

3x3 SOM

Vienet2>uebung4.exe; Matlab>demos>2dim. selforganizing map

SS 2009 Maschinelles Lernen und Neural Computation

14

Beispiel: politische Konflikte

• Daten: Konflikte und Vermittlungsversuche seit 1945 (Bercovitch & Langely 1993)

• 6 Dimensionen:– Dauer– Politische Macht A– Politische Macht B– Politische Rechte B– Initiator– Vermittlunsgerfolg

• 2 dim. Visualisierung

http://websom.hut.fi

SS 2009 Maschinelles Lernen und Neural Computation

15

SOM

• Durch schlechte Initaliseriung kann k-means zu sub-otpimalen Lösungen führen (lokales Minimum)

• SOM: durch Mitziehen der Nachbarn wird der Datenraum besser abgedeckt (lokale Minima können vermieden werden)

• Zusätzlich: – Topologische Beziehung– Mehr Zentren in Bereichen hoher

Dichte

SS 2009 Maschinelles Lernen und Neural Computation

16

Multidimensionale Skalierung

• Aufgabe: Bilde hochdimensionale (n-d) Daten auf niedrige Dimensionalität (k-d) ab, sodaß Abstände zwischen den Punkten annähernd gleich bleiben (Dimensionsreduktion)

• Funktioniert gut, wenn Daten auf k-dim. Mannigfaltigkeit liegen (z.B. gekrümmte Fläche)

SS 2009 Maschinelles Lernen und Neural Computation

17

SOM als MDS

• MDS entspricht dem Prinzip der topologischen Erhaltung in der SOM

SOM ist Clustering + MDS (mit Verzerrung abh. von Dichte)!

Bereich 1

1

Bereich 2

2

SS 2009 Maschinelles Lernen und Neural Computation

18

Topologische Darstellung

• Zwischenzustände durch Gewichtung mittels Distanz zu Zentren

• Ausgeprägte Grenzen darstellbar (U-Map, Ultsch)

SS 2009 Maschinelles Lernen und Neural Computation

19

Alternative: Sammon Mapping

• Minimiere Differenz aller Abstände:

• Nachteil: hoher Berechnungsaufwand• Lösung: zuerst Clustering, dann Sammon

Mapping (weniger Punkte); Flexer 1996• Aber: Gleiche Probleme mit lokalen Minima wie

k-means

i ij ji

jiji

ddd

Dxx

xxxx,

~,~, 2

Abstand OriginalpunktePunkte in der Map

Normalisierung

SS 2009 Maschinelles Lernen und Neural Computation

20

Probleme der SOM

• Keine probabilistische Beschreibung• Konvergenz nicht garantiert• Es gibt keine Fehlerfunktion, die minimiert wird!• Clustering und MDS beeinflussen einander (beides kann

suboptimal sein) • Es ist schwer abschätzbar, ob SOM gut ist oder nicht Empfehlung:

– SOM nur zur Visualisierung einsetzen!(nicht zum Clustering oder für überwachte Probleme)

– Genau überlegen, was Kriterium ist; Alternativen suchen

SS 2009 Maschinelles Lernen und Neural Computation

21

Generative Topographic Mapping (GTM)

• Bishop et al. (1996)• Nichtlineares Mapping von

einer Gitterstruktur auf eine Gaussian Mixture(z.B. durch MLP)

• GMM mit Randbedingungen• Probabilistische

Formulierung, umgeht viele der Probleme der SOM

Aus Bishop et al. (1996), Neural Computation 10(1), 215-235

Aus Netlab Demo demgtm2.m

Netlab>demgtm1.m, demgtm2.m

k

i i

i

i

i yp1

2

2

2exp

2|

W,xtWx,t

Zentrum abh. vonGitterpunkt

SS 2009 Maschinelles Lernen und Neural Computation

22

Praktische Aspekte• Auch für unüberwachte Verfahren gelten im

wesentlichen die 7 Schritte:1. Sichtung (Ausreißer)2. Vorverarbeitung:

Skalierung der Merkmale beeinflusst die Distanz Normalisierung

3. Merkmalsselektion:irrelevante Merkmalekönnen Clusteringerschweren:

SS 2009 Maschinelles Lernen und Neural Computation

23

Kreuzvalidierung für unüberwachtes Lernen

4. Modellschätzung mittels Kreuzvalidierung:bei k-means problematischbei GMM: Likelihood-Funktion als Fehlerfunktion

(„Loss“-Funktion)

SS 2009 Maschinelles Lernen und Neural Computation

24

Kombination von überwachtem mit unüberwachtem Lernen

• Unüberwachte Verfahren alleine eignen sich nur für unüberwachte Probleme!

• Bei überwachtem Problem (gelabelte Daten) kann unüberwachtes Verfahren eingesetzt werden als– Initialisierung– Vorstrukturierung

• Beispiele:– SOM oder GTM als Initialisierung eines RBFN– Learning Vector Quantization– ARTMAP

SS 2009 Maschinelles Lernen und Neural Computation

25

Learning Vector Quantization (LVQ)• Kohonen (1990)

Ordne Units Klassen zu

nearest neighbor Verfahren mit Vektorquantisierung (nicht jeder Trainingspunkt gespeichert)

• Vergleichbar mit Dichteschätzung der class-conditionals

kxcwx

kxcwxw

kii

kiiki

if

if

,

,,

hinbewegen, wenn richtige Klasse

wegbewegen, wenn falsche Klasse

SS 2009 Maschinelles Lernen und Neural Computation

26

Zusammenfassung

• Unüberwachte neuronale Netz-Verfahren reihen sich ebenfalls nahtlos in die Statistik

• Competitive Learning = k-means• GMM als probabilistisches Clusteringverfahren• SOM als Multidimensionale Skalierung +

Clustering, aber mit Problemen