next up previous contents
Next: Grundlagen und Algorithmus Up: List of Tables Previous: List of Tables

Einleitung

Clustersuche und -analyse sind wichtige Techniken der Datenanalyse, wenn man an einer Klassifikation von Punkten eines Vektorraums interessiert ist. Im Falle eines Konfigurationsraumes kann es von Interesse sein, Gebiete erh"ohter Teilchendichte sowie deren r"aumliche Ausdehnung und geometrische Formeigenschaften zu identifizieren. Die Koordinaten des Vektorraumes k"onnen beliebige Eigenschaften repr"asentieren. Gebiete erh"ohter Punktdichte erlauben dann eine Klassifikation der Punkte.

Als Ziel gilt hierbei, die Daten in verschiedene Klassen zu teilen. Jede Klasse repr"asentiert dabei eine bestimmte Kategorie der Messdaten. Das Problem der klassenweisen Clustereinteilung kann formal wie folgt beschrieben werden: Bestimme eine Partition von N unterschiedlichen Punkten eines metrischen D-dimensionalen Raumes tex2html_wrap_inline3722 in Klassen, so dass die Elemente einer Klasse untereinander "ahnlichere Eigenschaften haben als Elemente aus unterschiedlichen Klassen. Diese Klassen hei"sen Cluster. Dabei wird davon ausgegangen, dass ein Ma"s tex2html_wrap_inline3724 f"ur die Unterschiedlichkeit zweier Punkte i und j existiert oder aber dass jeder Datenpunkt durch einen Vektor tex2html_wrap_inline3730 in einem D-dimensionalen metrischen Raum repr"asentiert wird, wodurch dann tex2html_wrap_inline3732 definiert werden kann.

Die zwei haupts"achlichen Methoden der gruppenweisen Clustereinteilung hei"sen parametrisch und nichtparametrisch. Bei der parametrischen Herangehensweise wird eine Annahme "uber die grundlegende Struktur der Cluster verwendet. So kann ein Cluster z.B. durch ein Zentrum spezifiziert werden. Die Abst"ande der Punkte, die zu ihm geh"oren, sind um dieses Zentrum entsprechend einer Gau"sverteilung verstreut. In vielen F"allen werden diese Annahmen in ein globales Kriterium integriert, welches dann zu einer optimalen Einteilung f"uhrt. Ziel ist es, Datenpunkte so auf Gruppen zu verteilen, dass eine Variable das Kriterium, z.B. ein Minimum, erf"ullt. Klassische Ans"atze dieser Art sind Varianzminimierung, maximal likelihood und das K-Means-Verfahren (u.a. steinhausen77).

In vielen F"allen kann man jedoch keine vern"unftigen Annahmen "uber die Clusterstruktur machen. In diesem Fall bedient man sich nichtparametrischer Verfahren, welche weniger Annahmen "uber das Modell ben"otigen und dadurch auch flexibler in Bezug auf Clustereinteilung sind. "Ublicherweise verwenden diese Methoden ein lokales Kriterium, mit welchem an Hand der lokalen Struktur der Daten eine Klassifizierung unternommen wird. Diese Verfahren leiden aber meistens unter der Schw"ache, dass sie kein Ma"s f"ur die G"ute der Unterteilung liefern k"onnen, so dass es schwerf"allt, die richtige Clustereinteilung auszuw"ahlen. Dar"uber hinaus werden Daten auch in Gruppen eingeteilt, wenn gar keine Strukturierung der Datenpunkte vorliegt.

In der vorliegenden Arbeit wird ein nichtparametrisches Verfahren untersucht, welches von blatt96 vorgestellt wurde. Es basiert auf den physikalischen Eigenschaften eines magnetischen Systems. Diese Methode hat eine Reihe von n"utzlichen Eigenschaften: Es gibt Informationen "uber verschiedene selbstorganisierende Phasen. Die hierarchische Organisation der Daten wird durch die Art und Weise widergespiegelt, wie sich Cluster verbinden oder trennen, wenn ein Parameter des Algorithmus (die physikalische Temperatur) variiert wird. Zudem ist die Anzahl der Cluster ein Ergebnis der Analyse, kein Parameter des Verfahrens.

