圖形集羣工具

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代碼與這三條線沒有太大的不同。

希望這會有所幫助。