K-means

K-means es uno de los mejores algoritmos de Clustering particional.

Dado un conjunto de puntos y un número $k$ de clusters a identificar, el algoritmo particiona iterativamente el conjunto de puntos. Sea el conjunto de puntos o instancias $D=\{{\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_{\mathbf{n}}\}$ donde ${\mathbf{x}}_{\mathbf{i}}$ es un vector en un espacio euclidiano y $r$ es el número de atributos de la instancia o dimensiones del espacio, tal que ${\mathbf{x}}_{\mathbf{i}}=({\mathbf{x}}_{i1},{\mathbf{x}}_{i2},\dots ,{\mathbf{x}}_{\mathbf{ir}})$. El centroide de un cluster es la media de todos los puntos del cluster.

Una vez que todos los puntos del dataset han sido asignados a un cluster, se recalcula el centroide de cada cluster utilizando los puntos que corresponden a cada cluster. Esto se repite hasta alcanzar un criterio de parada:

• Hasta que ya no hay reasignación de datos en los diferentes clusters.
• Hasta que ya no hay cambios en los centroides.
• Hasta que se alcanzó un mínimo en la suma de errores cuadráticos:

$$\begin{gathered} SSE={\sum }_{j=1}^k{\sum }_{x \\ in{C}_j}\text{dist}(\mathbf{x},{\mathbf{m}}_{\mathbf{j}}{)}^2 \end{gathered}$$

K-means se puede usar siempre que se pueda calcular una media. Siendo $|C_j|$ el número de puntos en el cluster $C_j$, la media en el espacio euclidiano es:

${\mathbf{m}}_{\mathbf{j}}=\frac{1}{|{\mathbf{C}}_{\mathbf{j}}|}{\sum }_{{\mathbf{x}}_{\mathbf{i}}\in {\mathbf{C}}_{\mathbf{j}}}{\mathbf{x}}_{\mathbf{i}}$

La distancia de cada dato al centroide se calcula como:

$$\begin{array}{rl}\text{dist}({\mathbf{x}}_{\mathbf{i}},{\mathbf{m}}_{\mathbf{i}})& =||{\mathbf{x}}_{\mathbf{i}}-{\mathbf{m}}_{\mathbf{j}}||\\ & =\sqrt{(x_{i1}-m_{j1}{)}^2+\dots (x_{ir}-m_{jr}{)}^2}\end{array}$$

Algoritmo

$$\begin{array}{rl}& \text{Algorithm }k\text{-}means(k,D)\\ & \text{choose }k\text{ data points as the initial centroids (cluster centers)}\\ & \text{repeat}\\ & \text{for each data point }x\in D\text{ do}\\ & \text{compute the distance from }x\text{ to each centroid;}\\ & \text{assign }x\text{ to the closest centroid}\\ & \text{endfor}\\ & \text{re-compute the centroid using the current cluster memberships}\\ & \text{until }\text{the stopping criterion is met}\end{array}$$

La bibliografía recomienda ejecutar el algoritmo con al menos 500 iteraciones.

Existe una variante k-modes (usa modas en lugar de medias) para casos en los que no se pueda usar la media. La media también es sensible a los outliers.

Elegir las semillas o centroides iniciales de manera aleatoria puede distorsionar negativamente los clusters que el modelo creará (similar a encerrarlo en mínimos locales). Una heurística simple consiste en:

1. Calcular la media del dataset para que la primera semilla sea el punto más alejado de la media.
2. La segunda semilla será el punto más alejado de la primera semilla.
3. Los puntos sucesivos serán elegidos de manera que su distancia a los puntos ya seleccionados sea la máxima. Este método es empeora si existen outliers.