基于不確定圖的層次聚類算法研究

李俊輝

[摘要] 傳統的基于圖論的層次聚類算法都是對確定圖進行分割，然而實際中，很多網絡的圖結構都是不確定的，邊是以概率存在的。因此，本文提出了基于不確定有向加權圖的層次聚類算法。該算法首先求出不確定圖的可能強連通子圖作為聚類中心，再對剩余節點進行層次聚類。算法主要考慮邊的權重和存在概率。最后以一個例子說明算法的流程。

[關鍵詞] 不確定圖； 有向加權圖； 聚類中心； 層次聚類

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 24. 048

[中圖分類號]TP311[文獻標識碼]A[文章編號]1673 - 0194（2012）24- 0079- 02

圖的聚類算法是從節點開始的，一般的過程是：先是把圖中的每一個節點都初始化成一個子圖，圖中有多少節點，就形成多少子圖，設計一種子圖間相似度或距離計算方法，定義子圖之間的相似度或距離，以及凝聚過程的結束條件[1]。首先計算每個子圖對之間的相似度，合并相似度最高，距離最近的子圖成一個新的子圖，再重新計算所有子圖對之間的相似度或者距離數值，將此過程不斷重復，直到達到過程結束條件，最終得出整個圖的層次結構。聚類結果可以用樹狀圖來表示，這種方式可以清晰看出各種不同需求下得到的劃分結果。

主要的層次聚類算法包括Girvan和Newman[2]提出的基于邊的介數的聚類算法，Newman[3]為解決大規模網絡提出的快速算法，以及CURE算法[4]和Chameleon算法[5]等，近年來，許多研究者改進了傳統的層次聚類算法。例如，王小黎[6]等對相似度度量和時間復雜度進行改進，提出了基于相異度度量的凝聚聚類方法，采用曼哈坦距離作為節點相似性度量，并且證明了該方法的有效性。于慧娟[7]等提出了一種基于社團結構核心區域集的圖聚類方法，社團結構核心區域集是滿足某些限制條件的完全子圖的集合。同時分析了聚類過程，通過實驗表明了該方法能提高聚類的精度。然而目前的基于圖的層次聚類算法大部分都是在改進算法的運算效率以及結果的精度，很少有考慮到圖自身的結構。以往的研究都是基于圖的結構是完全確定的，并沒有考慮圖的結構可能是變化的。諸如一些信息流網絡，由于信息流并不是確定存在的，是以某種概率存在的。本文在此基礎上提出了基于不確定圖的層次聚類算法，并且最后以一個例證來說明算法的流程。該算法的思想是初步提出，算法的精度及有效性將會在以后的工作中呈現。

1不確定圖的相關定義

假設一個不確定有向加權圖為G = （V，E，W，Pr），其中V = {v1，v2，…，vn}是圖中節點的集合，E是網絡中有向邊的集合E = {e11，e21，…，epq}，epq = （vp，vq）表示vp到vq之間相連的邊，m表示網絡中的邊數，其中（vp，vq） ≠ （vq，vp）。W = {w11，w21，…，wpq}表示每條有向邊的權值。Pr = {pr11，pr21，…，prpq}表示邊存在的概率，其中prij∈（0，1]。在有向圖中，（vp，vi）表示vp的出集，（vi，vp）表示vp的入集。

（1） 求出網絡中所有強連通子圖作為子圖集。

（2） 刪除強連通概率不滿足θ的子圖。

（3） 刪除子圖集中重疊交錯的子圖。

（4） 重復步驟（2）、（3），最終獲得所有聚點中心。

網絡的聚類中心結果并不是唯一的，但對于穩定的聚類算法，初始聚類中心并不會使聚類結果差異太大。也就是說，不同的初始聚類節點在算法條件下具有等價性。

2層次聚類算法

聚類中心算法僅用于初始節點的計算，獲得初始聚類中心之后，計算剩余節點到各個聚類中心的聚集程度，將聚集程度最高的節點歸入到相應的聚類中心，逐步歸類，直到循環完所有的剩余節點，形成第二層虛擬節點或介節點。然后再重新計算介節點之間的權重和存在概率，根據聚合度合并介節點，形成圖的第三層，如此循環，直到合并成一個最高層的介節點為止。

在層次聚類之前，需要先定義節點到聚類中心的凝聚程度，以便將節點歸納到凝聚程度最高的聚類中心。以往的研究大部分都將節點間的最小距離作為合并的衡量標準，然而本文中需要考慮邊的權重以及存在概率，因此需要重新定義節點凝聚的衡量標準。

定義3：給定圖G = （V，E，W，Pr），其中V = {vi}，i = 1，…，n，E = {eij}，i ≠ j，eij ≠ eji，W = {wij}，Pr = {prij}以及聚類中心的集合H = {H1，H2，…，Hk}，Hi？奐G作為初始類，G中任意一不屬于H的節點v與Hi的凝聚程度為：

其中，wij，prij分別表示節點vi到vj的邊的權重和存在概率，vj屬于聚類中心Hj。β > 1是節點出集的影響因子。

