基于高斯核優(yōu)化的密度峰值聚類算法

王艦

摘要：DPC算法在處理緊密相鄰的團(tuán)形簇時(shí)，對(duì)于簇間樣本點(diǎn)分配效果不佳，同時(shí)DPC算法對(duì)于團(tuán)形簇由密集到稀疏的漸變區(qū)域，即邊界點(diǎn)和噪音點(diǎn)的劃分也存在著缺陷。針對(duì)這兩個(gè)問(wèn)題，本文提出基于高斯核優(yōu)化的密度峰值聚類算法（Gauss-DPC）。Gauss-DPC算法在DPC聚類算法快速發(fā)現(xiàn)簇中心的基礎(chǔ)之上，通過(guò)計(jì)算簇內(nèi)樣本點(diǎn)到簇中心距離的統(tǒng)計(jì)量，利用統(tǒng)計(jì)量構(gòu)建高斯判別式，使用高斯判別式進(jìn)行簇間樣本點(diǎn)的分配，最后引入高斯約束來(lái)區(qū)分簇邊界點(diǎn)和噪聲點(diǎn)。通過(guò)實(shí)驗(yàn)證明了Gauss-DPC算法具有更好的聚類效果，而且Gauss-DPC可以動(dòng)態(tài)的控制簇的邊界范圍。

關(guān)鍵詞：密度峰值聚類;簇內(nèi)統(tǒng)計(jì)量;高斯核;邊界約束

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

文章編號(hào)：1009-3044（2020）28-0192-03

1引言

聚類算法作為無(wú)監(jiān)督學(xué)習(xí)的分支，是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究方向。聚類算法在無(wú)任何先驗(yàn)知識(shí)的情況下，對(duì)數(shù)據(jù)集進(jìn)行特征提取[1]，發(fā)現(xiàn)數(shù)據(jù)中隱藏的內(nèi)在模式與規(guī)律。目前聚類算法的主要分類有基于劃分的聚類、基于層次的聚類、基于密度的聚類，基于圖論的聚類等[2，3]。K-means[4]算法是經(jīng)典的基于劃分的聚類算法，但是需要人工輸入聚類的簇個(gè)數(shù)，并且對(duì)非球形的數(shù)據(jù)聚類效果不好?；诿芏鹊木垲愃惴ɡ鏒BSCAN[5]，該算法需要人工輸入兩個(gè)參數(shù)，半徑和半徑內(nèi)樣本點(diǎn)數(shù)量閾值，DBSCAN算法遇到數(shù)據(jù)集樣本點(diǎn)分布密度差距較大的情況時(shí)聚類效果較差，DBSCAN算法的時(shí)間復(fù)雜度為O（n2），當(dāng)數(shù)據(jù)集規(guī)模較大時(shí)所消耗的計(jì)算資源非常大。2014年6月，Rodriguez等人在Science上發(fā)表的DPC[6]算法（《Clustering by fast search and find of density peaks》）為聚類算法的設(shè)計(jì)提供了一種新的思路。DPC算法基于兩個(gè)假設(shè)，第一簇中心擁有最大局部密度，第二兩個(gè)簇中心距離較遠(yuǎn)。DPC算法能夠適應(yīng)任意形狀的類簇，自動(dòng)獲取數(shù)據(jù)集中密度峰值樣本點(diǎn)。

近幾年，隨著DPC算法研究的深入，有大量針對(duì)該算法的優(yōu)化和改進(jìn)。謝娟英等人[7]提出了基于K近鄰優(yōu)化的KNN-DPC算法，該算法基于樣本點(diǎn)的K個(gè)最近鄰樣本點(diǎn)信息，計(jì)算樣本點(diǎn)的密度，然后在分配非簇中心時(shí)，按照K近鄰關(guān)系逐個(gè)分配。紀(jì)霞等人[8]通過(guò)相似度函數(shù)，找出每個(gè)點(diǎn)的K近鄰，然后根據(jù)K近鄰信息判斷樣本點(diǎn)的指向是否正確，從而可以有效減少錯(cuò)誤分配。

