基于貝葉斯優(yōu)化的密度峰值聚類(lèi)算法

吳濤 朱小東 劉喚喚 張順香

摘要：針對(duì)人工經(jīng)驗(yàn)設(shè)定密度峰值的聚類(lèi)算法（clustering by fast search and find of density peaks， DPC）的截?cái)嗑嚯x[dc]有很大的主觀性和隨機(jī)性，進(jìn)而導(dǎo)致密度峰值聚類(lèi)算法的性能無(wú)法完全發(fā)揮的問(wèn)題。提出貝葉斯算法（Bayesian Optimization，BO） 優(yōu)化密度峰值的聚類(lèi)算法以實(shí)現(xiàn)自適應(yīng)聚類(lèi)。并解決密度峰值的聚類(lèi)算法簇間數(shù)據(jù)點(diǎn)識(shí)別錯(cuò)誤問(wèn)題。該方法建立在數(shù)據(jù)集Aggregation、Flame、Jain、Spiral上進(jìn)行實(shí)驗(yàn)，分別通過(guò)內(nèi)部指標(biāo)Silhouette和外部指標(biāo)F-measure對(duì)實(shí)驗(yàn)結(jié)果評(píng)估，性能均有提升。

關(guān)鍵詞：密度峰值的聚類(lèi)算法;截?cái)嗑嚯x;貝葉斯算法;自適應(yīng)聚類(lèi);內(nèi)部指標(biāo)

中圖分類(lèi)號(hào)：TP391? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）22-0008-05

1 引言

21世紀(jì)隨著互聯(lián)網(wǎng)的快速普及，人們?cè)谛涡紊纳钪挟a(chǎn)生了大量的數(shù)據(jù)，大數(shù)據(jù)的時(shí)代隨之來(lái)臨，怎樣從這些數(shù)據(jù)中獲得有用的信息成為當(dāng)今研究熱點(diǎn)。

聚類(lèi)是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、圖像識(shí)別等領(lǐng)域預(yù)處理數(shù)據(jù)的一種基本算法。聚類(lèi)把一組沒(méi)有標(biāo)簽定義的數(shù)據(jù)集或者樣本集，依據(jù)樣本的一組特征值，按照某種相似性度量手段將特征值相似度較高的數(shù)據(jù)點(diǎn)劃分成同一個(gè)類(lèi)簇，為后續(xù)處理提供了可貼標(biāo)簽的分類(lèi)數(shù)據(jù)。

