k-Means

Toma como parámetro $k$ que es el número de clusters que forma.

Selecciona $k$ elementos aleatoriamente, los cuales representan el centro o media de cada cluster. A cada objeto restante se le asigna el cluster con el cual más se parece, basandose en una distancia entre el objeto y la media del cluster. Despúes calcula la nueva media del cluster e itera hasta no cambiar de medias.

Tabla 10.1: Algoritmo de k-means.

Normalmente se utiliza un medida de similaridad basada en el error cuadrático:

$$E = \sum_{i=1}^k \sum_{p \in C_i} \vert p - m_i\vert^2$$

donde: $p$ representa al objeto y $m_i$ a la media del cluster $C_i$ (ambos son objetos multidimensionales).

$k$-means es susceptible a valores extremos porque distorcionan la distribución de los datos.

Tambíen se pueden utilizar las modas ($k$-modes) para agrupar objetos categóricos.

Otra posibilidad es usar medianas ($k$-medoids) para agrupar en base al objeto más representativo del cluster. La idea básica es encontrar un objeto representativo. La estrategia es reemplazar una de las medianas por otro objeto en forma aleatoria y medir si la calidad de los clusters resultantes mejoran.

La calidad se evalúa con base a una función de costo que mide la disimilaridad promedio entre un objeto y la mediana en su cluster.

Para ver si un objeto aleatorio ($O_{alea}$) es un buen reemplazo de la mediana ($O_{actu}$) se consideran todos los objetos que no sean medianas y se analiza la re-distribución de los objetos a partir de la cual se calcula un costo basado, por ejemplo, en el error cuadrático. Esto se repite hasta que no exista mejora.

Cómo en muchos de los métodos vistos, este no garantiza encontrar el mínimo global, por lo que se recomiendo correr varias veces el algoritmo con diferentes valores iniciales.

Otra variante es hacer un $k$-means jerárquico, en donde se empieza con $k=2$ y se continua formando clusters sucesivos en cada rama.

Si queremos escalarlo a grandes bases de datos, podemos tomar únicamente muestras de los datos.