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 y , respectivamente.
Este curso se centra en el k-means porque se escala como , en el que es la cantidad de clústeres que elige el usuario. Este algoritmo agrupa los puntos 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:
Proporciona una estimación inicial para , que se puede revisar más adelante. Para este Por ejemplo, elegimos .
Elige centroides de forma aleatoria.
Figura 1: k-means en la inicialización. Asigna cada punto al centroide más cercano para obtener los clústeres iniciales.
Figura 2: Clústeres iniciales. 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.
Figura 3: centroides recalculados. Reasigna cada punto al centroide nuevo más cercano.
Figura 4: Clústeres después de la reasignación. 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.