周傳華， 魯 勇， 于 猜

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

0 引 言

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

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

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

1 OPTICS算法

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

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

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

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

(1)

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

OPTICS算法的具體步驟如下：

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

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

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

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

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

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

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

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

2.1.1 K-dist圖

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

圖1 K-dist曲線

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

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

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

1)K值的確定

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

(2)

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

2)初始聚類(lèi)中心的選取

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

2.2 分區(qū)合并

1)合并類(lèi)別

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

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

在實(shí)現(xiàn)數(shù)據(jù)分區(qū)時(shí)，某些較小的簇類(lèi)可能被劃分到不同的數(shù)據(jù)分區(qū)中，而在各個(gè)數(shù)據(jù)分區(qū)中由于其樣本點(diǎn)太少，導(dǎo)致在局部聚類(lèi)的過(guò)程中可能會(huì)被判定為噪聲點(diǎn)，因此在合并分區(qū)時(shí)同樣需要對(duì)分區(qū)內(nèi)的噪聲點(diǎn)進(jìn)行歸并處理，判斷這些噪聲點(diǎn)在全局中是否屬于某一簇類(lèi)，進(jìn)而將其歸類(lèi)到該簇中。對(duì)于一個(gè)噪聲點(diǎn)mi能否被歸類(lèi)到某一個(gè)簇類(lèi)Z中，定義如下：a.噪聲點(diǎn)mi和簇類(lèi)Z分別處于兩個(gè)相鄰的數(shù)據(jù)分區(qū)中；b.?pi∈Z，且dist(mi,pi)≤ε(Rz)，其中,ε(Rz)為類(lèi)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)測(cè)試，將DP-OPTICS算法聚類(lèi)結(jié)果與K均值算法、AP(affi-nity propagation)算法以及OPTICS算法進(jìn)行比較分析。K均值算法是目前應(yīng)用范圍最廣的聚類(lèi)算法，而AP算法擅長(zhǎng)處理高維數(shù)據(jù)，因此與上述三種算法進(jìn)行對(duì)比實(shí)驗(yàn)，可以很好地體現(xiàn)本文算法的有效性。

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

3.2 評(píng)價(jià)指標(biāo)

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

準(zhǔn)確率指正確聚類(lèi)樣本數(shù)占總樣本數(shù)的比例，計(jì)算方法簡(jiǎn)單且評(píng)價(jià)效果直觀，是最常用的評(píng)價(jià)指標(biāo)，適用于已知樣本標(biāo)簽的數(shù)據(jù)集。輪廓系數(shù)結(jié)合了內(nèi)聚度和簇間分離度兩種評(píng)價(jià)因素，是較為客觀全面的評(píng)價(jià)指標(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則表明聚類(lèi)效果越好。所有樣本點(diǎn)輪廓系數(shù)的平均值即為該數(shù)據(jù)集的總輪廓系數(shù)s(i)。

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

(4)

(5)

3.3 性能分析

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

圖2 4種算法聚類(lèi)效果

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

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

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

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

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

4 結(jié)束語(yǔ)

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