吳 昊 周建濤 祁瑞東

（內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院 呼和浩特 010021）

1 引言

聚類分析是數(shù)據(jù)挖掘［1］領(lǐng)域中的一種數(shù)據(jù)分析方法，它根據(jù)數(shù)據(jù)特征，利用相似性度量規(guī)則，將未被預(yù)先標(biāo)記的數(shù)據(jù)對(duì)象相似的數(shù)據(jù)集歸到同一組中?，F(xiàn)在，聚類方法已經(jīng)成為一個(gè)重要的研究領(lǐng)域，在互聯(lián)網(wǎng)［2］、地質(zhì)［3］和材料學(xué)［4］等多個(gè)領(lǐng)域都有廣泛的應(yīng)用。為了解決經(jīng)典聚類算法［5~7］存在參數(shù)設(shè)置復(fù)雜、需要預(yù)先輸入分類數(shù)、無法識(shí)別任意形狀簇等局限性，2014年Alex與Alessandro在《Science》提出密度峰值聚類算法（CFSFDP）［8］，該算法不需要設(shè)置初始簇?cái)?shù)量，只需設(shè)置一個(gè)參數(shù)且聚類結(jié)果對(duì)該參數(shù)的選擇并不敏感，聚類過程中可以自發(fā)地發(fā)掘數(shù)據(jù)集內(nèi)部結(jié)構(gòu)，并具有非常好的魯棒性。但密度峰值聚類算法還存在一個(gè)問題，初始簇中心的確定需要人工手動(dòng)選擇。

為了彌補(bǔ)密度峰值聚類存在的缺陷，本文基于最小二乘法結(jié)合決策圖選點(diǎn)提出一種自動(dòng)選擇聚類中心方法，并結(jié)合此方法提出自動(dòng)聚類算法，實(shí)驗(yàn)結(jié)果表明，該算法可有效地自動(dòng)識(shí)別初始簇中心，并有較好的聚類效果。

2 研究現(xiàn)狀與基本知識(shí)

2.1 初始簇中心選擇

初始簇中心選擇的方法大致分為三類，結(jié)合其他聚類方法結(jié)果兩階段聚類、計(jì)算閾值對(duì)決策點(diǎn)劃分以及尋找區(qū)域?qū)Q策圖劃分。結(jié)合其他聚類方法兩階段聚類的方法通常要先運(yùn)行可確定簇?cái)?shù)的聚類算法，Sun［9］等使用min-max聚類結(jié)果指導(dǎo)密度峰值聚類初始簇的選擇，在一定程度上可以找到合適的簇，但時(shí)間成本相當(dāng)高，Zhou［10］等則使用Canopy進(jìn)行初始簇識(shí)別也存在以上問題。閾值計(jì)算方法與b-ayes信息準(zhǔn)則相類似，迭代計(jì)算閾值進(jìn)行參考簇中心的選擇，2019年Sun和Jiang［11］提出使用高斯分布異常點(diǎn)檢測(cè)思想迭代概率閾值對(duì)初始簇進(jìn)行劃分，雖可以較有效地確定簇?cái)?shù)，但在計(jì)算過程中引入了新的參數(shù)需要選擇，這淡化了密度峰值聚類算法的優(yōu)勢(shì)。尋找區(qū)域的方法參照S.Salavador［12］所述Gap檢驗(yàn)，通過結(jié)合決策圖的圖像特征計(jì)算來找到下降劇烈和平緩之間的分界區(qū)域，如2017年Wang［13］等使用點(diǎn)組角度余弦最大值來界定區(qū)域。尋找區(qū)域的方法往往需要設(shè)置少量參數(shù)，更適用于對(duì)密度峰值聚類算法初始簇的選擇，但現(xiàn)有的區(qū)域?qū)ふ曳椒ㄓ?jì)算量較大。本文提出使用擬合直線的方法且對(duì)該方法進(jìn)行優(yōu)化，并結(jié)合新的選點(diǎn)策略提出自動(dòng)聚類算法，下一小節(jié)介紹密度峰值聚類算法的基礎(chǔ)知識(shí)。

2.2 密度峰值聚類算法

本節(jié)介紹密度峰值聚類算法中的一些定義、算法思想和具體算法過程，并分析算法過程中存在的問題。

