葛君偉，楊廣欣

（重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065）

0 概述

聚類是將數(shù)據(jù)按照一定的相似性度量規(guī)則分為多個(gè)不同的類別，將差異小的樣本盡可能聚為同一類，將差異大的樣本聚為不同的類。聚類算法在處理數(shù)據(jù)之前無需指定數(shù)據(jù)集的標(biāo)簽信息，屬于無監(jiān)督的機(jī)器學(xué)習(xí)領(lǐng)域，被廣泛應(yīng)用在圖像處理和模式識(shí)別等領(lǐng)域［1］。根據(jù)算法特點(diǎn)大致分為基于劃分的聚類算法（如K-means 算法）、基于層次的聚類算法（如BIRCHIS 算法）、基于密度的聚類算法（如DBSCAN 算法）、基于網(wǎng)格的聚類算法（如STING 算法等［2］）。對(duì)于凸數(shù)據(jù)集，許多聚類算法都能獲得較好的聚類效果，但是對(duì)于非凸數(shù)據(jù)集則難以識(shí)別復(fù)雜的數(shù)據(jù)集從而無法很好的聚類。由于譜聚類算法在非凸數(shù)據(jù)集上有較好的聚類效果，近年譜聚類算法的研究迅猛發(fā)展［3-4］。譜聚類算法將數(shù)據(jù)集中的每個(gè)點(diǎn)視為圖的頂點(diǎn)，并將任意兩點(diǎn)之間的相似性視為連接兩個(gè)頂點(diǎn)的邊的權(quán)重。根據(jù)圖劃分方法，將圖分為幾個(gè)不連續(xù)的子圖，子圖中包含的點(diǎn)集則是聚類后生成的簇［5］。

盡管譜聚類算法在實(shí)踐中取得了良好的性能，但作為一種新的聚類方法仍處于發(fā)展階段，有許多問題需要進(jìn)一步研究。譜聚類算法的聚類性能主要由相似性矩陣的構(gòu)造決定。在現(xiàn)有相似性矩陣的研究中，大多數(shù)研究都是基于歐幾里得距離、余弦相似度或高斯核函數(shù)來評(píng)估數(shù)據(jù)點(diǎn)之間的相似度。文獻(xiàn)［6］提出一種基于數(shù)據(jù)本身蘊(yùn)含信息的集成度量學(xué)習(xí)方法的譜聚類算法。文獻(xiàn)［7］通過將數(shù)據(jù)集樣本表示為稀疏的線性組合，通過構(gòu)造最優(yōu)化問題的模型，使該方法能較好地反映數(shù)據(jù)空間的局部一致性，從而提升系統(tǒng)的魯棒性。文獻(xiàn)［8］提出一種自適應(yīng)譜聚類技術(shù)，用于處理多尺度數(shù)據(jù)集，它沒有選擇全局參數(shù)σ，而是根據(jù)每個(gè)點(diǎn)的鄰域信息計(jì)算自適應(yīng)參數(shù)。文獻(xiàn)［9］通過局部密度獲得數(shù)據(jù)中隱含的簇結(jié)構(gòu)特征，結(jié)合自調(diào)整高斯核函數(shù)，提出一種基于共享鄰域自適應(yīng)相似度的譜聚類算法。文獻(xiàn)［10］提出流形結(jié)構(gòu)數(shù)據(jù)點(diǎn)之間的相似度計(jì)算方法，以提高算法的聚類性能。文獻(xiàn)［11］致力于找到核參數(shù)σ的最佳值以改進(jìn)譜聚類算法，但最佳值是一個(gè)全局值，不適用具有密度的簇?cái)?shù)據(jù)集。文獻(xiàn)［12］提出一種翹曲模型，用于將數(shù)據(jù)映射到新的空間，以更準(zhǔn)確進(jìn)行相似性度量。文獻(xiàn)［13］使用數(shù)據(jù)點(diǎn)之間的局部密度來縮放參數(shù)，具有放大集群內(nèi)相似性的作用。文獻(xiàn)［14］基于數(shù)據(jù)點(diǎn)之間的最大流量來測(cè)量相似度，以滿足譜聚類算法中使用相似度度量的要求。文獻(xiàn)［15］將相對(duì)密度敏感項(xiàng)引入相似性度量，在滿足全局和局部一致性的同時(shí)，通過相對(duì)密度敏感項(xiàng)能有效規(guī)避噪聲點(diǎn)對(duì)樣本空間的干擾，尤其是對(duì)于“橋”噪聲。文獻(xiàn)［16］通過截?cái)嗪朔稊?shù)的低秩張量分解方法。計(jì)算各視角的樣本相似度矩陣和轉(zhuǎn)移概率矩陣，從而解決譜聚類算法的多視角問題。

