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

史佳昕，朱慶生

（重慶大學計算機學院，重慶 400044）

0 引言

聚類分析作為一種重要的無監督學習方法，是人們探索和認知事物之間內在聯系的重要方式。聚類是將數據對象分為多個不同的子簇，使得同一簇中的對象之間具有較高的相似性，而不同簇中的對象差別較大[1]。傳統的聚類算法如K-means算法和EM算法等，對凸球形的數據分布樣本空間聚類效果好，但是對于形狀為非凸形的樣本容易陷入局部最優，聚類效果欠佳。譜聚類算法給聚類提供了一個新的思路[2]，是近年來提出的一類新型熱門算法，與傳統的聚類算法不同的是，它是基于圖論理論，主要通過求解圖的最優劃分問題從而得到最優的結果，能夠在任意形狀的樣本數據聚類并且收斂于全局最優解[3]。譜聚類在圖像分割、文本挖掘、模式識別等領域被廣泛應用[2]。

文獻[4]提出一種基于自適應模糊均值和改進Ncut的譜聚類算法，但是有較高的計算復雜度。Ra[5]提出一種用加權PageRank選取具有代表性的點進行譜聚類，提高了其可擴展性。文獻[6]提到用K-means的密度估計法來構成相似矩陣，提高了密度估計的準確性，缺點是參數過多。Li等[7]提出約束譜聚類的Nystrom方法，但是約束性參數會影響聚類結果。

在上述研究的基礎上，借鑒共享近鄰的思想，文中提出了一種基于共享自然近鄰的自適應譜聚類算法。該算法利用自然鄰產生的自然特征值與共享近鄰結合，對相似度矩陣重新定義，使得對參數不再敏感，最后通過不同的實驗驗證了算法的有效性和準確性。

1 相關理論

1. 1 譜聚類算法基本原理

譜聚類將研究對象視為頂點，為頂點之間的邊賦予權重，權重用對象間的相似度來表示。使用圖分割解決聚類問題：尋找最優圖分割的方法，使得分割之后連接簇與簇之間邊的權重盡量小，簇內邊之間的權重盡可能大。目前，常見的譜聚類算法有Ncut算法[8]和NJW[7]算法等。本文基于NJW算法闡述譜聚類的基本思想。設定原始數據集D={x1,x2,…,xn}∈Rd中的每一個樣本點看作無向圖中的頂點，記為V，根據樣本點間的相似度將頂點之間的邊E賦權值得到相似度矩陣W，由此構造了一個基于樣本間相似度的無向加權圖G=（V，E，W）。譜聚類算法可以歸納以下四個基本步驟：

（1）根據待聚類的數據集D生成圖的相似度矩陣W，其中每個元素Wij可以用高斯核函數來表示，即：

其中：d(xi-xj)表示數據點xi和xj之間的距離，σ為尺度參數。不同的尺度參數可能會導致不同聚類結果，需人為設定，且聚類效果對參數很敏感，對于多重尺度數據集很難得到滿意的聚類結果。

（2）計算拉普拉斯矩陣，并進行歸一化，其中D為度矩陣；

（3）對L進行特征分解，得到前K個特征向量，并構建特征向量空間；

（4）利用經典的聚類方法如K-means對特征向量進行聚類。

1. 2 自然鄰

自然鄰是近幾年才提出的一種新型的近鄰概念[9]，區別于k-最近鄰居和?-最近鄰居在于它不需要人為的設置參數，而是在不斷的擴大鄰域搜索范圍的過程中自適應得出。該方法受到社會關系的啟發，針對數據對象而言，假設數據對象y把x當作鄰居，同時x也把y當作鄰居，那么x和y互為自然鄰居。如果數據集中每個點都有一個自然鄰居，則可以達到一個穩定的狀態。

定義1：（自然穩定狀態）搜索數據集中每個數據對象 p∈D的k-最近鄰居，k依次取1,2,3,…,N。若k增長至SUPK時，數據集D中的任意點都至少存在一個逆近鄰，或者當數據集中逆近鄰數為0的數據點不變時，稱為自然穩定狀態。

根據以上定義，自然鄰搜索算法的過程具體如下：

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

2. 1 改進相似度度量

本文借鑒了Liu提出的共享近鄰的概念[10]來重新定義了兩點間的相似度。通過上述自然鄰搜索算法得出的自然特征值，來確定數據集中每個點的鄰域范圍。

定義2：（數據點之間的共享近鄰SNN）對于數據集D中的任意點i和點j，點i的SUPK近鄰集合為3NL（i），點 j的 SUPK 近鄰集合為 3NL（j）。數據集 D中的任意點i和j的共享近鄰是兩個點鄰域的交集，表示為：

定義3：（基于共享近鄰的相似度S）對于數據集中D中的任意點i和j，其共享近鄰相似度定義為：

其中dist是點i和j之間的距離，相似度僅在點i和j出現在彼此的SUPK近鄰時計算，否則，點i和j的相似性為0。

上述公式我們可以進行變換從而清楚地看到共享近鄰相似度的含義。

左邊的一部分代表點i和j的共享鄰域數，右邊是點i和j到所有共享鄰域距離均值的倒數，在一定程度上代表了這兩個點周圍的密度。通過同時得到共享鄰域和兩個點的密度，共享近鄰相似度可以更好地適應各種變換的數據集。