算法思想基于一個(gè)觀察：每一個(gè)簇中的密度大的區(qū)域總被密度小的區(qū)域包圍。算法的聚類中心滿足局部密度較大且離比它局部密度大的點(diǎn)較遠(yuǎn)。

密度峰值聚類算法首先需要選擇初始聚類中心，在簇中心的選擇過程中，設(shè)數(shù)據(jù)點(diǎn)i，需要計(jì)算局部密度ρi和到密度比自身高的點(diǎn)的距離δi，數(shù)據(jù)點(diǎn)i的局部密度的計(jì)算公式為

其中，dij為點(diǎn)i到點(diǎn)j的距離，dc為截?cái)嗑嚯x，χ(x)在當(dāng)x<0時(shí)χ(x)=1其他情況χ(x)=0，局部密度ρi也就等于點(diǎn)i在dc范圍內(nèi)的點(diǎn)的數(shù)目。

局部密度較大且δi較大的點(diǎn)將被選為簇中心，δi的計(jì)算公式為

在當(dāng)前計(jì)算點(diǎn)為密度最大點(diǎn)時(shí)δi=maxj(dij)。選擇初始聚類中心的具體步驟需要依照上述密度和距離組成的決策圖，通過在決策圖中選取離群較遠(yuǎn)的點(diǎn)。決策圖是選擇聚類中心的關(guān)鍵，Alex給我們提供的決策圖由ρ和δ組成，他同時(shí)給出的手動(dòng)選點(diǎn)方法是盡量選擇決策圖右上方區(qū)域中的離群點(diǎn)，也就是ρ和δ同時(shí)顯著大的點(diǎn)，但這些點(diǎn)可能僅僅是部分而不是全部的簇中心，如圖1。

圖1 Iris數(shù)據(jù)集手動(dòng)選擇決策圖

圖中右上角兩個(gè)實(shí)心點(diǎn)是非常突出的更容易被人為視作僅有的兩個(gè)初始簇中心，但I(xiàn)ris數(shù)據(jù)集正確分類數(shù)應(yīng)為3，可見出現(xiàn)了簇中心少選的情況，而這種情況在手動(dòng)選擇簇中心時(shí)是很常見的。找到初始簇中心之后，其他點(diǎn)歸于最臨近且局部密度最大的簇。對(duì)于每個(gè)簇都需要一個(gè)邊界區(qū)域來對(duì)不同簇進(jìn)行劃分，邊界區(qū)域（border region）為每個(gè)簇的劃分界限，每個(gè)簇的邊界區(qū)域由該簇中的點(diǎn)集組成，點(diǎn)集中成員點(diǎn)滿足距其他簇中點(diǎn)的距離在dc之內(nèi)。

不屬于該簇且未被劃入邊界區(qū)域的點(diǎn)則為該簇的環(huán)（halo），環(huán)點(diǎn)則適合選為噪聲點(diǎn)。

根據(jù)上述算法思想，密度峰值聚類算法的關(guān)鍵步驟如下：

1）輸入數(shù)據(jù)集S的距離矩陣

2）使用式（1）計(jì)算每個(gè)點(diǎn)的局部密度ρ。

3）使用式（2）計(jì)算距離密度較大點(diǎn)的距離δ。

4）根據(jù)計(jì)算結(jié)果構(gòu)造ρ-δ決策圖，選擇ρ和δ都明顯大于其他點(diǎn)的數(shù)據(jù)點(diǎn)作為初始簇中心。

5）將簇中心外的數(shù)據(jù)對(duì)象歸到距離較近且局部密度大于它的簇。

6）輸出數(shù)據(jù)對(duì)象的聚類結(jié)果。

3 自動(dòng)聚類算法

本節(jié)將針對(duì)密度峰值聚類算法存在的手動(dòng)選擇簇中心的問題，使用最小二乘法結(jié)合決策圖進(jìn)行選點(diǎn)自動(dòng)化。并且，為了提高運(yùn)算速度，使自動(dòng)選點(diǎn)更快速，同時(shí)使選點(diǎn)策略脫離經(jīng)驗(yàn)化，使用了新的選點(diǎn)策略。以此又提出密度峰值自動(dòng)聚類算法ADPCA（A-utomatic Density Peak Clustering Algorithm），在無需人為干預(yù)的情況下取得更好的聚類效果。

