Wikipedia · einfach zusammengefasst · Stand
Fuzzy-c-Means-Algorithmus
In der Informatik ist der Fuzzy-c-Means-Algorithmus, auch Algorithmus der c unscharfen Mittelwerte, ein unüberwachter Clustering-Algorithmus, der eine …
Inhalt5 Abschnitte
Überblick und Grundidee
Der Fuzzy-c-Means-Algorithmus ist ein unüberwachter Clustering-Algorithmus der Informatik und eine Erweiterung von k-Means. Er teilt Datenobjekte in eine vorher festgelegte Zahl C von Clustern ein. Anders als bei k-Means wird ein Objekt dabei nicht genau einem Cluster zugewiesen, sondern erhält für jeden Cluster einen Zugehörigkeitsgrad beziehungsweise ein Gewicht. Die generalisierte Form des Algorithmus wurde von Bezdek (1981) vorgestellt.
Beim k-Means-Verfahren werden zunächst zufällige Clusterzentren gewählt. Jedes Objekt wird dem nächstgelegenen Zentrum zugeordnet; anschließend werden die quadrierten Abstände aufsummiert und die Zentren aus den zugeordneten Objekten neu berechnet. Diese Schritte werden wiederholt, bis eine stabile Lösung erreicht ist. Ziel ist, die Summe J_kmeans der quadrierten Abstände möglichst klein zu machen. Ein Nachteil ist die harte, eindeutige Zuordnung: Das Ergebnis kann stark von den anfänglichen Zentren abhängen.
Unscharfe Zugehörigkeiten
Fuzzy-c-Means ersetzt die harte Zuordnung durch Gewichte (u_1i, …, u_Ci). Sie geben an, wie stark ein Objekt zu den einzelnen Clustern gehört. Für ein Objekt können beispielsweise die Werte u_blau = 0,1, u_grün = 0,1 und u_rot = 0,8 gelten. Ein Objekt nahe an der Grenze zweier Cluster kann dagegen etwa u_blau = 0,5, u_grün = 0,45 und u_rot = 0,05 erhalten.
Die Gewichte sind Fuzzy-Zahlen und werden zur Berechnung gewichteter Abstände zu allen Clusterzentren verwendet. Objekte nahe bei einem Zentrum erhalten normalerweise ein großes Gewicht für dessen Cluster. Die Gewichte müssen sich laut Grundidee nicht zwingend zu 1 addieren; in der mathematischen Beschreibung gilt jedoch als Nebenbedingung, dass ihre Summe für jeden Punkt 1 beträgt.
Zielfunktion und Einfluss des Fuzzifiers
Für jedes Objekt x_k (k = 1, …, N) und jeden Cluster i (i = 1, …, C) beschreibt u_ik im Intervall [0, 1] den Grad der Zugehörigkeit. Je größer u_ik ist, desto stärker gehört x_k zu Cluster i.
Die Zielfunktion lautet:
J(U,V) = Σ_i=1^C Σ_k=1^N u_ik^m d_ik².
Dabei ist d_ik² = (x_k − v_i)^T(x_k − v_i) der quadrierte euklidische Abstand zwischen Punkt x_k und Clusterzentrum beziehungsweise Prototyp v_i. U ist die Partitionsmatrix der Zugehörigkeitsgrade, V die Matrix der Prototypen, C die Clusterzahl und N die Größe des Datensatzes.
Der Fuzzifier m > 1 steuert die Schärfe der Zuordnung. Für m gegen unendlich nähern sich alle u_ik dem Wert 1/C; ein Punkt gehört dann gleich stark zu allen Clustern. Liegt m nahe bei 1, sind die Zugehörigkeiten näher bei 0 oder 1 und das Clustering ist schärfer. In der Praxis gelten Werte zwischen 1 und 2,5 als geeignet.
Berechnung und Ablauf
U und V werden so bestimmt, dass J minimal wird. Dabei gelten zwei Nebenbedingungen: Für jeden Punkt k ist Σ_i=1^C u_ik = 1, und kein Cluster darf leer sein, also gilt für jedes i: Σ_k=1^N u_ik > 0.
Mit dem Lagrangeverfahren ergeben sich die Aktualisierungen:
v_i = (Σ_k=1^N u_ik^m x_k) / (Σ_k=1^N u_ik^m)
u_ik = 1 / [Σ_j=1^C (d_ik / d_jk)^(2/(m−1))].
Der Algorithmus startet mit einer Partitionsmatrix U^0. In Iteration r werden zuerst die Prototypen V^r und danach die Partitionsmatrix U^r berechnet. Er endet, wenn ||U^r − U^(r−1)|| < ε gilt; ε ist ein kleiner Schwellenwert. Andernfalls werden die Schritte wiederholt.
Beispiel mit Schweizer Banknoten
Der Schweizer Banknoten-Datensatz enthält 100 echte und 100 gefälschte Schweizer 1000-Franken-Banknoten. Erfasst wurden sechs Variablen: WIDTH (Breite), LEFT (Höhe links), RIGHT (Höhe rechts), UPPER (Abstand des farbigen Drucks zur Oberkante), LOWER (Abstand zur Unterkante) und DIAGONAL (Diagonale des farbigen Drucks von links unten nach rechts oben).
Bei der Darstellung auf den ersten beiden Hauptkomponenten bildet ein kompakter Cluster rechts die echten Banknoten; die übrigen sind gefälscht. Beim k-Means-Clustering wurden echte und falsche Banknoten fast richtig klassifiziert, nur eine falsche Banknote wurde dem blauen Cluster zugeordnet. Das Clustering selbst verwendete alle sechs Variablen, die Grafik zeigt aber nur zwei Dimensionen.
Beim Fuzzy-c-Means-Clustering werden mehr Beobachtungen dem Cluster der echten Banknoten zugeordnet. Dies wirkt zunächst schlechter. Kleine Datenpunkte in der Grafik bedeuten jedoch unsichere Zuordnung: Für Punkte unten in der Mitte liegen die Zugehörigkeitswerte in beiden Clustern bei etwa 0,5. Die echten Banknoten wurden von einer Vorlage, also einer Druckplatte, gedruckt; die Fälschungen stammen aus verschiedenen Quellen und wahrscheinlich von verschiedenen gefälschten Druckplatten.
