基于最短路徑的隨機游走的圖聚類算法

牛品菽　徐保民

摘要：現(xiàn)實世界中的許多系統(tǒng)都以網(wǎng)絡圖形式存在，并且近年來圖聚類作為一種重要的分析手段已經(jīng)得到越來越多的關(guān)注。在眾多圖聚類算法中，譜圖聚類算法以其高效性、易于實現(xiàn)以及堅實的理論基礎等特性已經(jīng)得到越來越多的關(guān)注。本文提出一種基于最短路徑的隨機游走的譜圖聚類算法。該算法利用基于最短路徑的局部隨機游走模型將數(shù)據(jù)點之間的距離轉(zhuǎn)化為隨機游走的轉(zhuǎn)移概率，通過隨機游走的轉(zhuǎn)移概率構(gòu)造相似矩陣，最后利用譜方法得到聚類結(jié)果。實驗結(jié)果表明，使用本文所提出的聚類方法可以有效提高聚類效果。

關(guān)鍵字：隨機游走；圖聚類；最短距離；譜聚類

中圖分類號：TP311文獻標識碼：A文章編號：2095-2163（2015）06-

Abstract：There are many systems exiting in the form of network in the real world. And the graph clustering as an important analysis method has gained more and more attention in recent years. The spectral graph clustering algorithm is more popular because of its high efficiency， easy to implement and solid theory foundation. This paper proposes a Graph Clustering Algorithm based on Random Walk Model of the Shortest Path. This algorithm uses the random walk model based on the shortest path to transfer the distance between two data points to the transition probability， and structures the similarity matrix by the transition probability. Then the paper gets the result by using the spectral clustering algorithm. The experimental results show that using the presented clustering method can effectively improve the clustering effect.

Keywords： Random Walk； Graph Clustering； Shortest Distance； Spectral Clustering

0引言

聚類是最常用的數(shù)據(jù)分析技術(shù)之一，已經(jīng)被廣泛地應用到模式識別、數(shù)據(jù)挖掘和圖像處理等領(lǐng)域。聚類分析是一個將數(shù)據(jù)樣本劃分為由相似對象組成的分組的過程。每一個組稱為一個簇，每個簇中的數(shù)據(jù)對象的相似度大，而不同簇中的對象相似度小。從機器學習的角度來看，搜索簇就是一個無監(jiān)督學習的過程。大數(shù)據(jù)圖有很多內(nèi)部具有實際意義的數(shù)據(jù)對象組成，兩個數(shù)據(jù)對象間的相似關(guān)系可以轉(zhuǎn)化成圖模型?，F(xiàn)實世界中的許多系統(tǒng)都是由網(wǎng)絡圖形來進行表示的，比如Facebook上的朋友關(guān)系網(wǎng)、生物上的蛋白質(zhì)互質(zhì)網(wǎng)絡、科學家合著網(wǎng)絡以及網(wǎng)頁之間的超鏈接都是常見的網(wǎng)絡圖模型。近年來圖聚類作為一種重要的分析手段已經(jīng)得到越來越多的關(guān)注。圖聚類[1]主要是將圖上的節(jié)點劃分為一些子圖，使得這些節(jié)點在類內(nèi)具有較強的連接而類間的連接則相對較弱。圖聚類不僅有助于可視化和發(fā)現(xiàn)層次結(jié)構(gòu)[2]，還具有實際的意義，比如社區(qū)發(fā)現(xiàn)[3-4]、孤立點檢測[5]等，此外聚類的結(jié)果也可以用來構(gòu)建模塊，使得在一些算法中可以降低圖或模塊的復雜度[6-7]。

