基于目標(biāo)函數(shù)優(yōu)化的無向加權(quán)圖粗糙模糊聚類算法

何文倩, 劉士虎,宋 敏, 楊昔陽(yáng)

(1.云南民族大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,云南 昆明 650504;2.泉州師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福建 泉州 362000)

隨著數(shù)據(jù)庫(kù)技術(shù)的快速發(fā)展和數(shù)據(jù)庫(kù)管理系統(tǒng)的廣泛應(yīng)用，積累數(shù)據(jù)和掌控技術(shù)的用戶越來越多[1].數(shù)據(jù)爆炸的背后隱藏著重要信息，人們希望通過更高層次的分析來更好地利用數(shù)據(jù)[2].圖是一種重要的數(shù)據(jù)結(jié)構(gòu)，可用于描述復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，如社交網(wǎng)絡(luò)[2]、疫情傳播網(wǎng)絡(luò)[3]，傳感器網(wǎng)絡(luò)和蛋白質(zhì)網(wǎng)絡(luò)[4]等.圖數(shù)據(jù)聚類可以幫助檢測(cè)出含有重要信息的類結(jié)構(gòu)，此外，還可以幫助研究者更好地理解圖數(shù)據(jù)的特征和功能[5].

圖數(shù)據(jù)聚類是根據(jù)圖的拓?fù)湫畔⒑蛯傩孕畔⒁粋€(gè)大圖劃分為若干個(gè)子圖的過程，使得同子圖內(nèi)的頂點(diǎn)連接緊密而不同子圖內(nèi)的頂點(diǎn)連接稀疏，并且相似頂點(diǎn)應(yīng)劃分到相同子圖內(nèi)，不相似頂點(diǎn)應(yīng)劃分到不同子圖內(nèi)[4-5].研究者已經(jīng)提出許多相關(guān)算法，并成功地應(yīng)用于各種圖數(shù)據(jù)中.比如，基于結(jié)構(gòu)相似性的圖數(shù)據(jù)聚類算法利用結(jié)構(gòu)相似性來發(fā)現(xiàn)圖數(shù)據(jù)中無重疊的子圖類[5].Walktrap算法利用隨機(jī)游走技術(shù)檢測(cè)復(fù)雜圖數(shù)據(jù)中的類[6].此外一些算法還使用歸一化割方法、最小割方法和最大流最小割方法來進(jìn)行圖數(shù)據(jù)聚類反演.這些算法均基于邊連接權(quán)值對(duì)圖數(shù)據(jù)進(jìn)行聚類，但它們需要從所有頂點(diǎn)中選擇權(quán)值最小的邊，這是一個(gè)較難的問題.還存在一些算法，要么需要預(yù)先輸入少量信息，要么只考慮圖數(shù)據(jù)的拓?fù)湫畔⒑蛯傩孕畔⒅械囊粋€(gè).針對(duì)這些問題，Tian等[7]提出了一種基于屬性信息的關(guān)系對(duì)圖數(shù)據(jù)進(jìn)行聚類的算法，它將同一維度的屬性分組到同一個(gè)類中.不幸的是，該算法忽略了聚類內(nèi)的拓?fù)浣Y(jié)構(gòu).Zhou等[8]提出了一種圖數(shù)據(jù)中統(tǒng)一的距離度量方法，該方法通過在原始圖中添加帶屬性的頂點(diǎn)來生成屬性增廣圖，然后使用隨機(jī)游走方法計(jì)算頂點(diǎn)之間的距離.該算法得到的屬性增廣圖中頂點(diǎn)數(shù)大于原始圖中的頂點(diǎn)數(shù)，但是算法運(yùn)行時(shí)間不盡人意[9]，并且當(dāng)屬性較多時(shí)，算法的時(shí)間復(fù)雜度會(huì)很高[10].Javed等[11]提出了一種綜合考慮拓?fù)浜蛯傩缘膱D數(shù)據(jù)聚類算法，這種算法被廣泛應(yīng)用并且是一種基于描述驅(qū)動(dòng)思想的聚類方法，目標(biāo)是簡(jiǎn)單地聚類社交圖數(shù)據(jù)，其中每個(gè)頂點(diǎn)都用附加信息進(jìn)行注釋.

