基于滴水原理的關聯聚類算法*

華佳林，于 劍

1.北京交通大學 計算機與信息技術學院，北京 100044

2.交通數據分析與挖掘北京市重點實驗室，北京 100044

1 引言

聚類[1]是數據挖掘和機器學習中一個重要的問題，它根據某些標準將沒有標定的數據分割到不同的類中。通常要進行聚類的數據以兩種形式呈現[2]：特征向量或相似（相異）性矩陣。大多數的聚類算法采用特征向量作為輸入，這種類型的聚類算法已有大量的文獻進行研究[3]。這些研究主要集中在特征提取[4-7]和聚類方法[8-13]上，它們通常需要事先知道某些重要的參數，比如聚類的個數。

關聯聚類[14]是另外一種形式的聚類問題，算法輸入是一個有符號圖，圖中節點表示數據，節點之間由有符號邊連接，即正邊和負邊。這種有符號圖能夠很好地表達現實世界中的很多場景，比如對象之間的相似/不相似、朋友/敵人、喜歡/不喜歡等。數據之間的邊可以加上一個權重來表示正或負關系的程度。關聯聚類的目的是使得在同一個類中的點盡可能由正邊連接，而不同類中的點盡可能由負邊連接。在關聯聚類中不事先設定聚類的個數，而是完全由數據的內在結構所決定。

本文的主要貢獻如下:

（1）提出了一種基于滴水原理的大規模有符號圖收縮的方法（correlation clustering based on drop of water principle，CCDWP），基于該方法所得到的新的有符號圖能極大地降低問題的規模。

（2）基于新的有符號圖提出了一個關聯聚類算法，算法基于圖的內在結構，使用整數線性規化來對局部的點進行劃分。

（3）提出的算法既保證了結果的精確性，又能夠處理大規模有符號圖。

（4）應用不同數據集的實驗結果表明了本文提出的關聯聚類算法的有效性。

2 相關工作

對于圖中點的劃分通常在社交媒體數據挖掘中被定義為社區發現而進行研究。通常的社區發現任務要處理的圖并不考慮邊的符號，對于結果的要求是社區（聚類）內部邊的密度較大，社區之間邊的密度較小。

關聯聚類的任務包括兩種情況：第一種追求最大一致性，所謂的一致性指類內正邊和類間負邊；第二種追求最小不一致性，所謂的不一致性指類內負邊和類間正邊。無論哪種情況都被證明是NP-hard問題[14]。通常的方法基于求解最小不一致性。

對于關聯聚類的求解，一個自然的方法是將其表示成整數線性規化（integer linear programming，ILP）問題：

其中，w+ij和w-ij分別表示邊(i,j)的正權重或負權重；xij=0表示將點i和j指派到同一個類中，xij=1表示將點i和j指派到不同的類中。約束條件xij+xjk≥xik是為了防止結果中出現不一致的情況，比如xij=xjk=0,xik=1。但是ILP通常只能處理一兩百個點的網絡，面對更大的網絡時，時間的消耗讓人難以接受。很多研究將ILP中的變量xij∈{0,1}松弛到[0,1]中，從而轉化成線性規化（linear programming，LP）問題。對于新的變量的不同處理方式產生了不同的關聯聚類算法[15-18]。文獻[17-18]將xij看成是點之間的距離。文獻[17]將距離小于閾值的兩個點指派到同一個類中；而文獻[18]每次從任意一個點出發構造了一個球，凡是被球所包圍的點都與球心在同一個類中（稱為Ball-algorithm）。而文獻[16]將關聯聚類問題和聚類集成問題看成是同一個問題來進行研究，同時基于文獻[17]繼續研究如何取得更好的閾值。而文獻[15]則將1-xij看成點i和j在同一個類中的概率，當這個概率大于0.5時將對應的兩個點指派到同一個類中（稱為Pivot-algorithm）。Ball-algorithm和Pivot-algorithm是經典的關聯聚類算法。文獻[21]首先使用Fusion-Move的方法收縮有符號圖，在降低數據的規模后再使用傳統的關聯聚類算法（文中使用Pivot-algorithm）處理新的規模更小的圖。文獻[22]證明了關聯聚類問題如果按照最小不一致性來求解時與Multicut問題等價。