譜分析方法已經(jīng)成功地運用在解決數(shù)據(jù)聚類和圖劃分的問題方面。譜聚類是一種基于圖論的聚類分析方法，近幾年，由于譜聚類的高效性、易于實現(xiàn)以及成熟的理論基礎等特性已經(jīng)得到越來越多的關(guān)注，并被廣泛應用在圖像處理、計算機視覺、數(shù)據(jù)挖掘、機器學習等領(lǐng)域[8]。其基本思想是通過對樣本數(shù)據(jù)的拉普拉斯矩陣的特征向量進行聚類，從而達到對樣本數(shù)據(jù)聚類的目的。關(guān)于譜聚類算法已經(jīng)有很多人做了研究，其中經(jīng)典的算法有Perona和Freeman提出的PF算法[9]、Shi和Malik提出的SM算法[10]、Ng和Jordan等人提出的NJW算法[11]以及Meila提出的MS算法[12]等。譜聚類克服了傳統(tǒng)聚類方法僅在凸球形狀數(shù)據(jù)集上效果很好和會陷入局部最優(yōu)解的局限性，其在任意形狀數(shù)據(jù)集的聚類效果都比較理想且可以收斂到全局最優(yōu)解。

本文將提出一個新的高效的基于最短路徑的隨機游走的圖聚類算法（DWSC）。利用基于最短路徑的局部隨機游走模型將數(shù)據(jù)點之間的距離轉(zhuǎn)化為隨機游走的轉(zhuǎn)移概率，通過隨機游走的轉(zhuǎn)移概率構(gòu)造相似矩陣，最后利用譜方法得到聚類結(jié)果。

1相關(guān)工作

1.1譜聚類

譜聚類算法的思想來自譜圖劃分理論，譜聚類將聚類問題轉(zhuǎn)化為一個無向圖的多路劃分問題。譜方法類屬一種基于優(yōu)化的聚類方法，最早用于解決圖分割的問題，譜方法具有堅實的數(shù)學理論基礎，已發(fā)展成一種重要的聚類方法。該方法主要利用圖的特征分解和拉普拉斯矩陣進行聚類的。常見的圖分割準則有以下幾種。

（1）最小割集準則（Minimum-Cut）[13]

給定一個圖G，構(gòu)建其劃分的最簡單直接的方法是解決最小割問題。定義 ，并且 是A的補集。對于給定的子集數(shù)目k，尋找劃分 的問題為最小化目標函數(shù)：

當k=2時，最小割是一種簡單有效的方法。然而，這種方法并不是總能得到一個滿意的劃分，因為當k的取值不為2時，劃分容易發(fā)生傾斜，即使得一個單獨的頂點從整個圖中分離出來。顯然這不是研究想要的結(jié)果，聚類結(jié)果應該是由大量點組成的圖。

（2）比例割集準則（Ratio-Cut）[10]

Hagen和Kahng提出了比利割集準則，在該準則中 為第i類的節(jié)點個數(shù)，其目標函數(shù)為：

比例割集準則通過引入類中的節(jié)點數(shù)作為類平衡的條件，可以避免最小割集引起的劃分傾斜問題，但運行速度較慢。

（3）規(guī)范割集準則（Normalized-cut）[14]

Shi和Malik根據(jù)譜圖理論提出了2-way劃分的規(guī)范割集準則，在該準則中 為第i類中所有頂點的度之和，其目標函數(shù)為：

（4）最小最大割集準則（Min-max-cut）[15]

Ding提出了最小最大割集準則，該準則要求在最小化 的同時，最大化 ，其目標函數(shù)為：

由于構(gòu)造相似矩陣的構(gòu)造函數(shù)不同，使用的特征向量矩陣不同以及圖劃分準則不同等因素，譜圖聚類算法也存在著差異。由Perona和Freeman提出的PF算法[9]，是一種簡單的譜聚類算法。利用相似矩陣中最大特征值所對應的特征向量進行聚。對于塊對角相似矩陣，特征向量中非零元素對應的點為一類，零元素對應的點為另一類。由Shi和Malik提出的SM算法[10]目標函數(shù)定義為：

