Agrupamiento de k-medias

El agrupamiento de k -medias es un método de cuantificación vectorial , originariamente del procesamiento de señales , que tiene como objetivo particionar n observaciones en k grupos en los que cada observación pertenece al grupo con la media más cercana (centros de grupo o centroide de grupo ), que sirve como prototipo del grupo. Esto da como resultado una partición del espacio de datos en celdas de Voronoi . El agrupamiento de k -medias minimiza las varianzas dentro del grupo ( distancias euclidianas al cuadrado ), pero no las distancias euclidianas regulares, que sería el problema de Weber más difícil : la media optimiza los errores al cuadrado, mientras que solo la mediana geométrica minimiza las distancias euclidianas. Por ejemplo, se pueden encontrar mejores soluciones euclidianas utilizando k -medianas y k -medoides .

El problema es computacionalmente difícil ( NP-hard ); sin embargo, los algoritmos heurísticos eficientes convergen rápidamente a un óptimo local . Estos suelen ser similares al algoritmo de expectativa-maximización para mezclas de distribuciones gaussianas a través de un enfoque de refinamiento iterativo empleado tanto por k-means como por el modelado de mezcla gaussiana . Ambos utilizan centros de clústeres para modelar los datos; sin embargo, el agrupamiento k -means tiende a encontrar clústeres de extensión espacial comparable, mientras que el modelo de mezcla gaussiana permite que los clústeres tengan diferentes formas.

El algoritmo k -means no supervisado tiene una relación vaga con el clasificador de k -vecinos más cercanos , una técnica popular de aprendizaje automático supervisado para la clasificación que a menudo se confunde con k -means debido al nombre. La aplicación del clasificador de 1 vecino más cercano a los centros de los clústeres obtenidos por k -means clasifica los datos nuevos en los clústeres existentes. Esto se conoce como clasificador de centroide más cercano o algoritmo de Rocchio .

Dado un conjunto de observaciones ( x ₁ , x ₂ , ..., x _n ) , donde cada observación es un vector real -dimensional, la agrupación de k -medias tiene como objetivo particionar las n observaciones en k ( ≤ n ) conjuntos S = { S ₁ , S ₂ , ..., S _k } para minimizar la suma de cuadrados dentro del grupo (WCSS) (es decir, la varianza ). Formalmente, el objetivo es encontrar: donde μ _i es la media (también llamada centroide) de los puntos en , es decir, es el tamaño de , y es la norma L ² habitual . Esto es equivalente a minimizar las desviaciones al cuadrado por pares de puntos en el mismo grupo: La equivalencia se puede deducir de la identidad . Dado que la varianza total es constante, esto es equivalente a maximizar la suma de las desviaciones al cuadrado entre puntos en diferentes grupos (suma de cuadrados entre grupos, BCSS). ^[1] Esta relación determinista también está relacionada con la ley de varianza total en la teoría de probabilidad.${\displaystyle d}$$${\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}=\mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}|S_{i}|\operatorname {Var} S_{i}}$$${\displaystyle S_{i}}$$${\displaystyle {\boldsymbol {\mu _{i}}}={\frac {1}{|S_{i}|}}\sum _{\mathbf {x} \in S_{i}}\mathbf {x} ,}$$${\displaystyle |S_{i}|}$${\displaystyle S_{i}}$${\displaystyle \|\cdot \|}$$${\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\,{\frac {1}{|S_{i}|}}\,\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}}$$${\textstyle |S_{i}|\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\frac {1}{2}}\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}}$

El término " k -means" fue utilizado por primera vez por James MacQueen en 1967, ^[2] aunque la idea se remonta a Hugo Steinhaus en 1956. ^[3] El algoritmo estándar fue propuesto por primera vez por Stuart Lloyd de Bell Labs en 1957 como una técnica para la modulación de código de pulso , aunque no se publicó como artículo de revista hasta 1982. ^[4] En 1965, Edward W. Forgy publicó esencialmente el mismo método, por lo que a veces se lo conoce como el algoritmo Lloyd-Forgy. ^[5]

El algoritmo más común utiliza una técnica de refinamiento iterativo. Debido a su ubicuidad, a menudo se lo denomina " algoritmo k -means"; también se lo conoce como algoritmo de Lloyd , particularmente en la comunidad informática. A veces también se lo conoce como " algoritmo k -means ingenuo", porque existen alternativas mucho más rápidas. ^[6]

Dado un conjunto inicial de k medias m ₁ ⁽¹⁾ , ..., m _k ⁽¹⁾ (ver más abajo), el algoritmo procede alternando entre dos pasos: ^[7]

