Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern

K-means und seine scharfe Zuordnung, fuzzy c-means mit Zugehörigkeiten zu allen Clustern, der Fuzzifizierer m, Partitionskoeffizient und Xie-Beni-Index für die Wahl der Clusteranzahl — und warum Ausreißer hohe Zugehörigkeiten bekommen.

13 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 36 von 52

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Was du mitnimmst

Wie k-means funktioniert und was er über Punkte an der Grenze zwischen Clustern verschweigt.
Wie fuzzy c-means Zugehörigkeiten und Zentren berechnet und was der Fuzzifizierer m bewirkt.
Wie man die Anzahl der Cluster wählt und wo fuzzy c-means versagt.

Vorher gut zu wissen: Fuzzy-Mengen und Zugehörigkeitsfunktionen: wie man „etwas warm“ aufschreibt, Arten des maschinellen Lernens: überwacht, unüberwacht, halbüberwacht und mehr

Clustering sucht in Daten nach Gruppen, über die wir vorher nichts wissen: Kunden mit ähnlichem Kaufverhalten, Bereiche gleichen Gewebes in einer Magnetresonanzaufnahme, Dokumente zu einem ähnlichen Thema. Der klassische Algorithmus k-means ordnet jeden Punkt genau einer Gruppe zu. Echte Daten haben aber oft Punkte an der Grenze — einen Kunden, der ein bisschen wie ein Student und ein bisschen wie ein Elternteil einkauft, ein Pixel, in dem graue und weiße Hirnsubstanz aufeinandertreffen. Fuzzy-Clustering erlaubt einem Punkt, zu mehreren Gruppen gleichzeitig zu gehören, zu jeder ein wenig.

Es knüpft an die Teile Fuzzy-Mengen und Zugehörigkeitsfunktionen und Arten des maschinellen Lernens an, wo Clustering als typische Aufgabe des unüberwachten Lernens auftauchte.

1. Scharfes Clustering: k-means

Definition — die k-means-Aufgabe

Seien d ≥ 1 und n ≥ 1 natürliche Zahlen, x₁, …, x_n ∈ ℝ^d Punkte und c ∈ ℕ, 1 ≤ c ≤ n, die Clusteranzahl. Eine Zuordnung ist eine Abbildung shluk : {1, …, n} → {1, …, c}, die dem Punkt x_i die Nummer seines Clusters zuordnet. Für Zentren v₁, …, v_c ∈ ℝ^d und eine Zuordnung shluk sind die Kosten

J(v₁, …, v_c, shluk) = ∑_i=1ⁿ ‖x_i − v_shluk(i)‖²,

wobei ‖·‖ der euklidische Abstand ist (nächste Definition). Die k-means-Aufgabe besteht darin, Zentren und eine Zuordnung zu finden, für die J so klein wie möglich ist.

Lloyd-Algorithmus (Näherungslösung der k-means-Aufgabe). Eingabe: Punkte x₁, …, x_n ∈ ℝ^d und die Clusteranzahl c. Ausgabe: Zentren v₁, …, v_c und eine Zuordnung shluk. Schritte:

Wähle als Anfangszentren c paarweise verschiedene Punkte aus x₁, …, x_n (zufällig).
Zuordnung: Wähle für jedes i = 1, …, n shluk(i) ∈ argmin_{j ∈ {1, …, c}} ‖x_i − v_j‖²; gibt es mehrere nächste Zentren und ist das bisherige Zentrum des Punktes darunter, lass den Punkt in seinem Cluster.
Abbruch: Hat sich die Zuordnung gegenüber dem vorigen Durchlauf nicht geändert, beende und gib die Zentren und die Zuordnung zurück.
Zentren: Bezeichne für jedes j = 1, …, c S_j = {i : shluk(i) = j}, und ist S_j ≠ ∅, setze v_j = 1/|S_j| ∑_{i ∈ S_j} x_i (Mittelwert der Punkte des Clusters; ein leerer Cluster ändert sein Zentrum nicht).
Fahre mit Schritt 2 fort.

Einfach gesagt