將x松弛到[-1，1]之間，根據(jù)Rayleigh熵原理，將最小化目標函數(shù)的問題轉(zhuǎn)化為求解 的第二小特征值問題。利用特征值計算相應的Fiedler特征向量，并根據(jù)啟發(fā)式規(guī)則在向量中尋找劃分點，使得在該點上得到的Ncut（A，B）值最小，將Fiedler向量中大于該點值的歸為一類，小于該點值的為另一類。SM算法的效率明顯優(yōu)于PF算法。由Scott等人提出的SLH算法[16]對相似矩陣求其前k個特征值對應的特征向量構(gòu)造特征向量矩陣V。對V的行向量進行規(guī)范化得到 ，若Q（i，j）=1則表示頂點i，j為同一類。KVV[17]算法利用比例分割準則，同SM算法一樣利用Fiedler向量尋找劃分點。該算法可以有效避免算法的過分傾斜，但是運算速度較慢。由于2-way劃分準則包含特征向量比較少，很容易丟失一些有用的信息，且算法不穩(wěn)定。Ng等人提出一種采用多路劃分準則的NJW算法[11]。該算法選取拉普拉斯矩陣的前k最大特征值對應的特征向量構(gòu)造特征矩陣，將特征矩陣行向量變換為單位向量。矩陣中每一行看作一個數(shù)據(jù)點并使用k-means算法或其他簡單聚類算法進行聚類得到聚類結(jié)果。Meila提出了一種基于Markov鏈的隨機游走的聚類算法[12]。該算法利用隨機游走構(gòu)造相似矩陣，并對其求前k個特征值對應的特征向量構(gòu)造特征向量矩陣。將矩陣中每一行看作一個數(shù)據(jù)點，在此基礎上使用k-means算法或其他簡單聚類算法進行聚類得到聚類結(jié)果。

1.2基于最短路徑的隨機游走模型

給定一個無環(huán)無向圖 ，其中 和 分別表示節(jié)點集和邊集。在LRW[18]中，游走者從一個節(jié)點按照概率 游走到相應的任意一個鄰居節(jié)點。 代表節(jié)點的度。如此可以得到鄰接矩陣即一步轉(zhuǎn)移概率矩陣P。 表示從節(jié)點 到節(jié)點 的概率。如果兩節(jié)點直接相連則 的值是 ，否則為0。同時，研究還給出 階向量 。 表示經(jīng)過 步節(jié)點 到節(jié)點 的概率。初始轉(zhuǎn)移向量 表示游走者在節(jié)點 的初始概率為1。節(jié)點間轉(zhuǎn)移概率為

假如讓每個節(jié)點隨機游走的步數(shù)就是相互之間的最短距離。即沒有必要讓整個網(wǎng)絡采取統(tǒng)一的最優(yōu)步數(shù)。此時假設 為經(jīng)過 步節(jié)點 到節(jié)點 的概率。 為節(jié)點 到節(jié)點 的最終概率。定義 為節(jié)點 和 間的最短距離。顯然，當 時， 的值為零，所以節(jié)點間首次接觸的概率為 。用 去近似 就得到

式（8）則為基于最短路徑的局部隨機游走模型LDRW[19]。其主要特性是將最短路徑引入到隨機游走中，并引入基于最短路徑的首達概率概念。

1.3基于隨機游走的譜聚類

圖上的隨機游走是從一個頂點跳到另一個頂點的隨機過程，因此譜聚類的過程可以解釋為試圖尋找一個圖的劃分使得隨機游走只發(fā)生在類內(nèi)，而類間的游走則相對較少。Meila提出MS算法[12]用Markov鏈中的隨機游走來解釋相似性，通過計算轉(zhuǎn)移概率矩陣 的特征向量，以此構(gòu)造向量空間進行聚類。其主要步驟為：

（1）根據(jù)數(shù)據(jù)集構(gòu)造相似矩陣S和對角矩陣D；

（2）計算轉(zhuǎn)移概率矩陣 ；

（3）計算P的前 個特征值對應的特征向量 ，并構(gòu)造矩陣U；

（4）將矩陣E中的每一行看做 空間中的一個數(shù)據(jù)點，利用k-means或其他經(jīng)典聚類算法對其進行聚類，得到結(jié)果。

