k -means clustering es un método de cuantificación vectorial , originalmente a partir del procesamiento de señales , que tiene como objetivo dividir n observaciones en k grupos en los que cada observación pertenece al grupo con la media más cercana(centros de grupo o centroide de grupo), sirviendo como un prototipo el racimo. Esto da como resultado una partición del espacio de datos en celdas de Voronoi . k -significa que el agrupamiento minimiza las varianzas dentro del grupo ( distancias euclidianas al cuadrado ), pero no distancias euclidianas regulares, que sería el problema de Weber más difícil: la media optimiza los errores al cuadrado, mientras que solo la mediana geométrica minimiza las distancias euclidianas. Por ejemplo, se pueden encontrar mejores soluciones euclidianas usando k-medianas y k-medoides .
El problema es computacionalmente difícil ( NP-hard ); sin embargo, los algoritmos heurísticos eficientes convergen rápidamente a un óptimo local . Estos suelen ser similares al algoritmo de maximización de expectativas para mezclas de distribuciones gaussianas a través de un enfoque de refinamiento iterativo empleado por el modelado de mezclas k-medias y gaussianas . Ambos utilizan centros de clústeres 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 formas diferentes.
El algoritmo de k-medias no supervisado tiene una relación flexible con el clasificador de k -vecino más cercano , una técnica popular de aprendizaje automático supervisado para la clasificación que a menudo se confunde con k- medias debido al nombre. La aplicación del clasificador de 1 vecino más cercano a los centros de conglomerados obtenidos por medio de k clasifica los nuevos datos 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 d- dimensional, k -significa que el agrupamiento 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 de puntos en S i . Esto equivale a minimizar las desviaciones cuadradas por pares de puntos en el mismo grupo:
La equivalencia se puede deducir de la identidad. . Debido a 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] que se deriva de la ley de la varianza total .
Historia
El término " k- medias" 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 la modulación de código de pulso , aunque no se publicó como artículo de revista hasta 1982. [4] En 1965, Edward W. Forgy publicó esencialmente el mismo método, por lo que a veces se lo conoce como el algoritmo de Lloyd-Forgy. [5]
Algoritmos
Algoritmo estándar (k-medias ingenuo)
El algoritmo más común utiliza una técnica de refinamiento iterativo. Debido a su ubicuidad, a menudo se le llama "el algoritmo de k- medias"; también se lo conoce como algoritmo de Lloyd , particularmente en la comunidad de ciencias de la computación. A veces también se le conoce como " k- medios ingenuos ", porque existen alternativas mucho más rápidas. [6]
Dado un conjunto inicial de k medias 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: la de la distancia euclidiana mínima al cuadrado . [8] (Matemáticamente, esto significa dividir las observaciones de acuerdo con el diagrama de Voronoi generado por los medios).
- donde cada está asignado a exactamente uno , incluso si pudiera asignarse a dos o más de ellos.
- Paso de actualización : recalcular las medias ( centroides ) para las observaciones asignadas a cada grupo.
El algoritmo ha convergido cuando las asignaciones ya no cambian. No se garantiza que el algoritmo encuentre el óptimo. [9]
El algoritmo se presenta a menudo como la asignación de objetos al grupo más cercano por distancia. El uso de una función de distancia diferente a la distancia euclidiana (al cuadrado) puede evitar que el algoritmo converja. Se han propuesto varias modificaciones de k- medias tales 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 procede al paso de actualización, calculando así la media inicial para que sea 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. De acuerdo con Hamerly et al., [10] el método de partición aleatoria es generalmente preferible para algoritmos tales como las medias k- armónicas y las k- medias difusas. Para la maximización de expectativas y los algoritmos estándar de k medias, es preferible el método de inicialización de Forgy. Sin embargo, un estudio exhaustivo de Celebi et al. [11] encontró que los métodos de inicialización populares como Forgy, Random Partition y Maximin a menudo funcionan mal, mientras que el enfoque de Bradley y Fayyad [12] se desempeña "consistentemente" en "el mejor grupo" y k -means ++ funciona "generalmente bien".
1. k "medias" iniciales (en este caso k = 3) se generan aleatoriamente dentro del dominio de datos (mostrado en color).
2. Se crean k conglomerados 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 conglomerados se convierte en la nueva media.
4. Los pasos 2 y 3 se repiten hasta que se alcanza 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 de inicio. Sin embargo, el desempeño 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 -medias es polinomial. [14]
El paso de "asignación" se denomina "paso de expectativa", mientras que el "paso de actualización" es un paso de maximización, haciendo de este algoritmo 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-hard en el espacio euclidiano general (de dimensiones d ) incluso para dos grupos, [15] [16]
- NP-hard para un número general de clusters k incluso en el plano, [17]
- si k y d (la dimensión) son fijos, el problema puede resolverse 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, dado anteriormente.
El tiempo de ejecución del algoritmo de Lloyd (y la mayoría de las variantes) es , [9] [19] donde:
- n es el número de vectores d- dimensionales (a agrupar)
- 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 solo mejoran ligeramente después de la primera docena de iteraciones. Por lo tanto, el algoritmo de Lloyd se considera a menudo de complejidad "lineal" en la práctica, aunque en el peor de los casos es superpolinomial cuando se realiza hasta la convergencia. [20]
- En el peor de los casos, el algoritmo de Lloyd's necesita iteraciones, de modo que la complejidad del peor de los casos del algoritmo de Lloyd es superpolinomial . [20]
- El algoritmo de k- medias de Lloyd tiene un tiempo de ejecución suavizado por polinomios. Se muestra que [14] para un conjunto arbitrario de n puntos en, si cada punto es perturbado independientemente por una distribución normal con media 0 y varianza, entonces el tiempo de ejecución esperado del algoritmo de k- medias está limitado por, que es un polinomio en n , k , d y.
- Se han probado mejores límites para casos simples. Por ejemplo, se muestra que el tiempo de ejecución del algoritmo de k- medias está limitado porpara n puntos en una celosía entera . [21]
El algoritmo de Lloyd es el enfoque estándar para este problema. Sin embargo, gasta mucho tiempo de procesamiento calculando las distancias entre cada uno de los k centros del grupo y los n puntos de datos. Dado que los puntos generalmente permanecen 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
- k -medians clustering usa la mediana en cada dimensión en lugar de la media, y de esta manera minimizanorma ( geometría del taxi ).
- k -medoides (también: Partitioning Around Medoids, PAM) usa el medoide en lugar de la media, y de esta manera minimiza la suma de distancias parafunciones de distancia arbitrarias .
- El agrupamiento de medias C difusas es una versión suave de las medias k , 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 da un límite superior demostrable en el objetivo 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 del triángulo . [22] [23] [24] [27] [25]
- Escapa de los óptimos locales intercambiando puntos entre grupos. [9]
- El algoritmo de agrupamiento esférico k- medias es adecuado para datos textuales. [28]
- Variantes jerárquicas como Bisecar k- medias, [29] X-significa agrupamiento [30] y G-significa agrupamiento [31] dividen grupos repetidamente para construir una jerarquía , y también pueden intentar determinar automáticamente el número óptimo de grupos en un conjunto de datos .
- Las medidas de evaluación de conglomerados internos , como la silueta del conglomerado, pueden ser útiles para determinar el número de conglomerados .
- Minkowski ponderado k significa que calcula automáticamente los pesos de características específicas del clúster, 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 dado, lo que aumenta 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]
Método Hartigan-Wong
El método de Hartigan y Wong [9] proporciona una variación del algoritmo de k medias que progresa hacia un mínimo local del problema mínimo de suma de cuadrados con diferentes actualizaciones de la solución. El método es una búsqueda local que intenta de forma iterativa reubicar una muestra en un grupo diferente siempre que este proceso mejore la función objetivo. Cuando ninguna muestra se puede reubicar en un grupo diferente con una mejora del objetivo, el método se detiene (en un mínimo local). De manera similar a los medios k clásicos, el enfoque sigue siendo heurístico, ya que no garantiza necesariamente que la solución final sea globalmente óptima.
Dejar ser el costo individual de definido por , con el centro del grupo.
Paso de asignación: 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 lo cual la siguiente función alcanza un máximo
Para el que alcanzan este máximo, se mueve desde el clúster al racimo .
Terminación : el algoritmo termina una vez 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 de mejora, mientras que en una estrategia de mejora óptima , todas las reubicaciones posibles se prueban iterativamente y solo se aplica la mejor en cada iteración. El primer enfoque favorece la velocidad, ya sea que el segundo enfoque generalmente favorezca la calidad de la solución a expensas del tiempo de cálculo adicional. La funciónutilizado para calcular el resultado de una reubicación también se puede evaluar de manera eficiente utilizando la igualdad [35]
Optimización global y metaheurística
Se sabe que el algoritmo clásico de k-medias y sus variaciones solo convergen a los mínimos locales del problema de agrupamiento mínimo de suma de cuadrados definido como
Muchos estudios han intentado mejorar el comportamiento de convergencia del algoritmo y maximizar las posibilidades de alcanzar el óptimo global (o al menos, mínimos locales de mejor calidad). Las técnicas de inicialización y reinicio discutidas en las secciones anteriores son una alternativa para encontrar mejores soluciones. Más recientemente, los algoritmos de programación matemática basados en la generación de columnas y ramificaciones han producido soluciones "probadamente óptimas" para conjuntos de datos con hasta 2.300 entidades. [36] Como era de esperar, 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ña y mediana escala siguen siendo valiosas como herramienta de referencia para evaluar la calidad de otras heurísticas. Para encontrar mínimos locales de alta calidad dentro de un tiempo computacional controlado pero sin garantías de 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, [37] intercambios aleatorios [38] (es decir, iterados búsqueda local ), búsqueda de vecindad variable [39] y algoritmos genéticos . [40] [41] De hecho, se sabe que encontrar mejores mínimos locales del problema de agrupamiento mínimo de suma de cuadrados puede marcar la diferencia entre el fracaso y el éxito para recuperar estructuras de grupos en espacios de características de alta dimensión. [41]
Discusión
Tres características clave de los medios k que lo hacen eficiente a menudo se consideran sus mayores inconvenientes:
- La distancia euclidiana se usa como métrica y la varianza se usa como una medida de la dispersión de los conglomerados.
- El número de conglomerados k es un parámetro de entrada: una elección inadecuada de k puede producir malos resultados. Por eso, al realizar k- medias, es importante ejecutar comprobaciones de diagnóstico para determinar el número de clústeres en el conjunto de datos .
- La convergencia a un mínimo local puede producir resultados contradictorios ("incorrectos") (ver ejemplo en la Fig.).
Una limitación clave de k- medias es su modelo de clúster. El concepto se basa en conglomerados esféricos que son separables para que la media converja hacia el centro del conglomerado. Se espera que los conglomerados tengan un tamaño similar, de modo que la asignación al centro del conglomerado más cercano sea la asignación correcta. Cuando, por ejemplo, se aplican k- medias con un valor deen el conocido conjunto de datos de flores de Iris , el resultado a menudo no logra separar las tres especies de Iris contenidas en el conjunto de datos. Con, se descubrirán los dos grupos visibles (uno que contiene dos especies), mientras que con uno de los dos grupos se dividirá en dos partes pares. De echo,es más apropiado para este conjunto de datos, a pesar de que el conjunto de datos contiene 3 clases . Al igual que con cualquier otro algoritmo de agrupamiento, el resultado de k medias supone que los datos satisfacen ciertos criterios. Funciona bien en algunos conjuntos de datos y falla en otros.
El resultado de k -medias puede verse como las células de Voronoi de las medias del grupo. Dado que los datos se dividen a la mitad entre las medias de los clústeres, esto puede conducir a divisiones subóptimas, como se puede ver en el ejemplo del "ratón". Los modelos gaussianos utilizados por el algoritmo de maximización de expectativas (posiblemente una generalización de k- medias) son más flexibles al tener tanto varianzas como 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). En contraparte, 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 clústeres o matrices de covarianza mal condicionadas. K- medias está estrechamente relacionado con el modelado bayesiano no paramétrico . [43]
Aplicaciones
k -means clustering es bastante fácil de aplicar incluso a grandes conjuntos de datos, particularmente cuando se utilizan heurísticas como el algoritmo de Lloyd . Se ha utilizado con éxito en la segmentación del mercado , la visión por computadora y la astronomía, entre muchos otros dominios. A menudo se utiliza como un paso de preprocesamiento para otros algoritmos, por ejemplo, para encontrar una configuración inicial.
Cuantización vectorial
k -medios se origina en el procesamiento de señales y todavía encuentra uso en este dominio. Por ejemplo, en los 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 de k- medias se puede utilizar fácilmente para esta tarea y produce resultados competitivos. Un caso de uso de este enfoque es la segmentación de imágenes . Otros usos de la cuantificación vectorial incluyen el muestreo no aleatorio , ya que los k -medios se pueden usar fácilmente para elegir k objetos diferentes pero prototípicos de un gran conjunto de datos para un análisis posterior.
Análisis de conglomerados
En el análisis de conglomerados, el algoritmo de k- medias se puede utilizar para dividir el conjunto de datos de entrada en k particiones (conglomerados).
Sin embargo, el algoritmo puro de k medias 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 discutió anteriormente) cuando no está dado 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
k significa que el agrupamiento se ha utilizado como un paso de aprendizaje de características (o aprendizaje de diccionario ), ya sea en el aprendizaje ( semi ) supervisado o en el aprendizaje 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 ser etiquetados). Luego, para proyectar cualquier dato de entrada en el nuevo espacio de características, una función de "codificación", como el producto de matriz umbral del dato con las ubicaciones de centroide, 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, transformando 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- medias se ha combinado con éxito con clasificadores lineales simples para el aprendizaje semi-supervisado en PNL (específicamente para el reconocimiento de entidades con nombre ) [48] y en visión por computadora . En una tarea de reconocimiento de objetos, se encontró que exhibía un rendimiento comparable con enfoques de aprendizaje de características más sofisticados, como 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 solo 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 asociado de maximización de expectativas , es un caso especial de un modelo de mezcla gaussiana, específicamente, el caso límite cuando se fijan todas las covarianzas para que sean diagonales, iguales y tengan una varianza pequeña infinitesimal. [49] : 850 En lugar de pequeñas variaciones, una asignación de conglomerado rígido también se puede utilizar para mostrar otra equivalencia de k -medias agrupadas en un caso especial de modelado de mezcla gaussiana "duro". [50] ( 11.4.2.5 ) Esto no significa que sea eficiente utilizar el modelado de mezclas gaussianas para calcular k medias, sino solo que existe una relación teórica y que el modelado de mezclas gaussianas se puede interpretar 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 de k- medias es el algoritmo K-SVD, que estima puntos de datos como una combinación lineal dispersa de "vectores de libro de códigos". k -medias corresponde al caso especial de usar un solo 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 la agrupación, viene dada por el análisis de componentes principales (PCA). [52] [53] La intuición es que los medios k describen 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 de 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 bidimensional. Este plano también está definido por las dos primeras dimensiones del PCA. Los conglomerados bien separados se modelan eficazmente mediante conglomerados en forma de bola y, por tanto, se descubren mediante k -medios. Los grupos sin 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 las medias k tengan buenos resultados con estos datos. [54] Es sencillo producir contraejemplos de la afirmación de que el subespacio del centroide del clúster está atravesado por las direcciones principales. [55]
Agrupación de turnos medios
Los algoritmos básicos de agrupación de cambios medios 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 los puntos del conjunto que se encuentran dentro de una distancia determinada de ese punto. Por el contrario, k -medias 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 en este conjunto por la media de todos los puntos en el 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 desplazamiento medio que es similar entonces a k- medias, llamado desplazamiento medio de verosimilitud , reemplaza el conjunto de puntos en sustitución por la media de todos los puntos del conjunto de entrada que se encuentran dentro de una distancia determinada del conjunto cambiante. [56] Una de las ventajas del desplazamiento medio sobre las k- medias es que el número de conglomerados no está preespecificado, porque es probable que el desplazamiento medio encuentre sólo unos pocos conglomerados si sólo existe un pequeño número. Sin embargo, el desplazamiento medio puede ser mucho más lento que k -medios 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 preprocesan con la transformación de blanqueamiento , k -medios produce la solución para la tarea de análisis de componentes independientes lineales (ICA). Esto ayuda a explicar la aplicación exitosa de k -medios al aprendizaje de características . [57]
Filtrado bilateral
k significa implícitamente que asume que el orden del conjunto de datos de entrada no importa. El filtro bilateral es similar a k -medias y cambio de media en el sentido de 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 del núcleo) para incluir solo los 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 clúster que minimizan el error al cuadrado también incluye el algoritmo k -medoides , un enfoque que obliga al punto central de cada clúster 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 termina en 10 segundos, la más lenta tarda 25,988 segundos (~ 7 horas). [1] Las diferencias pueden atribuirse a la calidad de la implementación, las 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 los modos 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 de Java para k -medios.
- CrimeStat implementa dos algoritmos de k- medias espaciales , uno de los cuales permite al usuario definir las ubicaciones de inicio.
- ELKI contiene k -means (con iteración de Lloyd y MacQueen, junto con diferentes inicializaciones como k -means ++ inicialización) y varios algoritmos de agrupamiento más avanzados.
- Smile contiene k -medios 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 de agrupación en clústeres de JuliaStats.
- KNIME contiene nodos para k -medias y k -medoides.
- Mahout contiene un k -medio basado en MapReduce .
- mlpack contiene una implementación en C ++ de k -means.
- Octave contiene k -medias.
- OpenCV contiene una implementación de k- medias.
- Orange incluye un componente para la agrupación de k- medias con selección automática de k y puntuación de silueta de grupo.
- PSPP contiene k -means, el comando QUICK CLUSTER realiza k -means agrupamiento en el conjunto de datos.
- R contiene tres variaciones de k- medias.
- SciPy y scikit-learn contienen múltiples implementaciones de k- medias.
- Spark MLlib implementa un algoritmo distribuido de k- medias.
- Torch contiene un paquete unsup que proporciona k -means agrupación.
- Weka contiene k -medios y x -medios.
Propiedad
Las siguientes implementaciones están disponibles bajo términos de licencia de propiedad y pueden no tener código fuente disponible públicamente.
- Ayasdi
- Mathematica
- MATLAB
- OriginPro
- RapidMiner
- SAP HANA
- SAS
- SPSS
- Stata
Ver también
- Algoritmo BFR
- Teselado centroidal de Voronoi
- Roturas de cabeza / cola
- k q-flats
- K-medias ++
- Algoritmo Linde – Buzo – Gray
- Mapa autoorganizado
Referencias
- ↑ a b Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). "El arte (negro) de la evaluación en tiempo de ejecución: ¿estamos comparando algoritmos o implementaciones?". Sistemas de conocimiento e 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 5º Simposio de Berkeley sobre Probabilidad y Estadística Matemática. 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. Sci. (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 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 . Consultado el 15 de abril de 2009 .
- ^ Forgy, Edward W. (1965). "Análisis de conglomerados de datos multivariados: eficiencia versus interpretabilidad de clasificaciones". Biometría . 21 (3): 768–769. JSTOR 2528559 .
- ^ Pelleg, Dan; Moore, Andrew (1999). "Acelerar los algoritmos de k -medios exactos con razonamiento geométrico" . Actas de la Quinta Conferencia Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento y Minería de Datos - KDD '99 . San Diego, California, Estados Unidos: ACM Press: 277–281. doi : 10.1145 / 312129.312248 . ISBN 9781581131437. S2CID 13907420 .
- ^ MacKay, David (2003). "Capítulo 20. Un ejemplo de tarea de inferencia: agrupamiento" (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 .
- ^ Dado que la raíz cuadrada es una función monótona, esta también es la asignación de distancia euclidiana mínima.
- ^ a b c d e Hartigan, JA; Wong, MA (1979). "Algoritmo AS 136: A k- significa algoritmo de agrupación". Revista de la Sociedad Real de Estadística, Serie C . 28 (1): 100–108. JSTOR 2346830 .
- ^ a b Hamerly, Greg; Elkan, Charles (2002). "Alternativas al algoritmo k- medias que encuentran mejores agrupaciones" (PDF) . Actas de la undécima conferencia internacional sobre gestión de la información y el conocimiento (CIKM) .
- ^ Celebi, ME; Kingravi, HA; Vela, PA (2013). "Un estudio comparativo de métodos de inicialización eficientes para el algoritmo de agrupación de k -medios". 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). " Refinando los puntos iniciales para k -Means Clustering". 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 .
- ^ a b Arthur, David; Manthey, B .; Roeglin, H. (2009). "k-means tiene una complejidad suavizada polinomial". 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 del agrupamiento euclidiano de suma de cuadrados" . 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 la cuantificación de vectores". Transacciones IEEE sobre teoría de la información . 55 (7): 3229–3242. arXiv : 0805.1390 . doi : 10.1109 / TIT.2009.2021326 . S2CID 666114 .
- ^ Mahajan, Meena; Nimbhorkar, Prajakta; Varadarajan, Kasturi (2009). El problema de k- medias planas es NP-difícil . Apuntes de conferencias en informática. 5431 . págs. 274-285. CiteSeerX 10.1.1.331.1306 . doi : 10.1007 / 978-3-642-00202-1_24 . ISBN 978-3-642-00201-4.
- ^ Inaba, M .; Katoh, N .; Imai, H. (1994). Aplicaciones de diagramas de Voronoi ponderados y aleatorización al agrupamiento k basado en la varianza . Actas del X Simposio ACM sobre Geometría Computacional . págs. 332–339. doi : 10.1145 / 177424.178042 .
- ^ Manning, Christopher D .; Raghavan, Prabhakar; Schütze, Hinrich (2008). Introducción a la recuperación de información . Nueva York: Cambridge University Press. ISBN 978-0521865715. OCLC 190786122 .
- ^ a b Arthur, David; Vassilvitskii, Sergei (1 de enero de 2006). ¿Qué tan lento es el método k- medias? . Actas del Vigésimo Segundo Simposio Anual de Geometría Computacional . SCG '06. Nueva York, NY, EE.UU .: ACM. págs. 144-153. doi : 10.1145 / 1137856.1137880 . ISBN 978-1595933409. S2CID 3084311 .
- ^ Bhowmick, Abhishek (2009). "Un análisis teórico del algoritmo de Lloyd para k -means clustering" (PDF) . Archivado desde el original (PDF) el 8 de diciembre de 2015. Cite journal requiere
|journal=
( ayuda )Consulte también aquí . - ^ a b Phillips, Steven J. (4 de enero de 2002). "Aceleración de K-medias y algoritmos de agrupación relacionados". En Mount, David M .; Stein, Clifford (eds.). Aceleración de k- medias y algoritmos de agrupamiento relacionados . Apuntes de conferencias en informática. 2409 . Springer Berlín Heidelberg. págs. 166-177. doi : 10.1007 / 3-540-45643-0_13 . ISBN 978-3-540-43977-6.
- ^ a b Elkan, Charles (2003). "Uso de la desigualdad del triángulo para acelerar k- medias" (PDF) . Actas de la XX Conferencia Internacional sobre Aprendizaje Automático (ICML) .
- ^ a b Hamerly, Greg. "Hacer k significa aún más rápido". CiteSeerX 10.1.1.187.3017 .
- ^ a b Hamerly, Greg; Drake, Jonathan (2015). Acelerar el algoritmo de Lloyd para k significa agrupamiento . Algoritmos de agrupamiento particional . págs. 41–78. doi : 10.1007 / 978-3-319-09259-1_2 . ISBN 978-3-319-09258-4.
- ^ Kanungo, Tapas; Mount, David M .; Netanyahu, Nathan S .; Piatko, Christine D .; Silverman, Ruth; Wu, Angela Y. (2002). "Un algoritmo de clustering de k- medias eficiente : Análisis e implementación" (PDF) . Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 24 (7): 881–892. doi : 10.1109 / TPAMI.2002.1017616 . Consultado el 24 de abril de 2009 .
- ^ Drake, Jonathan (2012). " K acelerado- medias con límites de distancia adaptables" (PDF) . El quinto taller de NIPS sobre optimización para el aprendizaje automático, OPT2012 .
- ^ Dhillon, IS; Modha, DM (2001). "Descomposiciones de conceptos para grandes datos de texto 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 las técnicas de agrupación de documentos ". En". Taller de KDD sobre minería de textos . 400 (1): 525–526.
- ↑ Pelleg, D .; Y Moore, AW (2000, junio). " X-medias: extensión de k- medias con estimación eficiente del número de clústeres ". En ICML , vol. 1
- ^ Hamerly, Greg; Elkan, Charles (2004). "Aprendiendo la k en k-medias" (PDF) . Avances en sistemas de procesamiento de información neuronal . 16 : 281.
- ^ Amorim, RC; Mirkin, B. (2012). "Métrica de Minkowski, ponderación de características e inicialización de clústeres anómalos en k -Means Clustering". Reconocimiento de patrones . 45 (3): 1061–1075. doi : 10.1016 / j.patcog.2011.08.012 .
- ^ Amorim, RC; Hennig, C. (2015). "Recuperación del número de clústeres en conjuntos de datos con características de ruido utilizando factores de cambio de escala 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). "Web-scale k -means clustering" . Actas de la 19ª conferencia internacional sobre World Wide Web . ACM. págs. 1177-1178 . Consultado el 21 de diciembre de 2016 .
- ^ Telgarsky, Matus. "Método de Hartigan: k- significa agrupamiento sin Voronoi" (PDF) .
- ^ Aloise, Daniel; Hansen, Pierre; Liberti, Leo (2012). "Un algoritmo de generación de columna mejorado para la agrupación mínima de suma de cuadrados". Programación matemática . 131 (1–2): 195–220. doi : 10.1007 / s10107-010-0349-7 . S2CID 17550257 .
- ^ Bagirov, AM; Taheri, S .; Ugon, J. (2016). "Enfoque de programación DC no suave para los problemas de agrupamiento de suma de cuadrados mínimos". Reconocimiento de patrones . 53 : 12-24. doi : 10.1016 / j.patcog.2015.11.011 .
- ^ Fränti, Pasi (2018). "Eficiencia de la agrupación en clústeres 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. doi : 10.1016 / S0031-3203 (99) 00216-2 .
- ^ Krishna, K .; Murty, MN (1999). "Algoritmo genético de k-medias" . Transacciones IEEE sobre sistemas, hombre y cibernética, Parte B: Cibernética . 29 (3): 433–439. doi : 10.1109 / 3477.764879 . PMID 18252317 .
- ^ a b Gribel, Daniel; Vidal, Thibaut (2019). "HG-significa: una metaheurística híbrida escalable para la agrupación mínima 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-medias y k -medoides" . Consultado el 2 de enero de 2016 .
- ^ Kulis, Brian; Jordan, Michael I. (26 de junio de 2012). Revisando k -medias: nuevos algoritmos a través de no paramétricos bayesianos (PDF) . ICML . págs. 1131-1138. ISBN 9781450312851.
- ^ a b c Coates, Adam; Ng, Andrew Y. (2012). "Aprendizaje de representaciones de características 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 keypoints (PDF) . Taller ECCV sobre Aprendizaje Estadístico en Visión por Computador.
- ^ a b Coates, Adam; Lee, Honglak; Ng, Andrew Y. (2011). Un análisis de redes de una sola capa en el aprendizaje de funciones no supervisado (PDF) . Congreso Internacional de Inteligencia Artificial y Estadística (AISTATS). Archivado desde el original (PDF) el 10 de mayo de 2013.
- ^ Schwenker, Friedhelm; Kestler, Hans A .; Palm, 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 e IJCNLP. págs. 1030–1038.
- ^ a b Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 16.1. Modelos de mezcla gaussiana 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.
- ^ Kevin P. Murphy (2012). Aprendizaje automático: una perspectiva probabilística . Cambridge, Mass .: MIT Press. ISBN 978-0-262-30524-2. OCLC 810414751 .
- ^ Aharon, Michal; Elad, Michael; Bruckstein, Alfred (2006). "K-SVD: un algoritmo para diseñar diccionarios sobrecompletos para representación escasa" (PDF) . Transacciones IEEE sobre procesamiento de señales . 54 (11): 4311. Bibcode : 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 k -means Clustering" (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 a través del análisis de componentes principales" (PDF) . Actas de la Conferencia Internacional sobre Aprendizaje Automático (ICML 2004) : 225–232.
- ^ Drineas, Petros; Frieze, Alan M .; Kannan, Ravi; Vempala, Santosh; Vinay, Vishwanathan (2004). "Agrupación de grandes gráficos 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 .; Anciano, Sam; Musco, Cameron; Musco, Christopher; Persu, Madalina (2014). "Reducción de dimensionalidad para k -means agrupamiento y aproximación de rango bajo (Apéndice B)". arXiv : 1410.6801 [ cs.DS ].
- ^ a b Little, Max A .; Jones, Nick S. (2011). "Métodos generalizados y solucionadores de señales constantes por partes: parte I" (PDF) . Proceedings of the Royal Society A . 467 (2135): 3088–3114. Código Bib : 2011RSPSA.467.3088L . doi : 10.1098 / rspa.2010.0671 . PMC 3191861 . PMID 22003312 .
- ^ Vinnikov, Alon; Shalev-Shwartz, Shai (2014). "K-means recupera los filtros ICA cuando los componentes independientes son escasos" (PDF) . Actas de la Conferencia Internacional sobre Aprendizaje Automático (ICML 2014) .