對(duì)于構(gòu)造譜聚類算法中相似性矩陣，目前研究大多采用K 最近鄰（K-Nearest Neighbor，KNN）圖構(gòu)建相似圖，并基于密度敏感項(xiàng)改進(jìn)的歐幾里得距離相似性度量來評(píng)價(jià)樣本點(diǎn)之間的相似性。然而基于KNN 圖構(gòu)建的相似圖通常會(huì)引入冗余連接，并且易受噪聲影響，噪聲樣本點(diǎn)使聚類質(zhì)心不準(zhǔn)確。這兩個(gè)因素會(huì)降低譜聚類性能使其出現(xiàn)錯(cuò)誤的聚類結(jié)果［17］，需根據(jù)經(jīng)驗(yàn)確定K 最近鄰的值，使最終聚類效果具有不確定性?；跉W幾里得距離的相似性度量也存在著無法揭示某些復(fù)雜數(shù)據(jù)集的真實(shí)簇的問題，尤其是不能很好地分離數(shù)據(jù)集。因不同群集中某些數(shù)據(jù)點(diǎn)相距不遠(yuǎn)，噪聲的存在也會(huì)使數(shù)據(jù)集無法很好地分離。由于許多實(shí)際數(shù)據(jù)集沒有很好地分離，很難找到正確的聚類，因此提出一種對(duì)未分離的數(shù)據(jù)集具有魯棒性的聚類算法是十分必要。

本文以相似性矩陣構(gòu)造為切入點(diǎn)，提出一種基于共享鄰的密度自適應(yīng)鄰域譜聚類算法（SC-DANSN），構(gòu)建無需指定初始參數(shù)的相似圖，并將共享最近鄰作為樣本點(diǎn)之間的相似性度量，以減少噪聲信息在分離數(shù)據(jù)集上的影響，并解決譜聚類算法相似性度量無法準(zhǔn)確反映數(shù)據(jù)空間結(jié)構(gòu)的問題。

1 譜聚類

譜聚類是一種基于圖論的聚類方法。通過對(duì)數(shù)據(jù)集相似矩陣進(jìn)行譜分析得到較好的聚類結(jié)果。譜聚類的概念起源于譜劃分，譜劃分將數(shù)據(jù)聚類轉(zhuǎn)換為無向圖的多向劃分問題［18］。譜聚類算法將數(shù)據(jù)點(diǎn)定義為無向圖G=(V，E)的頂點(diǎn)，其中V是頂點(diǎn)集，E是頂點(diǎn)之間的邊集。建立圖上各頂點(diǎn)之間的相似度矩陣S，其元素Sij可被視為連接第i個(gè)數(shù)據(jù)點(diǎn)和第j個(gè)數(shù)據(jù)點(diǎn)的邊上的權(quán)重。相似度矩陣的元素Sij由高斯核函數(shù)表示：

其中，Pi和Pj分別表示第i個(gè)數(shù)據(jù)點(diǎn)和第j個(gè)數(shù)據(jù)點(diǎn)，而d2(Pi，Pj)表示Pi和Pj之間的歐幾里得距離，σ是確定數(shù)據(jù)點(diǎn)之間相似度的比例參數(shù)。NJW 算法使用歸一化相似度矩陣作為圖拉普拉斯矩陣，并通過考慮對(duì)應(yīng)于最大特征值的特征向量，基于歸一化割準(zhǔn)則優(yōu)化分區(qū)問題，譜聚類算法描述如下：

