自然鄰居密度極值聚類算法

張忠林，趙 昱，閆光輝

蘭州交通大學 電子與信息工程學院，蘭州 730000

數據聚類把數據對象按照不同屬性分割成確定數目的同質子集，每個同質子集貼上屬性標簽后稱之為類簇。對于任何一個類簇滿足簇內數據對象特征相似，簇間數據對象特征差異較大的條件[1]。聚類概念已被引入到多個研究領域之中，例如：智能算法改進、大數據分析、模式檢測、神經網絡等[2]。聚類算法發展過程中提出了許多經典算法，如基于劃分思想k-means算法[3]、基于層次思想EM算法[4]、基于密度思想DBSCAN、RNNDBSCAN算法[5-6]，基于網格思想CLIQUE算法[7]、基于模糊思想FCM算法[8]。

隨著對數據集深入研究發現密度峰值是數據集的一個重要屬性，因此2014年Rodriguez等[9]提出基于密度峰值算法（clustering by fast search and find of density peaks，DPC），DPC算法迭代過程中人工調參少，可以發現任意非球狀簇并且敏感數據集中的噪聲點。但是DPC算法也存在三個不足[10]：（1）預先選取的截斷距離具有一定隨機性和經驗性，選取的截斷距離直接影響聚類結果的好壞；（2）計算局部密度時忽略數據分布情況，當簇間的數據稀疏程度相差較大時，即使設定合理參數也得不到理想聚類效果；（3）數據對象間相似性度量僅采用歐氏距離模型，在高維數據集中導致度量結果不準確，并且隨著數據集規模遞增，每迭代一次相似性計算次數為n(n-1)2，導致算法時間復雜度為O(n2)影響算法效率。

DPC算法存在人工選擇的隨機性和數據間度量準則的不準確性。對上述兩個問題提出了多種改進方法，Du等[11]提出了k近鄰方法，利用k-近鄰概念定義截斷距離和局部密度，該方法根據數據集特征能夠生成合理的截斷距離，在新的截斷距離下計算的局部密度更符合數據集的真實分布，引入決策圖將決策點選取可視化。Gou等[12]把數據對象的k-最近鄰引入圖G中，對于任意數據對象若存在數據對象是其最近鄰，則在這兩點之間生成一條邊賦予對應的權值，遍歷圖用權值來定義局部密度。Jin等[13]引入自然鄰居概念，采用樹的遍歷檢索最近鄰，來消除對于參數k的敏感問題。Wang等[14]提出了基于極值的聚類方法剔除離群點，在局部范圍內采用合并運算找到近鄰最多的點設置為聚類中心，以此聚類中心為基礎完成聚類。

基于上述研究，本文針對密度峰值算法的不足：（1）當樣本數據集密度差異較大時，低密度區域聚類中心比高密度區域聚類中心難以發現，導致聚類結果不準確；（2）當聚類更稀疏時，一個數據對象被識別成離群點概率增加；為了解決上述的兩個問題，提出了自然鄰居密度極值聚類算法（Natural Neighbor Density Extremum Clustering algorithm，NN-DEC）。該算法以密度極值作為聚類中心選擇標準，更加準確和全面地選取數據集聚類中心。首先調用自然鄰居搜索算法，迭代有限次后數據集形成自然穩定狀態，在該狀態下分割出數據對象的自然鄰居；其次將處理后數據集導入密度距離自適應模型，生成數據對象局部密度；然后，計算數據對象連通值，在使用連通值將數據集劃分成高低密度區域和離群點，引入密度極值函數找出不同區域聚類中心點；最后，將不同區域內未被分配數據對象，劃分到離其最近的聚類中心所在簇中合并聚類結果。

1 相關工作

表1為文章所定義數據符號和算法縮寫摘要。

表1 符號摘要Table 1 Summary of notations

1.1 DPC算法

DPC算法聚類中心選取條件：（1）簇中心點為局部密度最高的點，周圍任何一點局部密度都低于簇中心點；（2）對于任意簇中心點比它密度更高的局部密度峰值點，在數據集中與其分布的距離較遠。DPC算法核心需要計算xi的局部密度ρi以及最近距離δi。局部密度ρi計算如公式（1）所示：

DPC算法另一種計算局部密度的方法采用高斯核定義計算，如公式（3）所示：