1. Paso de asignación : Asignar cada observación al grupo con la media más cercana: aquella con la distancia euclidiana de mínimos cuadrados . ^[8] (Matemáticamente, esto significa particionar las observaciones de acuerdo con el diagrama de Voronoi generado por las medias), donde cada una se asigna exactamente a una , incluso si pudiera asignarse a dos o más de ellas.$${\displaystyle S_{i}^{(t)}=\left\{x_{p}:\left\|x_{p}-m_{i}^{(t)}\right\|^{2}\leq \left\|x_{p}-m_{j}^{(t)}\right\|^{2}\ \forall j,1\leq j\leq k\right\},}$$${\displaystyle x_{p}}$${\displaystyle S^{(t)}}$
2. Paso de actualización : recalcular las medias ( centroides ) de las observaciones asignadas a cada grupo.$${\displaystyle m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}}$$

La función objetivo en k -medias es la WCSS (suma de cuadrados dentro del conglomerado). Después de cada iteración, la WCSS disminuye y, por lo tanto, tenemos una secuencia monótona decreciente no negativa. Esto garantiza que las k -medias siempre convergen, pero no necesariamente al óptimo global.

El algoritmo ha convergido cuando las asignaciones ya no cambian o, equivalentemente, cuando el WCSS se ha vuelto estable. No se garantiza que el algoritmo encuentre el óptimo. ^[9]

El algoritmo se presenta a menudo como la asignación de objetos al grupo más cercano por distancia. El uso de una función de distancia distinta a la distancia euclidiana (al cuadrado) puede impedir que el algoritmo converja. Se han propuesto varias modificaciones de las k -medias, como las k -medias esféricas y las k -medoides, para permitir el uso de otras medidas de distancia.

Pseudocódigo

El pseudocódigo que se muestra a continuación describe la implementación del algoritmo de agrupamiento estándar de k -medias. La inicialización de los centroides, la métrica de distancia entre puntos y centroides y el cálculo de nuevos centroides son opciones de diseño y variarán según las diferentes implementaciones. En este pseudocódigo de ejemplo, se utiliza argmin para encontrar el índice del valor mínimo.

def  k_means_cluster ( k ,  puntos ): # Inicialización: elija k centroides (Forgy, Partición aleatoria, etc.) centroides  =  [ c1 ,  c2 ,  ... ,  ck ]  # Inicializar lista de clusters clusters  =  [[]  para  _  en  rango ( k )]  # Bucle hasta la convergencia convergido  =  falso mientras  no  converja : # Borrar clústeres anteriores clusters  =  [[]  para  _  en  rango ( k )]  # Asigna cada punto al centroide "más cercano" para  punto  en  puntos : distancias_a_cada_centroide  =  [ distancia ( punto ,  centroide )  para  el centroide  en  centroides ] asignación_de_grupo  =  argmin ( distancias_a_cada_centroide ) clusters [ cluster_assignment ] .append ( punto )​  # Calcular nuevos centroides # (la implementación estándar utiliza la media de todos los puntos en una # cluster para determinar el nuevo centroide) new_centroids  =  [ calculate_centroid ( cluster )  para  el cluster  en  clusters ]  convergente  =  ( nuevos_centroides  ==  centroides ) centroides  =  nuevos_centroides  Si  convergió : devolver  clústeres

Los métodos de inicialización más utilizados son Forgy y Partición aleatoria. ^[10] El método Forgy elige aleatoriamente k observaciones del conjunto de datos y las utiliza como medias iniciales. El método Partición aleatoria primero asigna aleatoriamente un conglomerado a cada observación y luego procede al paso de actualización, calculando así la media inicial como el centroide de los puntos asignados aleatoriamente al conglomerado. El método Forgy tiende a dispersar las medias iniciales, mientras que la Partición aleatoria las coloca todas cerca del centro del conjunto de datos. Según Hamerly et al., ^[10] el método Partición aleatoria es generalmente preferible para algoritmos como las medias k -armónicas y las k -medias difusas . Para los algoritmos de maximización de expectativas y k -medias estándar, es preferible el método de inicialización Forgy. Sin embargo, un estudio exhaustivo de Celebi et al., ^[11] encontró que los métodos de inicialización populares como Forgy, Random Partition y Maximin a menudo tienen un desempeño deficiente, mientras que el enfoque de Bradley y Fayyad ^[12] funciona "consistentemente" en "el mejor grupo" y k -means++ funciona "generalmente bien".

• Demostración del algoritmo estándar
• 
  1. Las k "medias" iniciales (en este caso k = 3) se generan aleatoriamente dentro del dominio de datos (mostradas en color).
• 
  2. Los grupos k se crean asociando cada observación con la media más cercana. Las particiones aquí representan el diagrama de Voronoi generado por las medias.
• 
  3. El centroide de cada uno de los k grupos se convierte en la nueva media.
• 
  4. Se repiten los pasos 2 y 3 hasta alcanzar la convergencia.

