張素智 張 琳 曲旭凱

(鄭州輕工業(yè)學(xué)院計算機與通信工程學(xué)院 河南 鄭州 450002)

?

基于最短路徑的加權(quán)屬性圖聚類算法研究

張素智 張 琳 曲旭凱

(鄭州輕工業(yè)學(xué)院計算機與通信工程學(xué)院 河南 鄭州 450002)

圖在計算機領(lǐng)域是一種重要的數(shù)據(jù)結(jié)構(gòu)，可以用來描述事物之間的復(fù)雜關(guān)系。圖的節(jié)點和邊具備一個或者多個不同的屬性。如何結(jié)合屬性對圖進行聚類是目前所面臨的一個新的挑戰(zhàn)。目前的屬性圖聚類算法，多存在聚類效果差，消耗資源多，效率低等缺點。針對以上問題，提出一種基于最短距離的加權(quán)屬性圖聚類算法WASP(weighted attribute graph clustering algorithm based on shortest path)，建立加權(quán)屬性無向圖模型，在此模型上基于最短路徑算法度量節(jié)點間的關(guān)聯(lián)度，以此為原則選取新的聚類中心對圖進行聚類。實驗表明，新的聚類算法具有更高效的聚類效果。

圖 加權(quán)屬性圖 最短路徑 聚類

0 引 言

近年來，圖結(jié)構(gòu)被廣泛應(yīng)用于多個領(lǐng)域來描述數(shù)據(jù)之間的復(fù)雜結(jié)構(gòu)。針對海量圖數(shù)據(jù)的分析和挖掘越來越重要。作為圖數(shù)據(jù)挖掘算法的一種，圖聚類算法引起了眾多關(guān)注[1，2]。圖聚類，簡單描述就是根據(jù)圖結(jié)構(gòu)上節(jié)點和邊的某種相似性，將圖上的節(jié)點和邊劃分為不同的組。屬性圖聚類是圖聚類中的一種特殊情況，即在用節(jié)點和邊表示實體和實體關(guān)系的同時，還需要考慮到節(jié)點和邊的屬性。在屬性圖聚類時，同時考慮節(jié)點間結(jié)構(gòu)和屬性的相似性，則能夠得到更加準(zhǔn)確的聚類效果。如何更好地同時結(jié)合結(jié)構(gòu)和屬性進行聚類是目前圖聚類研究的熱點和難點。

針對屬性圖聚類問題，現(xiàn)階段也有許多研究成果：Tian等人[3]根據(jù)聚類中節(jié)點和屬性相一致的原則，提出了k-SNAP算法，該算法通過用戶的下鉆和上取，將屬性一致的點聚集在一起，實現(xiàn)了多粒度的圖聚類。但是此算法僅根據(jù)節(jié)點屬性聚類，會造成聚類結(jié)構(gòu)分散，聚類效果中節(jié)點數(shù)過多。針對k-SNAP算法存在的問題，Zhang等人[4]改進了該算法，對數(shù)值屬性分類，并對屬性相近對按相似度基于最大惡化程度進行劃分。Nevile 等人[5]將具有相同屬性的屬性個數(shù)定義為邊的權(quán)重值，并以此為基礎(chǔ)將屬性圖轉(zhuǎn)化為帶權(quán)圖進行聚類。Steinhaeuser等[6]提出了相似的算法，并將屬性擴展到具有連續(xù)值域的情況。此類算法由人工定義權(quán)重值，雖然算法效率高，但聚類效果和可拓展性差。也有一些算法通過增廣屬性圖[7，8]，采用熵的統(tǒng)一模型來衡量圖中的同質(zhì)性，實現(xiàn)屬性圖的聚類。該方法雖然將圖的結(jié)構(gòu)和屬性結(jié)合起來聚類，但統(tǒng)一聚類超結(jié)點中的結(jié)點聯(lián)系并不緊密。還有一些算法把模型的思想[9，10]應(yīng)用到屬性圖聚類中，將屬性圖聚類轉(zhuǎn)化為概率問題，但此類算法需要事先設(shè)定好聚類數(shù)量，才能達(dá)到較好的聚類效果。