聚類(lèi)是一種無(wú)監(jiān)督學(xué)習(xí)，即在無(wú)任何人工干預(yù)的情況下對(duì)數(shù)據(jù)進(jìn)行區(qū)分。相似度高的數(shù)據(jù)聚合成一類(lèi)簇。不同簇之間的樣本點(diǎn)相似性較低[1-2]。有監(jiān)督學(xué)習(xí)主要任務(wù)是分類(lèi)，通過(guò)很多已經(jīng)標(biāo)記過(guò)的數(shù)據(jù)來(lái)對(duì)新數(shù)據(jù)進(jìn)行區(qū)分。相比監(jiān)督學(xué)習(xí)，無(wú)監(jiān)督學(xué)習(xí)則不需要大量人工標(biāo)記的訓(xùn)練樣本來(lái)作為區(qū)分?jǐn)?shù)據(jù)的前提。在大數(shù)據(jù)信息共享時(shí)代，因?yàn)閿?shù)據(jù)聚集模式復(fù)雜、多變，單一相似度標(biāo)準(zhǔn)難以適應(yīng)多種模式，所以現(xiàn)有的聚類(lèi)算法不能夠滿(mǎn)足已有種類(lèi)繁多的數(shù)據(jù)集。面對(duì)以上現(xiàn)狀，不斷衍生出眾多的聚類(lèi)方法。目前常用的聚類(lèi)算法大致可分為：基于模型的聚類(lèi)，基于劃分的聚類(lèi)，基于層次的聚類(lèi)，基于網(wǎng)格的聚類(lèi)，基于密度的聚類(lèi)。其中，基于模型的聚類(lèi)算法一般假設(shè)要聚類(lèi)的數(shù)據(jù)來(lái)源于某個(gè)混合的潛在概率分布模型，通過(guò)對(duì)該模型進(jìn)行參數(shù)估計(jì)來(lái)完成聚類(lèi)?；趧澐值木垲?lèi)算法需要一個(gè)最優(yōu)化的目標(biāo)函數(shù)來(lái)發(fā)現(xiàn)聚類(lèi)數(shù)據(jù)中的類(lèi)別信息，迭代的將數(shù)據(jù)集劃分為幾個(gè)部分，再驗(yàn)證劃分過(guò)程是否科學(xué)合理。常見(jiàn)的劃分聚類(lèi)算法如K-means[3]，該算法簡(jiǎn)單并且高效，聚類(lèi)效果主要受類(lèi)簇中心點(diǎn)[k]值影響較大。一般情況下[k]值的確定具有很大的主觀性，這對(duì)沒(méi)有先驗(yàn)經(jīng)驗(yàn)的測(cè)試下的取值會(huì)對(duì)聚類(lèi)結(jié)果有很大的影響。面對(duì)高維的數(shù)據(jù)處理對(duì)象聚類(lèi)效果不佳?；诰W(wǎng)格的聚類(lèi)算法對(duì)數(shù)據(jù)的處理比較粗糙，主要用于處理大量多維數(shù)據(jù)的聚類(lèi)問(wèn)題?；趯哟蔚木垲?lèi)算法分為自下而上的聚合層次聚類(lèi)和自上而下的分裂層次聚類(lèi)，其目的是讓聚類(lèi)過(guò)程不受參數(shù)的影響并且更加靈活?；诿芏鹊木垲?lèi)核心思想是先選定較高密度的數(shù)據(jù)點(diǎn)，再將周邊與其相近的點(diǎn)聚為一類(lèi)。常見(jiàn)的基于密度的聚類(lèi)算法如DBSCAN[4]聚類(lèi)算法雖然能夠處理任意大小形狀的簇，對(duì)噪聲的容忍性較好，但當(dāng)簇密度變化較大時(shí)聚類(lèi)效果較差，并且當(dāng)遇到大量高維的數(shù)據(jù)時(shí)會(huì)大量地消耗計(jì)算資源。

DPC算法[5]是近幾年提出的一種基于密度劃分的聚類(lèi)算法，該算法依據(jù)密度峰值決策圖選取合適的密度峰點(diǎn);并將圖中代表樣本的其他數(shù)據(jù)點(diǎn)劃分到最近或匹配的密度峰點(diǎn)類(lèi)別中，從而得出簇的劃分。DPC算法的優(yōu)點(diǎn)之一是除了決策圖中的密度峰值點(diǎn)需要人工干預(yù)選擇外，整個(gè)算法僅需要預(yù)先給出一個(gè)輸入?yún)?shù)（截?cái)嗑嚯x） ，不需要像多數(shù)其他聚類(lèi)算法一般預(yù)先指定簇?cái)?shù)目，提高了算法的可靠性與適應(yīng)性。另一方面，DPC算法在初期決策圖中選擇的密度峰點(diǎn)即確定了簇的數(shù)目及分布，不需要通過(guò)反復(fù)迭代來(lái)獲得最優(yōu)結(jié)果，其效率相對(duì)于其他聚類(lèi)算法有著顯著優(yōu)勢(shì)。

隨著對(duì)DPC算法的不斷深入研究，越來(lái)越多的改進(jìn)DPC算法相繼出現(xiàn)。針對(duì)DPC算法的局部密度計(jì)算方式過(guò)于單一的問(wèn)題，Liu等人[6]提出ADPC結(jié)合KNN的算法，該算法重新定義了局部密度的計(jì)算方法。針對(duì)DPC算法的一次性樣本數(shù)據(jù)分配策略可能存在錯(cuò)誤分配連帶問(wèn)題，即一旦一個(gè)數(shù)據(jù)點(diǎn)被錯(cuò)誤分配，隨后可能會(huì)有更多的點(diǎn)被錯(cuò)誤分配，Seyed等人[7]提出了一種DPC-DLP的聚類(lèi)算法，該算法統(tǒng)一確定簇中心，將簇中心聯(lián)合起來(lái)構(gòu)建新的KNN圖，通過(guò)圖的傳播方法分配樣本數(shù)據(jù)。Xie[8]等人提出了計(jì)算數(shù)據(jù)[ai]相對(duì)于[其K]近鄰的局部密度度量方式和通過(guò)從聚類(lèi)中心開(kāi)始對(duì)點(diǎn)的K個(gè)最近鄰進(jìn)行廣度優(yōu)先搜索來(lái)分配數(shù)據(jù)點(diǎn)，從而對(duì)DPC聚類(lèi)算法進(jìn)行優(yōu)化。

