Cluster k-means online

Question

Esiste una versione online dell'algoritmo k-Means clustering?

Con l'online intendo che ogni punto dati viene elaborato in serie, uno alla volta mentre entrano nel sistema, risparmiando quindi il tempo di elaborazione quando viene utilizzato in tempo reale.

Ho scritto un mio io con buoni risultati, ma preferirei davvero avere qualcosa di "standardizzato" a cui fare riferimento, poiché deve essere usato nella mia tesi di laurea.

Inoltre, qualcuno ha consigli per altri algoritmi di clustering online? (lmgtfy fallito;))

Answer 1

Sì, c'è. Google non è riuscito a trovarlo perché è più comunemente noto come "k-means sequenziale".

È possibile trovare due implementazioni di pseudo-codice di K-medie sequenziali in this section of some Princeton CS class notes da Richard Duda. Ho riprodotto uno dei due implementazioni di seguito:

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 cosa bella di esso è che avete solo bisogno di ricordare la media di ogni cluster e il conteggio del numero di punti di dati assegnati al cluster. Una volta aggiornate queste due variabili, puoi eliminare il punto dati.

Non sono sicuro di dove si possa trovare una citazione per questo. Vorrei iniziare a cercare nel classico testo di Duda Pattern Classification and Scene Analysis o nella nuova edizione Pattern Classification. Se non è lì, potresti provare il nuovo libro di Chris Bishop o il testo recente di Daphne Koller e Nir Friedman.

Answer 2

È possibile trovare maggiori informazioni on-line k-means a "Introduzione alla Machine Learning" di Ethem Alpaydin nel capitolo 12. modelli locali