一種基于譜聚類的社交關系數據處理方法

吳陳，朱晨

（江蘇科技大學 江蘇 鎮江212000）

一種基于譜聚類的社交關系數據處理方法

吳陳，朱晨

（江蘇科技大學 江蘇 鎮江212000）

隨著社交應用軟件的廣泛普及，社交關系數據中存在的價值得到人們的廣泛關注，社交關系網絡可以抽象成一種圖結構，將用戶從關系結構上進行劃分等價于對圖進行分割。針對NJW多路譜聚類算法在處理圖分割時需要人為確定聚類數目的問題，引入本征間隙的方法，通過對輸入樣本數據的拉普拉斯矩陣進行譜分析，得出樣本的聚類數目。實驗證明，改進后的NJW算法，在實驗數據集上可以自動獲取聚類數目并具有較好的聚類效果。

譜聚類；NJW；本征間隙；K-means

隨著互聯網行業的蓬勃發展，各種社交應用積累了無數的用戶關系數據，海量社交數據的背后存在著巨大的價值，將用戶群體從結構上進行劃分，是所有社交應用研究人員關注的主要內容。想要從傳統的使用二維表記錄的用戶數據中發現用戶關系，可以使用嵌套的sql查詢語句方式得到，但是多層嵌套的sql語句運行的效率不佳。社交關系數據本質上是一個無邊際的網絡，網絡中的結點代表用戶，結點之間的邊代表用戶之間的關系，這種社交關系結構符合復雜網絡中的自組織、自相似、吸引子、小世界、無標度的特性。如何快速地從社交關系結構上將用戶分開，是如今很多學者研究的方向。將用戶從關系結構上進行劃分，可以看作是對圖進行分割。圖分割問題本質上是一個NP難問題，可以通過求取關系圖的相似度矩陣或Laplacian矩陣的譜分解來轉化它。

NJW算法是一種多路譜聚類算法，但在進行聚類之前仍然需要人為確定聚類數目。針對這一問題，通過對樣本數據建立相似矩陣并進行譜分析，從最大本征間隙所在的位置獲得聚類數目，將本征間隙與NJW算法結合，改進后的NJW算法可以自動獲取聚類數目，并在實驗數據上獲得了理想的聚類效果。

1 譜圖理論與譜聚類算法

圖是由結點（Vertices）和邊（Edge）構成，可以表示為G=（V，E），其中V（G）是圖中結點的非空點集，V（G）中元素的無序對構成邊集合E（G）。V（G）中元素稱為頂點或結點，通常表示為V=｛v1，v2，…，vn｝，其中結點的個數用n（G）=|V|表示。E（G）中的元素稱為邊，通常使用（vi，vj）表示結點vi和vj間相連的邊，邊數用m（G）=|E|表示。當vi∈V（G）稱為結點vi的度。

圖G的特征值即為圖G的鄰接矩陣W（G）的特征值。對于一個有n個結點的無向圖來說W（G）是一個n階實對稱陣，必有個特征值，并且這些特征值都是實數。用λi=（i=1，2，…，n）表示W（G）的n個特征值。鄰接矩陣W（G）的n個特征值λi=（i=1，2，…，n）組成的有序序列即為圖的譜。

由于社交關系數據中沒有具體的坐標值，因此不能直接使用歐幾里得距離等度量算法來對數據進行聚類［1］，對圖結構數據進行聚類主要通過譜聚類算法。

譜聚類（Spectral clustering）算法是一種圖分割算法，其思想來源于譜圖劃分理論［2］，與傳統的聚類算法相比，它具有在任意形狀的樣本空間上聚類且收斂于全局最優解的特點，并且在解決非塊狀、非凸球形數據的聚類問題時有著十分出色的表現［3］。

譜聚類算法的一般過程可以歸納為如下形式W：

1）根據選用的相似性度量方法，構建樣本數據的相似矩陣；

2）計算相似矩陣W的度矩陣D；

3）計算拉普拉斯矩陣L=D-W；

4）計算拉普拉斯矩陣L特征值與特征向量；

5）將樣本數據構成的點集映射到基于一個或多個特征向量確定的低維空間中；

6）在低維空間中，將數據集按行劃分到兩類或多類。

相似矩陣又稱親和矩陣，通常使用A或W來表示，該矩陣中的元素，其定義為：

其中d（vi，vj）表示樣本點 i與 j之間的距離，歐式距離‖vi，vj‖表示。σ是尺度參數 ，決定了樣本點之間相似性的縮放程度。將相似矩陣中每行元素值相加，即得到該樣本點的度。從樣本結點的度中可以找到該樣本點周圍其他結點的分布情況。所有樣本點的度值構成的對角矩陣，稱為度矩陣，D用表示，