目前，眾多模糊聚類算法也已被提出來處理圖數(shù)據(jù)聚類問題.模糊C均值聚類是最常用的模糊聚類技術(shù)[12]，由于模糊C均值在某些方面的不足，許多改進(jìn)算法也已經(jīng)被提出.在文獻(xiàn)[13]中，Naderipour引入了一種基于鄰近性的兩階段圖數(shù)據(jù)模糊聚類方法.隨后，一種基于抑制性因子的模糊聚類算法[14]被提出，在保證聚類效果的前提下，利用抑制因子提高算法收斂速度.此外，為了處理模糊C均值聚類算法的噪聲和較低收斂速度問題，文獻(xiàn)[14]提出了一種基于粗糙集思想的改進(jìn)聚類算法版本，由此可知粗糙集思想已經(jīng)不斷被廣泛應(yīng)用于圖數(shù)據(jù)的模糊聚類中[15].在目前的研究中，基于圖數(shù)據(jù)結(jié)構(gòu)信息和屬性信息的相似性度量來聚類是一項(xiàng)基礎(chǔ)任務(wù)[16].圖數(shù)據(jù)的多樣性，如其形狀、大小、密度以及噪聲的存在，這些都使得對(duì)圖數(shù)據(jù)的聚類更加困難[17].因此，研究這樣1種全面的聚類方法具有重要意義.在面對(duì)任何圖數(shù)據(jù)時(shí)，如果直接對(duì)圖數(shù)據(jù)進(jìn)行處理以確定聚類方向，則必須將圖數(shù)據(jù)中所有信息都考慮在內(nèi),以達(dá)到類內(nèi)高相似性和類間低相似性的理想目標(biāo)[18].

通過對(duì)以上問題進(jìn)行分析，本文在前人研究基礎(chǔ)上，提出了一種基于目標(biāo)函數(shù)優(yōu)化的無向加權(quán)圖粗糙模糊聚類算法.論文基于頂點(diǎn)的綜合結(jié)構(gòu)相似性和屬性相似性建立無向加權(quán)圖數(shù)據(jù)的聚類算法模型.引入粗糙集的上下近似集思想分別設(shè)計(jì)了類的上近似集和下近似集的模糊中心，并以此建立目標(biāo)函數(shù)迭代優(yōu)化機(jī)制，使得算法能夠處理一定的噪聲問題，拓寬算法的應(yīng)用范圍，還可以通過選擇實(shí)驗(yàn)有效性指標(biāo)的最小值，確定聚類的最佳個(gè)數(shù).

1 預(yù)備知識(shí)

為了行文簡(jiǎn)潔及后文敘述的需要，這里簡(jiǎn)單闡述與文中相關(guān)的一些基本概念，如無向加權(quán)圖數(shù)據(jù)、粗糙集和模糊C均值聚類算法.更詳細(xì)的描述參考文獻(xiàn)[9,12,15].

一般地，一個(gè)無向加權(quán)圖數(shù)據(jù)G可以表示為一個(gè)三元組G=(X,E,W)，其中非空有限集合X={x1,x2,…,xn}表示所有頂點(diǎn)的集合.如果每個(gè)頂點(diǎn)被m個(gè)屬性所刻畫，那么對(duì)應(yīng)地可表示為xi=(xi1,xi2,…,xim).從矩陣的角度而言，此時(shí)X可以采用如下表示

(1)

在無向加權(quán)圖數(shù)據(jù)中，E={(xi,xj)|xi,xj∈X}表示邊集合，其中(xi,xj)表示圖數(shù)據(jù)中任意2個(gè)頂點(diǎn)xi,xj之間的邊.W={wij|i,j=1,2,…,n}表示圖數(shù)據(jù)邊的權(quán)重集合，其中wij為任意兩個(gè)頂點(diǎn)xi,xj之間邊的權(quán)重，如果邊(xi,xj)?E，那么wij=0.

粗糙集作為一種處理不精確性和不確定性的軟計(jì)算工具，其數(shù)學(xué)描述可以用一對(duì)所謂的下近似集和上近似集來表示.給定一個(gè)知識(shí)庫(kù)K=(U,R)，其中U表示論域，R表示U上的等價(jià)關(guān)系.對(duì)于任意有限集合X?U，{Xi|i=1,2,…,c}是由模糊聚類過程中產(chǎn)生的聚類結(jié)果構(gòu)成的劃分，所有類中心的集合為{vi|i=1,2,…,c}，且類中心vi與類Xi是一一對(duì)應(yīng)的，則類Xi關(guān)于R的下近似集、上近似集和邊界域?yàn)?/p>

(2)

X的每個(gè)類Xi關(guān)于等價(jià)關(guān)系R的近似分類精度aR和粗糙度rR為

(3)

一個(gè)集合的不精確性是由其邊界域的存在而引起的，并且邊界域越大集合的精確性就越低.

進(jìn)一步，類劃分{Xi|i=1,2,…,c}關(guān)于R的近似分類精度AR和質(zhì)量QR為

(4)

近似分類精度描述的是當(dāng)使用等價(jià)關(guān)系R聚類時(shí)，所有可能的類中被正確聚類的數(shù)據(jù)所占的百分比，即所有類的下近似集數(shù)據(jù)在上近似集中的百分比.分類質(zhì)量表示的是應(yīng)用R能被確切地分于{Xi|i=1,2,…,c}中類的數(shù)據(jù)在論域中所占百分比，即所有類的下近似集中數(shù)據(jù)占論域的百分比，由此分析確定在論文中將近似分類精度和分類質(zhì)量分別作為下近似集和邊界域的計(jì)算權(quán)重.

