周傳華， 魯 勇， 于 猜

(1.中國科學(xué)技術(shù)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230026； 2.安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 馬鞍山 243002)

0 引 言

聚類算法是一種無監(jiān)督的學(xué)習(xí)方法，在圖像處理、模式識別等方面有著廣泛的應(yīng)用[1,2],其主要目的是從大量數(shù)據(jù)中提取出潛在的、有價值的信息。聚類算法的中心思想是依據(jù)數(shù)據(jù)自身的特性，將數(shù)據(jù)對象自動地歸類到相應(yīng)的簇中，使得簇間相似度盡可能小而簇內(nèi)相似度盡可能大。目前常用的聚類算法主要包括：層次聚類(balanced iterative reducing and clustering using hierarchies，BIRCH)[3]、劃分聚類(K-Means)[4]、密度聚類(density-based spatial clustering of applications with noise，DBSCAN)以及網(wǎng)格聚類(statistical information grid，STING)等[3～6]，其中基于密度的聚類算法更是近年來學(xué)者們的研究重點(diǎn)。

周水庚等人[7]率先提出了基于數(shù)據(jù)分區(qū)的DBSCAN算法,根據(jù)數(shù)據(jù)空間分布情況，將數(shù)據(jù)集劃分為若干個子區(qū)域，并在各個子區(qū)域內(nèi)實(shí)現(xiàn)聚類。Rodriguez A等人[8]隨后提出基于密度峰值的聚類算法,可以實(shí)現(xiàn)對凹數(shù)據(jù)集的聚類。劉滄生等人[9]利用密度峰值算法對模糊C均值聚類>算法進(jìn)行優(yōu)化，使其能夠自適應(yīng)產(chǎn)生初始聚類中心。于彥偉等人[10]在研究面向位置大數(shù)據(jù)聚類問題時，提出了一種高效的密度聚類算法(CBSCAN)，能夠?qū)θ我庑螤畹拇仡惣霸肼晫?shí)現(xiàn)快速定位。侯思祖等人[11]提出了一種適合多密度的DBSCAN改進(jìn)算法。該算法首先識別出每個數(shù)據(jù)對象周圍的密度，之后自動生成適合本區(qū)域密度的密度閾值。李薊濤等人[12]將密度聚類算法與圖論知識相結(jié)合，依照數(shù)據(jù)密度特征進(jìn)行分塊后合并處理，解決了傳統(tǒng)密度聚類算法使用全局參數(shù)的局限性。但密度聚類算法依然存在著對于密度不均勻以及高維數(shù)據(jù)聚類效果差的問題。

為了解決上述問題，本文提出了一種基于數(shù)據(jù)分區(qū)的OPTICS算法(DP-OPTICS)，并通過實(shí)驗(yàn)得出，該算法對密度不均勻和高維數(shù)據(jù)集都有不錯的聚類效果。

1 OPTICS算法

OPTICS算法是一種基于密度的聚類算法，是對傳統(tǒng)密度聚類算法DBSCAN的一種改進(jìn)，既繼承了密度聚類算法的優(yōu)點(diǎn)，同時也解決了密度聚類算法參數(shù)難以確定的問題[13]。DBSCAN算法需要確定兩個參數(shù)，即鄰域半徑ε以及點(diǎn)數(shù)閾值(minimum point threshold，MinPts)。目前，大部分學(xué)者認(rèn)為MinPts在二維空間聚類中一般取4[14]，或者取數(shù)據(jù)集合的1/25[15]，但鄰域半徑ε的數(shù)值卻需要在實(shí)驗(yàn)過程中不斷地調(diào)試，為算法的實(shí)現(xiàn)帶來一定的困擾。但OPTICS算法不直接顯示聚類結(jié)果，而是生成一個含有可達(dá)距離信息的增廣簇排序，從這個排序中可以觀察得到基于任何參數(shù)ε和MinPts的DBSCAN算法的聚類結(jié)果，大大提高了算法的執(zhí)行效率。

定義1核心對象：對?mp∈D，若在mp的ε鄰域內(nèi)的樣本點(diǎn)個數(shù)等于或大于MinPts，則稱mp為核心對象。

定義2核心距離：使得mp成為核心對象的最小鄰域半徑ε稱為mp的核心距離，記為cd(mp)。