使用高斯核計算數據對象的局部密度，ρi等于截斷距離dc內數據對象的個數和。

δi計算方法如公式（4）所示：

DPC算法將局部密度ρi和距離δi歸一化處理后，用做標準量引入到決策圖中，在決策圖中選定ρ和δ標準值。DPC算法偽代碼[15]如算法1所示：數據樣本為N，算法的時間復雜度為O(N)。

算法1DPC(ρ,d)

Input：局部密度ρ，距離矩陣d

1.2 密度自適應距離度量

如圖1所示，以歐式距離度量數據對象a和b之間的相似性，因距離較近則兩個數據對象相似性較高，可劃分到同一個簇中。但在數據集實際分布中a和c處在同一簇中，因此歐氏距離度量準則在該數據集中的度量誤差較大，同時不滿足上述聚類假設中特征交叉相似性。

圖1 合成數據集Fig.1 Synthetic datasets

基于上述分析應在環狀和密度差異較大數據集中，引入一種新的密度自適應距離度量方法。文獻[16]提出一種有效的密度自適應距離度量模型，將一個數據集分布映射到一個二維橢圓模型中，建立橢圓二維空間，度量兩個數據對象之間相似性度量，橢圓長軸和短軸參數將參與到運算過程中。

定義A={a1,a2,…,an}，B={b1,b2,…,bn}，自適應距離度量如公式（5）所示：

其中，wl和ws計算如公式（6）所示：

其中，wij1和wij2計算如公式（7）所示：

本文中采用高斯核方式進行局部密度計算，對于每一個數據對象都可以求出它在數據集中的局部密度ρi，密度自適應距離度量方法如公式（8）所示：

1.3 錨點選取方法

數據集中固定的點稱之為錨點，引入基于錨點的聚類[17]，計算每一個成為聚類中心點的最小損耗值，利用損耗值來優化聚類中心的選取。錨點選取如公式（9）所示：

f(xj)計算由公式（10）所示：

指示函數值為1表示該數據點可以作為錨點，值為0表示該數據點不能作為錨點。

1.4 高低密度區域劃分和離群點檢測

定義1（離群點[18]）觀察一組數據對象，存在異于這組觀察值的數據對象被稱為數據集中的離群點。

定義2（相似性度量）定義P={p1,p2,…,pn}和S={s1,s2,…,sn}，P和S屬性之間采用余弦相似性度量準則，如公式（11）所示：

數據集中所有向量計算后會生成一個余弦相似性矩陣Simn×n，n為數據集大小。矩陣中的每一項Sim[i,j]對應于xi和xj之間相似性值，使用相似性矩陣構建相互鄰居圖，問題就轉換成了如何在圖上找到孤立的點。假設該圖連通子圖集合中存在孤立的點，則該點就可以稱之為數據集中的離群點。

節點u的連通值[19]c(u)會隨著迭代次數t收斂于一個穩定的值，如公式（12）所示：

初始化每一個節點的連通值c0(vi)=1n(i:1-n)。

S稱之為轉移矩陣，如公式（14）所示：

相似矩陣標準化可以使得：（1）轉移矩陣中的每一行的求和的值為1；（2）符合馬爾可夫鏈的基本性質；根據連通值的大小找到數據集中的高低密度區域和離群點。

算法2Detection(X,T)

Input：數據集X={x1,x2,…,xn}，密度閾值T

Output：X_high，X_low，Outlies

算法2中主要是對數據集中每個元素連通值計算，假設數據集大小為n，則計算連通值時間復雜度為O(n2)，轉移矩陣S計算時間復雜度也為O(n2)，算法2主要包括連通值和轉移矩陣計算，因此時間復雜度為O(n2)。

1.5 自然鄰居

自然鄰居[20]是一種無參的近鄰概念，提出的目的是解決k-最近鄰[21-22]中參數選擇問題。

定義3（自然穩定結構[23]）xi存在鄰居為xj，同時xj也存在鄰居為xi，若滿足上述條件則xj是xi自然鄰居；若數據集任意數據對象存在至少一個自然鄰居，數據集就形成了自然穩定結構（Natural Stable Structure，NSS）。

