基于貝葉斯優化的密度峰值聚類算法

吳濤 朱小東 劉喚喚 張順香

摘要：針對人工經驗設定密度峰值的聚類算法（clustering by fast search and find of density peaks， DPC）的截斷距離[dc]有很大的主觀性和隨機性，進而導致密度峰值聚類算法的性能無法完全發揮的問題。提出貝葉斯算法（Bayesian Optimization，BO） 優化密度峰值的聚類算法以實現自適應聚類。并解決密度峰值的聚類算法簇間數據點識別錯誤問題。該方法建立在數據集Aggregation、Flame、Jain、Spiral上進行實驗，分別通過內部指標Silhouette和外部指標F-measure對實驗結果評估，性能均有提升。

關鍵詞：密度峰值的聚類算法;截斷距離;貝葉斯算法;自適應聚類;內部指標

中圖分類號：TP391? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）22-0008-05

1 引言

21世紀隨著互聯網的快速普及，人們在形形色色的生活中產生了大量的數據，大數據的時代隨之來臨，怎樣從這些數據中獲得有用的信息成為當今研究熱點。

聚類是數據挖掘、機器學習、圖像識別等領域預處理數據的一種基本算法。聚類把一組沒有標簽定義的數據集或者樣本集，依據樣本的一組特征值，按照某種相似性度量手段將特征值相似度較高的數據點劃分成同一個類簇，為后續處理提供了可貼標簽的分類數據。

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

DPC算法[5]是近幾年提出的一種基于密度劃分的聚類算法，該算法依據密度峰值決策圖選取合適的密度峰點;并將圖中代表樣本的其他數據點劃分到最近或匹配的密度峰點類別中，從而得出簇的劃分。DPC算法的優點之一是除了決策圖中的密度峰值點需要人工干預選擇外，整個算法僅需要預先給出一個輸入參數（截斷距離） ，不需要像多數其他聚類算法一般預先指定簇數目，提高了算法的可靠性與適應性。另一方面，DPC算法在初期決策圖中選擇的密度峰點即確定了簇的數目及分布，不需要通過反復迭代來獲得最優結果，其效率相對于其他聚類算法有著顯著優勢。

隨著對DPC算法的不斷深入研究，越來越多的改進DPC算法相繼出現。針對DPC算法的局部密度計算方式過于單一的問題，Liu等人[6]提出ADPC結合KNN的算法，該算法重新定義了局部密度的計算方法。針對DPC算法的一次性樣本數據分配策略可能存在錯誤分配連帶問題，即一旦一個數據點被錯誤分配，隨后可能會有更多的點被錯誤分配，Seyed等人[7]提出了一種DPC-DLP的聚類算法，該算法統一確定簇中心，將簇中心聯合起來構建新的KNN圖，通過圖的傳播方法分配樣本數據。Xie[8]等人提出了計算數據[ai]相對于[其K]近鄰的局部密度度量方式和通過從聚類中心開始對點的K個最近鄰進行廣度優先搜索來分配數據點，從而對DPC聚類算法進行優化。

面對不同類型數據時，這些改進的DPC聚類算法雖然有較好的聚類結果，但是截斷距離仍需要人為設定。當數據密度相差較大時，很難人為選擇一個合適的截斷距離，如果輸入截斷距離百分比過大時可能會出現所有數據點都被分到同一類，如果輸入截斷距離百分比過小時可能會出現聚類數目過多。所以截斷距離[dc]是影響聚類效果好壞的重要參數，截斷距離優化其實就是機器學習中超參數優化，目前主流的機器學習超參數優化方法有群體智能優化算法、網格搜索（即窮舉法） 、隨機搜索算法、貝葉斯優化算法。但是群體智能優化算法先要提供非常多的初始樣本點，并且其優化效率一般。網格搜索算法是將所有涉及的超參數進行組合，對每個組合進行建模與評價，最后選擇評價最高的組合作為模型最終的超參數，這種方法需要經過長時間的計算才能獲得最優的超參數組合。而隨機搜索則是在超參數的分布中隨機搜索超參數進行建模，它的缺點是容易錯過一些最優超參數。貝葉斯優化方法要優于群體智能優化算法、網格搜索算法和隨機搜索算法，因為它在嘗試下一組超參數時，會借鑒之前的評估結果，省去了很多無用功。因此本文選取貝葉斯算法[9-10]（Bayesian Optimization） 作為DPC聚類算法的優化手段，利用貝葉斯算法預測出的較優[dc]值，驅動DPC算法選擇出合適的聚類中心，提高DPC聚類算法的性能。

2 相關研究

2.1 DPC算法

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

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

2） 要使得不同簇中心之間的距離相對較遠。

為了能夠準確找到同時滿足以上兩個條件的簇中心，DPC算法引入了局部密度的定義。局部密度的計算如公式（1） 所示：

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

假設數據點[ai]的局部密度為[ρi]，[dij]為[ai]到[aj]的距離，[dc]為兩點間的截斷距離。[f（x）]為邏輯判斷函數，當[x]值小于0時[f（x）]判定為1否則[f（x）]判斷為0，該函數表示為滿足一定距離閾值數目[ai]的多少，數目越多值越大，密度越高。

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

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

[δi]表示為高密度的最小距離為[ai]到[aj]距離最近并且局部密度大于[ai]的局部密度的距離。當[ai]為數據集中密度最大的點時[δi]的計算如公式（3） 所示：

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

2.2 貝葉斯優化算法

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

1） 采集函數的構建

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

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

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

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

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

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

化簡為如公式（7） 所示：

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

對公式（7） 進行換元可以得到公式（8） 如下所示：

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

其中[δ（x）]為正態標準分布函數，若令[G（x）=μ-f*n]則有公式（9） ：

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

