朱慶生，付飄飄，張 程

(重慶大學 計算機學院，重慶 400044)

基于自然鄰的自適應譜聚類算法

朱慶生，付飄飄，張 程

(重慶大學 計算機學院，重慶 400044)

在傳統(tǒng)譜聚類算法中，構造相似矩陣時需要人為輸入尺度參數(shù)；除此之外，之后的k-means過程中還需要人工輸入確切的聚類數(shù)目，而以上兩個參數(shù)對聚類效果影響巨大。針對以上問題，提出了一種基于自然鄰的自適應譜聚類算法。該算法不需要人為輸入任何參數(shù)，完全實現(xiàn)自適應，主要方式是通過自然鄰算法獲取各點之間的鄰近信息，其中包括自然鄰個數(shù)、自然逆鄰個數(shù)、自然鄰居集以及自然逆鄰居集。通過實例分析，在多重尺度數(shù)據(jù)集下或者在流行數(shù)據(jù)集中，充分利用以上先驗信息構造出更加符合實際情況的相似矩陣。另外，根據(jù)近鄰傳播思想獲得聚類數(shù)目。將該算法運用于部分人工數(shù)據(jù)集上，且與譜聚類算法進行比較，聚類效果顯著改進。實驗結果表明，該算法具有一定的有效性和優(yōu)越性。

譜聚類;自然鄰;自適應;尺度參數(shù);聚類數(shù)目

0 引 言

聚類是數(shù)據(jù)挖掘中處理數(shù)據(jù)的一種重要方法。所謂聚類，就是將數(shù)據(jù)分類到不同的類或者簇這樣的一個過程，所以同一個簇中的對象有很大的相似性，而不同簇間的對象有很大的相異性?，F(xiàn)如今，聚類已有很多經(jīng)典算法，如k-means[1]、EM[2]等。這些算法對凸形樣本空間聚類效果較好，但對于任意形狀的非凸數(shù)據(jù)集聚類效果欠佳。近年來，基于圖論的算法的研究與應用已成為學術界的一個熱門，而譜聚類算法就是基于圖論理論，能夠在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解，因此也得到了較快的發(fā)展。

譜聚類算法給聚類提供了新的求解思路，在許多具體應用中取得了不錯的效果，但是本身也存在急需解決的問題。該算法利用高斯核函數(shù)構造相似矩陣，其中涉及到尺度參數(shù)，尺度參數(shù)在選取時沒有任何的范圍和規(guī)律；而譜聚類算法對尺度參數(shù)極為敏感，若尺度參數(shù)選擇不當，聚類效果急劇下降。另外在譜聚類過程中，需要選取k個特征向量，k值與聚類數(shù)目c相等；故而準確選取聚類數(shù)目同樣至關重要[3-10]。

針對譜聚類算法的關鍵問題，國內(nèi)外研究人員爭相研究并提出了相應的解決辦法。2001年，Ng等[11]提出通過選取不同的σ值查看運行效果，選取效果最好時所對應的參數(shù)值。做法實現(xiàn)簡單，但重復操作太多，耗時太長，且難以尋找到最佳效果；2004年，Zelnik Manor等[12]提出了著名的self-Tuning算法，為每一個點選取一個σ值，基本實現(xiàn)了參數(shù)的自適應，減弱了尺度參數(shù)對聚類結果的影響，但未能將更多有效的信息帶入到聚類中，聚類效果一般；2005年，Yeung等[13]將譜聚類與基于路徑聚類方法相結合，該相似度能很好地適應樣本的分布特點，但需要人為設置尺度參數(shù)；2007年，王玲等[14]根據(jù)聚類假設，定義非高斯核的相似度測量，基于密度敏感的相似性度量，引入另外一個參數(shù)，將密度信息引入到聚類中，避免人為設置高斯核參數(shù)，但限制信息是由人任意提供的，提供的限制信息不一定起到積極的指導作用；此外，文獻[15-17]也提出了相關算法。

在上述研究的基礎上，借鑒基于密度和近鄰傳播的思想，文中提出一種基于自然鄰的自適應譜聚類算法。該算法利用自然鄰產(chǎn)生的局部密度信息和近鄰關系對高斯函數(shù)進行修正，并獲取相應的聚類數(shù)目，使得譜聚類算法真正實現(xiàn)自適應。并通過仿真對該算法的聚類效果進行驗證。