面對(duì)不同類(lèi)型數(shù)據(jù)時(shí)，這些改進(jìn)的DPC聚類(lèi)算法雖然有較好的聚類(lèi)結(jié)果，但是截?cái)嗑嚯x仍需要人為設(shè)定。當(dāng)數(shù)據(jù)密度相差較大時(shí)，很難人為選擇一個(gè)合適的截?cái)嗑嚯x，如果輸入截?cái)嗑嚯x百分比過(guò)大時(shí)可能會(huì)出現(xiàn)所有數(shù)據(jù)點(diǎn)都被分到同一類(lèi)，如果輸入截?cái)嗑嚯x百分比過(guò)小時(shí)可能會(huì)出現(xiàn)聚類(lèi)數(shù)目過(guò)多。所以截?cái)嗑嚯x[dc]是影響聚類(lèi)效果好壞的重要參數(shù)，截?cái)嗑嚯x優(yōu)化其實(shí)就是機(jī)器學(xué)習(xí)中超參數(shù)優(yōu)化，目前主流的機(jī)器學(xué)習(xí)超參數(shù)優(yōu)化方法有群體智能優(yōu)化算法、網(wǎng)格搜索（即窮舉法） 、隨機(jī)搜索算法、貝葉斯優(yōu)化算法。但是群體智能優(yōu)化算法先要提供非常多的初始樣本點(diǎn)，并且其優(yōu)化效率一般。網(wǎng)格搜索算法是將所有涉及的超參數(shù)進(jìn)行組合，對(duì)每個(gè)組合進(jìn)行建模與評(píng)價(jià)，最后選擇評(píng)價(jià)最高的組合作為模型最終的超參數(shù)，這種方法需要經(jīng)過(guò)長(zhǎng)時(shí)間的計(jì)算才能獲得最優(yōu)的超參數(shù)組合。而隨機(jī)搜索則是在超參數(shù)的分布中隨機(jī)搜索超參數(shù)進(jìn)行建模，它的缺點(diǎn)是容易錯(cuò)過(guò)一些最優(yōu)超參數(shù)。貝葉斯優(yōu)化方法要優(yōu)于群體智能優(yōu)化算法、網(wǎng)格搜索算法和隨機(jī)搜索算法，因?yàn)樗趪L試下一組超參數(shù)時(shí)，會(huì)借鑒之前的評(píng)估結(jié)果，省去了很多無(wú)用功。因此本文選取貝葉斯算法[9-10]（Bayesian Optimization） 作為DPC聚類(lèi)算法的優(yōu)化手段，利用貝葉斯算法預(yù)測(cè)出的較優(yōu)[dc]值，驅(qū)動(dòng)DPC算法選擇出合適的聚類(lèi)中心，提高DPC聚類(lèi)算法的性能。

2 相關(guān)研究

2.1 DPC算法

密度峰值的聚類(lèi)算法[11-12]（clustering by fast search and find of density peaks， DPC），該算法能夠自尋簇中心，對(duì)任意類(lèi)型、大小的數(shù)據(jù)集能夠進(jìn)行準(zhǔn)確高效的聚類(lèi)。DPC算法具有兩個(gè)前提：

1） 峰值密度點(diǎn)（簇中心） 局部密度大于近鄰圍繞的局部密度。

2） 要使得不同簇中心之間的距離相對(duì)較遠(yuǎn)。

為了能夠準(zhǔn)確找到同時(shí)滿(mǎn)足以上兩個(gè)條件的簇中心，DPC算法引入了局部密度的定義。局部密度的計(jì)算如公式（1） 所示：

[ ρi=j≠if（dij-dc）]? ? ? ? ? ? ? ?（1）

假設(shè)數(shù)據(jù)點(diǎn)[ai]的局部密度為[ρi]，[dij]為[ai]到[aj]的距離，[dc]為兩點(diǎn)間的截?cái)嗑嚯x。[f（x）]為邏輯判斷函數(shù)，當(dāng)[x]值小于0時(shí)[f（x）]判定為1否則[f（x）]判斷為0，該函數(shù)表示為滿(mǎn)足一定距離閾值數(shù)目[ai]的多少，數(shù)目越多值越大，密度越高。

