Methoden zur Cluster - AnalyseKapitel 4

Spezialvorlesung Modul 10-202-2206(Fortgeschrittene Methoden in der Bioinformatik)

Jana Hertel

Professur fur BioinformatikInstitut fur Informatik

Universitat Leipzig

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 1/14

Methoden zur Cluster - Analyse Einfuhrung

Cluster - Analyse

Finde ahnliche Strukturen in großen Datensatzen → Cluster.

Ordne jedes Objekt einem Cluster zu → Clustering.

k-Means-Algorithmus

Learning Vector Quantization

EM-Algorithmus

k-Nearest-Neighbor Klassifikation

Beziehung zw. Eigenschaften der Objekte und Klassenzuordnung unbekannt!

Als black box Algorithmen zur Klassifikation und Mustererkennung genutzt.

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 2/14

Methoden zur Cluster - Analyse k-Means-Algorithmus

k-Means-Algorithmus

.. finde Cluster und deren Clusterzentren in einer Menge ungelabelter Objekte.

Gegeben: initiale Menge an Zentren, alterniere die folgenden Schritte:

1. ∀ Zentren identifiziere Teilmenge an Trainingspunkten (Cluster), die naher andiesem Zentrum liegen als an allen anderen

2. berechne Mittelwert aller Eigenschaften der Datenpunkte → neues Zentrumdes Clusters

Iteriere bis Algorithmus konvergiert.

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 3/14

Methoden zur Cluster - Analyse k-Means-Algorithmus

Beispiel: Ein Durchlauf des k-means Algorithmus zur Bestimmung von 3 Gruppen.

Zufallige Wahl der initialen Clusterzentren

Ordne Objekte (Rechtecke) den ihnen amnachsten liegenden Clusterzentren zu

Neuberechnung der Zentren anhand neuerZuordnung

Neuverteilung der Objekte zu denClusterzentren die am nachsten liegen

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 4/14

Methoden zur Cluster - Analyse k-Means-Algorithmus

k-means mit Prototypen

Bisher: Cluster definiert durch Zentrum, Objekte nach min. Abstand zumZentrum zugeordnet.

Problem: Ausreiser!

Losungsansatz: Einfuhrung von R Prototypen fur jede Klasse K

Fuhre k-means in jeder Klasse einzeln durch um R Prototypen zu finden

→ R Zentren von R Sub-Klassen jeder Klasse!

Label jeden der K × R Prototypen entspr. der zugehorigen Klasse

Klassifiziere ein Objekt x zu der Klasse mit nachstliegenden Prototyp

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 5/14

Methoden zur Cluster - Analyse k-Means-Algorithmus

k-means mit Prototypen

Problem: Einige der Prototypenzu nah an den Klassengrenzen

→ Klassifizierungsfehler!

Warum? BeiEinzeldurchfuhrung vonk-means, Einfluss benachbarterKlassen nicht berucksichtigt.

Losung: Benutze alleDatenpunkte um Prototypen zubestimmen!

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 6/14

Methoden zur Cluster - Analyse Learning Vector Quantization - LVQ

Learning Vector Quantization - LVQ

Idee: Trainingspunkte ziehen richtige Prototypen an und stoßen falsche ab.

1. Wahle R initiale Prototypen fur jede Klassem1(k),m2(k), . . . ,mR(k), k = 1, 2, . . . ,K

2. Wahle ein Trainingsobjekt xi zufallig (Sample mit Zurucklegen!), mj(k) istnachster Prototyp zu xi

a) Falls xi in Klasse k, verschiebe Prototyp in Richtung xi :

mj(k)← mj(k) + ε(xi −mj(k))

b) sonst, schiebe Prototyp von xi weg:

mj(k)← mj(k)− ε(xi −mj(k))

3. Wiederhole 2, wobei Lernrate ε mit jeder Iteration Richtung 0 reduziert wird.

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 7/14

Methoden zur Cluster - Analyse Learning Vector Quantization - LVQ

Bild: k-means mit 5 Prototypen

Bild: LVQ, gestartet mit k-means Losung.Prototypen wurden von den Klassengrenzenweggeschoben.

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 8/14

Methoden zur Cluster - Analyse EM Algorithmus

Gauss’sche Mischverteilungen - EM Algorithmus

Ahnlich k-means und LVQ, zur Bestimmung weicher Klassengrenzen.

Jedes Cluster durch Gaussverteilung mit Centroid und Covariancematrixbeschrieben.

1. E-Schritt: Jeder Beobachtung ein Gewicht fur jedes Cluster zugewiesen,entspr. der Verteilung

Punkte nahe Centroid - Gewicht nahe 1 fur dieses Cluster und 0 fur alle anderen,Punkte zwischen Centroids bekommen entspr. Gewichtsverteilung

2. M-Schritt: Neuberechnung von Centroids und Covarianzen fur jedes Cluster

→ EM Algorithmus ∼ weiche Clustering Methode

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 9/14

Methoden zur Cluster - Analyse EM Algorithmus

Bild: k-means mit 5 Prototypen Bild: EM Algorithmus, gestartet aufk-means Losung.

Klassengrenzen grob ahnlich, aber fur Gaussian Model weich!Obwohl beide Methoden einen grunen Prototyp angeben, kann Gaussian Model diese Regionignorieren.

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 10/14

Methoden zur Cluster - Analyse k-Nearest-Neighbor Klassifikation

k-Nearest-Neighbor Klassifikation

Speicherbasierte Methode, welche kein trainiertes Model vorraussetzt.

Prinzip:

Gegeben ein Objekt x0

Finde k Trainingsobjekte x(r), r = 1, . . . , k , die am nachsten an x0 liegen

Klassifiziere nach Mehrheitsprinzip zwischen den k Nachbarn

Geeignet fur Probleme bei denen:

viele mogliche Prototypen per Klasse

Klassengrenzen sehr unregelmaßig

Vielfaltige Anwendung u.a. in Handschrifterkennung, Analyse von Satellitenbildernund EKG Mustern.

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 11/14

Methoden zur Cluster - Analyse k-Nearest-Neighbor Klassifikation

Bild: k-means mit 5 Prototypen Bild: 15-nearest Neighbor

Entscheidungsgrenze weicher als bei k-means Klassifikationen.

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 12/14

Methoden zur Cluster - Analyse k-Nearest-Neighbor Klassifikation

Bild: k-means mit 5 Prototypen Bild: 1-nearest Neighbor

Beziehung zu Protoyp-Methoden: k Trainingsobjekt(e) entsprechen 1 Prototyp.

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 13/14

Methoden zur Cluster - Analyse k-Nearest-Neighbor Klassifikation

How to choose k?

Problem: kleines k → Bias klein, aberVarianz hoch!

Losungsansatz:

k = 1

k + + solange Fehlerrate undVarianz sich verbessern

← Abhangig vom Problem erhalt manverschiedene Werte fur k.

J. Hertel Bioinf - Uni Leipzig

Machine learning in bioinformatics K4 14/14