K-means

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

K -means es un método de agrupamiento, que tiene como objetivo la [partición [de un conjunto]] n observaciones en k grupos en el que cada observación pertenece al grupo más cercano a la media. Es un método utilizado en mineria de datos.

La agrupación del conjunto de datos puede ilustrarse en una partición del espacio de datos en celdas de Voronoi.

El problema es computacionalmente difícil (NP-hard). Sin embargo, hay eficientes heurísticas que se emplean comúnmente y convergen rápidamente a un óptimo local. Estos suelen ser similares a los algoritmos expectation-maximization de mezclas de distribuciones gausianas por medio de un enfoque de refinamiento iterativo empleado por ambos algoritmos. Además, los dos algoritmos usan los centros que los grupos utilizan para modelar los datos, sin embargo k-means tiende a encontrar grupos de extensión espacial comparable, mientras que el mecanismo expectation-maximization permite que los grupos que tengan formas diferentes.

Descripción[editar]

Dado un conjunto de observaciones (x1, x2, …, xn), donde cada observación es un vector real de d dimensiones, k-means construye una partición de las observaciones en k conjuntos (k = n) S = {S1S2, …, Sk}

a fin de minimizar la suma de los cuadrados  dentro de cada grupo (WCSS):
\underset{\mathbf{S}} {\operatorname{arg\,min}} 
\sum_{i=1}^{k} \sum_{\mathbf x_j \in S_i} \left\| \mathbf x_j - 
\boldsymbol\mu_i \right\|^2

donde µi es la media de puntos en Si.

Historia[editar]

El término "k-means" fue utilizado por primera vez por James MacQueen en 1967,[1] aunque la idea se remonta a Hugo Steinhaus en 1957.[2] El algoritmo estándar fue propuesto por primera vez por Stuart Lloyd en 1957 como una técnica para modulación por impulsos codificados, aunque no se publicó fuera de los laboratorios Bell hasta 1982.[3] En 1965, E. W. Forgy publicó esencialmente el mismo método, por lo que a veces también se le nombra como Lloyd-Forgy.[4] Una versión más eficiente fue propuesta y publicada en Fortran por Hartigan y Wong en 1975/1979.[5] [6]

Algoritmos[editar]

Algoritmo estándar[editar]

El algoritmo más común utiliza una técnica de refinamiento iterativo. Debido a su ubicuidad a menudo se llama el algoritmo k-means', también se le conoce como 'algoritmo de Lloyd, sobre todo en la comunidad informática.

Dado un conjunto inicial de k centroides m1(1),…,mk(1)

(ver más abajo), el algoritmo continúa alternando entre dos pasos:[7] 
Paso de asignación: Asigna cada observación al grupo con la media

más cercana (es decir, la partición de las observaciones de acuerdo con el diagrama de Voronoi generado por los centroides).

S_i^{(t)} = \big \{ x_p : \big \| x_p - m^{(t)}_i \big \| 
\le \big \| x_p - m^{(t)}_j \big \| \ \forall\ 1 \le j \le k 
\big\}
Donde cada x_p va exactamente dentro de un

S^{(t)}_i, incluso aunque pudiera ir en dos de ellos.

Paso de actualización: Calcular los nuevos centroides como el centroide de las observaciones en el grupo.
\mathbf m^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf 
x_j \in S^{(t)}_i} \mathbf x_j

El algoritmo se considera que ha convergido cuando las asignaciones ya no cambian.

Comúnmente utilizados son los métodos de inicialización de Forgy y Partición Aleatoria.[8] El método Forgy elige aleatoriamente k observaciones del conjunto de datos y las utiliza como centroides iniciales. El método de partición aleatoria primero asigna aleatoriamente un clúster para cada observación y después procede a la etapa de actualización, por lo tanto calcular el cluster inicial para ser el centro de gravedad de los puntos de la agrupación asignados al azar. El método Forgy tiende a dispersar los centroides iniciales, mientras que la partición aleatoria ubica los centroides cerca del centro del conjunto de datos. Según Hamerly y compañia,[8] el método de partición aleatoria general, es preferible para los algoritmos tales como los k-harmonic means y fuzzy k-means. Para expectation maximization y el algoritmo estandar el método de Forgy es preferible.

