自動確定聚類中心的比較密度峰值聚類算法

，2*

（1.山東科技大學(xué)測繪科學(xué)與工程學(xué)院，山東青島 266590；2.山東省基礎(chǔ)地理信息與數(shù)字化技術(shù)重點實驗室（山東科技大學(xué)），山東青島 266590）

0 引言

隨著互聯(lián)網(wǎng)、社交網(wǎng)絡(luò)等技術(shù)的迅猛發(fā)展，數(shù)據(jù)源的多樣化使數(shù)據(jù)量呈現(xiàn)爆炸式的增長，如何在大規(guī)模數(shù)據(jù)集中進行有效的分析并挖掘背后的價值已經(jīng)成為了眾多行業(yè)面臨的首要問題。聚類分析［1］作為一種重要的數(shù)據(jù)挖掘技術(shù)，能夠在無監(jiān)督的條件下探索數(shù)據(jù)背后潛在的數(shù)據(jù)結(jié)構(gòu)。依據(jù)聚類算法原理的不同，可將現(xiàn)有的聚類算法大致分為五類［2-3］：劃分聚類［4］、層次聚類［5］、密度聚類［6］、網(wǎng)格聚類［7］以及模型聚類［8］。k-means 算法［9］是著名的劃分聚類算法，具有操作簡單、效率高等優(yōu)點，但需要預(yù)先指定聚類個數(shù)；基于密度的噪聲應(yīng)用空間聚類（Density-Based Spatial Clustering of Application with Noise，DBSCAN）算法［10］對密度估計使用了索引結(jié)構(gòu)，在處理大規(guī)模數(shù)據(jù)集時，有效地提高了聚類速度，但容易受鄰域半徑和閾值這兩個參數(shù)的影響；Ankerst 等［11］提出了OPTICS（Ordering Points To Identify the Clustering Structure）算法，該算法解決了DBSCAN 對輸入?yún)?shù)敏感的問題；Frey 等［12］提出了一種與k-means 同屬于劃分聚類的近鄰傳播（Affinity Propagation，AP）聚類算法，該算法不需要指定聚類個數(shù)，但所得的聚類個數(shù)受“preference”的影響。

2014 年6 月，Rodriguez 等［13］首次提出了密度峰值聚類（Density Peaks Clustering，DPC）算法。該算法簡單高效、無須迭代，能夠檢測任意形狀的類簇，且不需要提前設(shè)定類簇的數(shù)量，目前在圖像分割、醫(yī)學(xué)影像處理、社區(qū)發(fā)現(xiàn)［14-17］等領(lǐng)域具有潛在的應(yīng)用價值。但該算法也存在缺陷：1）采用歐氏距離進行距離度量，無法正確反映復(fù)雜數(shù)據(jù)集的分布情況；2）對截斷距離異常敏感，微小的變化就會導(dǎo)致不同的聚類結(jié)果；3）在確定聚類中心時需要根據(jù)決策圖手動選擇聚類中心，效率低下。為了解決DPC存在的問題，Du等［18］將流形學(xué)習(xí)的測地距離引入距離度量中，很好地解決了包含有多流行結(jié)構(gòu)的數(shù)據(jù)處理問題；Mehmood 等［19］引入熱擴散理論提出了一種從數(shù)據(jù)集中自動提取截斷距離的方法，解決了DPC 算法中參數(shù)難以確定的問題；吳斌等［20］將基尼系數(shù)引入提出了一種自適應(yīng)截斷距離的方法，以獲得最優(yōu)的截斷距離值；馬春來等［21］根據(jù)簇中心權(quán)值的變化趨勢來搜索“拐點”，并將“拐點”之前的點作為各簇中心，該算法避免了通過決策圖判斷簇中心的方法所帶來的誤差；丁志成等［22］利用KL（Kullback-Leibler）散度的差異性度量準(zhǔn)則劃分聚類中心點和非聚類中心點，根據(jù)散度排序圖中的拐點實現(xiàn)對聚類中心的自動選取。