Du steckst ein paar „Fahnen“ in die Daten. Jeder Punkt schließt sich der nächsten an. Dann zieht jede Fahne in die Mitte ihrer Punkte um. Die Punkte schließen sich wieder der nächsten Fahne an — und so weiter, bis sich nichts mehr ändert. Jeder Schritt verkleinert J, also endet der Algorithmus sicher, wenn auch nicht unbedingt in der bestmöglichen Aufteilung.

Definition — euklidischer Abstand

Seien d ≥ 1 und x = (x₁, …, x_d), v = (v₁, …, v_d) ∈ ℝ^d. Der euklidische Abstand der Punkte x und v ist die nichtnegative Zahl

‖x − v‖ = √∑_r=1^d (x_r − v_r)².

In der Ebene (d = 2) ist das die gewöhnliche Länge einer Strecke, etwa vom Punkt M1 = (4,5; 2,5) zum Zentrum des Clusters A (1,73; 2,31), wie es fuzzy c-means weiter unten findet: √2,77² + 0,19² ≈ 2,78. Clustering arbeitet mit dem Quadrat ‖·‖² — die Wurzel entfällt, und entfernte Punkte werden stärker bestraft.

def kmeans(X, c):
    V = c zufällig gewählte Punkte aus X          # Anfangszentren
    while True:
        shluk = [argmin_j ‖x − V[j]‖² for x in X]  # Zuordnungsschritt
        if shluk unverändert: return V, shluk
        for j in range(c):                         # Zentrenschritt
            V[j] = Mittelwert der Punkte x mit shluk(x) = j

Satz — der Lloyd-Algorithmus terminiert

Seien x₁, …, x_n ∈ ℝ^d, 1 ≤ c ≤ n, und der Lloyd-Algorithmus laufe nach der Definition oben (einschließlich der Regel, dass ein Punkt bei gleichem Abstand in seinem Cluster bleibt). Dann gilt:

kein Zuordnungsschritt und kein Zentrenschritt vergrößert den Wert J;
der Algorithmus endet nach endlich vielen Durchläufen.

Beweis: Zuordnung: Jeder Summand ‖x_i − v_shluk(i)‖² wird durch den kleinsten aller ‖x_i − v_j‖² ersetzt, wird also nicht größer. Zentren: Für eine nichtleere Indexmenge S eines Clusters mit dem Mittelwert x̄ = 1/|S| ∑_i∈S x_i und ein beliebiges v ∈ ℝ^d gilt die Zerlegung

∑_i∈S ‖x_i − v‖² = ∑_i∈S ‖x_i − x̄‖² + |S| · ‖x̄ − v‖²

(der gemischte Term 2 ∑ (x_i − x̄) · (x̄ − v) ist null, weil ∑ (x_i − x̄) = 0). Die Summe ist also für v = x̄ am kleinsten. Es gibt nur endlich viele Aufteilungen von n Punkten in c Cluster, und J sinkt bei jeder Änderung der Zuordnung echt (bei gleichem Abstand lassen wir den Punkt in seinem Cluster), sodass sich keine Aufteilung wiederholt. ∎

Der Satz sagt nichts darüber, ob die gefundene Aufteilung die mit dem kleinsten J ist — nur dass der Algorithmus nicht in eine Schleife gerät.

Unsere Daten: drei Gruppen zu je 40 Punkten — A links unten, B rechts und C oben —, vier Punkte an der Grenze (M1–M4) und zwei Ausreißer weit weg von allem (O1, O2). K-means hat sich nach vier Iterationen stabilisiert:

k-means: Jeder Punkt gehört genau einem Cluster

Die Cluster hat er gut gefunden, aber die Punkte an der Grenze musste er entscheiden: M1, M3 und M4 kamen zu B, M2 zu A. Dabei liegt M3 fast genau zwischen B und C — k-means sagt darüber nichts. Und beide Ausreißer landeten im Cluster C, als gehörten sie genauso dazu wie sein Kern.

2. Fuzzy c-means

Definition — fuzzy c-means (Dunn 1973, Bezdek 1981)

Seien x₁, …, x_n ∈ ℝ^d Punkte, c ∈ ℕ, 2 ≤ c < n, die Clusteranzahl und m ∈ ℝ, m > 1, der Fuzzifizierer. Eine Zugehörigkeitsmatrix ist eine Matrix U = (u_ij) vom Typ n × c (i = 1, …, n nummeriert die Punkte, j = 1, …, c die Cluster), die erfüllt:

