algorithm - 基于关系权重对对象进行聚类的聚类算法

Question

我有 n 个词和它们的相关权重，这给了我一个 n*n 矩阵。我打算将其用于搜索算法，但问题是我需要根据成对关系对输入的关键字进行聚类。假设关键字是 {tennis,federer,wimbledon,london,police} 并且我们的权重矩阵中有以下数据:

            tennis  federer  wimbledon  london  police      
tennis        1       0.8       0.6       0.4     0.0
federer       0.8      1        0.65      0.4     0.02
wimbledon     0.6     0.65       1        0.08    0.09
london        0.4     0.4       0.08        1      0.71
police        0.0     0.02      0.09      0.71     1

我需要一种算法将它们聚类为 2 个聚类:{tennis,federer,wimbledon} {london,police}。有什么知道的聚类算法可以处理这样的事情吗？我做了一些研究，看起来 K-means 算法是用于聚类的最著名的算法，但显然 K-means 不适合这种情况。 如果有任何帮助，我将不胜感激。

Answer 1

您可以将其视为网络聚类问题。使用最新版本的 mcl 软件 ( http://micans.org/mcl )，您可以执行此操作(我将您的示例命名为 fe.data)。

mcxarray  -data fe.data -skipr 1 -skipc 1 -write-tab fe.tab -write-data fe.mci -co 0 -tf 'gq(0)' -o fe.cor
   # the above computes correlations (put in data file fe.cor) and a network (put in data file fe.mci).
   # below proceeds with the network.
mcl fe.mci -I 3 -o - -use-tab fe.tab
   # this outputs the clustering you expect. -I is the 'inflation parameter'. The latter affects
   # cluster granularity. With the default parameter 2, everything ends up in a single cluster.

免责声明:我编写了 mcl 和一系列相关的网络加载/转换和分析程序，最近更名为“mcl-edge”。它们都集中在一个软件包中。看到你的例子让我很好奇它是否可以用 mcl-edge 来实现，所以我很快就测试了它。