基于現(xiàn)有研究，本文設(shè)計了一種自動確定聚類中心的比較密度峰值聚類算法（Comparative density Peaks Clustering algorithm with Automatic determination of clustering center，ACPC）。ACPC根據(jù)決策圖中數(shù)據(jù)的分布特征，采用了基于統(tǒng)計分析的二維區(qū)間估計方法來自動地識別決策圖中聚類中心點。距離比較量主要集中對第二個假設(shè)的定量建模上，使聚類中心點在決策圖中更明顯地區(qū)別于非聚類中心點。實驗結(jié)果說明，新算法有較高的準(zhǔn)確性且適應(yīng)性更好。

1 經(jīng)典DPC算法

密度峰值聚類算法是一種可以發(fā)現(xiàn)非凸簇類的新型聚類算法。其核心思想建立在對聚類中心點的兩個重要假設(shè)之上。

假設(shè)1 聚類中心的局部密度大于其周圍鄰近點的密度。

假設(shè)2 聚類中心與比其密度高的數(shù)據(jù)點的距離相對較遠。

根據(jù)這兩個設(shè)定，聚類中心應(yīng)該是同時具備較大局部密度和較大相對距離。要確定數(shù)據(jù)集的聚類中心，對于每一個數(shù)據(jù)點，都需要計算兩個屬性：數(shù)據(jù)點i的局部密度pi和相對距離δi。令待聚類的數(shù)據(jù)集S={x1，x2，…，xn}，IS={1，2，…，n}為相應(yīng)的指標(biāo)集。

定義1局部密度pi（Cut-off kernel 和Gaussian kernel 兩種計算方式）。

Cut-off kernel：

其中函數(shù)：

式（1）中：i和j分別為第i個數(shù)據(jù)點、第j個數(shù)據(jù)點；rij=，rij為數(shù)據(jù)點xi和xj之間的歐氏距離；參數(shù)rc為截斷距離，其作為密度峰值聚類算法的唯一參數(shù)，實際起著距離閾值的作用。

Gaussian kernel：

式（1）為數(shù)據(jù)集規(guī)模較大時數(shù)據(jù)i的局部密度計算方式；當(dāng)數(shù)據(jù)集的規(guī)模較小，為減小截斷距離的選擇對算法的影響，DPC 算法采用高斯核函數(shù)來估計數(shù)據(jù)i的局部密度，如式（3）所示。

定義2相對距離δi：

計算pi和δi之后，密度峰值聚類算法通過構(gòu)造決策圖選擇pi和δi都較大的數(shù)據(jù)點作為聚類中心。

圖1（a）展示了原始數(shù)據(jù)點集的分布。圖1（b）為該數(shù)據(jù)集的決策圖，其包含每個數(shù)據(jù)點的局部密度pi和相對距離δi。從決策圖中可以容易發(fā)現(xiàn)，灰色圓形點和菱形點標(biāo)記的數(shù)據(jù)點為聚類中心點，因為這兩個點同時具有較大的pi值和δi值。

圖1 原始數(shù)據(jù)點分布和決策圖的實例Fig.1 Examples of original data point distribution and decision graph

在選定聚類中心后，密度峰值聚類算法按照密度從大到小的順序?qū)⑹Ｓ鄶?shù)據(jù)點依次歸入比它密度大且與其距離最近的數(shù)據(jù)點的類簇，僅一步就可以高效地完成數(shù)據(jù)點的分配。

2 自動確定聚類中心的比較密度峰值聚類算法

2.1 比較量

依據(jù)密度峰值聚類算法第二個假設(shè)的描述，即聚類中心與比其密度高的數(shù)據(jù)點的距離相對較遠可知，聚類中心點的δi值一定相對較大。原算法對于“相對較大”的概念只是讓用戶在決策圖的可視化分析中進行比較，然而決策圖中不是所有的聚類中心點都能體現(xiàn)出來，并且有時聚類中心點與非聚類中心點在決策圖中顯示不夠清晰。借鑒文獻［23］思想，本文采用比較量d來替代δ，實現(xiàn)定量比較的方式來顯示相對距離，從而凸顯聚類中心。

