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(n^2 log(n))\) y \(O(n^2)\), 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:
Proporciona una estimación inicial para \(k\), que se puede revisar más adelante. Para este Por ejemplo, elegimos \(k = 3\).
Elige centroides \(k\) de forma aleatoria.
Figura 1: k-means en la inicialización. Asigna cada punto al centroide más cercano para obtener \(k\) 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.