In einem ersten Schritt wird der D-dimensionale Konfigurationsraum von N Punkten tex2html_wrap_inline3738 um einen q-dimensionalen Spinzustandsraum tex2html_wrap_inline3742 erweitert (tex2html_wrap_inline3744) und damit der "Ubergang zu einem irregul"aren Spingitter vollzogen. Der tex2html_wrap_inline3738 entspricht den Koordinaten dieses Spingitters. Dieses wird als Modellmagnet im kanonischen Ensemble betrachtet. Theoretische Grundlage ist das Potts-Modell, wobei die Magnetisierung durch ein Monte-Carlo-Verfahren bestimmt wird.

Wie aus der Festk"orperphysik bekannt, existieren Materialien (z.B. Eisenoxidteilchen, die mit Zirkonoxidteilchen "uberzogen sind), die in Abh"angigkeit von der Temperatur neben der ferromagnetischen und der paramagnetischen Phase einen weiteren Phasenzustand aufweisen. Dabei handelt es sich um die sogenannte superparamagnetische Phase, in der Spindom"anen wie Superspins agieren (gleicher Spinzustand in ganzem Bereich), wogegen diese Dom"anen untereinander keine Spinkorrelation zeigen. Durch Auffinden dieser Dom"anen in der superparamagnetischen Phase wird die Clusteridentifikation ausgef"uhrt.

Wie onsager44 am Beispiel des 2D-Ising-Modells nachwies, sind in solchen Spingittern Phasen"uberg"ange m"oglich, z.B. ferromagnetisch-paramagnetisch. Im Potts-Modell, das als Erweiterung des Ising-Modells zu verstehen ist, k"onnen diese Phasen"uberg"ange auch beobachtet werden. Diese Eigenschaft wird nun zur Identifikation von Clustern benutzt.

Ziel der Arbeit ist eine Untersuchung der Anwendbarkeit dieses Algorithmus zur Clustersuche in Punktfeldern nat"urlicher Systeme.

Die Ergebnisse der Anwendung auf Testdaten nach Vorbild von blatt97 werden in Kapitel 4 detailliert untersucht.

S"amtliche Untersuchungen wurden mit dem von mir nach den in blatt96 und blatt97 gegebenen Erl"auterungen geschriebenen Programm clusterg durchgef"uhrt. Ein Anwendungsleitfaden ist im Anhang beigef"ugt.

Der erste Teil der Arbeit befasst sich mit den physikalischen Grundlagen des Algorithmus. In Kapitel 2 wird ein kurzer "Uberblick "uber das Konzept der Punktfelder gegeben, welches zur Einordnung der zu untersuchenden Daten hilfreich ist. Anschlie"send wird im Kapitel 3 das Potts-Modell als Erweiterung des Ising-Modells erkl"art und dessen rechentechnische Behandlung mit Monte-Carlo-Simulationen beschrieben. Wie oben schon erw"ahnt, folgt dann die Erl"auterung des Algorithmus und seine Anwendung auf geeignete Testdaten in Kapitel 4.

Im zweiten Teil der Arbeit werden Ergebnisse der Anwendung dieses Verfahrens auf Datens"atze aus den Bereichen Kosmologie (Kap. 5), granularer Gase (Kap. 6) und Seismologie (Kap. 7) dargestellt.

Schlie"slich folgt in Kapitel 8 eine Zusammenfassung und Diskussion der Ergebnisse der vorangegangenen Kapitel.


next up previous contents
Next: Grundlagen und Algorithmus Up: List of Tables Previous: List of Tables

Udo Schwarz
Thu Mar 1 15:43:04 MET 2001