本文用τi作為數(shù)據(jù)點i與其密度更低點的最短距離，具體定義如下：

式（5）中當(dāng)數(shù)據(jù)點i的局部密度為最小值時，它的τi值為δi值。τi值的定義作為與δi值正好相反的一個距離屬性，為了描述其差值，用d來表示，其定義如下：

di為δi與τi的比較數(shù)量，有助于識別潛在的聚類中心。如圖2（b）所示，當(dāng)di值較大時，表明該數(shù)據(jù)點距離低密度區(qū)域的數(shù)據(jù)點很近而距離更高密度的數(shù)據(jù)點更遠，符合聚類中心的選擇特征。當(dāng)di的值在零附近，表明該數(shù)據(jù)點既有密度更大的數(shù)據(jù)點也有密度更小的點，說明該數(shù)據(jù)點處于某個類簇中。若di遠小于零，該數(shù)據(jù)點距離密度高的數(shù)據(jù)點較近而距離密度低的點較遠，這類點為類簇邊緣點。

圖2 決策圖對比Fig.2 Decision diagram comparison

2.2 基于統(tǒng)計分析的聚類中心點自動識別

DPC 算法在選取聚類中心時設(shè)計了一種啟發(fā)式方法，在決策圖上手動選擇同時具備高密度和高距離的數(shù)據(jù)點作為聚類中心。這種方法雖然可以人為地在決策圖上可視化地識別聚類中心，但只是在數(shù)據(jù)集分布清晰的條件下能有較好的識別效果，當(dāng)處理大規(guī)模數(shù)據(jù)并且具有復(fù)雜的決策圖時，人為的方式就難以保證聚類結(jié)果較高的準(zhǔn)確性。針對該問題，借鑒文獻［24］思想，本文采用特定統(tǒng)計量來實現(xiàn)聚類中心點的自動識別。

根據(jù)數(shù)據(jù)點在決策圖中的分布特征，用高斯核函數(shù)來估計特定密度值pi處的概率密度ρy(pi，y)，其定義如下：

其中：y表示特定密度值pi處可能的距離值。數(shù)值n為數(shù)據(jù)點的總數(shù)，參數(shù)a、b為核寬度值。分母是一個歸一化的因子，可以確保(pi，y)=1。核寬度a和b作為概率密度估計重要的參數(shù)，通過pi和di的標(biāo)準(zhǔn)差估計得到，rp和rd設(shè)置為0.5，具體定義如下：

根據(jù)式（8）得到的概率密度估計，然后在特定密度值pi對最小距離值y的期望值和方差值進行估計，其定義如下：

通過化簡可以得到：

式（11）、（12）中，n為數(shù)據(jù)點總數(shù)，pi表示數(shù)據(jù)點i的局部密度，參數(shù)a、b表示核寬度值，dj表示比較量。

完成在特定密度值pi處最小距離y的期望值和方差值的計算后，利用以下公式進行聚類中心的自動化識別：

根據(jù)式（13）可知：μy(pi)表示y的期望值，σy(pi)表示y的標(biāo)準(zhǔn)差。如果數(shù)據(jù)點的最小距離值di＞THd(pi)，它將會自動識別為聚類中心點。為了便于了解自動化識別聚類中心算法，圖3 進行了直觀描述，其中黑色圓形點為聚類中心，菱形為期望值，正方形為標(biāo)準(zhǔn)差。

圖3 用于聚類中心點自動識別的統(tǒng)計量Fig.3 Statistics for automatic recognition of clustering center points

2.3 算法的主要步驟描述

ACPC算法的具體實現(xiàn)步驟如下：

2.4 時間復(fù)雜度分析