u_ij ∈ [0, 1] für alle i, j;
∑_j=1^c u_ij = 1 für jedes i — jeder Punkt verteilt die Gesamtzugehörigkeit 1 auf die Cluster;
0 < ∑_i=1ⁿ u_ij < n für jedes j — kein Cluster ist leer, und keiner verschluckt alle Punkte vollständig.

Für eine Zugehörigkeitsmatrix U und Zentren V = (v₁, …, v_c) ∈ (ℝ^d)^c sind die Kosten

J_m(U, V) = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖².

Fuzzy c-means ist die Aufgabe, U und V mit den kleinsten Kosten J_m zu finden, und der folgende Algorithmus zu ihrer Näherungslösung. Eingabe: Punkte, c, m, Genauigkeit ε > 0 und die maximale Anzahl der Iterationen. Ausgabe: U und V. Schritte:

Wähle Anfangszentren v₁, …, v_c (z. B. c verschiedene zufällige Punkte).
Zugehörigkeiten: Berechne für alle i, j d_ij = ‖x_i − v_j‖ (wir setzen d_ij > 0 voraus) und u_ij = 1/∑_k=1^c (d_ij/d_ik)^2/(m−1).
Abbruch: Hat sich seit dem vorigen Durchlauf kein u_ij um ε oder mehr geändert oder ist die Anzahl der Iterationen erschöpft, beende (nach dem ersten Durchlauf wird nicht beendet) und gib U und V zurück.
Zentren: Setze für jedes j = 1, …, c v_j = ∑_i=1ⁿ u_ij^m x_i/∑_i=1ⁿ u_ij^m und fahre mit Schritt 2 fort.

Beide Rechenschritte folgen aus den Optimalitätsbedingungen (Satz unten): Jeder minimiert J_m bei fester zweiter Variablengruppe.

Einfach gesagt

Jeder Punkt verteilt seine Eins auf alle Cluster — mehr an den, dem er näher ist. Das Zentrum eines Clusters ist der gewichtete Mittelwert aller Punkte: Punkte, die stark zum Cluster gehören, ziehen es mehr, Punkte aus anderen Clustern nur ganz wenig. Die Formel für die Zugehörigkeit vergleicht Abstände: Ist ein Punkt einem Zentrum doppelt so nah wie dem anderen, bekommt er (bei m = 2) eine viermal größere Zugehörigkeit.

J_m = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖², ∑_j u_ij = 1

J_m: die gesamten „Kosten“ der Aufteilung — der Algorithmus minimiert sie; sie sind klein, wenn die Punkte vor allem zu nahe gelegenen Zentren gehören
∑_i ∑_j: jeder Punkt wird zu jedem Cluster gerechnet — anders als bei k-means, wo nur ein Cluster pro Punkt zählte
u_ij: Zugehörigkeit des Punktes i zum Cluster j — das Gewicht, mit dem der Abstand in die Kosten eingeht
^m: Fuzzifizierer — ohne Potenz (m = 1) lohnte es sich, die ganze Eins dem nächsten Zentrum zu geben, und heraus käme wieder k-means; mit m > 1 lohnt sich das Teilen: Ein Punkt gleich weit von zwei Zentren zahlt bei m = 2 und hälftiger Aufteilung nur (½² + ½²) · d² = ½d² statt d²
‖x_i − v_j‖²: quadrierter Abstand — was es kostet, den Punkt „bei“ diesem Zentrum zu haben; ein entferntes Zentrum wird teuer
∑_j u_ij = 1: Nebenbedingung — ohne sie wäre das Minimum trivial: alle u_ij = 0 und Kosten null

u_ij = 1/∑_k=1^c ( d_ij/d_ik )^2/(m−1)

