kmeans.tex

K-means punta a creare $K$ gruppi distinti di uguale varianza, con $K$, ovvero il numero di cluster richiesti, definito a priori.

L'algoritmo si può riassumere in questi punti:
\begin{algorithm}
	\begin{algorithmic}[1]
  		\caption{K-means}
		\State Seleziona K punti come centroidi.
		\Repeat
			\State Forma K cluster assegnando ogni elemento al centroide più vicino.
			\State Ricalcola i centroidi per ogni cluster.
		\Until{I centroidi non cambiano posizione (con possibile errore $\sim$ 1\%).}
  	\end{algorithmic}
\end{algorithm}

Solitamente, la scelta iniziale della posizione dei $K$ centroidi viene presa in modo casuale. In alcuni casi è conveniente utilizzare altre tecniche: ad esempio, se il numero di elementi si aggira attorno ad alcune centinaia di punti e se $K$ è relativamente piccolo rispetto alla dimensione del cluster, si può utilizzare il clustering gerarchico fino a definire $K$ cluster ed utilizzare i centroidi di questi cluster come i centroidi dell'intero sistema.

Tuttavia, per assegnare ogni elemento ad un centroide si ha bisogno di una misura in grado di quantificare il concetto di ``vicinanza''. Considerando che esistono diverse tipologie di dato che ipoteticamente si potrebbero clusterizzare, si ha bisogno di diverse funzioni per calcolare queste vicinanze: la distanza euclidea, conosciuta come $L2$, è solitamente utilizzata per dati rappresentabili su spazio euclideo; per la distanza tra documenti, invece, ha più senso utilizzare il $coseno\ di\ similitudine$.

Nel caso di dati rappresentabili su spazio euclideo misuriamo la qualità di un cluster utilizzando \emph{SSE}, ovvero lo scarto quadratico medio. Il compito dell'algoritmo è di minimizzare quest'errore. Possiamo definire SSE come segue:

\begin{equation*}
	SSE = \sum_{i=1}^{K}{\sum_{x \in C_i} {dist(c_i, x)^2}}
\end{equation*}
dove \emph{dist} è la distanza euclidea, $C_i$ è l'$i$-esimo cluster e $c_i$ è l'$i$-esimo centroide.

Si può dimostrare che il centroide che minimizza lo scarto quadratico medio del cluster è ottimale. Il centroide dell'$i$-esimo cluster è definito come segue:
\begin{equation*}
	c_i = \frac{1}{m_i} \sum_{x \in C_i}{x}
\end{equation*}
dove $m_i$ è il numero di oggetti nell'$i$-esimo cluster.

Nel caso di documenti, invece, si deve massimizzare la similarità tra i documenti presenti in un cluster; questo valore viene detto \emph{coesione} del cluster, l'analogo dello scarto quadratico medio, e viene calcolato come segue:

\begin{equation*}
	Total\ Cohesion = \sum_{i=1}^{K}{\sum_{x \in C_i} {cos(x, c_i)}}
\end{equation*}
dove \emph{cos} è il $coseno\ di\ similitudine$.

In ogni caso l'algoritmo termina quando i centroidi assumono uno stato di fermo\cite{k-means}.