Znajdowanie centrum klastra

Question

Mam następujący problem - streszczenie, aby wydobyć kluczowe kwestie.

Mam 10 punktów, każda w pewnej odległości od drugiej. Chcę

1. móc znaleźć centrum gromady czyli punkt, dla którego parami odległość do każdego innego punktu jest zminimalizowane,
   Niech P (j) ~ p (k) reprezentuje parami odległość beteen punkty j i k
   p (i) jest punktem środkowym klastra iff p (i) min [suma (p (j) ~ p (k))] dla wszystkich 0 < j, k < = n gdzie mamy n punktów w klastrze
2. określić, jak podzielić klastra na dwa klastry po liczbie punkty danych w klastrze przekraczają pewien próg t.

To nie jest przestrzeń euklidesowa. Ale odległości można podsumować następująco - P (i) jest punkt 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 

Jak obliczyć, która jest centralnym punktem tej grupy?

Answer 1

O ile rozumiem, to wygląda algorytm centroidów i co szukasz jest zazwyczaj znany jako "Medoids.

Zobacz tutaj: http://en.wikipedia.org/wiki/Medoids lub tutaj: http://en.wikipedia.org/wiki/K-medoids

Answer 2

)

• znaleźć mediana lub średnie wartości wszystkich dystansach. = avgAll
• Dla każdego p, znajdź średnią odległość do innych maszyn. = avgP (i)
• Wybierz bliżej jako środek. avgAll ~ = avgp (i)

b) żaden pomysł na razie ..

może dla każdego p, znaleźć bliżej urządzenia.

według tej logiki utworzyć wykres.

niż jakoś (nie wiem jeszcze) podzielić wykres

Answer 3

Co starasz się zrobić, albo co najmniej (b) należy do Cluster Analysis. Oddział matematyki/statystyki/ekonometrii, w którym punkty danych (np. Punkty w przestrzeni n-wymiarowej) są dzielone między grupy lub klastry. Jak to zrobić, nie są to trywialne pytania, istnieje wiele, wiele możliwych sposobów.

Czytaj więcej na the wikipedia article on cluster analysis.

Answer 4

Być może niedługo będę miał ten dreszcz, który pojawia się tuż przed ujawnieniem całkowitej głupoty. Ale czy to nie daje łatwo brutalnej siły? W języku 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