常見的圖劃分準則有最小割集準則（Minimum cut）［4］，規范割集準則（Normalized cut）［5］，比例割集準則（Ratio cut）［6］，平均割集準則（Average cut）［7］，最小最大割集準則（Min-max cut）［8］。拉普拉斯矩陣主要有兩種形式，即規范化拉普拉斯矩陣和非規范化拉普拉斯矩陣，規范化拉普拉斯矩陣是通過松弛Ncut得到，非規范化拉普拉斯矩陣是通過松弛RatioCut得到［9］。

非規范化拉普拉斯矩陣可以表示為L=D-A，并具有如下特性：

2）L是半正定矩陣；

3）L中存在0特征值，并且0特征值對應的特征向量所含元素全為1；

4）L中存在n個非負實特征值，即：0=λ1≤λ2≤…≤λn。

規范化拉普拉斯矩陣存在兩種表示形式，分別為：

規范化拉普拉斯矩陣具有如下特性：

3）如果λ是Lrw的特征值，以及其對應的特征向量為，當且僅當λ和Lsym滿足Lv=λDv；

5）Lrw和Lsym都是半正定矩陣，Lrw和Lsym對應的n個非負的實特征值，存在0=λ1≤λ2≤…≤λn。

文中主要采用樣本數據集的規范化拉普拉斯矩陣做處理。

2 NJW算法

Ng，Jordan等人選取拉普拉斯矩陣Lsym的前k個最大特征值對應的特征向量，使其Rk在空間中構成與原數據一一對應的表述，然后在Rk空間中進行聚類［3］。

NJW算法描述如下：

1）計算矩陣Lsym的前k個最大特征值及其所對應的特征向量x1，x2，…xk，正交化處理并構造矩陣X=［x1，x2，…xk］∈Rn×k；

3）將矩陣Y的每一行看作是Rk空間中的一個點，對其使用k-means算法，得到k個聚類；

4）將樣本點yi劃分到聚類j中，當且僅當Y的第i行被劃分到聚類j中。

3 本征間隙

本征間隙即相鄰特征值的差值，在譜聚類算法中引入本征間隙的概念，第一個極大本征間隙出現的位置預示著聚類個數。對于有個理想的彼此分離的樣本點的有限數據集來說，由該數據集構建的相似矩陣的前個最大特征值為1，而第個特征值則嚴格小于1，兩者之間的差距取決于這個聚類的分布情況［10］。

由矩陣攝動理論可知，本征間隙越大，選取的個特征向量所構成的子空間就越穩定［11］，因此，只要找到樣本數據集的相似矩陣或拉普拉斯矩陣的最大本征間隙的位置，就能確定樣本數據集的聚類數目［12］，從而解決了聚類問題普遍存在的確定聚類數目的問題。再調用聚類算法，就能很快將樣本點進行分類。

從本征間隙得到聚類數目算法的思路：

1）首先計算樣本數據集的規范化相似度矩陣Anor；

2）計算Anor的特征值；

3）將特征值按順序從小到大排列，即λ1≤λ2≤…≤λn；

4）計算本征間隙，得到本征間隙序列｛g1，g2，…，gn|gi=λi+1-λi｝；

5）取得本征間隙序列中第一個極大值所在的位置，即本征間隙的下標；

6）從本征間隙的下標得到聚類數目k，即k=argmin｛gi-gj|j＜i＞0∧gi-gi+1＞0｝。

求取聚類簇數目的偽代碼：

輸入：按從小到大排序的規范拉普拉斯矩陣的特征值

輸出：輸出聚類數目

｛

Max_eigengap=0

Max_eigengap_position=0

4 改進后的NJW算法

改進后的NJW算法，在輸入樣本數據之前，先對樣本數據構建拉普拉斯矩陣 Lsym，然后對Lsym進行譜分析［13］，得出最大本征間隙所在的位置，根據最大本征間隙出現的位置自動獲取聚類數目，其步驟描述如下：

1）輸入樣本數據計算矩陣Lsym；

2）對矩陣Lsym進行譜分析，獲得最大本征間隙存在的位置，得到聚類簇數目k；

3）計算矩陣Lsym的前k個最大特征值及其所對應的特征向量x1，x2，…，xk；

5）矩陣Y的每一行看作是Rk空間中的一個點，使用kmeans算法對Rk空間聚類，得到得k個聚類；

6）將數據點yi劃分到聚類j中，當且僅當Y的第i行被劃分到聚類j中。

5 實驗過程

本實驗是在Ubuntu14.04環境下完成，使用的Python版本為 2.7.6，實驗中主要引用了 Networkx，numpy，sklearn，numpy，pylab，graph_laplacian，eigsh等Python包。