定義3可達(dá)距離：對于?mp,mq∈D，則其可達(dá)距離記為

(1)

定義4直接密度可達(dá)：若mq在mp的ε鄰域內(nèi)，且mp是核心對象，則稱mq是從mp直接密度可達(dá)的。

OPTICS算法的具體步驟如下：

Step1 標(biāo)記數(shù)據(jù)集D中所有樣本點(diǎn)均為未處理點(diǎn)，設(shè)置參數(shù)鄰域半徑ε以及點(diǎn)數(shù)閾值MinPts。

Step2 創(chuàng)建有序隊列和結(jié)果隊列，其中結(jié)果隊列用來存儲樣本的輸出順序。

Step3 若樣本數(shù)據(jù)集D中的所有樣本點(diǎn)均被標(biāo)記為已處理，則算法結(jié)束。否則選取一個核心對象，將其直接密度可達(dá)點(diǎn)放入有序隊列中，并依據(jù)可達(dá)距離升序排序。

Step4 若有序隊列中已無樣本點(diǎn)，則跳轉(zhuǎn)步驟Step2,否則將有序隊列的第一個點(diǎn)放入結(jié)果隊列中，并做以下操作：1)如果該點(diǎn)不是核心對象則返回Step4，反之則記錄該點(diǎn)所有的密度可達(dá)點(diǎn)；2)若直接密度可達(dá)點(diǎn)已在結(jié)果隊列中，則忽略；若在有序隊列中，則在新舊可達(dá)距離中選擇更小的可達(dá)距離記錄，并按距離遠(yuǎn)近依次排序；若不在兩個隊列中，則在有序隊列中插入該點(diǎn)并排序。

Step5 迭代Step3、Step4直至算法結(jié)束，按順序輸出結(jié)果隊列中的所有樣本點(diǎn)及其對應(yīng)的可達(dá)距離。

2 數(shù)據(jù)分區(qū)的OPTICS算法

OPTICS算法雖然以輸出有序決策圖的方式解決了DBSCAN算法參數(shù)ε難以確定的問題，但對數(shù)據(jù)密度不均勻以及高維數(shù)據(jù)進(jìn)行聚類時，輸出的有序決策圖比較雜亂，難以選擇一個合適的鄰域半徑ε將簇精準(zhǔn)地分隔開?；谏鲜隹紤]，本文提出DP-OPTICS聚類算法,通過計算樣本點(diǎn)之間的K-dist距離，利用改進(jìn)的K均值算法對樣本點(diǎn)的K-dist距離進(jìn)行單維度聚類，實(shí)現(xiàn)數(shù)據(jù)分區(qū)。數(shù)據(jù)分區(qū)完成后，在各個子區(qū)域內(nèi)進(jìn)行用OPTICS算法進(jìn)行局部聚類，最后再按照一定規(guī)則合并分區(qū)并對局部聚類過程中產(chǎn)生的噪聲點(diǎn)作相應(yīng)處理。

2.1 數(shù)據(jù)分區(qū)

2.1.1 K-dist圖

K-dist圖是由Ester等人于1996年首次提出的，基本思想是計算數(shù)據(jù)集中每個樣本點(diǎn)與其第K個臨近點(diǎn)之間的距離，并輸出以樣本點(diǎn)序列號為橫坐標(biāo)，K-dist值為縱坐標(biāo)的散點(diǎn)圖，將這些點(diǎn)連接起來就形成了K-dist圖。如圖1所示，曲線A，B分別對應(yīng)兩個不同數(shù)據(jù)集的K-dist曲線。曲線A中平緩的部分對應(yīng)數(shù)據(jù)集中的大多數(shù)樣本點(diǎn)，這些點(diǎn)的K-dist值差距不大，說明樣本點(diǎn)分布較均勻；曲線A后半部分K-dist值突然增大，說明所對應(yīng)的樣本點(diǎn)是邊界點(diǎn)或噪聲點(diǎn)。曲線B分為6個階段，其中a，b，c三個階段較為平緩且依次上升，分別代表數(shù)據(jù)集的三個密度水平；曲線d，e段則是連接a，b以及b，c的密度轉(zhuǎn)折曲線，曲線f代表邊界點(diǎn)或噪聲點(diǎn)。研究表明，k>4時的K-dist曲線圖與k=4時的曲線圖幾乎完全一致，因此在實(shí)際應(yīng)用中k值一般取4[16]。

