Clustering dinamica efficiente

Question

Ho una serie di punti dati dal intervallo unitario (cioè set di dati 1-dimensionale con valori numerici). Ricevo alcuni datapoints aggiuntivi on-line, e per di più il valore di alcune datapoints potrebbe cambiare in modo dinamico. Sto cercando un algoritmo di clustering ideale in grado di gestire questi problemi in modo efficiente.

sequenziale k-means clustering di affronta l'aggiunta di nuovi casi e immagino con lievi modifiche può funzionare con valori di istanza dinamica (cioè prima di prendere l'istanza modificata dal rispettivo cluster, aggiornando la media del cluster e infine dando l'esempio modificato come input all'algoritmo così come l'aggiunta di un'istanza invisibile).

mia preoccupazione con utilizzando l'algoritmo k-means è il requisito di fornire il numero di cluster come input. So che hanno battuto gli altri algoritmi di clustering (gas, MST, metodi gerarchici, ecc) in tempo e complessità spaziale. Onestamente non sono sicuro, ma forse posso farla franca con l'utilizzo di uno degli algoritmi di cui sopra. Anche che i miei insiemi di dati sono relativamente grandi, l'esistenza di una sola dimensione mi domando.

In particolare un tipico caso di test di mine conterrebbe circa 10K-200K datapoints 1-dimensionali. Desidero completare il raggruppamento preferibilmente meno di un secondo. I cambiamenti dinamici nei punti valore sono assunti essere liscia, cioè relativamente piccolo. Potendo così utilizzare soluzioni esistenti (cioè poter continuare il clustering su quella esistente quando un valore viene modificato o nuovo viene aggiunto) è altamente preferito.

Quindi, tutto sommato:

Si può pensare a un algoritmo che fornirà un punto debole tra efficienza computazionale e l'accuratezza dei cluster WRT. il problema sopra definita?

Ci sono alcune euristiche bello per il k-means algoritmo per calcolare automaticamente il valore di K in anticipo?

Answer 1

Credo che il clustering gerarchico sarebbe più tempo efficiente nel tuo caso (con una sola dimensione). A seconda del compito, è possibile implementare qualcosa di simile:

Avendo N datapoints d _i con il valore 1-dimensione x _i :

1. Ordina datapoints in base alla loro x _i Valore.
2. calcolare distanze tra datapoints adiacenti (N-1) distanze. Ciascuna distanza deve essere assegnata una coppia di punti dati originali (d _i , D _j ).
3. distanze Sort al fine di generare lista di coppie Datapoint (d _i , D _j ), a partire da quello più vicino decrescente.
4. iterativamente unire datapoint (d _i , D _j ) in gruppi, a partire dall'inizio della lista (la coppia più vicino). (A seconda dello stato attuale di d _i d _j , unendoli significa: (a) creazione di nuovo cluster per due datapoint non clustered, (b) aggiungere un punto dati di cluster esistente e (c) che unisce due cluster.)
5. Interrompi unire, se la distanza è superiore a una certa soglia.
6. Creare Singleton cluster per datapoints che non hanno ottenuto in cluster.

Questo algoritmo implementa unico legame clustering. Può essere regolato facilmente per implementare linkage media. Complete linkage sarà meno efficiente, ma quelle forse più facile darà buoni risultati a seconda dei dati e compito .

Credo di 200K datapoints deve prendere sotto il secondo, se si utilizzano strutture di dati corretti per le operazioni di cui sopra.

Answer 2

Provare a utilizzare HDBSCAN, anche se si tratta di un metodo gerarchico, potrebbe rivelarsi più efficiente. Sono in esecuzione su insiemi di dati multidimensionali un po 'più lunghe rispetto 200k, e ci vuole meno di un minuto per l'esecuzione. L'avvertenza è il numero di cluster che potrebbe produrre. Se sono troppi si potrebbe desiderare di attaccare con un metodo di partizionamento.