分布的自動閾值密度峰值聚類算法

彭啟慧，宣士斌，高 卿

廣西民族大學(xué) 信息科學(xué)與工程學(xué)院，南寧530006

聚類分析[1]是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)中的一個基礎(chǔ)研究內(nèi)容。在過去的幾十年中，研究人員已提出多種聚類算法。典型算法包括基于分區(qū)的K-means[2]和Kmedoids[3]、基于層次的CURE[4]和BIRCH[5]、基于密度的DBSCAN[6]和OPTICS[7]和基于網(wǎng)格的WaveCluster[8]和STING[9]，以及基于模型的統(tǒng)計聚類[10]和基于圖論的譜聚類[11]。經(jīng)典的聚類算法K-means是通過指定聚類中心，然后通過迭代的方式更新聚類中心，在具有凸球形結(jié)構(gòu)的數(shù)據(jù)集上實現(xiàn)了良好的聚類結(jié)果，但由于每個點都被指派到距離其最近的聚類中心，所以導(dǎo)致它不能檢測非球面類別的數(shù)據(jù)分布。雖然有DBSCAN可以對任意形狀的分布進(jìn)行聚類，并且具有很強(qiáng)的抗噪能力，但對于變密度簇和高維數(shù)據(jù)的聚類效果較差[12-14]，此外，選擇半徑和閾值也是DBSCAN的難題。Rodriguez和Laio[15]提出的DPC（Clustering by fast search and find of Density Peaks）根據(jù)局部密度和密度最近鄰可以得到?jīng)Q策圖，并根據(jù)決策圖求得聚類中心。這種算法不僅高效，而且所依賴的參數(shù)只有截止距離這一個。雖然DPC算法在某些方面有著明顯的優(yōu)勢，但它仍然存在如下的一些情況：

首先，局部密度和距離測量的定義簡單[16-17]，因此，當(dāng)處理具有多尺度，交叉纏繞，各種密度或高維度的復(fù)雜數(shù)據(jù)集時，DPC算法的聚類結(jié)果可能較差[18-21]。其次，依據(jù)決策圖人工選擇類中心點，帶有較強(qiáng)的主觀性[22-23]。第三，由于在大多數(shù)情況下每個屬性的范圍都是未知的，所以通常很難確定截斷距離[24-25]。針對DPC存在的問題，研究人員提出了很多DPC的改進(jìn)和優(yōu)化方法。Xu等[26]提出用網(wǎng)格距離代替了歐式距離用于解決DPC對距離的測量定義過于簡單，且需要計算所有數(shù)據(jù)點之間的距離這一計算量大的缺點。針對無法有效地對具有任意形狀或多流形結(jié)構(gòu)的數(shù)據(jù)進(jìn)行分組，Du等[27]提出了使用測地距離（DPC-GD）的密度峰聚類，它將測地距離的概念引入到原始DPC方法中。Liu等[28]針對高維度復(fù)雜數(shù)據(jù)集時，DPC聚類時會掩蓋低密度的類別，導(dǎo)致效果不好，提出了一種基于共享最近鄰居的密度峰值聚類。類中心的手動選擇是CFSFDP在智能數(shù)據(jù)分析中的一大局限。Bie等[29]提出了一種有效地選擇聚類中心的模糊CFSFDP方法。它是使用模糊規(guī)則來自動選擇類中心，避免人工選擇。Wang等[30]提出了一種利用原始數(shù)據(jù)集中數(shù)據(jù)場的潛在熵自動提取閾值最優(yōu)值的新方法。

由于DPC方法中的局部密度定義簡單，僅是統(tǒng)計了截斷距離內(nèi)點的數(shù)量，而沒有考慮截斷距離內(nèi)數(shù)據(jù)點的具體分布情況，只要是數(shù)據(jù)點的數(shù)量相同，就簡單地認(rèn)定局部密度大小相同，從而導(dǎo)致在某些情況下聚類中心的錯判，影響聚類效果。為此，提出了基于分布的自動閾值密度峰值的聚類方法，同時考慮點的數(shù)量和分布情況來定義局部密度，自適應(yīng)確定樣本數(shù)目權(quán)重因子占有的比例。并在預(yù)處理階段，引入了密度分布函數(shù)的概念，然后用最大類間差法確定閾值找出聚類中心，最后指派剩余點完成聚類。

1 密度峰值聚類算法的介紹