圖1 K-dist曲線

K-dist圖能夠反映數(shù)據(jù)集的空間分布情況，緊密的簇類K-dist值普遍較小，稀疏的簇類K-dist值則相對較大，因此對K-dist值進(jìn)行單維度聚類，對比橫坐標(biāo)所代表的樣本點(diǎn)的序列號，即可依據(jù)數(shù)據(jù)密度差實(shí)現(xiàn)數(shù)據(jù)分區(qū)。同時，由于K-dist是一種基于密度的概念，與每個簇類所處的位置無關(guān)，所以，即使簇類之間存在包含或交叉等關(guān)系，K-dist圖也能夠很好地實(shí)現(xiàn)數(shù)據(jù)分區(qū)[17]。

2.1.2 改進(jìn)的K均值算法

本文選用簡單快速的K均值算法實(shí)現(xiàn)對K-dist圖的單維度聚類，以實(shí)現(xiàn)初步的數(shù)據(jù)分區(qū)。算法基本步驟是隨機(jī)選取K個樣本點(diǎn)作為初始聚類中心，計算每個樣本點(diǎn)與各個聚類中心之間的距離，并將樣本點(diǎn)歸類到與其距離最小的聚類中心，之后不斷更新迭代，直至所有樣本點(diǎn)均劃分到相應(yīng)的簇中。K均值算法在實(shí)際運(yùn)用過程中需要預(yù)先設(shè)置K值(即簇類數(shù))，同時初始聚類中心的選取也至關(guān)重要。

1)K值的確定

使用誤差平方和(SSE)建立肘圖，以此確定K均值算法中K值的大小，具體定義如下

(2)

式中ml為某個簇的各個樣本點(diǎn)，p為聚類中心。肘圖以K值為橫坐標(biāo)，以SSE為縱坐標(biāo)，隨著K值的增大，簇內(nèi)聚合越緊密，SSE將逐漸變小并趨于0。若K值小于真實(shí)簇類數(shù)，則隨著K值增大，簇內(nèi)聚合程度將大幅增加，SSE快速減??；而如果K值大于真實(shí)簇類數(shù)，繼續(xù)增大K值所得到的聚合程度回報會迅速變小，SSE的下降幅度也會驟減，因此肘圖拐點(diǎn)處所對應(yīng)的K值就應(yīng)當(dāng)是數(shù)據(jù)的真實(shí)簇類數(shù)。

2)初始聚類中心的選取

改進(jìn)的K均值算法雖然在計算K值和初始聚類中心時需要耗費(fèi)一定的時間，但在整個迭代過程中，算法能夠更加快速地收斂，因此實(shí)際上提高了算法運(yùn)行效率。

2.2 分區(qū)合并

1)合并類別

在局部聚類完成后，需要對各個數(shù)據(jù)分區(qū)進(jìn)行合并，進(jìn)而完成對整個數(shù)據(jù)集的聚類?？紤]到利用K-dist圖分區(qū)時，可能會出現(xiàn)同一個簇被劃分到兩個相鄰的數(shù)據(jù)分區(qū)中，因此在合并分區(qū)時，不能簡單地將分區(qū)中的簇的種類數(shù)疊加，而要考慮分區(qū)合并后，兩個簇是否能合并為一個簇。為了提高數(shù)據(jù)分區(qū)的合并效率，在局部聚類的過程中，標(biāo)記了分區(qū)內(nèi)的噪聲點(diǎn)以及簇的邊界點(diǎn)，并記錄其信息。對于兩個類X和Y的合并，給出如下定義：a.類X和類Y分別被分割在兩個相鄰的數(shù)據(jù)分區(qū)Rx和Ry中；b.存在任意兩個樣本點(diǎn)mp∈X，mq∈Y，且dist(mp,mq)≤min{ε(Rx),ε(Ry)}。若滿足上述兩種情況，在分區(qū)合并后，選用Rx和Ry兩個分區(qū)中更小的鄰域半徑ε，類X和類Y將會合并為一類，故此認(rèn)為X，Y同屬一個簇類。