2 基于共享鄰的密度自適應(yīng)鄰域譜聚類

2.1 密度自適應(yīng)鄰域構(gòu)建算法

譜聚類算法主要是構(gòu)建相似性矩陣，在此之前，先構(gòu)建能反映樣本空間的無向圖。主要方法是基于KNN 圖或ε鄰域圖，其缺點(diǎn)是對(duì)參數(shù)的選取敏感，不能較好地反映數(shù)據(jù)空間。

聚類是基于相似性度量形成點(diǎn)組，因此同組內(nèi)的點(diǎn)之間相似度很高，而來自不同群體點(diǎn)的相似度很低。鄰居包括本地相似的點(diǎn)，因此數(shù)據(jù)點(diǎn)及其鄰居應(yīng)位于同一簇中。

在2 個(gè)數(shù)據(jù)集上使用KNN 和ε鄰域算法構(gòu)建的鄰域如圖1 所示。根據(jù)歐氏距離來衡量相似度，圖1（a）中有2 個(gè)簇。當(dāng)K≤3 時(shí)，簇2 中點(diǎn)i的KNN 鄰域包括來自同一簇的點(diǎn)，即點(diǎn)j，m和n；當(dāng)K≥4 時(shí)，簇1 中點(diǎn)p包含在點(diǎn)i的鄰域中。因此，KNN 無法提取點(diǎn)i和o之間超過點(diǎn)m的間接連接，并導(dǎo)致混合鄰域。圖1（b）中的數(shù)據(jù)集有3 個(gè)簇，其中1 個(gè)簇具有內(nèi)部密度變化。對(duì)于固定半徑ε，點(diǎn)s的鄰域包括來自同一簇簇1 的點(diǎn)，但是點(diǎn)r的鄰域?yàn)榭眨词顾皇请x群值也是如此。當(dāng)ε值增大時(shí)，點(diǎn)r不再是異常值，但點(diǎn)s的鄰域也增大，并引起了簇2 和簇3 的鄰域混合［19］。從圖1 可以看出，聚類問題中參數(shù)對(duì)鄰域方法的敏感性。

圖1 聚類問題示例鄰域的構(gòu)建Fig.1 Construction of example neighborhoods for clustering problem

本文采用一種密度自適應(yīng)的鄰域構(gòu)造（Neighborhood Construction，NC）算法克服KNN 和ε鄰域方法的局限性。算法的流程如圖2 所示。

圖2 密度自適應(yīng)鄰域構(gòu)建流程Fig.2 Construction process of density adaptive neighborhood

在構(gòu)建密度自適應(yīng)鄰域算法之前，定義以下概念：

D：代表一個(gè)數(shù)據(jù)集；

i，j，p：代表數(shù)據(jù)點(diǎn)；

dij：代表點(diǎn)i和j之間點(diǎn)歐氏距離；

CCi：代表點(diǎn)i的核心近鄰點(diǎn)；

BCi：代表點(diǎn)i的密度連接近鄰點(diǎn)；

PCi：代表點(diǎn)i的擴(kuò)展近鄰點(diǎn)；

CSi：代表點(diǎn)i的最終近鄰點(diǎn)；

B(i，j，dij)：以i和j為圓上兩點(diǎn)，dij為直徑，作一個(gè)圓，圓內(nèi)點(diǎn)的集合是B(i，j，dij)；

直接連接：當(dāng)且僅當(dāng)B(i，j，dij)∩D=?時(shí)，稱點(diǎn)i和j為直接連接，即i和j之間的集合B(i，j，dij)內(nèi)不存在任何點(diǎn)；

間接連接：如果B(i，j，dij)∩D≠?時(shí)，稱點(diǎn)i和j為間接連接，即i和j之間的集合B(i，j，dij)內(nèi)至少存在一個(gè)點(diǎn)；

Densityij：代表點(diǎn)i和j之間的密度，該值定義為集合B(i，j，dij)∩D內(nèi)點(diǎn)的個(gè)數(shù)。

NC 算法描述如下：

