¿Qué es el agrupamiento en clústeres k-means?

Como se mencionó anteriormente, muchos algoritmos de agrupamiento no se escalan a los conjuntos de datos que se usan en el aprendizaje automático, que a menudo tienen millones de ejemplos. Por ejemplo, los algoritmos de agrupamiento jerárquico aglomerativo o divisivo analizan todos los pares de puntos y tienen complejidades de $O(n^2 log(n))$ y $O(n^2)$, respectivamente.

Este curso se enfoca en k-means porque se escala como $O(nk)$, donde $k$es la cantidad de clústeres que elige el usuario. Este algoritmo agrupa puntos en$k$ clúster minimizando las distancias entre cada punto y el centroide de su clúster (consulta la Figura 1).

Como resultado, k-means trata los datos de manera eficaz como si estuvieran compuestos por una serie de distribuciones aproximadamente circulares y trata de encontrar clústeres que correspondan a estas distribuciones. Sin embargo, los datos del mundo real contienen valores atípicos y clústeres basados en la densidad, y es posible que no coincidan con las suposiciones subyacentes de k-means.

Algoritmo de agrupamiento en clústeres con k-means

El algoritmo sigue estos pasos:

1. Proporciona una suposición inicial para $k$, que se puede revisar más adelante. En este ejemplo, elegimos $k = 3$.

2. Elige $k$ centroides de forma aleatoria.

   

   Figura 1: k-means en la inicialización.

3. Asigna cada punto al centroide más cercano para obtener $k$ clústeres iniciales.

   

   Figura 2: Clústeres iniciales.

4. Para cada clúster, calcula un nuevo centroide tomando la posición media de todos los puntos del clúster. Las flechas de la Figura 4 muestran el cambio en las posiciones del centroide.

   

   Figura 3: Centroides recalculados.

5. Vuelve a asignar cada punto al centroide nuevo más cercano.

   

   Figura 4: Conglomerados después de la reasignación.

6. Repite los pasos 4 y 5, y vuelve a calcular los centroides y la membresía del clúster hasta que los puntos ya no cambien de clúster. En el caso de los conjuntos de datos grandes, puedes detener el algoritmo antes de la convergencia en función de otros criterios.

Debido a que las posiciones de los centroides se eligen inicialmente de forma aleatoria, el algoritmo k-means puede mostrar resultados muy diferentes en ejecuciones sucesivas. Para resolver este problema, ejecuta k-means varias veces y elige el resultado con las mejores métricas de calidad. (Descubriremos las métricas de calidad más adelante en este curso). Necesitarás una versión avanzada de k-means para elegir mejores posiciones iniciales del centroide.

Aunque no es necesario comprender en detalle las matemáticas, para quienes tengan curiosidad, el k-means es un caso especial del algoritmo de maximización de expectativas. Consulta las notas de las clases sobre el tema de la Universidad de Pensilvania.