模糊C均值聚類算法是數(shù)據(jù)分析的有用工具，該算法將聚類問題轉(zhuǎn)化成帶約束的目標(biāo)函數(shù)最優(yōu)化問題，因此可借助數(shù)學(xué)領(lǐng)域中的非線性規(guī)劃理論進(jìn)行求解.此算法的目標(biāo)函數(shù)為

(5)

其約束條件為

(6)

公式(5)所描述目標(biāo)函數(shù)的優(yōu)化過程具體是通過更新以下形式的uij和vi

(7)

(8)

其中uij表示xj關(guān)于第i個(gè)類的模糊隸屬度.m表示模糊因子，用于調(diào)整模糊隸屬矩陣的模糊程度.‖xj-vi‖2表示xj與第i個(gè)類中心vi之間的歐氏距離.

2 基于目標(biāo)函數(shù)優(yōu)化的粗糙模糊聚類算法

針對(duì)無向加權(quán)圖數(shù)據(jù)聚類問題，本文從拓?fù)湫畔⒑蛯傩孕畔⒔嵌瘸霭l(fā)，利用粗糙集思想構(gòu)建了基于目標(biāo)函數(shù)優(yōu)化的模糊聚類算法.該算法從以下2個(gè)步驟對(duì)圖數(shù)據(jù)進(jìn)行相似性度量和模糊聚類.首先基于共享鄰居的結(jié)構(gòu)相似性和邊權(quán)重貢獻(xiàn)構(gòu)造了無向加權(quán)圖數(shù)據(jù)中頂點(diǎn)的綜合結(jié)構(gòu)相似性，通過論域上的等價(jià)關(guān)系R設(shè)計(jì)出頂點(diǎn)的屬性相似性度量方法.其次，通過引入粗糙集思想分別提出模糊類的上近似集和下近似集的類中心表示，并以此為基礎(chǔ)建立聚類算法的隸屬函數(shù)和目標(biāo)函數(shù)優(yōu)化機(jī)制.算法執(zhí)行過程是基于目標(biāo)函數(shù)優(yōu)化機(jī)制對(duì)無向加權(quán)圖數(shù)據(jù)進(jìn)行模糊聚類.

2.1 權(quán)重歸一化處理

(9)

2.2 綜合結(jié)構(gòu)相似性度量

在一個(gè)無向加權(quán)圖數(shù)據(jù)G=(X,E,W)中，將與頂點(diǎn)xi之間直接由邊連接的頂點(diǎn)稱為xi的一階鄰居，由所有一階鄰居組成的集合叫作xi的結(jié)構(gòu)鄰域，并表示為N[xi]，其集合表達(dá)形式為N[xi]={xj∈X|(xi,xj)∈E}.此外，頂點(diǎn)xi的度數(shù)記作d[xi]=|N[xi]|，即為一階鄰域中元素的個(gè)數(shù).

對(duì)于無向加權(quán)圖數(shù)據(jù)G=(X,E,W)中任意2個(gè)頂點(diǎn)xi和xj，定義其結(jié)構(gòu)相似性為2個(gè)頂點(diǎn)的結(jié)構(gòu)鄰域N[xi]和N[xj]中共同頂點(diǎn)的數(shù)量與它們度數(shù)的幾何平均數(shù)的比值，即

(10)

對(duì)于任意2個(gè)頂點(diǎn)，如果其結(jié)構(gòu)鄰域中的共同頂點(diǎn)越多，則它們之間的結(jié)構(gòu)相似性就越大.以圖1中的頂點(diǎn)x1和x2為例不難發(fā)現(xiàn)，這2個(gè)頂點(diǎn)的共同鄰居為x3、x4、x5和x7，即共同鄰居的個(gè)數(shù)為4，由此可計(jì)算得2個(gè)頂點(diǎn)的度數(shù)分別為d[x1]=5，d[x2]=5，進(jìn)而可根據(jù)公式(10)計(jì)算頂點(diǎn)x1和x2的結(jié)構(gòu)相似性為S12=0.8.

圖1 無向加權(quán)圖數(shù)據(jù)

一般地，對(duì)于大多數(shù)真實(shí)無向加權(quán)圖數(shù)據(jù)來說，除了具有重要價(jià)值的拓?fù)浜蛯傩孕畔⒈豢紤]之外，各個(gè)邊上帶有的權(quán)重也不容忽略.權(quán)重是對(duì)任意2個(gè)頂點(diǎn)之間的關(guān)聯(lián)性重要程度的定量分配，對(duì)于圖數(shù)據(jù)的聚類仍然具有較大參考價(jià)值[19].基于以上對(duì)無向加權(quán)圖數(shù)據(jù)中頂點(diǎn)的結(jié)構(gòu)相似性討論，為了發(fā)現(xiàn)潛在的具有高相似性的類，下面綜合考慮頂點(diǎn)的結(jié)構(gòu)相似性和經(jīng)過歸一化處理后的邊權(quán)重信息，統(tǒng)一計(jì)算兩者對(duì)無向加權(quán)圖數(shù)據(jù)聚類的貢獻(xiàn).