Como se trata de un algoritmo heurístico, no hay ninguna garantía de que convergen al óptimo global, y el resultado puede depender de los grupos iniciales. Como el algoritmo suele ser muy rápido, es común para ejecutar varias veces con diferentes condiciones de partida. Sin embargo, en el peor de los casos, k-means puede ser muy lento para converger: en particular, se ha demostrado que existen conjuntos de determinados puntos, incluso en 2 dimensiones, en la que k-means toma tiempo exponencial, es decir 2O(n), para converger.[9] Estos conjuntos de puntos no parecen surgir en la práctica: esto se ve corroborado por el hecho de que en la mayoría de los casos el tiempo de ejecución de k-means es polinomial.[10]

El "paso de asignación" también se le conoce como paso expectativa, la "etapa de actualización", como paso maximización, por lo que este algoritmo una variante del algoritmo generalizado expectation-maximization.

Complejidad[editar]

Respecto a la complejidad computacional, el agrupamiento k-means para problemas en espacios de d dimensiones es:

  • NP-hard en un espacio euclideano general d incluso para 2 grupos

[11] [12]

  • NP-hard para un numero general de grupos k incluso en el plano

[13]

  • Si k y d son fijados, el problema se puede resolver en un tiempo
O(ndk+1 log n), donde  n es el numero de entidades a particionar[14] 


Por lo tanto, una gran variedad de heuristicas son usadas generalmente.

  • El algoritmo k-means que se discute debajo tiene

orden polinomial para la mayoria de los casos. Se ha demostrado que[10] para un conjunto arbitrario de n puntos en [0,1]^d, si cada punto es perturbado independientemente por una distribución normal con media 0 y varianza \sigma^2, entonces el tiempo de corrida del algoritmo k-means esta acotado por O( 
n^{34}k^{34}d^8 log^4(n)/ \sigma^6 ), que es un tiempo polinomial en n, k, d y 1/\sigma.

  • Se han demostrado mejores cotas para casos simples. Por

ejemplo,[15] demuestra que el tiempo de corrida del algoritmo k-means esta acotado por O(dn^4M^2) para n puntos enteros en la rejilla \{1,\dots, M\}^d.

Variaciones[editar]

donde cada punto tiene un grado difuso de pertenecia a cada grupo.

una asignación probabilística a cada grupo, en vez de asignaciones deterministas.

  • Se han presentado varios métodos para elegir mejor los centroides iniciales. Una propuesta reciente es k-means++.
  • Algoritmos de filtrado utilizan kd-trees para mejorar la eficiencia en cada paso del algoritmo.[16]
  • Algunos métodos también intentan acelerar el algoritmo usando coresets[17]
or the triangle inequality.[18] 
  • Se puede escapar de óptimos locales intercambiando puntos entre los grupos.[6]

del ruido asignando pesos a las componentes de los vectores por grupos[20]

Discusión[editar]

Un ejemplo típico de la convergencia del k-means a un óptimo local. En este ejemplo, el resultado del algoritmo contradice la estructura obvia de los grupos para el conjunto de datos. Los circulos pequeños son los puntos, las cuatro cruces son los centroides. La configuración inicial es la figura de la izquierda. El algoritmo converge en cinco iteraciones mostradas de izquierda a derecha. La ilustración es preparada con el Mirkes Java applet.[21]
ELKI]]. Los centroides de los grupos son mercados usando símbolos semi'transparentes un poco más grandes.
agrupamiento k-means y agrupamiento EM en un conjunto de datos artificial ("mouse"). La tendencia del k-means a producir grupos con tamaños parecidos nos lleva a obtener malos resultados, mientras que EM se beneficia de la distribución gausiana presente en el conjunto de datos.

