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

王贏己，董紅斌

哈爾濱工程大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

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

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

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

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

1 相關(guān)工作

1.1 DP 算法

密度峰值算法的本質(zhì)在于聚類中心，該算法在于提出一種方式高效地選取數(shù)據(jù)集中的聚類中心。 Rodriguez 等[6]提出2 個關(guān)于聚類中心的假設(shè)：

假設(shè)1聚類中心的密度應(yīng)比其鄰居密度都要大，即它任意鄰居的密度均小于它。

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

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

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

1.1.1 截斷內(nèi)核

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

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

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

1.2 自然鄰居

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

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

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

圖1 自然鄰居示意

1.3 肘方法

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

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

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

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

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

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

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

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

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

2.2 肘方法的搜索范圍

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

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

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

2.3 NDP 指標(biāo)

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

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

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

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

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

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

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

1)如果當(dāng)前看到的元素恰好等于目標(biāo)值，那么當(dāng)前元素有可能是目標(biāo)值出現(xiàn)的第一個位置，因為要找第1 個位置，此時應(yīng)該向左邊繼續(xù)查找。

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

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

Algorithm1 總結(jié)了所提出的BNaN 算法。

3 實驗結(jié)果

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

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

3.1 使用人工數(shù)據(jù)集進行實驗

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

對于Parallel2 數(shù)據(jù)集，其正確的類數(shù)目為2。所得到的聚類結(jié)果也為2。通過實驗發(fā)現(xiàn)，在給定最優(yōu)類簇數(shù)目時，其余11 個人工數(shù)據(jù)集的實驗結(jié)果與Parallel2 數(shù)據(jù)集的實驗結(jié)果相似。因此，可以得出的結(jié)論，在給定最佳聚類數(shù)的情況下，可以正確劃分12 個人工數(shù)據(jù)集。

圖2 12 個人工數(shù)據(jù)集的聚類結(jié)果

3.2 使用真實數(shù)據(jù)集進行實驗

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

表1 真實數(shù)據(jù)集上的運行結(jié)果

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

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

表2 真實數(shù)據(jù)集上算法的運行時間

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

表3 真實數(shù)據(jù)集上聚類效果

4 結(jié)論

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

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