針對以上算法的問題，本文提出了一種基于最短路徑的加權(quán)屬性圖聚類算法WASP。該算法通過建立加權(quán)屬性圖模型，對圖中邊和節(jié)點的屬性設(shè)置權(quán)值，確定節(jié)點相似度，采用最短路徑算法計算節(jié)點間的距離，確定聚類中心，并在聚類過程中自動更新權(quán)重值，以此為基礎(chǔ)進行聚類。最后將WASP算法應(yīng)用在DBLP數(shù)據(jù)集中，通過實驗對比，該算法具有較好的聚類效果。

1 相關(guān)定義

1.1 屬性加權(quán)無向圖定義

定義1屬性加權(quán)無向圖G=(V,E,A,ω)；其中：

V表示屬性圖中節(jié)點集合：V={v1,v2,…,vn}；

E表示屬性圖中邊的集合：E={(vi,vj)|(vi,vj)∈R,1≤i,j≤n,i≠j}；

A表示圖的屬性的集合：A={a1,a2,…,am}；其中|A|=m′；

ω為邊的權(quán)重值：ω={ω1,ω2,…，ωp} ，|ω|=p′ ，ωa(ik)表示節(jié)點vi的屬性ak的權(quán)值，若任意兩節(jié)點vi、vj直接相連，則這兩點節(jié)點間的權(quán)重值為ωi,j= ωq，q∈{1,2…，p}；

1.2 節(jié)點相似度定義

在社交網(wǎng)絡(luò)中，如果用戶之間的公共朋友越多，則用戶之間的聯(lián)系越大。對于屬性圖中的節(jié)點，如果節(jié)點之間聯(lián)系的公共節(jié)點越多，則這些節(jié)點位于同一個簇的可能性越大。本文考慮將與節(jié)點直接關(guān)聯(lián)的點稱為該節(jié)點的節(jié)點朋友。

定義2屬性圖G=(V,E),v為圖中的節(jié)點。定義節(jié)點朋友集合為Κ(v)：

K(v)={u∈V|(v,u)∈E}∪{v}

(1)

若v、u之間有邊，即∈E,則將邊的相似度定義為：

(2)

2 算法描述

2.1 自動更新屬性權(quán)重值

為了得到較好的聚類效果，提出了一種自動更新屬性權(quán)重值的方法，在聚類過程中不斷更新屬性權(quán)重值，來得到較好的聚類效果。

(3)

因此更新后的權(quán)重值：

(4)

2.2 最短路徑算法

為了發(fā)現(xiàn)圖中高關(guān)聯(lián)度的邊，考慮到邊的權(quán)重和相似度，設(shè)定參數(shù)α、β，且α+β=1。任意一條邊上的關(guān)聯(lián)度為：

(5)

兩個節(jié)點間路徑越長，則關(guān)聯(lián)度越小，若要取得最大關(guān)聯(lián)度的節(jié)點，則相鄰節(jié)點直接取節(jié)點間最短距離，非相鄰節(jié)點取節(jié)點之間最短距離的和。最大關(guān)聯(lián)度的和為:

(6)

其中，Z是節(jié)點va、ub中間節(jié)點的集合。本文采用最短路徑算法中的經(jīng)典算法Dijkstra算法。

根據(jù)最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)，如果存在一條從i到j(luò)的最短路徑(vi,…,vk,vj)，vk是vj前面的一頂點，那么(vi，…，vk)也必定是從i到j(luò)的最短路徑。為了求出最短路徑，Dijkstra提出了以最短路徑長度遞增，逐次生成最短路徑的算法。例如對于源頂點v0，首先選擇其直接相鄰的頂點中長度最短的頂點vi，那么當(dāng)前已知可得從v0到達(dá)vj頂點的最短距離：

(7)

根據(jù)這種思路，假設(shè)存在圖G=(V,E,ω)，源頂點為v0，U={v0},dist[i]記錄v0到vi的最短距離，path[i]記錄從v0到vi路徑上的i前面的一個頂點，則算法過程為：

1) 從{V-U}中選擇使dist[i]值最小的頂點i，將i加入到U中；

2) 更新與i直接相鄰頂點的dist值，即dist[j]=min{dist[j],dist[i]+matrix[i][j]}；

3) 直到U=V。

2.3 聚類算法描述

