K-medias
Sin embargo, hay eficientes heurísticas que se emplean comúnmente y convergen rápidamente a un óptimo local.
Además, los dos algoritmos usan los centros que los grupos utilizan para modelar los datos, sin embargo k-medias tiende a encontrar grupos de extensión espacial comparable, mientras que el mecanismo expectation-maximization permite que los grupos tengan formas diferentes.
El término "k-medias" 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.
[5][6] El algoritmo más común utiliza una técnica de refinamiento iterativo.
Debido a su ubicuidad a menudo se llama el algoritmo k-medias, 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] El algoritmo se considera que ha convergido cuando las asignaciones ya no cambian.
[8] El método Forgy elige aleatoriamente k observaciones del conjunto de datos y las utiliza como centroides iniciales.
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ñía,[8] el método de partición aleatoria general, es preferible para los algoritmos tales como los k-medias armonizadas y fuzzy k-medias.
Para expectation maximization y el algoritmo estándar el método de Forgy es preferible.
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-medias 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-medias toma tiempo exponencial, es decir 2O(n), para converger.
Respecto a la complejidad computacional, el agrupamiento k-medias para problemas en espacios de d dimensiones es: Por lo tanto, una gran variedad de heurísticas son usadas generalmente.
Las dos características claves del k-medias, las que lo hacen eficiente vienen a convertirse en su principal problema: Una limitación clave del k-medias 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.
, los dos grupos visibles(uno conteniendo dos especies) se pueden observar, mientras que con
Simplemente trabaja bien en algunos conjuntos de datos mientras que falla en otros.
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-medias) 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-medias tanto como grupos correlacionados (no en este ejemplo).
Por lo que ha sido ampliamente usado en muchas áreas como segmentación de mercados, visión por computadoras, geoestadística,[21] 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.
[22] Se trata de una alternativa del algoritmo K-medias.
grupos se calculan sus respectivos medoides que serán los nuevos centros.
Nótese que los centros, en este caso, siempre forman parte de las observaciones.
Asimismo, este algoritmo, a diferencia de K-medias, funciona para nociones de métrica (o similitud) que no permite calcular medias.