給定G=(X,E,W)，為了有效均衡頂點(diǎn)的結(jié)構(gòu)相似性和邊權(quán)重的貢獻(xiàn)，引入一個(gè)均衡參數(shù)α∈(0,1)，在實(shí)驗(yàn)中取α=0.6.則任意2個(gè)頂點(diǎn)xi和xj之間基于結(jié)構(gòu)相似性和邊權(quán)重的綜合結(jié)構(gòu)相似性為

(11)

算法通過綜合考慮無向加權(quán)圖數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)和邊的權(quán)重，使類內(nèi)頂點(diǎn)連接緊密的同時(shí)使具有較大權(quán)重的頂點(diǎn)被劃分到一類，而類間頂點(diǎn)之間連接稀疏.這樣，既保證具有較大權(quán)重邊連接的頂點(diǎn)不被分開，同時(shí)使類內(nèi)頂點(diǎn)間連接緊密.

2.3 目標(biāo)函數(shù)優(yōu)化機(jī)制建立

在傳統(tǒng)的數(shù)據(jù)聚類中，頂點(diǎn)只能屬于某個(gè)特定的類.在模糊聚類中，頂點(diǎn)可以按照一定的隸屬程度屬于多個(gè)類.模糊聚類所獲得的聚類結(jié)果具有不確定性和模糊化，這種模糊程度由隸屬度函數(shù)來決定.

給定圖數(shù)據(jù)G=(X,E,W)，其中頂點(diǎn)集為X={xj|j=1,2,…,n}.假設(shè)X中頂點(diǎn)被劃分到c個(gè)類，c個(gè)類中心為{vi|i=1,2,…,c}，其類中心與類一一對(duì)應(yīng).則定義頂點(diǎn)xj關(guān)于第i個(gè)類的隸屬度函數(shù)uij為

(12)

基于模糊C均值聚類的類中心更新公式(8)，對(duì)于任意X?U，{Xi|i=1,2,…,c}是模糊聚類結(jié)果構(gòu)成的一個(gè)劃分，類中心集合為{vi|i=1,2,…,c}，且每一個(gè)類中心vi對(duì)應(yīng)一個(gè)類Xi.定義無向加權(quán)圖數(shù)據(jù)每個(gè)類的類中心計(jì)算方式為

(13)

由于頂點(diǎn)隸屬度的存在導(dǎo)致每個(gè)類表示缺乏確定性，因此引入粗糙集思想使得類可用其一對(duì)下近似集和上近似集來表示，針對(duì)上近似集和下近似集自然會(huì)產(chǎn)生一個(gè)表示中心.接下來分別建立類的上下近似集的模糊中心表示.給定知識(shí)庫(kù)K=(U,R)，對(duì)于任意X?U，對(duì)應(yīng)為G=(X,E,W)中的頂點(diǎn)集X={xj|j=1,2,…,n}，{Xi|i=1,2,…,c}是由模糊聚類過程中產(chǎn)生的聚類結(jié)果構(gòu)成的劃分.建立每個(gè)劃分類的下近似集的模糊中心表示vl和上近似集的模糊中心表示vu.

(14)

其中，vl為劃分類Xi下近似集的模糊中心，vu是Xi上近似集的模糊中心.aR和rR為上面已定義的近似精度和粗糙度，AR和QR為近似分類精度和質(zhì)量.在這里aR代表下近似集的權(quán)重并且rR代表上近似集的權(quán)重，且有aR+rR=1,aR≥rR.類劃分{Xi|i=1,2,…,c}關(guān)于R的屬性相似性為

(15)

在模糊聚類中，當(dāng)隸屬度約束條件放松時(shí)，頂點(diǎn)的隸屬度可能大于1.那么每個(gè)類中頂點(diǎn)的隸屬度就大不相同.換句話說，一些頂點(diǎn)對(duì)于每個(gè)類可能具有較高隸屬度，而其它頂點(diǎn)對(duì)于每個(gè)類可能具有較低隸屬度.如果頂點(diǎn)在一個(gè)類中具有較高隸屬度，則最終類可能只包含這一個(gè)頂點(diǎn)[14]，也就是說，噪聲會(huì)被聚到單個(gè)類，會(huì)導(dǎo)致聚類結(jié)果不理想.在我們的聚類算法設(shè)計(jì)中，給出一個(gè)可在uij基礎(chǔ)上快速提高的隸屬度函數(shù)

(16)

基于對(duì)類上下近似集中心表示和隸屬度函數(shù)的論述，對(duì)給定的圖數(shù)據(jù)G=(X,E,W)，本文嘗試構(gòu)建基于目標(biāo)函數(shù)的模糊聚類方法.其模型的目標(biāo)函數(shù)為

(17)

其中，d(vl,vu,xj)表示圖數(shù)據(jù)中基于類的上近似集和下近似集的模糊中心與所有頂點(diǎn)之間的距離度量，其基于粗糙集思想的數(shù)學(xué)定義為