El algoritmo no garantiza la convergencia al óptimo global. El resultado puede depender de los grupos iniciales. Como el algoritmo suele ser rápido, es común ejecutarlo varias veces con diferentes condiciones iniciales. Sin embargo, el rendimiento en el peor de los casos puede ser lento: en particular, ciertos conjuntos de puntos, incluso en dos dimensiones, convergen en tiempo exponencial, es decir, 2 ^{Ω( n )} . ^[13] Estos conjuntos de puntos no parecen surgir en la práctica: esto se corrobora por el hecho de que el tiempo de ejecución suavizado de k -medias es polinomial. ^[14]

El paso de "asignación" se denomina "paso de expectativa", mientras que el "paso de actualización" es un paso de maximización, lo que convierte a este algoritmo en una variante del algoritmo de expectativa-maximización generalizado .

Encontrar la solución óptima al problema de agrupamiento de k -medias para observaciones en d dimensiones es:

• NP-hard en el espacio euclidiano general (de d dimensiones) incluso para dos cúmulos, ^{[15] [16]}
• NP-duro para un número general de grupos k incluso en el plano, ^[17]
• Si k y d (la dimensión) son fijos, el problema se puede resolver exactamente en el tiempo , donde n es el número de entidades a agrupar. ^[18]${\displaystyle O(n^{dk+1})}$

Por lo tanto, generalmente se utilizan una variedad de algoritmos heurísticos como el algoritmo de Lloyd mencionado anteriormente.

El tiempo de ejecución del algoritmo de Lloyd (y la mayoría de las variantes) es , ^{[9] [19]} donde:${\displaystyle O(nkdi)}$

• n es el número de vectores de dimensión d (que se van a agrupar)
• k el número de clusters
• i el número de iteraciones necesarias hasta la convergencia.

En el caso de datos que sí tienen una estructura de agrupamiento, el número de iteraciones hasta la convergencia suele ser pequeño y los resultados solo mejoran ligeramente después de la primera docena de iteraciones. Por lo tanto, en la práctica, el algoritmo de Lloyd suele considerarse de complejidad "lineal", aunque en el peor de los casos es superpolinomial cuando se ejecuta hasta la convergencia. ^[20]

• En el peor de los casos, el algoritmo de Lloyd necesita iteraciones, por lo que la complejidad del peor de los casos del algoritmo de Lloyd es superpolinomial . ^[20]${\displaystyle i=2^{\Omega ({\sqrt {n}})}}$
• El algoritmo k -medias de Lloyd tiene un tiempo de ejecución suavizado por polinomios. Se muestra que ^[14] para un conjunto arbitrario de n puntos en , si cada punto es perturbado independientemente por una distribución normal con media 0 y varianza , entonces el tiempo de ejecución esperado del algoritmo k -medias está limitado por , que es un polinomio en n , k , d y .${\displaystyle [0,1]^{d}}$${\displaystyle \sigma ^{2}}$${\displaystyle O(n^{34}k^{34}d^{8}\log ^{4}(n)/\sigma ^{6})}$${\displaystyle 1/\sigma }$
• Se han demostrado límites mejores para casos simples. Por ejemplo, se muestra que el tiempo de ejecución del algoritmo k -means está limitado por para n puntos en una red de números enteros . ^[21]${\displaystyle O(dn^{4}M^{2})}$ ${\displaystyle \{1,\dots ,M\}^{d}}$

El algoritmo de Lloyd es el enfoque estándar para este problema. Sin embargo, dedica mucho tiempo de procesamiento a calcular las distancias entre cada uno de los centros de los k grupos y los n puntos de datos. Dado que los puntos suelen permanecer en los mismos grupos después de unas pocas iteraciones, gran parte de este trabajo es innecesario, lo que hace que la implementación ingenua sea muy ineficiente. Algunas implementaciones utilizan el almacenamiento en caché y la desigualdad triangular para crear límites y acelerar el algoritmo de Lloyd. ^{[9] [22] [23] [24] [25]}

Encontrar el número óptimo de clústeres ( k ) para la agrupación en k -medias es un paso crucial para garantizar que los resultados de la agrupación sean significativos y útiles. ^[26] Existen varias técnicas disponibles para determinar un número adecuado de clústeres. A continuación, se presentan algunos de los métodos más utilizados:

