Come raggruppare oggetti (senza coordinate)

Question

Ho una lista di oggetti opachi. Sono in grado di calcolare la distanza tra loro (non è vero, basta impostare le condizioni per il problema), solo:

class Thing { 
    public double DistanceTo(Thing other); 
} 

Vorrei raggruppare questi oggetti. Vorrei controllare il numero di cluster e vorrei per "vicino" oggetti di essere nello stesso cluster:

List<Cluster> cluster(int numClusters, List<Thing> things); 

Qualcuno può suggerire (e link al ;-)) alcuni algoritmi di clustering (la più semplice, meglio è!) o biblioteche che possono aiutarmi?

Chiarimento La maggior parte degli algoritmi di clustering richiedono che gli oggetti siano disposti in uno spazio N-dimensionale. Questo spazio è usato per trovare "centroidi" di cluster. Nel mio caso, non so cosa sia N, né so come estrarre un sistema di coordinate dagli oggetti. Tutto quello che so è quanto distano 2 oggetti. Mi piacerebbe trovare un buon algoritmo di clustering che usi solo quell'informazione.

Immagina di raggruppare in base all'odore di un oggetto. Non sai come deporre "gli odori" su un piano 2D, ma sai se due odori sono simili o meno.

Answer 1

Penso che stiate cercando K-Medoids. È come K-significa che si specifica in anticipo il numero di cluster, K, ma non è necessario avere una nozione di "mediazione" degli oggetti che si stanno raggruppando come fa K-means.

Invece, ogni cluster ha un mediatore rappresentante, che è il membro del cluster più vicino al centro. Si potrebbe pensare a una versione di K-means che trova "mediani" invece di "mezzi". Tutto ciò di cui hai bisogno è una metrica di distanza per raggruppare le cose, e ho usato questo in alcuni dei miei lavori proprio per le stesse ragioni che hai citato.

Naive K-medoids non è l'algoritmo più veloce, ma ci sono varianti veloci che sono probabilmente abbastanza buone per i vostri scopi. Qui ci sono le descrizioni degli algoritmi e dei collegamenti alla documentazione per le loro implementazioni in R:

1. PAM è la base O implementazione (n^2) di k-medoids.
2. CLARA è una versione di PAM più veloce e campionata. Funziona raggruppando sottoinsiemi di oggetti casualmente campionati con PAM e raggruppando l'intero set di oggetti in base al sottoinsieme. Dovresti comunque essere in grado di ottenere ottimi clustering velocemente con questo.

Se avete bisogno di ulteriori informazioni, here's a paper che fornisce una panoramica di questi e altri metodi K-medoidi.

Answer 2

Ecco un rapido algoritmo.

While (points_left > 0) { 
Select a random point that is not already clustered 
Add point and all points within x distance 
    that aren't already clustered to a new cluster. 
} 

In alternativa, leggere the wikipedia page. K-means clustering è una buona scelta:

L'algoritmo di K-means assegna ciascun punto al cluster il cui centro (detto anche centroide) è più vicino. Il centro è la media di tutti i punti nel cluster, ovvero le sue coordinate sono la media aritmetica per ogni dimensione separatamente su tutti i punti nel cluster.

I passi dell'algoritmo sono:

* Choose the number of clusters, k. 
* Randomly generate k clusters and determine the cluster centers, or 
    directly generate k random points as cluster centers. 
* Assign each point to the nearest cluster center. 
* Recompute the new cluster centers. 
* Repeat the two previous steps until some convergence criterion is 
    met (usually that the assignment hasn't changed). 

I principali vantaggi di questo algoritmo sono la sua semplicità e velocità che permette di eseguire su grandi insiemi di dati. Il suo svantaggio è che non produce lo stesso risultato con ogni esecuzione, poiché i cluster risultanti dipendono da le assegnazioni casuali iniziali. È minimizza la varianza intra-cluster, ma non garantisce che il risultato abbia un minimo globale di varianza globale. Un altro svantaggio è il requisito per il concetto di un mezzo definibile che non è sempre il caso. Per tali dataset la variante k-medoids è appropriata.

Answer 3

Ecco uno schema per un algoritmo di clustering che non ha il requisito di K di trovare un centroide.

1. Determina la distanza tra tutti gli oggetti. Registrare il n più oggetti separati.
   [trova radici dei nostri cluster, tempo O (n^2)]
2. attribuiscono ciascuna di tali n punti casuali per n nuovi cluster distinti.
3. Per ogni altro oggetto:
   [oggetti assegnare ai cluster, un tempo O (n^2)]
   1. Per ogni cluster:
      1. calcolare la distanza media da un cluster a quella oggetto calcolare la media della distanza di ciascun oggetto nel cluster rispetto all'oggetto.
         
   2. Assegnare l'oggetto al cluster più vicino.

Questo algoritmo sarà certamente raggruppare gli oggetti. Ma il suo runtime è O (n^2). Inoltre è guidato da quei primi n punti scelti.

Qualcuno può migliorare su questo (migliore durata runtime, meno dipendente dalle scelte iniziali)? Mi piacerebbe vedere le tue idee.

Answer 4

Che ne dite di questo approccio:

1. Assegna tutti gli oggetti di un cluster.
2. Trova i due oggetti, un e b, che si trovano all'interno dello stesso cluster, k, e che sono la distanza massima parte. Per chiarire, ci dovrebbe essere uno un e B per l'intera serie, non uno un e b per ogni cluster.
3. grappolo Split k in due gruppi, k1 e k2, uno con oggetto un e uno con oggetto b.
4. Per tutti gli altri oggetti del cluster k, aggiungerlo alla k1 o k2 determinando la distanza media minima per tutti gli altri oggetti nello stesso cluster.
5. Ripetere i passaggi da 2 a 5 fino alla formazione dei cluster N.

Penso che questo algoritmo dovrebbe fornire un clustering abbastanza buono, anche se l'efficienza potrebbe essere piuttosto negativa. Per migliorare l'efficienza, è possibile modificare il passaggio 3 in modo da individuare la distanza minima solo dall'oggetto originale che ha avviato il cluster, anziché la distanza media di tutti gli oggetti già presenti nel cluster.

Answer 5

L'analisi di sequenza filogenetica del DNA utilizza regolarmente il clustering gerarchico su stringhe di testo, con matrici di distanza [allineamento].Ecco un bel tutorial R per il clustering:

• http://www.statmethods.net/advstats/cluster.html

(scorciatoia: andare direttamente alla sezione "Hierarchical agglomerante" ...)

Ecco alcuni altri [lingua] biblioteche:

• http://bonsai.ims.u-tokyo.ac.jp/~mdehoon/software/cluster/
• http://code.google.com/p/scipy-cluster/

Questo approccio può aiutare a determinare quanti [k] cluster "naturali" ci sono e quali oggetti utilizzare come radici per gli approcci k-means sopra.