高密度最小值計(jì)算如公式（2） 所示：

[δi=minj：pj>pi（dij）]? ? ? ? ? ? ? ?（2）

[δi]表示為高密度的最小距離為[ai]到[aj]距離最近并且局部密度大于[ai]的局部密度的距離。當(dāng)[ai]為數(shù)據(jù)集中密度最大的點(diǎn)時(shí)[δi]的計(jì)算如公式（3） 所示：

[δi=maxj?c（dij）]? ? ? ? ? ? ?（3）

2.2 貝葉斯優(yōu)化算法

貝葉斯優(yōu)化算法（Bayesian Optimization，BO） 是一種基于黑盒的優(yōu)化算法[13]，該算法的優(yōu)化思路是首先生成初選解集合[x1，x2，x3，...xn]，也就是n個(gè)采樣點(diǎn)，其次用目標(biāo)函數(shù)[f（x）]分別計(jì)算以上樣本點(diǎn)處的值，接著通過(guò)高斯回歸過(guò)程來(lái)計(jì)算每一點(diǎn)處[fx]函數(shù)值的均值和方差，并且根據(jù)當(dāng)前采樣數(shù)據(jù)點(diǎn)集[D={（xn，f（xn）}]更新[pf（x）|D]的均值和方差計(jì)算采集函數(shù)[u（x）]，然后使用采集函數(shù)極大值[xn+1=argmaxxu（x）]確定下一個(gè)采樣點(diǎn)。下一個(gè)采樣點(diǎn)的函數(shù)值為[yn=f（xn+1）]，將該采樣點(diǎn)加入原有集合中，不斷重復(fù)直至迭代終止，最后從這些點(diǎn)集中找出[fx]函數(shù)值最大的點(diǎn)就是問(wèn)題的最優(yōu)解。

1） 采集函數(shù)的構(gòu)建

構(gòu)建采集函數(shù)[14]常用的方法有基于提升策略的PI，EI辦法和置信邊界策略方法。因?yàn)镋I采集函數(shù)參數(shù)少，既整合提升的概率又體現(xiàn)不同的提升量，所以本文采用基于提升策略中的EI方法作為采集函數(shù)。已知對(duì)[n]個(gè)數(shù)據(jù)點(diǎn)進(jìn)行探索，該點(diǎn)集中極大值函數(shù)按公式（4） 計(jì)算：

[f*n=max（f（x1），...，f（xn））]? ? ? ?（4）

現(xiàn)考慮下一搜索點(diǎn)[x]，如果下一搜索點(diǎn)[f（x）]值大于等于[f*n]，則該點(diǎn)處的極大值為[f（x）]否則為[f*n]。將加入新點(diǎn)后的改進(jìn)值寫(xiě)成[f（x）-f*n+]（如果下一搜索點(diǎn)[f（x）]值大于等于[f*n]，則[f（x）-f*n+]等于正值[f（x）-f*n]，否則[f（x）-f*n+]為0），再計(jì)算所有[x]處的改進(jìn)值的數(shù)學(xué)期望，并將數(shù)學(xué)期望最大的[x]點(diǎn)作為下一個(gè)探索點(diǎn)。期望改進(jìn)函數(shù)如公式（5） 所示：

[EInx=Enf（x）-f*n+]? ? ? ? ? ?（5）

根據(jù)上述公式計(jì)算出[n]個(gè)采樣點(diǎn)[x1，x2，x3，...xn]和函數(shù)值[y1，y2，y3，...yn].該期望采用高斯過(guò)程回歸定義。假設(shè)在[xn]點(diǎn)的均值為[μ（x）]方差為[σ2（x）]，令[Z=f（x）]，根據(jù)期望定義能夠得出公式（6） ：

[EIn（x）=-∞+∞Zf*n+12πσexp-（Z-μ）22σ2dZ]? ?（6）

化簡(jiǎn)為如公式（7） 所示：

[EIn（x）=-∞+∞（Z-f*n）12πσexp-（Z-μ）22σ2dZ] （7）

對(duì)公式（7） 進(jìn)行換元可以得到公式（8） 如下所示：

[EIn（x）=μ-f*n（1-δf*n-μ/σ+σφf(shuō)*n-μ/σ）]? ? ? ? ? ? ? ? ? ? ? ? ? ? （8）

其中[δ（x）]為正態(tài)標(biāo)準(zhǔn)分布函數(shù)，若令[G（x）=μ-f*n]則有公式（9） ：

