Нахождение центра кластера

Question

У меня следующая проблема - сделана аннотация, чтобы выявить ключевые проблемы.

У меня есть 10 точек, каждая из которых находится на некотором расстоянии друг от друга. Я хочу

1. быть в состоянии найти центр кластера, то есть точку, для которой минимизируется попарное расстояние до каждой другой точки,
   пусть p (j) ~ p (k) представляет попарно расстояние между точками j и k
   p (i) - центральная точка кластера, если p (i) s.t. min [сумма (p (j) ~ p (k))] для всех 0
2. определяет, как разбить кластер на два кластера, когда число точек данных в кластере превысит некоторый порог t.

Это не евклидово пространство. Но расстояния можно суммировать следующим образом - p (i) - это точка 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 

Как бы я вычислил, какая точка центра этого кластера?

Answer 1

Насколько я понимаю, это похоже на кластеризацию K-средств, а то, что вы ищете, обычно называется "Medoids".

См. Здесь: http://en.wikipedia.org/wiki/Medoids или здесь: http://en.wikipedia.org/wiki/K-medoids

Answer 2

Может быть, у меня будет этот фриссон, который случится прямо перед тем, как проявить полную глупость. Но разве это не легко поддается грубой силе? В 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

Answer 3

а)

• найти средние или средние значения всех расстояний. = avgAll
• Для каждого p найдите среднее расстояние до других машин. = avgP (i)
• Выберите ближайший центр. avgAll ~ = avgP (i)

б) пока понятия не имею ..

может быть, для каждого р, найти машину ближе.

по этой логике составить график.

чем-то (я пока не знаю) поделить график

Answer 4

То, что вы пытаетесь сделать, или, по крайней мере (б), относится к кластерному анализу. Раздел математики / статистики / эконометрики, где точки данных (например, точки в n-мерном пространстве) разделены между группами или кластерами. Как это сделать, это не тривиальные вопросы, есть много-много возможных способов.

Подробнее читайте в статье в Википедии о кластерном анализе .