(18)

在傳統(tǒng)模糊聚類算法中，用一般歐式距離作為頂點(diǎn)之間的相似性或距離度量，且每個(gè)類皆用單個(gè)類中心來表示.在本文算法中，首先通過引入聚類基于上下近似集的粗糙表示，產(chǎn)生關(guān)于上下近似集的模糊中心表示，然后針對(duì)這3種模糊中心的表示提出一種特殊的距離度量方式，確定3種模糊類中心vl、vu和vi.

3 算法

算法通過引入粗糙集中上下近似集的思想，分別設(shè)計(jì)了相應(yīng)的類上下近似集的模糊中心表示.針對(duì)無向加權(quán)圖數(shù)據(jù)，算法綜合考慮其拓?fù)浣Y(jié)構(gòu)信息和邊權(quán)重得到一種綜合結(jié)構(gòu)相似性度量方法.在聚類過程中，以初始化的模糊隸屬度矩陣出發(fā)，算法通過不斷對(duì)類中心和模糊隸屬度矩陣進(jìn)行更新迭代，直到目標(biāo)函數(shù)達(dá)到穩(wěn)定值或滿足停止閾值，此時(shí)便可獲得最終的模糊聚類結(jié)果.參考算法最終輸出的模糊隸屬度矩陣，對(duì)頂點(diǎn)依據(jù)每個(gè)類的隸屬度進(jìn)行劃分.具體步驟可參考算法 1.

眾所周知，模糊聚類算法對(duì)初始化聚類中心較敏感，往往會(huì)得到顯著誤差.我們?cè)谒惴ㄖ型ㄟ^尋找最小指標(biāo)值對(duì)應(yīng)的類數(shù)來確定最優(yōu)聚類數(shù)，以確定類中心.

算法1基于目標(biāo)函數(shù)優(yōu)化的無向加權(quán)圖粗糙模糊聚類算法

輸入： 無向加權(quán)圖數(shù)據(jù)G(X,E,W).

輸出： 隸屬度矩陣U和類中心V.

過程：

第一步 根據(jù)公式(9)歸一化處理圖數(shù)據(jù)中邊權(quán)重.

第二步 初始化算法相關(guān)參數(shù)：類數(shù)c、m=2、ε=0.001、T=0、α=0.6、U0.

第三步 根據(jù)公式(11)計(jì)算頂點(diǎn)的綜合結(jié)構(gòu)相似性.

第四步 根據(jù)公式(15)計(jì)算頂點(diǎn)的屬性相似性.

第五步 根據(jù)公式(13)和(14)分別計(jì)算類中心vi，上近似集模糊中心vu和下近似集模糊中心vl.

第七步 如果|J(T+1)-J(T)|≤ε，則轉(zhuǎn)到步驟7，否則轉(zhuǎn)到步驟5.

第八步 根據(jù)步驟4和步驟5得到U和V，計(jì)算算法各項(xiàng)指標(biāo)值.

第九步 求有效性指標(biāo)的最小值，選擇對(duì)應(yīng)的c作為最佳聚類數(shù).

4 實(shí)驗(yàn)分析

針對(duì)無向加權(quán)圖數(shù)據(jù)，本文結(jié)合了基于頂點(diǎn)拓?fù)湫畔⑴c邊權(quán)重貢獻(xiàn)的綜合結(jié)構(gòu)相似性和基于等價(jià)關(guān)系R的屬性相似性度量，提出一種基于目標(biāo)函數(shù)優(yōu)化的粗糙模糊聚類算法，并且算法通過隸屬度函數(shù)和類中心的不斷更新迭代來記錄目標(biāo)函數(shù)的變化趨勢(shì).

為了測(cè)試算法的聚類性能，實(shí)驗(yàn)使用了UCI數(shù)據(jù)庫(kù)中的真實(shí)數(shù)據(jù)集，將我們的聚類算法與4種經(jīng)典聚類算法進(jìn)行對(duì)比.實(shí)驗(yàn)環(huán)境均為Win10 64位操作系統(tǒng)、Matlab軟件、8G內(nèi)存、Intel(R) Core(TM) i5-10210U CPU.

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本實(shí)驗(yàn)將論文提出的聚類算法與其它4種經(jīng)典的聚類算法分別在4種無向加權(quán)圖數(shù)據(jù)集進(jìn)行比較分析，對(duì)比算法分別為近鄰傳播算法(AP)、近似模糊C均值聚類(AFCM)、基于核的改進(jìn)模糊C均值聚類(KFCM)和模糊C均值聚類(FCM).表1列出圖數(shù)據(jù)信息并且已進(jìn)行了標(biāo)準(zhǔn)化處理.

表1 數(shù)據(jù)集

4.2 評(píng)價(jià)指標(biāo)