由于表達式（1）中的變量xij不是直接的類標，有些約束并沒有考慮在其中，比如xii=0,導致基于LP的關聯聚類算法得到的結果往往精度不高。因此在文獻[17,19-20]中半正定優化（semi-definite positive，SDP）被引入來求解關聯聚類問題。變量xij被重新定義為對應兩個點的類標向量的內積。所謂的類標向量，比如第i個點的類標向量表示點i被指派到第k個類中，而xij=ind(i)?ind(j)。顯然矩陣X=(xij)是半正定的。文獻[19-20]構建下列半正定模型：

分水嶺（watersheds）算法最早被用來進行梯度圖像的分割。對于一個梯度圖像根據滴水原理（drop of water principle）可以構造出圖像的分水嶺，一個積水盆地（catchment basin）即是圖像的一個分割。

本文提出的關聯聚類算法借用分水嶺算法的思路，首先對符號圖中的點按照正度從高到低進行排序，每次對度最高的點按照正權重降低最慢尋找路徑，將每個路徑中的點合并成一個新的點，從而收縮圖的規模。在收縮的圖上選出重要的點，利用ILP來判斷這些點和周圍點之間的合并或分割關系，從而最終得到聚類結果。

3 基于滴水原理的符號圖收縮

下面主要介紹如何借鑒滴水原理的思路來收縮大規模有符號圖。

3.1 滴水原理基本定義

滴水原理在機器學習中常被用來進行圖像分割處理。所謂的滴水原理是指當水從高處往下滴落時會沿著滴落速度最快的路徑下落。在基于分水嶺的圖像分割中，滴落路徑構成分水嶺，從而對圖像進行分割。

3.2 基于滴水原理的有符號圖收縮

在關聯聚類中，圖中的點從聚類的意義上看重要性并不一致，其中的正度比較大的點更容易形成聚類，這些點從某種意義上可以看成聚類的原型（prototypes），因此本文從重要的點（即正度比較大的點，記為i）開始，首先將與i有正邊連接的點（記為j）看作候選點，如果邊(i,j)的權重是點j所有的邊中權重最大的，則將i與j合并，找出所有這樣的j（記為j1,j2,…,jk），這些點都與i合并成一個新的點（新點還是記為i）。記I={i,j1,j2,…,jk}，任何兩個端點都在I中的邊直接刪除，而一個點在I中另一個不在其中的邊都合并成與i相連的邊，邊的權重是原來邊的權重相加。作者先前研究過按這種方式減小有符號圖的規模的關聯聚類算法并取得了不錯的效果，現在將進一步減小圖的規模。

基于滴水原理的有符號圖收縮來自這樣的一個直覺：從度較大的點出發，尋找一個正權重變化最小的路徑，則路徑上的點以極大的可能性屬于同一個類。因此繼續從j出發，尋找與j有正邊連接的點（記為l），如果l與j之間的邊的權重是l的所有正邊中權重最大的，則將l也加入集合I；接下來繼續從l出發按照上面的邏輯繼續往下尋找合適的點并入I，直到不能繼續往下搜索則終止。本文以一個隨機產生的有符號圖來說明。如圖1所示，圖1（a）是原始的有符號圖，圖中實線表示正邊，虛線表示負邊，邊上的數字表示權重，邊的粗細與權重匹配。進行簡單的統計就可以知道圖中的點4、15和24是比較重要的點，這幾個點以極大的概率稱為類原型。首先從4開始遍歷，可以看到點3、5、8、9和12與4之間的邊是其最大權重正邊，因此I={3,4,5,8,9,12}。繼續從I中的點出發，比如從3開始，發現2與3之間的邊是2的所有正邊中權重最大的邊，因此將2并入集合I，對I中其他點進行類似的處理，最終可以得到I={1,2,3,4,5,6,7,8,9,10,11,12,13}。接下來分別從15和24出發進行類似的操作，最終形成圖1（b）中所示的3個分割，每個分割是新的有符號圖中的一個點，這3個點之間是合并還是分割可以轉化成式（1）所示的ILP問題而獲得最佳解，從而形成最終的聚類結果。上面從點i出發構造集合I的過程實際上就是從點i出發沿正邊尋找權重變化最小的路徑，然后將這條路徑上的所有點合并成一個點，這個過程類似于滴水時的情形。

4 基于滴水原理的關聯聚類算法

下面給出詳細的算法過程。

算法1基于滴水原理的關聯聚類算法（CCDWP）

輸入：有符號圖G=(V,E,W)，其中V是頂點集合，E是邊集合，W是邊的權重集合。

輸出：聚類結果。