• Método del codo (agrupamiento) : este método implica trazar la variación explicada como una función del número de conglomerados y elegir el codo de la curva como el número de conglomerados a utilizar. ^[27] Sin embargo, la noción de "codo" no está bien definida y se sabe que no es confiable. ^[28]
• Silueta (agrupamiento) : el análisis de silueta mide la calidad del agrupamiento y proporciona una idea de la distancia de separación entre los agrupamientos resultantes. ^[29] Una puntuación de silueta más alta indica que el objeto coincide bien con su propio agrupamiento y mal con los agrupamientos vecinos.
• Estadística de brecha : la estadística de brecha compara la variación total dentro del grupo para diferentes valores de k con sus valores esperados bajo una distribución de referencia nula de los datos. ^[30] El k óptimo es el valor que produce la estadística de brecha más grande.
• Índice de Davies-Bouldin : el índice de Davies-Bouldin es una medida de cuánta separación hay entre los clústeres. ^[31] Los valores más bajos del índice de Davies-Bouldin indican un modelo con mejor separación.
• Índice de Calinski-Harabasz : este índice evalúa los conglomerados en función de su compacidad y separación. El índice se calcula utilizando la relación entre la varianza entre conglomerados y la varianza dentro de los conglomerados; los valores más altos indican conglomerados mejor definidos. ^[32]
• Índice Rand : Calcula la proporción de acuerdo entre los dos clústeres, considerando ambos pares de elementos que están correctamente asignados al mismo o a diferentes clústeres. ^[33] Los valores más altos indican mayor similitud y mejor calidad de agrupamiento. Para proporcionar una medida más precisa, el Índice Rand Ajustado (ARI), introducido por Hubert y Arabie en 1985, corrige el Índice Rand ajustando la similitud esperada de todos los emparejamientos debido al azar. ^[34]

• Optimización de rupturas naturales de Jenks : k -medias aplicadas a datos univariados
• La agrupación de k -medianas utiliza la mediana en cada dimensión en lugar de la media, y de esta manera minimizala norma ( geometría del taxi ).${\displaystyle L_{1}}$
• k -medoids (también: Partitioning Around Medoids, PAM) utiliza el medoide en lugar de la media, y de esta manera minimiza la suma de distancias para funciones de distancia arbitrarias .
• El agrupamiento difuso de C-medias es una versión suave de k -medias, donde cada punto de datos tiene un grado difuso de pertenencia a cada grupo.
• Los modelos de mezcla gaussiana entrenados con el algoritmo de expectativa-maximización (algoritmo EM) mantienen asignaciones probabilísticas a los clústeres, en lugar de asignaciones deterministas, y distribuciones gaussianas multivariadas en lugar de medias.
• k -means++ elige centros iniciales de una manera que proporciona un límite superior demostrable para el objetivo WCSS.
• El algoritmo de filtrado utiliza árboles k -d para acelerar cada paso de k -medias. ^[35]
• Algunos métodos intentan acelerar cada paso de k -medias utilizando la desigualdad triangular . ^{[22] [23] [24] [36] [25]}
• Escapar de los óptimos locales intercambiando puntos entre grupos. ^[9]
• El algoritmo de agrupamiento k -medias esférico es adecuado para datos textuales. ^[37]
• Las variantes jerárquicas como la bisección de k -medias, ^[38] la agrupación en clústeres de X-medias ^[39] y la agrupación en clústeres de G-medias ^[40] dividen repetidamente los clústeres para construir una jerarquía y también pueden intentar determinar automáticamente la cantidad óptima de clústeres en un conjunto de datos.
• Las medidas de evaluación de clústeres internos, como la silueta de clústeres, pueden ser útiles para determinar la cantidad de clústeres .
• La k -media ponderada de Minkowski calcula automáticamente los pesos de las características específicas de cada grupo, lo que respalda la idea intuitiva de que una característica puede tener diferentes grados de relevancia en diferentes características. ^[41] Estos pesos también se pueden utilizar para volver a escalar un conjunto de datos determinado, lo que aumenta la probabilidad de que un índice de validez de grupo se optimice en la cantidad esperada de grupos. ^[42]
• Mini-lotes k -medias: variación de k -medias utilizando muestras de "minilotes" para conjuntos de datos que no caben en la memoria. ^[43]
• El método de Otsu

El método de Hartigan y Wong ^[9] proporciona una variación del algoritmo k -means que avanza hacia un mínimo local del problema de suma mínima de cuadrados con diferentes actualizaciones de solución. El método es una búsqueda local que intenta iterativamente reubicar una muestra en un grupo diferente siempre que este proceso mejore la función objetivo. Cuando no se puede reubicar ninguna muestra en un grupo diferente con una mejora del objetivo, el método se detiene (en un mínimo local). De manera similar al clásico k -means, el enfoque sigue siendo una heurística ya que no garantiza necesariamente que la solución final sea globalmente óptima.

Sea el costo individual de definido por , con el centro del clúster.${\displaystyle \varphi (S_{j})}$${\displaystyle S_{j}}$${\textstyle \sum _{x\in S_{j}}(x-\mu _{j})^{2}}$${\displaystyle \mu _{j}}$

Paso de asignación

El método de Hartigan y Wong comienza dividiendo los puntos en grupos aleatorios .${\displaystyle \{S_{j}\}_{j\in \{1,\cdots k\}}}$

Paso de actualización