2算法描述

本文提出的基于最短路徑的隨機游走的圖聚類算法（DWSC）通過節(jié)點間的最短路徑的隨機游走構(gòu)造相似矩陣，利用相似矩陣構(gòu)造轉(zhuǎn)移概率矩陣并對其進行特征分解，取前k個特征值對應的特征向量，對N*K維的特征向量進行k-means得到聚類結(jié)果。

2.1問題定義

本文中，定義無向圖 ，其中 是頂點集合， 是圖的邊集。相似度矩陣Similarity，其中 。對角矩陣Diagonal，其中 。概率矩陣Probability，其中 且對于矩陣Probability的任意i行有 。

2.2實驗步驟

輸入：無向圖 和聚類數(shù)目 ；

（1）計算圖的頂點間的最短距離，構(gòu)造距離矩陣distance；

（2）利用LWRD算法計算頂點相似度矩陣Similarity；

（3）計算對角矩陣Diagonal；

（4）計算轉(zhuǎn)移概率矩陣Probability；

（5）對Probability進行特征分解，去前k個特征值對應的特征向量 ；

（6）構(gòu)造矩陣 ，其中 是 中的第i列；

（7）將Eigen的每一行看做一個頂點 ，對這n個點 進行k-means聚類得到結(jié)果 ；

輸出：聚類結(jié)果 。

3結(jié)果與分析

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

3.1.1 美國大學生足球聯(lián)盟網(wǎng)絡（American College Football）

這個數(shù)據(jù)集來自UCI Network Data Repository（M. Girvan and M. E. J. Newman 2002）[20]，該網(wǎng)絡中共有115個節(jié)點，615條邊。網(wǎng)絡中的每個節(jié)點表示一支大學足球隊，每條邊表示兩個球隊間進行的一場比賽。根據(jù)地理位置，全部的足球隊組成了12個聯(lián)盟，因此也用這12個聯(lián)盟來作為算法劃分的結(jié)果，如圖1所示。

3.1.2 美國政治書籍網(wǎng)絡（Books about US Politics）

這個數(shù)據(jù)集來自UCI Network Data Repository（Adamic and Glance 2005）[21]，該網(wǎng)絡包含105個節(jié)點，441條邊。每個節(jié)點代表一本書籍，每條邊代表兩本書同時被一個購買者所購買。全本書籍總共被分為3類，如圖2所示。

3.2實驗結(jié)果

3.2.1 對比實驗及評價標準

本文采用k-means算法和MS算法作為對比實驗，評價標準分別有模塊性（Modularity）[22]，Normalized Mutual Information（NMI）[23]，Rand Index。其中NMI和Rand Index指標都是與正確性相關(guān)的評價指標，并且都是對兩個數(shù)據(jù)集相似性作對比，這里即是將聚類后的結(jié)果與數(shù)據(jù)集真實的label做對比。模塊性也是評價聚類好壞常用的一個指標，一個好的聚類結(jié)果應該具有較大的聚類內(nèi)邊數(shù)和較小的聚類間邊數(shù)。

3.2.2 實驗結(jié)果

實驗結(jié)果分別如表1和表2所示。由表1和表2可以看出，本文所提出的DWSC算法大大提高了聚類的正確性。

4結(jié)束語

本文提出了一個新的基于最短路徑的隨機游走的圖聚類算法，可以很好地應用于圖聚類的領(lǐng)域。該算法主要利用最短路徑的隨機游走構(gòu)造相似矩陣，基于譜圖理論，利用特征向量進行聚類得到結(jié)果。最后利用k-means算法和MS算法進行校驗，實驗表明，通過最短路徑的隨機游走可以更好地發(fā)現(xiàn)網(wǎng)絡圖中的相似性并有利于發(fā)現(xiàn)聚類，同時可以提高聚類的準確性。

參考文獻：

[1] SCHAEFFER S E. Graph clustering[J]. Computer Science Review， 2007， 1（1）：27–64.