（1）對圖中點按照正邊度進行排序，對于正度最高的點i1，將所有與i1有正邊連接且該正邊是其所有邊中權重最大的點與i1合并，產生集合I1。

（2）對集合I1中除i1之外的點沿正邊尋找權重變化最小的路徑，將這些路徑中的點合并變成圖中一個新的點，將原來的邊進行合并產生新的邊，兩個端點都在I1中的邊直接刪除。

（3）將所有I1中的點、所有內部的邊及所有一個端點在I1中的邊及其對應的另一個端點從原來的圖中刪除，對剩下的圖繼續執行（1）和（2），直到不能找到新的點。

（4）記Θ={I1,I2,…,IN}為按照（1）~（3）所找到的N個集合，則可以得到一個收縮的有符號圖G′=(V′,E′,W′)，其中

（5）每次從Θ中的一個集合出發，比如Ij，尋找所有Ij的鄰居，然后按照式（1）來計算它們之間合并與否，對于不能合并的點將其作為一個新的類原型加入Θ中。繼續這個過程直到所有的點都已處理完畢，這樣得到的Θ即為最終的聚類結果。

在算法CCDWP中有幾個地方需要聲明：第一是在第（4）步中得到了N個集合，每個集合都看作是一個類原型，但是要注意的是N并不是人們認為的類個數，因為可能存在多原型的情形。另外在第（5）步中要使用到ILP，其效率比較低，通常只能處理規模為幾百個點的圖。因此如果Ij的鄰居比較多，可能會產生超出ILP處理能力的情況。在實驗中發現，大多數情形下鄰居個數不會超出ILP的處理范圍，而如果超出了ILP的處理范圍的話也很容易處理，只需要設置一個閾值T（比如取T=200），當鄰居數超過T的時候，將這些鄰居與Ij之間的邊的權重從大到小進行排序，ILP只處理前T個鄰居，至于其他點則在以后的優化中再進行處理。這樣做對于最終的聚類結果并不會產生影響，而僅僅是稍微降低了算法的速度。

Fig.1 Original signed graph and three clusters圖1 原始的符號圖和形成的3個類

接下來以一個實例來詳細說明算法的過程。在圖2（a）所示的圖中根據點的正度從高到底排序可以得到3個重要的點4、15和24。因此分布從這3個點出發按照滴水原理尋找正權重變化最小的路徑。分別可以找到如下所示的路徑：即圖2（b）中陰影所示的部分。在這個過程中要注意選中的點所對應的邊一定是權重最大的邊，比如在路徑4→3→2中，路徑在點2即停止而沒有再走下去，因為邊（1,2）對應的邊不是點1所有的邊中權重最大的邊，所以即使最后的結果是1和2同屬一個類，但是為保證算法精度而不會將1納入。這樣就得到3個小的團體，將其作為3個類原型，將這些團體中的點合并成一個點，點的標示分別是4、15、24，將每個團體內部的邊直接取消，外部的邊進行合并，從而得到一個收縮的新的有符號圖，如圖2（c）所示。可以看到新的圖較原來的圖的規模大為縮小。接下來基于新的圖繼續進行處理。對于剩下的點，比如點1，發現其與33、4和15有連接，這些點之間的合并或分割的關系可以表示成式（1）的ILP問題，由于問題規模很小，可以快速進行求解。最終得到如圖2（d）所示的聚類結果。

Fig.2 Procedure of CCDWP圖2CCDWP算法過程

5 實驗與結果

本文在人工數據和真實數據上測試算法CCDWP的有效性，并將CCDWP與Ball-algorithm[18]、Pivotalgorithm[15]、FusionCC[21]算法進行對比測試。

5.1 人工數據實驗

首先設計了一個生成人工有符號圖數據的算法，如算法2所示。

算法2產生有符號圖

輸入：點個數ND，類個數k，類內正邊概率p，類內負邊概率w，類間正邊概率e，類間負邊概率q。

輸出：有符號圖。

隨機產生ND個點，并隨機分配到k個類中。

