Online k-means clustering

Question

¿Hay una versión en línea del algoritmo k-Means clustering?

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

He escrito uno yo mismo con buenos resultados, pero realmente preferiría tener algo "estandarizado" para referirse, ya que se va a utilizar en mi tesis de maestría.

Además, ¿alguien tiene consejos para otros algoritmos de clustering en línea? (lmgtfy failed;))

Answer 1

Sí, lo hay. Google no pudo encontrarlo porque es más comúnmente conocido como "k-means secuencial".

Puede encontrar dos implementaciones de pseudocódigo de K-means secuenciales en this section of some Princeton CS class notes por Richard Duda. He reproducido una de las dos implementaciones siguientes:

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 sólo es necesario recordar la media de cada grupo y el recuento del número de puntos de datos asignados a la agrupación. Una vez que actualice esas dos variables, puede descartar el punto de datos.

No estoy seguro de dónde podría encontrar una cita. Comenzaría a buscar en el texto clásico de Duda Pattern Classification and Scene Analysis o en la edición más reciente Pattern Classification. Si no está allí, puedes probar el libro más nuevo de Chris Bishop o el reciente texto de Daphne Koller y Nir Friedman.

Answer 2

Puede encontrar más información sobre k-medias en línea "Introducción a Machine Learning" por Ethem Alpaydin en el capítulo 12. Los modelos locales