因此由上述公式可以推導出[μ（x）]，[σ2（x）]均為[x]的函數，因此EI也是[x]的函數。為了能夠優化目標函數[f（x）]因此通過最大化[EIn（x）]來得到新的評估點[xn+1]，計算如公式（10） 所示：

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

3 BO-DPC算法

3.1 主要思想

DPC在數據聚類方面具有很好的性能，但是截斷距離[dc]值研究者憑借經驗設定的，DPC算法不能完全發揮DPC算法的性能。因此本文選取貝葉斯算法來優化DPC聚類，利用貝葉斯算法預測出的較優[dc]值，驅動DPC算法選擇出合適的聚類中心，提高DPC聚類算法的性能。獲得最終的聚類結果。BO-DPC算法的流程圖如圖1所示。

當數據數量較多，類間距離不均勻時，試圖依靠用戶的經驗來人工確定一個合適的[dc]值并取得較好的聚類效果是相當困難的一項任務，這也是阻礙DPC算法廣泛應用的主要瓶頸之一。本文認為不應事先確定密度峰值聚類算法的這一項關鍵參數，而應在聚類過程中根據聚類的結果來不斷對該參數尋優，直到算法逐漸收斂于使目標函數值最大化的全局最優截斷距離[dc]值。首先創建截斷距離[dc]值的尋參空間和生成尋優初選集合，輪廓系數Silhouette是簇的密集與分散程度的評價指標，它結合了內聚度和分離度兩種因素，因為它可以用來在相同原始數據的基礎上評價算法不同運行方式對聚類效果的影響，因此本文將Silhouette指標函數作為[f（x）]目標函數進行尋優。算法的最終目的在于優化[f（x）]指標值，使得[dc]值向最優的[dc]值慢慢靠近，因此希望采集函數每次評估的[dc]值都盡可能使得[f（x）]達到更大。通過采集函數[EI]進行構造，使得探索開發區域平衡，進而獲取新的評估點[dc]，豐富[dc]集合。設置最大迭代次數為[N]，通過對原有[dc]值集合進行[N]次的迭代更新尋找最優[dc]值。最終找到使目標函數Silhouette值最大的[dc]值作為最優參數，然后用這個[dc]值完成后續的密度峰值聚類步驟。

3.2 算法步驟

4 實驗的仿真與分析

4.1 實驗數據

為測試BO-DPC算法的聚類效果，本文采用以下Aggregation、Flame、Jain、Spiral四種數據集進行實驗對比，四種數據集實驗數據見表3。

Aggregation、Flame、Spiral是二維數據集，Flame、Spiral在數據點個數上較少。Jain數據集為三維數據集在數據處理時需對Jain數據集維度進行降維。

4.2 實驗評價指標

為驗證BO-DPC聚類效果的有效性，本文選取了內部和外部評價指標進行分析，分別是Silhouette指標和F-measure指標。

1） Silhouette評價指標：

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

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

對于目標[i]有[i?Ck]，[Ck]表示為第[k]個簇。[b（i）]表示為到[Ck]類平均不相似度，計算如公式如（12） 所示：

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

根據如上公式（11）、（12） 可以定義出Silhouette指標計算公式如（13） 所示：

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

2） F-measure評價指標：

F-measure指標是結合了信息檢索中準確率（ACC） 和查全率（Recall） 聚類算法的外部評價方法，ACC、Recall、F-measure評價指標計算公式如（14） 、（15） 、（16） 所示：

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

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

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

TP表示兩個數據樣本在同一個簇的數量情況，TN表示兩個非同類樣本在兩個簇中的數量情況。FP表示非同類數據樣本在同一個簇的數量情況，FN表示兩個同類樣本分別在兩個簇中的數量情況。如表2所示為以上四種參數的混淆矩陣（Pair Confusion Matrix）。

4.3 實驗結果與分析：

本文在內存12G筆記本上采用python對BO-DPC算法和DPC算法進行實驗仿真。通過四個數據集進行實驗比對，根據實驗結果BO-DPC聚類算法在內部評價指標Silhouette和外部評價指標F-measure上均優于傳統的DPC算法。兩種算法的評價指標如表5所示：

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

由圖2～圖5四種數據集聚類二維示例圖可以看出，本文BO-DPC算法和DPC算法都可兼顧到各點的密度和點間距的內部關系。可以準確地確定數據集類簇的數量和確定類簇中心點。但對于傳統的DPC算法，相比于BO-DPC算法對簇邊界的點容易造成誤判，對大型簇的劃分較為混亂。改進后的BO-DPC會對誤判的簇邊界點進行修正和劃分合理的簇類。

綜上所述BO-DPC 算法相對于DPC算法在處理不同大小的數據集都有較好的效果。通過BO算法在尋優空間進行迭代尋參，對DPC算法聚類結果進行修正，可以提升聚類效果。盡管BO-DPC算法效果提升不太明顯，但是可以看出該算法在Aggregation、Flame、Jain、Spiral數據集上表現優于算法樣本自身分布，體現了BO-DPC適應性較強。

5 結束語

傳統DPC聚類算法需要指定截斷距離，本文提出采用貝葉斯算法提升DPC聚類性能，通過在尋優空間計算迭代找到適應度最優的[dc]值，使BO-DPC算法聚類效果達到最優。通過實驗分析BO-DPC算法相比于傳統的DPC算法在內部指標Silhouette和外部評價指標F-measure當中都有更優異的表現。接下來研究重點如何進一步提升DPC聚類算法的性能是后續工作的重點。

參考文獻：

[1] 胡明，唐東凱，李芬田，等.不確定聚類中距離計算方法綜述[J].長春工業大學學報（自然科學版），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.

【通聯編輯：謝媛媛】