[EIn（x）=G（x）++σ（x）φG（x）σ（x）-G（x）δG（x）σ（x）]? ? （9）

因此由上述公式可以推導(dǎo)出[μ（x）]，[σ2（x）]均為[x]的函數(shù)，因此EI也是[x]的函數(shù)。為了能夠優(yōu)化目標(biāo)函數(shù)[f（x）]因此通過(guò)最大化[EIn（x）]來(lái)得到新的評(píng)估點(diǎn)[xn+1]，計(jì)算如公式（10） 所示：

[xn+1=argmaxEIn（x）]? ? ? ? ? ? ? ?（10）

3 BO-DPC算法

3.1 主要思想

DPC在數(shù)據(jù)聚類(lèi)方面具有很好的性能，但是截?cái)嗑嚯x[dc]值研究者憑借經(jīng)驗(yàn)設(shè)定的，DPC算法不能完全發(fā)揮DPC算法的性能。因此本文選取貝葉斯算法來(lái)優(yōu)化DPC聚類(lèi)，利用貝葉斯算法預(yù)測(cè)出的較優(yōu)[dc]值，驅(qū)動(dòng)DPC算法選擇出合適的聚類(lèi)中心，提高DPC聚類(lèi)算法的性能。獲得最終的聚類(lèi)結(jié)果。BO-DPC算法的流程圖如圖1所示。

當(dāng)數(shù)據(jù)數(shù)量較多，類(lèi)間距離不均勻時(shí)，試圖依靠用戶(hù)的經(jīng)驗(yàn)來(lái)人工確定一個(gè)合適的[dc]值并取得較好的聚類(lèi)效果是相當(dāng)困難的一項(xiàng)任務(wù)，這也是阻礙DPC算法廣泛應(yīng)用的主要瓶頸之一。本文認(rèn)為不應(yīng)事先確定密度峰值聚類(lèi)算法的這一項(xiàng)關(guān)鍵參數(shù)，而應(yīng)在聚類(lèi)過(guò)程中根據(jù)聚類(lèi)的結(jié)果來(lái)不斷對(duì)該參數(shù)尋優(yōu)，直到算法逐漸收斂于使目標(biāo)函數(shù)值最大化的全局最優(yōu)截?cái)嗑嚯x[dc]值。首先創(chuàng)建截?cái)嗑嚯x[dc]值的尋參空間和生成尋優(yōu)初選集合，輪廓系數(shù)Silhouette是簇的密集與分散程度的評(píng)價(jià)指標(biāo)，它結(jié)合了內(nèi)聚度和分離度兩種因素，因?yàn)樗梢杂脕?lái)在相同原始數(shù)據(jù)的基礎(chǔ)上評(píng)價(jià)算法不同運(yùn)行方式對(duì)聚類(lèi)效果的影響，因此本文將Silhouette指標(biāo)函數(shù)作為[f（x）]目標(biāo)函數(shù)進(jìn)行尋優(yōu)。算法的最終目的在于優(yōu)化[f（x）]指標(biāo)值，使得[dc]值向最優(yōu)的[dc]值慢慢靠近，因此希望采集函數(shù)每次評(píng)估的[dc]值都盡可能使得[f（x）]達(dá)到更大。通過(guò)采集函數(shù)[EI]進(jìn)行構(gòu)造，使得探索開(kāi)發(fā)區(qū)域平衡，進(jìn)而獲取新的評(píng)估點(diǎn)[dc]，豐富[dc]集合。設(shè)置最大迭代次數(shù)為[N]，通過(guò)對(duì)原有[dc]值集合進(jìn)行[N]次的迭代更新尋找最優(yōu)[dc]值。最終找到使目標(biāo)函數(shù)Silhouette值最大的[dc]值作為最優(yōu)參數(shù)，然后用這個(gè)[dc]值完成后續(xù)的密度峰值聚類(lèi)步驟。

3.2 算法步驟

4 實(shí)驗(yàn)的仿真與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

為測(cè)試BO-DPC算法的聚類(lèi)效果，本文采用以下Aggregation、Flame、Jain、Spiral四種數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對(duì)比，四種數(shù)據(jù)集實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表3。