在實驗中讓產生的邊的權重分布在-5到5之間，然后在同種參數下產生10個隨機數據運行4個算法，記錄每次每個算法所產生的不一致性的數量。實驗結果如圖3所示。圖中縱坐標表示算法結果的不一致性數量D，值越小表示算法越優。橫坐標中的10個點表示10個隨機產生的人工有符號圖。圖3（a）、（b）、（c）和（d）分別是在60個點、100個點、150個點和200個點的設置下產生的隨機圖。Ball-algorithm和Pivot-algorithm這兩個傳統的關聯聚類算法，在人工數據上的實驗結果與先前的研究結果一致：Ballalgorithm的結果要劣于Pivot-algorithm。FusionCC算法也是一種基于收縮的算法，毋庸置疑的是它的效果確實較以前的算法有很大的提高，但對于收縮之后所產生的新圖其仍然是使用傳統的關聯聚類算法，比如Pivot-algorithm，也就是基于將ILP松弛為LP的優化方法。而CCDWP算法則謹慎地將圖更大規模地進行收縮，對于收縮之后的圖采取局部ILP優化的方法求解結果，算法沒有采用降低算法精度的松弛方法，因此算法的效果要更優越，實驗結果完全證明了這一點。在圖3（a）中，圖的規模較小，因此FusionCC和CCDWP算法對于圖的收縮空間較小，同時ILP和LP的效果也相差不大。可以看到，10個隨機圖中有4個FusionCC的不一致性數量小于CCDWP，有4個CCDWP的不一致性數量小于FusionCC，另外兩個則幾乎一致。但是隨著圖的規模的增大，CCDWP算法中圖收縮方法的優越性則越來越明顯，同時局部的ILP比LP也更精確，因此在圖3（b）、（c）和（d）中CCDWP算法都求得了最小的不一致性數量。

Fig.3 Experiments on synthetic data圖3 人工數據實驗結果

5.2 真實數據實驗

本文在真實數據上繼續驗證CCDWP算法的效果。首先在兩個小的有符號網絡上驗證CCDWP算法，這兩個網絡分別是Gahuku-Gama Subtribes（GGS）網絡[23]和 Slovene Parliamentary Party（SPP）網絡[24]。GGS網絡表示的是16個部落之間的友好（正邊）或敵對（負邊）的關系。SPP網絡表示的是斯洛文尼亞國會政黨之間政治理念相似（正邊）或不相似（負邊）。CCDWP算法在這兩個數據集上得到的結果如圖4和圖5所示，以不同的顏色表示不同的聚類。顯而易見本文算法在GGS和SPP兩個數據集上都給出了擁有最小不一致性的結果。

Fig.4 Clustering result of GGS圖4GGS的聚類

Fig.5 Clustering result of SPP圖5 SPP的聚類結果

接下來繼續在更大規模的真實數據上驗證CCDWP算法。這些數據包括Epidermal Growth Factor Receptor pathway network（EGFR）[25]、Macrophage network（Macrophage）[26]、Yeast network（Yeast）[27]、Gene regulatory network of the Escherichia Coli（Ecoli）[28]、voting network of Wikipedia[32]，統計信息如表1所示，其中“#A”表示A的數量，比如#Vertice表示點的數量，E+和E-表示正邊和負邊。原始的Wikipedia數據是有向圖，將其轉化成無向圖并按照下面的公式計算邊的權重：

即如果原來i和j相互信任，則對應的邊的權重為2，如果原來相互不信任，則對應的邊的權重為-2，如果原來一個信任對方但對方不信任他，則權重為0，即沒有邊。

Table 1 Information of 5 real data sets表1 5個真實數據集信息

由于Ball-algorithm和Pivot-algorithm無法運行較大規模的數據，本文只對比測試了FusionCC算法和CCDWP算法，比較這兩個算法給出的結果的不一致性數量，如表2所示，其中“X”表示沒有結果。從真實數據的結果上看，兩個算法的效果與前面人工數據上的效果類似，即當數據的規模不大，邊非常稀疏時，CCDWP算法與FusionCC算法各有所長，算法的效果在一定程度上與數據的結果有關系。在5個數據集中，本文算法在EGFR和Ecoli上取得了更好的效果，在Macrophage和Yeast上兩個算法取得的結果差別很小。而CCDWP算法最大的一個優勢在于能夠處理大規模的數據集。在運行Wikipedia數據集時，由于圖的規模太大，即使在收縮之后的圖上面FusionCC算法仍然難以運行。CCDWP算法則不存在這樣的問題，仍然能夠執行算法過程。

Table 2 Results of FusionCC and CCDWPin 5 real data sets表2FusionCC和CCDWP算法在5個真實數據集上的結果

6 總結

本文提出了一種基于滴水原理的關聯聚類算法CCDWP。CCDWP算法根據滴水原理來搜索有符號圖，將其中最有可能的路徑上的點進行收縮，從而大大減小了數據規模并得到類原型。同時，本文通過巧妙地在局部執行ILP，將可能的點逐步合并到類原型中得到聚類結果。實驗結果表明，本文提出的關聯聚類算法在準確度和效率方面優于許多已有的關聯聚類算法，因此本文算法是可行且高效的。