A continuación, determina el y para el cual la siguiente función alcanza un máximo. Para los que alcanzan este máximo, se mueve del clúster al clúster .${\displaystyle n,m\in \{1,\ldots ,k\}}$${\displaystyle x\in S_{n}}$$${\displaystyle \Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\setminus \{x\})-\varphi (S_{m}\cup \{x\}).}$$${\displaystyle x,n,m}$${\displaystyle x}$${\displaystyle S_{n}}$${\displaystyle S_{m}}$

Terminación

El algoritmo termina una vez que es menor que cero para todos .${\displaystyle \Delta (m,n,x)}$${\displaystyle x,n,m}$

Se pueden utilizar diferentes estrategias de aceptación de movimientos. En una estrategia de primera mejora , se puede aplicar cualquier reubicación que mejore, mientras que en una estrategia de mejor mejora , se prueban iterativamente todas las reubicaciones posibles y solo se aplica la mejor en cada iteración. El primer enfoque favorece la velocidad, mientras que el segundo enfoque generalmente favorece la calidad de la solución a expensas de un tiempo computacional adicional. La función utilizada para calcular el resultado de una reubicación también se puede evaluar de manera eficiente mediante el uso de la igualdad ^[44].${\displaystyle \Delta }$

$${\displaystyle \Delta (x,n,m)={\frac {\mid S_{n}\mid }{\mid S_{n}\mid -1}}\cdot \lVert \mu _{n}-x\rVert ^{2}-{\frac {\mid S_{m}\mid }{\mid S_{m}\mid +1}}\cdot \lVert \mu _{m}-x\rVert ^{2}.}$$

Se sabe que el algoritmo clásico k -means y sus variaciones solo convergen a mínimos locales del problema de agrupamiento de suma mínima de cuadrados definido como Muchos estudios han intentado mejorar el comportamiento de convergencia del algoritmo y maximizar las posibilidades de alcanzar el óptimo global (o al menos, mínimos locales de mejor calidad). Las técnicas de inicialización y reinicio discutidas en las secciones anteriores son una alternativa para encontrar mejores soluciones. Más recientemente, los algoritmos de optimización global basados ​​en programación de ramificación y acotación y semidefinida han producido soluciones "demostradamente óptimas" para conjuntos de datos con hasta 4177 entidades y 20 531 características. ^[45] Como se esperaba, debido a la dureza NP del problema de optimización subyacente, el tiempo computacional de los algoritmos óptimos para k -means aumenta rápidamente más allá de este tamaño. Las soluciones óptimas para pequeña y mediana escala siguen siendo valiosas como herramienta de referencia para evaluar la calidad de otras heurísticas. Para encontrar mínimos locales de alta calidad dentro de un tiempo computacional controlado pero sin garantías de optimalidad, otros trabajos han explorado metaheurísticas y otras técnicas de optimización global , por ejemplo, basadas en enfoques incrementales y optimización convexa, ^[46] intercambios aleatorios ^[47] (es decir, búsqueda local iterada ), búsqueda de vecindad variable ^[48] y algoritmos genéticos . ^{[49] [50]} De hecho, se sabe que encontrar mejores mínimos locales del problema de agrupamiento de suma mínima de cuadrados puede marcar la diferencia entre el fracaso y el éxito para recuperar estructuras de clúster en espacios de características de alta dimensión. ^[50]$${\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}.}$$

Tres características clave de k -means que lo hacen eficiente a menudo se consideran sus mayores desventajas:

• La distancia euclidiana se utiliza como métrica y la varianza se utiliza como medida de dispersión de conglomerados.
• El número de conglomerados k es un parámetro de entrada: una elección inadecuada de k puede dar lugar a resultados deficientes. Por ello, al realizar el análisis de k -medias, es importante realizar comprobaciones de diagnóstico para determinar el número de conglomerados en el conjunto de datos .
• La convergencia a un mínimo local puede producir resultados contra-intuitivos ("erróneos") (véase el ejemplo en la figura).

Una limitación clave de k -means es su modelo de clúster. El concepto se basa en clústeres esféricos que son separables de modo que la media converge hacia el centro del clúster. Se espera que los clústeres sean de tamaño similar, de modo que la asignación al centro del clúster más cercano sea la asignación correcta. Cuando, por ejemplo, se aplica k -means con un valor de en el conocido conjunto de datos de flores de iris , el resultado a menudo no logra separar las tres especies de iris contenidas en el conjunto de datos. Con , se descubrirán los dos clústeres visibles (uno que contiene dos especies), mientras que con uno de los dos clústeres se dividirá en dos partes iguales. De hecho, es más apropiado para este conjunto de datos, a pesar de que el conjunto de datos contiene 3 clases . Al igual que con cualquier otro algoritmo de agrupamiento, el resultado de k -means hace suposiciones de que los datos satisfacen ciertos criterios. Funciona bien en algunos conjuntos de datos y falla en otros.${\displaystyle k=3}$${\displaystyle k=2}$${\displaystyle k=3}$${\displaystyle k=2}$