Aggregation、Flame、Spiral是二維數(shù)據(jù)集，F(xiàn)lame、Spiral在數(shù)據(jù)點(diǎn)個(gè)數(shù)上較少。Jain數(shù)據(jù)集為三維數(shù)據(jù)集在數(shù)據(jù)處理時(shí)需對(duì)Jain數(shù)據(jù)集維度進(jìn)行降維。

4.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

為驗(yàn)證BO-DPC聚類(lèi)效果的有效性，本文選取了內(nèi)部和外部評(píng)價(jià)指標(biāo)進(jìn)行分析，分別是Silhouette指標(biāo)和F-measure指標(biāo)。

1） Silhouette評(píng)價(jià)指標(biāo)：

Silhouette遵循類(lèi)的緊致性，用來(lái)描述目標(biāo)自身所處的簇和其他簇之間的相似性。其范圍為[-1，1]之間，Silhouette越大表明自身所在關(guān)系之間的匹配度越高，相反的與其他非自身相關(guān)簇匹配度越低。Silhouette的定義：對(duì)于聚類(lèi)算法已經(jīng)分成了很多類(lèi)，對(duì)于目標(biāo)[i]有[i?Ci]，[Ci]表示為第[i]個(gè)簇，就可以得到樣本[i]在[Ci]類(lèi)中與其他所有樣本平均不相似度[a（i）]，計(jì)算如公式如（11） 所示：

[ a（i）=1Ci-1j?Ci，i≠jdij]? ? ? ? ? ? ?（11）

對(duì)于目標(biāo)[i]有[i?Ck]，[Ck]表示為第[k]個(gè)簇。[b（i）]表示為到[Ck]類(lèi)平均不相似度，計(jì)算如公式如（12） 所示：

[b（i）=mink≠i1Ckj?Ck，i≠jdij]? ? ? ? ?（12）

根據(jù)如上公式（11）、（12） 可以定義出Silhouette指標(biāo)計(jì)算公式如（13） 所示：

[Sili=b（i）-a（i）max{a（i），b（i）}]? ? ? ? ? ? ?（13）

2） F-measure評(píng)價(jià)指標(biāo)：

F-measure指標(biāo)是結(jié)合了信息檢索中準(zhǔn)確率（ACC） 和查全率（Recall） 聚類(lèi)算法的外部評(píng)價(jià)方法，ACC、Recall、F-measure評(píng)價(jià)指標(biāo)計(jì)算公式如（14） 、（15） 、（16） 所示：

[? ACC=TP+TNTP+TN+FP+FN]? ? ? ? ? ?（14）

[Recall=TPTP+FN]? ? ? ? ? ? ? ?（15）

[F1-measure=2Precision?RecallPrecision+Recall]? ? ? ?（16）

TP表示兩個(gè)數(shù)據(jù)樣本在同一個(gè)簇的數(shù)量情況，TN表示兩個(gè)非同類(lèi)樣本在兩個(gè)簇中的數(shù)量情況。FP表示非同類(lèi)數(shù)據(jù)樣本在同一個(gè)簇的數(shù)量情況，F(xiàn)N表示兩個(gè)同類(lèi)樣本分別在兩個(gè)簇中的數(shù)量情況。如表2所示為以上四種參數(shù)的混淆矩陣（Pair Confusion Matrix）。

4.3 實(shí)驗(yàn)結(jié)果與分析：

本文在內(nèi)存12G筆記本上采用python對(duì)BO-DPC算法和DPC算法進(jìn)行實(shí)驗(yàn)仿真。通過(guò)四個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)比對(duì)，根據(jù)實(shí)驗(yàn)結(jié)果BO-DPC聚類(lèi)算法在內(nèi)部評(píng)價(jià)指標(biāo)Silhouette和外部評(píng)價(jià)指標(biāo)F-measure上均優(yōu)于傳統(tǒng)的DPC算法。兩種算法的評(píng)價(jià)指標(biāo)如表5所示：

根據(jù)表5可以得出基于BO算法優(yōu)化的DPC建立在Aggregation、Flame、Jain和Spiral數(shù)據(jù)集上的內(nèi)部指標(biāo)Sil和外部指標(biāo)F-measure均有提升。在數(shù)據(jù)集Aggregation、Flame、Jain、Spiral中，BO優(yōu)化后的DPC算法Sil指標(biāo)相比于DPC算法提高提升了1.7%、1.3%、4.5%、3.3%。F-measure提升了3.3%、1.9%、2.2%、3.8%。Aggregation、Flame、Jain和Spiral聚類(lèi)結(jié)果二維圖分別如圖2～圖5所示：

