next up previous contents
Next: Auffinden der superparamagnetischen Phase Up: Algorithmus Previous: Algorithmus

Suche nach Nachbarn

Zuerst werden die Nachbarn jedes Punktes entsprechend eines ausgew"ahlten Kriteriums bestimmt.

Man kann Nachbarschaft definieren, indem man sagt, jeder Punkt j innerhalb eines bestimmten Abstandes r von einem Punkt i ist Nachbar. Dieses Vorgehen kann jedoch zu Problemen bei sehr inhomogenen Punktverteilungen f"uhren; au"serdem ist in diesem Fall die Gesamtanzahl der Nachbarn schlecht vorherzusehen, was es erschwert, den Rechenzeitaufwand abzusch"atzen. Als Problem kommt in inhomogenen Punktfeldern der Effekt zum Tragen, dass Punkten in schwach besetzten Regionen evtl. keine Nachbarn zugeordnet werden k"onnen. Diese Punkte w"urden in der Clusterdetektion nicht ber"ucksichtigt werden. Auf den ersten Blick erscheint dieser Umstand als nicht so gravierend, weil Punkte in schwach besetzten Regionen sicherlich nicht zu H"aufungen in dichten Regionen geh"oren. Wie in Abschnitt 4.2.2 aber gezeigt wird, ist der Algorithmus in der Lage, Cluster in unterschiedlich dichten Region aufzufinden. Aus diesem Grund ist es w"unschenswert, andere Nachbarschaftskriterien zu verwenden, die diese Beschr"ankungen nicht aufweisen.

blatt96 schlagen f"ur zwei- und dreidimensionale Probleme vor, diejenigen Punkte als Nachbarpunkte zu bezeichnen, deren Voronoi-Zellen (u. a. fukuda98) gemeinsame Grenzen haben. Diese Beschr"ankung beruht aber wohl eher auf der Tatsache, dass blatt96 kein effizienter Algorithmus zur Voronoi-Triangulation in h"oheren Dimensionen zur Verf"ugung stand. F"ur h"oherdimensionale Datens"atze ist das Kriterium der sogenannten K-gegenseitigen Nachbarschaft (K-mutual neighbourhood) zu pr"aferieren. Dabei gilt das Kriterium wie folgt: Zwei Punkte i und j sind K-Nachbarn, dann und nur dann, wenn der Punkt j einer der K n"achsten Nachbarn des Punktes i und der Punkt i einer der K n"achsten Nachbarn der Punktes j ist. Die Bezeichnung n"achster Nachbar wird hier im euklidischen Sinne verstanden. K ist bei Verwendung dieses Nachbarschaftskriteriums ein Parameter f"ur die Clustersuche.

F"ur gro"se Datens"atze ist diese Methode die schnellste, jedoch ist die Nachbardefinition entsprechend des Voronoi-Kriteriums unmittelbar verst"andlich und intuitiv treffend. Da hier auch ein effizienter multidimensionaler Algorithmus [Fukuda1998] zur Verf"ugung stand, werden die Analysen der Daten in dieser Arbeit fast ausschlie"slich mit dem Voronoi-Kriterium durchgef"uhrt. Ein Vergleich der Ergebnisse der unterschiedlichen Methoden der Nachbarschaftssuche ist in Abbildung 4.1 zu sehen.

  figure152
Figure 4.1: Vergleich der Ergebnisse mit den unterschiedlichen Verfahren der Nachbarschaftsuche: Radius (r=0.125, links), K-gegenseitige Nachbarn (K=10, Mitte), Voronoi (rechts). Der Referenzpunkt ist durch eine rote Raute gekennzeichnet, blaue Quadrate bezeichnen die gefundenen Nachbarn, schwarze Kreise stellen die restliche Punktmenge dar.

Hierbei ist zu beobachten, dass bei den Verfahren mit festem Radius und der K-gegenseitigen Nachbarschaft in dem hier gew"ahlten Beispiel nur Punkte als Nachbarn festgelegt werden, die sich auf einer Seite des Referenzpunktes befinden. Das f"uhrt zu einer gewissen Inhomogenit"at der Richtung der sp"ater eingef"uhrten Wechselwirkungen. Nur bei der Definition nach dem Voronoi-Kriterium ist mit einer ann"ahernd richtungsunabh"angigen Nachbarwahl zu rechnen.

Hier ist auch leicht einzusehen, dass die Wahl des Nachbarschaftskriteriums einen nicht zu vernachl"assigenden Einflu"s auf die endg"ultige Form der detektierten Cluster hat. Mit dem Verfahren mit vorgegebenem Radius und der K-gegenseitigen Nachbarschaftsmethode sind Punktkonfigurationen denkbar, bei denen Punkte existieren, die keine Nachbarn besitzen.

Gleichzeitig mit der Nachbarschaftsbestimmung wird der mittlere Abstand der n"achsten Nachbarn a bestimmt, eine Gr"o"se, die in die Berechnung der einheitenlosen Kopplungsparameter tex2html_wrap_inline3756 (Gl. 4.1) f"ur die Monte-Carlo-Simulation eingeht.
 equation159
tex2html_wrap_inline3864 ist hierbei die mittlere Anzahl von Nachbarn pro Punkt. Bei der Methode der K-gegenseitigen Nachbarn ist tex2html_wrap_inline3868.

Diese exponentielle Abstandsabh"angigkeit des Kopplungsparameters wurde aus Gr"unden der Vergleichbarkeit mit der Beschreibung dieses Algorithmus verwendet. Es besteht jedoch keine Garantie, dass sich s"amtliche Punktfelder mit dieser Definition erfolgreich in Cluster unterteilen lassen.


next up previous contents
Next: Auffinden der superparamagnetischen Phase Up: Algorithmus Previous: Algorithmus

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