為驗(yàn)證論文所提出算法模型的有效性，實(shí)驗(yàn)共采用了10種常見聚類有效性指標(biāo)，除了表2已列出的5種指標(biāo)外還有聚類準(zhǔn)確率、召回率、標(biāo)準(zhǔn)化互信息、聚類模塊度和運(yùn)行時(shí)間效率.

聚類有效性指標(biāo)需要突出反映類內(nèi)緊密度和類之間的分離度[8].劃分系數(shù)(PC)[3]和劃分熵(CE)[3]是聚類模糊性的一種度量指標(biāo).PC值越大，CE值越小，表明聚類越明顯，算法效果越好.劃分指數(shù)(SC)[8]是類內(nèi)緊致性與類間分離度的比值，Davies-Bouldin指數(shù)(DBI)[16]和分離指數(shù)(S)[16]是類間分離度與類內(nèi)緊致性的比值.因此，SC值越大表明算法的聚類性能越好；對(duì)于DBI和S來說，情況正好相反.表2為5個(gè)聚類有效性指標(biāo)的簡(jiǎn)要描述.

表2 有效性指標(biāo)描述

此外，準(zhǔn)確率(Acc)和召回率(Re)的具體公式為

(19)

(20)

其中，ai表示正確劃分到類bi的頂點(diǎn)數(shù)，bi表示本該屬于類bi但被錯(cuò)誤劃分到其它類的頂點(diǎn)數(shù).

標(biāo)準(zhǔn)化互信息(NMI)的計(jì)算方式為

(21)

其中，I(X,Y)為劃分類X和Y之間的互信息，H(X)是X的熵，具有如下的表示形式

(22)

其中，H(Y)的計(jì)算類似于H(X)，p(i)表示從X中隨機(jī)選取的頂點(diǎn)在類Xi的概率.

GAO提出評(píng)價(jià)重疊聚類結(jié)果質(zhì)量的模塊度函數(shù)(Q)[5]

(23)

其中，kj表示頂點(diǎn)xj的度數(shù)，Aij表示圖數(shù)據(jù)的鄰接矩陣，m表示圖中邊個(gè)數(shù).

4.3 實(shí)驗(yàn)結(jié)果

本次實(shí)驗(yàn)通過不斷增加聚類數(shù)和迭代嘗試，記錄實(shí)驗(yàn)所得數(shù)據(jù)對(duì)比結(jié)果.下面將5種算法分別在4個(gè)圖數(shù)據(jù)上的各類指標(biāo)對(duì)比結(jié)果進(jìn)行展示和分析.

圖2展示了所有對(duì)比算法分別在4個(gè)數(shù)據(jù)集上的收斂性曲線及對(duì)比結(jié)果.從整體可以看出，所提出的算法(紅色曲線表示)在4個(gè)圖數(shù)據(jù)集上都表現(xiàn)出明顯的收斂性.隨著迭代次數(shù)的不斷增加，對(duì)應(yīng)的目標(biāo)函數(shù)值都逐漸減小并最終趨于一個(gè)穩(wěn)定的常數(shù)值，且收斂于穩(wěn)定狀態(tài)經(jīng)過了較少的迭代次數(shù)，這也表明了算法花費(fèi)較少的運(yùn)行時(shí)間.從單個(gè)圖數(shù)據(jù)集上來看，論文提出算法的目標(biāo)函數(shù)趨于穩(wěn)定過程中的速度基本快于其它對(duì)比算法，但因受到不同數(shù)據(jù)集本身差異的影響，算法在個(gè)別迭代次數(shù)時(shí)的收斂性出現(xiàn)輕微波動(dòng)，表現(xiàn)為曲線下降的不光滑現(xiàn)象.總體來說，依然可表明我們算法的良好收斂性且較優(yōu)于其它算法.

圖2 算法的收斂性對(duì)比

圖3分別給出了4個(gè)圖數(shù)據(jù)上5種算法聚類結(jié)果的指標(biāo)(僅表2所示指標(biāo))對(duì)比結(jié)果，其中5種顏色分別代表5種指標(biāo)，橫坐標(biāo)表示5種算法.從圖3整體看出，文中算法聚類結(jié)果的PC、SC 值較其它算法大，同時(shí)CE、S、DBI值較其它算法更小，說明算法整體上具有更明顯的正向算法優(yōu)勢(shì).依據(jù)指標(biāo)評(píng)價(jià)標(biāo)準(zhǔn)，論文提出算法在Cumulative networks數(shù)據(jù)集上具有更好表現(xiàn).

表5 算法NMI %

從單個(gè)圖數(shù)據(jù)來看，文中的算法在Cumulative networks數(shù)據(jù)集(圖3(a))上相對(duì)于其它圖數(shù)據(jù)集獲得較小的S值為0.21、 最大的PC值為1.82和最大的SC值為1.51.已知SC是類內(nèi)緊致性與類間分離度的比值，PC是聚類模糊性的一種度量指標(biāo)，S是類間分離度與類內(nèi)緊致性的比值.因此，SC和PC值最大意味著算法聚類性能最好，S值越小聚類越明顯，算法效果越好.從3個(gè)指標(biāo)值對(duì)比可知，文中算法在Cumulative networks數(shù)據(jù)集上的聚類效率都明顯優(yōu)于在其它圖數(shù)據(jù)上.

