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

李俊輝

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

[關(guān)鍵詞] 不確定圖； 有向加權(quán)圖； 聚類中心； 層次聚類

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

[中圖分類號]TP311[文獻(xiàn)標(biāo)識碼]A[文章編號]1673 - 0194（2012）24- 0079- 02

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

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

1不確定圖的相關(guān)定義

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

（1） 求出網(wǎng)絡(luò)中所有強(qiáng)連通子圖作為子圖集。

（2） 刪除強(qiáng)連通概率不滿足θ的子圖。

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

（4） 重復(fù)步驟（2）、（3），最終獲得所有聚點(diǎn)中心。

網(wǎng)絡(luò)的聚類中心結(jié)果并不是唯一的，但對于穩(wěn)定的聚類算法，初始聚類中心并不會使聚類結(jié)果差異太大。也就是說，不同的初始聚類節(jié)點(diǎn)在算法條件下具有等價性。

2層次聚類算法

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

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

定義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的節(jié)點(diǎn)v與Hi的凝聚程度為：

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

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

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

定義4：介節(jié)點(diǎn)Ha到Hb之間的出集或入集存在概率：

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

其中，vi∈Ha，vj∈Hb。

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

定義5：介節(jié)點(diǎn)Ha到Hb之間的出集或出集權(quán)重：

其中，vi∈Ha，vj∈Hb。

入集權(quán)重的計算方法和出集權(quán)重的計算方法相同，都是取介節(jié)點(diǎn)中子節(jié)點(diǎn)出集或入集的權(quán)重的平均值。

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

3算法例證

給定有向加全圖G = （V，E，W，Pr），該圖是有15個節(jié)點(diǎn)，42條邊構(gòu)成的。如圖1所示，圖中每條邊上的數(shù)值為（權(quán)重/存在概率）。

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

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

根據(jù)圖2進(jìn)行聚類，可得第三層的節(jié)點(diǎn)集合：v31 = （v21，v24），v32 = （v22，v23，v25）。

第四層節(jié)點(diǎn)集合為：v41 = （v31，v32）。至此，層次聚類算法結(jié)束。

4總結(jié)

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

主要參考文獻(xiàn)

[1] 郭春艷. 基于連接度的圖聚類方法研究[D]. 太原：山西大學(xué)，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ìn)的圖聚類的相異度度量方法[J]. 計算機(jī)應(yīng)用與軟件，2011，28（5）：139-141.

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

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