El resultado de k -medias puede verse como las celdas de Voronoi de las medias de los conglomerados. Dado que los datos se dividen a la mitad entre las medias de los conglomerados, esto puede conducir a divisiones subóptimas como se puede ver en el ejemplo del "ratón". Los modelos gaussianos utilizados por el algoritmo de expectativa-maximización (podría decirse que una generalización de k -medias) son más flexibles al tener varianzas y covarianzas. El resultado EM es así capaz de acomodar conglomerados de tamaño variable mucho mejor que k -medias, así como conglomerados correlacionados (no en este ejemplo). En contrapartida, EM requiere la optimización de un mayor número de parámetros libres y plantea algunos problemas metodológicos debido a conglomerados que se desvanecen o matrices de covarianza mal condicionadas. k -medias está estrechamente relacionado con el modelado bayesiano no paramétrico . ^[52]

La agrupación en clústeres de k -medias es bastante fácil de aplicar incluso a grandes conjuntos de datos, en particular cuando se utilizan heurísticas como el algoritmo de Lloyd . Se ha utilizado con éxito en la segmentación de mercados , la visión artificial y la astronomía , entre muchos otros campos. A menudo se utiliza como un paso de preprocesamiento para otros algoritmos, por ejemplo, para encontrar una configuración inicial.

La cuantificación vectorial , una técnica que se utiliza habitualmente en el procesamiento de señales y en gráficos por ordenador, implica la reducción de la paleta de colores de una imagen a un número fijo de colores, conocido como k . Un método popular para lograr la cuantificación vectorial es mediante la agrupación de k -medias. En este proceso, se aplica k -medias al espacio de color de una imagen para dividirla en k grupos, donde cada grupo representa un color distinto en la imagen. Esta técnica es especialmente útil en tareas de segmentación de imágenes, donde ayuda a identificar y agrupar colores similares.

Ejemplo: En el campo de los gráficos por computadora , la agrupación de k -medias se emplea a menudo para la cuantificación de color en la compresión de imágenes. Al reducir la cantidad de colores utilizados para representar una imagen, se pueden reducir significativamente los tamaños de archivo sin una pérdida significativa de calidad visual. Por ejemplo, considere una imagen con millones de colores. Al aplicar la agrupación de k -medias con k establecido en un número menor, la imagen se puede representar utilizando una paleta de colores más limitada , lo que da como resultado una versión comprimida que consume menos espacio de almacenamiento y ancho de banda. Otros usos de la cuantificación vectorial incluyen el muestreo no aleatorio , ya que k -medias se pueden utilizar fácilmente para elegir k objetos diferentes pero prototípicos de un gran conjunto de datos para su posterior análisis.

El análisis de conglomerados , una tarea fundamental en la minería de datos y el aprendizaje automático , implica agrupar un conjunto de puntos de datos en conglomerados en función de su similitud. El agrupamiento de k -medias es un algoritmo popular utilizado para particionar datos en k conglomerados, donde cada conglomerado está representado por su centroide.

Sin embargo, el algoritmo k -means puro no es muy flexible y, como tal, su uso es limitado (excepto cuando la cuantificación vectorial como la descrita anteriormente es el caso de uso deseado). En particular, se sabe que el parámetro k es difícil de elegir (como se explicó anteriormente) cuando no está determinado por restricciones externas. Otra limitación es que no se puede utilizar con funciones de distancia arbitrarias o con datos no numéricos. Para estos casos de uso, muchos otros algoritmos son superiores.

Ejemplo: En marketing, la agrupación de k -medias se emplea con frecuencia para la segmentación del mercado , donde se agrupan los clientes con características o comportamientos similares. Por ejemplo, una empresa minorista puede utilizar la agrupación de k -medias para segmentar su base de clientes en grupos distintos en función de factores como el comportamiento de compra, la demografía y la ubicación geográfica. A continuación, se pueden dirigir estrategias de marketing y ofertas de productos personalizadas a estos segmentos de clientes para maximizar las ventas y la satisfacción del cliente.

La agrupación en k -medias se ha utilizado como un paso de aprendizaje de características (o aprendizaje de diccionario ), tanto en el aprendizaje ( semi ) supervisado como en el aprendizaje no supervisado . ^[53] El enfoque básico es primero entrenar una representación de agrupación en k -medias, utilizando los datos de entrenamiento de entrada (que no necesitan estar etiquetados). Luego, para proyectar cualquier dato de entrada en el nuevo espacio de características, una función de "codificación", como el producto matricial umbralizado del dato con las ubicaciones de los centroides, calcula la distancia desde el dato a cada centroide, o simplemente una función indicadora para el centroide más cercano, ^{[53] [54]} o alguna transformación suave de la distancia. ^[55] Alternativamente, al transformar la distancia del grupo de muestra a través de una RBF gaussiana , se obtiene la capa oculta de una red de función de base radial . ^[56]