Las dos características claves del k-means, las que lo hacen eficiente vienen a convertirse en su principal problema:

  • La distancia euclideana se usa como una métrica y la varianza es usada como una medida de la dispersión de los grupos.
  • El número de grupos k es un parámetro de entrada: una elección inapropiada puede acarrear malos resultados. Por eso es muy importante cuando corremos el k-means tener en cuenta la importancia de determinar el numeros de grupos para un conjunto de datos.
  • La convergencia a óptimos locales puede traer malos resultados(ver ejemplo en Fig.).

Una limitación clave del k-means es su modelo de agrupamiento. El concepto se basa en grupos esféricos que son separables de una forma en que el valor de la media converge hacia el centro del grupo. Se espera que los grupos tengan igual tamaño, por lo que la asignación al grupo más cercano es la asignación correcta. Cuando por ejemplo aplicamos k-means con un valor de k=3 al conjunto de datos Iris flower, el resultado no es el esperado incluso habiendo tres especies en el conjunto de datos. Con k=2, los dos grupos visibles(uno conteniendo dos especies) se pueden observar, mientras que con k=3 uno de los dos grupos se divide en dos partes iguales. De hecho, k=2 es más apropiado para este conjunto de datos, aunque este último contenga 3 clases. Como con cualquier otro algoritmo de agrupamiento, el resultado de k-means depende del conjunto de datos para satisfacer las necesidades del algoritmo. Simplemente trabaja bien en algunos conjuntos de datos mientras que falla en otros.

El resultado del k-means se puede ver como las celdas de Voronoi de los centroides de los grupos. Como los datos se separan en cierta forma por la media de los grupos, esto puede llevarnos a óptimos locales como se puede ver en el conjunto "mouse". Los modelos gausianos usados por el algoritmo Expectation-maximization (que puede ser visto como una generalización del k-means) son más flexibles ya que controlan varianzas y covarianzas. El resultado de EM crea grupos con tamaño variable más fácilmente que k-means tanto como grupos correlacionados (no en este ejemplo).

Aplicaciones del algoritmo[editar]

Agrupamiento k-means cuando se usan heurísticas como el algoritmo de Lloyd es fácil de implementar incluso para largos conjuntos de datos. Por lo que ha sido ampliamente usado en muchas áreas como segmentación de mercados, visión por computadoras, geoestadística,[22] , astronomía y minería de datos en agricultura. También se usa como preprocesamiento para otros algoritmos, por ejemplo para buscar una configuración inicial.

Software[editar]

Libre[editar]

Comercial[editar]

Código fuente[editar]

  • ELKI and Weka esta escrito en Java y contiene implementaciones del k-means
  • K-means en PHP,[23] using VB,[24] using Perl,[25] using C++,[26] using Matlab,[27] using Ruby,[28] [29] using Python with scipy,[30] using X10[31]
  • Una implementación en C[32]
  • Una colección de algoritmos de agrupamientos incluido k-means, implementado en Javascript.[33] Online demo.[34]

Puede consultar también[editar]

