Agrupamiento k -medias

El algoritmo más común utiliza una técnica de refinamiento iterativo. Debido a su omnipresencia, a menudo se le denomina " algoritmo k -medias"; también se le conoce como algoritmo de Lloyd , particularmente en la comunidad de informática. En ocasiones, también se le llama " k -medias ingenuo", ya que existen alternativas mucho más rápidas. ^{[ 7 ]}

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

1. Paso de asignación : Asigne cada observación al clúster con la media (centroide) más cercana: aquella con la distancia euclidiana al cuadrado más baja . ^{[ 9 ]} (Matemáticamente, esto significa particionar las observaciones según el diagrama de Voronoi generado por las medias).$${\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\},}$$donde cada${\displaystyle x_{p}}$se asigna a exactamente uno${\displaystyle S^{(t)}}$, incluso si pudiera asignarse a dos o más de ellos.
2. Paso de actualización : Recalcular las medias ( centroides ) de las observaciones asignadas a cada grupo. Esto también se denomina reajuste.$${\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 suma de cuadrados dentro de cada clúster (WCSS). Tras cada iteración, la WCSS disminuye monótonamente, generando una secuencia no negativa decreciente. Esto garantiza que k -medias siempre converge, aunque no necesariamente al óptimo global.

El algoritmo ha convergido cuando las asignaciones ya no cambian o, equivalentemente, cuando el WCSS se ha estabilizado. No se garantiza que el algoritmo encuentre la asignación de clúster óptima. ^{[ 10 ]}

El algoritmo se suele presentar asignando objetos al clúster más cercano según su distancia. El uso de una función de distancia distinta a la distancia euclidiana (al cuadrado) puede impedir la convergencia del algoritmo. Se han propuesto diversas modificaciones del algoritmo k -medias, como k- medias esféricas y k- medoides, para permitir el uso de otras medidas de distancia.

Pseudocódigo

El siguiente pseudocódigo describe la implementación del algoritmo estándar de agrupamiento k -means. La inicialización de los centroides, la métrica de distancia entre puntos y centroides, y el cálculo de nuevos centroides son decisiones de diseño y variarán según la implementación. En este ejemplo de pseudocódigo, distance()se devuelve la distancia entre los puntos especificados.

La función kmeans(k, puntos) es // Inicializar centroides centroides ← lista de k centroides iniciales convergió ← falso mientras converge == falso hacer // Crear clústeres vacíos clústeres ← lista de k listas vacías // Asigna cada punto al centroide más cercano para i ← 0 hasta length(points) - 1 hacer punto ← puntos[i] índice más cercano ← 0 minDistance ← distancia(punto, centroides[0]) para j ← 1 a k - 1 hacer d ← distancia (punto, centroides[j]) si d < minDistance ENTONCES distanciaMínima ← d índice más cercano ← j clústeres[índice más cercano]. agregar (punto) // Recalcular los centroides como la media de cada clúster. newCentroids ← lista vacía para i ← 0 a k - 1 hacer nuevoCentroid ← calcularCentroid (clusters[i]) newCentroids.append ( newCentroid ) // Comprobar la convergencia Si newCentroids == centroids ENTONCES convergió ← verdadero demás centroides ← nuevosCentroides clústeres de retorno

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

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

Por lo tanto, se suelen utilizar diversos algoritmos heurísticos, como el algoritmo de Lloyd mencionado anteriormente.

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

• n es el número de vectores d -dimensionales (que se van a agrupar).
• k el número de clústeres
• i el número de iteraciones necesarias hasta la convergencia.

En datos que sí presentan 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, el algoritmo de Lloyd se considera a menudo de complejidad "lineal" en la práctica, aunque en el peor de los casos es superpolinomial cuando se ejecuta hasta la convergencia. ^{[ 21 ]}

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

El algoritmo de Lloyd es el método estándar para este problema. Sin embargo, consume mucho tiempo de procesamiento calculando las distancias entre cada uno de los k centros de clúster y los n puntos de datos. Dado que los puntos suelen permanecer en los mismos clústeres tras varias 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. ^{[ 23 ] [ 10 ] [ 24 ] [ 25 ] [ 26 ] [ 27 ]}

Determinar el número óptimo de clústeres ( k ) para el agrupamiento k -medias es un paso crucial para garantizar que los resultados del agrupamiento sean significativos y útiles. ^{[ 28 ]} Existen varias técnicas 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 consiste en graficar la variación explicada en función del número de clústeres y seleccionar el punto de inflexión de la curva como el número de clústeres a utilizar. ^{[ 29 ]} Sin embargo, la noción de "codo" no está bien definida y se sabe que es poco fiable. ^{[ 30 ]}
• Silueta (agrupamiento) : El análisis de silueta mide la calidad del agrupamiento y proporciona información sobre la distancia de separación entre los grupos resultantes. ^{[ 31 ]} Una puntuación de silueta más alta indica que el objeto se ajusta bien a su propio grupo y se ajusta mal a los grupos vecinos.
• Estadística de brecha : La estadística de brecha compara la variación total dentro del clúster para diferentes valores de k con sus valores esperados bajo la distribución de referencia nula de los datos. ^{[ 32 ]} El valor óptimo de k es el que produce la mayor estadística de brecha.
• Índice de Davies-Bouldin : El índice de Davies-Bouldin es una medida de la separación entre clústeres. ^{[ 33 ]} 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 clústeres en función de su compacidad y separación. Se calcula utilizando la relación entre la varianza entre clústeres y la varianza dentro de los clústeres; valores más altos indican clústeres mejor definidos. ^{[ 34 ]}
• Índice de Rand : Calcula la proporción de concordancia entre dos clústeres, considerando tanto los pares de elementos que se asignan correctamente al mismo clúster como a clústeres diferentes. ^{[ 35 ]} Valores más altos indican mayor similitud y mejor calidad de agrupamiento. Para proporcionar una medida más precisa, el Índice de Rand Ajustado (ARI), introducido por Hubert y Arabie en 1985, corrige el Índice de Rand ajustándolo a la similitud esperada de todos los emparejamientos debido al azar. ^{[ 36 ]}

• Optimización de rupturas naturales de Jenks : k -medias aplicadas a datos univariados
• El agrupamiento k -medianas utiliza la mediana en cada dimensión en lugar de la media, y de esta manera minimiza${\displaystyle L_{1}}$norma ( geometría del taxi ).
• El método k -medoides (también conocido como Particionamiento alrededor de los medoides, PAM) utiliza el medoide en lugar de la media, y de esta manera minimiza la suma de distancias parafunciones de distancia arbitrarias .
• El agrupamiento Fuzzy C-Means es una versión suave de k -means, donde cada punto de datos tiene un grado difuso de pertenencia a cada clúster.
• 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.
• El algoritmo k -means++ elige centros iniciales de forma que proporciona una cota superior demostrable para la función objetivo WCSS.
• El algoritmo de filtrado utiliza árboles k -d para acelerar cada paso de k -medias. ^{[ 37 ]}
• Algunos métodos intentan acelerar cada paso de k -medias utilizando la desigualdad triangular . ^{[ 24 ] [ 25 ] [ 26 ] [ 38 ] [ 27 ]}
• Escapar de los óptimos locales intercambiando puntos entre clústeres. ^{[ 10 ]}
• El algoritmo de agrupamiento k -medias esféricas es adecuado para datos textuales. ^{[ 39 ]}
• Las variantes jerárquicas como el k -medias bisecante, ^{[ 40 ]} el agrupamiento X-means ^{[ 41 ]} y el agrupamiento G-means ^{[ 42 ]} dividen repetidamente los clústeres para construir una jerarquía y también pueden intentar determinar automáticamente el número óptimo de clústeres en un conjunto de datos.
• Las medidas de evaluación interna de clústeres , como el coeficiente de silueta del clúster, pueden ser útiles para determinar el número de clústeres .
• El algoritmo k -means ponderado de Minkowski calcula automáticamente los pesos de las características específicas de cada clúster, lo que respalda la idea intuitiva de que una característica puede tener diferentes grados de relevancia en diferentes momentos. ^{[ 43 ]} Estos pesos también se pueden usar para reescalar un conjunto de datos dado, aumentando la probabilidad de que un índice de validez de clúster se optimice en el número esperado de clústeres. ^{[ 44 ]}
• k -medias de minilotes : variación de k -medias que utiliza muestras de "minilotes" para conjuntos de datos que no caben en la memoria. ^{[ 45 ]}
• El método de Otsu

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

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

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${\displaystyle n,m\in \{1,\ldots ,k\}}$y${\displaystyle x\in S_{n}}$para la cual la siguiente función alcanza un máximo$${\displaystyle \Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\setminus \{x\})-\varphi (S_{m}\cup \{x\}).}$$Para el${\displaystyle x,n,m}$que alcanzan este máximo,${\displaystyle x}$movimientos del grupo${\displaystyle S_{n}}$al grupo${\displaystyle S_{m}}$.

