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

Question

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

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

1. уметь найти центр кластера, т.е.точка, для которой попарное расстояние друг от друга минимально,
   пусть p(j) ~ p(k) представляет собой попарное расстояние между точками j и k.
   p(i) является центральной точкой кластера тогда и только тогда, когда p(i) st.t.min[sum(p(j)~p(k))] для всех 0 < j,k <= n, где у нас есть n точек в кластере
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 означает, и то, что вы ищете, обычно известно как «медоиды».

Глянь сюда: http://en.wikipedia.org/wiki/Medoids или здесь: http://en.wikipedia.org/wiki/K-medoids

Answer 2

Возможно, меня вот-вот охватит дрожь, которая возникает перед тем, как продемонстрировать полную глупость.Но разве это не легко поддается грубой силе?В Питоне:

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

а)

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

б) пока не знаю ..

возможно, для каждого p найдите более близкую машину.

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

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

Answer 4

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

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