:

[1]Alpaydin E.Introduction to machine learning[M].Cambridge:MIT Press,2014.

[2]Yu Jian.Generalized categorization axioms[J].CoRR abs/1503.09082,2015.

[3]Xu Rui,Wunsch D C.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks,2005,16(3):645-678.

[4]Wold S,Esbensen K,Geladi P.Principal component analysis[J].Chemometrics&Intelligent Laboratory Systems,1987,2(1/3):37-52.

[5]Jain A K,Duin R P W,Mao Jianchang.Statistical pattern recognition:a review[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(1):4-37.

[6]Hyv?rinen A.Survey on independent component analysis[J].Neural Computing Surveys,1999,2(7):1527-1558.

[7]Young F W,Hamer R M.Multidimensional scaling:history,theory,and applications[M].Hillsdale:Lawrence Erlbaum Associates,1987.

[8]Jain A K,Dubes R C.Algorithms for clustering data[M].Upper Saddle River:Prentice-Hall,1988.

[9]Jain A K,Murty M N,Flynn P J.Data clustering:a review[J].ACM Computing Surveys,1999,31(3):264-323.

[10]Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[11]Jain A K.Data clustering:50 years beyondK-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[12]Luxburg V.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.

[13]Parsons L,Haque E,Liu Huan.Subspace clustering for high dimensional data:a review[J].ACM SIGKDD Explorations Newsletter,2004,6(1):90-105.

[14]Bansal N,Blum A,Chawla S.Correlation clustering[J].Machine Learning,2004,56(1/3):89-113.

[15]Ailon N,Charikar M,Newman A.Aggregating inconsistent information:ranking and clustering[J].Journal of the ACM,2008,55(5):23.

[16]Gionis A,Mannila H,Tsaparas P.Clustering aggregation[J].ACM Transactions on Knowledge Discovery from Data,2007,1(1):4.

[17]Charikar M,Guruswami V,WirthA.Clustering with qualitative information[C]//Proceedings of the 44th Symposium on Foundations of Computer Science,Cambridge,Oct 11-14,2003.Washington:IEEE Computer Society,2003:524-533.

[18]Demaine E E,Immorlica N.Correlation clustering with partial information[C]//LNCS 2764:Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problem and 7th International Workshop on Randomization and Approximation Techniques in Computer Science,Princeton,Aug 24-26,2003:1-13.

[19]Elsner M,Schudy W.Bounding and comparing methods for correlation clustering beyond ILP[C]//Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing,Boulder,2009.Stroudsburg:ACL,2009:19-27.

[20]Mathieu C,Schudy W.Correlation clustering with noisy input[C]//Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms,Austin,Jan 17-19,2010.Philadelphia:SIAM,2010:712-728.

[21]Beier T,Hamprecht F A,Kappes J H.Fusion moves for correlation clustering[C]//Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition,Bos-ton,Jun 7-12,2015.Washington:IEEE Computer Society,2015:3507-3516.

[22]Emanuel D,Fiat A.Correlation clustering—minimizing disagreements on arbitrary weighted graphs[C]//LNCS 2832:Proceedings of the 11th Annual European Symposium on Algorithms,Budapest,Sep 16-19,2003.Berlin,Heidelberg:Springer,2003:208-220.

[23]Read K E.Cultures of the central highlands,new guinea[J].Southwestern Journal ofAnthropology,1954,10(1):1-43.

[24]Doreian P,Mrvar A.A partitioning approach to structural balance[J].Social Networks,1996,18(2):149-168.

[25]Oda K,Matsuoka Y,Funahashi A,et al.A comprehensive pathway map of epidermal growth factor receptor signaling[J].Molecular Systems Biology,2005.

[26]Oda K,Kimura T,Matsuoka Y,et al.Molecular interaction map of a macrophage[J].AfCS Research Reports,2004,2(14):1-12.

[27]Milo R,Shen-Orr S,Itzkovitz S,et al.Network motifs:simple building blocks of complex networks[J].Science,2002,298:824-827.

[28]Salgado H,Gama-Castro S,Peralta-Gil M,et al.RegulonDB(version 5.0):Escherichia coli K-12 transcriptional regulatory network,operon organization,and growth conditions[J].NucleicAcids Research,2006,34(D):394-397.