Ejecuta el algoritmo de agrupamiento en clústeres

En el aprendizaje automático, a veces se encuentran conjuntos de datos que pueden tener millones de ejemplos. Los algoritmos de AA deben escalar de manera eficiente a estos grandes conjuntos de datos. Sin embargo, muchos algoritmos de agrupamiento en clústeres no escalan porque necesitan calcular la similitud entre todos los pares de puntos. Esto significa que sus entornos de ejecución aumentan como el cuadrado de la cantidad de puntos, indicado como \(O(n^2)\). Por ejemplo, los algoritmos de agrupamiento en clústeres jerárquico o adivinante observan todos los pares de puntos y tienen complejidades de \(O(n^2 log(n))\) y \(O(n^2)\), respectivamente.

Este curso se enfoca en los k-medios porque escala como \(O(nk)\), en el que \(k\)es la cantidad de clústeres. Los grupos k-medios apuntan a \(k\) clústeres mediante la minimización de las distancias entre los puntos y el centroide de su clúster (como se muestra en la Figura 1 a continuación). El centroide de un clúster es la media de todos los puntos en el clúster.

Como se muestra, k-means encuentra clústeres aproximadamente circulares. Conceptualmente, esto significa que k-means trata efectivamente los datos como compuestos por varias distribuciones aproximadamente circulares y trata de encontrar clústeres que correspondan a estas distribuciones. En realidad, los datos contienen valores atípicos y es posible que no se adapten a ese modelo.

Antes de ejecutar k-means, debes elegir la cantidad de clústeres, \(k\). Inicialmente, comienza con un cálculo para \(k\). Más adelante, veremos cómo definir mejor esta cifra.

Algoritmo de agrupamiento en clústeres de k-means

Para agrupar datos en clústeres \(k\) , k-means sigue los pasos que se indican a continuación:

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

Paso uno

El algoritmo elige al azar un centroide para cada clúster. En nuestro ejemplo, elegimos un \(k\) de 3 y, por lo tanto, el algoritmo elige al azar 3 centroides.

Figura 2: Clústeres iniciales.

Paso dos

El algoritmo asigna cada punto al centroide más cercano para obtener \(k\) clústeres iniciales.

Figura 3: Recomputación de centroides.

Paso tres

Para cada clúster, el algoritmo recalcula el centroide mediante el promedio de todos los puntos del clúster. Los cambios en los centroides se muestran en la figura 3 con flechas. Como los centroides cambian, el algoritmo vuelve a asignar los puntos al centroide más cercano. En la figura 4, se muestran los clústeres nuevos después de la reasignación.

Figura 4: Clústeres después de la reasignación.

Paso cuatro

El algoritmo repite el cálculo de los centroides y la asignación de puntos hasta que estos dejen de cambiar de clúster. Cuando agrupas en conjuntos de datos grandes, debes detener el algoritmo antes de alcanzar la convergencia mediante otros criterios.

No necesitas entender las matemáticas detrás de los k-medios para este curso. Sin embargo, si tienes curiosidad, consulta la siguiente prueba matemática.

Haz clic en el ícono de signo más para ver la prueba matemática

Dados los ejemplos \(n\) asignados a los clústeres \(k\) , minimiza la suma de distancias de ejemplos a sus centroides. Aquí:

• \(A_{nk} = 1\) cuando el \(n\).o ejemplo se asigna al \(k\).o clúster y, de lo contrario, 0
• \(\theta_k\) es el centroide del clúster \(k\)

Queremos minimizar la siguiente expresión:$$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$, sujeta a:$$A_{nk} \in \{0,1\} \forall n,k$$y$$\sum^{K}_{k=1}A_{nk}=1 \forall n$$. Para minimizar la expresión con respecto a los centroides del clúster \(\theta_k\), toma la derivada con \(\theta_k\) y equivale a 0. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ El numerador es la suma de todas las distancias centroides de ejemplo en el clúster. El denominador es la cantidad de ejemplos en el clúster. Por lo tanto, el centroide del clúster\(\theta_k\) es el promedio de las distancias centroides de ejemplo en el clúster. Por lo tanto, lo demostró.

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

Experimento: Con este simulador de k-means de Stanford, intenta ejecutar k-means varias veces y ver si obtienes resultados diferentes.

Términos clave:

• centroide