經典的譜聚類算法中主要是高斯核函數來作為相似度函數從而形成相似度矩陣，使其更加接近原始的相似度矩陣。理想狀態下，同一類中的點很相似，相似度接近1；反之兩點不相似，相似度接近0。對比經典的高斯核函數計算相似度和本文提到的改進相似度，原始的高斯核函數，尺度參數的選擇可能會導致不同聚類結果，需人為設定；針對所有數據點來計算相似度使用了統一的參數，會在螺旋數據集上無法識別相互纏繞的簇。而本文改進的相似度可以通過兩點是否存在共享近鄰來動態判斷兩點之間的相似度關系彌補了上述單一尺度參數的缺點，同時在共享近鄰的基礎上，還考慮到兩點到共享近鄰的距離，來反映兩點周圍的密度使得其包含真實的聚類信息，有利于可以發現真實的簇分布，得到正確的聚類結果。

2. 2 算法過程

根據以上定義，基于共享自然近鄰的自適應譜聚類的過程具體如下:

輸入：數據集D,聚類數C

輸出：每個數據對象P的類標記

1.對數據進行自然鄰搜索算法，得到SUPK值和每個點的鄰域范圍

2.根據共享近鄰，構建相似度矩陣S

3.構建拉普拉斯矩陣,其中D為對角矩陣

4.計算前C個特征值所對應的特征向量

5.通過特征向量構成矩陣，用K-means進行聚類

6.將原始數據點分配到各自所在的類中，得到對應類標記

3 實驗分析

3. 1 人工數據集

首先通過4個人工數據集進行實驗來驗證算法的有效性和可行性，其中Dataset1（Aggregation）表示一個包含7類的N=788的球狀數據集；Dataset2（Moon）表示包含2類的N=1000的弧形數據集；Dataset3（Spiral）表示一個包含3類的N=312的螺旋形數據集；Dataset4（Db2）表示一個包含4類的N=315的條狀數據集。下面給出具體的數據點分布圖1。

為了驗證該算法的有效性，分別在人工數據集和真實數據集上，對標準譜聚類算法（NJW）、自調節譜聚類算法（STSC）[11]、共享近鄰的譜聚類算法（SNN-SC）[12]和本文算法（簡記為SNaN-SC）進行了對比實驗。

圖1 不同算法的聚類結果

各算法在4個數據集上的聚類效果如圖1，其中圖1中第一列（a）是算法NJW的聚類效果，第二列（b）是算法STSC的聚類效果，第三列（c）是算法SNN-SC的聚類效果圖，第四列（d）是算法3NS-SC的聚類效果。NJW算法需要人工設定σ值，按照文獻給出的方法，設定σ的值為數據點之間歐氏距離變化范圍dist=max(D)-min(D)的10%～20%，這 里 我 們 取σ=0.1dist來進行實驗。STSC算法參數k為[2，50]中最優值，參考文獻中建議的經驗值p=7附近來進行實驗[12]。SNN-SC算法中需要設定兩個參數，p也取7，參數kd選取的范圍值為5-25。

對比分析可知，本文提出的SNaN-SC算法在四個人工數據集上均能正確聚類；在Dataset1、Dataset2和Datase4數據集上，本算法聚類效果明顯，而其他三個算法均出現不同程度的錯誤聚類；在DataSet3數據集上，NJW算法無法正確聚類，剩余三個算法聚類效果較好，但是在STSC算法結果上存在幾個誤差。NJW算法的相似矩陣完全是基于距離的，所以聚類結果在流行數據集上效果明顯下降；STSC算法的相似矩陣考慮了密度和距離的關系，在數據集Dataset3上效果明顯，在Dataset4上只能將一個范圍內的數據分開，雖然考慮了數據點鄰域的關系，但在弧形數據集上效果不好；同樣針對流行數據集，流行間隙大且密度較高，SNNSC算法聚類效果理想，但也會受到參數的影響。而本文提出的算法將共享近鄰來計算相似矩陣，而且只計算共享范圍內的數據點，獲得了更加符合實際情況的鄰域信息，而且減弱了遠范圍點對聚類的影響。聚類結果充分可以體現本文算法的優越性。

3. 2 UCI真實數據集

此外本文還選取了3個UCI數據集進行實驗，以驗證算法的有效性。表3展示了真實數據集的特征。不同的評價標準會突出聚類算法的不同特性，本實驗選取RI指標[13]和NMI指標[14]作為評價標準。

四種算法在RI評價標準下的對比實驗結果如表4所示。RI的值越高，說明聚類效果越好。分析實驗結果，發現：SNN-SC在Iris和Glass數據集上的RI指標相比NJW算法和STSC算法，取得了較好的聚類結果。而本文算法3NS-SC算法在三個數據集上取得很好的結果，得益于新的相似度量考慮自然領域和數據集點之間的局部信息對相似度的影響，有利于挖掘數據點間內在關系。

四種算法在NMI評價標準下的對比實驗結果如表5所示。由于針對真實數據集很難找到合適的參數，而且其余三個算法的性能依賴于對參數的設定。本文算法SNaN-SC在四個數據集上較其他算法的NMI值都高。評價標準的側重點不同或是數據集自身的特點導致Glass數據集上用RI進行評價時，SNN-SC性能最好，但是NMI評價時，該算法性能并不比我們的算法好。因此，從兩種評價結果來看，相較于其他算法相比，SNaN-SC算法在真實數據集上具有更好的性能。

表3 UCI真實數據集

表4 算法在真實數據集上的RI對比

表5 算法在真實數據集上的NMI對比

4 結語

本文通過引入自然鄰概念自動確定鄰域個數，利用數據之間的共享近鄰和距離信息重新定義了相似度計算，提出了基于共享自然鄰的自適應譜聚類算法。該相似度能夠有效描述數據之間的實際分布和內在聯系。通過人工數據集和真實數據集的實驗對比分析，表明該方法比其他算法具有很強的自適應能力，且聚類準確率較高。下一步的研究重心將放在運行效率的提高上。