定義4（k-最近鄰[24]）數據對象xi與數據集中其他數據對象的歐氏距離，小于設定閾值的所有點集合，通過上述集合生成自然鄰居集合（Natural Neighborhood Set，NNS）。

定義5（自然特征值[25]）自然鄰居特征值（Natural Neighbor Eigenvalue，NNE）λ是在搜索自然鄰居過程中，當數據的形成NSS結構時所迭代的次數。

定義6（自然鄰居[25]）自然鄰居（Natural Neighbor，NaN）在集合概念下定義如公式（18）所示：

如圖2，對比了自然穩定狀態下數據對象之間的關系和k近鄰下數據對象之間的關系。

圖2 自然鄰居和k最近鄰對比Fig.2 Comparison of natural neighbors and k-nearest neighbors

基于上述公式的分析，給出自然鄰居搜索算法基本思想：首先要尋找到每一個數據對象的k-最近鄰，根據k-最近鄰結果構造相互鄰居圖。算法迭代終止條件：（1）不存在最近鄰數據對象時；（2）迭代次數大于等于自然鄰居個數減去迭代次數開方時。自然鄰居搜索算法（Natural Neighbor Search Algorithm，NaNSA）如算法3所示：

算法3NaNSA(X)

Input：數據集X={x1,x2,…,xn}

Output：自然鄰居個數num，相互鄰居圖G，自然特征值λ

算法3的時間復雜度分析：假定數據對象個數為n，算法時間消耗主要在構建KD樹數據結構上，構建KD樹的時間復雜度為O(nlbn)。由于數據對象個數n是有限的，因此算法時間復雜度為O(nlbn)。

2 NN-DEC算法

2.1 聚類中心確定

根據文獻[26]提出極值理論，極值描述現象是“不平均”分布，聚焦的是高分位數而不是數據集整體的統計數據。例如，樣本均方差、樣本期望、樣本離差平方和等。

密度差異較大的數據集對低密度區域聚類中心選取存在一定誤差，會導致聚類結果不準確，因此引入極值概念來解決上述出現的問題。本文采用密度極值目標函數計算每一個數據對象局部密度極值，采用橢圓模型處理后，使局部密度更加貼合數據集的真實分布。

自然鄰居搜索算法自適應得到數據對象自然鄰居，自適應搜索過程中消除了對于截斷距離dc的敏感問題。對得到自然鄰居數據對象計算局部密度，根據數據對象之間歐式距離選擇聚類中心存在誤差，因此引入上文提出密度自適應距離方法，選擇高低密度區域聚類中心。

為了提升算法效率調整因子采用線性方式計算wij=θwij1+(1-θ)wij2。θ計算取決于wij1和wij2，調整因子計算方式如公式（19）所示：

因此自然穩定狀態下xi局部密度計算公式，如公式（21）所示：

采用上文提到過的密度自適應距離度量方法，對數據對象局部密度計算。上述方法當數據集為NSS狀態時計算每一個數據對象局部密度。

密度在一個數據集中分布是不平衡，因此會存在高密度區域和低密度區域，選取聚類中心時需要設置一個合理閾值，區分出聚類中心點和非聚類中心點。

歸一化采用最小最大標準化處理（Min-Max Normalization）如公式（22）所示：

使用上述歸一化處理可以將密度和距離范圍控制到[0,1]范圍之內。計算出ρi如公式（23）所示：

密度和距離歸一化處理后，如圖3所示。

圖3 決策圖和聚類結果Fig.3 Decision graph and clustering results

從上述決策圖看出在決策范圍中出現了7個聚類中心點，這些點可以作為聚類中心。體現在圖3（b）中Aggregation聚類結果圖，標準化后聚類中心選擇更加準確，邊界區分明顯聚類效果提升。

本文設定φ(x)計算采用均方根公式，將其引入到聚類中心識別函數中，如公式（24）所示：

引入上文提到錨點選取方法，構造一個聚類中心識別函數H，如公式（25）所示：

其中，密度自適應距離度量過程中，將損益值取均方根保證算法在迭代過程中函數損益值不會出現負值。上述公式第二部分cosρ(xj)引入密度對于聚類中心選擇的影響，公式（21）對于低密度區域聚類中心選擇誤差較大，在此基礎上用極值來尋找聚類中心。

對公式（25）中密度ρi求導可得：

