基于密度峰值及肘方法的類數目確定

王贏己，董紅斌

哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001

伴隨著時代的發展與進步，大數據技術已深入到人們的生活中，比如在視頻廣告、交易平臺和視頻終端，每天產生海量的數據，如果將這些數據加以利用，就可以化“數字”為“神奇”，創造無窮價值，因此“數據挖掘”技術被廣泛運用。而聚類[1-5]分析是數據挖掘的一項重要技術，是探索數據之間隱藏聯系的重要一環。聚類分析源自分類學，但是聚類和分類并不一樣。分類是已經知曉物品的標簽，將其分到對應的標簽下；而聚類是未知的，是一種無監督的分類方法。

密度峰值(DP)算法[6]是一種近幾年流行的聚類算法。該算法的優勢在于不受數據集形狀的限制，可以識別出任意形狀的數據，如流形、線形、環形和簇形等數據集；也很容易發現數據集中的噪聲點。而且其參數唯一、易于使用，并具有很好的魯棒性，廣受學者們的歡迎。盡管如此，DP 算法還是有一些不足：1)DP 算法的局部密度計算方式是通過截斷距離（dc）來計算的，這個值往往是通過經驗設置，無法適應不同密度的數據集。2)DP 算法是根據排序好的候選中心來聚類的，若開始選擇了較差的候選者則會導致難以估量的后果。近年來，針對DP 算法提出很多的改進算法，如引入信息熵概念來改進dc的計算[7]，這樣會使DP 算法聚類中心的選擇過程更直觀；還有利用基尼不純度發現最佳dc[8]；Liu 等[9]提出基于KNN 的新密度度量方式的ADPC-KNN 算法；Mehmood 等[10]結合了截斷距離選擇和核密度估計的邊界矯正的CFSFDP-HD，以實現更精確的聚類效果，不受噪聲點的干擾。

經過上述分析發現，實現自適應DP 聚類算法關鍵是聚類中心的選取、dc的計算和類數目的確定。目前針對前2 個因素的改進已經進行了大量的相關研究[11]，但是對于類數目的確定仍然停留在人工干預選擇的階段，缺少自動選擇類數目的相關工作。

本文針對上述分析，提出以下內容：1)提出基于自然鄰居的新內核；2)改進自然鄰居的搜索算法；3)聯合肘方法以自適應確定類數目。

1 相關工作

1.1 DP 算法

密度峰值算法的本質在于聚類中心，該算法在于提出一種方式高效地選取數據集中的聚類中心。 Rodriguez 等[6]提出2 個關于聚類中心的假設：

假設1聚類中心的密度應比其鄰居密度都要大，即它任意鄰居的密度均小于它。

假設2聚類中心應與其他密度大于它的聚類中心的“距離”相對更大，即2 個聚類中心應有一段距離。

設數據集D={x1,x2,···,xN}，標簽集F={f1,f2,···,fN}，候選聚類中心C={c1,c,···,cK}，dij=dist(xi,xj)表示數據點xi和xj之間的歐幾里得(或者其他度量方法)距離。

對于局部密度 ρi的計算方式大體有2 種，分別是截斷內核(Cut-off kernel)和高斯內核(Gaussian kernel)。

1.1.1 截斷內核

通過式(1)可知：若xi的局部密度為全局最大時， δi為xi與數據集中所有數據點的聚類降序排序中的最大值；否則 δi為所有局部密度大于xi的數據點中的距離降序排序中的最小值。

文中提出一種新的參數 γ，用來表示聚類中心的評估值，參數 γ是局部密度 ρi和距離 δi的 乘積：

顯然，一個數據點的 γ值越大，它是聚類中心的可能性越高。

1.2 自然鄰居

自然鄰居是一個新的鄰居概念[12-14]。與k個最近鄰居相比，此方法不需要設置任何參數，并且是自適應搜索鄰居的方法。自然鄰居主要受到人類社會關系的啟發：假設2 個人A 和B，2 個人之間的友誼應該是相互的，即A 認識了解B，而B 也認識了解A，此時才認為2 個人是熟悉的；而當A 認識B，但B 不認識A 時，可以說兩者并沒有任何關系。這說明一個數據點的自然鄰居個數越多，其越緊密；反之，說明其越稀疏。

