图形集群工具

Question

我已经构建了一个协作过滤算法（余弦项目项目）来揭示项目之间的关系。最后，我的结果数据看起来像这样，

itemNo relatedItemNo similarityValue 
1546301 1543903 0.10767638 
1546301 1530836 0.093250481 
1546301 1479721 0.10767638 
1557616 1573636 0.121267813 
1557616 1558024 0.161690417 
1086551 1437760 0.127000127 
1086551 1552321 0.083333333 
1086551 1578137 0.127000127 
1086551 1560842 0.081110711 
....... ....... ........... 

现在我想对它进行聚类。使用项目之间的相似性值我想要得到一些集群说1546301,1479721,1543903是在集群A; 1086551,1552321,1560842在群集B中。

我该如何管理？我不熟悉数据挖掘，因此即使是简单的工具也很难使用。

我知道这叫做Graph Clustering，Ive下载了igraph for r，安装了cluto并尝试了一些步骤，但我甚至都没有明白它们的输入数据格式。

你能告诉我方式吗？ :)

Answer 1

图聚类的主题是巨大的，有很多不同的方法，每个方法都有自己的特殊细节。有关该主题的广泛治疗，请参阅this review。

但是，如果您正在寻找能够帮助您入门的内容并根据目前提供的说明进行操作，则可以尝试使用Centrality来识别群集。具体而言，betweenness centrality（定义为顶点）将提供一种机会，通过最常见的首选项（假设您的相似性指的是something like this）对图的顶点（表示项目）进行排序。

在Python这样做是几行用Networkx

import networkx 
G = networkx.read_edgelist("myfile.csv", delimiter="\t") #Assuming that your file is tab separated here. If it is coma separated then substitute \t for a ,. Also, it would be good to get rid of the header (i.e. the first line of the CSV. 
bc = networkx.betweenness_centrality(G) 

可变bc的事现在持有的每个节点的中介中心。要按相反顺序排序（因此首先获得集群“集线器”），您可以简单地使用bc_sorted = sorted(bc.items(),key=lambda x:x[1],reverse=True)

您可以将上述内容用作将代码“翻译”为其他语言的模板，例如， R.实际上，有相当于Python的包（igraph），它对已经实现的节点有betweenness centrality度量标准，以及Read_Edgelist可以让你从磁盘读取数据。也就是说，让你开始的等效R代码与这三条线没有太大的不同。

希望这会有所帮助。