基于共享最近鄰的密度自適應鄰域譜聚類算法

葛君偉，楊廣欣

（重慶郵電大學計算機科學與技術學院，重慶 400065）

0 概述

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

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

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

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

1 譜聚類

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

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

2 基于共享鄰的密度自適應鄰域譜聚類

2.1 密度自適應鄰域構建算法

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

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

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

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

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

圖2 密度自適應鄰域構建流程Fig.2 Construction process of density adaptive neighborhood

在構建密度自適應鄰域算法之前，定義以下概念：

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

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

dij：代表點i和j之間點歐氏距離；

CCi：代表點i的核心近鄰點；

BCi：代表點i的密度連接近鄰點；

PCi：代表點i的擴展近鄰點；

CSi：代表點i的最終近鄰點；

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

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

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

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

NC 算法描述如下：

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

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

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

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

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

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

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

圖4 點I 和點2 的3 個最近鄰居Fig.4 Three nearest neighbors of point 1 and point 2

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

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

相似矩陣S為：

通過對DAN 進行加權構建一種基于共享鄰的局部自適應鄰域相似矩陣。

2.3 基于共享最近鄰的密度自適應鄰域譜聚類

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

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

3 實驗與結果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為進一步驗證SC-DANSN 算法的有效性，隨機選取UCI 機器學習庫的4 個真實數(shù)據(jù)集。4 個數(shù)據(jù)集的屬性如表2 所示。

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

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

表3 UCI 數(shù)據(jù)集實驗結果Table 3 Experimental results of UCI datasets

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

圖9 Iris 數(shù)據(jù)集實驗結果Fig.9 Experimental results of Iris dataset

圖10 Breast 數(shù)據(jù)集實驗結果Fig.10 Experimental results of Breast dataset

圖11 Wine 數(shù)據(jù)集實驗結果Fig.11 Experimental results of Wine dataset

圖12 Ecoli 數(shù)據(jù)集實驗結果Fig.12 Experimental results of Ecoli dataset

4 結束語

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