在Les Miserables數(shù)據(jù)集(圖3(b))上，論文所提出算法的最終聚類結(jié)果獲得了最低的DBI值為0.03、最小的CE值0.2.已知CE是聚類模糊性的一種重要度量指標(biāo)，DBI是類間分離度與類內(nèi)緊致性的比值.故由最小的CE和DBI值可以說明所得聚類劃分結(jié)果越明顯，類的模糊性就越低，類間的分離度越大，類內(nèi)頂點(diǎn)間更緊致，表明算法聚類效果越好.

圖3 單個(gè)數(shù)據(jù)集上的PC、CE、SC、S、DBI指標(biāo)對(duì)比

在Netscience數(shù)據(jù)集(圖3(c))上本文算法較其它圖數(shù)據(jù)獲得最小CE值為0.2，獲得S值為0.32且明顯大于算法在Cumulative networks數(shù)據(jù)集上的結(jié)果.S是類間分離度與類內(nèi)緊致性的比值.因此，S值較小表現(xiàn)出較強(qiáng)聚類性能且聚類越明顯.所以僅在Netscience數(shù)據(jù)集上，算法的S指標(biāo)值結(jié)果不是理想的較小或最小值，說明算法在此數(shù)據(jù)集上基于S指標(biāo)表現(xiàn)不明顯，而基于CE指標(biāo)的結(jié)果較好.除此之外，指標(biāo)PC、SC和DBI在此數(shù)據(jù)集上的數(shù)值變化處于中等偏上水平，總體可認(rèn)為算法在Netscience數(shù)據(jù)集上基于指標(biāo)的聚類效果略優(yōu)于其它圖數(shù)據(jù)，但是相差不大.

在Neural network數(shù)據(jù)集(圖3(d))上，本文算法獲得CE值為0.21，較Les Miserables和數(shù)據(jù)集Netscience僅大0.01.算法獲得了最小的S值為0.13，這與Les Miserables數(shù)據(jù)集上獲得的指標(biāo)值之間的最大差值為0.19.已知S是類間分離度與類內(nèi)緊致性的一個(gè)平衡指標(biāo).因此，最小的S值意味著算法聚類結(jié)果具有較高類間分離度和類內(nèi)緊致性.基于算法效率而言，這體現(xiàn)出較其它算法最強(qiáng)的聚類性能和最佳的聚類結(jié)果.另外，算法的PC和DBI在此圖數(shù)據(jù)集上的表現(xiàn)不具有很明顯的優(yōu)勢(shì).各項(xiàng)聚類效率指標(biāo)值的對(duì)比分析表明我們的算法在單個(gè)Neural network數(shù)據(jù)集相對(duì)于其它算法和圖數(shù)據(jù)表現(xiàn)穩(wěn)定，具有較好聚類性能.

為了更直觀地比較算法的優(yōu)劣，圖4分別展示了各個(gè)算法分別在4個(gè)圖數(shù)據(jù)上聚類結(jié)果的Acc、Re、NMI和Q對(duì)比情況.相應(yīng)地，表3～5分別給出Acc、Re和NMI的具體數(shù)值.

圖4 算法Acc、Re、NMI、Q對(duì)比

表3 算法Acc %

從圖4(a)和表3來看，本文算法獲得最高的Acc值，比其它算法都具有明顯地提高.但是AP算法在4個(gè)數(shù)據(jù)集上均獲得最低Acc值，這是由于當(dāng)AP聚類算法被應(yīng)用于一個(gè)圖數(shù)據(jù)時(shí)，如果歸屬同類的頂點(diǎn)相似性很高而不同類的頂點(diǎn)相似度很小，那么這類算法不具有優(yōu)勢(shì).但對(duì)于類與類間邊界不清晰的圖數(shù)據(jù)來說，我們的算法則更加適用.從單個(gè)數(shù)據(jù)集觀察來看，AP算法在Cumulative networks數(shù)據(jù)集上的聚類結(jié)果依然表現(xiàn)最差，而算法與其余3種算法獲得了相同且最高的Acc值為90.60%.在Les Miserables數(shù)據(jù)集上，算法僅與KFCM算法獲得相同最高的Acc值，表明2個(gè)算法的最高聚類效率.在其余2個(gè)圖數(shù)據(jù)上，算法均取得了最高的Acc值，更加說明了我們算法的聚類效果.

