Clusteranalyse |
Grundsätzlich geht es bei Clusterverfahren darum, eine Menge von Objekten so in Gruppen einzuteilen, daß die Mitglieder derselben Gruppe einander möglichst ähnlich und Mitglieder unterschiedlicher Gruppen möglichst verschieden sind. Mathematisch ausgedrückt heißt dies, daß man versucht, eine auf der Menge der Partitionen der Objektmenge definierte Funktion zu optimieren. Dabei stößt man auf verschiedene theoretische wie praktische Schwierigkeiten. Hierzu zählt die
Wahl einer Zielfunktion, die eine zufriedenstellende Struktur der Cluster liefert und sich auch bei Datenmengen von Millionen von Elementen mit komplexen Merkmalen noch in akzeptabler Zeit optimieren läßt. Die aus der Literatur bekannten
Beispiele gingen bis vor kurzem nicht über einige hundert Objekte mit höchstens acht Merkmalen hinaus.
Mathematisch läßt sich das Clusterproblem für das im Rahmen der Simulation von Bausparkollektiven verwendete Clusterverfahren, die Centroidmethode, folgendermaßen als Minimierungsaufgabe formulieren: Gesucht ist eine Verteilung von m Objekten auf K Cluster derart, daß die Summe der Abstände der Objekte Ajk aller Cluster zu ihrem jeweiligen Mittelwertvektor Zk minimal wird: Dieses Problem ist NP-schwer, d.h.es ist kein deterministischer Algorithmus bekannt, der das Problem effizient (in polynomialer Zeit) exakt löst. Man ist deshalb auf Heuristiken angewiesen, die eine gute Lösung - im allgemeinen ein lokales Minimum - in angemessener Zeit liefern. Zwei von uns eingesetzte Methoden sind das Minimaldistanzverfahren und das Austauschverfahren, wobei sich in der Praxis die Kombination der beiden genannten Verfahren bewährt hat. Beim Minimaldistanzverfahren werden abwechselnd alle Objekte ihrem nächsten Zentralpunkt zugeordnet und dann die Zentralpunkte neu berechnet. Beim Austauschverfahren wird für ein bestimmtes Objekt geprüft, ob durch Zuordnung dieses Objekts zu einem anderen Cluster die Summe der Abstände zum jeweiligen Mittelpunkt für alle Objekte verringert werden kann. Ist dies der Fall, wird dieses eine Objekt umsortiert und der Schritt erneut durchgeführt.
|
| Zur Leitseite "Simulation von Bausparkollektiven" |