u_ij: neue Zugehörigkeit des Punktes i zum Cluster j bei festen Zentren
d_ij/d_ik: Abstandsverhältnis — wie viel weiter das Zentrum j entfernt ist als das Zentrum k; das Verhältnis (nicht die Differenz) macht das Ergebnis unabhängig vom Maßstab der Daten
Exponent 2/m − 1: wie scharf das Verhältnis entscheidet — für m = 2 ist es 2, ein doppelt so nahes Zentrum bekommt also viermal so viel; für m → 1 wächst der Exponent über alle Grenzen, und alles bekommt das nächste Zentrum
∑_k: Vergleich mit allen Zentren einschließlich j selbst (der Summand k = j ist 1) — dadurch summieren sich die Zugehörigkeiten eines Punktes genau zu 1

Für m = 2 vereinfacht sich die Formel zu u_ij = 1/d_ij²/∑_k 1/d_ik²: Die Zugehörigkeit ist proportional zum Kehrwert des quadrierten Abstands.

Satz — woher die beiden Schritte kommen

Seien x₁, …, x_n ∈ ℝ^d, c und m > 1 wie in der Definition von fuzzy c-means. Dann gilt:

Für feste Zentren v₁, …, v_c, für die alle Abstände d_ij = ‖x_i − v_j‖ positiv sind, nimmt J_m auf der Menge der Matrizen mit u_ij ≥ 0 und ∑_j u_ij = 1 sein Minimum genau für u_ij = 1/∑_k=1^c (d_ij/d_ik)^2/(m−1) an.
Für eine feste Matrix U, in der ∑_i u_ij^m > 0 für jedes j gilt, nimmt J_m sein Minimum über v₁, …, v_c ∈ ℝ^d genau für v_j = ∑_i u_ij^m x_i/∑_i u_ij^m an.

Beweis. Zugehörigkeiten bei festen Zentren. J_m ist eine Summe über die Punkte, und die Bedingungen betreffen jeweils eine Zeile von U; es genügt also, für einen Punkt i ∑_j u_ij^m d_ij² unter der Nebenbedingung ∑_j u_ij = 1 zu minimieren. Die Lagrange-Funktion ist L = ∑_j u_ij^m d_ij² − λ (∑_j u_ij − 1). Aus ∂L/∂u_ij = m u_ij^m−1 d_ij² − λ = 0 folgt u_ij = (λ/m)^1/(m−1) · d_ij^−2/(m−1). Setzt man das in die Summenbedingung ein, kürzt sich die Unbekannte λ heraus, und es bleibt

u_ij = d_ij^−2/(m−1)/∑_k d_ik^−2/(m−1) = 1/∑_k (d_ij/d_ik)^2/(m−1).

Heraus kommen positive Zahlen, die Bedingung u_ij ≥ 0 muss also nicht eigens überwacht werden. Die Funktion u ↦ u^m d² ist für m > 1 und d > 0 auf [0, 1] streng konvex, dieser einzige stationäre Punkt ist also das Minimum. (Liegt ein Punkt genau im Zentrum, d_ij = 0, bekommt er zu diesem Cluster die Zugehörigkeit 1; unsere Implementierung löst das so, dass der Abstand nie unter 10⁻¹² fällt.)

Zentren bei festen Zugehörigkeiten. J_m ist in v_j eine konvexe quadratische Funktion (streng konvex, weil ∑_i u_ij^m > 0), und ∂J_m/∂v_j = −2 ∑_i u_ij^m (x_i − v_j) = 0 ergibt v_j = ∑_i u_ij^m x_i/∑_i u_ij^m. ∎

Jeder Schritt minimiert also J_m bei fester zweiter Variablengruppe und kann es nicht vergrößern — dasselbe Argument wie bei k-means. Bezdek u. a. (1987, eine Korrektur von Bezdeks ursprünglichem Satz aus dem Jahr 1980) zeigten, dass die Folge Häufungspunkte in stationären Punkten von J_m hat (nicht unbedingt im globalen Minimum).

import numpy as np

def fcm(X, c, m=2.0, iteraci=100, eps=1e-5):
    U = np.random.dirichlet(np.ones(c), size=len(X))        # zufällige Zugehörigkeiten, Zeile = 1
    for _ in range(iteraci):
        W = U ** m
        V = (W.T @ X) / W.sum(axis=0)[:, None]             # Zentren als gewichtete Mittelwerte
        D = np.linalg.norm(X[:, None, :] - V[None, :, :], axis=2) + 1e-12
        nove = 1 / ((D[:, :, None] / D[:, None, :]) ** (2 / (m - 1))).sum(axis=2)
        if np.abs(nove - U).max() < eps:
            return V, nove
        U = nove
    return V, U