基于最短路徑的圖聚類算法，就是在計算最大關(guān)聯(lián)度時采用最短路徑算法，選取相應(yīng)的節(jié)點并劃分到同一簇中。具體算法步驟如下：

輸入：屬性加權(quán)無向圖G=(V,E,A,ω)，初始權(quán)重值ω=1.0，聚類數(shù)量k，參數(shù)α=0.4，β=0.6；

輸出：劃分的不同的簇；

1) 計算邊的相似度Γ(v,u)；

2) 在初始聚類數(shù)量k中選擇節(jié)點作為初始聚類中心Vstart，且Vstart不能為空集。定義剩余節(jié)點Vleft=V-Vstart；

4) 在劃分好的節(jié)點中，根據(jù)更新的權(quán)重值，得到L(va,ub)，并將關(guān)聯(lián)度大且距離短的的節(jié)點劃分為一簇；

5) 若Vleft=?，則聚類結(jié)束，所有節(jié)點劃分完畢，若Vleft≠?且Vleft

WASP算法是一種基于最短路徑對圖的結(jié)構(gòu)和屬性聚類的算法。在算法時間復(fù)雜度方面，第1步，計算邊的相似度，時間復(fù)雜度為Ο(n)；第2、3步，選擇聚類中心的，時間復(fù)雜度為Ο(n3)，第3-5步，計算最短路徑，劃分節(jié)點到不同的簇，時間復(fù)雜度為Ο(kn-n2)，其中k為初始聚類數(shù)量。該算法總體時間復(fù)雜度為Ο(n3)。

3 實驗與分析

3.1 實驗數(shù)據(jù)集

本次實驗采用DBLP數(shù)據(jù)集。這是一個學(xué)術(shù)合作關(guān)系的網(wǎng)絡(luò)。由德國的特里爾大學(xué)創(chuàng)建的發(fā)表在計算機期刊、雜志和會議論文的數(shù)據(jù)庫系統(tǒng)。該網(wǎng)絡(luò)包括一萬多個節(jié)點和兩萬多條無向邊。其中節(jié)點表示論文作者，邊代表作者們合作完成的論文。本次實驗選擇了該網(wǎng)絡(luò)提供的在數(shù)據(jù)挖掘、數(shù)據(jù)庫、人工智能、信息檢索等相關(guān)領(lǐng)域發(fā)表論文最多的5000名作者英文單位。

作者單位的中英文要完全對應(yīng)，每個實詞的首字母大寫。在部門名稱和單位名稱之間、在單位名稱和城市名之間使用英文逗號隔開，城市名和郵編之間使用一個英文空格隔開，不能用逗號。

3.2 評價標(biāo)準(zhǔn)

(8)

3.3 實驗結(jié)果

實驗時設(shè)定聚類初始數(shù)量k=5,10,15,20,25,30，圖1為WASP算法與SCAN算法在DBLP數(shù)據(jù)集上的聚類密度效果。由圖1可知，在聚類數(shù)量較少時，WASP算法與SCAN算法聚類效果沒有太大差別，但當(dāng)聚類數(shù)量增多時，WASP算法更具有優(yōu)勢。這是因為WASP算法不但考慮了圖的屬性和結(jié)構(gòu)，還考慮到了節(jié)點間的權(quán)重值，在聚類數(shù)量增多的時候，節(jié)點間的權(quán)重值也會增大，此時WASP算法聚類效果更明顯。

圖1 聚類密度結(jié)果圖

為了更好地對比兩個算法的聚類效率，選擇對比兩算法的聚類時間。在實驗數(shù)據(jù)集上分別運行WASP算法和SCAN算法各10次，并記錄下每次運算所消耗的時間。取10次運算的平均值作為聚類時間。

由圖2可知，當(dāng)聚類數(shù)目較小時，WASP算法與SCAN算法聚類時間差距不大。但當(dāng)聚類數(shù)目開始增多時，SCAN算法無明顯變化，WASP算法卻出現(xiàn)變化。這是因為由于該算法在聚類迭代時，每次都要計算當(dāng)前聚類中心到所有節(jié)點的最短距離。當(dāng)聚類數(shù)量增多，即k的值增加時，由于算法3-5步的時間復(fù)雜度為Ο(kn-n2)，算法第3-5步所消耗的時間將會增加。因此算法總體時間將會變長，而對于SCAN算法來說，時間復(fù)雜度不會有明顯變化。在大型圖聚類算法中，WASP算法時間會長于SCAN算法，但由于k值對WASP算法時間影響較小，因此具體到實際應(yīng)用中只有幾秒鐘時間，且在小型數(shù)目集中沒有明顯區(qū)別。