DPC算法也存在著不足，對(duì)于緊密聚集的團(tuán)形簇，DPC算法對(duì)于簇間共享的樣本點(diǎn)分配存在誤判，針對(duì)這一問(wèn)題提出高斯判別優(yōu)化的密度峰值聚類算法（Density Peak ?Clustering algorithm based on Gaussian kernel optimization， Gauss-DPC）。Gauss-DPC算法從樣本分布頻率的角度對(duì)光暈點(diǎn)進(jìn)行分配。

2密度峰值聚類算法

DPC算法有一個(gè)需要人工設(shè)置的參數(shù)截?cái)嗑嚯x[dc]，數(shù)據(jù)集中的樣本點(diǎn)以[dc]為半徑計(jì)算局部密度。DPC算法使用[dc]來(lái)計(jì)算兩個(gè)關(guān)鍵參數(shù)，局部密度[ρ]和高局部密度最小距離[δ]。DPC算法將簇間共享的樣本點(diǎn)命名為光暈點(diǎn)，光暈點(diǎn)的具體定義為：如果樣本點(diǎn)[i]的截?cái)嗑嚯x半徑之內(nèi)存在一個(gè)樣本[j]與[i]屬于不同簇，則稱點(diǎn)[i]為光暈點(diǎn)。

密度峰值聚類算法的聚類過(guò)程的創(chuàng)新之處在于簇中心的獲取，在得到每個(gè)樣本點(diǎn)的局部密度[ρi]和高局部密度最小距離[δi]后，以[ρ]為x軸，[δ]為y軸構(gòu)造決策圖，使用決策圖輔助選取密度峰值點(diǎn)，也即簇的中心。在獲取簇中心之后，將每個(gè)樣本點(diǎn)指向比自身密度更高且最近的樣本點(diǎn)，通過(guò)這種逐層迭代的方法分配非簇中心點(diǎn)。

3高斯核優(yōu)化的密度峰值聚類算法

DPC算法的優(yōu)勢(shì)在于通過(guò)構(gòu)建決策圖可以快速確定簇中心，但是DPC算法單一的樣本點(diǎn)分配策略對(duì)于簇間光暈點(diǎn)分配和噪音點(diǎn)識(shí)別存在不足。本文提出的Gauss-DPC算法將簇內(nèi)樣本點(diǎn)分布轉(zhuǎn)化為點(diǎn)到簇中心的距離，通過(guò)計(jì)算距離的統(tǒng)計(jì)信息構(gòu)建高斯判別式，利用高斯判別式改善了原DPC算法的不足。

3.1高斯判別式相關(guān)定義

本節(jié)將介紹高斯判別式的相關(guān)定義。

定義7 ?高斯約束系數(shù)（Gausslimit）

Gausslimit為人工輸入可調(diào)參數(shù)，作用是用來(lái)判別低局部密度點(diǎn)的屬性。將低密度點(diǎn)的樣本簇內(nèi)距離[dcen]和對(duì)應(yīng)的簇內(nèi)統(tǒng)計(jì)量代入高斯判別式，求出對(duì)應(yīng)的值與Gausslimit進(jìn)行對(duì)比來(lái)判斷是簇邊界還是噪音點(diǎn)。

3.2高斯判別式處理光暈點(diǎn)歸屬

結(jié)合3.1小節(jié)定義的簇內(nèi)統(tǒng)計(jì)量的相關(guān)定義，本節(jié)將基于高斯核判別式應(yīng)用到簇間光暈樣本點(diǎn)歸屬的判斷。

高斯判別式進(jìn)行簇間光暈點(diǎn)歸屬判斷的過(guò)程如下：取出光暈點(diǎn)距離兩個(gè)簇中心的距離，分別代入兩個(gè)局部核心簇的高斯判別式（公式4）;對(duì)比兩個(gè)高斯判別式值的大小，將光暈點(diǎn)歸入高斯判別式值大的那個(gè)簇。高斯判別過(guò)程模型如圖1所示。