為了減小計(jì)算誤差同時(shí)便于實(shí)現(xiàn)自動(dòng)選擇簇中心，本文在計(jì)算局部密度和決策圖的使用與上文介紹方法有所不同，局部密度計(jì)算使用了高斯核，相比式（1），高斯核計(jì)算數(shù)據(jù)點(diǎn)有相同局部密度的概率較小，從而有效避免沖突；決策圖方面使用γ-n決策圖。具體公式見式（3）。

其中di，j表示di和dj之間的距離，dc表示截?cái)嗑嚯x。γ計(jì)算公式見式（4）。

在γ-n決策圖中，γ分布曲線特點(diǎn)總體呈單調(diào)遞減，且在下降過程中存在一個(gè)位置，該位置我們稱為中間位置，它將圖像分為左右兩部分，左半部分下降速度快點(diǎn)較為稀疏，右半部分點(diǎn)較為密集下降更平緩。我們想要求得的簇中心特點(diǎn)是局部密度ρi和δi都較大的點(diǎn)，即γ值較大點(diǎn)，也即是要求左半部分的所有點(diǎn)作為簇中心點(diǎn)，由于簇中心點(diǎn)相比于其他點(diǎn)會(huì)大很多，那么我們接下來的工作就要尋找中間位置從而找到中間位置左側(cè)曲線上的點(diǎn)作為簇中心，γ-n決策圖例如圖2所示。

圖2 γ-n決策圖在Aggregation數(shù)據(jù)集中使用

本文中我們選擇使用兩條直線來表示左右兩部分區(qū)域，并在兩直線交點(diǎn)處作為中間位置［11］。擬合直線時(shí)我們使用最小二乘法［14］，對(duì)于曲線左右兩部分分別使用最小二乘法尋找擬合直線，對(duì)于每條擬合直線，我們?cè)O(shè)直線通過計(jì)算最小化平方誤差和來解得直線，平方誤差和如式（5）。

要想求得式（5）的最小值，對(duì)式（5）中a和b分別求偏導(dǎo)數(shù)，讓它們分別等于零。推導(dǎo)后得出正規(guī)方程（6）和（7）。

求解得a和b的表達(dá)式（8）和（9）。

從而得出左右直線。

下面的工作我們需要通過式（11）計(jì)算每條直線的均方根誤差（RMSE）并通過式（12）計(jì)算結(jié)果求得全局均方根誤差，從而在全局均方根誤差最小處找到合適的分界點(diǎn)C。其中xl=[2 ，3，…，c]，xr=[c +1，c+2，…，m]。

我們?cè)O(shè)左直線為L(zhǎng)右直線為R，以左直線L（右同理）為例的RMSE計(jì)算式（11）：

總的RMSE計(jì)算公式為式（12）：

我們要求的目標(biāo)C為式（13）：

上述過程中由于分界點(diǎn)更容易偏向于左半部分分布，我們不使用所有點(diǎn)進(jìn)行迭代，從而將有限的計(jì)算力集中于最可能出現(xiàn)分界點(diǎn)C的區(qū)域，因此我們從x=2開始向x軸正向選m-1個(gè)點(diǎn)。因?yàn)閏是區(qū)分是否為簇中心的分界點(diǎn)，我們的選點(diǎn)策略根據(jù)這一點(diǎn)首先要計(jì)算最可能成為簇中心的點(diǎn)的個(gè)數(shù)，然后將求得的個(gè)數(shù)乘以倍數(shù)k以覆蓋潛在的分界點(diǎn)C，選點(diǎn)策略過程在算法計(jì)算ρi和γi時(shí)同時(shí)完成，選點(diǎn)策略主要步驟如下：

1）計(jì)算平均局部密度mp，和δ值的標(biāo)準(zhǔn)差sδ。

2）統(tǒng)計(jì)點(diǎn)集

{x|ρ(x)>mp，且δ(x)>1.5sδ}中的點(diǎn)的數(shù)量n。

3）當(dāng) 數(shù) 據(jù) 集 大 小DT<1000時(shí)m=6n，當(dāng)DT≥1000時(shí)m=10n。