2)歸并噪聲點(diǎn)

在實(shí)現(xiàn)數(shù)據(jù)分區(qū)時，某些較小的簇類可能被劃分到不同的數(shù)據(jù)分區(qū)中，而在各個數(shù)據(jù)分區(qū)中由于其樣本點(diǎn)太少，導(dǎo)致在局部聚類的過程中可能會被判定為噪聲點(diǎn)，因此在合并分區(qū)時同樣需要對分區(qū)內(nèi)的噪聲點(diǎn)進(jìn)行歸并處理，判斷這些噪聲點(diǎn)在全局中是否屬于某一簇類，進(jìn)而將其歸類到該簇中。對于一個噪聲點(diǎn)mi能否被歸類到某一個簇類Z中，定義如下：a.噪聲點(diǎn)mi和簇類Z分別處于兩個相鄰的數(shù)據(jù)分區(qū)中；b.?pi∈Z，且dist(mi,pi)≤ε(Rz)，其中,ε(Rz)為類C所在分區(qū)Rz的鄰域半徑。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文在UCI真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)測試，將DP-OPTICS算法聚類結(jié)果與K均值算法、AP(affi-nity propagation)算法以及OPTICS算法進(jìn)行比較分析。K均值算法是目前應(yīng)用范圍最廣的聚類算法，而AP算法擅長處理高維數(shù)據(jù)，因此與上述三種算法進(jìn)行對比實(shí)驗(yàn)，可以很好地體現(xiàn)本文算法的有效性。

選取的實(shí)驗(yàn)數(shù)據(jù)集為人工數(shù)據(jù)集Jain,Spiral以及UCI真實(shí)數(shù)據(jù)集Iris,Seeds和Glass，五個數(shù)據(jù)集常用于聚類算法的測試且均具有一定的代表性。Jain數(shù)據(jù)集有2個簇，簇間距離較近且樣本點(diǎn)密度不均，使得聚類難度較大；Spiral數(shù)據(jù)集包含3個類別，該數(shù)據(jù)集最大的特點(diǎn)就是簇間差異大、簇的形狀呈螺旋狀且含有噪聲點(diǎn)。Iris,Seeds,Glass數(shù)據(jù)集來源于UCI真實(shí)數(shù)據(jù)集，數(shù)據(jù)維度分別為4，7，9維，可以用于檢驗(yàn)算法處理高維數(shù)據(jù)的能力。各數(shù)據(jù)集具體的屬性描述見表1。

3.2 評價指標(biāo)

聚類算法常用的評價標(biāo)準(zhǔn)包括準(zhǔn)確率、蘭德指數(shù)(Rand index，RI)、調(diào)整蘭德指數(shù)(adjusted Rand index,ARI)、以及輪廓系數(shù)等?？紤]到使用單一的評價指標(biāo)可能會導(dǎo)致評價結(jié)果過于片面，因此，本文選取上述指標(biāo)對4種算法的聚類結(jié)果進(jìn)行綜合評價。

準(zhǔn)確率指正確聚類樣本數(shù)占總樣本數(shù)的比例，計算方法簡單且評價效果直觀，是最常用的評價指標(biāo)，適用于已知樣本標(biāo)簽的數(shù)據(jù)集。輪廓系數(shù)結(jié)合了內(nèi)聚度和簇間分離度兩種評價因素，是較為客觀全面的評價指標(biāo)，輪廓系數(shù)的具體定義如下

(3)

式中a(i)為點(diǎn)mi到所屬簇的其他點(diǎn)的平均距離，表示簇內(nèi)不相似度；b(i)為點(diǎn)mi到其他簇中的樣本點(diǎn)的平均距離最小值，表示簇間不相似度。s(mi)的取值范圍為[-1,1]，-1表示該樣本應(yīng)該被歸為其他簇，0代表該樣本在兩簇的邊界上，輪廓系數(shù)越接近1則表明聚類效果越好。所有樣本點(diǎn)輪廓系數(shù)的平均值即為該數(shù)據(jù)集的總輪廓系數(shù)s(i)。

ARI表示聚類結(jié)果的類別信息與正確類別相符的程度。ARI取值范圍為[-1,1]，值越大意味著聚類結(jié)果與真實(shí)情況吻合度越高，具體定義如下