1 相關算法

1.1譜聚類算法

譜聚類算法是一種基于圖論的分割問題。該算法將數(shù)據(jù)點映射為帶權的無向圖，把樣本數(shù)據(jù)點對應于圖的節(jié)點，邊的權重則代表樣本點特征之間的相似性，然后利用某種分割準則得到圖的最佳劃分結果，將樣本點的聚類問題轉化為圖的分割問題。

譜聚類算法的處理過程如下所述：

Step1：根據(jù)相應的高斯核函數(shù)構造相似矩陣W；

Step2：計算出拉普拉斯矩陣并進行歸一化；

Step3：求出矩陣的最小的前k個特征向量以及對應的特征矩陣；

Step4：用k-means將k個特征向量進行聚類，得到最終結果。

在此過程中，高斯核函數(shù)的定義以及k值的確定是該算法聚類好壞的關鍵所在。而在原始的譜聚類算法中，這些都需要人為確定，勢必給聚類帶來非常大的困擾。

1.2自然鄰算法

自然鄰是一種最新尋找鄰居的方法，是一種無尺度的鄰域劃分，這也是它與k-近鄰與ε-近鄰的最大不同所在。自然鄰無需指定參數(shù)，自適應地找出自己周圍的鄰域。在了解自然鄰之前，先給出以下幾個概念：

定義1(自然鄰居)：對于數(shù)據(jù)X，如果數(shù)據(jù)X是數(shù)據(jù)Y的近鄰，那么就稱數(shù)據(jù)X是數(shù)據(jù)Y的自然鄰居。

定義2(自然逆鄰居)：對于數(shù)據(jù)X，如果數(shù)據(jù)X是數(shù)據(jù)Y的近鄰，那么就稱數(shù)據(jù)Y是數(shù)據(jù)X的自然逆鄰居。

定義3(自然鄰居連通分支數(shù))：由數(shù)據(jù)集X中的每個點i與自己所有的自然鄰居相連接構造出來的連通分支數(shù)。

定義4(自然逆鄰居連通分支數(shù))：由數(shù)據(jù)集X中的每個點i與自己所有的自然逆鄰居相連接構造出來的連通分支數(shù)。

自然鄰算法的基本思想是各點自適應地尋找自己的鄰居和逆鄰居，直到所有點都出現(xiàn)在其他點鄰域中為止；最后得出的是各點出現(xiàn)在其余點鄰域中的次數(shù)，出現(xiàn)的次數(shù)越多，說明該點分布在越密集處，反之則分布在較稀疏處。另外，還可以得到每個點的自然鄰居集和自然逆鄰居集。下面給出自然鄰算法的基本過程[18]。

輸入：數(shù)據(jù)集X

輸出：nb,supk,NN,RNN

r=1,flag=0

while(flag==0)

ifall(nb(i))≠0,then flag=1

else for ?i∈X

nnr(i)=getNNr(i,r)

nb(nnr(i))=nb(nnr(i))+1

RNNr(nnr(i))=RNNr(nnr(i))∪i

NNr(i)=NNr(i)∪nnr(i)

end for

r=r+1

end if

end while

自然鄰算法的終止條件是所有點都出現(xiàn)在別人的鄰域中，這樣在不需要人工干預的情況下獲取到數(shù)據(jù)點之間的相關信息，包括點周圍的自然逆鄰個數(shù)nb、數(shù)據(jù)集中平均每個點的逆鄰居數(shù)supk、自然鄰居集NN以及自然逆鄰居集RNN。

2 基于自然鄰的自適應譜聚類算法

2.1改進思路

構造出可靠的相似矩陣W，為后面k-means聚類提供有力的聚類依據(jù)。原始譜聚類算法中相似矩陣是通過以下的高斯函數(shù)來實現(xiàn)的：

(1)

其中，d(i,j)表示數(shù)據(jù)點i與j之間的歐氏距離；σ是需要輸入的尺度參數(shù)；

圖1中數(shù)據(jù)點分布在以a為中心點的圓圈內(nèi)，b和c到a的距離相等，但b處于與a密度較為接近的稠密區(qū)，而c屬于稀疏區(qū)。

圖1 數(shù)據(jù)點分布圖(1)