對于函數H進行求導時，將數據集每一個數據對象密度看作變量，數據對象xi密度在求導過成中當作常量。公式（25）中f(xj)判斷該數據對象是否為錨點指示，若是錨點則取值為1，若不是則取值為0；公式（26）求導后得到結果為公式（27）所示，其中將ρi替換后并且去掉集合符號得到一個密度極值函數，如公式（27）所示：

其中，x代表數據對象密度，密度定義在[0,1]，函數H′中冪函數增幅是大于正弦函數增幅，根據導函數定義在定義域范圍內大于零，得出該導函數對應的原函數是單調遞增，對于局部來說函數值越大，代表這個點周圍數據點分布是更加密集，說明這個數據對象在局部范圍內具有更高的密度。使用極值方法可以在高低密度區域中準確識別到聚類中心點。

2.2 高低密度區域聚類

根據2.1節按照統一密度閾值去選取聚類中心，低密度區域聚類中心選取會存在誤差，針對上述問題構建馬爾可夫模型，使用模型生成相互鄰居圖，利用圖上節點連通值去區分低密度和高密度區域，并且剔除掉離群點，進而對兩個區域分別進行聚類。

首先利用公式（11）計算每一個數據對象與其他剩余數據對象之間的VS值，采用這些值生成一個余弦相似性矩陣Simn×n，其中矩陣中每一項sim[i,j]代表，數據對象xi和數據對象xj之間VS值；對Simn×n每一行進行歸一化處理得到轉移矩陣，得到轉移矩陣后初始化每一個數據對象連通值c(u)，在每一次迭代中使用公式（12）更新當前每一個數據對象c(u)值；當連續兩次迭代中，數據對象連通值不再發生變化說明節點連通值穩定，然后將每一個數據對象連通值進行降序排列。根據文獻[19]提出的模型設定閾值T，區分出高低密度區域和離群點，如果一個數據對象連通值c(u)等于0，則說明該數據點為這個數據集中的離群點。

區分出高密度和低密度區域后，兩個區域分別進行聚類，高密度區域聚類，首先剔除離群點，再使用密度自適應距離方法計算數據對象局部密度極值，對比密度極值，大于所設定的密度閾值點歸入聚類中心點集合，高密度區域非聚類中心點較多，可以采用最近鄰原則將剩余點歸并到最近的簇中。在低密度區域，將每一個數據對象密度帶入公式（27）計算密度極值，當大于設置密度閾值時，將該點劃入聚類中心集合之中，因為在低密度區域中剩余數據量較少，將集合中非聚類中心點使用k-means算法完成聚類，各自完成聚類后合并兩個區域的聚類結果。

基于上述分析，給出NN-DEC算法基本思想：首先，引入自然鄰居概念消除了對近鄰參數k的敏感問題，采用密度自適應距離方法來計算數據對象局部密度。其次，構建錨點和密度極值函數篩選聚類中心，計算每一個數據對象連通值，根據連通值排序將數據集拆分成高密度區域和低密度區域，分別計算每個區域內數據對象密度極值，迭代對比將數據集分成聚類中心點集合和非聚類中心點集合。最后將非聚類中心點集合，按近鄰原則歸并到距離其最近的聚類中心所在簇中。NN-DEC算法偽代碼如算法4所示：

算法4NN-DEC(X)

Input：數據集X=(x1,x2,…,xn)

Output：聚類結果CL

設數據集中數據樣本個數為n，首先，獲得自然鄰居的時間復雜度為O(nlbn)，在自然穩定態下計算局部密度時間復雜度為O(n2)。在進行聚類之前需要將數據集分成不同的區域，采用連通值構建相互鄰居圖時間復雜度小于O(n2)，離群點檢測和高低密度區域聚類，時間復雜度均小于O(n2)，綜上所述算法4時間復雜度為O(n2)。

3 實驗結果與分析

為了驗證NN-DEC算法在不同數據集上的聚類效果，分別在人工合成數據集和真實數據集上運行算法。合成數據集包括不同規模和不同形狀的數據集，用于驗證算法處理不同形狀簇的效果；真實數據集：UCI公共數據集，數據集稀疏程度差異較大來驗證算法聚類效果。通過與基于聚類中心的K-means算法[3]、基于密度的DBSCAN算法[5]、DPC算法[9]、基于K近鄰優化的KNN-DPC算法[11]、基于密度極值的EC算法[14]、基于自然近鄰密度極值優化的NNDP算法[13]進行各項指標的對比。