策略中第一步與第二步意在找出近似簇中心的點(diǎn)的數(shù)量，而在第三步中對(duì)可能存在的分界點(diǎn)C進(jìn)行覆蓋，且保證不選擇過多的點(diǎn)造成計(jì)算壓力，同時(shí)在實(shí)際應(yīng)用過程中m應(yīng)小于，N為數(shù)據(jù)集大小。最終的自動(dòng)聚類算法關(guān)鍵步驟如下：

1）輸入數(shù)據(jù)集S的距離矩陣；

2）計(jì)算數(shù)據(jù)點(diǎn)i的ρi和γi通過式（3）、（4）；

3）通過γ值構(gòu)造γ-n決策圖；

4）使用選點(diǎn)策略計(jì)算m，設(shè)RMSEC={}；

5）使用式（8）~（12）迭代計(jì)算每個(gè)選點(diǎn)處的RMSEC加入到RMSEC向量；

6）使用式（13）計(jì)算C的位置；

7）在γ-n決策圖中選擇[1 ，2，…，C]點(diǎn)作為初始簇中心；

8）分配非簇中心點(diǎn)到最近且ρ較大的簇中；

9）輸出簇k的點(diǎn)集a。

算法流程圖3所示。

圖3 ADPCA算法流程圖

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

本文實(shí)驗(yàn)環(huán)境為，3.5GHz CPU，16GB內(nèi)存，Windows10操作系統(tǒng)下，使用Matlab2020a完成。實(shí)驗(yàn)選用6個(gè)UCI常用數(shù)據(jù)集來驗(yàn)證自動(dòng)密度峰值聚類算法對(duì)于聚類工作的有效性，數(shù)據(jù)集包括二維數(shù)據(jù)和多維數(shù)據(jù)，使實(shí)驗(yàn)過程盡可能廣泛含蓋數(shù)據(jù)的各種分布形式。

具體數(shù)據(jù)集信息見表1其中數(shù)據(jù)集都有不同的分布特征。Aggregation數(shù)據(jù)集有7個(gè)類圓形的分布，其中兩個(gè)類圓形之間有連接部分；Iris是一種常用的多重變量分析的數(shù)據(jù)集，在統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)領(lǐng)域都很常用的數(shù)據(jù)集，通過它既可測(cè)試算法的準(zhǔn)確度，也可以檢驗(yàn)算法識(shí)別噪聲的能力；R15是生成用以測(cè)試多個(gè)聚類數(shù)的數(shù)據(jù)集，它包含15個(gè)不同形狀的簇；Spiral數(shù)據(jù)集呈旋渦形狀分布，其中組成旋渦的每一條圓弧曲線為同一簇，數(shù)據(jù)集用以測(cè)試不規(guī)則曲線形簇是否能準(zhǔn)確聚類；Ruspini數(shù)據(jù)集成四部分較分散分布，用以測(cè)試對(duì)不規(guī)則分布的數(shù)據(jù)集聚類效果；Sonar數(shù)據(jù)集用以測(cè)試在較高維度情況下的聚類效果。

表1 數(shù)據(jù)集信息

該算法只需設(shè)置一個(gè)參數(shù)截?cái)嗑嚯xdc，聚類結(jié)果對(duì)該參數(shù)設(shè)置不敏感，此參數(shù)的選擇時(shí)使在每個(gè)數(shù)據(jù)點(diǎn)的截?cái)嗑嚯x范圍內(nèi)的鄰居點(diǎn)數(shù)應(yīng)占數(shù)據(jù)點(diǎn)總數(shù)的2%~3%［8］，本文在實(shí)驗(yàn)過程中將此值選擇范圍定在4%。ADPCA算法在計(jì)算距離矩陣、局部密度、較高密度距離時(shí)的時(shí)間復(fù)雜度為O(n2)，選點(diǎn)策略實(shí)施包含在上述計(jì)算中。類算法必在降序排γ值時(shí)的時(shí)間復(fù)雜度為O(n log(n))，而聚類時(shí)的時(shí)間復(fù)雜度為O(n)，綜上ADPCA算法的時(shí)間復(fù)雜度為O(n2)，而距離矩陣是每個(gè)聚須計(jì)算的一步，因此如果不考慮參數(shù)計(jì)算，ADPCA算法在時(shí)間復(fù)雜度僅為O(n log(n))［15］。

我們使用DBSCAN、K-Means、DPC、ADPCA算法并使用ARI［16］（調(diào)蘭德指數(shù)）對(duì)相同數(shù)據(jù)集聚類結(jié)果進(jìn)行對(duì)比分析。