3. Fuzzy c-means auf unseren Daten

Die Farbe eines Punktes ist jetzt eine Mischung der Clusterfarben gemäß den Zugehörigkeiten: Ein rein grüner Punkt gehört nur zu A, ein Punkt „zwischen“ Grün und Orange liegt teils in A und teils in B. Die gepunkteten Linien zeigen, wie die Zentren gewandert sind — der Algorithmus hat sich nach neun Iterationen stabilisiert:

Fuzzy c-means (m = 2): Die Farbe ist eine Mischung nach den Zugehörigkeiten

Punkt	k-means	A	B	C
M1 (4,5; 2,5)	B	0,41	0,45	0,15
M2 (3,3; 4,5)	A	0,43	0,18	0,38
M3 (5,8; 5)	B	0,12	0,44	0,45
M4 (4,6; 4)	B	0,28	0,40	0,32

Jetzt sieht man, was k-means verschwiegen hat. M1 liegt fast genau zur Hälfte zwischen A und B; M3 gehört eigentlich um ein Haar mehr zu C als zu B, obwohl k-means ihn B zugeordnet hat; und M4 in der Mitte des Dreiecks gehört ein wenig zu allen dreien. Punkte in den Clusterkernen haben zu ihrem Cluster eine Zugehörigkeit nahe eins. Die Zentren kamen praktisch genauso heraus wie bei k-means — fuzzy c-means ändert nicht, wo die Cluster liegen, sondern liefert die Information, wie sicher welcher Punkt zu ihnen gehört.

Beispiel — Zugehörigkeiten des Punktes M1 = (4,5; 2,5)

Zentren nach neun Iterationen: A ≈ (1,73; 2,31), B ≈ (7,12; 2,87), C ≈ (4,51; 7,11). Für m = 2 genügen die Kehrwerte der quadrierten Abstände (Farben nach der vereinfachten Formel für m = 2 in der Bildunterschrift oben):

Cluster	`d`²	1/`d`²	`u` = 1/`d`²/0,3190
A	2,77² + 0,19² ≈ 7,72	0,1296	0,41
B	2,62² + 0,37² ≈ 7,03	0,1423	0,45
C	0,01² + 4,61² ≈ 21,25	0,0471	0,15
Summe		0,3190	1,00

M1 ist von den Zentren A und B fast gleich weit entfernt (7,72 gegenüber 7,03) und teilt sich deshalb fast hälftig zwischen ihnen auf; C ist dreimal so weit weg (im Quadrat) und bekommt nur den Rest.

4. Der Fuzzifizierer m

Definition — Partitionskoeffizient

Seien n ≥ 1, c ≥ 2 und U = (u_ij) eine Matrix vom Typ n × c mit u_ij ∈ [0, 1] und ∑_j=1^c u_ij = 1 für jedes i (eine Zugehörigkeitsmatrix). Der Partitionskoeffizient (partition coefficient) ist die Zahl

PC(U) = 1/n ∑_i=1ⁿ ∑_j=1^c u_ij².

Stets gilt 1/c ≤ PC(U) ≤ 1, wobei

PC(U) = 1 genau dann, wenn die Aufteilung scharf ist: In jeder Zeile ist ein u_ij = 1 und die übrigen 0;
PC(U) = 1/c genau dann, wenn u_ij = 1/c für alle i, j — jeder Punkt gehört zu allen Clustern gleich stark.

(Für jede Zeile ist ∑_j u_ij² ≤ ∑_j u_ij = 1 mit Gleichheit nur für die Werte 0 und 1, und nach der Cauchy-Schwarz-Ungleichung ist ∑_j u_ij² ≥ 1/c (∑_j u_ij)² = 1/c mit Gleichheit nur für gleiche Werte.)

Einfach gesagt

Eine Zahl, die sagt, wie „scharf“ die Aufteilung ist. Bei drei Clustern liegt sie zwischen 1/3 (alles ist verschwommen) und 1 (jeder Punkt hat ein klares Zuhause).

PC = 1/n ∑_i ∑_j u_ij²