實驗環境：Operating System Win10 64；Inter?Core?i5-10210U CPU＠1.60 GHz 2.11 GHz處理器，16.00 GB RAM。所有代碼采用Python語言實現。

聚類評價指標為標準互信息[27]（Normalized Mutual Information，NMI）、F值[1]（F-Measure）、聚類準確率[27]（Clustering Accuracy，CA）以此來判斷全局聚類準確性。其中NMI、F值和CA取值范圍為[0,1]，值越接近1表示在該數據集上聚類效果明顯。

3.1 合成數據集實驗結果分析

本節中采用7個合成數據集進行實驗，各類數據集的基本屬性如表2所示。選取表2中四個數據集對比NN-DEC和K近鄰算法，聚類中心點和非聚類中心點之間的緊湊程度如圖4所示。選取表2中四個人工數據集對比NN-DEC算法和DPC算法，聚類效果如圖5所示。

表2 合成數據集Table 2 Synthetic datasets

圖4 NN-DEC算法在Aggregation、Jain、Flame、Spiral上緊湊結果Fig.4 Compact results of NN-DEC algorithm on Aggregation，Jain，Flame，Spiral

圖5 NN-DEC和DPC算法在Aggregation、S1、Flame、Spiral上聚類結果Fig.5 NN-DEC and DPC algorithm clustering results on Aggregation，S1，Flame，Spiral

在圖4中可以看出本文提出的算法，對于聚類中心和非聚類中心之間的緊湊程度表達更好，在Spiral數據集上NN-DEC算法的邊界緊湊效果更加明顯。對于Jain數據集，本文算法在聚類的緊湊程度好于DPC算法。

圖5中前4個子圖為NN-DEC算法聚類效果，后4個子圖為DPC算法聚類效果。從圖5中可以看出，在Flame合成數據集上，由于簇之間分布距離較近密度分布差異不均衡，因此在DPC算法進行聚類時導致聚類結果不準確，而采用NN-DEC算法進行聚類時，剔除了離群點影響，密度分布不均衡有更好的聚類結果，并且在其他合成數據集上具有較好聚類分布。其余幾個數據集上來看NN-DEC算法聚類結果的邊界更清晰，準確度更高，聚類效果更加明顯。接下來分別在合成數據集上計算CA、NMI、F值。對上述對比聚類算法計算各指標值，結果如表3所示。

表3中展示了NN-DEC算法與對比的NNDP算法、EC算法、KNN-DPC算法、DPC算法、DBSCAN算法、Kmeans算法在合成數據集上三種評價指標，可以看出除了Flame數據集，其他六個數據集上性能都優于所對比的算法。具體分析：在Aggregation數據集上因為數據分布廣且密度分布不均勻，因此NN-DEC算法在上面聚類效果是最佳的，NNDP算法的性能要優于EC算法，因為數據點密度分布較為均勻，EC算法在Aggregation數據集上性能也是較好的。S1數據集類別數較多、每個類之間密度差異較大、類之間距離較遠，因此NNDEC算法在S1數據上性能優于NNDP算法。Pathbased數據集數據分布相對集中密度分布較均勻，因此NN-DEC算法在該數據集上密度計算準確，聚類效果優于其他對比聚類算法。Spiral是一個環狀數據分布，數據間稀疏程度適中，由于數據間稠密程度均勻，NNDP、KNN-DPC、DPC、DBCSCAN算法和NN-DEC算法在該數據集上聚類性能相當。Flame數據集上類別較少密度分布相對集中，EC算法在該數據集上性能要優于NN-DEC算法。綜上所述說明NN-DEC算法在處理密度差異較大數據上具有不錯的效果。

采用折線圖方式來直觀表達NN-DEC算法NMI值，整體上優于其他對比算法，如圖6。

從圖6中可以看出NN-DEC算法NMI值優于其他對比算法，在DS6數據集上NN-DEC算法聚類結果明顯優于EC算法。

3.2 UCI數據集實驗結果分析

