吳陳，朱晨

（江蘇科技大學(xué) 江蘇 鎮(zhèn)江212000）

一種基于譜聚類的社交關(guān)系數(shù)據(jù)處理方法

吳陳，朱晨

（江蘇科技大學(xué) 江蘇 鎮(zhèn)江212000）

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

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

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

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

1 譜圖理論與譜聚類算法

圖是由結(jié)點（Vertices）和邊（Edge）構(gòu)成，可以表示為G=（V，E），其中V（G）是圖中結(jié)點的非空點集，V（G）中元素的無序?qū)?gòu)成邊集合E（G）。V（G）中元素稱為頂點或結(jié)點，通常表示為V=｛v1，v2，…，vn｝，其中結(jié)點的個數(shù)用n（G）=|V|表示。E（G）中的元素稱為邊，通常使用（vi，vj）表示結(jié)點vi和vj間相連的邊，邊數(shù)用m（G）=|E|表示。當(dāng)vi∈V（G）稱為結(jié)點vi的度。

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

由于社交關(guān)系數(shù)據(jù)中沒有具體的坐標(biāo)值，因此不能直接使用歐幾里得距離等度量算法來對數(shù)據(jù)進行聚類［1］，對圖結(jié)構(gòu)數(shù)據(jù)進行聚類主要通過譜聚類算法。

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

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

1）根據(jù)選用的相似性度量方法，構(gòu)建樣本數(shù)據(jù)的相似矩陣；

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

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

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

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

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

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

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

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

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

2）L是半正定矩陣；

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

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

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

規(guī)范化拉普拉斯矩陣具有如下特性：

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

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

文中主要采用樣本數(shù)據(jù)集的規(guī)范化拉普拉斯矩陣做處理。

2 NJW算法

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

NJW算法描述如下：

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

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

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

3 本征間隙

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

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

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

1）首先計算樣本數(shù)據(jù)集的規(guī)范化相似度矩陣Anor；

2）計算Anor的特征值；

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

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

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

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

求取聚類簇數(shù)目的偽代碼：

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

輸出：輸出聚類數(shù)目

｛

Max_eigengap=0

Max_eigengap_position=0

4 改進后的NJW算法

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

1）輸入樣本數(shù)據(jù)計算矩陣Lsym；

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

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

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

6）將數(shù)據(jù)點yi劃分到聚類j中，當(dāng)且僅當(dāng)Y的第i行被劃分到聚類j中。

5 實驗過程

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

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

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

圖1 樣本數(shù)據(jù)集在Hu Yifan比例下的展示

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

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

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

6 結(jié)束語

從實驗結(jié)果可以看出，改進后的NJW算法能夠?qū)斎氲纳缃魂P(guān)系數(shù)據(jù)自動獲取聚類數(shù)目，提高了算法的自動性，并且在實驗數(shù)據(jù)集上對算法行了驗證，實驗結(jié)果表明該算法可以有效將樣本數(shù)據(jù)進行劃分，保證了算法的正確性和有效性。

表2 實驗數(shù)據(jù)集聚類結(jié)果

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

［1］溫菊屏，鐘勇.圖聚類的算法及其在社會關(guān)系網(wǎng)絡(luò)中的應(yīng)用［J］.計算機應(yīng)用與軟件，2012，29（2）:161-163.

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

［3］蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述［J］，計算機科學(xué)，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］嚴俊.譜聚類算法改進及在社交網(wǎng)絡(luò)中的應(yīng)用［D］.桂林：廣西師范大學(xué)，2014.

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

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

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

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

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

［15］李全鑫，魏海平.基于聚類分類法的信息過濾技術(shù)研究［J］.電子設(shè)計工程，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—），男，湖北天門人，博士，教授。研究方向：實驗智能與模式識別，粗糙集理論及應(yīng)用，數(shù)據(jù)挖掘與知識發(fā)現(xiàn)。