文中將改進的NJW算法應用到實驗數據集上得到理想的效果，使用的實驗數據集如表1所示。該實驗數據［15］集中包含12個用戶，20條邊關系。實驗數據集在HuYifan比例下呈圖1所示，通過觀察可以發現樣本數據中包含3個子圖。

表1 實驗實驗數據集

圖1 樣本數據集在Hu Yifan比例下的展示

圖2為按從小到大排列的拉普拉斯矩陣特征值，從圖2中還能看出相鄰特征值之間的差值，特征值λ3與λ4之間的差值最大［14］，即最大本征間隙為 λ4-λ3，因此該樣本數據集的聚類數目為3，與直接觀察法得到相同結果。

最后，通過K-means算法得到實驗數據集的聚類結果。如表2所示。

圖2 本征間隙及普拉斯矩陣特征值

6 結束語

從實驗結果可以看出，改進后的NJW算法能夠對輸入的社交關系數據自動獲取聚類數目，提高了算法的自動性，并且在實驗數據集上對算法行了驗證，實驗結果表明該算法可以有效將樣本數據進行劃分，保證了算法的正確性和有效性。

表2 實驗數據集聚類結果

文中提出了使用譜聚類算法處理社交關系數據的方法，分析了NJW多路譜聚類算法的原理，指出其存在的不足，即聚類數目需要人為確定，提出使用本征間隙改進NJW算法，使算法可以根據輸入樣本數據的結構自動獲取聚類數目。實驗證明，改進后的NJW算法，在實驗數據集上可以自動獲取聚類數目并具有較好的聚類效果。

［1］溫菊屏，鐘勇.圖聚類的算法及其在社會關系網絡中的應用［J］.計算機應用與軟件，2012，29（2）:161-163.

［2］Foedler M.Algebraic connectivity of graphys［J］.Czech Math，1973（23）:298-305.

［3］蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述［J］，計算機科學，2008，35（7）:14-18.

［4］Wu Z，Leahy R.An optimal grapy theoretic approach to data clustering:theory and its application to image segmentation［J］.IEEE Trans on PAMI，1993，15（11）:1101-1113.

［5］Shi J，Malik J.Normalized cuts and image segmentation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）:888-905.

［6］Hagen L，Kahng A B.New spectral methods for radio cut partition and clustering［J］.IEEE Trans.Computer-Aided Design，1992，11（9）:1074-1085.

［7］Sarkar S，Soundararajan P.Supervised learning of large perceptual organization:Graph spectral partitioning and learning automata［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2000，22（5）:504-525.

［8］Ding C，He X，Zha.Spectral Min-Max cut for Graph Partitioning and Data Mining［J］.IEEE International Conference on Data Mining，2001:107-114.

［9］嚴俊.譜聚類算法改進及在社交網絡中的應用［D］.桂林：廣西師范大學，2014.

［10］田錚，李小斌，句彥偉.譜聚類的擾動分析［J］.中國科學，2007，37（4）:527-543.

［11］孫繼廣.矩陣擾動分析［M］.北京:科學出版社，2001.

［12］姜慧霖.基于層次聚類的案例檢索策略［J］.電子設計工程，2014，22（17）：158-161.

［13］黃婷，黃偉.基于不同算法求解子問題的Benders分解法在無功規劃中的應用［J］.陜西電力，2013（3）：23-26.

［14］張偉，陳鋒，馬軍強，等.軌/姿控發動機脈沖后效沖量快速算法的研究及應用［J］.火箭推進，2012（1）：51-56.

［15］李全鑫，魏海平.基于聚類分類法的信息過濾技術研究［J］.電子設計工程，2014，22（20）：14-16.

A processingmethod of social relational data based on spectral clustering

WU Chen，ZHU Chen
（Jiangsu University of Science and Technology，Zhenjiang 212000，China）

With the large-scaleuse ofsocialmedia applications，the value of social relationship data has drawnwide attention. The structure ofsocialnetworks can be abstracted asa graph.To divide communities from the relationalstructure isequivalent to graph segmentation.When we use NJW multiple spectral clustering algorithm to process graph segmentation issue，we need to determine the clustering numbermanually.In order to solve this problem，this paper tried to introduce the concept of Eigengap to predict the number of clusters after spectrum analysis of inputsample's Laplacianmatrix.The effectiveness of the proposed algorithm was verified with on experimentaldata and got the desired results.

spectral clustering；NJW；eigengap；K-means

TN302

A

1674－6236（2016）20-0020-04

2015-10-29 稿件編號：201510221

吳 陳（1962—），男，湖北天門人，博士，教授。研究方向：實驗智能與模式識別，粗糙集理論及應用，數據挖掘與知識發現。