Este uso de k -medias se ha combinado con éxito con clasificadores lineales simples para el aprendizaje semisupervisado en NLP (específicamente para el reconocimiento de entidades nombradas ) ^[57] y en visión artificial . En una tarea de reconocimiento de objetos, se encontró que exhibía un rendimiento comparable con enfoques de aprendizaje de características más sofisticados, como autocodificadores y máquinas de Boltzmann restringidas . ^[55] Sin embargo, generalmente requiere más datos para un rendimiento equivalente, porque cada punto de datos solo contribuye a una "característica". ^[53]

Ejemplo: En el procesamiento del lenguaje natural (PLN), la agrupación en clústeres de k -medias se ha integrado con clasificadores lineales simples para tareas de aprendizaje semisupervisado como el reconocimiento de entidades nombradas (NER). Al agrupar primero los datos de texto sin etiquetar utilizando k -medias, se pueden extraer características significativas para mejorar el rendimiento de los modelos NER. Por ejemplo, la agrupación en clústeres de k -medias se puede aplicar para identificar grupos de palabras o frases que frecuentemente aparecen simultáneamente en el texto de entrada, que luego se pueden usar como características para entrenar el modelo NER. Se ha demostrado que este enfoque logra un rendimiento comparable con técnicas de aprendizaje de características más complejas , como autocodificadores y máquinas de Boltzmann restringidas , aunque con un mayor requisito de datos etiquetados.

Los avances recientes en la aplicación de la agrupación en clústeres de k -medias incluyen mejoras en las técnicas de inicialización, como el uso de la inicialización de k -medias++ para seleccionar los centroides de agrupación iniciales de una manera más eficaz. Además, los investigadores han explorado la integración de la agrupación en clústeres de k -medias con métodos de aprendizaje profundo, como las redes neuronales convolucionales (CNN) y las redes neuronales recurrentes (RNN), para mejorar el rendimiento de varias tareas en visión artificial , procesamiento del lenguaje natural y otros dominios.

El algoritmo lento "estándar" para el agrupamiento de k -medias, y su algoritmo asociado de expectativa-maximización , es un caso especial de un modelo de mezcla gaussiana, específicamente, el caso límite cuando se fijan todas las covarianzas para que sean diagonales, iguales y tengan una varianza infinitesimalmente pequeña. ^{[58] : 850} En lugar de varianzas pequeñas, también se puede utilizar una asignación de agrupamiento estricta para mostrar otra equivalencia del agrupamiento de k -medias con un caso especial de modelado de mezcla gaussiana "duro". ^{[59] : 354, 11.4.2.5} Esto no significa que sea eficiente utilizar el modelado de mezcla gaussiana para calcular k -medias, sino simplemente que existe una relación teórica y que el modelado de mezcla gaussiana se puede interpretar como una generalización de k -medias; por el contrario, se ha sugerido utilizar el agrupamiento de k -medias para encontrar puntos de partida para el modelado de mezcla gaussiana en datos difíciles. ^{[58] : 849}

Otra generalización del algoritmo k -means es el algoritmo k -SVD, que estima los puntos de datos como una combinación lineal dispersa de "vectores de libro de códigos". k -means corresponde al caso especial de utilizar un único vector de libro de códigos, con un peso de 1. ^[60]

La solución relajada de la agrupación de k -medias, especificada por los indicadores de agrupación, se da mediante el análisis de componentes principales (PCA). ^{[61] [62]} La intuición es que las k -medias describen agrupaciones con forma esférica (similar a una bola). Si los datos tienen 2 agrupaciones, la línea que conecta los dos centroides es la mejor dirección de proyección unidimensional, que también es la primera dirección de PCA. Cortar la línea en el centro de masa separa las agrupaciones (esta es la relajación continua del indicador de agrupación discreto). Si los datos tienen tres agrupaciones, el plano bidimensional abarcado por tres centroides de agrupación es la mejor proyección 2-D. Este plano también está definido por las dos primeras dimensiones de PCA. Las agrupaciones bien separadas se modelan de manera efectiva mediante agrupaciones con forma de bola y, por lo tanto, se descubren mediante k -medias. Las agrupaciones que no tienen forma de bola son difíciles de separar cuando están cerca. Por ejemplo, dos agrupaciones con forma de media luna entrelazadas en el espacio no se separan bien cuando se proyectan en el subespacio de PCA. No se debe esperar que k -means tenga un buen desempeño con estos datos. ^[63] Es sencillo producir contraejemplos a la afirmación de que el subespacio del centroide del grupo está abarcado por las direcciones principales. ^[64]