PC: Schärfe der gesamten Aufteilung, eine Zahl aus [1/c; 1]
1/n ∑_i: Mittelwert über die Punkte — damit sich Datensätze unterschiedlicher Größe vergleichen lassen
∑_j u_ij²: Schärfe eines einzelnen Punktes — das Quadrat „belohnt“ eine konzentrierte Zugehörigkeit: (1, 0, 0) ergibt 1, (⅓, ⅓, ⅓) nur ⅓; bei fester Summe 1 ist die Quadratsumme am kleinsten, wenn alle Anteile gleich sind

Der Punkt M1 mit den Zugehörigkeiten (0,41; 0,45; 0,15) trägt 0,41² + 0,45² + 0,15² ≈ 0,39 bei; Punkte aus den Clusterkernen fast 1 — der Mittelwert über alle 126 Punkte ist 0,84.

Fuzzy c-means für m = 1,2; 2 und 5

Für m nahe 1 nähert sich fuzzy c-means an k-means an: Der Partitionskoeffizient ist 0,98, und der Punkt M4 gehört zu 0,79 zu B. Für m = 2 ist der Koeffizient 0,84 und für m = 5 nur 0,42 — die Farben verschwimmen, und selbst ein Punkt aus dem Kern des Clusters A hat zu A nur die Zugehörigkeit 0,45. Für m → ∞ gingen alle Zugehörigkeiten gegen 1/3. Am häufigsten verwendet man m = 2: weich genug, damit die Punkte an der Grenze sichtbar werden, und scharf genug, damit die Cluster deutlich bleiben.

Beispiel — ein Punkt, der einem von zwei Zentren doppelt so nah ist

Ein Punkt hat zum Zentrum 1 den Abstand 1 und zum Zentrum 2 den Abstand 2. In der Formel für die Zugehörigkeit ist der Summand k = 1 gleich 1, und der Summand k = 2 hat das Verhältnis 1/2, also ist u₁ = 1/1 + (1/2)^2/(m−1) (Farben nach der Formel für u_ij oben):

m = 1,2: Exponent 10, u₁ = 1/1 + 1/1 024 ≈ 0,999 — praktisch eine scharfe Zuordnung,
m = 2: Exponent 2, u₁ = 1/1 + 1/4 = 0,8,
m = 5: Exponent 0,5, u₁ = 1/1 + 0,707 ≈ 0,586,
m → ∞: Exponent → 0, (1/2)⁰ = 1 und u₁ → 1/2.

Allgemein: Für m → 1⁺ geht der Exponent 2/m − 1 gegen unendlich, Verhältnisse d_ij/d_ik < 1 gehen gegen null und solche > 1 gegen unendlich, sodass das nächste Zentrum 1 bekommt und die übrigen 0 (k-means). Für m → ∞ geht der Exponent gegen null, alle c Summanden gehen gegen 1, und u_ij → 1/c.

5. Wie viele Cluster?

Die Anzahl der Cluster müssen wir dem Algorithmus vorgeben. Wenn wir sie nicht kennen, lassen wir ihn für verschiedene c laufen und vergleichen die Güte der Aufteilungen. Dafür eignen sich der Partitionskoeffizient und der Xie-Beni-Index.

Definition — Xie-Beni-Index

Seien x₁, …, x_n ∈ ℝ^d, c ≥ 2, m > 1, U = (u_ij) eine Zugehörigkeitsmatrix vom Typ n × c und v₁, …, v_c ∈ ℝ^d paarweise verschiedene Zentren (typischerweise das Ergebnis von fuzzy c-means). Der Xie-Beni-Index ist die Zahl

XB(U, V) = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖²/n · min_{j ≠ k} ‖v_j − v_k‖².

Der Nenner ist positiv, weil die Zentren verschieden sind. Xie und Beni (1991) führten den Index mit dem Exponenten 2 ein (also für m = 2); mit allgemeinem m wird er üblicherweise in derselben Form verwendet. Beim Vergleich von Aufteilungen ist die mit dem kleineren XB besser.

Einfach gesagt

Der Zähler misst, wie eng die Punkte bei ihren Zentren liegen; der Nenner, wie weit die zwei nächstgelegenen Zentren voneinander entfernt sind. Eine gute Aufteilung hat kompakte Cluster, die weit auseinanderliegen.