3.3簇邊界點(diǎn)和噪音點(diǎn)判斷

在高斯判別式的基礎(chǔ)之上引入高斯約束來(lái)區(qū)分簇邊界點(diǎn)和噪聲點(diǎn)。首先通過(guò)稀疏局部密度閾值[ρlimit]篩選出可能為噪音的樣本點(diǎn)，然而低密度點(diǎn)可能是簇邊界點(diǎn)或者少量聚集的噪音點(diǎn)，雖然為密度相近的密度低點(diǎn)，但是邊界點(diǎn)的簇內(nèi)距離[dcen]顯然比少量聚集的噪音點(diǎn)的簇內(nèi)距離[dcen]要小;然后利用高斯判別式，將低密度點(diǎn)的簇內(nèi)距離[dcen]代入到高斯判別式，邊界點(diǎn)對(duì)應(yīng)的高斯判別式值要大于噪音點(diǎn)對(duì)應(yīng)的高斯判別式值。再將計(jì)算出來(lái)的高斯判別式的值和高斯約束的值進(jìn)行對(duì)比，小于高斯約束值的樣本點(diǎn)判定為噪音點(diǎn)。

3.4Gauss-DPC算法

Gauss-DPC算法首先通過(guò)引入簇內(nèi)統(tǒng)計(jì)量的概念，對(duì)DPC算法輸出的每一個(gè)簇獨(dú)立構(gòu)建高斯判別式，以此來(lái)處理簇間歸屬有爭(zhēng)議的光暈點(diǎn)。然后引入稀疏局部密度閾值率，將可能是噪音點(diǎn)的低密度樣本點(diǎn)篩選出來(lái);最后通過(guò)高斯約束系數(shù)，再次利用高斯判別式將低密度樣本點(diǎn)分為邊界點(diǎn)和噪音點(diǎn)。Gauss-DPC算法流程如表1所示。

Gauss-DPC算法流程圖如圖2所示。

4實(shí)驗(yàn)分析

為驗(yàn)證Gauss-DPC算法的效果，實(shí)驗(yàn)用到3個(gè)數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，數(shù)據(jù)集相關(guān)信息見(jiàn)表2。

R15數(shù)據(jù)集是有15個(gè)團(tuán)形簇的數(shù)據(jù)集，由圖3（a）可得Gauss-DPC算法可以精準(zhǔn)地識(shí)別出離群點(diǎn)。圖3（b）為 DPC算法的聚類結(jié)果，可以看出DPC算法雖然正確的聚類，但是對(duì)噪音點(diǎn)的識(shí)別不可控。圖3（c） DBSCAN算法聚類結(jié)果，DBSCAN可以正確聚類，但是為了得到正確聚類結(jié)果需要經(jīng)過(guò)多次反復(fù)調(diào)參。由圖3（d）可知K-means算法對(duì)于稀疏的團(tuán)形簇聚類效果較好。

D31數(shù)據(jù)集為31個(gè)復(fù)雜團(tuán)形簇聚集的數(shù)據(jù)集。由圖3（a）可以看出Gauss-DPC算法對(duì)比復(fù)雜地聚集在一起的團(tuán)形數(shù)據(jù)集可以準(zhǔn)確地聚類，同時(shí)還可以精準(zhǔn)地對(duì)噪音進(jìn)行識(shí)別。圖3（b）為DPC算法聚類結(jié)果，DPC算法對(duì)于緊密聚在一起的簇存在嚴(yán)重的簇邊界誤判情況。圖3（d）為DBSCAN算法的聚類結(jié)果，DBSCAN算法無(wú)法區(qū)分緊密聚集在一起的簇。由圖3（d）可以看出，對(duì)于復(fù)雜的團(tuán)形簇K-means算法對(duì)于簇邊界點(diǎn)有明顯的錯(cuò)誤分類。