ACPC 算法的時間復(fù)雜度主要有4部分［25］構(gòu)成：1）計算相似度矩陣，其時間復(fù)雜度為O(n2)；2）求每個數(shù)據(jù)點的比較量d，其中距離δ的時間復(fù)雜度為O(n2)，對比量τ的時間復(fù)雜度為O(n)，比較量d時間復(fù)雜度為O(n2)，所以計算每個數(shù)據(jù)點的比較量d的整體時間復(fù)雜度為O(n2)；3）對特定密度值pi處最小距離值y的期望值和方差值估計，時間復(fù)雜度為O(n2)；4）分配樣本的時間復(fù)雜度與DPC 中相應(yīng)操作的時間復(fù)雜度相同，為O(n2)。因此，ACPC算法的整體時間復(fù)雜度為O(n2)。

3 實驗仿真及分析

選用人工數(shù)據(jù)集和UCI（University of California lrvine）［26］公開數(shù)據(jù)進行實驗驗證，數(shù)據(jù)集的詳細信息如表1 所示，并將其與DPC、基于KL 散度的密度峰值聚類算法（Density Peaks Clustering based on Kullback-Leibler divergence，KLDPC）、改進的快速搜索與發(fā)現(xiàn)密度峰值聚類（Clustering by Fast Search and Find of Density Peaks，CFSFDP）、APC（density-based Clustering using Automatic density Peaks detection）、自動確定聚類中心的快速搜索和發(fā)現(xiàn)密度峰值的聚類算法（AUTOmatic determination of clustering center for CFSFDP，AUTO-CFSFDP）算法［27］進行比較，各算法在不同數(shù)據(jù)集上的參數(shù)取值如表2 所示。實驗開發(fā)環(huán)境Matlab2014a，硬件條件為：Intel Core i5-3470 CPU，主頻3.20 GHz，內(nèi)存4.00 GB。

表1 數(shù)據(jù)集信息Tab.1 Information of datasets

3.1 人工數(shù)據(jù)集的實驗結(jié)果分析

本文采用4 個人工數(shù)據(jù)集驗證ACPC 的聚類效果，圖4 為實驗數(shù)據(jù)的二維圖形展示，圖5～8 為各算法分別對DS1～DS4的聚類結(jié)果。

圖5 為DS1 在五種算法中得到的聚類結(jié)果。DPC 算法、APC算法、ACPC算法都可以準(zhǔn)確確定聚類個數(shù)且聚類效果都很好。KLDPC 算法、改進的CFSFDP 算法、AUTO-CFSFDP 算法不能正確聚類，錯誤地將多個球形數(shù)據(jù)聚為一個類簇。

圖4 實驗數(shù)據(jù)的二維圖形展示Fig.4 2D shapes of experimental data

圖6 為DS2 在五種算法中得到的聚類結(jié)果。DPC 算法、KLDPC 算法、APC 算法、AUTO-CFSFDP 算法、ACPC 算法對數(shù)據(jù)集都有很好的聚類效果。改進的CFSFDP 算法對環(huán)形數(shù)據(jù)集聚類結(jié)果不理想，錯誤地將兩個類簇的數(shù)據(jù)點聚類成一類。

表2 各算法在11個數(shù)據(jù)集上的參數(shù)取值Tab.2 Parameters of different algorithms on 11 datasets

圖7 為DS3 在五種算法中得到的聚類結(jié)果。DPC 算法、改進的CFSFDP 算法、ACPC 算法能準(zhǔn)確確定聚類個數(shù)，但在兩個離得近的球形數(shù)據(jù)上沒能正確分配。KLDPC 算法得不到數(shù)據(jù)集聚類中心點的準(zhǔn)確個數(shù)，將五個類簇劃分為兩個類簇。APC 算法錯誤地將一個簇類分成多個類簇。AUTOCFSFDP算法不能正確確定聚類個數(shù)，錯誤地將數(shù)據(jù)密集的類簇識別為多個類簇。

