Fuzzy C-Means

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Fuzzy C-Means (FCM) Algorithmus ist ein unüberwachter Clustering-Algorithmus, der auf einem Modell der Zielfunktions-Optimierung basiert. In einer generalisierten Form wurde er von Bezdek (1981) vorgestellt.

Der Begriff fuzzy beschreibt dabei eine Methode der Clusteranalyse, die es erlaubt, ein Objekt mehr als nur einem Cluster zuzuordnen. Ermöglicht wird dies dadurch, dass ein Grad der Zugehörigkeit (membership degree) $u i k$ des Objekts $x k$ $(k = 1,..., N)$ zu jedem Cluster $i$ $(i = 1,..., C)$ verwendet wird. Jedes $u i k$ liegt dabei im Intervall [0,1]. Je größer $u i k$ , desto stärker ist die Zugehörigkeit von $x k$ zu $i$ .

Die Zielfunktion des FCM-Algorithmus lautet:

$J(U,V)=\sum_{i=1}^C \sum_{k=1}^N u_{ik}^{m} d_{ik}^2$

Dabei gibt $d_{ik}^2=(x_{k}-v_{i})^T(x_{k}-v_{i})$ die quadrierten (euklidschen) Distanzen zwischen den Punkten $x k$ und den Clusterzentren (Prototypen) $v i$ aus der Matrix V an. Die Partitionsmatrix U gibt die membership degrees $u i k$ wieder. C ist die Anzahl an Clustern und N die Größe des Datensatzes. Der "fuzzifier" m(>1) bestimmt, wie scharf die Objekte den Clustern zugeordnet werden. Lässt man m gegen unendlich laufen, so nähern sich die $u i k$ dem Wert $\frac{1}{C}$ an, d.h. die Zugehörigkeit der Punkte ist zu allen Clustern gleich groß. Liegt m nahe bei 1, so ist das Clustering scharf, d.h. die Zugehörigkeiten liegen näher bei 0 oder 1. In der Praxis haben sich für m Werte zwischen 1 und 2,5 als geeignet herausgestellt (vgl. Stutz (1999)). Die Werte $u i k$ und $v i$ werden durch Minimierung der Zielfunktion J bestimmt. Die Objekte werden den Clustern also so zugeordnet, dass die Summe der quadrierten Abstände $d_{ik}^2$ minimal wird. Die Optimierung findet unter Nebenbedingungen statt:

1.) Für jeden Punkt ist die Summe der Zugehörigkeiten zu allen Clustern gleich 1:

$\sum_{i=1}^C u_{ik}=1, \forall k$

2.) Die Cluster sind nicht-leer:

$\sum_{k=1}^N u_{ik} > 0, \forall i$

Zur Lösung des Minimierungs-Problems wird das Lagrangeverfahren angewandt. Die Lagrangefunktion

$J(U,V,\lambda)=\sum_{i=1}^C \sum_{k=1}^N u_{ik}^{2} d_{ik}^2 -\lambda_{k} \left(\sum_{i=1}^C u_{ik}-1 \right)$

wird nach u,v, und $λ$ abgeleitet. Als Lösung ergibt sich:

$v_i=\frac{\sum_{k=1}^N u_{ik}^m x_k}{\sum_{k=1}^N u_{ik}^m}$ und

$u_{ik}=\frac{1}{\sum_{i=1}^C \left(\frac{d_{ik}}{d_{ij}}\right)^\frac{2}{m-1}}$

Der Algorithmus besteht dann aus den folgenden Schritten:

Initialisiere eine Start-Partitionsmatrix $U 0$
Berechne die Prototypen $V r = [v i]$ im Iterationsschritt r
Berechne die Partitionsmatrix $U r = [u i k]$ im Iterationsschritt r
Falls $\|{U}^r-{U}^{r-1}\|<\varepsilon$ dann Stopp. Sonst zurück zu Schritt 2

Dabei gibt $ε$ einen kleinen Schwellenwert an.

[Bearbeiten] Literatur

Christiane Stutz: Anwendungsspezifische Fuzzy-Clustermethoden (Dissertation zur künstlichen Intelligenz, TU München). Infix, Sankt Augustin 1999.
James C. Bezdek: Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, New York 1981