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


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


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


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


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


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


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


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


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


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


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


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)


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


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


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


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)


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


18

Topologische Darstellung

• Zwischenzustände durch Gewichtung mittels Distanz zu Zentren

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


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


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


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


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:


23

Kreuzvalidierung für unüberwachtes Lernen

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

(„Loss“-Funktion)


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


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


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

Documents

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