Terminación

El algoritmo finaliza una vez${\displaystyle \Delta (m,n,x)}$es menor que cero para todos${\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 la solución, mientras que en una estrategia de mejor mejora , todas las reubicaciones posibles se prueban iterativamente y solo se aplica la mejor en cada iteración. El primer enfoque favorece la velocidad, mientras que el segundo generalmente favorece la calidad de la solución a costa de un mayor tiempo de cálculo. La función${\displaystyle \Delta }$utilizado para calcular el resultado de una reubicación también puede evaluarse eficientemente mediante el uso de la igualdad ^{[ 46 ]}

$${\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 k -medias clásico y sus variaciones solo convergen a mínimos locales del problema de agrupamiento de suma mínima de cuadrados definido como $${\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}.}$$ 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 analizadas en las secciones anteriores son una alternativa para encontrar mejores soluciones. Más recientemente, los algoritmos de optimización global basados ​​en ramificación y acotación y programación semidefinida han producido soluciones "demostradamente óptimas" para conjuntos de datos con hasta 4177 entidades y 20 531 características. ^{[ 47 ]} Como era de esperar, debido a la NP-dificultad del problema de optimización subyacente, el tiempo de cálculo de los algoritmos óptimos para k -medias aumenta rápidamente más allá de este tamaño. Las soluciones óptimas para escalas pequeñas y medianas 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, ^{[ 48 ]} intercambios aleatorios ^{[ 49 ]} (es decir, búsqueda local iterada ), búsqueda de vecindario variable ^{[ 50 ]} y algoritmos genéticos . ^{[ 51 ] [ 52 ]} 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. ^{[ 52 ]}

En aplicaciones biológicas, las limitaciones del agrupamiento k -means estándar suelen abordarse adaptando las medidas de distancia y las funciones objetivo utilizadas para reflejar mejor la estructura de los datos experimentales. En lugar de basarse en la distancia euclidiana y las medidas de dispersión de clústeres basadas en la varianza, a veces se utilizan métricas de similitud alternativas, como el índice de Jaccard , al analizar conjuntos de datos genómicos con k-means. En estos contextos, el agrupamiento puede realizarse directamente sobre matrices de distancias, y los medoides (puntos de datos representativos que tienen la menor distancia promedio a todos los demás puntos dentro de un clúster) pueden seleccionarse como centros de clúster en lugar de las medias aritméticas. Esto permite que los métodos de agrupamiento capturen patrones de características genómicas compartidas o coocurrencia que no están bien representados en un análisis euclidiano tradicional. ^{[ 55 ]}

El agrupamiento se utiliza ampliamente en el análisis de datos biológicos para identificar patrones en conjuntos de datos de alta dimensionalidad, como perfiles de expresión génica y matrices de interacción genómica. Técnicas como el agrupamiento k -means dividen las observaciones en grupos según su similitud, lo que permite a los investigadores detectar estructuras en conjuntos de datos complejos. En los estudios de expresión génica, el agrupamiento se utiliza comúnmente para agrupar genes con perfiles de expresión similares, revelando a menudo genes corregulados e interacciones biológicas subyacentes. ^{[ 56 ]}

Además del análisis de la expresión génica, se aplican métodos de agrupamiento a los datos de interacción de la cromatina para identificar regiones de actividad coordinada. Medidas de similitud como el índice de Jaccard pueden utilizarse para cuantificar características compartidas entre observaciones, y el agrupamiento de las matrices de distancia resultantes puede revelar la organización estructural dentro del genoma. Estos patrones se visualizan comúnmente mediante mapas de calor, donde las regiones agrupadas corresponden a dominios de interacción o cosegregación, lo que proporciona información sobre la organización reguladora del genoma. ^{[ 55 ]} En tales análisis, el agrupamiento de matrices de similitud o codetección puede revelar grupos de ventanas genómicas que exhiben un comportamiento coordinado en diferentes condiciones experimentales. ^{[ 55 ]}

Los métodos de agrupamiento proporcionan una forma práctica de descubrir estructuras biológicamente significativas a partir de conjuntos de datos complejos. Al agrupar observaciones con patrones similares de detección genómica, expresión o interacción, estas técnicas pueden revelar relaciones funcionales, organización espacial dentro del núcleo y comportamiento regulador. En muchas aplicaciones, los grupos resultantes corresponden a estados biológicos o dominios estructurales distintos, lo que ilustra aún más la amplia aplicabilidad del agrupamiento k-means. ^{[ 56 ]}

La cuantización vectorial , una técnica comúnmente utilizada en el procesamiento de señales y los gráficos por computadora, consiste en reducir la paleta de colores de una imagen a un número fijo de colores, conocido como k . Un método popular para lograr la cuantización vectorial es mediante el agrupamiento k -means. En este proceso, k -means se aplica 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 particularmente ú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 , el agrupamiento k -means se emplea frecuentemente para la cuantificación del color en la compresión de imágenes. Al reducir la cantidad de colores utilizados para representar una imagen, el tamaño de los archivos se puede disminuir significativamente sin una pérdida significativa de calidad visual. Por ejemplo, consideremos una imagen con millones de colores. Al aplicar el agrupamiento k -means con k establecido en un número menor, la imagen se puede representar utilizando una paleta de colores más limitada , lo que resulta en 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 -means se puede utilizar fácilmente para seleccionar k objetos diferentes pero prototípicos de un gran conjunto de datos para su posterior análisis.

El análisis de clústeres , una tarea fundamental en la minería de datos y el aprendizaje automático , consiste en agrupar un conjunto de datos en clústeres según su similitud. El algoritmo k -means es un método popular para dividir los datos en k clústeres, donde cada clúster está representado por su centroide.

Sin embargo, el algoritmo k -medias puro no es muy flexible y, por lo tanto, su utilidad es limitada (excepto cuando la cuantización vectorial, como se mencionó 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 ni con datos no numéricos. Para estos casos de uso, existen muchos otros algoritmos superiores.

Ejemplo: En marketing, el algoritmo k -means se utiliza frecuentemente para la segmentación de mercado , donde se agrupan clientes con características o comportamientos similares. Por ejemplo, una empresa minorista puede usar k -means para segmentar su base de clientes en grupos distintos según factores como el comportamiento de compra, la demografía y la ubicación geográfica. Estos segmentos de clientes pueden ser el objetivo de estrategias de marketing y ofertas de productos personalizadas para maximizar las ventas y la satisfacción del cliente.

El agrupamiento k -means se ha utilizado como un paso de aprendizaje de características (o aprendizaje de diccionario ), ya sea en aprendizaje ( semi ) supervisado o no supervisado . ^{[ 57 ]} El enfoque básico consiste primero en entrenar una representación de agrupamiento k -means, 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 del dato a cada centroide, o simplemente una función indicadora para el centroide más cercano, ^{[ 57 ] [ 58 ]} o alguna transformación suave de la distancia. ^{[ 59 ]} Alternativamente, transformar la distancia muestra-clúster a través de una RBF gaussiana , obtiene la capa oculta de una red de función de base radial . ^{[ 60 ]}

Este uso de k -medias se ha combinado con éxito con clasificadores lineales simples para el aprendizaje semisupervisado en PLN (específicamente para el reconocimiento de entidades nombradas ) ^{[ 61 ]} 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 autoencoders y máquinas de Boltzmann restringidas . ^{[ 59 ]} Sin embargo, generalmente requiere más datos para un rendimiento equivalente, porque cada punto de datos solo contribuye a una "característica". ^{[ 57 ]}

Ejemplo: En el procesamiento del lenguaje natural (PLN), el agrupamiento k -means se ha integrado con clasificadores lineales simples para tareas de aprendizaje semisupervisado, como el reconocimiento de entidades nombradas (REN). Al agrupar primero datos de texto sin etiquetar mediante k -means, se pueden extraer características significativas para mejorar el rendimiento de los modelos de REN . Por ejemplo, el agrupamiento k -means se puede aplicar para identificar grupos de palabras o frases que coocurren con frecuencia en el texto de entrada, las cuales se pueden usar como características para entrenar el modelo de REN. Se ha demostrado que este enfoque logra un rendimiento comparable con técnicas de aprendizaje de características más complejas , como los autoencoders y las máquinas de Boltzmann restringidas , aunque requiere una mayor cantidad de datos etiquetados.

El algoritmo estándar de Lloyd es inherentemente secuencial. Su complejidad temporal efectiva es O(nkdi), lo que se convierte en un cuello de botella a medida que aumenta el número de puntos de datos (n) o dimensiones (d). Esto puede resultar ineficiente al utilizarse con conjuntos de datos masivos y multidimensionales, como las redes sociales. Se han desarrollado diversas estrategias de paralelización para distribuir la carga de trabajo entre procesadores multinúcleo, GPU y clústeres distribuidos.

• Modelo de Memoria Compartida ( OpenMP ): Este enfoque divide el trabajo entre los hilos de la CPU para el paso de reasignación del proceso. Estos hilos calculan de forma independiente las distancias a los centroides. Las sumas parciales y los recuentos de cada hilo se agregan para calcular los nuevos centroides para la siguiente iteración. ^{[ 62 ]}

• Paralelización de GPU ( OpenACC ): A diferencia de la implementación de OpenMP, la directiva parallel del programa OpenACC se llama en cada paso necesario en lugar de al principio. Esto aprovecha la arquitectura SIMT (Single Instruction, Multiple Threads) de las GPU para realizar miles de cálculos de distancia simultáneamente. ^{[ 62 ]}

Observamos que en ambas versiones paralelas, la eficiencia aumenta considerablemente para conjuntos de datos grandes. Esta aceleración es significativa en la implementación de OpenACC, debido a la naturaleza masivamente paralela de las arquitecturas de GPU .

Los modernos estudios astronómicos como APOGEE y el catálogo Gaia recopilan datos espectroscópicos y fotométricos de millones de estrellas, lo que hace que la clasificación manual sea impracticable a gran escala. Se ha aplicado el algoritmo de agrupamiento K -means a estos datos para identificar automáticamente poblaciones estelares distintas basándose en propiedades como la luminosidad, la temperatura, el color y la abundancia química. ^{[ 63 ]}

Una aplicación importante es la identificación de poblaciones estelares mediante el etiquetado químico. Las estrellas que se forman juntas en el mismo cúmulo comparten composiciones químicas similares, por lo que los algoritmos de agrupamiento aplicados a los datos de abundancia pueden recuperar estas agrupaciones incluso después de que las estrellas se hayan dispersado por toda la galaxia. Estudios que utilizaron k -medias en espectros infrarrojos de APOGEE midieron abundancias de hasta 13 elementos y lograron distinguir con éxito cúmulos estelares conocidos de las estrellas de campo circundantes. ^{[ 63 ]} Esto también ha revelado poblaciones con patrones de abundancia inusuales que serían difíciles de detectar mediante inspección manual.

El algoritmo K -means también se ha combinado con técnicas de reducción de dimensionalidad para clasificar un gran número de objetos de estudio sin etiquetar, separando estrellas, galaxias y cuásares según sus propiedades de luz observadas. Las etiquetas de los ejemplos confirmados se propagan a los miembros de cúmulos cercanos. Este enfoque ha logrado una precisión comparable a la de los métodos totalmente supervisados, requiriendo muchos menos ejemplos etiquetados, lo que lo hace idóneo para la escala de los estudios celestes modernos. ^{[ 64 ]}

Una inicialización adecuada es fundamental para encontrar el óptimo global en un algoritmo de agrupamiento. La inicialización aleatoria se usa frecuentemente en el agrupamiento k-means, pero esto puede resultar en clústeres de baja calidad. ^{[ 65 ]} Por esta razón se desarrolló el algoritmo de inicialización k-means++ . ^{[ 65 ]} Este algoritmo busca centros iniciales lo más cercanos posible al óptimo global, reduciendo el tiempo de cálculo y generando clústeres más precisos. ^{[ 65 ]}

El algoritmo k-means++ funciona distribuyendo los centros de los clústeres iniciales. Selecciona el primer centro de forma uniforme y aleatoria del conjunto de datos. Cada centro subsiguiente se elige estocásticamente, con una probabilidad proporcional a su contribución al error total. ^{[ 65 ]} Este método logra una aproximación O(log k) de la solución óptima. ^{[ 65 ]}

El principal inconveniente del algoritmo k-means++ estándar es su naturaleza inherentemente secuencial. Para encontrar k centros iniciales, el algoritmo debe realizar k pasadas separadas sobre los datos, ya que la selección de cada nuevo centro depende de las elecciones anteriores. ^{[ 66 ]} Esto se vuelve prohibitivamente lento al agrupar conjuntos de datos masivos en un gran número de clústeres. ^{[ 66 ]}

Para superar estas limitaciones, los investigadores desarrollaron k-means||, una versión paralela de k-means++ . ^{[ 66 ]} En lugar de muestrear un solo punto por pasada, k-means|| utiliza un factor de sobremuestreo ℓ = Ω (k) para muestrear múltiples puntos en cada ronda. ^{[ 66 ]} El algoritmo reduce drásticamente el número de pasadas necesarias, obteniendo un conjunto de centros casi óptimo con una complejidad temporal de O(log n). ^{[ 66 ]} En la práctica, se necesitan tan solo cinco rondas para alcanzar una solución de alta calidad. Después de varias rondas, el algoritmo suele tener O(log n) centros intermedios. ^{[ 66 ]} A estos se les asignan pesos en función de cuántos puntos están cerca de ellos y se vuelven a agrupar, a menudo utilizando k-means++ estándar , para reducir el conjunto final a k centros exactos. ^{[ 66 ]}

Los avances recientes en la aplicación del algoritmo de agrupamiento k -means han explorado la integración de este algoritmo con métodos de aprendizaje profundo, como las redes neuronales convolucionales (CNN) y las redes neuronales recurrentes (RNN), para mejorar el rendimiento de diversas tareas en visión artificial , procesamiento del lenguaje natural y otros ámbitos.

El lento "algoritmo estándar" para la agrupación k -medias, y su algoritmo de expectativa-maximización asociado , 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. ^{[ 67 ] : 850} En lugar de pequeñas varianzas, también se puede utilizar una asignación de clústeres dura para mostrar otra equivalencia de la agrupación k -medias a un caso especial de modelado de mezcla gaussiana "dura". ^{[ 68 ] : 354, 11.4.2.5} Esto no significa que sea eficiente utilizar el modelado de mezcla gaussiana para calcular k -medias, sino solo que existe una relación teórica, y que el modelado de mezcla gaussiana puede interpretarse como una generalización de k -medias; por el contrario, se ha sugerido utilizar la agrupación k -medias para encontrar puntos de partida para el modelado de mezcla gaussiana en datos difíciles. ^{[ 67 ] : 849}

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

La solución relajada del agrupamiento k -means, especificada por los indicadores de clúster, viene dada por el análisis de componentes principales (PCA). ^{[ 70 ] [ 71 ]} La intuición es que k -means describe clústeres de forma esférica (como una bola). Si los datos tienen 2 clústeres, 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 los clústeres (esta es la relajación continua del indicador de clúster discreto). Si los datos tienen tres clústeres, el plano bidimensional generado por los tres centroides de clúster es la mejor proyección bidimensional. Este plano también está definido por las dos primeras dimensiones de PCA. Los clústeres bien separados se modelan eficazmente mediante clústeres en forma de bola y, por lo tanto, se descubren mediante k -means. Los clústeres que no tienen forma de bola son difíciles de separar cuando están cerca. Por ejemplo, dos clústeres en forma de media luna entrelazados en el espacio no se separan bien cuando se proyectan en el subespacio de PCA. No se debe esperar que k -means funcione bien con estos datos. ^{[ 72 ]} Es sencillo producir contraejemplos a la afirmación de que el subespacio del centroide del clúster está generado por las direcciones principales. ^{[ 73 ]}

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. Luego, todos los puntos se mueven iterativamente hacia la media de los puntos que los rodean. Por el contrario, k -medias restringe el conjunto de clústeres a k clústeres, generalmente 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 -medias, llamado desplazamiento de la media de la verosimilitud , reemplaza el conjunto de puntos que se está reemplazando por la media de todos los puntos en el conjunto de entrada que están dentro de una distancia dada del conjunto que cambia. ^{[ 74 ]} Una ventaja del agrupamiento por desplazamiento de la media sobre k -medias 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 método Mean Shift puede ser mucho más lento que el algoritmo k -means 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 preprocesan 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 . ^{[ 75 ]}

El algoritmo k -means asume implícitamente que el orden de los datos de entrada no importa. El filtro bilateral es similar a k -means y al cambio de media, ya 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 el núcleo) para incluir solo los puntos que están cerca en el orden de los datos de entrada. ^{[ 74 ]} Esto lo hace aplicable a problemas como la eliminación de ruido en imágenes, donde la disposición espacial de los píxeles en una imagen es de vital importancia.

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 en C# para k -means, k -means++ y k- modes.
• ALGLIB contiene implementaciones paralelas en C++ y C# para k -means y k -means++.
• AOSP contiene una implementación en Java para el algoritmo k -medias.
• CrimeStat implementa dos algoritmos k -medias espaciales, uno de los cuales permite al usuario definir las ubicaciones de inicio.
• ELKI incluye el algoritmo k -means (con la 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 incluye k -means y otros algoritmos, así como visualización de resultados (para Java, Kotlin y Scala).
• Julia incluye una implementación del algoritmo k -means en el paquete JuliaStats Clustering.
• KNIME contiene nodos para k -medias y k -medoides.
• Mahout incluye un algoritmo k- means basado en MapReduce .
• mlpack contiene una implementación en C++ del algoritmo k -medias.
• Octave contiene k -medias.
• OpenCV incluye una implementación del algoritmo k -means.
• Orange incluye un componente para la agrupación k -means con selección automática de k y puntuación de la silueta del clúster.
• PSPP contiene k -means. El comando QUICK CLUSTER realiza una agrupación k -means en el conjunto de datos.
• R contiene tres variaciones del algoritmo k -medias.
• SciPy y scikit-learn contienen múltiples implementaciones del algoritmo k -means.
• Spark MLlib implementa un algoritmo k -medias distribuido.
• Torch incluye 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.