k-Means-Algorithmus

Einfache Sprache

Def. k-Means-Algorithmus

Gegeben sei das Clusterproblem. Dazu seinen $k\in\mathbb N$ Gruppen $\{C_1,\ldots,C_k\}$ definiert durch jeweils einen Punkt $\{c_1,\ldots,c_k\}$. Ziel ist es die Kosten $K$, definiert durch

$$K = \sum_{i=1}^l\sum_{x\in C_i}(x-c_i)^2\;,$$

zu minimieren. Um einen optimale Lösung zu finden wenden wir einen Greedy-Algorithmus an. Dabei werden Abstrakt meist die folgenden Schritte abgearbeitet:

1. Wähle $k$ zufällige Punkte für $\{c_1,\ldots,c_k\}$.
2. Ordne jeden Datenpunkte zu dem nähstem Cluster zu.
3. Passe die Cluster an, basierend auf den Datenpunkten im Cluster.

Dabei wrid 2. und 3. solange wiederholt bis sich die Cluster nicht mehr ändern.

Lloyd-Algorithmus

Die häufigste Variante von $k$-Means.

	\begin{algorithm}
	\caption{Lloyd-Algorithmus}
	\begin{algorithmic}
	\Input Database $D$,$k\in\mathbb N$
	\State Wähle $k$ zufälle Punkte $\{c^{(1)}_1,\ldots,c^{(1)}_k\}$.
	\State $t \gets 1$
	\While{$\mathrm{TRUE}$}
		\State $t\gets t+1$
		\ForAll{$o\in D$}
			\State Finde $i\in[0,1]$ so, das $||o-c^(t)_i||^2$ minimal ist.
			\State $C^{(t)}_i \gets C^{(t)}_i \cup o$
	    \EndFor
	    \State $c^{(t+1)}_i \gets \frac{1}{C^{(t)}_i}\sum_{o\in C^{(t)}_i}o$
	    \State Break wenn sich zwischen $c^{(t1)}_i$ und $c^{(t+1)}_i$ nicht mehr signifikant was ändert.
    \EndWhile
	\end{algorithmic}
	\end{algorithm}

Die Durchschnittslaufzeit von $k$-Means ist $\mathcal O(t\cdot k \cdot n)$, wobei $t$ die anzahl der Schleifendurchläufe ist.