自然鄰居的生成過程是這樣實現的：首先初始化當前鄰居個數r，通過不斷增加r以擴大搜索范圍，且每次計算每個點的逆最近鄰居數量。當滿足以下2 個條件之一時，即：1)所有點具逆最近鄰居；2)沒有逆最近鄰居的個數不變，可以認為達到了自然穩定狀態。此時的搜索范圍r是自然特征值 λ。

如圖1 所示，當r=2 時，紅色圓圈的K近鄰為藍、綠圓圈，其中，藍色圓圈的K近鄰為紅、黑圓圈，綠色圓圈的K近鄰為白色圓圈。此時，紅、藍互為自然鄰居；反之紅、綠不是自然鄰居。

圖1 自然鄰居示意

1.3 肘方法

肘方法顧名思義，就是類似人的手肘，有一個拐點存在[15]。肘方法就是通過這個拐點來得到最終的K值。它是基于2 條曲線得到：一條是由誤差平方和(sum of the squared errors，SSE)計算得到，另一條是搜索范圍的起點和終點的SSE 連線(y=ax+b)；然后將兩者的差值中的最大值所在的K值作為最終結果。其中K的搜索范圍影響著2 條曲線差值的精度。若范圍太大，則當誤差平方和趨于平緩時，搜索還未結束；反之范圍太小，搜索就會在誤差平方和還在下降時結束。無論哪一個都會導致最終的K值無效。如何解決這一問題是使用肘方法的關鍵。傳統的肘方法是通過經驗設置搜索范圍，本文將其與密度峰值聯合以自適應計算肘方法的搜索范圍。

2 基于自然鄰居的密度峰值算法

傳統的密度峰值算法無法實現真正的自適應，其中的參數dc往往根據經驗設置，若設置合適，能取得不錯的結果，但是這也將導致其局限性。若數據集差別較大，則要么需要通過大量實驗重新設置參數，要么會導致得到較差的聚類結果。為了改進這一缺陷，本文通過引入自然鄰居的思想，重新定義每個數據點的鄰居關系，來重新計算每個數據點的局部密度 ρi和距離 δi，根據得到的候選集合聯合肘方法得到全局最優類數目。本文還引入了減而治之的思想，改進計算自然鄰居的搜索算法，大大減少運行時間。

對于傳統的KNN 算法，每個數據點要根據dist(x,y)(其中y是任意非x數據點)排序，根據距離的大小來判斷誰是它的鄰居；這就需要事先知道K的大小，否則無法實現真正的自適應。而自然鄰居(nature neighbor)的思想是，2 個數據點互相認為對方此時是自己的K最近鄰居，才認為彼此是自然鄰居關系。此時，可以說2 個數據點是可靠穩定的鄰居關系。通過自然鄰居的思想，不僅可以得到理論上更為可靠的鄰居關系，并且基于此可以得到更可靠的局部密度，以實現真正意義上的自適應，不再受數據集的規模和固有參數的限制。

由于肘方法的搜索范圍往往是根據經驗確定，設置數據集大小為N，搜索范圍一般為對于一些規模較大的數據集，根據經驗選擇搜索范圍在一些情況下可能會耗費更高的時間成本，甚至還會降低聚類的精度。本文通過基于自然鄰居的密度峰值算法來確定肘方法的搜索范圍，經實驗驗證，該方法可以大大縮小肘方法的搜索范圍，繪制的曲線也更能準確地獲得數據集的真實類數目。

2.1 基于自然鄰居思想的密度峰值算法

密度峰值算法思想的核心是密集區域的局部密度要大于稀疏地區的局部密度，即密集區域的鄰居之間的距離要更小，反之鄰居之間的距離要更大。本文結合自然鄰居思想給出局部密度 ρi的定義為

式中： ω為在自然鄰居尋找過程中迭代結束后r的值，即某個數據點擁有的最高自然鄰居的個數；NNω(i)表示距i數據點的 ω最近鄰居，而dist(i,j)是數據點i和數據點j的歐幾里得距離。

