cluster-analysis - example - plot k means python

Online k-means clustering

Question

¿Existe una versión en línea del algoritmo de agrupamiento k-Means ?

Por línea me refiero a que cada punto de datos se procesa en serie, uno a la vez a medida que ingresan al sistema, ahorrando tiempo de computación cuando se usa en tiempo real.

Me he escrito uno con buenos resultados, pero realmente preferiría tener algo "estandarizado" para referirme, ya que se utilizará en mi tesis de maestría.

Además, ¿alguien tiene consejos para otros algoritmos de agrupación en línea? (lmgtfy falló;))

Answer 1

Sí hay. Google no lo encontró porque se conoce más comúnmente como "k-medias secuenciales".

Puede encontrar dos implementaciones de pseudocódigo de K-medias secuenciales en esta sección de algunas notas de Princeton CS de Richard Duda . He reproducido una de las dos implementaciones a continuación:

Make initial guesses for the means m1, m2, ..., mk
Set the counts n1, n2, ..., nk to zero
Until interrupted
Acquire the next example, x
If mi is closest to x
Increment ni
Replace mi by mi + (1/ni)*( x - mi)
end_if
end_until

Lo bonito de esto es que solo necesita recordar la media de cada grupo y el número de puntos de datos asignados al grupo. Una vez que actualice esas dos variables, puede desechar el punto de datos.

No estoy seguro de dónde podría encontrar una cita para ello. Me gustaría comenzar a buscar en la clásica Clasificación de Patrones y Análisis de Escenas del texto de Duda o en la nueva Edición de Clasificación de Patrones . Si no está allí, puedes probar el libro más reciente de Chris Bishop o el texto reciente de Daphne Koller y Nir Friedman.