XB = ∑_i ∑_j u_ij^m ‖x_i − v_j‖²/n · min_{j ≠ k} ‖v_j − v_k‖²

XB: Verhältnis der Streuung innerhalb der Cluster zum Abstand zwischen ihnen — kleiner ist besser
∑ ∑ u_ij^m ‖x_i − v_j‖²: Kompaktheit — genau der Wert J_m, den der Algorithmus minimiert hat
n: Anzahl der Punkte — macht aus dem Zähler einen Mittelwert pro Punkt, damit der Index nicht mit der Datenmenge wächst
min_{j ≠ k} ‖v_j − v_k‖²: Trennung — entscheidend ist das nächstgelegene Zentrenpaar; J_m allein sinkt mit zunehmender Clusterzahl nur, und dieser Term bestraft eine Aufteilung, die einen echten Cluster in zwei nahe beieinanderliegende spaltet

Beispiel — Xie-Beni-Index für c = 3

Nach dem Ende des Algorithmus ist J₂ ≈ 166,73. Quadrierte Abstände der Zentren: A–B ≈ 29,4, A–C ≈ 30,8, B–C ≈ 24,79 (am nächsten liegen B und C). Für n = 126 Punkte (Farben nach der Formel oben):

XB = 166,73/126 · 24,79 = 166,73/3 124 ≈ 0,053.

Clusteranzahl `c`	2	3	4	5	6
Partitionskoeffizient (größer ist besser)	0,745	0,841	0,748	0,661	0,609
Xie-Beni-Index (kleiner ist besser)	0,228	0,053	0,298	0,682	0,529

Beide Kennzahlen einigen sich auf die drei Cluster, die wir in die Daten gelegt haben. Bei echten Daten ist eine solche Übereinstimmung nicht selbstverständlich, und die Kennzahlen sind eher ein Wegweiser als ein Urteil.

6. Wo fuzzy c-means versagt

Sieh dir die Ausreißer an: O1 rechts oben hat zu C die Zugehörigkeit 0,45 und zu B 0,39; O2 links oben sogar 0,58 zu C. Dabei gehören sie zu keinem Cluster. Schuld ist die Bedingung ∑_j u_ij = 1: Ein Punkt muss seine Eins jemandem geben, auch wenn er von allen weit entfernt ist. Zugehörigkeit bedeutet hier eher „wem er am nächsten ist“ als „wie gut er hierher gehört“.

Beispiel — warum O2 = (0,2; 9,5) zu C „gehört“

Quadrierte Abstände zu den Zentren: A ≈ 54,07, B ≈ 91,88, C ≈ 24,29. Selbst vom nächsten Zentrum C ist er also 4,9 entfernt — mehr als das Sechsfache der Standardabweichung 0,8, mit der die Clusterpunkte um ihre Zentren gestreut sind. Nach der Formel für m = 2 (Farben nach der Bildunterschrift zur Formel für u_ij) ergeben die Kehrwerte 1/54,07 ≈ 0,0185, 1/91,88 ≈ 0,0109 und 1/24,29 ≈ 0,0412 die Summe 0,0706 und die Zugehörigkeiten

u_A = 0,0185/0,0706 ≈ 0,26, u_B = 0,0109/0,0706 ≈ 0,15, u_C = 0,0412/0,0706 ≈ 0,58.

Die Formel sieht nur die Verhältnisse der Abstände, nicht ihre Größe: Je weiter der Punkt läge, desto mehr näherten sich die Verhältnisse 1 und die Zugehörigkeiten 1/3 — gegen null gingen sie aber nie.

Definition — possibilistisches c-means (Krishnapuram und Keller, 1993)

Seien x₁, …, x_n ∈ ℝ^d, c ≥ 1, m > 1, v₁, …, v_c ∈ ℝ^d Zentren, d_ij = ‖x_i − v_j‖ und η₁, …, η_c > 0 im Voraus gewählte Parameter (meist aus dem Ergebnis von fuzzy c-means geschätzt). Possibilistisches c-means sucht eine Matrix U = (u_ij) vom Typ n × c mit u_ij ∈ [0, 1] — ohne die Bedingung ∑_j u_ij = 1 — und Zentren, die die Kosten