密度峰值聚類算法DPC是一種基于密度的聚類算法，算法思想是：（1）類中心點擁有比其周圍鄰近點大的密度值；（2）類中心點到其他比其密度值大的數(shù)據(jù)點之間的距離較大。當(dāng)類中心點確定以后，每一個數(shù)據(jù)點分配給比其密度值大且距離其最近的數(shù)據(jù)點相同的標(biāo)記按密度值由大到小依次更新所有數(shù)據(jù)點的標(biāo)記直到聚類完成。

其中，χ(?)是密度核函數(shù)；dij是任意兩點之間的距離；dc是距離閾值或者稱為截斷距離，用于搜索范圍的限定，參數(shù)dc需要人為提前設(shè)定。高斯核密度函數(shù)是另一種常用的密度估計方法[31]，被廣泛地應(yīng)用在基于密度的聚類算法分析中，可定義為：

exp(·)稱為核函數(shù)，dij是數(shù)據(jù)點i,j之間的距離，dc為截斷距離。公式（1）可導(dǎo)致不同的數(shù)據(jù)點具有相同的局部密度，不利于后續(xù)的排序工作，因此本文采用式（2）進(jìn)行局部密度的計算。

數(shù)據(jù)點i所對應(yīng)的最小距離δi是密度值比數(shù)據(jù)點i大，且距離點i最近的數(shù)據(jù)點與點j的距離：

正如定義的那樣，δi值通常會大于數(shù)據(jù)點i周圍其他鄰居點的最小距離值。如果數(shù)據(jù)點i是局部或者全局密度最大點，這種現(xiàn)象會特別明顯。

算法1DPC算法

步驟1計算任意兩點之間的距離dij。

步驟2計算每一點的局部密度ρi，將密度點按由高到低排序。

步驟3根據(jù)式（3）求得密度距離δi并存儲與之對應(yīng)的標(biāo)號。

步驟4根據(jù)ρi及δi的關(guān)系決策圖，選取類中心點。

步驟5根據(jù)類中心點、數(shù)據(jù)對象標(biāo)號及密度邊界閾值，將剩余點分到各個類或邊界域。

為了選取合適的類中心點，通過借助決策圖人工選取類中心點。決策圖有兩個重要的參數(shù)：每一個數(shù)據(jù)點i的局部密度ρi和到比其密度大距離其最近的數(shù)據(jù)點的距離δi。通過數(shù)據(jù)點密度值ρi和最小距離δi的計算，便可以得到相應(yīng)數(shù)據(jù)集的決策圖如圖1。

2 基于分布的自動閾值密度峰值聚類方法

DPC算法在計算局部密度時，只考慮了截斷距離內(nèi)的點個數(shù)作為局部密度，沒有考慮截斷距離內(nèi)點的分布情況，導(dǎo)致局部密度的真實值有偏差，這不利于類中心選擇的最終結(jié)果的準(zhǔn)確性。除此之外，DPC算法在選擇聚類中心時需要人工輔助選擇，選擇方式在決策圖中，利用矩形框選擇與其他的點差異最大的一組點為聚類中心，使得算法具有一定的主觀性。本章針對DPC算法上述兩個不足點提出了優(yōu)化，使得算法對類中心的劃分更為合理，并且可以自動選擇聚類中心。

圖1 DPC算法的決策圖

2.1 基本思路

相比于DBSCAN及其他聚類算法，DPC能夠有效發(fā)現(xiàn)不同形狀、不同密度的簇，并且不用事先指定簇的數(shù)量，也沒有很多的參數(shù)。然而，由于在定義局部密度時只是簡單統(tǒng)計半徑為dc的鄰域內(nèi)數(shù)據(jù)點的個數(shù)，而沒有考慮鄰域內(nèi)數(shù)據(jù)點的具體分布情況，在某些情況下可能導(dǎo)致錯判為密度峰值，使得聚類結(jié)果出現(xiàn)錯誤。如圖2所示，以紅色小圓點為圓心，半徑為dc大小相同的圓圈內(nèi)，圈內(nèi)的星星點的個數(shù)都是12，右上角的圓圈內(nèi)星星點的個數(shù)分布均勻，左下角的圓圈內(nèi)星星點全部集中在小部分區(qū)域，如果局部密度都為12，顯然是不合理的。

圖2 樣本點分布對比圖

