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

史佳昕，朱慶生

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

0 引言

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

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

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

1 相關(guān)理論

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

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

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

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

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

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

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

1. 2 自然鄰

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

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

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

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

2. 1 改進(jìn)相似度度量

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

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

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

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

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

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

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

2. 2 算法過程

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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