K-means++

En minería de datos, k-means++^[1][2] es un algoritmo que se utiliza para la selección de los valores iniciales (o "semillas") en el algoritmo k-means clustering. Fue propuesto en 2007 por David Arthur y Sergei Vassilvitskii, como un algoritmo de aproximación para el problema NP-duro k-means—una forma de evitar los agrupamientos pobres a veces encontrados por el algoritmo k-means estándar. Es similar al primero de tres métodos para encontrar semillas propuestos, en 2006,^[3] por Rafail Ostrovsky, Yuval Rabani, Leonard Schulman and Chaitanya Swamy. (La distribución de la primera semilla es diferente).

Base

El problema k-means consiste en encontrar grupos de puntos tal que se minimice la varianza intra-grupo, es decir, minimizar la suma de las distancias al cuadrado de cada punto al centro más cercano a él. Aunque la búsqueda de una solución exacta al problema de k-means para una entrada arbitraria es NP-duro,^[4] el enfoque estándar de encontrar una solución aproximada (a menudo llamado el algoritmo de Lloyd o el algoritmo k-means) es utilizado ampliamente y con frecuencia encuentra soluciones razonables rápidamente.

Sin embargo, el algoritmo k-means tiene por lo menos dos grandes deficiencias teóricas:

• Primero, ha sido mostrado que, en el caso peor, el tiempo de corrida del algoritmo es súper-polinomial en el tamaño de la entrada.^[5]
• Segundo, la aproximación encontrada puede ser arbitrariamente mala con respecto a la función objetivo comparado al agrupamiento óptimo.

El algoritmo k-means++ aborda la segunda de estas deficiencias mediante la especificación de un procedimiento para inicializar los centros de los conjuntos antes de proceder con las k-means iteraciones de optimización estándar . Con la inicialización de k-means++ , el algoritmo está garantizado para encontrar una solución que es O (log k) competitiva a la solución óptima de k-means.

Algoritmo de inicialización

La intuición detrás de este enfoque es que la expansión de los k iniciales centros de conjuntos es una buena idea: el primer centro de conjunto se obtiene con una variable aleatoria uniforme desde los puntos que están agrupados, después de esto cada centro de grupo siguiente se elige desde el resto de los puntos con probabilidad proporcional a su distancia al cuadrado desde del centro de conjunto existente más cercano del punto.

El algoritmo exacto es como sigue:

1. Escoger un centro de entre los puntos de datos utilizando una variable aleatoria uniforme.
2. Para cada punto x, calcular D(x), que es la distancia entre x y el centro más cercano que ya ha sido seleccionado.
3. Escoger un nuevo punto al azar (con variable aleatoria uniforme) como nuevo centro, utilizando una distribución de probabilidad ponderada donde un punto x es escogido con la probabilidad proporcional a D(x)².
4. Repetir paso 2 y 3 hasta que se hayan seleccionado k centros.
5. Ahora que los centros iniciales han sido elegidos, continuar utilizando k-means clustering estándar.

Este método produce una mejora considerable en el error final de k-means. Aunque la selección inicial en el algoritmo toma tiempo extra, k-means converge muy rápidamente después de la selección de puntos iniciales y por lo tanto este algoritmo reduce el tiempo de cálculo. Los autores probaron su método con conjuntos de datos reales y sintéticos y obtuvieron mejoras de 2-veces en la velocidad, y para ciertos conjuntos de datos, cerca de 1000 veces mejoras en error. En estas simulaciones el nuevo método casi siempre se ejecuta al menos tan bien como vainilla k-means, tanto en la velocidad y como en el error.

Además, los autores calculan una relación de aproximación para su algoritmo. El algoritmo k-means++ garantiza una relación de aproximación O (log k) a la espera (más de la aleatoriedad del algoritmo), donde k es el número de grupos utilizados. Esto está en contraste con vainilla k-means, el cual puede generar grupos arbitrariamente peor que la solución óptima.^[6]

Ejemplo caso peor

Para ilustrar el potencial del algoritmo de k-means para agrupar arbitrariamente mal (con respecto a la función objetivo de minimizar la suma de las distancias al cuadrado de los puntos al centroide de sus grupos), considere el ejemplo de cuatro puntos en R² que forman un rectángulo cuya anchura es mayor que su altura.

