k means

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 unmé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 mezclasde 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.

Historia
Eltérmino "k-means" fue utilizado por primera vez por James MacQueen en 1967, aunque la idea se remonta a Hugo Steinhaus en 1957.fue propuesto por primera vez por Stuart Lloyd en 1957 como una técnicapara modulación por impulsos codificados, aunque no se publicó fuera de los laboratorios Bell hasta 1982. En 1965, E. W. Forgy publicó esencialmente el mismo método, por lo que a veces también se lenombra como Lloyd-Forgy.4Una versión más eficiente fue propuesta y publicada en Fortran por Hartigan y Wong en 1975/1979.
Variaciones
Fuzzy C-Means Clustering es una versión difusa del K-means,
dondecada punto tiene un grado difuso de pertenecia a cada grupo.

Modelos de mezclas gausianas entrenadas con el algoritmo expectation-maximization presentan
una asignación probabilística a cadagrupo, 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...