因此，本文通過分析半徑為dc鄰域內(nèi)數(shù)據(jù)點的數(shù)量以及分布情況，來定義局部密度?；舅枷耄菏紫雀鶕?jù)公式（1）計算每個點半徑為dc鄰域內(nèi)點的個數(shù)ni；然后通過反余弦函數(shù)得到鄰域內(nèi)所有數(shù)據(jù)點與x軸正向的夾角，進(jìn)而得到該鄰域數(shù)據(jù)點的分布情況。將該鄰域分成ni個扇形區(qū)域，fn是鄰域內(nèi)所有數(shù)據(jù)點占據(jù)了鄰域內(nèi)的扇形區(qū)域個數(shù)。例如ni=12，則把鄰域分成了12個區(qū)域，如圖3所示，如果這12個點占據(jù)了9個扇形區(qū)域，則局部分布密度是9；如果這12個點只占據(jù)了2個扇形區(qū)域，則局部分布密度為2。所以當(dāng)鄰域內(nèi)點的個數(shù)相同時，這些點所占的扇形區(qū)域越多，鄰域內(nèi)數(shù)據(jù)點分布越均勻。

為此，定義基于分布的局部密度ρ′：

圖3 基于分布的密度對比圖

其中，ni根據(jù)公式（1）計算得到半徑為dc的鄰域內(nèi)數(shù)據(jù)點的個數(shù)，ρ′是基于分布的局部密度，fn是這些點分配到ni區(qū)域中所占據(jù)的扇形區(qū)域。

2.2 聚類中心自動選擇策略

此外，DPC中將那些具有較大密度距離δi且同時具有較大局部密度ρi的點定義為聚類中心。所以綜合考慮δi值和ρi值，而這兩類值可能處于不同的數(shù)量級。因此，對兩者做一次歸一化[32]再相乘得到密度距離γi。原始數(shù)據(jù)經(jīng)過歸一化處理后，各指標(biāo)處于同一數(shù)量級。

如果數(shù)據(jù)存在異常值和較多噪音，數(shù)據(jù)歸一化會使得最優(yōu)解的尋優(yōu)過程變得平緩，更容易正確地收斂到最優(yōu)解?？梢蚤g接避免異常值和極端值的影響，故而減少了噪音點[33-35]。

由于對于兩者在選取聚類中心時需要人工輔助，使得聚類過程中帶有一定的隨意性和主觀性，不利于算法的實現(xiàn)和應(yīng)用。為此，提出用最大類間差法（Otsu）求出閾值，確定聚類中心，最后指派剩余點到各個簇。其基本思想是：通過統(tǒng)計整個數(shù)據(jù)集的密度距離γ值直方圖特性來實現(xiàn)全局閾值T的自動選取。首先，按密度距離把數(shù)據(jù)集分成2個部分，一部分密度距離較?。礉撛诘姆蔷垲愔行模?，另一部分密度距離較大（即潛在的聚類中心），使得兩個部分之間的值差異最大，每個部分之間的差異最小；其次，通過計算方差尋找一個合適的γ值來進(jìn)行劃分。

潛在的非聚類中心點數(shù)占整個數(shù)據(jù)集的比例ω0：

潛在聚類中心點數(shù)占整個數(shù)據(jù)集的比例ω1：

潛在的非聚類中心平均密度距離值μ0：

潛在的聚類中心平均密度距離值μ1：

數(shù)據(jù)集的總平均密度距離μ：

類間方差g：

將式（11）代入式（12），得到等價類間方差公式：

算法2給出了類中心選取策略的具體步驟。

算法2自動選擇聚類中心算法

步驟1先計算整個數(shù)據(jù)集的密度距離γ值的直方圖，即將所有的點按照0～maxγ共10個bin，統(tǒng)計落在每個bin的γ量。

步驟2歸一化直方圖，即將每個bin中點數(shù)量除以總數(shù)據(jù)集點的數(shù)量。

步驟3初始化分類閾值T為0。

步驟4統(tǒng)計密度距離在0～T的個數(shù)所占整個數(shù)據(jù)集的比例ω0，并根據(jù)公式（8）非潛在聚類中心的平均γ值μ0；統(tǒng)計T～maxγ密度距離點所占整個數(shù)據(jù)集的比例ω1，由公式（9）計算潛在聚類中心平均γ值μ1；并根據(jù)公式（10）統(tǒng)計整個數(shù)據(jù)集的平均γ值μ。