Los algoritmos básicos de agrupamiento por desplazamiento de la media mantienen un conjunto de puntos de datos del mismo tamaño que el conjunto de datos de entrada. Inicialmente, este conjunto se copia del conjunto de entrada. A continuación, todos los puntos se mueven iterativamente hacia la media de los puntos que los rodean. Por el contrario, k -means restringe el conjunto de clústeres a k clústeres, normalmente mucho menos que el número de puntos en el conjunto de datos de entrada, utilizando la media de todos los puntos en el clúster anterior que están más cerca de ese punto que cualquier otro para el centroide (por ejemplo, dentro de la partición de Voronoi de cada punto de actualización). Un algoritmo de desplazamiento de la media que es similar a k -means, llamado desplazamiento de la media de verosimilitud , reemplaza el conjunto de puntos sometidos a reemplazo por la media de todos los puntos en el conjunto de entrada que están dentro de una distancia dada del conjunto cambiante. ^[65] Una ventaja del agrupamiento por desplazamiento de la media sobre k -means es la detección de un número arbitrario de clústeres en el conjunto de datos, ya que no hay un parámetro que determine el número de clústeres. El cambio de media puede ser mucho más lento que k -medias y aún requiere la selección de un parámetro de ancho de banda.

Bajo supuestos de escasez y cuando los datos de entrada se procesan previamente con la transformación de blanqueamiento , k -means produce la solución a la tarea de análisis de componentes independientes lineales (ICA). Esto ayuda a explicar la aplicación exitosa de k -means al aprendizaje de características. ^[66]

k -means asume implícitamente que el orden del conjunto de datos de entrada no importa. El filtro bilateral es similar a k -means y al cambio de media en que mantiene un conjunto de puntos de datos que se reemplazan iterativamente por medias. Sin embargo, el filtro bilateral restringe el cálculo de la media (ponderada por kernel) para incluir solo puntos que están cerca en el orden de los datos de entrada. ^[65] Esto lo hace aplicable a problemas como la eliminación de ruido de imágenes, donde la disposición espacial de los píxeles en una imagen es de importancia crítica.

El conjunto de funciones de clúster que minimizan el error al cuadrado también incluye el algoritmo k -medoides , un enfoque que fuerza a que el punto central de cada clúster sea uno de los puntos reales, es decir, utiliza medoides en lugar de centroides .

Las diferentes implementaciones del algoritmo presentan diferencias de rendimiento: la más rápida en un conjunto de datos de prueba finaliza en 10 segundos, mientras que la más lenta tarda 25 988 segundos (aproximadamente 7 horas). ^[1] Las diferencias se pueden atribuir a la calidad de la implementación, las diferencias de lenguaje y compilador, los diferentes criterios de terminación y niveles de precisión, y el uso de índices para la aceleración.

Las siguientes implementaciones están disponibles bajo licencias de software libre/de código abierto , con código fuente disponible públicamente.

• Accord.NET contiene implementaciones de C# para k -means, k -means++ y k -modes.
• ALGLIB contiene implementaciones de C++ y C# paralelizadas para k -means y k -means++.
• AOSP contiene una implementación de Java para k -means.
• CrimeStat implementa dos algoritmos k -medias espaciales, uno de los cuales permite al usuario definir las ubicaciones de inicio.
• ELKI contiene k -means (con iteración de Lloyd y MacQueen, junto con diferentes inicializaciones como la inicialización k -means++) y varios algoritmos de agrupamiento más avanzados.
• Smile contiene k -means y varios otros algoritmos y visualización de resultados (para Java, Kotlin y Scala).
• Julia contiene una implementación de k -means en el paquete JuliaStats Clustering.
• KNIME contiene nodos para k -medias y k -medoides.
• Mahout contiene un k -means basado en MapReduce .
• mlpack contiene una implementación en C++ de k -means.
• Octave contiene k -medias.
• OpenCV contiene una implementación de k -medias.
• Orange incluye un componente para agrupamiento de k -medias con selección automática de k y puntuación de silueta de grupo.
• PSPP contiene k -medias. El comando QUICK CLUSTER realiza la agrupación en k -medias en el conjunto de datos.
• R contiene tres variaciones de k -medias.
• SciPy y scikit-learn contienen múltiples implementaciones de k -means.
• Spark MLlib implementa un algoritmo k -medias distribuido.
• Torch contiene un paquete unsup que proporciona agrupamiento k -means.
• Weka contiene k -medias y x -medias.

Las siguientes implementaciones están disponibles bajo términos de licencia propietaria y es posible que no tengan código fuente disponible públicamente.

• Algoritmo BFR
• Teselación de Voronoi centroidal
• Análisis de conglomerados
• Escaneo de base de datos
• Roturas de cabeza y cola
• k q -bemoles
• k -significa++
• Algoritmo de Linde-Buzo-Gray
• Mapa autoorganizativo