表2所示結(jié)果中，DBSCAN想要趨近期望結(jié)果，需要不斷調(diào)整兩個(gè)參數(shù)，可見該算法結(jié)果對(duì)參數(shù)設(shè)置的敏感性，如果提供的數(shù)據(jù)集預(yù)先未知期望簇?cái)?shù)的情況下想要較為準(zhǔn)確的聚類難度較大。K-Means算法需設(shè)置初始k值，從表中可以看出聚類效果相比其他三種算法較差，實(shí)際實(shí)驗(yàn)過程中在識(shí)別任意形狀的簇時(shí)效果較差，如在Spiral旋渦型數(shù)據(jù)集中，在輸入k正確的情況下，存在將不同曲線的點(diǎn)劃分到同一簇中的情況。DPC在初始簇?cái)?shù)選擇正確的情況下對(duì)任意形狀的數(shù)據(jù)聚類效果較好，在手動(dòng)選擇初始簇時(shí)不可避免會(huì)出現(xiàn)多選或少選。ADPCA無需人為干預(yù)的情況下即可獲得較好的聚類結(jié)果，對(duì)參數(shù)的設(shè)置不敏感，參數(shù)設(shè)置都較為相似情況下也能取得期望的結(jié)果。ADPCA算法通過自動(dòng)尋找初始簇中心進(jìn)行有效聚類，我們使用UCI常用數(shù)據(jù)集測(cè)試該算法。圖4為ADPCA聚類結(jié)果，可見不同形狀的簇也可以有良好的聚類效果，從圖4（a）聚類結(jié)果中，可見ADPCA可準(zhǔn)確識(shí)別任意形狀的簇；對(duì)于在圖4（b）聚類結(jié)果中存在的連通點(diǎn)干擾的兩個(gè)簇也有較好的聚類效果；圖4（c）中的螺旋形數(shù)據(jù)與圖4（e）的非規(guī)則數(shù)據(jù)集可準(zhǔn)確聚類；圖4（d）為ADPCA面對(duì)多分類數(shù)時(shí)的聚類結(jié)果表現(xiàn)，綜上說明ADPCA可以自動(dòng)準(zhǔn)確地計(jì)算簇?cái)?shù)，同時(shí)可以將每個(gè)點(diǎn)正確地分配到任意數(shù)據(jù)集形狀的類中。

表2 聚類算法對(duì)相同數(shù)據(jù)集聚類數(shù)對(duì)比

圖4 ADPCA在UCI常用數(shù)據(jù)集決策圖和聚類結(jié)果

從圖5中數(shù)據(jù)分布無特定形狀，密度較高的點(diǎn)分配在一個(gè)簇中，而黑色數(shù)據(jù)點(diǎn)被識(shí)別為噪聲點(diǎn)，可見ADPCA對(duì)任意形狀數(shù)據(jù)識(shí)別能力和對(duì)噪聲點(diǎn)的識(shí)別能力較強(qiáng)。

圖5 文獻(xiàn)［8］數(shù)據(jù)集聚類結(jié)果

5 結(jié)語

本文提出了一種自動(dòng)選擇密度峰值聚類算法ADPCA，該算法在聚類過程無需人工參與，能夠在聚類前自動(dòng)識(shí)別簇?cái)?shù)，無需結(jié)合聚類結(jié)果分析簇?cái)?shù)，同時(shí)我們對(duì)該算法聚類過程進(jìn)行優(yōu)化，提出選點(diǎn)策略減少需要考慮的數(shù)據(jù)量來減少算法運(yùn)行時(shí)間。為了證明ADPCA算法有效性，我們使用6種UCI數(shù)據(jù)集進(jìn)行測(cè)試，并測(cè)試了在高位數(shù)據(jù)集下的性能表現(xiàn)，實(shí)驗(yàn)結(jié)果看來算法的表現(xiàn)良好，在達(dá)到有效聚類的同時(shí)發(fā)現(xiàn)數(shù)據(jù)集的內(nèi)部規(guī)律，并對(duì)噪聲點(diǎn)進(jìn)行識(shí)別。

在未來的工作中我們想進(jìn)一步改進(jìn)dc選取方法，并解決可能出現(xiàn)的簇中心多選問題，使算法更具魯棒性。