圖2 聚類時間圖

4 結(jié) 語

本文通過對現(xiàn)有圖聚類算法的研究，以加權(quán)屬性圖為模型，提出了基于最短路徑的加權(quán)屬性圖算法。該算法結(jié)合圖的屬性和結(jié)構(gòu)進行聚類，實驗表明，該算法比一般圖聚類算法具有更好的聚類效果。但是該算法在大型圖上聚類時間略長于其他聚類算法，需要在今后的工作中進一步的改進。

[1] Majumdar D,Kanjilal A,Bhattacharya S.Separation of scattered concerns: a graph based approach for aspect mining[J].ACM SIGSOFT Software Engineering Notes,2011,36(2): 1-11.

[2] Sengupta S,Kanjilal A,Bhattacharya S.Measuring complexity of component based architecture: a graph based approach[J].ACM SIGSOFT Software Engineering Notes,2011,36(1): 1-10.

[3] Tian Y,Hankins R A,Patel J M.Efficient aggregation for graph summarization[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data.ACM,2008: 567-580.

[4] Zhang N,Tian Y,Patel J M.Discovery-driven graph summarization[C]//Data Engineering (ICDE),2010 IEEE 26th International Conference on.IEEE,2010: 880-891.

[5] Neville J,Adler M,Jensen D.Clustering relational data using attribute and link information[C]//Proceedings of the text mining and link analysis workshop,18th international joint conference on artificial intelligence.2003: 9-15.

[6] Steinhaeuser K,Chawla N V.Community detection in a large real-world social network[M]//Social computing,behavioral modeling,and prediction.Springer US,2008: 168-175.

[7] Cheng H,Zhou Y,Yu J X.Clustering large attributed graphs: A balance between structural and attribute similarities[J].ACM Transactions on Knowledge Discovery from Data (TKDD),2011,5(2): 12.

[8] Liu Z,Yu J X,Cheng H.Approximate homogeneous graph summarization[J].Information and Media Technologies,2012,7(1): 32-43.

[9] Xu Z,Ke Y,Wang Y,et al.A model-based approach to attributed graph clustering[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.ACM,2012: 505-516.

[10] Zanghi H,Volant S,Ambroise C.Clustering based on random graph model embedding vertex features[J].Pattern Recognition Letters,2010,31(9): 830-836.

[11] Zhou Y,Cheng H,Yu J X.Clustering large attributed graphs: An efficient incremental approach[C]//Data Mining (ICDM),2010 IEEE 10th International Conference on.IEEE,2010: 689-698.

STUDY ON SHORTEST PATH-BASED CLUSTERING ALGORITHM OF WEIGHTED ATTRIBUTE GRAPH

Zhang Suzhi Zhang Lin Qu Xukai

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,Henan,China)

Graph is an important data structure in computer science,and can be used to describe the complex relationship between things.The nodes and edges in graph have one or more different attributes.How to cluster the graph in combination with attributes is a new challenge encountered at present.Many of current attribute graph clustering algorithms have the drawbacks of poor clustering effect,big resource consumption and low efficiency.In view of the above problems,this paper puts forward a shortest path-based weighted attribute graph clustering algorithm,and builds the weighted attribute undirected graph model.Based on the model the algorithm measures the correlation degree between the nodes based on shortest path algorithm,and takes this as the principle to select new clustering centre to cluster the graph.Experiment shows that the new clustering algorithm has more efficient clustering effect.

Graph Weighted attribute graph Shortest path Clustering

2015-06-10。國家自然科學(xué)基金青年科學(xué)基金項目(61201447)。張素智，教授，主研領(lǐng)域：Web數(shù)據(jù)庫，分布式計算，異構(gòu)系統(tǒng)集成。張琳，碩士生。曲旭凱，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2016.11.050