由式(2)易知，基于自然鄰居的思想，可以真正自適應地計算合適的鄰居個數，為更準確地得到聚類結果提供保證。

2.2 肘方法的搜索范圍

式中：nbi為數據點i的自然鄰居個數；F(x)為x的算術平均值。

候選因子 θi的大小取決于兩點，一是數據點x的自然鄰居個數，二是其所有自然鄰居的自然鄰居個數的平均值?？梢园l現，一個點的自然鄰居個數比其所有自然鄰居的自然鄰居個數都多，則它很可能是聚類中心。

在選擇候選聚類中心時，首先，計算每個數據點的候選因子 θi，只有當θi>1時，說明其有資格作為候選聚類中心，即它的自然鄰居個數要大于它的鄰居；反之，排除它成為候選聚類中心的可能。然后，再根據候選聚類中心的特征值 γi排序，將結果降序排列。最后，肘方法的搜索范圍即經過候選因子 θi過濾出來的數據點，再根據特征值γi降序排列，采用肘方法得到最優的類數目。

2.3 NDP 指標

肘方法的核心思想是：隨著聚類的類別數目K增加，數據集的誤差平方和的下降幅度會驟減；然后隨著K值的繼續增大而趨于平緩，那么曲線圖的拐點就是聚類中心。本文提出NDP 指標，該指標由2 條直線的差值計算得到，一條是由數據集的誤差平方和計算得到(Z={z1,z2,···,zM})，另一條是肘方法搜索范圍的起點和終點的SSE 值兩點確定的一條直線y=ax+b(Y={y1,y2,···,yM})；然后將2 條曲線的差值作為每個K值的NDP 指標值，即集合H={h1,h2,···,hM}，最優的類數目是該集合中的最大值所對應的指標K值。

式中C為候選聚類中心集合，C={c1,c2,···,ck},?θci>1。

2.4 減而治之的自然鄰居搜索算法

自然鄰居的計算過程為，設置n初始值為1(n為自然鄰居個數)，遍歷n直到滿足以下任意條件其中一個：1)所有數據點的自然鄰居集合不為空，即每個數據點都至少有1 個自然鄰居，次迭代中沒有自然鄰居的數據點的個數相等，即新一輪迭代沒有減少還未有自然鄰居的數據點的個數，時間復雜度是O(n)2。本文對此作出了改進，提出了基于二分的自然鄰居搜索算法(binary natuer-neighbor，BNaN)。該算法采用減而治之的思想，每一輪迭代都在縮短搜索區間，以進一步減少時間復雜度并提升運行效率。

首先，算法的目標是找到一個n值使得每個數據點都至少有一個自然鄰居。而對于數據來說，有這樣一個趨勢：隨著n的遞增，數據集中至少有1 個自然鄰居的數據點的個數是遞增的，且當達到最大值時停止增加。即可以將求n值的問題轉換為在一個遞增序列中求這個最大值出現的位置。

二分查找的基本用法是在一個有序數組里查找目標元素，具體是檢查區間中間元素的值與目標值的大小關系。如果等于，就可以直接返回；如果嚴格大于，就往右邊查找；如果嚴格小于，就往左邊查找。這也符合人類的邏輯思維。

由于一個元素出現多次，即當所有數據點都有自然鄰居時，再增加n的值，得到的計算結果相同，此時的n值就是該序列中的最大值。算法具體可以分為3 種情況：

1)如果當前看到的元素恰好等于目標值，那么當前元素有可能是目標值出現的第一個位置，因為要找第1 個位置，此時應該向左邊繼續查找。

2)如果當前看到的元素嚴格大于目標值，那么當前元素一定不是要找的目標值出現的第一個位置(理論上不存在大于目標的值)，此時應該向左邊繼續查找。

3)小于的情況與第2 種情況類似。

Algorithm1 總結了所提出的BNaN 算法。

3 實驗結果

為了證實新NDP 指標和BNaN 算法的性能，本文使用了12 個人工數據集和3 個真實數據集來測試NDP 索引。此外，我們使用調整蘭德指標來評估12 個合成數據集和3 個實際數據集的聚類結果。