步驟5根據(jù)公式（11）計算潛在非聚類中心和潛在聚類中心的方差。

步驟6T=T+1轉(zhuǎn)到步驟4，直到T為maxγ時結(jié)束迭代。

步驟7將最大g相應(yīng)的T值作為數(shù)據(jù)集的全局閾值。

圖4 是來自文獻(xiàn)[26]的Aggregation數(shù)據(jù)集，用DPC決策圖的方法和使用Otsu算法所得到的聚類中心對比圖。綠色的方框代表決策圖方法選擇出來的聚類中心，紅色的圓圈代表Otsu方法得到的聚類中心?？梢悦黠@地看到，圖4中的1、2、5、6、7區(qū)域的類中心幾乎沒有差別，但在3區(qū)域，Otsu方法得到的以紅色圈點為類中心的藍(lán)色圓內(nèi)包含點的個數(shù)即密度是13，以綠色圈點為類中心時，所包含的點的個數(shù)是10；在4區(qū)域紅色圈點為類中心時，圓內(nèi)所包含的點的個數(shù)即密度是9，綠色圈點為類中心時，所包含的點是6，且有2個點是在圓圈的邊界線上，將會形成光暈點或噪音點。故以紅色圈點為類中心顯然更合理。

圖4 Aggeragation數(shù)據(jù)集聚類中心對比圖

最后，提出基于分布的局部密度和最大類間差法（Otsu）自動選擇類中心的策略如算法3：

算法3基于分布的自動閾值密度峰值聚類方法

步驟1計算任意兩點之間的距離，根據(jù)類數(shù)目確定dc。

步驟2根據(jù)反三角余弦函數(shù)acosθ計算各數(shù)據(jù)點的密度值ρ′i。

步驟3計算各數(shù)據(jù)點δi。

步驟4計算各數(shù)據(jù)點歸一化的ρ″i與δ′i的乘積γi。

步驟5利用直方圖對數(shù)據(jù)點的γi值進(jìn)行分類，找出潛在的聚類中心。

步驟6Otsu算法找到γ的閾值，確定聚類中心的個數(shù)。

步驟7根據(jù)簇中心點，將剩余點分到各個簇或邊界域。

3 仿真實驗

為驗證算法的有效性，本文使用5類數(shù)據(jù)集，分別采用DBSCAN、DPC、ADPC-KNN[36]以及改進(jìn)后的密度峰值聚類4種算法，從聚類結(jié)果、正確率兩個方面對算法的性能進(jìn)行了評估及分析，實驗環(huán)境及參數(shù)設(shè)置如表1所列。

表1 數(shù)據(jù)集屬性

3.1 實驗分析

（1）以788點的Aggregation數(shù)據(jù)集為例，分別采用DPC算法和改進(jìn)的搜索密度峰值的聚類中心算法對聚類誤差平方和進(jìn)行對比。Aggregation數(shù)據(jù)集正確分類是7類。圖5（a）是Eps=1.2，MinPts=3.5的DBSCAN算法聚類的結(jié)果，雖然沒有噪音點，但類中心只有4個，明顯不正確；圖5（b）是DPC決策圖法得到的聚類結(jié)果，聚類結(jié)果是7個類簇，但很明顯聚類效果不好，有很多的噪音點存在；圖5（c）是ADPC-KNN得到的聚類結(jié)果，是6個類簇，不正確；圖5（d）是dc=2改進(jìn)后的聚類結(jié)果圖，得到的類別正確，沒有光暈點和噪聲點，聚類效果很好。

圖5 Aggregation對比圖

（2）Flame數(shù)據(jù)集做的實驗，圖6（a）是Eps=1.1，MinPts=3的DBSCAN得到的結(jié)果；圖6（b）是DPC決策圖，手動選擇的類簇是2，類別正確，但噪音點非常多，幾乎占據(jù)了一半；圖6（c）是ADPC-KNN，噪音點少了很多，但得到的聚類結(jié)果是3類，不正確；圖6（d）是改進(jìn)后自動選擇聚類中心，得到類簇是2，噪音點只有右下角最邊緣的2個點沒有歸類。

圖6 Flame對比圖

