algorithm - 寻找簇的中心

Question

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

我有 10 个点，它们之间有一定的距离。我要

1. 能够找到集群的中心，即与其他点的成对距离最小化的点，
   令 p(j) ~ p(k) 表示点 j 和 k 之间的成对距离
   p(i) 是簇的中心点当且仅当 p(i) s.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 均值聚类，而您要查找的通常称为“Medoids”。

See here: http://en.wikipedia.org/wiki/Medoids or here: http://en.wikipedia.org/wiki/K-medoids