[2]HERMAN I， MELANCON G， MARSHALL M S. Graph visualization and navigation in information visualization： A survey[J]. Visualization & Computer Graphics IEEE Transactions on， 2000， 6（1）：24-43.

[3] FORTUNATO S. Community detection in graphs[J]. Physics Reports， 2009， 486（3-5）：75-174.

[4] WHITE S， SMYTH P. A spectral clustering approach to finding communities in graph[C]// Siam International Conference on Data Mining，Newport Beach， CA， USA： .[s.n.]，2005：76-84.

[5] GUPTA M， GAO J， SUN Y， et al. Integrating community matching and outlier detection for mining evolutionary community outliers[J]. Kdd， 2012：859--867.

[6] SONG Y， ZHUANG Z， LI H， et al. Real-time automatic tag recommendation[C]// Proc. of the 31st Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval （SIGIR）， New York， NY， USA： ACM，2008：515–522.

[7] DALVI B B， KSHIRSAGAR M， SUDARSHAN S. Keyword search on external memory data graphs.[J]. Keyword search on external memory data graphs. - ResearchGate， 2008， 1（1）：1189-1204.

[8] LUXBURG U V. A tutorial on spectral clustering[J]. Statistics & Computing， 2007， 17（4）：395-416.

[9]Perona P， Freeman W. A factorization approach to grouping[M]//

H Burkhardt，B Neumann. Computer Vision — ECCV'98.Berlin Heidelberg： Springer， 1998：655-670.

[10] SHI J， MALIK J. Normalized cuts and image segmentation[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on， 2000， 22（8）：888-905.

[11] NG A Y， JORDAN M I， WEISS Y. On spectral clustering： Analysis and an algorithm[J]. Advances in Neural Information Processing Systems， 2002， 14：849-856.

[12] MEILA M， SHI J. Learning segmentation by random walks[C]. NIPS， Den，Co，USA：MIT Press，2000：873-879.

[13]WU Z， LEAHY R. An optimal graph theoretic approach to data clustering： theory and its application to image segmentation [J]. IEEE Transactions on PAMI，1993，15（11）：1101-1113.

[14] WANG S， SISKIND J M. Image segmentation with ratio cut [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2003，25（6）：675-690.

[15] DING C H Q， HE X， ZHA H， et al. A Min-max Cut Algorithm for Graph Partitioning and Data Clustering[C]// 2013 IEEE 13th International Conference on Data Mining. Dallas， TX， USA： IEEE Computer Society， 2001：107.

[16] SCOTT G L， LONGUET H C. Feature grouping by "relocalisation " of eigenvectors of the proximity matrix[C]// Proceedings of the British Machine Vision Conference， Oxford UK：BMVA Press， 1990：103--108.

[17] KANNAN R， VEMPALA S， VETA A. On clusterings-good， bad and spectral[C]// 2013 IEEE 54th Annual Symposium on Foundations of Computer Science， [s.l.]： IEEE Computer Society， 2000：367-367.

[18] LüLinyuan ， ZHOU A T. Link prediction in weighted networks： The role of weak ties[J]. Epl， 2010， 89（1）：18001.

[19] BAOMIN XU， TINGLIN XIN， YUNFENG WANG， et al. Local Random Walk with Distance Measure[J]. Modern Physics Letters B， 2013， 27（8）：269-275.

[20] GIRVAN M， NEWMAN ME J. Community structure in social and biological networks[J]. ProcNatl. Acad. Sci. USA 99， 2002， 99（12）：7821-7826.

[21]ADAMIC L A， GLANCE N. The political blogosphere and the 2004 U.S. Election： Divided They Blog[C]// Proceedings of the 3rd international workshop on Link discovery，New York， NY， USA： ACM， 2005：36--43.

[22]NEWMAN M E， GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2004， 69（2Pt2）：026113-026113.

[23]RAND W M. Objective criteria for the evaluation of clustering methods[J]. Journal of the American Statistical Association， 1971， 66（336）：846-850.