史佳昕，朱慶生

（重慶大學(xué)計算機學(xué)院，重慶 400044）

0 引言

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

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

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

1 相關(guān)理論

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

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

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

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

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

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

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

1. 2 自然鄰

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

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

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

2 基于共享自然近鄰的自適應(yīng)譜聚類算法

2. 1 改進相似度度量

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

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

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

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

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

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

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

2. 2 算法過程

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

輸入：數(shù)據(jù)集D,聚類數(shù)C

輸出：每個數(shù)據(jù)對象P的類標(biāo)記

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

2.根據(jù)共享近鄰，構(gòu)建相似度矩陣S

3.構(gòu)建拉普拉斯矩陣,其中D為對角矩陣

4.計算前C個特征值所對應(yīng)的特征向量

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

6.將原始數(shù)據(jù)點分配到各自所在的類中，得到對應(yīng)類標(biāo)記

3 實驗分析

3. 1 人工數(shù)據(jù)集

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

為了驗證該算法的有效性，分別在人工數(shù)據(jù)集和真實數(shù)據(jù)集上，對標(biāo)準(zhǔn)譜聚類算法（NJW）、自調(diào)節(jié)譜聚類算法（STSC）[11]、共享近鄰的譜聚類算法（SNN-SC）[12]和本文算法（簡記為SNaN-SC）進行了對比實驗。

圖1 不同算法的聚類結(jié)果

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

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

3. 2 UCI真實數(shù)據(jù)集

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

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

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

表3 UCI真實數(shù)據(jù)集

表4 算法在真實數(shù)據(jù)集上的RI對比

表5 算法在真實數(shù)據(jù)集上的NMI對比

4 結(jié)語

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