（3）R15數(shù)據(jù)集做的實驗，圖7（a）是Eps=0.11，MinPts=1.1的DBSCAN得到的聚類結(jié)果圖，圖7（b）DPC決策圖的類簇是15，類別正確，但噪音點多，對比ADPC-KNN中圖7（c），左下角的藍(lán)色區(qū)域，DPC明顯沒有噪音點，但圖7（c）和圖7（d）比較而言，改進(jìn)后的圖7（d）結(jié)果，中間藍(lán)綠區(qū)域趨于沒有噪音點，整體上噪聲點也都明顯下降，幾乎沒有。

（4）Spiral數(shù)據(jù)集實驗，圖8（a）是Eps=1，MinPts=3的DBSCAN得到的結(jié)果，可以看得到結(jié)果圖有5個顏色的點，基本上不能形成明顯的類簇；圖8（b）是DPC聚類得到的結(jié)果，雖然可以得到3個類別，但每個螺旋的最后部分都是無法分類的；圖8（c）是ADPC-KNN，得到的聚類結(jié)果是不正確的；圖8（d）是改進(jìn)后得到的聚類結(jié)果圖，可以得到3個類簇，并且沒有噪音點，全部歸類。

（5）Two-moon數(shù)據(jù)集實驗，圖9（a）是Eps=1，MinPts=1.1的DBSCAN得到的結(jié)果，可以看到結(jié)果圖有2個顏色的點，雖然可以形成類別，但有太多的噪音點；圖9（b）是DPC聚類得到的結(jié)果，把其中的一個類分成了兩類，明顯是不合理的；圖9（c）是ADPC-KNN得到的聚類結(jié)果，同理把一個類分成了兩個類，不合理；圖9（d）是改進(jìn)后得到的聚類結(jié)果圖，可以得到2個類簇，并且沒有噪音點，全部歸類。

圖7 R15對比圖

圖8 Spiral對比圖

圖9 Two-moon對比圖

3.2 準(zhǔn)確度分析

為考察傳統(tǒng)的DBSCAN算法、DPC算法，以及改進(jìn)后的算法的聚類準(zhǔn)確率，本文采用了5類數(shù)據(jù)集測試，進(jìn)行了100次蒙特卡羅實驗并統(tǒng)計了聚類準(zhǔn)確率及F-measure實驗結(jié)果如圖10、11所示。

圖10 算法的準(zhǔn)確率對比圖

由圖10、圖11可看出，DPC算法，ADPC-KNN及其本文改進(jìn)后的算法在準(zhǔn)確度、F-measure方面都明顯高于DBSCAN算法，說明了密度峰值聚類算法的優(yōu)越性。DPC算法依據(jù)局部密度和密度最近鄰?fù)瑫r大時作為類簇中心，需要人為選擇類簇，帶有很大的主觀性。DBSCAN算法需要通過判斷鄰域半徑Eps核心點的閾值、MinPts來劃分類簇，由于使用了統(tǒng)一的鄰域半徑，因此當(dāng)數(shù)據(jù)密度和類簇間距離分布不均勻時，容易導(dǎo)致簇聚類準(zhǔn)確度降低。標(biāo)準(zhǔn)的DPC聚類算法的準(zhǔn)確度和F-measure與DBSCAN算法差不多，但都略低于改進(jìn)后的DPC算法，這是由于，在局部密度及密度峰值時綜合考慮了鄰域內(nèi)樣本點的具體分布，并且改進(jìn)后的算法能夠自動選取合適的簇中心點，降低了人工輔助決策圖的主觀性導(dǎo)致的平均誤差。

4 結(jié)束語

本文提出一種基于分布的自動閾值密度峰值聚類算法。首先，該算法通過由鄰域內(nèi)的數(shù)據(jù)點個數(shù)以及鄰域內(nèi)數(shù)據(jù)點的具體分布情況來計算數(shù)據(jù)點的局部密度，然后通過最大類間差法自動聚類。通過實驗，分布的自動閾值密度峰值聚類算法在對復(fù)雜密度變化大的數(shù)據(jù)的處理上具有相當(dāng)大的優(yōu)越性，在局部密度及密度峰值綜合考慮了鄰域內(nèi)樣本點的具體分布，并且改進(jìn)后的算法能夠自動選取合適的簇中心點，降低了人工輔助決策圖的主觀性導(dǎo)致的平均誤差，比DPC、DBSCAN、ADPCKNN算法更有效。

圖11 算法的F-measure對比