Trovare il centro di un cluster

Question

Ho il seguente problema - fatto astratto per far emergere i problemi chiave.

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?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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