k-significa agrupamiento

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-duro ); 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 el de 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 ₁ , x ₂ , ..., 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 ₁ , S ₂ , ..., S _k } para minimizar la suma de cuadrados dentro del grupo (WCSS) (es decir, la varianza ). Formalmente el objetivo es encontrar: ${\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}}$$

μ _i ${\displaystyle S_{i}}$

$${\displaystyle {\boldsymbol {\mu _{i}}}={\frac {1}{|S_{i}|}}\sum _{\mathbf {x} \in S_{i}}\mathbf {x} ,}$$

${\displaystyle |S_{i}|}$norma habitual L 2 ${\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}}$$

diferentes^[1]ley de la varianza total ${\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}}$

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 (k-medias ingenuas)

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 ingenuos", porque existen alternativas mucho más rápidas. ^[6]

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

1. 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).
   $${\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 uno se asigna exactamente a uno , incluso si se pudiera asignar a dos o más de ellos. ${\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}}$$

El algoritmo ha convergido cuando las asignaciones ya no cambian. 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.

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 -medias 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 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 generalizado de maximización de expectativas .

Complejidad

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

• NP-duro en el espacio euclidiano general (de d dimensiones) incluso para dos grupos, ^{[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 que se agruparán. ^[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 sus variantes) es , ^{[9] [19]} donde: ${\displaystyle O(nkdi)}$

• 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] ${\displaystyle i=2^{\Omega ({\sqrt {n}})}}$
• 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 . ${\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 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] ${\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 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]}

Variaciones

• 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) 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.
• Los modelos de mezcla gaussiana entrenados con el algoritmo de maximización de expectativas (algoritmo EM) mantienen asignaciones probabilísticas a grupos, en lugar de asignaciones deterministas, y distribuciones gaussianas multivariadas en lugar de medias.
• k -means++ elige los centros iniciales de una manera que proporcione un límite superior demostrable en el objetivo de WCSS.
• El algoritmo de filtrado utiliza árboles kd para acelerar cada paso de k -medias. ^[26]
• Algunos métodos intentan acelerar cada paso de k -medias utilizando la desigualdad triangular . ^{[22] [23] [24] [27] [25]}
• Escapar de los óptimos locales intercambiando puntos entre grupos. ^[9]
• El algoritmo de agrupamiento de medias k esféricas es adecuado para datos textuales. ^[28]
• Las variantes jerárquicas como Bisecting k -means, ^[29] X-means clustering ^[30] y G-means clustering ^[31] dividen repetidamente los clusters para construir una jerarquía y también pueden intentar determinar automáticamente el número óptimo de clusters en un conjunto de datos. .
• Las medidas internas de evaluación de conglomerados, como la silueta de los conglomerados, pueden ser útiles para determinar el número de conglomerados .
• 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. ^[32] 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. ^[33]
• Mini-lote k -significa: k -significa variación usando muestras de "mini lote" para conjuntos de datos que no caben en la memoria. ^[34]
• El método de Otsu

Método Hartigan-Wong

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 necesariamente garantiza que la solución final sea globalmente óptima.

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

Paso de tarea

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 ${\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\}).}$$

Para el que alcanza este máximo, se pasa de un clúster a otro . ${\displaystyle x,n,m}$ ${\displaystyle x}$ ${\displaystyle S_{n}}$ ${\displaystyle S_{m}}$

Terminación

El algoritmo termina una vez y 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 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 ^[35] ${\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}.}$$

Optimización global y metaheurísticas.

Se sabe que el algoritmo clásico de k-medias 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}.}$$

programación semidefinida^[36]dureza NPmetaheurísticasde optimización global^[37][38]iterados búsqueda localbúsqueda de vecindad variable ^[39]algoritmos genéticos^{[40] [41][41]}

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. ^[42]

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:

• La distancia euclidiana se utiliza como métrica y la varianza como medida de dispersión de conglomerados.
• 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. ${\displaystyle k=3}$ ${\displaystyle k=2}$ ${\displaystyle k=3}$ ${\displaystyle k=2}$

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 llevar 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 . ^[43]

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

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

k -means se origina en el procesamiento de señales y todavía encuentra uso en este dominio. Por ejemplo, en gráficos por computadora , la cuantificación del color es la tarea de reducir la paleta de colores de una imagen a un número fijo de colores k . El algoritmo k -means se puede utilizar fácilmente para esta tarea y produce resultados competitivos. Un caso de uso para este enfoque es la segmentación de imágenes . 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

