SOTA

Andrej Gisbrecht26.01.2007

26.01.2006 SOTA 2

Inhalt

MotivationAlgorithmusAnwendungZusammenfassung

26.01.2006 Motivation 3

DNA Microarray

26.01.2006 Motivation 4

DNA Microarray

Zeilen: Tausende verschiedene GeneSpalten: verschiedene KonditionenZellen: Intensität

26.01.2006 Motivation 5

Microarray-Analyse

Probleme:Sehr große DimensionViel RedundanzViel Rauschen

26.01.2006 Motivation 6

1. Versuch: UPGMA

Unweighted Pair Group Method with Arithmetic Meanvereinige mit minimalem in Cluster uHöhe ist = gewichtetes Mittel der Abstände u zu und

Probleme:Kann nicht mit Rauschen umgehenDeterministische Natur, unmöglich neu zu evaluieren

ij ijd

2ijd

kud i j

26.01.2006 Motivation 7

2. Versuch: SOM

Self-Organising MapRobust bei RauschenSchnell, geeignet für große DatensätzeVisualisierung

Probleme:Anzahl der Cluster festDurch Redundanz viele Cluster an einer StelleOhne Baumstruktur keine Beziehung der Gene erkennbar

26.01.2006 Motivation 8

SOTA

Self-Organising Tree AlgorithmVereinigt Vorteile der beiden MethodenOhne Nachteile zu übernehmen

Ergebnis ist ein hierarchisches Clustering erreicht mit

der Präzision und Robustheit eines Neuronalen Netzes

26.01.2006 Algorithmus 9

Zelle

Knoten

SOTA-Training

Unter allen Zellen wird die heterogenste ausgewählt

Die Zelle bekommt zwei Zellenkinder und wird selbst zum Knoten

Knoten

ZelleZelle

Zwei äußere Elemente, bezeichnet als Zellen, verbunden mit einem Mutterneuron, bezeichnet als Knoten

26.01.2006 Algorithmus 10

Distanzfunktion

Pearson correlation coefficient, r

Wobei Mittelwert und Standardabweichung aller

Punkte des k-ten Profils sind

21

221112

))ˆ)(ˆ((1)1(

SeSe

neeeerd i ii

ke kSe

)...,,,( 112111 neeegene )...,,,( 222212 neeegene

i

ii eed 22112

Zwei Gene und Euklidische Distanz

26.01.2006 Algorithmus 11

Adaption

Adaption erfolgt in Epochen. Jede Epoche besteht aus zwei Schritten:

Finde für jedes Profil die Gewinnerzelle, so dass dpc am kleinsten istAktualisiere die Gewinnerzelle und ihre Nachbarschaft mit der Formel:

))(()()1( ijii CPCC

26.01.2006 Algorithmus 12

Nachbarschaft

Es wird zwischen zweiFällen unterschieden

Wenn die Schwesterzelle Nachkommen hat, wird nur die Gewinnerzelle aktualisiertSonst werden Gewinnerzelle, Mutterzelle und Schwesterzelle mit verschiedenen aktualisiert

001,0;005,0;01,0 saw

26.01.2006 Algorithmus 13

Heterogenität

Die Heterogenität einer Zelle wird durch ihre Ressource

R bestimmt:

Es werden die Distanzen zu allen Profilen, die zu dieser

Zelle zugewiesenen wurden, aufsummiert und durch

ihre Anzahl geteilt.

K

dR

K

k CPi

ik 1

26.01.2006 Algorithmus 14

Konvergenz des Netzwerks

Am Ende jeder Epoche wird der Gesamtfehler berechnet:

Das Netzwerk konvergiert, wenn der Fehlerzuwachs unter einen Grenzwert fällt:

Danach wächst das Netzwerk weiter, indem die Zelle mitder größten Heterogenität zwei Nachkommen bekommt und der nächste Trainingszyklus anfängt.

i

it R

Et

tt

1

1

26.01.2006 Algorithmus 15

Wachstum des Netzwerks

Das Netzwerk hört auf zu wachsen wenn:Die am Anfang festgelegte Anzahl der Cluster erreicht wurde.Die Heterogenität des Netzwerks unter einen vorgegebenen Grenzwert fällt. Setzt man diesen Wert auf Null bekommt jedes Gen eine eigene Zelle.

Auf diese Weise kann man steuern auf welchem Hierarchielevel das Clustering aufhören soll.

26.01.2006 Algorithmus 16

Laufzeit

UPGMA quadratische LaufzeitSOTA annährend lineare Laufzeit

26.01.2006 Anwendung 17

SOTA + Perzeptron

Gegeben: verschiedene Krebszellen

Zuerst wurde unüberwacht geclustertDanach überwacht gelernt

Die Krebsarten werden erkannt

26.01.2006 Anwendung 18

Clustertiefe

Es wurden verschiedene Clustertiefen ausprobiertZwei Optima bei 44 und 223 ClusternBei zu wenig Clustern gehen viele Informationen verlorenBei zu vielen entsteht Overfitting

26.01.2006 Anwendung 19

Vergleich

26.01.2006 Anwendung 20

Perzeptrongewichte

Durch die Gewichte des Perzeptrons kann man herausfinden welche

Gene für welche Krebsarten verantwortlich sind

26.01.2006 Zusammenfassung 21

Zusammenfassung

Stabil bei Redundanz und RauschenSehr schnellHierarchisches ClusteringGute Resolution der kleinen KlassenErkennt relevante Gene

26.01.2006 Algorithmus 22

Vielen Dank für Ihre Aufmerksamkeit!

SOTA

HauptseminarSelf-Organizing Maps WS06/07

Referent:

Andrej Gisbrecht