由圖2～圖5四種數(shù)據(jù)集聚類(lèi)二維示例圖可以看出，本文BO-DPC算法和DPC算法都可兼顧到各點(diǎn)的密度和點(diǎn)間距的內(nèi)部關(guān)系?？梢詼?zhǔn)確地確定數(shù)據(jù)集類(lèi)簇的數(shù)量和確定類(lèi)簇中心點(diǎn)。但對(duì)于傳統(tǒng)的DPC算法，相比于BO-DPC算法對(duì)簇邊界的點(diǎn)容易造成誤判，對(duì)大型簇的劃分較為混亂。改進(jìn)后的BO-DPC會(huì)對(duì)誤判的簇邊界點(diǎn)進(jìn)行修正和劃分合理的簇類(lèi)。

綜上所述BO-DPC 算法相對(duì)于DPC算法在處理不同大小的數(shù)據(jù)集都有較好的效果。通過(guò)BO算法在尋優(yōu)空間進(jìn)行迭代尋參，對(duì)DPC算法聚類(lèi)結(jié)果進(jìn)行修正，可以提升聚類(lèi)效果。盡管BO-DPC算法效果提升不太明顯，但是可以看出該算法在Aggregation、Flame、Jain、Spiral數(shù)據(jù)集上表現(xiàn)優(yōu)于算法樣本自身分布，體現(xiàn)了BO-DPC適應(yīng)性較強(qiáng)。

5 結(jié)束語(yǔ)

傳統(tǒng)DPC聚類(lèi)算法需要指定截?cái)嗑嚯x，本文提出采用貝葉斯算法提升DPC聚類(lèi)性能，通過(guò)在尋優(yōu)空間計(jì)算迭代找到適應(yīng)度最優(yōu)的[dc]值，使BO-DPC算法聚類(lèi)效果達(dá)到最優(yōu)。通過(guò)實(shí)驗(yàn)分析BO-DPC算法相比于傳統(tǒng)的DPC算法在內(nèi)部指標(biāo)Silhouette和外部評(píng)價(jià)指標(biāo)F-measure當(dāng)中都有更優(yōu)異的表現(xiàn)。接下來(lái)研究重點(diǎn)如何進(jìn)一步提升DPC聚類(lèi)算法的性能是后續(xù)工作的重點(diǎn)。

參考文獻(xiàn)：

[1] 胡明，唐東凱，李芬田，等.不確定聚類(lèi)中距離計(jì)算方法綜述[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，29（5）：477-483.

[2] Xu R，Wunsch D.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks，2005，16（3）：645-678.

[3] Zhao W L，Deng C H，Ngo C W.K-means：a revisit[J].Neurocomputing，2018，291：195-206.

[4] Ester M，Kriegel H P，Sander J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//kdd，1996，96（34）：226-231.

[5] Rodriguez A，Laio A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1496.

[6] Liu Y H，Ma Z M，Yu F.Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy[J].Knowledge-Based Systems，2017，133：208-220.

[7] Seyedi S A，Lotfi A，Moradi P，et al.Dynamic graph-based label propagation for density peaks clustering[J].Expert Systems With Applications，2019，115：314-328.

[8] Xie J Y，Gao H C，Xie W X，et al.Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors[J].Information Sciences，2016，354：19-40.

[9] Shahriari B，Swersky K，Wang Z Y，et al.Taking the human out of the loop：a review of Bayesian optimization[J].Proceedings of the IEEE，2016，104（1）：148-175.

[10] Ghahramani Z.Probabilistic machine learning and artificial intelligence[J].Nature，2015，521（7553）：452-459.

[11] Jiang J H，Tao X，Li K Q.DFC：density fragment clustering without peaks[J].Journal of Intelligent & Fuzzy Systems，2018，34（1）：525-536.

[12] Jiang J H，Hao D H，Chen Y J，et al.GDPC：gravitation-based density peaks clustering algorithm[J].Physica A：Statistical Mechanics and Its Applications，2018，502：345-355.

[13] Williams C K，Rasmussen C E.Gaussian processes for machine learning[M].Cambridge，MA：MIT press，2006.

[14] Hoffman M，Brochu E，De Freitas N.Portfolio Allocation for Bayesian Optimization[C]//UAI，2011：327-336.

【通聯(lián)編輯：謝媛媛】