通過觀察圖4(b)和表4發(fā)現(xiàn)，本文提出算法依然獲得最高Re值，而AP算法獲得最低值.從單個(gè)圖數(shù)據(jù)來看，算法與對(duì)比算法AFCM和KFCM在Cumulative networks數(shù)據(jù)集上的聚類結(jié)果最佳，Re達(dá)到最高值90.70%，但是AP算法對(duì)于Cumulative networks數(shù)據(jù)集的Re最低，聚類結(jié)果仍然最差.在Les Miserables數(shù)據(jù)集上，本文算法與KFCM算法取得相同最高Re值為88.00%，而在另外2個(gè)圖數(shù)據(jù)上，算法均獲得最高值說明了算法在此圖數(shù)據(jù)上的聚類效果最好.

表4 算法Re %

從圖4(c)和表5的NMI來看，本文算法依然在單個(gè)圖數(shù)據(jù)上均獲得最高值.NMI用來衡量2個(gè)變量之間的相關(guān)性，是一種常見的評(píng)價(jià)聚類指標(biāo).實(shí)驗(yàn)中用指標(biāo)NMI來衡量頂點(diǎn)的實(shí)際類別與實(shí)驗(yàn)結(jié)果是否一致，而最高的值直接說明了算法聚類效率很大程度符合實(shí)際結(jié)果.從單個(gè)圖數(shù)據(jù)來看，算法對(duì)于Cumulative networks數(shù)據(jù)集的聚類結(jié)果最佳，標(biāo)準(zhǔn)化互信息達(dá)到92.30%，而AP算法獲得最低值，算法較之明顯提高了7.20%.但在圖數(shù)據(jù)集Les Miserables上，本文算法與KFCM取得相同最高NMI為76.00%.綜上分析得本文算法的聚類效率具有明顯的優(yōu)勢(shì).同時(shí)可通過選擇最小指標(biāo)值找到正確合理的聚類數(shù).

為了進(jìn)一步證明算法效率，對(duì)比算法聚類結(jié)果的Q值.已知Q大小取決于聚類情況，其值越接近1表示類結(jié)構(gòu)強(qiáng)度越強(qiáng)，聚類質(zhì)量越好.圖4(d)給出對(duì)比結(jié)果，從圖整體發(fā)現(xiàn)，論文提出算法(綠色柱狀)在生成高質(zhì)量聚類的Q值明顯大于等于其它算法.在第一個(gè)圖數(shù)據(jù)集上，算法同F(xiàn)CM、AFCM和KFCM獲得相同且最高的Q為90.70%.在單個(gè)的數(shù)據(jù)集Les Miserables上，算法同KFCM算法獲得相同且較高Q值為88.00%，但僅較對(duì)比算法AFCM高0.02%，在其余圖數(shù)據(jù)上僅我們的算法獲得最高Q值.綜上分析表明，本文方法的類識(shí)別能力較好.基于獲得Q值可以通過選擇最高模塊度值確定算法的最佳聚類結(jié)果.

圖5為所有對(duì)比算法分別在4個(gè)圖數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比情況，結(jié)果同樣可證明算法的有效性.從單個(gè)數(shù)據(jù)集來看，在Cumulative networks數(shù)據(jù)集上，算法較其它算法的運(yùn)行時(shí)間最短，且較KFAM算法運(yùn)行時(shí)間短 0.018 s.在其它數(shù)據(jù)集上我們算法的運(yùn)行時(shí)間依然是最短的.特別地，在Neural network數(shù)據(jù)集上，AP、FCM和AFCM算法的運(yùn)行時(shí)間較我們算法更久.從實(shí)驗(yàn)結(jié)果得出，論文提出的算法繼承了模糊C均值算法的時(shí)間優(yōu)勢(shì)，運(yùn)行時(shí)間比其它算法花費(fèi)更少，因此在運(yùn)行時(shí)間和內(nèi)存消耗上都具有優(yōu)勢(shì).這是因?yàn)樗惴ú坏紤]了圖的結(jié)構(gòu)相似性和屬性相似性，還考慮了頂點(diǎn)之間邊的權(quán)重貢獻(xiàn)，在聚類數(shù)量增多時(shí)，頂點(diǎn)間的權(quán)重也會(huì)增大，此時(shí)算法聚類效果更明顯.

圖5 算法時(shí)間效率對(duì)比

5 結(jié)語(yǔ)

針對(duì)無向加權(quán)圖數(shù)據(jù)聚類問題，本文提出了一種考慮圖數(shù)據(jù)屬性信息和拓?fù)湫畔⒌拇植谀：垲愃惴?提出一種結(jié)合拓?fù)湫畔⑴c邊權(quán)重的綜合結(jié)構(gòu)相似性度量方法和一種由等價(jià)關(guān)系R誘導(dǎo)的屬性相似性，并通過結(jié)合這2種相似性構(gòu)建了算法聚類具有快速提高性質(zhì)的隸屬度函數(shù).算法進(jìn)一步引入粗糙集思想，建立了聚類的上下近似集的模糊中心表示，并以此為基礎(chǔ)構(gòu)建了參與算法迭代的目標(biāo)函數(shù).實(shí)驗(yàn)結(jié)果表明，本文提出的算法具有更高效的聚類性能.