通常，聚類K值的范圍是[2,kmax]，我們選擇NDP算法則是自適應地選擇K值。在下面的實驗結果中都設置以下規則：所有適用NDP 索引的算法如果沒有特殊表明，都是使用BNaN 算法。

3.1 使用人工數據集進行實驗

實驗包括12 個合成數據集，其中包括通過計算機模擬生成的二維隨機數。這些數據集是Semicircle2、Semicircle3、Semicircle4、Mix3、Norm2、Norm3，Norm4，Ring2，Parallel2，Parallel3，Segenment4和Circle2。在這些數據集中，Parallel2、Parallel3、Segenment4 數據集的結構是線性的，Semicircle2、Semicircle3、Semicircle4 數據集的結構是多方面的，Ring2 和Circle2 數據集是環形的，Norm2、Norm3、Norm4 數據集的結構是凸的，而Mix3 數據集是混合的。12 個數據集的聚類效果如圖2 所示。

對于Parallel2 數據集，其正確的類數目為2。所得到的聚類結果也為2。通過實驗發現，在給定最優類簇數目時，其余11 個人工數據集的實驗結果與Parallel2 數據集的實驗結果相似。因此，可以得出的結論，在給定最佳聚類數的情況下，可以正確劃分12 個人工數據集。

圖2 12 個人工數據集的聚類結果

3.2 使用真實數據集進行實驗

實驗包括3 個真實數據集：Seeds、Iris 和Titanic，這些數據集分別來自UCI 機器學習存儲庫(http://archive.ics.uci.edu/ml/)和KEEL 存儲庫(https://sci2s.ugr.es/keel/datasets.php)。表1 為本文算法對3 個真實數據集的最佳類數的實驗結果。

表1 真實數據集上的運行結果

表1 中加粗部分表示在當前數據集中得到的最大值。表1 顯示了通過候選因子限定了簇數的搜索范圍，其中，Seeds 簇數的搜索范圍是2～14，Iris 簇數的搜索范圍是2～12，而Titanic 簇數的搜索范圍是2～6?？梢钥闯鐾ㄟ^候選因子，能減少搜索范圍，提升計算效率。比如Titanic 的樣本數目是2 201，若按照經驗，K值的搜索范圍應該是而通過候選因子計算得到的聚類中心候選人的數目是6，遠遠小于46，可以得出候選因子的提出可以大大提高肘方法的計算效率。最后通過實驗可以發現，本文提出的NDP 算法可以為3 個真實數據集獲得正確的最優簇數。當肘方法形成的拐點圖肉眼難以區分其拐點時，通過所提出的方法，可以有效地識別拐點，得到最優類簇數目。

表2 列出了使用3 個真實數據集確定最佳簇數的算法的運行時間，通過觀察該表可以發現，通過改進自然鄰居的搜索算法(BNaN-Searching)，可以大幅減少算法的時間成本。

表2 真實數據集上算法的運行時間

為了驗證本文提出算法的有效性，將本文算法與自適應密度峰值算法(adaptive peak cluster，APC)、密度峰值算法(density peak cluster, DPC)、基于密度的聚類算法((density-based cluster，DBSCAN)和K-means 算法進行比較。真實數據集的聚類結果采用綜合評價指標(F值)、歸一化互信息(NMI)、準確率(ACC)這3 個聚類指標進行評價。通過表3數據可以看出NDP 算法的各評價指標均高于其他算法。

表3 真實數據集上聚類效果

4 結論

密度峰值算法已經成為近幾年流行的聚類算法，本文針對其依賴固有參數，對于不同數據集的聚類具有很大局限性這一缺點，引入自然鄰居思想，實現真正的自適應密度峰值算法，并通過結合肘方法和候選因子，可以快速有效地得到類簇數目。最后對自然鄰居的選取算法進一步改良，以實現更高效率的聚類。通過理論研究和實驗結果證明，本文提出的新內核和方法可以準確地得到數據集的最優類簇數目，并適用于多種類型的數據集，如線形、流形、環形和凸形數據集。

本文還存在一些不足，所求的局部密度對于噪聲點敏感，當噪聲較多時，聚類效果和類簇數目的準確度會降低。后續會引入歸一化來更好地求得數據點的密度。