7

私は次の問題を抱えています-重要な問題を引き出すために抽象化しました。

私はそれぞれ10ポイントを持っており、それらは互いにある程度の距離を置いています。したい

  1. クラスターの中心、つまり、他の点とのペアワイズ距離が最小化されているポイントを見つけることができます
    。p（j）〜p（k）は、ポイントjとk
    p（i）が中心である間のペアワイズ距離を表します。クラスター内のn個のポイントがあるすべての0<j、k <= nに対して、クラスターのポイントiff p（i）st min [sum（p（j）〜p（k））]
  2. クラスター内のデータポイントの数があるしきい値tを超えたら、クラスターを2つのクラスターに分割する方法を決定します。

これはユークリッド空間ではありません。しかし、距離は次のように要約できます-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

このクラスターの中心点を計算するにはどうすればよいですか？

4

4 に答える 4

8

私が理解している限り、これは K Means Clustering のように見えます。探しているものは、通常「Medoids」として知られています。

こちらをご覧ください: http://en.wikipedia.org/wiki/Medoidsまたはこちら: http://en.wikipedia.org/wiki/K-medoids

于 2009-08-10T09:05:18.413 に答える
4

私は、完全な愚かさを示す直前に来るあのフリッソンを持とうとしているのかもしれません。しかし、これは力ずくで簡単に屈服しませんか? 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
于 2009-08-11T14:02:14.117 に答える
1

a）

  • すべての距離の中央値または平均値を見つけます。= avgAll
  • 各pについて、他のマシンまでの平均距離を求めます。= avgP（i）
  • 近い方を中心として選びます。avgAll〜= avgP（i）

b）今のところわからない。

多分各pについて、より近いマシンを見つけてください。

このロジックでグラフを作成します。

どういうわけか（私はまだ知りません）グラフを分割するよりも

于 2009-08-10T08:59:27.597 に答える
1

あなたがやろうとしていること、または少なくとも（b）クラスター分析に属しています。データポイント (たとえば、n 次元空間のポイント) がグループまたはクラスター間で分割される、数学/統計/計量経済学の分野。これを行う方法は些細な問題ではなく、非常に多くの方法が考えられます。

詳細については、クラスター分析に関するウィキペディアの記事を参照してください。

于 2009-08-10T14:23:19.163 に答える