圖8 為DS4 在五種算法中得到的聚類結(jié)果。ACPC 算法對DS2 簡單流形數(shù)據(jù)能很好聚類，對于DS4 數(shù)據(jù)錯誤地將一類聚成兩類。DPC 算法、KLDPC 算法、改進的CFSFDP 算法、APC算法、AUTO-CFSFDP算法在聚類效果上很不理想。

3.2 UCI數(shù)據(jù)集的實驗結(jié)果分析

為了進一步驗證ACPC 算法的性能，采用準(zhǔn)確率（Accuracy，ACC）與標(biāo)準(zhǔn)互信息（Normalized Mutual Information，NMI）兩類聚類指標(biāo)對本文算法和現(xiàn)有算法進行了性能對比，加粗的數(shù)據(jù)為數(shù)據(jù)的最優(yōu)聚類結(jié)果。表3 為聚類結(jié)果的性能對比。

已知真實類劃分U={U1，U2，…，UT}，V={V1，V2，…，VT}為聚類結(jié)果。

定義3準(zhǔn)確率（ACC）：

其中，ncorrect代表分類正確的記錄個數(shù)，ntatol代表全部測試數(shù)據(jù)的個數(shù)。當(dāng)預(yù)測結(jié)果與真實結(jié)果完全相符時準(zhǔn)確率為1，兩者越不相符準(zhǔn)確率越低。

定義4標(biāo)準(zhǔn)互信息（NMI）：

其中：H(U)和H(V)是U和V兩種分布的熵，MI(U，V)是U與V之間的互信息，NMI 取值范圍為［0，1］，值越大意味著聚類結(jié)果與真實情況越吻合。每一部分的計算見文獻［28］。

由表3 可知，ACPC 算法在準(zhǔn)確率上，除了在Sonar 數(shù)據(jù)集上聚類效果差一些，在其他數(shù)據(jù)集上都達到了最優(yōu)。在標(biāo)準(zhǔn)互信息上，ACPC在Iris和Wine數(shù)據(jù)集上要優(yōu)于其他算法，在其他數(shù)據(jù)集上略差一點。綜合這兩種聚類指標(biāo)來看，ACPC算法優(yōu)于DPC、KLDPC、改進的CFSFDP、APC、AUTO-CFSFDP算法。

圖5 五種算法在DS1數(shù)據(jù)集上的聚類結(jié)果Fig.5 Clustering results of five algorithms on DS1 dataset

圖6 五種算法在DS2數(shù)據(jù)集上的聚類結(jié)果Fig.6 Clustering results of five algorithms on DS2 dataset

4 結(jié)語

針對DPC 需要手動選取聚類中心，以及在處理密度變化較大的數(shù)據(jù)集時生成的決策圖聚類中心和非聚類中心不夠清晰的問題，實現(xiàn)了一種無須人工交互選擇聚類中心的比較密度峰值聚類算法。該算法通過統(tǒng)計分析的二維區(qū)間估計方法實現(xiàn)對聚類中心的自動選取，同時采用距離的比較量di來代替原算法的δi，使?jié)撛诘木垲愔行脑跊Q策圖中更加突出。通過對人工和UCI 數(shù)據(jù)集的實驗驗證，并與其他算法的對比分析，本文算法不僅能夠自動選取聚類中心，實現(xiàn)了聚類過程的自動化，并且具有更好的準(zhǔn)確性以及適用性。如何自動地確定最佳的截斷距離以及將DPC 算法應(yīng)用于實際問題將是下一步的研究重點。

圖7 五種算法在DS3數(shù)據(jù)集上的聚類結(jié)果Fig.7 Clustering results of five algorithms on DS3 dataset

圖8 五種算法在DS4數(shù)據(jù)集上的聚類結(jié)果Fig.8 Clustering results of five algorithms on DS4 dataset

表3 聚類結(jié)果對比Tab.3 Comparisin of clustering results