Information Technology Reference
In-Depth Information
1. Die Prototypen werden initialisiert, in der Regel zufällig, beispielsweise indem
man c Datenpunkt zufällig als Prototypen auswählt.
2. Jedes Datenobjekt wird dem Prototypen zugeordnet, zu dem es den kleinsten
Abstand hat.
3. Jeder Prototype wird neu berechnet als Schwerpunkt der Daten, die ihm zuge-
ordnet sind.
4. Schritt 2 und 3 werden so lange wiederholt, bis sich keine Änderungen mehr
ergeben.
Zunächst sollte sichergestellt werden, dass der Algorithmus überhaupt konver-
giert, d. h. dass das Abbruchkriterium irgendwann erfüllt ist. Dies lässt sich dadurch
zeigen, indem man den Algorithmus als Minimierungsstrategie der folgenden Ziel-
funktion interpretiert:
c
i =1
k
j =1 u ij v i x j 2
F ( U , V ; X )=
(21.1)
Die zu optimierenden Parameter sind die Prototypen v i und die Zuordnungen u ij
{ 0, 1 } der Daten zu den Clustern. Als Nebenbedingung wird gefordert, dass für jedes
Datenobjekt x j X = { x 1 ,..., x k }
R q genau eines u ij der gleich 1 und alle anderen
gleich 0 sein müssen. Auf diese Weise wird garantiert, dass jedes Datenobjekt genau
einem Cluster zugeordnet wird. Insgesamt gilt es, die quadratischen Abstände der
Prototypen zu den ihnen zugeordneten Daten zu minimieren.
Die Strategie zur Minimierung dieser Zielfunktion, die der c -Means-Clustering-
Algorithmus verfolgt, besteht in der alternierenden Optimierung. Dabei wird jeweils
ein Parametersatz — entweder die Prototypen oder die Zuordnungen der Daten —
festgehalten und der andere Parametersatz so eingestellt, dass sich ein minimaler
We r t de r Zi e l f unk t i on bezüg l i ch de r f e s t geha l t enen We r t e de s ande ren Pa r ame t e r sa t -
zes ergibt. Offensichtlich muss man zur Minimierung der Zielfunktion bei festgehal-
tenen Prototypen die Zuordnungen der Daten zu den Clustern so wie in Schritt 2
wählen. Genauso müssen bei gegebener Zuordnung der Daten zu den Clustern die
Prototypen zur Minimierung der Zielfunktion so wie im Schritt 3 gewählt werden.
Daher wird der Wert der Zielfunktion in jedem Schritt des c -Means-Clustering-
Algorithmus verringert. Da es nur endliche viele Zuordnungen der Daten zu den
Clustern gibt, muss dieses Verfahren irgendwann konvergieren. Der Algorithmus
garantiert allerdings nicht die Konvergenz im lokalen Minimum der Zielfunktion.
Es kann passieren, dass der Algorithmus in einem lokalen Minimum stecken bleibt.
Wir betrachten dazu als Beispiel den Datensatz, der in Abbildung 21.1 dargestellt
ist. Dieser Datensatz enthält offensichtlich drei Cluster, die durch unterschiedliche
Symbole gekennzeichnet sind. Wird der c -Means-Clustering-Algorithmus mit c = 3
Clustern beispielsweise mit drei Prototypen initialisiert, von denen zwei in demClu-
ster unten links liegen und der dritte Prototyp etwa in der Mitte zwischen den beiden
rechten Clustern gewählt wird, konvergiert der Algorithmus zu einer Clustereintei-
lung, bei der die beiden rechten Cluster zu einem Cluster zusammengefasst werden
und das linke Cluster künstlich in zwei Cluster aufgeteilt werden.
Search WWH ::




Custom Search