最原始的譜聚類算法中，僅僅利用了數(shù)據(jù)點之間的距離信息來構造相似函數(shù)，得出Wab=Wac,但實際上應該是Wab>Wac。這就需要將密度信息引入，而1.2節(jié)的自然鄰算法，剛好可以獲得一個密度信息nb。nb越大，表示它周圍數(shù)據(jù)點越密集，反之越稀疏。

為此，定義了一個新的相似度構造函數(shù)：

(2)

(3)

(4)

其中，nb(i)表示點i的自然鄰個數(shù)；max(nb)表示數(shù)據(jù)集中最大的nb值。

按照式(2)得出的相似矩陣，在相同距離下，通過rate(i,j)對相似度進行調(diào)整，同處高密度區(qū)域的點間相似度更大。

雖然上述改進確實更加符合實際情況，但是當數(shù)據(jù)點如圖3分布時，a、b、c三處密度相等，a獨處右側簇中，而b、c處于左側簇中。

圖2 數(shù)據(jù)點分布圖(2)

按式(2)計算相似矩陣，則Wab=Wbc,這與實際情況不相符，b、c處于同一個簇，a、b處于不同簇，實際上應該是Wab

圖2中，僅僅利用點與點之間的先驗信息還是難以構造出理想的相似矩陣。算法1.2的輸出中還有NN與RNN，這兩個信息能更加具體地表示點與點之間的近鄰信息。按照近鄰傳播思想，在NN或RNN上進行擴展，必然能夠得到更多初步的先驗信息。下面給出在自然鄰算法輸出的鄰域中擴展的基本步驟。

Step1：任意選取數(shù)據(jù)集X中一點i，C的值設為0；

Step2：檢測點i是否被訪問過，若沒有訪問則更新該點的訪問狀態(tài)，C自增一；若訪問過則轉步驟4；

Step3：對點i鄰域中的每一點j進行深度遍歷，更新相關點的訪問狀態(tài)，直到鄰域中所有點被訪問；

Step4：檢測數(shù)據(jù)集中是否還存在未訪問的點，若存在則轉到步驟2；如不存在則結束。

上述算法中，C值用來標記在同一個擴展區(qū)域所有的點，所有點之間的近鄰信息用式(5)表示。

定義5(近鄰信息)：將各點之間的近鄰信息按以下規(guī)則記錄：

(5)

將flag引入相似矩陣的構造中，處于不同擴展鄰域中的相似度大大減小，處于相同擴展鄰域中的相似度顯著增大。

為此再次更改之前的相似矩陣構造函數(shù)：

(6)

(7)

式(6)是在(4)的基礎上，加上flag的先驗信息；式(7)計算出的相似矩陣更能貼切地反映實際數(shù)據(jù)點之間的關系，處于同一鄰域中的高密度點相似度增大，而處于不同的鄰域的高密度點相似度減小。

在近鄰擴展的過程中，必然會將數(shù)據(jù)集劃分為幾個塊，這樣的塊與所需要的聚類數(shù)目存在某種必然聯(lián)系。算法中的C值，某種程度上就是聚類數(shù)目。為了可視化該過程中的問題，給出一個簡單的實例進行模擬。a、b、c、d、e五個點都在一個類，具體分布如圖3所示，a、b、c三點距離較近，與d、e兩點距離稍遠。

圖3 數(shù)據(jù)點分布圖(3) 表1 數(shù)據(jù)集輸出信息表

頂點nbNNRNNa2{b,c}{b,c}b2{a,c}{a,c}c4{a,b}{a,b,d,e}d1{e,c}{e}e1{d,c}zvhv5vb

表1顯示的是圖3數(shù)據(jù)集在自然鄰算法后得出的信息。按照擴展鄰域的思想，上述數(shù)據(jù)集選取a點開始在自然近鄰NN上進行擴充，得到的是C=2，其中a、b、c為一類，d、e為另一類；若選取d點開始，得到的結果是C=1。同樣在逆近鄰集RNN上擴充，不同的輸入順序也得到不同的聚類數(shù)目。

由此可以看出，聚類結果的好壞與數(shù)據(jù)點輸入順序有關，使得該算法的穩(wěn)定性不強；針對這樣一個問題，提出了自然全鄰居的概念。

定義6(自然全鄰居)：對于數(shù)據(jù)集X中的每個點i，點i的全鄰居是由自己所有的自然鄰居和自然逆鄰居組成，記為SNN。

