Cluster en ligne k-means

Question

Existe-t-il une version en ligne de l'algorithme k-Means clustering?

En ligne, je veux dire que chaque point de données est traité en série, un à la fois, lorsqu'il pénètre dans le système, économisant ainsi le temps de calcul lorsqu'il est utilisé en temps réel. Je l'ai écrit moi-même avec de bons résultats, mais je préférerais vraiment avoir quelque chose de «standardisé» auquel faire référence, puisqu'il doit être utilisé dans ma thèse de master.

De même, quelqu'un a-t-il des conseils pour d'autres algorithmes de clustering en ligne? (lmgtfy failed;))

Answer 1

Oui il y a. Google n'a pas réussi à le trouver car il est plus communément connu sous le nom de "k-means séquentiels".

Vous pouvez trouver deux implémentations de pseudo-codes de K-means séquentiels dans this section of some Princeton CS class notes par Richard Duda. J'ai reproduit l'une des deux implémentations ci-dessous:

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 

La belle chose à ce sujet est que vous avez seulement besoin de se rappeler la moyenne de chaque groupe et le décompte du nombre de points de données affectés au cluster. Une fois que vous avez mis à jour ces deux variables, vous pouvez jeter le point de données.

Je ne suis pas sûr où vous seriez capable de trouver une citation pour cela. Je voudrais commencer à regarder dans le texte classique de Duda Pattern Classification and Scene Analysis ou la nouvelle édition Pattern Classification. Si ce n'est pas là, vous pouvez essayer le dernier livre de Chris Bishop ou Daphne Koller et le texte récent de Nir Friedman.

Answer 2

Vous pouvez trouver plus sur en ligne k-means dans « Introduction à l'apprentissage machine » par Ethem Alpaydin au chapitre 12. Les modèles locaux