本節選取6個數據稀疏程度較大UCI真實數據集進行實驗。計算NN-DEC算法和對比算法，在真實數據集上的各個指標值。如表4所示，所選取UCI數據集都為常見代表數據集，其中Waveform數據集為數據密度分布較密集、不均勻程度較大，具有代表性的一類數據。

表3 各聚類算法在合成數據集上的評價指標對比Table 3 Comparison of evaluation metrics of various clustering algorithms on synthetic data sets

圖6 算法在DS1～DS7上NMI值Fig.6 Algorithm NMI values on DS1～DS7

表4 UCI數據集Table 4 UCI Datasets

表5中計算了CA、NMI、F值三個聚類指標，并給出了NN-DEC算法和其他六個算法，在六個UCI公共數據集上的聚類指標結果。從表4中可以看出NN-DEC算法，在各個真實數據集上的聚類評價指標結果均優于其他六個對比算法。Iris數據集上分布較散且密度相對分布均勻，NN-DEC算法的聚類性能雖然優于其他幾個算法，但是由于密度較均勻其他對比算法聚類性能參數也較好。Cancer數據集維度大、密度分布差異大，NNDEC算法在該數據集上聚類效果較好，KNN-DPC和EC算法在該數據集上聚類性能相當，NNDP算法性能要優于EC和KNN-DPC算法。Wine數據集上密度極值分布明顯，數據分布緊湊，所以NN-DEC算法和EC算法聚類性能相差很小，而NNDP算法沒有對聚類中心點之間的距離，做自適應處理性能低于EC算法，DBSCAN算法處理密度集中分布的數據集時聚類性能，相較于其他算法更差。Waveform數據集中數據分布集中，局部密度極值容易計算，因此NN-DEC算法的性能優于其他對比算法。Breast數據集上類別數較少，K-means進行劃分時聚類效果明顯，聚類性能與NN-DEC算法相差不大。Segment數據集上數據分布離散，密度極值分布不均勻，EC算法的聚類性能最差，NNDP和NN-DEC算法局部密度計算效率相當，但對于距離的度量NN-DEC算法更加合理，所以NN-DEC算法聚類效果更優。綜上所述NN-DEC算法在UCI真實數據集上的性能是最優的。

表5 各聚類算法在UCI數據集上的評價指標對比Table 5 Comparison of evaluation metrics of various clustering algorithms on the UCI dataset

采用折線圖方式來直觀表達NN-DEC算法NMI值，整體上優于其他對比算法，如圖7。

3.3 算法時間復雜度分析

分別在合成數據集和UCI公共數據集上，對比不同算法在不同數據集下的時間復雜度。

圖7 算法在UCI數據集上NMI值Fig.7 Algorithm NMI values on UCI dataset

如圖8所示為7種算法在合成數據集Aggregation上運行時間（迭代運行30次取平均值）。

圖8 算法在Aggregation數據集上運行時間Fig.8 Algorithm runtime on Aggregation dataset

NN-DEC算法運行時間效率上，比不上K-means和DBSCAN線性時間復雜度的算法，但是在聚類效果上明顯優于這兩個算法，因為在Aggregation數據集上密度分布差異大，所以本文提出算法時間復雜度優于NNDP和EC算法。

如圖9所示為7種算法在UCI數據集Wine上運行時間（迭代運行30次取平均值）。

圖9 算法在Wine數據集上運行時間Fig.9 Algorithm runtime on Wine dataset

在Wine數據集上密度極值分布明顯，離群點容易剔除，所以本文提出算法在時間復雜度上優于NNDP和EC算法。

4 結束語

本文提出了一種自然鄰居密度極值算法NN-DEC算法。當數據集密度真實分布差異較大時，采用統一標準去篩選聚類中心，對于低密度區域聚類中心選取存在較大誤差，在這個基礎上引入連通值概念，采用連通值將數據集進行區域劃分，使用數學上極值的概念計算密度極值，以此來找到不同區域的聚類中心點，不同區域分開進行聚類，最后將聚類結果合并到一起。文中對于閾值選取以先前文獻的取值為基礎，這樣會導致對自己算法存在不足，在接下來工作中對于閾值選取可以提出一個模型優化閾值參數選取。每次迭代要更新所有節點連通值消耗時間太久，采用隨機游走方式，計算連通值提高算法的效率。可以增加一個空間度量值將數據按層次空間分開，讓算法自適應地去處理高維數據集。