Si k = 2 y los dos centros iniciales de conjuntos se encuentran en los puntos medios de los segmentos de línea superior e inferior del rectángulo formado por los cuatro puntos, el algoritmo k-means converge inmediatamente, sin mover estos centros de los conjuntos. En consecuencia, los dos puntos de fondo se agrupan juntos y los dos puntos que forman la parte superior del rectángulo se agrupan juntos, un agrupamiento subóptimo debido a que la anchura del rectángulo es mayor que su altura.

Ahora, considera extender el rectángulo horizontalmente a un ancho arbitrario. El algoritmo k-means estándar continuará a agrupar los puntos suboptimalmente, y por incrementar la distancia horizontal entre los dos puntos en cada grupo, podemos hacer que el algoritmo agrupe arbitrariamente mal con respecto a la función objetivo del k-means

Aplicaciones

El enfoque de k-means++ se ha aplicado desde su propuesta inicial. En una revisión por Shindler^[7] que incluye muchos tipos de algoritmos de agrupamiento, el método se dice que supera con éxito algunos de los problemas asociados con otras formas de definir centros iniciales de conjuntos para k-means clustering. Lee et al.^[8] Informe de una aplicación de k-means++ para crear grupos geográficos de fotografías sobre la base de la información de latitud y longitud unido a las fotos. Una aplicación para la diversificación económica es reportado por Howard y Johansen^[9] Otro tipo de apoyo para el método y en curso de discusión también está disponible en línea^[10] dado que la inicialización de k-means++ necesita k pasadas por encima de los datos no se escala muy bien a conjuntos grandes de datos Bahman Bahmani et al. ha propuesto una variante escalable de k-means++ llamada k-means || que ofrece las mismas garantías teóricas y sin embargo es altamente escalable.^[11]

Software

• Scikit-learn tiene un K-means que usa k-means++ por defecto.
• ELKI minería de datos contiene múltiples variaciones de k-means, incluyendo k-means++ para inicialización.
• GNU R incluye k-means, y el paquete "flexclust" puede hacer k-means++.
• OpenCV, implementación
• Weka contiene k-means (con k-means++ opcional) y x-means clustering.
• La implementación de [http://www.stanford.edu/~darthur/kmpp.zip (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). David Arthur's] ^{[dead link]}
• La implementación de Apache Commons Math Java Archivado el 4 de marzo de 2016 en Wayback Machine.
• [https://web.archive.org/web/20141203225249/http://docs.graphlab.org/clustering.html (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). CMU's GraphLab] eficiente, la agrupación de código abierto en multinúcleo

Referencias

1. Arthur, D. and Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding" Archivado el 21 de agosto de 2017 en Wayback Machine. (PDF).
2. http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Slides for presentation of method by Arthur, D. and Vassilvitskii, S.
3. Ostrovsky, R., Rabani, Y., Schulman, L. J. and Swamy, C. (2006).
4. Drineas, P. and Frieze, A. and Kannan, R. and Vempala, S. and Vinay, V. (2004).
5. Arthur, D. and Vassilvitskii, S. (2006), "How slow is the k-means method?"
6. T. Kanungo, D. Mount, N. Netanyahux, C. Piatko, R. Silverman, A. Wu "A Local Search Approximation Algorithm for k-Means Clustering" Archivado el 9 de febrero de 2006 en Wayback Machine. 2004 Computational Geometry: Theory and Applications.
7. https://web.archive.org/web/20110927100642/http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf Approximation Algorithms for the Metric k-Median Problem
8. http://sir-lab.usc.edu/publications/2008-ICWSM2LEES.pdf Archivado el 3 de marzo de 2016 en Wayback Machine. Discovering Relationships among Tags and Geotags, 2007
9. http://www.cse.ohio-state.edu/~johansek/clustering.pdf (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). Clustering Techniques for Financial Diversification, March 2009
10. http://lingpipe-blog.com/2009/03/23/arthur-vassilvitskii-2007-kmeans-the-advantages-of-careful-seeding/ Lingpipe Blog
11. B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii "Scalable K-means++" 2012 Proceedings of the VLDB Endowment.

• Datos: Q13414807