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

Como se mencionó anteriormente, muchos algoritmos de agrupamiento en clústeres no escalan a los conjuntos de datos. que se usan en el aprendizaje automático y que suelen tener millones de ejemplos. Por ejemplo: los algoritmos de agrupamiento en clústeres jerárquico aglomerativo o divisivo analizan todos los pares de puntos y tienen la complejidad de O(n2log(n)) y O(n2), respectivamente.

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

Como resultado, k-means trata de manera eficaz los datos como compuestos por un número aproximado distribuciones circulares e intenta encontrar clústeres correspondientes a estas distribuciones. Pero los datos del mundo real contienen valores atípicos y clústeres basados en la densidad. y podría no coincidir con los supuestos subyacentes de k-means.

Algoritmo de agrupamiento en clústeres k-means

El algoritmo sigue estos pasos:

  1. Proporciona una estimación inicial para k, que se puede revisar más adelante. Para este Por ejemplo, elegimos k=3.

  2. Elige centroides k de forma aleatoria.

    Gráfico de k-means en
  Inicialización en la que se muestran tres centroides seleccionados al azar
    Figura 1: k-means en la inicialización.

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

    A cada punto se le asigna el color de su
  centroide más cercano
    Figura 2: Clústeres iniciales.

  4. Para cada clúster, calcula un centroide nuevo 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.

    Muestra centroides nuevos más cerca del
  centro de cada clúster de color
    Figura 3: centroides recalculados.

  5. Reasigna cada punto al centroide nuevo más cercano.

    Se ajustaron los clústeres después de la reasignación.
  a nuevos centroides
    Figura 4: Clústeres después de la reasignación.

  6. Repite los pasos 4 y 5, recalculando los centroides y la membresía del clúster, hasta que puntos ya no cambian grupos. En el caso de grandes conjuntos de datos, puedes detener el algoritmo antes de la convergencia según otros criterios.

Debido a que las posiciones del centroide se eligen inicialmente de forma aleatoria, k-means puede para mostrar resultados significativamente diferentes en ejecuciones sucesivas. Para resolver esto ejecuta k-means varias veces y elige el resultado con la mejor calidad métricas. (Más adelante en este curso, describiremos las métricas de calidad). Necesitarás versión avanzada de k-medios para elegir mejores posiciones iniciales del centroide.

Si bien no es necesario un profundo conocimiento de la matemática, a aquellos que curioso, k-means es un caso especial de la algoritmo de maximización de expectativas. Consulta notas de la clase sobre el tema de la UPenn.