Verfahren zur Zuordnung von Objekten einer gebenen Menge Q in unscharfe Cluster \(\tilde{Q}_{k}\).

Dabei wird die gegebene Menge Q = {O₁, …, O_N} von Objekten O_j so in Fuzzy-Teilmengen \(\tilde{Q}_{1},\ldots,\tilde{Q}_{n}\ \mathrm{mit}\ \tilde{Q}_{k}=\{(O_{j},\mu_{Q_{k}}(O_{j})\vert O_{j} \in Q\}\) zerlegt, daß

• \(\begin{eqnarray}\displaystyle \underset{k=1}{\overset{n}{\cup }}\text{supp}({\tilde{Q}}_{j})=Q\end{eqnarray}\) und
• \(\begin{eqnarray}\displaystyle \sum _{k=1}^{n}\mu {Q}_{k}({O}_{j})=1\end{eqnarray}\) für alle Objekte \(O_{j} \in Q\).

In der Literatur existieren zahlreiche Verfahren zur Clusterbildung, deren Brauchbarkeit vom gegebenen Kontext abhängt. Eine der bekanntesten Methoden ist das von Bezdek (1981) entwickelte Iterationsverfahren ISODATA-FCM, das hier beispielhaft dargestellt wird:

Voraussetzung ist, daß sich die Objekte O_j durch ihre Merkmalsvektoren \(\mathbf{x}_{j}=(x_{1j},\ldots,x_{mj})^{T}\in \mathbb{R}^{m}\) beschreiben lassen und im ℝ^m eine Norm ||x-y|| existiert.

Schritt 1

Man wählt die gewünschte Clusteranzahl n, n< N, und einen Exponenten p ∈ [0, +∞).

Dann wählt man eine Ausgangsmatrix U⁽⁰⁾ = {u_jk} mit \begin{align} & u_{jk}=\mu_{Q_{k}}(O_{j}),\\ & \sum_{k=1}^{n}u_{jk}=1,\\ & 0<\sum_{k=1}^{N}u_{jk}\lt N. \end{align}

Man setze die Iterationsnummer r gleich 0.

Schritt 2

Berechnung der Clusterzentren \(\mathbf{v}^{(r)}_{k}\) gemäß der Formel \begin{equation} \mathbf{v}^{(r)}_{k}=\frac{\sum_{j=1}^{N}\left(u_{jk}^{(r)}\right)^{p}\cdot \mathbf{x}_{j}}{\sum_{j=1}^{N}\left(u_{jk}^{(r)}\right)^{p}}. \end{equation}

Schritt 3

Man berechne U^(r+1) gemäß der folgenden Vorschrift: \begin{align} & I_{j}=\{k\in\{1,\ldots,n\}\vert \Vert \mathbf{x}_{j}-\mathbf{v}_{k}^{(r)}\Vert=0\},\\ & C(I_{j})=\{1,\ldots,n\}/I_{j}, \end{align} für alle j = 1,…,N.

Ist I_j = ∅, so setze man \begin{equation} u^{(r+1)}_{jk}=\left[\sum_{s=1}^{n}\left(\frac{\Vert\mathbf{x}_{j}-\mathbf{v}_{k}^{(r)} \Vert}{\Vert\mathbf{x}_{j}-\mathbf{v}_{s}^{(r)} }\right)^{\frac{2}{n-1}}\right]^{-1} \end{equation}Ist I_j ≠ ∅,, so setze man \begin{equation} u_{jk}^{(r+1)}=0\,\,\ \mathrm f\ddot{\mathrm u}\mathrm r\ \mathrm{jedes}\ k\in C(I_{j}) \end{equation} und wähle die übrigen \(u_{jk}^{(r+1)}\) so, daß \begin{equation} \sum_{k\in I_{j}}u_{jk}^{(r+1)}=1. \end{equation}

Schritt 4

Wähle eine zu || · || passende Matrixnorm und ein ϵ > 0.

Falls ||U^(r+1) − U^(r) ≤ ϵ, dann beende man das Iterationsverfahren mit U^(r+1), andernfalls fahre man mit Schritt 2 fort.