2009-08-10 26 views
5

Ho il seguente problema - fatto astratto per far emergere i problemi chiave.Trovare il centro di un cluster

Ho 10 punti ciascuno che è una certa distanza dall'altro. Voglio

  1. essere in grado di trovare il centro del cluster vale a dire il punto per il quale è ridotto al minimo la distanza a coppie l'uno all'altro punto,
    Sia P (j) ~ p (k) rappresentano la distanza a coppie beteen punti je k
    p (i) è il punto centrale del cluster iff p (i) st min [sum (p (j) ~ p (k))] per tutti 0 < j, k < = n dove abbiamo n punti del cluster
  2. determinare come dividere il cluster in due cluster dopo che il numero di i punti dati nel cluster superano una certa soglia t.

Questo non è spazio euclideo. Ma le distanze possono essere riassunti come segue - p (i) è il punto I:

 p(1) p(2) p(3) p(4) p(5) p(6) p(7) p(8) p(9) p(10) 
p(1) 0  2  1  3  2  3  3  2  3  4 
p(2) 2  0  1  3  2  3  3  2  3  4 
p(3) 1  1  0  2  0  1  2  1  2  3 
p(4) 3  3  2  0  1  2  3  2  3  4  
p(5) 2  2  1  1  0  1  2  1  2  3 
p(6) 3  3  2  2  1  0  3  2  3  4 
p(7) 3  3  2  3  2  3  0  1  2  3 
p(8) 2  2  1  2  1  2  1  0  1  2 
p(9) 3  3  2  3  2  3  2  1  0  1 
p(10) 4  4  3  4  3  4  3  2  1  0 

Come faccio a calcolare quale è il punto centrale di questo cluster?

+1

Si prega di definire "centro del cluster" – Nifle

+0

@ Nifle - done ...avete qualche idea – Ankur

+0

L'applicazione ha a che fare con i concetti di clustering - la mia applicazione è un archivio di dati semantico - i punti rappresentano oggetti astratti. Voglio raggruppare gli oggetti per poter determinare "concetti" – Ankur

risposta

7

Per quanto ho capito questo si presenta come K-Means, e ciò che si sta cercando è generalmente nota come 'Medoids.

vedere qui: http://en.wikipedia.org/wiki/Medoids o qui: http://en.wikipedia.org/wiki/K-medoids

+0

In suvated: questo in effetti sembra la strada da percorrere per le metriche non euclidee, ma richiede almeno che la disuguaglianza triangolare sia valida, confesso che non sono abbastanza paziente da verificare che per esempio di Ankur: –

+0

@ Jim, la disuguaglianza triangolare si trova nel mio "spazio metrico", quindi questo dovrebbe funzionare – Ankur

1

una)

  • ritrovamento mediana o valori medi di tutte le distanze. = avgAll
  • Per ogni p, trova la distanza media dalle altre macchine. = avgP (i)
  • Selezionare quello più vicino come centro. avgAll ~ = avgP (i)

b) idea per ora ..

forse per ogni p, trovare la macchina più vicino.

da questa logica fare un grafico.

che in qualche modo (non so ancora) dividere il grafico

1

Quello che stai cercando di fare, o per lo meno (b) appartiene al cluster Analysis. Un ramo di matematica/statistica/econometria dove i punti di riferimento (ad esempio punti nello spazio n-dimensionale) sono suddivisi tra gruppi o cluster. Come fare questo non è una domanda banale, ci sono molti, molti modi possibili.

Ulteriori informazioni allo the wikipedia article on cluster analysis.

2

Potrei essere sul punto di avere quel brivido che viene prima di mostrare la totale stupidità. Ma questo non rende facilmente la forza bruta? In Python:

distances = [ 
[ 0 , 2 , 1 , 3 , 2 , 3 , 3 , 2 , 3 , 4 , ], 
[ 2 , 0 , 1 , 3 , 2 , 3 , 3 , 2 , 3 , 4 , ], 
[ 1 , 1 , 0 , 2 , 0 , 1 , 2 , 1 , 2 , 3 , ], 
[ 3 , 3 , 2 , 0 , 1 , 2 , 3 , 2 , 3 , 4 , ], 
[ 2 , 2 , 1 , 1 , 0 , 1 , 2 , 1 , 2 , 3 , ], 
[ 3 , 3 , 2 , 2 , 1 , 0 , 3 , 2 , 3 , 4 , ], 
[ 3 , 3 , 2 , 3 , 2 , 3 , 0 , 1 , 2 , 3 , ], 
[ 2 , 2 , 1 , 2 , 1 , 2 , 1 , 0 , 1 , 2 , ], 
[ 3 , 3 , 2 , 3 , 2 , 3 , 2 , 1 , 0 , 1 , ], 
[ 4 , 4 , 3 , 4 , 3 , 4 , 3 , 2 , 1 , 0 , ], 
] 

currentMinimum = 99999 

for point in range (10) : 
    distance_sum = 0 
    for second_point in range (10) : 
     if point == second_point : continue 
     distance_sum += distances [ point ] [ second_point ] 
    print '>>>>>', point, distance_sum 

    if distance_sum < currentMinimum : 
     currentMinimum = distance_sum 
     centre = point 

print centre 
+0

Ciao Bill, sono giunto a una conclusione simile: una volta che hai il tuo cluster e vuoi scegliere il centro di un ammasso, th è praticamente il modo di farlo. Quello che sto facendo è questo: comincio con un cluster singolo perché comincio con 1 punto dati, man mano che altri vengono aggiunti e il mio cluster diventa maggiore di qualche soglia t, l'ho diviso. Quindi scelgo i due punti più importanti come centri per i nuovi cluster. Ogni punto viene quindi assegnato a uno dei due punti a seconda di quale è più vicino. Quindi viene calcolato il centro effettivo in ciascun cluster. – Ankur

Problemi correlati