Raggruppamento in 2 punti

Question

Dato: Dato un insieme di N punti nel piano 2D (coordinate xey) e un set di N raggi corrispondenti a ciascun punto. Faremo riferimento al disco di un punto come il disco centrato nel punto con il suo raggio.

Problema: Raggruppa i punti. Un gruppo di punti è tale che ogni punto cade all'interno del disco di almeno un altro punto nel cluster OPPURE almeno un altro punto nel cluster cade nel suo disco. I cluster di punti singoli non contano come cluster.

Ho bisogno di un algoritmo per calcolare questo in modo efficiente (preferibilmente senza ricorrere a complicate tecniche di hashing spaziale come kd-tree). Posso accontentarmi del tempo di esecuzione O (N^2) ma sicuramente non più di O (N^3). Credo che questo dovrebbe essere semplice, ma mi sto facendo prendere dalla natura non reciproca della mia condizione di clustering.

In sostanza, sto cercando di compilare il prototipo di funzione C:

int cluster_points(
    size_t n, 
    point_t *pt, // length n list of points 
    double *radius, // length n list of radii for each point 
    int *cluster, // length n list of cluster indexes; -1 if not clustered 
    size_t *ncluster // number of clusters (number of distinct non -1 entries in cluster) 
); 

Questo non è lavoro. Ho bisogno di questo come parte di un algoritmo a matrice per il clustering di numeri complessi.

Answer 1

La soluzione forza bruta è solo O (N), quindi dovrebbe funzionare per voi.

1) Iniziare con tutti i punti nel gruppo non assegnato.

2) Seleziona un punto e guarda tutti gli altri nel gruppo non assegnato e verifica se soddisfa il criterio dei raggi che descrivi.

• 2a) Se sì, avviare un gruppo, e continuare con tutti gli altri punti per vedere se si adattano a questo gruppo (in base al punto corrente), e se si inseriscono in, spostarli da il gruppo non assegnato a questo nuovo.
• 2ab) Al termine del punto corrente, passare a ciascun punto aggiunto al gruppo e controllare tutti i punti nel gruppo non assegnato.
• 2b) Tuttavia, se nessun punto corrisponde ai criteri di raggio per il punto corrente, scartarlo.

3) Alla fine avrete raggruppato i punti dai vostri criteri, e avrà fatto altro che N * (N/2) ispezioni.

Btw, quello che descrivi non è quello che normalmente si intende per "clustering", quindi penso che stia buttando qui le persone. Ciò che rende il clustering un problema difficile è che la questione se due punti vicini saranno assegnati allo stesso cluster è determinata da tutti gli altri punti nel set di dati. Nel tuo caso, è (fondamentalmente) determinato solo dalle proprietà dei due punti, in modo che nel tuo caso, puoi semplicemente controllarli tutti.

Answer 2

k-means basano su una combinazione di ricerca locale e l'algoritmo di Lloyd

http://www.cs.umd.edu/~mount/Projects/KMeans/
(programma è distribuito sotto le condizioni della GNU General Public License.)

k-means, K- mediane, k-medoids, treecluster, mappe auto-organizzanti, clustercentroids, clusterdistance http://bonsai.hgc.jp/~mdehoon/software/cluster/cluster.pdf

Answer 3

clustering è un problema NP-hard, anche se si è data il numero di cluster a priori, quindi si può probabilmente rinunciare a ottenere un tempo di esecuzione polinomiale. Esistono molte tecniche per fare ciò e la letteratura si trova principalmente nella comunità di apprendimento automatico, k-means è probabilmente l'algoritmo più semplice da comprendere e implementare.

Answer 4

Sembra che l'ovvio algoritmo di O (n^2) sia quello di creare un grafico con i punti come vertici e quindi collegare due punti se le condizioni che si danno sono soddisfatte. E poi leggi i componenti collegati del grafico, scartando i singleton. Inoltre, la condizione che hai dato per il clustering mi sembra simmetrica. Mi sto perdendo qualcosa?

Answer 5

Hai una collezione U di coppie (p, R) dove p è un punto e R il suo raggio.

La relazione ~ su U: (p, R) ~ (q, S) < => p si trova nel disco di q o q si trova nel disco di p < => | p-q | < = max (R, S)

è chiaramente riflessivo e simmetrico e quindi la sua chiusura transitiva (~ , ad esempio) è una relazione di equivalenza. Le classi di equivalenza sotto ~ saranno (singletons o) cluster.

Credo ci siano algoritmi standard per calcolare le classi di equivalenza della chiusura transitiva di una relazione come ~ sopra. Ad esempio questo è discusso in Numerical Recipes nel capitolo sull'ordinamento, e dicono che la loro routine è basata su Knuth.

(Mi spiace non fornire un collegamento, ma una breve ricerca non ha prodotto esattamente la cosa giusta).