NC 算法最終輸出的密度自適應(yīng)鄰居集可以構(gòu)造密度自適應(yīng)的無向圖G=(V，E)，本文把圖G記為DAN（Density Adaptive Neighborhood）。構(gòu)造相似矩陣還需要對(duì)無向圖DAN 進(jìn)行加權(quán)，權(quán)重樣本點(diǎn)之間的相似性度量。

2.2 基于共享最近鄰的相似性度量

在構(gòu)建局部自適應(yīng)鄰域后可以生成無向圖。為實(shí)現(xiàn)譜聚類算法應(yīng)先對(duì)該無向圖加權(quán)，權(quán)重即為數(shù)據(jù)點(diǎn)之間的相似度。目前譜聚類算法廣泛使用基于歐氏距離的相似性度量，這種相似性度量有時(shí)難以反映數(shù)據(jù)點(diǎn)之間的真實(shí)相似程度［18］。因此考慮一種基于共享最近鄰的新相似性度量，并將其與局部自適應(yīng)鄰域構(gòu)建相結(jié)合，從而形成一種改進(jìn)的譜聚類算法。本文基于局部自適應(yīng)鄰域圖中共享的最近鄰來測(cè)量數(shù)據(jù)點(diǎn)之間的相似度。

設(shè)Ni表示局部自適應(yīng)鄰域圖中數(shù)據(jù)點(diǎn)Xi的鄰集。Xi與Xj之間共享鄰居的集合為Ni∩Nj，通過集合Ni∩Nj來測(cè)量成對(duì)相似度Sij。通常Ni不包括Xi，因此Ni∩Nj不包括兩個(gè)測(cè)量點(diǎn)Xi和Xj。Ni∩Nj是否包含Xi和Xj取決于Xi和Xj的關(guān)系，并影響相似性度量。在圖3（a）和圖3（b）中兩種不同情況下顯示點(diǎn)1和點(diǎn)2 的鄰居。在圖3（b）中，點(diǎn)1 和點(diǎn)2 是彼此的鄰居，在圖3（a）中則不是。如果不考慮點(diǎn)1 和點(diǎn)2 的關(guān)系，在兩種情況下點(diǎn)1 和點(diǎn)2 的共享鄰居集相同。因在圖3（b）中點(diǎn)1 和點(diǎn)2 是彼此的鄰居，圖3（b）中的點(diǎn)1 和點(diǎn)2 的相似度高于圖3（a）。

圖3 點(diǎn)1 和點(diǎn)2 的共享鄰居示意圖Fig.3 Schematic diagram of shared neighbors of point 1 and point 2

通過考慮兩個(gè)測(cè)量點(diǎn)之間的關(guān)系來重新定義圖中兩個(gè)點(diǎn)的共享鄰居集合。Ni是Xi的鄰居集合，并且不包括Xi。Ni∩Nj是點(diǎn)Xi和Xj之間共享鄰居的集合，其重新定義為：

根據(jù)式（2）定義共享鄰居的集合來測(cè)量成對(duì)相似性。許多基于共享鄰居的聚類方法都將成對(duì)相似性視為共享鄰居數(shù)量的函數(shù)。如果2 個(gè)數(shù)據(jù)點(diǎn)具有更多共享的鄰居，則它們具有較高的成對(duì)相似性。但僅考慮共享最近鄰居的數(shù)量可能會(huì)導(dǎo)致測(cè)量結(jié)果錯(cuò)誤。在2 種不同情況下點(diǎn)1 和點(diǎn)2 的3 個(gè)鄰居如圖4 所示。點(diǎn)1 和點(diǎn)2 在圖4（a）中具有2 個(gè)共享鄰居，而在圖4（b）中它們具有1 個(gè)共享鄰居。如果僅考慮共享鄰居數(shù)量，圖4（a）中的點(diǎn)1 和點(diǎn)2 的成對(duì)相似度高于圖4（b）中的點(diǎn)。圖4（b）中點(diǎn)1 和點(diǎn)2 非常接近，它們的成對(duì)相似度應(yīng)高于圖4（a）。因此僅考慮共享鄰居的數(shù)量可能會(huì)忽略數(shù)據(jù)點(diǎn)的緊密度。