(4)

(5)

3.3 性能分析

本文的實(shí)驗(yàn)環(huán)境配置：CPU為Intel?CoreTMi7—4720HQ@2.60 GHz，16.0 GB內(nèi)存，采用Python語言在PyCharm環(huán)境下編程實(shí)現(xiàn)。首先使用3種對比算法和DP-OPTICS算法對密度不均勻的人工數(shù)據(jù)集Jain,Spiral進(jìn)行聚類，聚類的具體效果如圖2所示。

圖2 4種算法聚類效果

由圖2可知，K均值聚類算法和AP聚類算法不能識別Spiral數(shù)據(jù)集中螺旋狀的簇，同時對于密度不均的Jain數(shù)據(jù)集也很難處理，聚類效果相對較差；而OPTICS算法和DP-OPTICS算法，兩者雖然都可以識別出螺旋狀簇類，但是OPTICS密度聚類算法在Jain和Spiral數(shù)據(jù)集上的聚類效果明顯弱于DP-OPTICS算法，尤其是在Jain數(shù)據(jù)集兩個簇接近的部分，OPTICS算法未能將簇完全區(qū)分正確，而DP-OPTICS算法則只有一個樣本點(diǎn)沒有歸類正確。4種算法在各數(shù)據(jù)集上聚類的具體實(shí)驗(yàn)結(jié)果數(shù)據(jù)見表2。

表2 不同算法在各數(shù)據(jù)集上評價指標(biāo)準(zhǔn)確率、輪廓系數(shù)、ARI對比

由表2可知，本文提出的DP-OPTICS算法在各個數(shù)據(jù)集上表現(xiàn)均佳，尤其是在密度不均勻的人工數(shù)據(jù)集上有著較大的優(yōu)勢，準(zhǔn)確率分別達(dá)到了99.73 %和100 %，輪廓系數(shù)和ARI也更高。

傳統(tǒng)的密度聚類OPTICS算法在Jain，Spiral數(shù)據(jù)集上表現(xiàn)不錯，但在高維數(shù)據(jù)集上聚類效果則有明顯下降，而經(jīng)過改進(jìn)后的DP-OPTICS算法不僅對密度不均勻的人工數(shù)據(jù)集有著更好的聚類效果，在其他三個高維數(shù)據(jù)集上的聚類結(jié)果也明顯更優(yōu)，準(zhǔn)確率均達(dá)到90 %以上，ARI也穩(wěn)定在0.8左右。

由于AP算法不能識別螺旋狀的簇，導(dǎo)致對Spiral數(shù)據(jù)集聚類效果差，各項(xiàng)評價指標(biāo)均遠(yuǎn)小于DP-OPTICS算法。而在Iris數(shù)據(jù)集上，由于數(shù)據(jù)集本身簇類之間差別較小，用K-dist圖進(jìn)行分區(qū)時，可能會破壞聚類的自然結(jié)構(gòu)，因此DP-OPTICS算法在Iris數(shù)據(jù)集上的表現(xiàn)不如擅長處理高維數(shù)據(jù)集的AP算法，但聚類效果仍要強(qiáng)于K-Means算法和OPTICS算法。

4 結(jié)束語

本文通過對OPTICS密度聚類算法的分析，針對其局限性，提出了結(jié)合K-dist圖和K均值算法進(jìn)行數(shù)據(jù)分區(qū)的DP-OPTICS算法。實(shí)驗(yàn)結(jié)果表明：DP-OPTICS算法在對密度不均勻的Jain數(shù)據(jù)集進(jìn)行聚類時，明顯緩解了密度聚類算法因采用全局參數(shù)ε而導(dǎo)致的聚類效果不佳的問題，聚類精準(zhǔn)性相較于傳統(tǒng)聚類算法有顯著提高，聚類的結(jié)果更接近于數(shù)據(jù)的實(shí)際分布情況。同時，對于高維數(shù)據(jù)集，DP-OPTICS算法也有著不錯的處理能力，但對于高維數(shù)據(jù)中簇類差距較小的數(shù)據(jù)集，其聚類效果不如擅長處理高維數(shù)據(jù)集的AP聚類算法，尚有改進(jìn)的空間。