定義7(自然全鄰居連同分支數(shù))：由數(shù)據(jù)集X中的每個點i與SNN中各點相連接構造出來的連通分支數(shù)。

將上述數(shù)據(jù)集在自然全鄰居中進行擴充，若選取a點開始，得出的結果是C=1；若選取d點開始，得到的結果也是C=1;這樣算法的穩(wěn)定性就得以保證。上述得到的自然全鄰居連通分支數(shù)就作為譜聚類算法中聚類的數(shù)目。

2.2具體算法的實現(xiàn)過程

輸入：數(shù)據(jù)點集X；

輸出：數(shù)據(jù)點的劃分。

算法步驟：

Step1：按照1.2節(jié)算法計算nb,supk,NN,RNN;

Step2：依據(jù)2.1中的擴充原理進行擴充，并得到相應的C值和近鄰信息flag;

Step3：根據(jù)式(7)計算出相似矩陣的值W;

Step5：獲取前C個最大特征值對應的特征向量并進行歸一化處理，得到X=[x1,x2,…,xc];

Step6：將X中的每一行看做一個點，對其使用k-means算法聚成C類;

Step7：若X中的第i行屬于第C類，那么將Xi劃分到第C類。

3 實驗結果與分析

3.1有效性實驗

為了驗證文中提出算法的有效性，選擇了4個具有代表性的人工數(shù)據(jù)集進行測試。在4個數(shù)據(jù)集上進行聚類，聚類效果如圖4所示，不同簇類使用不同標識標注。

從圖4可以看出，基于自然鄰自適應譜聚類算法可以很好地區(qū)分出不同的簇類，聚類效果理想。

圖4 文中算法在不同數(shù)據(jù)集上的聚類效果

3.2對比性實驗

為了對比分析文中算法與原始譜聚類算法，分別在一些典型且分布不同的數(shù)據(jù)集上進行測試。

原始譜聚類算法需要手動設置尺度參數(shù)和聚類數(shù)目。在聚類過程中，數(shù)據(jù)集(a)設置了σ∈[10,100]和C=3；數(shù)據(jù)集(b)設置了σ∈[10,100]和C=4；數(shù)據(jù)集(c)設置了σ=10和C=2；數(shù)據(jù)集(d)設置了σ∈[10,100]和C=5。

圖5 兩種算法結果的對比

圖5為兩個算法的聚類效果。原始的譜聚類算法不僅需要手動設置參數(shù)，而且在流型數(shù)據(jù)集上的效果不理想；文中算法完全不需要人為輸入?yún)?shù)，且聚類效果較為理想。

根據(jù)圖5，分別對兩種算法統(tǒng)計在4個數(shù)據(jù)集聚類后出現(xiàn)的誤分點個數(shù)。無論如何設置尺度參數(shù)和聚類數(shù)目，譜聚類算法的誤分率都高達30%甚至更高，聚類效果也不理想。而文中算法在4個數(shù)據(jù)集上都未出現(xiàn)誤分點數(shù)，且不需要人工干預。

在時間復雜度方面，原始譜聚類算法的時間復雜度為O(n2)。文中算法的時間由兩部分構成：一部分是自然鄰算法的時間，一部分是后面聚類算法的時間，即為O(nlogn)+O(n2)=O(n2)。在n較大時，兩種算法的時間復雜度幾乎是相等的。

由此看見，相比原始譜聚類算法，提出的基于自然鄰的自適應譜聚類算法具有一定的優(yōu)越性。

4 結束語

將譜聚類算法與自然鄰算法相結合，提出了基于自然鄰的自適應譜聚類算法，嘗試使用自然鄰算法得到更多數(shù)據(jù)點間的先驗信息，將該信息進一步轉化到相似矩陣的構造和聚類數(shù)目的確定上。該算法實現(xiàn)了完全的自適應，只需輸入數(shù)據(jù)點，便能輸出較為理想的聚類效果。在多個數(shù)據(jù)集上的對比實驗結果表明，該算法聚類效果理想，具有一定的優(yōu)越性和有效性。降低時間復雜度將是下一步研究的問題。

[1] Hastie T,Tibshirani R,Friedman J J H.The elements of statistical learning[M].New York:Springer,2001:460-514.

[2] Fiedler M.Algebraic connectivity of graphs[J].Czechoslovak Mathematical Journal,1973,23:298-305.