En el análisis de conglomerados, el algoritmo k -means se puede utilizar para dividir el conjunto de datos de entrada en k particiones (clústeres).

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.

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 . ^[44] 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, ^{[44] [45]} o alguna transformación suave de la distancia. ^[46] 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 . ^[47]

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 ) ^[48] 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 . ^[46] Sin embargo, generalmente requiere más datos, para un rendimiento equivalente, porque cada punto de datos sólo contribuye a una "característica". ^[44]

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. ^{[49] : 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". ^{[50] : 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 la agrupación de k-medias para encontrar puntos de partida para el modelado de mezclas gaussianas en datos difíciles. ^{[49] : 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. ^[51]

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). ^{[52] [53]} 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. ^[54] Es sencillo producir contraejemplos a la afirmación de que el subespacio del centroide del grupo está abarcado por las direcciones principales. ^[55]

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, este conjunto se reemplaza iterativamente por la media de aquellos puntos del conjunto que están dentro de una distancia determinada de ese punto. Por el contrario, k -means restringe este conjunto actualizado a k puntos, generalmente mucho menos que el número de puntos en el conjunto de datos de entrada, y reemplaza cada punto de este conjunto por la media de todos los puntos del conjunto de entrada que están más cerca de ese punto. que cualquier otro (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. ^[56] Una de las ventajas del cambio medio sobre k -medias es que el número de grupos no está preespecificado, porque es probable que el cambio medio encuentre sólo unos pocos grupos si sólo existe un pequeño número. Sin embargo, 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. El cambio medio tiene variantes suaves.

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. ^[57]

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. ^[56] 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 de k -medias, 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.
• Mahout contiene k -means basado en MapReduce .
• mlpack contiene una implementación C++ de k -means.
• La octava contiene k -medias.
• OpenCV contiene una implementación de k -means.
• 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 k -means distribuido.
• 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.

• ayasdi
• Matemáticas
• MATLAB
• OrigenPro
• Minero rápido
• SAP HANA
• SAS
• SPSS
• estado

Ver también

• algoritmo BFR
• Teselación centroidal de Voronoi
• Roturas de cabeza/cola
• k q -pisos
• k -significa ++
• Algoritmo de Linde-Buzo-Gray
• Mapa autoorganizado

Referencias

1. 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.
2. 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 .
3. 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.
4. 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 . 
5. 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.
6. 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. ISBN 9781581131437. S2CID  13907420.
7. 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. ISBN 978-0-521-64298-9. SEÑOR  2012999.
8. Dado que la raíz cuadrada es una función monótona, esta también es la asignación de distancia euclidiana mínima.
9. Hartigan, JA; Wong, MA (1979). "Algoritmo AS 136: A k -Algoritmo de agrupación de medios". Revista de la Royal Statistical Society, Serie C. 28 (1): 100–108. JSTOR  2346830.
10. 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) .
11. 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.
12. 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 .
13. 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.
14. 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 .
15. 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 .
16. 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.
17. 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. ISBN 978-3-642-00201-4.
18. 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 .
19. Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (2008). Introducción a la recuperación de información . Prensa de la Universidad de Cambridge. ISBN 978-0521865715. OCLC  190786122.
20. 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. ISBN 978-1595933409. S2CID  3084311.
21. 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í.
22. 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. ISBN 978-3-540-43977-6.
23. 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) .
24. 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. ISBN 978-0-89871-703-7.
25. 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. ISBN 978-3-319-09258-4.
26. 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 .
27. 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 .
28. 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 .
29. 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.
30. 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
31. Hamerly, Greg; Elkan, Charles (2004). "Aprender la k en k-medias" (PDF) . Avances en los sistemas de procesamiento de información neuronal . 16 : 281.
32. 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 -medias". Reconocimiento de patrones . 45 (3): 1061-1075. doi :10.1016/j.patcog.2011.08.012.
33. 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.
34. Sculley, David (2010). "Agrupación de k-significa 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 .
35. Telgarsky, Matus. "Método de Hartigan: k-significa agrupación sin Voronoi" (PDF) .
36. 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.
37. 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.
38. 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 .
39. 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.
40. 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.
41. 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.
42. Mirkes, EM "Subprograma K-means y k-medoids" . Consultado el 2 de enero de 2016 .
43. 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. ISBN 9781450312851.
44. 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.
45. 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.
46. 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.
47. 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. 
48. 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.
49. 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. ISBN 978-0-521-88068-8.
50. Kevin P. Murphy (2012). Aprendizaje automático: una perspectiva probabilística . Cambridge, Massachusetts: MIT Press. ISBN 978-0-262-30524-2. OCLC  810414751.
51. 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.
52. 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.
53. 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.
54. 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 .
55. 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].
56. Pequeño, Max A.; Jones, Nick S. (2011). "Métodos generalizados y solucionadores de señales constantes por partes: Parte I" (PDF) . Actas de la Royal Society A. 467 (2135): 3088–3114. Código Bib : 2011RSPSA.467.3088L. doi :10.1098/rspa.2010.0671. PMC 3191861 . PMID  22003312. 
57. 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) .