圖4 點(diǎn)I 和點(diǎn)2 的3 個(gè)最近鄰居Fig.4 Three nearest neighbors of point 1 and point 2

為測(cè)量成對(duì)相似度Sij，根據(jù)Ni∩Nj中共享鄰居對(duì)數(shù)據(jù)點(diǎn)Xi和Xj的權(quán)重。令Wij表示Ni∩Nj中共享的鄰居的權(quán)重。令Xr為Ni∩Nj中共享的鄰居之一。假設(shè)Xr是Xi的第個(gè)鄰居和Xi的第個(gè)鄰居，則鄰居Wij的權(quán)重表達(dá)式為：

為了進(jìn)行統(tǒng)計(jì)分析，考慮在Sij∈［0，1］范圍內(nèi)的成對(duì)相似性。計(jì)算成對(duì)相似度Sij為：

相似矩陣S為：

通過對(duì)DAN 進(jìn)行加權(quán)構(gòu)建一種基于共享鄰的局部自適應(yīng)鄰域相似矩陣。

2.3 基于共享最近鄰的密度自適應(yīng)鄰域譜聚類

為提高傳統(tǒng)譜聚類算法對(duì)相似性矩陣構(gòu)造參數(shù)的敏感性，以及相似性度量難以準(zhǔn)確反映復(fù)雜數(shù)據(jù)和非凸數(shù)據(jù)的結(jié)構(gòu)，增加聚類算法結(jié)果的穩(wěn)定性。本文在原有譜聚類算法的基礎(chǔ)上，結(jié)合一種密度自適應(yīng)鄰域構(gòu)建方法，并通過共享最近鄰進(jìn)行樣本點(diǎn)的相似性衡量，提出一種新的基于共享近鄰的密度自適應(yīng)鄰域譜聚類算法SC-DANSN。利用密度自適應(yīng)鄰域構(gòu)建方法構(gòu)建無向圖DAN；通過最終鄰居集基于共享最近鄰對(duì)DAN 的邊進(jìn)行加權(quán)；生成相似矩陣，并計(jì)算相應(yīng)的拉普拉斯矩陣和度矩陣，再進(jìn)行特征向量的計(jì)算，最終通過K-means 算法進(jìn)行聚類得到最終的聚類結(jié)果。

SC-DANSN 算法主要由3 部分構(gòu)成，第1 部分為通過NC 算法構(gòu)造DAN 圖，具體分為5 步，步驟1 和步驟2 的時(shí)間復(fù)雜度由密度計(jì)算確定，該步驟的程序執(zhí)行次數(shù)與樣本點(diǎn)個(gè)數(shù)n成103增長(zhǎng)，即時(shí)間復(fù)雜度為O(n3)。步驟3 和步驟4 在整個(gè)過程中的時(shí)間復(fù)雜度為O(n2)。步驟5 在O(n2)時(shí)間內(nèi)檢查點(diǎn)與其鄰域的相互連通性，重復(fù)進(jìn)行直到鄰域不再變化。所以構(gòu)造DAN 圖即NC 算法的時(shí)間復(fù)雜度為O(n3)。第2 部分為測(cè)量成對(duì)相似的構(gòu)造相似性矩陣S，該部分的時(shí)間復(fù)雜度為O(n2d)，d表示數(shù)據(jù)集的維度即特征數(shù)目。第3 部分為聚類部分，采用K-means 算法，故該部分的時(shí)間復(fù)雜度為O(tkn)，t表示迭代次數(shù)，k表示類別數(shù)目。結(jié)合上述3 部分分析，由于構(gòu)建DAN 時(shí)的算法復(fù)雜度較高，本文所提算法SCDANSN 的時(shí)間復(fù)雜度為O(n3)比傳統(tǒng)譜聚類算法時(shí)間復(fù)雜度O(n2)高，

3 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)環(huán)境為Intel?CoreTMi7-6700HQ CPU@2.60 GHz，內(nèi)存為8.0 GB；編程環(huán)境為PyCharm；在Windows10 操作系統(tǒng)的計(jì)算機(jī)上進(jìn)行測(cè)試。通過在人工數(shù)據(jù)集和UCI 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，評(píng)估和分析所提算法。

