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

朱慶生，付飄飄，張 程

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

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

朱慶生，付飄飄，張 程

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

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

譜聚類;自然鄰;自適應;尺度參數;聚類數目

0 引 言

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

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

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

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

1 相關算法

1.1譜聚類算法

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

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

Step1：根據相應的高斯核函數構造相似矩陣W；

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

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

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

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

1.2自然鄰算法

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

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

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

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

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

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

輸入：數據集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

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

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

2.1改進思路

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

(1)

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

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

圖1 數據點分布圖(1)

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

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

(2)

(3)

(4)

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

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

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

圖2 數據點分布圖(2)

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

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

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

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

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

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

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

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

(5)

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

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

(6)

(7)

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

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

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

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

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

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

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

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

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

2.2具體算法的實現過程

輸入：數據點集X；

輸出：數據點的劃分。

算法步驟：

Step1：按照1.2節算法計算nb,supk,NN,RNN;

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

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

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

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

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

3 實驗結果與分析

3.1有效性實驗

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

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

圖4 文中算法在不同數據集上的聚類效果

3.2對比性實驗

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

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

圖5 兩種算法結果的對比

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

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

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

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

4 結束語

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

[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] 王 磊.一種改進的半監督譜聚類算法[J].商洛學院學報,2013,27(4):55-58.

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

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

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

[10] 李 揚,陸 璐,崔紅霞.譜聚類圖像分割中相似度矩陣構造研究[J].計算機技術與發展,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] 王 玲,薄列峰,焦李成.密度敏感的半監督譜聚類[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，FU 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">網絡出版時間

時間：2017-08-01

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

朱慶生(1960-)，男，博士，教授，研究方向為面向服務的軟件工程、離群檢測與數據挖掘；付飄飄(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