以上公式表示了節點與各個聚類中心的凝聚程度，這個程度是相對的。coh（vj，Hj）的值越大表示節點與該聚類中心的凝聚程度越高。如果節點到兩個聚類中心的凝聚值是相同的，則隨機選擇一個聚類中心。決定凝聚程度的參數是邊的權重和存在概率，如果兩個節點之間沒有邊，則權重和存在概率都為0。節點的出集和入集對凝聚程度具有不同的影響。例如在信息流網絡中，一個節點調用其他節點的信息比被其他節點調用的耦合度會更高，因此在凝聚值計算中加入了參數β。

通過上述過程，可以將初始節點聚類合并到聚類中心，形成了第二層介節點，介節點包含該類所有元節點的資源和功能。然而在第二層介節點中，需要重新計算介節點之間的權重和存在概率，以便形成第三層節點。計算方法如下：

定義4：介節點Ha到Hb之間的出集或入集存在概率：

pr（Ha，Hb） = max（pr（vi，vj））

其中，vi∈Ha，vj∈Hb。

由上式可知，出集或入集的計算是選取兩個介節點中的子節點最大存在概率作為介節點的相鄰存在概率。

定義5：介節點Ha到Hb之間的出集或出集權重：

其中，vi∈Ha，vj∈Hb。

入集權重的計算方法和出集權重的計算方法相同，都是取介節點中子節點出集或入集的權重的平均值。

權重和存在概率重新計算之后，再根據凝聚度的公式，合并凝聚度較高的介節點。兩個介節點之間最多只有一個出度和一個入度，形成一個2階的完全圖，這種情況說明兩個介節點的交互較多，合并成一個更高層級的介節點的可能性較大。這種計算方法不容易產生碎片和邊緣類，比較符合信息系統的現實意義。選擇凝聚度大的類逐漸合并，知道滿足聚類數為止，得到最終的聚類結果。

3算法例證

給定有向加全圖G = （V，E，W，Pr），該圖是有15個節點，42條邊構成的。如圖1所示，圖中每條邊上的數值為（權重/存在概率）。

根據層次聚類算法的步驟，首選求出圖中的聚類中心，設置聚類中心每條邊的存在概率閾值為0.5。圖1中有兩個強連通圖分別是G1 = （v2，v4，v5），G2 = （v8，v12，v13）。然而在G1中，Pr（e45） < 0.5和Pr（e54） < 0.5不滿足聚類中心的要求。因此，圖中的聚類中心為H1 = （v8，v12，v13）。

獲得聚類中心后，遍歷剩余的所有節點。對某個節點而言，如果該節點的所有相鄰節點中，coh（vj，H1）的值最大，則將該節點并入H1中，否則并入其他節點。設置β = 1.2，計算每個節點的凝聚值，直到每個節點都與其他節點合并。有此可得，第二層的節點集合為v21 = （v1，v2，v4），v22 = （v3，v9），v23 = （v5，v11，v14，H1），v24 = （v6，v7，v10），v25 = （v15，v16）

根據圖2進行聚類，可得第三層的節點集合：v31 = （v21，v24），v32 = （v22，v23，v25）。

第四層節點集合為：v41 = （v31，v32）。至此，層次聚類算法結束。

4總結

傳統的圖聚類算法的研究都是基于結構確定圖，然而，現實生活中，很多圖的結構都是不確定的，邊以某個概率存在。因此，本文提出了基于不確定圖的層次聚類算法，該算法考慮邊的存在概率，將邊權重較大，且存在概率最高的節點聚合到一起。由于該算法初步提出，有很多方面未作研究，比如該如何驗證聚類的結果等。下一步工作便是考慮算法的速率及精確度等。

主要參考文獻

[1] 郭春艷. 基于連接度的圖聚類方法研究[D]. 太原：山西大學，2008.

[2] M Girvan，ME J Newman. Community Structure in Social an Biological Networks[C] // Proceedings of the National Academy of Sciences of the United States of America， 2002.

[3] M E J Newman. Fast Algorithm for Detecting Community Structure in Networks[J]. Phys Rev E，2004，69（6）：066-133.

[4] Sudipto Guha， Rajeev Rastogi，Kyuseok Shim.Cure：An efficient Clustering Algorithm for Large Databases [C] // Proceedings of the Fourth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，1998.

[5] G Karypis，E H Han，VKumar.Chameleon： A Hierarchical Clustering Algorithm Using Dynamic Modeling[J]. IEEE Transaction of Computer，1999，32（8）：68-75.

[6] 王小黎. 一種改進的圖聚類的相異度度量方法[J]. 計算機應用與軟件，2011，28（5）：139-141.

[7] 于慧娟，崔軍，毋曉志，等. 一種改進的凝聚圖聚類方法[J]. 山西煤炭管理干部學院學報，2010（3）.

[8] 袁野，王國仁. 面向不確定圖的概率可達查詢[J]. 計算機學報，2010，33（8）.