J(U, V) = ∑_i=1ⁿ ∑_j=1^c u_ij^m d_ij² + ∑_j=1^c η_j ∑_i=1ⁿ (1 − u_ij)^m

minimieren. Der zweite Term verhindert die triviale Lösung U = 0. Bei festen Zentren liegt das Minimum bei

u_ij = 1/1 + (d_ij²/η_j)^1/(m−1),

die Zentren werden genauso berechnet wie bei fuzzy c-means. η_j ist der „Radius“ des Clusters j: Ein Punkt im Abstand d² = η_j hat die Zugehörigkeit 1/2, für m = 2 ein Punkt mit d² = 9η_j nur 1/1 + 9 = 0,1. Die Zugehörigkeit hängt jetzt vom Abstand zu einem einzigen Zentrum ab, nicht vom Verhältnis zu den anderen — ein Ausreißer bekommt überall kleine Werte.

Possibilistisches c-means (Krishnapuram und Keller, 1993) hebt die Summenbedingung auf — ein Ausreißer bekommt dann zu allen Clustern kleine Zugehörigkeiten.
Form der Cluster. Der euklidische Abstand erzeugt runde Cluster. Der Algorithmus von Gustafson und Kessel (1979) gibt jedem Cluster eine eigene Abstandsmatrix und findet auch langgestreckte Ellipsen.
Anfangslage. Genau wie k-means kann er in einem schlechteren lokalen Minimum enden — in der Praxis lässt man ihn mehrmals von verschiedenen Startpunkten laufen.

7. Fuzzy-Clustering in der Praxis

Medizinische Bilder. Die Segmentierung von MRT-Aufnahmen des Gehirns in graue Substanz, weiße Substanz und Liquor ist eine klassische Anwendung: Ein Pixel an der Gewebegrenze enthält tatsächlich beides.
Kundensegmentierung. Ein Kunde kann teilweise zu mehreren Gruppen gehören, und das Marketing kann damit rechnen.
Der probabilistische Verwandte. Gaußsche Mischmodelle, gelernt mit dem EM-Algorithmus, ordnen Punkte ebenfalls „weich“ Clustern zu — allerdings mit Wahrscheinlichkeiten, nicht mit Zugehörigkeiten. Die Ergebnisse sind oft ähnlich, die Deutung unterscheidet sich genau so, wie es der Teil über Fuzzy-Logik und Wahrscheinlichkeit beschrieben hat.
Embeddings. Texte, die ein Sprachmodell in Vektoren umgewandelt hat, lassen sich genauso clustern; die weiche Zuordnung zeigt dann Dokumente, die zwischen Themen liegen.

8. Zusammenfassung

K-means ordnet jeden Punkt genau einem Cluster zu und sagt über Punkte an der Grenze nichts.
Fuzzy c-means sucht Zugehörigkeiten u_ij mit Summe 1 und Zentren als gewichtete Mittelwerte; er wechselt zwei einfache Schritte ab.
Auf unseren Daten fand er dieselben Zentren wie k-means und zeigte zusätzlich, dass die Punkte M1–M4 zu zwei oder drei Clustern gleichzeitig gehören.
Der Fuzzifizierer m steuert, wie weich die Aufteilung ist; Partitionskoeffizient und Xie-Beni-Index helfen bei der Wahl der Clusteranzahl.
Die Summenbedingung 1 gibt Ausreißern hohe Zugehörigkeiten; possibilistische Varianten lösen das.

Willst du es selbst ausprobieren? Lass einen KI-Agenten fuzzy c-means auf die Pixelfarben eines eigenen Fotos anwenden und es nach den Clustern einfärben — und sieh dir an, welche Pixel „zwischen“ den Farben liegen.

Siehst du das anders? Schreib an support@coden-app.com.

Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern

1. Scharfes Clustering: k-means

2. Fuzzy c-means

3. Fuzzy c-means auf unseren Daten

4. Der Fuzzifizierer m

5. Wie viele Cluster?

6. Wo fuzzy c-means versagt

7. Fuzzy-Clustering in der Praxis

8. Zusammenfassung

Ein Agent auf deinem Rechner, vom Telefon aus gesteuert