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 il link alla ;-)) alcuni algoritmi di clustering (il più semplice, meglio è!) O le librerie che mi può aiutare?

Chiarimento La maggior parte delle algoritmi di clustering richiedono che gli oggetti siano disposti in un certo spazio n-dimensionale. Questo spazio viene utilizzato per trovare "baricentri" di cluster. Nel mio caso, io non so cosa è N, né so come estrarre un sistema di coordinate dagli oggetti. Tutto quello che so è quanto lontano a parte 2 oggetti sono. Vorrei trovare un buon algoritmo di clustering che utilizza solo quelle informazioni.

Immaginate di essere il clustering basato sul "odore" di un oggetto. Non sai come laici "odori out" su un piano 2D, ma non si sa se due odori sono simili o meno.

Answer 1

Credo che siete alla ricerca di k-medoids . E 'come K-significa in specificare il numero di cluster, K , in anticipo, ma non richiede che si dispone di una nozione di "media" gli oggetti che si stanno raggruppando come K- mezzi fa.

Al contrario, ogni gruppo ha un rappresentante medoid , che è il membro del cluster più vicino al centro. Si potrebbe pensare ad esso come una versione di K-means che trova "mediane" invece di "mezzi". Tutto ciò che serve è una metrica distanza per raggruppare le cose, e ho usato questo in alcuni dei miei lavori esattamente per le stesse ragioni che citi.

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

1. PAM è la base O (n ^ 2) realizzazione di k-medoids.
2. CLARA è un molto più più veloce, campionato versione di PAM. Funziona raggruppando sottoinsieme campionatura casuale di oggetti con PAM e raggruppare l'intero set di oggetti basati sulla sottoinsieme. Si dovrebbe comunque essere in grado di ottenere ottimi clustering veloce con questo.

Se avete bisogno di ulteriori informazioni, ecco una carta che dà un panoramica di queste e di altre k-medoids metodi.

Answer 2

Ecco uno schema per un algoritmo di clustering che non ha il K-means esigenza di trovare un baricentro.

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

Questo algoritmo sarà certamente raggruppare gli oggetti. Ma il suo tempo di esecuzione è O (n ^ 2) . Più esso è guidato da quei primi n i punti scelti.

Qualcuno può migliorare su questo (perf runtime migliori, meno dipendente scelte iniziali)? Mi piacerebbe vedere le vostre idee.

Answer 3

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 pagina di Wikipedia . K-means clustering di è una buona scelta:

  

L'algoritmo K-means assegna ogni punto al cluster cui centro (chiamato anche centroide) è più vicino. Il centro è la media di tutti i punti del cluster - cioè, le sue coordinate sono la media aritmetica per ogni dimensione separatamente su tutti i punti del 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 è così   allo stesso risultato ad ogni esecuzione,   poiché i cluster ottenuti dipendono   le assegnazioni casuali iniziali. esso   minimizza intra-cluster varianza, ma   non assicura che il risultato ha un   minimo globale di varianza. Un altro   svantaggio è il requisito per   il concetto di un mezzo per essere definibile   che non è sempre il caso. Per tale   set di dati variante k-medoids è   . Appropriato

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 sono all'interno dello stesso cluster, k , e che sono la distanza massima parte. Per chiarire, ci dovrebbe essere un a e b per l'intera serie, non uno a 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 , aggiungerli su k1 o k2 determinando la distanza media minima per tutti gli altri oggetti che cluster.
5. Ripetere i passaggi 2-5 fino sono formate N cluster.

Credo che questo algoritmo dovrebbe darvi una discreta clustering, anche se l'efficienza potrebbe essere piuttosto male. Per migliorare l'efficienza si potrebbe alterare il punto 3 in modo che a trovare la distanza minima da solo l'oggetto originale che ha iniziato il cluster, piuttosto che la distanza media a tutti gli oggetti già presenti nel cluster.

Answer 5

filogenetica analisi della sequenza del DNA utilizza regolarmente il clustering gerarchico su stringhe di testo, con [allineamento] matrici a distanza. 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] librerie:

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

Questo approccio potrebbe aiutare a determinare quanti [k] clusters "naturali" ci sono e quali oggetti da usare come le radici per il K-means approcci sopra.