Algoritmo de cuantificación vectorial que minimiza la suma de desviaciones al cuadrado.
El clustering de k -medias es un método de cuantificación vectorial , originario del procesamiento de señales , que tiene como objetivo dividir n observaciones en k clusters en los que cada observación pertenece al cluster con la media más cercana (centros de cluster o centroide de cluster ), sirviendo como prototipo de el cúmulo. Esto da como resultado una partición del espacio de datos en celdas Voronoi . La agrupación de k -medias minimiza las variaciones dentro del grupo ( distancias euclidianas al cuadrado ), pero no las distancias euclidianas regulares, lo que sería el problema de Weber más difícil : la media optimiza los errores al cuadrado, mientras que sólo 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-difícil ); sin embargo, los algoritmos heurísticos eficientes convergen rápidamente hacia un óptimo local . Suelen ser similares al algoritmo de maximización de expectativas para mezclas de distribuciones gaussianas mediante un enfoque de refinamiento iterativo empleado tanto por el modelado de k-medias como por mezclas gaussianas . Ambos utilizan centros de conglomerados para modelar los datos; sin embargo, la agrupación de k -medias tiende a encontrar agrupaciones de extensión espacial comparable, mientras que el modelo de mezcla gaussiana permite que las agrupaciones tengan diferentes formas.
El algoritmo k -means no supervisado tiene una relación vaga con el clasificador k -vecino más cercano , una técnica popular de aprendizaje automático supervisado para 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 conglomerados obtenidos por k -means clasifica los datos nuevos en los conglomerados existentes. Esto se conoce como clasificador de centroide más cercano o algoritmo de Rocchio .
Descripción
Dado un conjunto de observaciones ( x 1 , x 2 , ..., x n ) , donde cada observación es un vector real -dimensional, la agrupación de k -means tiene como objetivo dividir las n observaciones en k ( ≤ n ) conjuntos S = { S 1 , S 2 , ..., 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 2 habitual . Esto equivale a minimizar las desviaciones cuadradas por pares de puntos en el mismo grupo:
la equivalencia se puede deducir de la identidad . Dado que la varianza total es constante, esto equivale 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 la varianza total en la teoría de la probabilidad.
Historia
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 técnica para 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, razón por la cual a veces se lo denomina algoritmo de Lloyd-Forgy. [5]
Algoritmos
Algoritmo estándar (ingenuo)k-medio)
Convergencia de k -medias
El algoritmo más común utiliza una técnica de refinamiento iterativo. Debido a su ubicuidad, a menudo se le llama "el algoritmo k -means"; También se le conoce como algoritmo de Lloyd , particularmente en la comunidad informática. A veces también se lo denomina " k -means ingenuo", porque existen alternativas mucho más rápidas. [6]
Dado un conjunto inicial de k significa m 1 (1) , ..., m k (1) (ver más abajo), el algoritmo procede alternando entre dos pasos: [7]
Paso de asignación : Asigne cada observación al grupo con la media más cercana: el que tiene la distancia euclidiana de mínimos cuadrados . [8] (Matemáticamente, esto significa dividir las observaciones de acuerdo con el diagrama de Voronoi generado por las medias), donde cada una se asigna exactamente a una , incluso si se pudiera asignar a dos o más de ellas.
Paso de actualización : recalcular las medias ( centroides ) de las observaciones asignadas a cada grupo.
La función objetivo en k -medias es la WCSS (dentro de la suma de cuadrados del grupo). Después de cada iteración, el WCSS disminuye y, por lo tanto, tenemos una secuencia no negativa monótonamente decreciente. 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, de manera equivalente, cuando el WCSS se ha estabilizado. No se garantiza que el algoritmo encuentre el óptimo. [9]
El algoritmo a menudo se presenta como una asignación de objetos al grupo más cercano por distancia. El uso de una función de distancia diferente a la distancia euclidiana (al cuadrado) puede evitar que el algoritmo converja. Se han propuesto varias modificaciones de 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 de agrupamiento estándar k -means. La inicialización de 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, argmin se utiliza 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 clustersgrupos = [[] para _ en el rango ( k )]# Bucle hasta la convergenciaconvergente = falsomientras no converge :# Borrar grupos anterioresgrupos = [[] para _ en el rango ( k )]# Asignar cada punto al centroide "más cercano"para punto en puntos :distancias_a_cada_centroide = [ distancia ( punto , centroide ) para centroide en centroides ]asignación_clúster = argmin ( distancias_a_cada_centroide )clústeres [ asignación_clúster ] . añadir ( punto )# Calcular nuevos centroides# (la implementación estándar utiliza la media de todos los puntos en un# cluster para determinar el nuevo centroide)new_centroids = [ calcular_centroid ( clúster ) para clúster en clústeres ]convergente = ( nuevos_centroides == centroides )centroides = nuevos_centroidessi converge :grupos de retorno
Métodos de inicialización
Los métodos de inicialización más utilizados son Forgy y Random Partition. [10] El método Forgy elige aleatoriamente k observaciones del conjunto de datos y las utiliza como medio inicial. El método de partición aleatoria primero asigna aleatoriamente un grupo a cada observación y luego continúa con el paso de actualización, calculando así la media inicial como el centroide de los puntos asignados aleatoriamente del grupo. El método Forgy tiende a distribuir los medios iniciales, mientras que la partición aleatoria los coloca todos cerca del centro del conjunto de datos. Según Hamerly et al., [10] el método de partición aleatoria es generalmente preferible para algoritmos como los k -medios armónicos y los k -medios difusos. Para los algoritmos de maximización de expectativas y k -means estándar, es preferible el método de inicialización de Forgy. Sin embargo, un estudio exhaustivo realizado por Celebi et al. [11] encontró que los métodos de inicialización populares como Forgy, Random Partition y Maximin a menudo funcionan mal, mientras que el enfoque de Bradley y Fayyad [12] funciona "consistentemente" en "el mejor grupo". y k -means++ funciona "en general bien".
Demostración del algoritmo estándar.
1. k "medios" iniciales (en este caso k =3) se generan aleatoriamente dentro del dominio de datos (que se muestra en color).
2. k grupos se crean asociando cada observación con la media más cercana. Las particiones aquí representan el diagrama de Voronoi generado por los medios.
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 un 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 -means es polinómico. [14]
El paso de "asignación" se conoce como "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 generalizado de expectativa-maximización .
Complejidad
Encontrar la solución óptima al problema de agrupamiento de k -medias para observaciones en d dimensiones es:
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 que se agruparán. [18]
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 sus variantes) es , [9] [19] donde:
n es el número de vectores d -dimensionales (que se agruparán)
k el número de conglomerados
i el número de iteraciones necesarias hasta la convergencia.
En los datos que tienen una estructura de agrupamiento, el número de iteraciones hasta la convergencia suele ser pequeño y los resultados sólo mejoran ligeramente después de la primera docena de iteraciones. Por lo tanto, a menudo se considera que el algoritmo de Lloyd es de complejidad "lineal" en la práctica, aunque en el peor de los casos es superpolinomio cuando se realiza hasta la convergencia. [20]
En el peor de los casos, el algoritmo de Lloyd necesita iteraciones, por lo que la complejidad del algoritmo de Lloyd en el peor de los casos es superpolinomial . [20]
El algoritmo k -means de Lloyd tiene un tiempo de ejecución polinomial suavizado. Se muestra que [14] para un conjunto arbitrario de n puntos en , si cada punto está perturbado independientemente por una distribución normal con media 0 y varianza , entonces el tiempo de ejecución esperado del algoritmo k -means está limitado por , que es un polinomio en norte , k , d y .
Se han demostrado mejores límites para casos simples. Por ejemplo, se muestra que el tiempo de ejecución del algoritmo k -means está limitado por n puntos en una red de números enteros . [21]
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 k centros del grupo y los n puntos de datos. Dado que los puntos suelen permanecer en los mismos grupos después de algunas 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 del triángulo para crear límites y acelerar el algoritmo de Lloyd. [9] [22] [23] [24] [25]
Número óptimo de grupos
Encontrar el número óptimo de conglomerados ( k ) para la agrupación de k -medias es un paso crucial para garantizar que los resultados de la agrupación sean significativos y útiles. [26] Hay varias técnicas disponibles para determinar un número adecuado de grupos. Éstos son algunos de los métodos comúnmente utilizados:
Método del codo (agrupación) : este método implica trazar la variación explicada en función del número de conglomerados y seleccionar 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 (agrupación) : el análisis de silueta mide la calidad de la agrupación y proporciona información sobre la distancia de separación entre los grupos resultantes. [29] Una puntuación de silueta más alta indica que el objeto coincide bien con su propio grupo y no coincide con los grupos 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 la separación que existe entre los conglomerados. [31] Valores más bajos del índice de Davies-Bouldin indican un modelo con mejor separación.
Índice 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 grupos y la varianza dentro de los grupos; los valores más altos indican grupos mejor definidos. [32]
Índice de Rand : Calcula la proporción de concordancia entre los dos clusters, considerando tanto los pares de elementos que están correctamente asignados al mismo cluster como a diferentes. [33] Los valores más altos indican una mayor similitud y una mejor calidad de agrupación. 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 ajustando la similitud esperada de todos los pares debido al azar. [34]
k -medoids (también: Partitioning Around Medoids, PAM) usa el medoide en lugar de la media, y de esta manera minimiza la suma de distancias para funciones de distancia arbitrarias .
Fuzzy C-Means Clustering es una versión suave de k -means, donde cada punto de datos tiene un grado difuso de pertenencia a cada grupo.
Las medias k ponderadas de Minkowski calculan automáticamente las ponderaciones de características específicas del grupo, lo que respalda la idea intuitiva de que una característica puede tener diferentes grados de relevancia en diferentes características. [41] Estas ponderaciones también se pueden utilizar para volver a escalar un conjunto de datos determinado, aumentando la probabilidad de que un índice de validez de conglomerado se optimice en el número esperado de conglomerados. [42]
Mini-lote k -significa: k -significa variación usando muestras de "mini lote" para conjuntos de datos que no caben en la memoria. [43]
El método de Hartigan y Wong [9] proporciona una variación del algoritmo k -means que progresa 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 ninguna muestra puede reubicarse en un conglomerado diferente con una mejora del objetivo, el método se detiene (en un mínimo local). De manera similar a la clásica k -medias, el enfoque sigue siendo heurístico ya que no garantiza necesariamente que la solución final sea globalmente óptima.
Sea el costo individual de definido por , con el centro del grupo.
Paso de tarea
El método de Hartigan y Wong comienza dividiendo los puntos en grupos aleatorios .
Paso de actualización
A continuación determina el y para el cual la siguiente función alcanza un máximo. Para el que alcanza este máximo, se mueve de un clúster a otro .
Terminación
El algoritmo termina una vez y es menor que cero para todos .
Se pueden utilizar diferentes estrategias de aceptación de movimientos. En una estrategia de primera mejora , se puede aplicar cualquier reubicación mejorada, 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 expensas del tiempo computacional adicional. La función utilizada para calcular el resultado de una reubicación también se puede evaluar eficientemente utilizando la igualdad [44]
Optimización global y metaheurísticas.
Se sabe que el algoritmo clásico k -medias y sus variaciones sólo 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 algoritmo global. óptimo (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 programación semidefinida y ramificada han producido soluciones "comprobadamente óptimas" para conjuntos de datos con hasta 4.177 entidades y 20.531 características. [45] Como se esperaba, debido a la dureza NP 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 pequeñas y medianas escalas 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 optimización, 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, iterados búsqueda local ), 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 en la recuperación de estructuras de conglomerados en espacios de características de alta dimensión. [50]
Discusión
Un ejemplo típico de convergencia de k -medias a un mínimo local. En este ejemplo, el resultado de la agrupación de k -medias (la figura de la derecha) contradice la estructura de agrupación obvia del conjunto de datos. Los círculos pequeños son los puntos de datos, las estrellas de cuatro rayos son los centroides (medias). La configuración inicial está en la figura de la izquierda. El algoritmo converge después de cinco iteraciones presentadas en las figuras, de izquierda a derecha. La ilustración fue preparada con el subprograma Java Mirkes. [51]k -significa resultado de agrupación para el conjunto de datos de flores de Iris y las especies reales visualizadas usando ELKI . Las medias de los grupos se marcan utilizando símbolos semitransparentes más grandes.k -significa agrupación frente a agrupación EM en un conjunto de datos artificial ("ratón"). La tendencia de k -medias a producir grupos del mismo tamaño conduce a malos resultados aquí, mientras que EM se beneficia de las distribuciones gaussianas con diferentes radios presentes en el conjunto de datos.
Tres características clave de k -means que lo hacen eficiente a menudo se consideran sus mayores inconvenientes:
El número de grupos k es un parámetro de entrada: una elección inapropiada de k puede producir malos resultados. Por eso, al realizar k -medias, es importante ejecutar comprobaciones de diagnóstico para determinar la cantidad de grupos en el conjunto de datos .
La convergencia a un mínimo local puede producir resultados contrarios a la intuición ("incorrectos") (ver ejemplo en la Fig.).
Una limitación clave de k -means es su modelo de clúster. El concepto se basa en grupos esféricos que son separables de modo que la media converge hacia el centro del grupo. Se espera que los conglomerados sean de tamaño similar, de modo que la asignación al centro de conglomerados más cercano sea la asignación correcta. Cuando, por ejemplo, se aplican k -means con un valor de al conocido conjunto de datos de flores 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 grupos visibles (uno que contiene dos especies), mientras que con uno de los dos grupos se dividirá en dos partes pares. De hecho, es más apropiado para este conjunto de datos, a pesar de que el conjunto de datos contiene 3 clases . Como ocurre con cualquier otro algoritmo de agrupamiento, el resultado de k -means supone que los datos satisfacen ciertos criterios. Funciona bien con algunos conjuntos de datos y falla con otros.
El resultado de k -means puede verse como las células de Voronoi del grupo de medias. Dado que los datos se dividen a mitad de camino entre las medias del grupo, esto puede dar lugar a divisiones subóptimas, como se puede ver en el ejemplo del "ratón". Los modelos gaussianos utilizados por el algoritmo de maximización de expectativas (posiblemente una generalización de k -medias) son más flexibles al tener varianzas y covarianzas. Por lo tanto, el resultado de EM es capaz de acomodar grupos de tamaño variable mucho mejor que k -medias, así como grupos correlacionados (no en este ejemplo). Por el contrario, EM requiere la optimización de un mayor número de parámetros libres y plantea algunos problemas metodológicos debido a la desaparición de clusters o matrices de covarianza mal condicionadas. k -means está estrechamente relacionado con el modelado bayesiano no paramétrico . [52]
Aplicaciones
La agrupación en clústeres de k -medias es bastante fácil de aplicar incluso a conjuntos de datos grandes, especialmente cuando se utilizan heurísticas como el algoritmo de Lloyd . Se ha utilizado con éxito en segmentación de mercados , visión por computadora y astronomía , entre muchos otros dominios. A menudo se utiliza como paso de preprocesamiento para otros algoritmos, por ejemplo para encontrar una configuración inicial.
Cuantización vectorial
La cuantización vectorial , una técnica comúnmente utilizada en el procesamiento de señales y gráficos por computadora, implica 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 cuantificación vectorial es mediante la agrupación de k -medias. En este proceso, se aplica k -means al espacio de color de una imagen para dividirlo 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.
Imagen de ejemplo con solo canal rojo y verde (con fines ilustrativos)Cuantización vectorial de colores presentes en la imagen de arriba en celdas de Voronoi usando k -medias
Ejemplo: en el campo de los gráficos por computadora , la agrupación de k -medias a menudo se emplea 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 reducir significativamente sin una pérdida significativa de calidad visual. Por ejemplo, considere una imagen con millones de colores. Al aplicar la agrupación k -means con k establecido en un número menor, la imagen se puede representar usando 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 usar fácilmente para elegir k objetos diferentes pero prototípicos de un gran conjunto de datos para su posterior análisis.
Análisis de conglomerados
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. La agrupación de k -means es un algoritmo popular que se utiliza para dividir datos en k grupos, donde cada grupo está representado por su centroide.
Sin embargo, el algoritmo k -means puro no es muy flexible y, como tal, tiene un uso limitado (excepto cuando la cuantificación vectorial como la anterior es en realidad el caso de uso deseado). En particular, se sabe que el parámetro k es difícil de elegir (como se analizó 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 clientes con características o comportamientos similares. Por ejemplo, una empresa minorista puede utilizar la agrupación k -means para segmentar su base de clientes en distintos grupos en función de factores como el comportamiento de compra, la demografía y la ubicación geográfica. Luego, estos segmentos de clientes pueden orientarse con estrategias de marketing y ofertas de productos personalizadas para maximizar las ventas y la satisfacción del cliente.
Aprendizaje de funciones
La agrupación de k -medias se ha utilizado como un paso de aprendizaje de características (o aprendizaje de diccionario ), ya sea en aprendizaje ( semi ) supervisado o no supervisado . [53] El enfoque básico es primero entrenar una representación de agrupamiento de k -medias, utilizando los datos de entrenamiento de entrada (que no necesitan etiquetarse). 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 muestra-grupo a través de un RBF gaussiano , se obtiene la capa oculta de una red de función de base radial . [56]
Este uso de k -means se ha combinado con éxito con clasificadores lineales simples para el aprendizaje semisupervisado en PNL (específicamente para el reconocimiento de entidades nombradas ) [57] y en visión por computadora . En una tarea de reconocimiento de objetos, se descubrió que exhibía un rendimiento comparable con enfoques de aprendizaje de características más sofisticados, como codificadores automáticos y máquinas Boltzmann restringidas . [55] Sin embargo, generalmente requiere más datos para un rendimiento equivalente, porque cada punto de datos sólo contribuye a una "característica". [53]
Ejemplo: en el procesamiento del lenguaje natural (PNL), la agrupación de k -means se ha integrado con clasificadores lineales simples para tareas de aprendizaje semisupervisadas, como el reconocimiento de entidades nombradas]] (NER). Al agrupar primero datos de texto sin etiquetar utilizando k -means, se pueden extraer características significativas para mejorar el rendimiento de los modelos NER. Por ejemplo, la agrupación de k -means se puede aplicar para identificar grupos de palabras o frases que coexisten con frecuencia en el texto de entrada, que luego se pueden utilizar como características para entrenar el modelo NER. Se ha demostrado que este enfoque logra un rendimiento comparable con técnicas de aprendizaje de funciones más complejas , como codificadores automáticos y máquinas Boltzmann restringidas , aunque con un mayor requisito de datos etiquetados.
Desarrollos recientes
Los avances recientes en la aplicación de la agrupación de k -means incluyen mejoras en las técnicas de inicialización, como el uso de la inicialización de k -means++ para seleccionar los centroides del grupo inicial de una manera más efectiva. Además, los investigadores han explorado la integración de la agrupación 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 diversas tareas en visión por computadora , procesamiento del lenguaje natural y otras. dominios.
Relación con otros algoritmos
modelo de mezcla gaussiana
El lento "algoritmo estándar" para la agrupación de k -medias y su algoritmo de maximización de expectativas asociado es un caso especial de un modelo de mezcla gaussiano, específicamente, el caso límite cuando se fijan todas las covarianzas para que sean diagonales, iguales y tengan una varianza pequeña infinitesimal. [58] : 850 En lugar de pequeñas variaciones, también se puede utilizar una asignación de conglomerado estricto para mostrar otra equivalencia de 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 mezclas gaussianas para calcular k -medias, sino simplemente que existe una relación teórica y que el modelado de mezclas gaussianas puede interpretarse como una generalización de k. -medio; por el contrario, se ha sugerido utilizar agrupamiento de k -medias para encontrar puntos de partida para el modelado de mezclas gaussianas en datos difíciles. [58] : 849
k-SVD
Otra generalización del algoritmo k -means es el algoritmo k -SVD, que estima 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]
Análisis de componentes principales
La solución relajada de la agrupación de k -medias, especificada por los indicadores de agrupación, viene dada por el análisis de componentes principales (PCA). [61] [62] La intuición es que k -means describe grupos de forma esférica (en forma de bola). Si los datos tienen 2 grupos, 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 PCA. Cortar la línea en el centro de masa separa los grupos (esta es la relajación continua del indicador de grupo discreto). Si los datos tienen tres grupos, el plano bidimensional abarcado por tres centroides del grupo es la mejor proyección 2D. Este plano también está definido por las dos primeras dimensiones PCA. Los grupos bien separados se modelan eficazmente mediante grupos en forma de bola y, por lo tanto, se descubren mediante k -medias. Los racimos que no tienen forma de bola son difíciles de separar cuando están cerca. Por ejemplo, dos cúmulos en forma de media luna entrelazados en el espacio no se separan bien cuando se proyectan en el subespacio 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]
Agrupación de cambios medios
Los algoritmos básicos de agrupamiento por desplazamiento medio 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 conglomerados a k conglomerados, normalmente mucho menos que el número de puntos en el conjunto de datos de entrada, utilizando la media de todos los puntos del conglomerado anterior que están más cerca de ese punto que cualquier otro para el centroide (por ejemplo, dentro de la partición Voronoi de cada punto de actualización). Un algoritmo de cambio de media que es similar a k -medias, llamado cambio de media de probabilidad , reemplaza el conjunto de puntos que se reemplazan por la media de todos los puntos en el conjunto de entrada que están dentro de una distancia determinada del conjunto cambiante. [65] Una ventaja de la agrupación por desplazamiento medio sobre k -medias es la detección de un número arbitrario de agrupaciones en el conjunto de datos, ya que no hay un parámetro que determine el número de agrupaciones. El cambio medio puede ser mucho más lento que k -medias y aún requiere la selección de un parámetro de ancho de banda.
Análisis de componentes independientes
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 lineal de componentes independientes (ICA). Esto ayuda a explicar la aplicación exitosa de k -means al aprendizaje de funciones. [66]
Filtrado bilateral
k -means supone implícitamente que el orden del conjunto de datos de entrada no importa. El filtro bilateral es similar a k -medias y 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.
Problemas similares
El conjunto de funciones de conglomerado que minimizan el error al cuadrado también incluye el algoritmo k -medoides , un enfoque que obliga al punto central de cada conglomerado a ser uno de los puntos reales, es decir, utiliza medoides en lugar de centroides .
Implementaciones de software
Las diferentes implementaciones del algoritmo exhiben diferencias de rendimiento: la más rápida en un conjunto de datos de prueba finaliza en 10 segundos, la más lenta tarda 25 988 segundos (~7 horas). [1] Las diferencias se pueden atribuir a la calidad de la implementación, diferencias de lenguaje y compilador, diferentes criterios de terminación y niveles de precisión, y el uso de índices para la aceleración.
Software libre/código abierto
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 paralelizadas de C++ y C# para k -means y k -means++.
AOSP contiene una implementación Java para k -means.
CrimeStat implementa dos algoritmos espaciales k -means, 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 de 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.
Orange incluye un componente para agrupación de k -medias con selección automática de k y puntuación de silueta de agrupación.
PSPP contiene k -means. El comando QUICK CLUSTER realiza k -means agrupación 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 distribuido de k -means.
Torch contiene un paquete unsup que proporciona agrupación k -means.
Weka contiene k -medias y x -medias.
Propiedad
Las siguientes implementaciones están disponibles bajo términos de licencia patentados y es posible que no tengan un código fuente disponible públicamente.
^ ab Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). "El arte (negro) de la evaluación del tiempo de ejecución: ¿estamos comparando algoritmos o implementaciones?". Sistemas de Conocimiento y Información . 52 (2): 341–378. doi :10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.
^ MacQueen, JB (1967). Algunos Métodos de Clasificación y Análisis de Observaciones Multivariadas. Actas del V Simposio de Berkeley sobre probabilidad y estadística matemática. vol. 1. Prensa de la Universidad de California. págs. 281–297. SEÑOR 0214227. Zbl 0214.46201 . Consultado el 7 de abril de 2009 .
^ Steinhaus, Hugo (1957). "Sur la division des corps matériels en Parties". Toro. Acad. Polon. Ciencia. (en francés). 4 (12): 801–804. Señor 0090073. Zbl 0079.16403.
^ Lloyd, Stuart P. (1957). "Cuantización de mínimos cuadrados en PCM". Documento de Bell Telephone Laboratories .Publicado en una revista mucho más tarde: Lloyd, Stuart P. (1982). «Cuantización de mínimos cuadrados en PCM» (PDF) . Transacciones IEEE sobre teoría de la información . 28 (2): 129-137. CiteSeerX 10.1.1.131.1338 . doi :10.1109/TIT.1982.1056489. S2CID 10833328 . Consultado el 15 de abril de 2009 .
^ Forgy, Edward W. (1965). "Análisis de conglomerados de datos multivariados: eficiencia versus interpretabilidad de las clasificaciones". Biometría . 21 (3): 768–769. JSTOR 2528559.
^ Pelleg, Dan; Moore, Andrés (1999). "Acelerar algoritmos k exactos -significa con razonamiento geométrico". Actas de la quinta conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . San Diego, California, Estados Unidos: ACM Press. págs. 277–281. doi :10.1145/312129.312248. ISBN9781581131437. S2CID 13907420.
^ MacKay, David (2003). "Capítulo 20. Un ejemplo de tarea de inferencia: agrupación" (PDF) . Teoría de la información, inferencia y algoritmos de aprendizaje. Prensa de la Universidad de Cambridge. págs. 284–292. ISBN978-0-521-64298-9. SEÑOR 2012999.
^ Dado que la raíz cuadrada es una función monótona, esta también es la asignación de distancia euclidiana mínima.
^ ab Hamerly, Greg; Elkan, Charles (2002). "Alternativas al algoritmo k-means que encuentran mejores agrupaciones" (PDF) . Actas de la undécima conferencia internacional sobre gestión de la información y el conocimiento (CIKM) .
^ Celebi, YO; Kingravi, HA; Vela, PA (2013). "Un estudio comparativo de métodos de inicialización eficientes para el algoritmo de agrupamiento de k -medias". Sistemas Expertos con Aplicaciones . 40 (1): 200–210. arXiv : 1209.1960 . doi :10.1016/j.eswa.2012.07.021. S2CID 6954668.
^ Bradley, Paul S.; Fayyad, Usama M. (1998). "Refinamiento de puntos iniciales para k -Agrupación de medios". Actas de la Decimoquinta Conferencia Internacional sobre Aprendizaje Automático .
^ Vattani, A. (2011). "k-means requiere exponencialmente muchas iteraciones incluso en el plano" (PDF) . Geometría Discreta y Computacional . 45 (4): 596–616. doi : 10.1007/s00454-011-9340-1 . S2CID 42683406.
^ ab Arturo, David; Manthey, B.; Roeglin, H. (2009). "k-means tiene una complejidad polinómica suavizada". Actas del 50º Simposio sobre fundamentos de la informática (FOCS) . arXiv : 0904.1113 .
^ Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). "NP-dureza de la agrupación de sumas de cuadrados euclidiana". Aprendizaje automático . 75 (2): 245–249. doi : 10.1007/s10994-009-5103-0 .
^ Dasgupta, S.; Freund, Y. (julio de 2009). "Árboles de proyección aleatoria para cuantificación de vectores". Transacciones IEEE sobre teoría de la información . 55 (7): 3229–42. arXiv : 0805.1390 . doi :10.1109/TIT.2009.2021326. S2CID 666114.
^ Mahajan, Meena; Nimbhorkar, Prajakta; Varadarajan, Kasturi (2009). "El problema plano de k-medias es NP-difícil". WALCOM: Algoritmos y Computación . Apuntes de conferencias sobre informática. vol. 5431, págs. 274–285. doi :10.1007/978-3-642-00202-1_24. ISBN978-3-642-00201-4.
^ Inaba, M.; Katoh, N.; Imai, H. (1994). "Aplicaciones de diagramas de Voronoi ponderados y aleatorización a k -clustering basado en varianza" . Actas del décimo simposio ACM sobre geometría computacional . págs. 332–9. doi : 10.1145/177424.178042 .
^ Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (2008). Introducción a la recuperación de información . Prensa de la Universidad de Cambridge. ISBN978-0521865715. OCLC 190786122.
^ ab Arturo, David; Vassilvitskii, Sergei (1 de enero de 2006). "¿Qué tan lento es el método k -means?". Actas del vigésimo segundo simposio anual sobre geometría computacional . SCG '06. ACM. págs. 144-153. doi :10.1145/1137856.1137880. ISBN978-1595933409. S2CID 3084311.
^ Bhowmick, Abhishek (2009). "Un análisis teórico del algoritmo de Lloyd para la agrupación de k-medias" (PDF) . Archivado desde el original (PDF) el 8 de diciembre de 2015.Ver también aquí.
^ ab Phillips, Steven J. (2002). "Aceleración de K-Means y algoritmos de agrupación relacionados". En Monte, David M.; Stein, Clifford (eds.). "Aceleración de k -Means y algoritmos de agrupamiento relacionados" . Apuntes de conferencias sobre informática. vol. 2409. Saltador. págs. 166-177. doi :10.1007/3-540-45643-0_13. ISBN978-3-540-43977-6.
^ ab Elkan, Charles (2003). "Uso de la desigualdad del triángulo para acelerar k-medias" (PDF) . Actas de la vigésima conferencia internacional sobre aprendizaje automático (ICML) .
^ ab Hamerly, Greg (2010). "Hacer k-means aún más rápido". Actas de la Conferencia Internacional SIAM 2010 sobre Minería de Datos . págs. 130-140. doi :10.1137/1.9781611972801.12. ISBN978-0-89871-703-7.
^ ab Hamerly, Greg; Drake, Jonathan (2015). "Aceleración del algoritmo de Lloyd para la agrupación de k-medias". Algoritmos de agrupamiento particional . págs. 41–78. doi :10.1007/978-3-319-09259-1_2. ISBN978-3-319-09258-4.
^ Abiodun M. Ikotun, Absalom E. Ezugwu, Laith Abualigah, Belal Abuhaija, Jia Heming, Algoritmos de agrupamiento de K-means: una revisión exhaustiva, análisis de variantes y avances en la era del big data, Ciencias de la información, volumen 622, 2023, Páginas 178–210, ISSN 0020-0255, https://doi.org/10.1016/j.ins.2022.11.139.
^ 276.doi:10.1007/BF02289263. S2CID 120467216.
^ Schubert, Erich (22 de junio de 2023). "Deje de utilizar el criterio del codo para k-medias y, en su lugar, elija cómo elegir el número de grupos". Boletín de exploraciones de ACM SIGKDD. 25 (1): 36–42. arXiv:2212.12189. doi:10.1145/3606274.3606278. ISSN 1931-0145.
^ Peter J. Rousseeuw (1987). "Siluetas: una ayuda gráfica para la interpretación y validación del análisis de conglomerados". Matemática Computacional y Aplicada. 20: 53–65. doi:10.1016/0377-0427(87)90125-7.
^ Robert Tibshirani; Günther Walther; Trevor Hastie (2001). "Estimación del número de grupos en un conjunto de datos mediante la estadística de brecha". Revista de la Royal Statistical Society, Serie B. 63 (2): 411–423. doi:10.1111/1467-9868.00293. S2CID 59738652.
^ Davies, David L.; Bouldin, Donald W. (1979). "Una medida de separación de grupos". Transacciones IEEE sobre análisis de patrones e inteligencia artificial. PAMI-1 (2): 224–227. doi:10.1109/TPAMI.1979.4766909. S2CID 13254783.
^ Caliński, Tadeusz; Harabasz, Jerzy (1974). "Un método de dendritas para el análisis de conglomerados". Comunicaciones en Estadística. 3 (1): 1–27. doi:10.1080/03610927408827101.
^ WM Rand (1971). "Criterios objetivos para la evaluación de métodos de agrupamiento". Revista de la Asociación Estadounidense de Estadística. 66 (336). Asociación Estadounidense de Estadística: 846–850. doi:10.2307/2284239. JSTOR 2284239.
^ Hubert, L. y Arabie, P. (1985). Hubert, L. y Arabie, P. (1985). Comparando particiones. Revista de clasificación, 2(1), 193-218. https://doi.org/10.1007/BF01908075
^ Kanungo, Tapas; Monte, David M .; Netanyahu, Nathan S .; Piatko, Christine D .; Silverman, Rut; Wu, Ángela Y. (2002). "Un algoritmo de agrupamiento de k-medias eficiente: análisis e implementación" (PDF) . Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 24 (7): 881–892. doi :10.1109/TPAMI.2002.1017616. S2CID 12003435 . Consultado el 24 de abril de 2009 .
^ Pato, Jonathan (2012). "K-medias aceleradas con límites de distancia adaptativos" (PDF) . El quinto taller de NIPS sobre optimización para el aprendizaje automático, OPT2012 .
^ Dhillon, ES; Modha, DM (2001). "Descomposiciones de conceptos para datos de texto grandes y dispersos mediante agrupación". Aprendizaje automático . 42 (1): 143-175. doi : 10.1023/a:1007612920971 .
^ Steinbach, M.; Karypis, G.; Kumar, V. (2000). ""Una comparación de técnicas de agrupación de documentos". En". Taller KDD sobre minería de textos . 400 (1): 525–526.
^ Pelleg, D.; y Moore, AW (2000, junio). "X-means: ampliación de k-means con estimación eficiente del número de conglomerados". En ICML , vol. 1
^ Amorim, RC; Mirkin, B. (2012). "Métrica de Minkowski, ponderación de características e inicialización de clústeres anómalos en agrupación de k -Means". Reconocimiento de patrones . 45 (3): 1061-1075. doi :10.1016/j.patcog.2011.08.012.
^ Amorim, RC; Hennig, C. (2015). "Recuperar la cantidad de grupos en conjuntos de datos con características de ruido utilizando factores de reescalado de características". Ciencias de la Información . 324 : 126-145. arXiv : 1602.06989 . doi :10.1016/j.ins.2015.06.039. S2CID 315803.
^ Sculley, David (2010). "Agrupación de k-means a escala web". Actas de la 19ª conferencia internacional sobre la World Wide Web . ACM. págs. 1177-1178 . Consultado el 21 de diciembre de 2016 .
^ Telgarsky, Matus. "Método de Hartigan: k-significa agrupación sin Voronoi" (PDF) .
^ Piccialli, Verónica; Sudoso, Antonio M.; Wiegele, Angelika (28 de marzo de 2022). "SOS-SDP: un solucionador exacto para agrupaciones mínimas de suma de cuadrados". Revista INFORMA de Informática . 34 (4): 2144–2162. arXiv : 2104.11542 . doi :10.1287/ijoc.2022.1166. ISSN 1091-9856. S2CID 233388043.
^ Bagírov, AM; Taheri, S.; Ugón, J. (2016). "Enfoque de programación DC no suave para los problemas de agrupación de suma mínima de cuadrados". Reconocimiento de patrones . 53 : 12-24. Código Bib : 2016PatRe..53...12B. doi :10.1016/j.patcog.2015.11.011.
^ Fränti, Pasi (2018). "Eficiencia de la agrupación de intercambio aleatorio". Revista de Big Data . 5 (1): 1–21. doi : 10.1186/s40537-018-0122-y .
^ Hansen, P.; Mladenovic, N. (2001). "J-Means: una nueva heurística de búsqueda local para la agrupación de suma mínima de cuadrados". Reconocimiento de patrones . 34 (2): 405–413. Código Bib : 2001PatRe..34..405H. doi :10.1016/S0031-3203(99)00216-2.
^ Krishna, K.; Murty, MN (1999). "Algoritmo genético k-means". Transacciones IEEE sobre sistemas, hombre y cibernética - Parte B: Cibernética . 29 (3): 433–439. doi : 10.1109/3477.764879. PMID 18252317.
^ ab Gribel, Daniel; Vidal, Thibaut (2019). "HG-medias: una metaheurística híbrida escalable para agrupaciones mínimas de suma de cuadrados". Reconocimiento de patrones . 88 : 569–583. arXiv : 1804.09813 . doi :10.1016/j.patcog.2018.12.022. S2CID 13746584.
^ Mirkes, EM "Subprograma K-means y k-medoids" . Consultado el 2 de enero de 2016 .
^ Kulis, Brian; Jordania, Michael I. (26 de junio de 2012). "Revisando k-means: nuevos algoritmos mediante métodos no paramétricos bayesianos" (PDF) . ICML . págs. 1131-1138. ISBN9781450312851.
^ abc Coates, Adán; Ng, Andrew Y. (2012). "Aprendizaje de representaciones de funciones con k-medias" (PDF) . En Montavon, G.; Orr, GB; Müller, K.-R. (eds.). Redes neuronales: trucos del oficio . Saltador.
^ Csurka, Gabriella; Danza, Christopher C.; Fan, Lixin; Willamowski, Jutta; Bray, Cédric (2004). Categorización visual con bolsas de puntos clave (PDF) . Taller ECCV sobre Aprendizaje Estadístico en Visión por Computador.
^ ab Coates, Adán; Lee, Honglak; Ng, Andrew Y. (2011). Un análisis de redes de una sola capa en el aprendizaje de funciones no supervisadas (PDF) . Congreso Internacional sobre Inteligencia Artificial y Estadística (AISTATS). Archivado desde el original (PDF) el 10 de mayo de 2013.
^ Schwenker, Friedhelm; Kestler, Hans A.; Palma, Günther (2001). "Tres fases de aprendizaje para redes de función de base radial". Redes neuronales . 14 (4–5): 439–458. CiteSeerX 10.1.1.109.312 . doi :10.1016/s0893-6080(01)00027-2. PMID 11411631.
^ Lin, Dekang; Wu, Xiaoyun (2009). Agrupación de frases para el aprendizaje discriminativo (PDF) . Reunión Anual de la ACL y IJCNLP. págs. 1030-1038.
^ ab Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 16.1. Modelos de mezclas gaussianas y agrupación de k-medias". Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York (NY): Cambridge University Press. ISBN978-0-521-88068-8.
^ Kevin P. Murphy (2012). Aprendizaje automático: una perspectiva probabilística . Cambridge, Massachusetts: MIT Press. ISBN978-0-262-30524-2. OCLC 810414751.
^ Aarón, Mical ; Elad, Michael; Bruckstein, Alfred (2006). "K-SVD: un algoritmo para diseñar diccionarios sobrecompletos para una representación escasa" (PDF) . Transacciones IEEE sobre procesamiento de señales . 54 (11): 4311. Código bibliográfico : 2006ITSP...54.4311A. doi :10.1109/TSP.2006.881199. S2CID 7477309.
^ Zha, Hongyuan; Ding, Chris; Gu, Ming; Él, Xiaofeng; Simon, Horst D. (diciembre de 2001). "Relajación espectral para agrupación de k-medias" (PDF) . Sistemas de procesamiento de información neuronal Vol.14 (NIPS 2001) : 1057–1064.
^ Ding, Chris; Él, Xiaofeng (julio de 2004). "Agrupación de K-medias mediante análisis de componentes principales" (PDF) . Actas de la Conferencia Internacional sobre Aprendizaje Automático (ICML 2004) : 225–232.
^ Drineas, Petros; Friso, Alan M.; Kannan, Ravi; Vempala, Santosh; Vinay, Vishwanathan (2004). "Agrupación de gráficos grandes mediante la descomposición de valores singulares" (PDF) . Aprendizaje automático . 56 (1–3): 9–33. doi : 10.1023/b:mach.0000033113.59016.96 . S2CID 5892850 . Consultado el 2 de agosto de 2012 .
^ Cohen, Michael B.; Mayor, Sam; Musco, Cameron; Musco, Cristóbal; Persu, Madalina (2014). "Reducción de dimensionalidad para k -medias agrupación y aproximación de rango bajo (Apéndice B)". arXiv : 1410.6801 [cs.DS].
^ ab Pequeño, Max A.; Jones, Nick S. (2011). "Métodos generalizados y solucionadores para la eliminación de ruido de señales constantes por partes. I. Teoría de antecedentes". Actas de la Royal Society A. 467 (2135): 3088–3114. doi :10.1098/rspa.2010.0671. PMC 3191861 . PMID 22003312.
^ Vínnikov, Alon; Shalev-Shwartz, Shai (2014). "K-means recupera filtros ICA cuando los componentes independientes son escasos" (PDF) . Actas de la Conferencia Internacional sobre Aprendizaje Automático (ICML 2014) .