Referencias[editar]

  1. a b MacQueen, J. B. (1967). «[http://projecteuclid.org/euclid.bsmsp/1200512992 Some Methods for classification and Analysis of Multivariate Observations]». Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1. University of California Press. pp. 281–297. 
  2. Steinhaus, H. (1957). «Sur la division des corps matériels en parties» (en francés). Bull. Acad. Polon. Sci. 4 (12):  pp. 801–804. 
  3. a b Lloyd, S. P. (1957). «Least square quantization in PCM». Bell Telephone Laboratories Paper.  Publicado mucho mas tarde en la revista: Lloyd., S. P. (1982). «Least squares quantization in PCM». IEEE Transactions on Information Theory 28 (2):  pp. 129–137. doi:10.1109/TIT.1982.1056489. http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf. 
  4. E.W. Forgy (1965). «Cluster analysis of multivariate data: efficiency versus interpretability of classifications». Biometrics 21:  pp. 768–769. 
  5. J.A. Hartigan (1975). Clustering algorithms. John Wiley & Sons, Inc. 
  6. a b c Hartigan, J. A.; Wong, M. A. (1979). «Algorithm AS 136: A K-Means Clustering Algorithm». Journal of the Royal Statistical Society, Series C (Applied Statistics) 28 (1):  pp. 100–108. 
  7. MacKay, David (2003). «Chapter 20. An Example Inference Task: Clustering». Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN 0-521-64298-1. MR 2012999. 
  8. a b Hamerly, G. and Elkan, C. (2002). «[http://charlotte.ucsd.edu/users/elkan/cikm02.pdf Alternatives to the k-means algorithm that find better clusterings]». Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 
  9. Vattani., A. (2011). «k-means requires exponentially many iterations even in the plane». Discrete and Computational Geometry 45 (4):  pp. 596–616. doi:10.1007/s00454-011-9340-1. http://cseweb.ucsd.edu/users/avattani/papers/kmeans-journal.pdf. 
  10. a b Arthur, D.; Manthey, B.; Roeglin, H. (2009). «k-means has polynomial smoothed complexity». Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). 
  11. Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). «NP-hardness of Euclidean sum-of-squares clustering». Machine Learning 75:  pp. 245–249. doi:10.1007/s10994-009-5103-0. 
  12. Dasgupta, S. and Freund, Y. (July 2009). «Random Projection Trees for Vector Quantization». Information Theory, IEEE Transactions on 55:  pp. 3229–3242. doi:10.1109/TIT.2009.2021326. 
  13. Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. (2009). «The Planar k-Means Problem is NP-Hard». Lecture Notes in Computer Science 5431:  pp. 274–285. doi:10.1007/978-3-642-00202-1_24. 
  14. Inaba, M.; Katoh, N.; Imai, H. (1994). «Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering». Proceedings of 10th ACM Symposium on Computational Geometry. pp. 332–339. doi:10.1145/177424.178042. 
  15. Arthur; Abhishek Bhowmick (2009). «A theoretical analysis of Lloyd's algorithm for k-means clustering». 
  16. Kanungo, T.; Mount, D. M.; [[Nathan Netanyahu|Netanyahu, N. S.]]; Piatko, C. D.; Silverman, R.; Wu, A. Y. (2002). «[http://www.cs.umd.edu/~mount/Papers/pami02.pdf An efficient k-means clustering algorithm: Analysis and implementation]». IEEE Trans. Pattern Analysis and Machine Intelligence 24:  pp. 881–892. doi:10.1109/TPAMI.2002.1017616. http://www.cs.umd.edu/~mount/Papers/pami02.pdf. 
  17. Frahling, G.; Sohler, C. (2006). «A fast k-means implementation using coresets». Proceedings of the twenty-second annual symposium on Computational geometry (SoCG). 
  18. Elkan, C. (2003). «Using the triangle inequality to accelerate k-means». Proceedings of the Twentieth International Conference on Machine Learning (ICML). 
  19. Dhillon, I. S.; Modha, D. M. (2001). «Concept decompositions for large sparse text data using clustering». Machine Learning 42 (1):  pp. 143–175. 
  20. Amorim, R. C.; Mirkin, B (2012). «Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering». Pattern Recognition 45 (3):  pp. 1061–1075. doi:10.1016/j.patcog.2011.08.012. 
  21. Error en la cita: Etiqueta <ref> inválida; no se ha definido el contenido de las referencias llamadas Mirkes2011
  22. Honarkhah, M and Caers, J, 2010, [http://dx.doi.org/10.1007/s11004-010-9276-7 Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling], Mathematical Geosciences, 42: 487 - 517
  23. http://www25.brinkster.com/denshade/kmeans.php.htm
  24. K-Means Clustering Tutorial: Download
  25. Perl script for Kmeans clustering
  26. Antonio Gulli's coding playground: K-means in C
  27. K-Means Clustering Tutorial: Matlab Code
  28. AI4R :: Artificial Intelligence for Ruby
  29. reddavis/K-Means · GitHub
  30. K-means clustering and vector quantization (scipy.cluster.vq) — SciPy v0.11 Reference Guide (DRAFT)
  31. http://dist.codehaus.org/x10/applications/samples/KMeansDist.x10
  32. http://www.cs.princeton.edu/~wdong/kmeans/
  33. http://code.google.com/p/figue/ FIGUE
  34. http://web.science.mq.edu.au/~jydelort/figue/demo.html