7

我有以下问题 - 抽象出来以提出关键问题。

我有 10 个点，每个点都有一些距离。我想要

  1. 能够找到簇的中心，即与其他点的成对距离最小的点， 令 p(j) ~ p(k) 表示点 j 和 k p(i) 之间
    的成对距离 -
    集群的点 iff p(i) st min[sum(p(j)~p(k))] for all 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

我将如何计算哪个是该集群的中心点？

4

4 回答 4

8

据我了解，这看起来像 K 均值聚类，而您正在寻找的通常被称为“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

一种）

  • 找到所有距离的中值或平均值。= 平均所有
  • 对于每个 p，找到到其他机器的平均距离。= avgP(i)
  • 选择较近的一个作为中心。avgAll ~= avgP(i)

b）暂时不知道..

也许对于每个 p，找到更接近的机器。

通过这个逻辑制作一个图表。

比以某种方式（我还不知道）划分图表

于 2009-08-10T08:59:27.597 回答
1

您正在尝试做的事情，或者至少（b）属于聚类分析。数学/统计/计量经济学的一个分支，其中数据点（例如 n 维空间中的点）在组或集群之间进行划分。如何做到这一点并不是一个小问题，有很多很多可能的方法。

阅读更多关于聚类分析的维基百科文章。

于 2009-08-10T14:23:19.163 回答