為了比較和分析聚類結(jié)果，在以下實(shí)驗(yàn)中采用評(píng)估2 種聚類性能方法歸一化互信息（NMI）［18］和蘭德指數(shù)（RI）［20］。

歸一化互信息（NMI）被廣泛用于評(píng)估聚類算法性能。令C={C1，C2，…，CK}表示正確的聚類結(jié)果，C′=表示通過聚類算法獲得的預(yù)測(cè)聚類結(jié)果。P(ci)=|ci|/n是數(shù)據(jù)點(diǎn)屬于簇|ci|的概率，其中|ci|是簇ci的基數(shù)，n是數(shù)據(jù)點(diǎn)的總數(shù)。是數(shù)據(jù)點(diǎn)屬于群集ci和c′j交集的概率。NMI計(jì)算如下：

N值越大表示聚類結(jié)果越好，N最大為1，表示所有數(shù)據(jù)點(diǎn)均被正確分類。

蘭德指數(shù)（RI）用于測(cè)量2 個(gè)群集的相似性，考慮到同群集和不同群集中存在的數(shù)據(jù)點(diǎn)數(shù)量。RI 將群集標(biāo)簽分配視為數(shù)據(jù)點(diǎn)之間的成對(duì)關(guān)系，表明每對(duì)數(shù)據(jù)點(diǎn)可以分配給相同的群集，還可以屬于不同的群集。對(duì)于具有N個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集，RI 的計(jì)算如下：

其中，Nlk表示在U中屬于相同簇l的數(shù)據(jù)點(diǎn)和V中屬于相同簇k數(shù)據(jù)點(diǎn)的數(shù)量，Nl.表示分配給U中的相同簇l并屬于其中不同簇?cái)?shù)據(jù)點(diǎn)的數(shù)量，Nk.表示屬于U中不同簇并分配給V中的相同簇k數(shù)據(jù)點(diǎn)的數(shù)量。RI 的值在0～1，其中RI 值越高表示聚類效果越好。

3.1 人工合成數(shù)據(jù)集

在人工合成數(shù)據(jù)集中隨機(jī)選取4 個(gè)數(shù)據(jù)集，分別測(cè)試K-means、SC-KNN、SC-DANSN 算法的聚類效果。采用的數(shù)據(jù)集屬性如表1 所示。

表1 人工合成數(shù)據(jù)集參數(shù)設(shè)置Table 1 Parameters setting of artificial datasets

聚類結(jié)果如圖5～圖8 所示。在凸數(shù)據(jù)集Five_cluster，K-means、SC-KNN 和SC-DANSN 算法均能正確的聚類如圖7 所示，而在其他3 個(gè)非凸數(shù)據(jù)集，K-means 算法效果最差（見圖5、圖6、圖8）。本次實(shí)驗(yàn)固定SC-KNN 算法的核參數(shù)為5，K最近鄰為20即構(gòu)建相似圖時(shí)選取20 個(gè)最近的鄰居作為構(gòu)圖參數(shù)。由于SC-KNN 算法受限于相似矩陣構(gòu)建時(shí)參數(shù)的影響，聚類效果不穩(wěn)定，需要不斷地嘗試選擇參數(shù)來實(shí)現(xiàn)正確的聚類。本次實(shí)驗(yàn)中SC-DANSN 算法的共享最近鄰數(shù)量也設(shè)為20。由于SC-DANSN 算法采用一種密度自適應(yīng)鄰域方法來構(gòu)造相似圖，無需指定構(gòu)建相似圖的參數(shù)信息，只需指定共享最近鄰的數(shù)量以測(cè)量成對(duì)相似性。由于SC-DANSN 算法無參構(gòu)造相似圖的特性，無需像傳統(tǒng)譜聚類算法要不斷嘗試構(gòu)造相似圖的參數(shù)，所以其聚類效果穩(wěn)定并能正確聚類。對(duì)于加入噪聲的數(shù)據(jù)集Cluto_t4，SC-KNN 算法無論進(jìn)行何種調(diào)參，噪聲樣本都無法很好地分離。而SC-DANSN 算法通過引入共享最近鄰能較好地分離噪聲信息，在3 種算法中抗噪聲性能最優(yōu)。