[3] 張向榮,騫曉雪,焦李成.基于免疫譜聚類的圖像分割[J].軟件學報,2010,21(9):2196-2205.

[4] 徐 森,盧志茂,顧國昌.解決文本聚類集成問題的兩個譜算法[J].自動化學報,2009,35(7):997-1002.

[5] 高 琰,谷士文,唐 琎,等.機器學習中譜聚類方法的研究[J].計算機科學,2007,34(2):201-203.

[6] 王 磊.一種改進的半監(jiān)督譜聚類算法[J].商洛學院學報,2013,27(4):55-58.

[7] 吳 希,牛新宇.限制性半監(jiān)督譜聚類算法[J].中國科技信息,2013(23):47-49.

[8] 卜德云,張道強.自適應譜聚類算法研究[J].山東大學學報:工學版,2009,39(5):22-26.

[9] 蔡曉妍,戴冠中,楊黎斌.譜聚類算法綜述[J].計算機科學,2008,35(7):14-18.

[10] 李 揚,陸 璐,崔紅霞.譜聚類圖像分割中相似度矩陣構造研究[J].計算機技術與發(fā)展,2016,26(7):55-58.

[11] Ng A Y,Jordan M I,Weiss Y.On spectral clustering:analysis and an algorithm[C]//Proceedings of advances in neural information processing systems.[s.l.]:MIT Press,2001:849-856.

[12] Zelnik-Manor L,Perona P.Self-tuning spectral clustering[C]//Advances in neural information processing systems.[s.l.]:MIT Press,2004:1601-1608.

[13] Chang H,Yeung D Y.Robust path-based spectral clustering with application to image segmentation[C]//Tenth international conference on computer vision.[s.l.]:IEEE,2005:278-285.

[14] 王 玲,薄列峰,焦李成.密度敏感的半監(jiān)督譜聚類[J].軟件學報,2007,18(10):2412-2422.

[15] Yang P,Zhu Q H,Huang B.Spectral clustering with density sensitive similarity function[J].Knowledge-Based Systems,2011,24(5):621-628.

[16] Shang F H,Jiao L C,Shi J R,et al.Fast affinity propagation clustering:a multilevel approach[J].Pattern Recognition,2012,45(1):474-486.

[17] 李志偉.基于近鄰傳播與密度信息的譜聚類算法研究與應用[D].無錫:江南大學,2014.

[18] 黃金龍.基于自然最近鄰的無參聚類算法研究[D].重慶:重慶大學,2014.

AnAdaptiveSpectralClusteringAlgorithmBasedonNaturalNeighbor

ZHU Qing-sheng，F(xiàn)U Piao-piao，ZHANG Cheng

(School of Computer Science,Chongqing University,Chongqing 400044,China)

In traditional spectral clustering algorithm,the input scaling parameters are needed to construct the similar matrix.In addition,the exact number of clusters is needed to be input in the subsequentk-means process.The above two parameters have a huge influence on the clustering effect.Aiming at the above problems,an adaptive spectral clustering algorithm based on natural neighbors is proposed.It does not need to input any parameters artificially and can achieve complete self-adaptation,the main way of which is to obtain the proximity information between the points by the natural neighbor algorithm,including the number of natural neighbors and inverse natural neighbors,the natural neighbor sets and the inverse natural neighbor sets.Through the case analysis,in the multi-scale or popular data set,the above priori information is made full use of to construct a similarity matrix more consistent with the actual situation.In addition,the number of clusters is gained according to the idea of spread of neighbors.The algorithm is applied to some artificial data sets,and compared with the spectral clustering algorithm,improving the clustering effect remarkably.Experimental results show that it has certain validity and superiority.

spectral clustering;natural neighbor;adaptive;scaling parameter;number of clustering

2016-11-29

2017-03-31 < class="emphasis_bold">網(wǎng)絡出版時間

時間：2017-08-01

重慶市基礎與前沿研究計劃項目(cstc2013jcyjA40049)

朱慶生(1960-)，男，博士，教授，研究方向為面向服務的軟件工程、離群檢測與數(shù)據(jù)挖掘；付飄飄(1991-)，女，碩士，研究方向為聚類分析。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1553.052.html

TP301

A

1673-629X(2017)11-0019-05

10.3969/j.issn.1673-629X.2017.11.004