王贏己，董紅斌

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

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

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

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

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

1 相關(guān)工作

1.1 DP 算法

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

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

假設(shè)2聚類中心應(yīng)與其他密度大于它的聚類中心的“距離”相對(duì)更大，即2 個(gè)聚類中心應(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ù)點(diǎn)xi和xj之間的歐幾里得(或者其他度量方法)距離。

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

1.1.1 截?cái)鄡?nèi)核

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

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

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

1.2 自然鄰居

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

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

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

圖1 自然鄰居示意

1.3 肘方法

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

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

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

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

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

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

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

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

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

2.2 肘方法的搜索范圍

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

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

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

2.3 NDP 指標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 使用人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)

實(shí)驗(yàn)包括12 個(gè)合成數(shù)據(jù)集，其中包括通過計(jì)算機(jī)模擬生成的二維隨機(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 個(gè)數(shù)據(jù)集的聚類效果如圖2 所示。

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

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

3.2 使用真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)

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

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

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

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

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

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

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

4 結(jié)論

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

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