圖5 ThreeCircles 數(shù)據(jù)集聚類結(jié)果Fig.5 The clustering results of ThreeCircles datasets

圖6 TwoMoons 數(shù)據(jù)集聚類結(jié)果Fig.6 The clustering results of TwoMoons datasets

圖7 Five_cluster 數(shù)據(jù)集聚類結(jié)果Fig.7 The clustering results of Five_cluster datasets

圖8 Cluto_t4 數(shù)據(jù)集聚類結(jié)果Fig.8 The clustering results of Cluto_t4 datasets

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

為進(jìn)一步驗(yàn)證SC-DANSN 算法的有效性，隨機(jī)選取UCI 機(jī)器學(xué)習(xí)庫(kù)的4 個(gè)真實(shí)數(shù)據(jù)集。4 個(gè)數(shù)據(jù)集的屬性如表2 所示。

表2 UCI 數(shù)據(jù)集參數(shù)設(shè)置Table 2 Parameters setting of UCI datasets

本次實(shí)驗(yàn)對(duì)每種數(shù)據(jù)集進(jìn)行10 次獨(dú)立的實(shí)驗(yàn)，對(duì)于SC-KNN、SC-DANSN 算法，取K值從5～50 步長(zhǎng)為5，K在SC-KNN 算法中代表K最近鄰數(shù)量，在SC-DANSN 算法中代表共享最近鄰的數(shù)量。經(jīng)過10 次獨(dú)立的試驗(yàn)后，K-means、SC-KNN、SC-DANSN算法在UCI 數(shù)據(jù)集的RI 和NMI 值的平均值如表3 所示。結(jié)果表明基于RI 和NMI 準(zhǔn)則，在4 種UCI 數(shù)據(jù)集中，SC-DANSN 算法的聚類效果最好，SC-KNN 次之，兩種算法聚類結(jié)果相似。由于K-means 基于劃分的聚類規(guī)則，對(duì)于非凸數(shù)據(jù)集分離效果不好，相比其他譜聚類算法，其聚類效果最差。

表3 UCI 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Table 3 Experimental results of UCI datasets

為驗(yàn)證SC-DANSN 算法對(duì)參數(shù)選擇的不敏感性，使用SC-DANSN 和SC-KNN 算法對(duì)4 個(gè)UCI 數(shù)據(jù)集的最近鄰數(shù)K的變化進(jìn)行聚類實(shí)驗(yàn)。SC-DANSN和SC-KNN 算法在K值選取4 個(gè)最佳結(jié)果時(shí)的敏感性如圖9～圖12 所示，可以看出，SC-DANSN 算法對(duì)參數(shù)K的敏感性更小。

圖9 Iris 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Fig.9 Experimental results of Iris dataset

圖10 Breast 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Fig.10 Experimental results of Breast dataset

圖11 Wine 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Fig.11 Experimental results of Wine dataset

圖12 Ecoli 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Fig.12 Experimental results of Ecoli dataset

4 結(jié)束語

本文提出一種基于共享最近鄰的密度自適應(yīng)鄰域譜聚類算法SC-DANSN，以降低譜聚類算法對(duì)構(gòu)造相似圖的參數(shù)敏感性并充分分離數(shù)據(jù)集。該算法的相似性度量是基于無向DAN 圖中共享的最近鄰居的接近度，與基于無向KNN 圖的傳統(tǒng)譜聚類算法相比，其對(duì)共享最近鄰居數(shù)K不敏感。實(shí)驗(yàn)結(jié)果表明，在人工合成數(shù)據(jù)集和UCI 真實(shí)數(shù)據(jù)集上，SC-DANSN 分離復(fù)雜結(jié)構(gòu)和含噪聲數(shù)據(jù)集的性能優(yōu)于傳統(tǒng)的譜聚類算法。下一步考慮使用分布式和并行算法構(gòu)造相似性矩陣并計(jì)算特征向量，并將譜聚類算法應(yīng)用于大數(shù)據(jù)集。