Aggregation數(shù)據(jù)集是典型的不規(guī)則的團(tuán)形簇，一共有由7個(gè)簇，Gauss-DPC，DPC，DNSCAN算法均能正確的得到7個(gè)簇的聚類結(jié)果，但是由圖5（b）和5（c）可知DPC算法和DBSCAN算法將部分粗邊界點(diǎn)判斷為噪音點(diǎn)。由圖5（a）可知Gauss-DPC算法對(duì)于簇邊界可以正確的判斷，對(duì)于簇邊界點(diǎn)誤判的噪音點(diǎn)，可以通過(guò)高斯約束參數(shù)作為修正，將誤判為噪音的樣本點(diǎn)修正為相應(yīng)的簇內(nèi)樣本點(diǎn)。由圖5（d）可知K-means算法將一個(gè)大型簇一分為二，可見(jiàn)周?chē)⌒痛貙?duì)于整體的聚類效果會(huì)發(fā)生影響。

綜上Gauss-DPC算法可對(duì)簇間光暈點(diǎn)根據(jù)簇內(nèi)密度進(jìn)行自適應(yīng)劃分，通過(guò)調(diào)節(jié)低密度閾值和高斯約束兩個(gè)參數(shù)，實(shí)現(xiàn)對(duì)簇邊界的約束，經(jīng)過(guò)對(duì)DPC算法聚類結(jié)果的兩次修正，提升聚類結(jié)果的準(zhǔn)確率。盡管Gauss-DPC算法對(duì)于部分?jǐn)?shù)據(jù)集上聚類效果不佳，但是得益于Gauss-DPC算法樣本自身分布統(tǒng)計(jì)信息對(duì)交叉樣本進(jìn)行分類，在大部分?jǐn)?shù)據(jù)集上表現(xiàn)較優(yōu)，體現(xiàn)了較強(qiáng)的適應(yīng)性。

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

本文提出了基于高斯核優(yōu)化的密度峰值聚類算法，從頻率分布的思想進(jìn)行判別簇間樣本點(diǎn)歸屬，以及判斷簇邊界和噪音點(diǎn)的判斷。通過(guò)實(shí)驗(yàn)，將Gauss-DPC與DPC，DBSCAN，K-means進(jìn)行對(duì)比，證明了Gauss-DPC算法有更好的聚類結(jié)果。Gauss-DPC算法引入了低密度閾值和高斯約束兩個(gè)可調(diào)參數(shù)，實(shí)現(xiàn)了根據(jù)數(shù)據(jù)特征和實(shí)際應(yīng)用的需求對(duì)簇的邊界范圍進(jìn)行控制。

參考文獻(xiàn)：

[1] 喬少杰，韓楠，張凱峰.復(fù)雜網(wǎng)絡(luò)大數(shù)據(jù)中重疊社區(qū)檢測(cè)算法[J].軟件學(xué)報(bào)，2017，28（3）：631-647.

[2] 謝娟英，丁麗娟. 基于譜聚類的無(wú)監(jiān)督特征選擇算法[J]. 軟件學(xué)報(bào)，2020，31（4）：1009-1024

[3] 陳葉旺，申蓮蓮，鐘才明，等.密度峰值聚類算法綜述[J].計(jì)算機(jī)研究與發(fā)展，2020，57（2）：378-394.

[4] MacQueenJ. Some Methods for Classification and Analysis of MultiVariate Observations[C].Proc of Berkeley Symposium on Mathematical Statistics & Probability， 1965.

[5] Ester M， Kriegel H P. A density-based algorithm for discovering clusters in large spatial databases with noise[C]. Proceedings of the second International Conference on Knowledge Discovery and Data Mining， 1996， 96（34）： 226-231.

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

[7] 謝娟英，高紅超，謝維信.K近鄰優(yōu)化的密度峰值快速搜索聚類算法[J].中國(guó)科學(xué)：信息科學(xué)，2016，46（2）：258-280.

[8] 紀(jì)霞，張濤，朱建磊，等.近鄰密度分布優(yōu)化樣本分配的改進(jìn)DPC聚類算法[J].華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，47（2）：98-105.

【通聯(lián)編輯：唐一東】