數(shù)據(jù)點(diǎn)的密度引力聚類新算法*

溫曉芳，楊志翀，陳 梅

蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070

1 引言

隨著互聯(lián)網(wǎng)和信息產(chǎn)業(yè)的高速發(fā)展，數(shù)據(jù)量不斷增長，形式也呈現(xiàn)多樣化、復(fù)雜化。但傳統(tǒng)的數(shù)據(jù)處理技術(shù)仍處于貧乏的狀態(tài)[1]。如何有效地識(shí)別各種數(shù)據(jù)集的真實(shí)結(jié)構(gòu)是數(shù)據(jù)挖掘目前面臨的一個(gè)主要問題。聚類分析作為數(shù)據(jù)挖掘的一項(xiàng)重要技術(shù)[2]，能夠根據(jù)數(shù)據(jù)間的相似性識(shí)別出數(shù)據(jù)集中的內(nèi)在模式，特別適用于探索數(shù)據(jù)點(diǎn)之間的相互關(guān)系，以對(duì)其結(jié)構(gòu)進(jìn)行評(píng)估[3]。然而，很多先進(jìn)的聚類算法在劃分不同類型的數(shù)據(jù)集時(shí)，均遇到了精確性不高或者執(zhí)行效率較低等問題[4]，因此聚類算法性能的提高勢(shì)在必行。

目前，已有許多聚類算法被提出。其中，最經(jīng)典的基于劃分的方法有k-means和k-medoids，但是由于這兩種算法對(duì)初始中心的選取較為依賴，通常不能獲得全局最優(yōu)結(jié)果，并且只能發(fā)現(xiàn)球狀簇?；诿芏鹊囊粋€(gè)經(jīng)典聚類算法DBSCAN（density-based spatial clustering of application with noise）[5]將高密度點(diǎn)連通區(qū)域劃分為簇，它能夠識(shí)別任意形狀和任意大小簇，但當(dāng)數(shù)據(jù)集的密度變化較大時(shí)，聚類質(zhì)量就會(huì)變差。OPTICS[6]通常被認(rèn)為是DBSCAN的改進(jìn)算法，它不顯示產(chǎn)生的結(jié)果簇，而是為聚類分析方便生成了一個(gè)有序的對(duì)象列表，但其依然對(duì)數(shù)據(jù)集中的密度變化較敏感。一個(gè)先進(jìn)的層次聚類方法——CHAMELEON[7]使用動(dòng)態(tài)模型通過簇間相對(duì)互連度和相對(duì)接近度將分開的小簇合并，直到最終簇形成。該算法雖然可以發(fā)現(xiàn)任意形狀簇，但其時(shí)間復(fù)雜度非常高。CURE[8]和ROCK[9]也是基于層次的聚類算法。CURE使用多個(gè)點(diǎn)表示簇，并使用隨機(jī)抽樣的方法來提高效率，從而可以有效處理大數(shù)據(jù)，并且能檢測(cè)到異常點(diǎn)，但其時(shí)間復(fù)雜度依然較高。相對(duì)于CURE，ROCK克服了其缺點(diǎn)，但它對(duì)全局參數(shù)非常敏感，不能識(shí)別密度不均勻的數(shù)據(jù)集。AP（affinity propagation）[10]是一個(gè)根據(jù)數(shù)據(jù)點(diǎn)間相似度自動(dòng)聚類的方法。吸引度和歸屬度信息在數(shù)據(jù)點(diǎn)間迭代交換，直到高質(zhì)量的一組樣本和相應(yīng)的簇出現(xiàn)。該算法不需要用戶指定聚類個(gè)數(shù)，但需事先設(shè)置參考度，且數(shù)據(jù)量大時(shí)運(yùn)行時(shí)間長。

近年來，人們又提出了一些新的聚類方法。Attractor[11]是一個(gè)社團(tuán)檢測(cè)聚類算法。它通過檢測(cè)節(jié)點(diǎn)之間的“距離”變化，使得相同社區(qū)的節(jié)點(diǎn)互相靠近，不同社區(qū)的節(jié)點(diǎn)彼此遠(yuǎn)離，自動(dòng)在網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)。為分析網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)提供了一種直觀的方法。CLUB（clustering based on backbone）[12]是一個(gè)根據(jù)簇的密度主干聚類的算法。它先將兩個(gè)互k-近鄰點(diǎn)聚在一起形成初始簇，然后取初始簇內(nèi)密度較大的半數(shù)點(diǎn)，不斷吸引與其有k-近鄰關(guān)系的點(diǎn)來擴(kuò)展簇；最后將剩余不含標(biāo)簽的點(diǎn)分配給密度比它大的最近鄰所屬的簇，形成最終簇。該算法能自動(dòng)適應(yīng)不同密度，并正確檢測(cè)出簇的數(shù)目和結(jié)構(gòu)，為發(fā)現(xiàn)任意簇提供了有價(jià)值的參考。一個(gè)無參聚類算法Txmeans[13]采用自頂向下分而治之的策略，迭代地將一個(gè)簇分成兩個(gè)不相交的子簇。其性能在噪聲和變化的聚類結(jié)構(gòu)上表現(xiàn)穩(wěn)定，并且可擴(kuò)展到大型數(shù)據(jù)集，為層次聚類提供了一種新的思路。Perch[14]是一個(gè)非貪心增量算法。它先將新數(shù)據(jù)點(diǎn)路由到生長樹的樹葉，然后通過旋轉(zhuǎn)操作來保持其質(zhì)量，最后以遞增的方式在數(shù)據(jù)點(diǎn)上構(gòu)建樹結(jié)構(gòu)。這種樹結(jié)構(gòu)使得有效搜索大數(shù)據(jù)集成為可能，同時(shí)為提取不同分辨率下的多個(gè)簇提供了豐富的數(shù)據(jù)結(jié)構(gòu)。

基于上述存在的問題，本文提出一種數(shù)據(jù)點(diǎn)間的密度引力聚類算法。從物理學(xué)角度來看，任何兩個(gè)物體間存在著萬有引力。由于數(shù)據(jù)集中的每個(gè)點(diǎn)可以看作為物體的質(zhì)點(diǎn)，從而認(rèn)為兩個(gè)數(shù)據(jù)點(diǎn)間也存在著某種引力。本文研究將這種引力與數(shù)據(jù)點(diǎn)的密度建立起一種關(guān)系，稱之為密度引力。通過此引力將每個(gè)數(shù)據(jù)點(diǎn)與密度比它大且距離其最近的互近鄰點(diǎn)劃分到一起形成初始簇。然后合并具有共同點(diǎn)的初始簇，得到數(shù)據(jù)集的真實(shí)劃分。該算法可以發(fā)現(xiàn)任意簇，如實(shí)地反映了數(shù)據(jù)的實(shí)際情況。

本文其余部分安排如下：第2章描述了數(shù)據(jù)點(diǎn)的密度引力聚類算法；第3章分析比較了本文算法與對(duì)比算法在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果；第4章對(duì)本文進(jìn)行總結(jié)和未來展望。

2 密度引力聚類算法

從物理學(xué)角度來看，任何兩個(gè)物體在自然界中是相互吸引的。數(shù)據(jù)集中的每個(gè)點(diǎn)可以看作為一個(gè)質(zhì)點(diǎn)。通過模擬事物在自然界中的運(yùn)行規(guī)律和自然狀態(tài)，本文定義了密度引力的概念。進(jìn)一步，提出基于數(shù)據(jù)點(diǎn)的密度引力聚類算法。

設(shè)在歐式空間中，存在一個(gè)包含n個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集D，記作D={x1,x2,…,xi,…,xn}，i=1,2,…,n。其中，xi表示數(shù)據(jù)集D中的第i個(gè)點(diǎn)，并且每個(gè)點(diǎn)都有p個(gè)屬性，屬性之間相互獨(dú)立，每個(gè)點(diǎn)可以表示為xi=(xi1,xi2,…,xip)。

2.1 相關(guān)定義

定義1（k-近鄰）對(duì)于D中的每個(gè)點(diǎn)xi，通過計(jì)算xi與D中其他點(diǎn)之間的歐氏距離并按從小到大的順序排列，其中排在前k個(gè)的點(diǎn)均被稱為xi的k-近鄰。記作Nk(xi)，且Nk(xi)?D。

定義2（互k-近鄰）設(shè)數(shù)據(jù)集D中，如果點(diǎn)xi是xj的k-近鄰點(diǎn)，同時(shí)xj也是xi的k-近鄰點(diǎn)，則稱xi和xj互為k-近鄰；否則，二者不互為k-近鄰。另外，xi所有的互k-近鄰記作MNk(xi)。

定義3（點(diǎn)密度）數(shù)據(jù)集中點(diǎn)的局部密度與其周圍鄰居點(diǎn)的密集程度有關(guān)。若點(diǎn)xi的鄰居越多，鄰居距離該點(diǎn)越近，則點(diǎn)xi的密度就越大。因此定義點(diǎn)密度與其鄰居的個(gè)數(shù)成正比，與鄰居點(diǎn)到該點(diǎn)間的距離和成反比。點(diǎn)密度如式（1）所示：

其中，ρi表示點(diǎn)xi的密度，K表示xi鄰居點(diǎn)的個(gè)數(shù)，dij表示xi與其鄰居xj之間的歐氏距離。

定義4（密度引力）自然界中任意兩個(gè)物體之間存在著引力，當(dāng)把物體看作為質(zhì)點(diǎn)時(shí)，根據(jù)分布規(guī)律，本文提出兩質(zhì)點(diǎn)之間仍存在一種引力——密度引力。如式（2）所示：

其中，F(xiàn)表示點(diǎn)xi和xj之間的密度引力，G表示一個(gè)引力常量。

本文使用基于互k-近鄰的距離度量，彌補(bǔ)了單方向挖掘數(shù)據(jù)點(diǎn)而缺乏的信息，使得數(shù)據(jù)點(diǎn)之間的關(guān)系更加緊湊。采用這種方法可以將相關(guān)性強(qiáng)的點(diǎn)吸引進(jìn)同一個(gè)簇，實(shí)現(xiàn)數(shù)據(jù)集的真實(shí)劃分。

2.2 聚類過程

本文提出的密度引力聚類算法將通過三個(gè)階段來發(fā)現(xiàn)數(shù)據(jù)集中的真實(shí)簇。首先，通過式（1）獲得每個(gè)點(diǎn)的密度并尋找其互k-近鄰；然后，采用密度引力的思想形成初始簇；最后，將具有共同點(diǎn)的初始簇合并形成最終簇。具體過程如下描述。

算法1獲得點(diǎn)密度及其互近鄰

輸入：數(shù)據(jù)集D，最近鄰居個(gè)數(shù)k。

輸出：每個(gè)點(diǎn)的密度ρi，互近鄰集合M。

在第一階段，首先通過式（1）計(jì)算每個(gè)點(diǎn)的密度ρi。當(dāng)分子K依次增加1時(shí)，分母依次增加一個(gè)距離diK且diK≥diK-1，因此整體點(diǎn)密度隨著K的增大而減小。然而每個(gè)點(diǎn)密度的相對(duì)大小幾乎保持不變。為了方便計(jì)算，將K設(shè)置為固定值5。然后，尋找D中每個(gè)點(diǎn)的互k-近鄰點(diǎn)（k≥K）。對(duì)于每個(gè)點(diǎn)xi，找到其k-近鄰后，依次判斷是否同時(shí)滿足條件xj∈Nk(xi)和xi∈Nk(xj)，如果滿足，那么xi和xj為互k-近鄰；否則，掃描下一個(gè)點(diǎn)，直到所有的點(diǎn)都被掃描完。最后，將點(diǎn)xi和其互k-近鄰放入mi中，再將所有的mi放入互近鄰集合M中。

在第二階段，數(shù)據(jù)集中的每個(gè)點(diǎn)有三種情況：（1）沒有互k-近鄰。說明點(diǎn)xi周圍比較稀疏，成為孤立點(diǎn)的概率比較大，將該點(diǎn)獨(dú)自放在一個(gè)簇中。（2）點(diǎn)xi的密度大于其所有的互k-近鄰點(diǎn)的密度。說明點(diǎn)xi周圍的點(diǎn)比較密集，很有可能是簇的代表中心點(diǎn)，且對(duì)每個(gè)互k-近鄰點(diǎn)的吸引比較大，從而將其與所有的互k-近鄰點(diǎn)聚集到同一個(gè)簇中。（3）點(diǎn)xi的密度小于或等于其所有的互k-近鄰點(diǎn)的密度。說明點(diǎn)xi的互近鄰中有比其密度大的點(diǎn)，同時(shí)對(duì)xi具有很強(qiáng)的吸引力，將點(diǎn)xi分配給密度比它大且距離最近的互k-近鄰點(diǎn)形成初始簇，其中也包含密度相同的點(diǎn)。通過這種分配方式可以將密集的數(shù)據(jù)點(diǎn)劃分到同一個(gè)簇，稀疏的點(diǎn)相隔開，過于分散的點(diǎn)則被識(shí)別為異常點(diǎn)。

算法2形成初始簇。

輸入：每個(gè)點(diǎn)的密度ρi，互近鄰集合M。

輸出：初始簇集合C。

算法3合并得到最終簇

輸入：初始簇集合C。

輸出：最終簇集合C′。

在第三階段，合并初始簇形成最終簇。上階段得到的初始簇都是一些比較小的簇集合，由于每個(gè)簇中的點(diǎn)相對(duì)密集，因此需要將多個(gè)具有相同數(shù)據(jù)點(diǎn)的初始簇合并，逐漸擴(kuò)大簇的規(guī)模，直到?jīng)]有可以合并的簇為止，最終形成真實(shí)的數(shù)據(jù)結(jié)構(gòu)。采用這種方法不需要用戶輸入停止參數(shù)，可以根據(jù)數(shù)據(jù)集的特點(diǎn)進(jìn)行自動(dòng)合并并停止。

2.3 時(shí)間復(fù)雜度分析

由于該算法使用k-d樹[15]作為數(shù)據(jù)結(jié)構(gòu)，當(dāng)有效地檢索特定點(diǎn)給定距離內(nèi)的所有點(diǎn)時(shí)，時(shí)間復(fù)雜度為O(nlbn)，其中，n為數(shù)據(jù)集D中點(diǎn)的個(gè)數(shù)。在第一階段中，計(jì)算每個(gè)點(diǎn)的k個(gè)鄰居時(shí)需要花費(fèi)O(nlbn)的時(shí)間，尋找每個(gè)點(diǎn)的互k-近鄰時(shí)的時(shí)間復(fù)雜度為O(kn)，其中，k為最近鄰居點(diǎn)的數(shù)量，由于k?n，因此尋找互k-近鄰的時(shí)間復(fù)雜度接近O(n)。第二階段形成初始簇時(shí)，外循環(huán)中，由于依次掃描數(shù)據(jù)集中每個(gè)點(diǎn)，時(shí)間復(fù)雜度為O(n)；內(nèi)循環(huán)中，依次掃描每個(gè)點(diǎn)的互近鄰并進(jìn)行判斷，由于每個(gè)點(diǎn)的互近鄰個(gè)數(shù)不盡相等且遠(yuǎn)小于n，因此時(shí)間復(fù)雜度為O(mn)，m為所有互近鄰的平均數(shù)且m≤k?n，從而此階段的時(shí)間復(fù)雜度接近O(n)。第三階段，合并具有相同點(diǎn)的初始簇平均時(shí)間復(fù)雜度為O(nlbn)。因此，最后整個(gè)算法的時(shí)間復(fù)雜度計(jì)算為O(nlbn)。

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

為了評(píng)估算法性能，將本文提出的算法與六種對(duì)比算法分別在六個(gè)數(shù)據(jù)集上進(jìn)行測(cè)試。其中，k-means（http://scikit-learn.org/stable/）、DBSCAN（http://scikitlearn.org/stable/）和 OPTICS（https://github.com/）是三種經(jīng)典算法；BOOL（binary coding oriented clustering）[16]、CLASP（towards effective and efficient mining of arbitrary shaped clusters）[17]和 CFDP（clustering by fast search and find of density peaks）[18]是三種新算法，代碼均由其作者提供。六個(gè)數(shù)據(jù)集分別為：三個(gè)二維數(shù)據(jù)集（Aggregation、Spiral、R15，https://cs.joensuu.fi/sipu/datasets/）和三個(gè)多維數(shù)據(jù)集（Ecoli、Glass、Iris，http://archive.ics.uci.edu/ml/datasets.html）。

同時(shí)使用ARI（adjusted rand index）和NMI（normalized mutual information）作為算法的評(píng)價(jià)指標(biāo)。它們的取值越大代表結(jié)果越接近真實(shí)情況。其中，用作比較的結(jié)果都是算法在數(shù)據(jù)集上的最優(yōu)取值，輸入?yún)?shù)通過迭代調(diào)整得到，具體分析如下。

3.1 對(duì)比算法分析

六種對(duì)比算法中的三種經(jīng)典算法已在引言中做過介紹，本節(jié)將對(duì)BOOL、CLASP和CFDP三種新算法進(jìn)行分析。

BOOL是一個(gè)多變量數(shù)據(jù)聚類算法。它首先將所有數(shù)據(jù)點(diǎn)離散化，并用二進(jìn)制數(shù)字表示；然后使用定義的函數(shù)迭代地將所有的小簇合并，形成最終簇。盡管該算法對(duì)參數(shù)不敏感，且比一些算法更快，但在一些數(shù)據(jù)集上仍不能獲得正確劃分。

CLASP首先通過刪除異常值來自動(dòng)縮小數(shù)據(jù)集的大小，使用k-means算法找到代表點(diǎn)來有效保持簇的形狀信息。然后，調(diào)整代表點(diǎn)的位置以提高它們的內(nèi)在關(guān)系，使得每個(gè)代表點(diǎn)更接近其鄰居同時(shí)遠(yuǎn)離其他點(diǎn)。最后它在基于互k-近鄰相似性度量下執(zhí)行凝聚聚類來識(shí)別簇結(jié)構(gòu)。不過，運(yùn)行時(shí)需要過多的參數(shù)，而這些參數(shù)都不太容易確定[3]。

CFDP的核心思想在于聚類中心的刻畫，聚類中心同時(shí)具有以下特點(diǎn)：簇中心的密度大，由一些局部密度比較低的點(diǎn)圍繞，并且這些點(diǎn)距離其他高局部密度點(diǎn)的距離比較大。該算法使得簇的數(shù)量直觀出現(xiàn)，離群值不論形狀和維度被自動(dòng)發(fā)現(xiàn)。然而，需要計(jì)算所有的點(diǎn)與點(diǎn)之間的距離，如果樣本太大，整個(gè)距離矩陣的內(nèi)存開銷特別大。

3.2 算法難點(diǎn)與創(chuàng)新點(diǎn)分析

本文算法特點(diǎn)在于通過將數(shù)據(jù)點(diǎn)分配給距離其最近且密度比它大的互近鄰點(diǎn)來形成初始簇，從而可以自動(dòng)識(shí)別數(shù)據(jù)集中任意簇。在對(duì)比算法中，kmeans將事先隨機(jī)確定的每個(gè)簇中心點(diǎn)看作為初始簇，然后就近分配其他點(diǎn)，導(dǎo)致算法對(duì)初始簇具有一定的依賴性；CLASP同樣采用k-means找到簇中心并不斷調(diào)整形成初始簇，使得其最終簇與初始簇的形成緊密相關(guān)；BOOL則通過將數(shù)據(jù)點(diǎn)離散化后用二進(jìn)制數(shù)字表示來形成初始簇，使得空間相對(duì)位置較近的數(shù)據(jù)點(diǎn)聚在一起。由于本文算法是根據(jù)數(shù)據(jù)點(diǎn)密度將每個(gè)點(diǎn)分配給其最緊密的互近鄰點(diǎn)形成初始簇，從而總是將關(guān)系最近的數(shù)據(jù)點(diǎn)聚在一起，使得算法整個(gè)過程對(duì)初始簇的形成沒有依賴性。

3.3 二維數(shù)據(jù)集實(shí)驗(yàn)分析

表1描述了本文算法與六種對(duì)比算法在二維數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，其中包含了算法最優(yōu)結(jié)果的參數(shù)值、ARI和NMI值。參數(shù)中k為最近鄰居的個(gè)數(shù)，m為簇的數(shù)目。DBSCAN的兩個(gè)參數(shù)分別表示鄰居半徑和最小鄰居數(shù)；BOOL的三個(gè)參數(shù)分別為簇個(gè)數(shù)的下界、距離參數(shù)、異常點(diǎn)參數(shù)；CLASP的五個(gè)參數(shù)分別表示簇個(gè)數(shù)、最近鄰居數(shù)、數(shù)據(jù)集尺寸的調(diào)整參數(shù)、降維標(biāo)志和迭代最大次數(shù)。從表中清楚地看出，本文算法聚類結(jié)果與CFDP一樣優(yōu)于其他算法，評(píng)價(jià)指標(biāo)值高達(dá)0.99以上，更符合真實(shí)情況。

3.3.1 Aggregation數(shù)據(jù)集上的實(shí)驗(yàn)分析

圖1展示了本文算法與六種對(duì)比算法在Aggregation數(shù)據(jù)集上的結(jié)果。此數(shù)據(jù)集的特征是簇內(nèi)密度比較均勻，簇間密度差異不大，且簇的形狀是任意的。其中圖1（a）是Aggregation的真實(shí)情況，圖1（b）～圖1（h）是各種算法的聚類結(jié)果。

顯然地，CFDP可以正確地識(shí)別出整個(gè)數(shù)據(jù)集的真實(shí)簇。其次，本文算法通過使用數(shù)據(jù)點(diǎn)間密度關(guān)系在互近鄰中聚類使得相同簇中的點(diǎn)相互吸引，不同簇中的點(diǎn)自然分開，從而能夠發(fā)現(xiàn)任意形狀的簇，與真實(shí)結(jié)果最接近，僅僅相差三個(gè)點(diǎn)。k-means由于受初始簇中心的影響，導(dǎo)致最終的數(shù)據(jù)結(jié)構(gòu)被硬性分成七個(gè)簇，每個(gè)簇都是圍繞其中心點(diǎn)的一個(gè)球狀簇，從而沒能將該數(shù)據(jù)集的特征很好地體現(xiàn)出來。同理CLASP對(duì)最終的識(shí)別也不是很好。DBSCAN由于受密度參數(shù)影響，一部分簇邊緣的點(diǎn)被錯(cuò)誤劃分。作為DBSCAN的優(yōu)化算法，OPTICS結(jié)果有所改善，但仍有少數(shù)點(diǎn)無法被正確識(shí)別。同樣地，BOOL則將同一個(gè)簇中的部分點(diǎn)視為異常點(diǎn)，最終導(dǎo)致劃分不夠精確。

Table 1 Comparison results on 2-dimensional data sets表1 二維數(shù)據(jù)集上的對(duì)比結(jié)果

Fig.1 Comparison results on data setAggregation圖1 Aggregation數(shù)據(jù)集上的比對(duì)結(jié)果圖

3.3.2 Spiral數(shù)據(jù)集上的實(shí)驗(yàn)分析

圖2展示了數(shù)據(jù)集Spiral上本文算法與六種對(duì)比算法的聚類結(jié)果。此數(shù)據(jù)集的形狀是螺旋型，且每個(gè)簇內(nèi)數(shù)據(jù)點(diǎn)的密度由里到外逐漸變小，簇間距離相似。其中圖2（a）是 Spiral的真實(shí)情況，圖2（b）～圖2（h）是各種算法的最優(yōu)結(jié)果。

Fig.2 Comparison results on data set Spiral圖2 Spiral數(shù)據(jù)集上的比對(duì)結(jié)果圖

從圖2可以清楚地看出，本文算法的聚類結(jié)果與DBSCAN和CFDP一樣完全符合數(shù)據(jù)集真實(shí)情況。算法同時(shí)考慮密度與距離，使得數(shù)據(jù)集中各個(gè)簇自動(dòng)發(fā)現(xiàn)，然后通過相同點(diǎn)串聯(lián)的方式實(shí)現(xiàn)數(shù)據(jù)集的真實(shí)劃分。除此之外，其他算法聚類結(jié)果均不是很理想。k-means和CLASP一樣，受初始簇中心選取的影響，沒有考慮到密度，只是將整個(gè)數(shù)據(jù)集平均分成了三部分，導(dǎo)致大部分點(diǎn)被錯(cuò)誤劃分。OPTICS由于受密度差異影響，密度較大的點(diǎn)實(shí)現(xiàn)了正確劃分，而其他密度較小的點(diǎn)均被視為異常點(diǎn)。最后，BOOL則根據(jù)數(shù)據(jù)點(diǎn)的位置將整個(gè)數(shù)據(jù)集劃分成多個(gè)不同的小簇，合并后仍沒有很好地將真實(shí)簇識(shí)別出。

3.3.3 R15數(shù)據(jù)集上的實(shí)驗(yàn)分析

圖3顯示了本文算法與六種對(duì)比算法在數(shù)據(jù)集R15上的聚類結(jié)果。該數(shù)據(jù)集的特點(diǎn)是每個(gè)簇內(nèi)密度不均勻，簇間距離各有不同，且均為球狀簇。其中圖3（a）是R15的真實(shí)情況，圖3（b）～圖3（h）是各種算法的最優(yōu)結(jié)果。

不難看出，本文算法與k-means、CFDP一樣可以發(fā)現(xiàn)數(shù)據(jù)集的真實(shí)結(jié)構(gòu)，性能優(yōu)于其他幾種對(duì)比算法。通過對(duì)密度和距離的雙重考慮，本文算法不僅可以很好地發(fā)現(xiàn)任意形狀簇，還可以發(fā)現(xiàn)球狀簇。其次，DBSCAN受簇內(nèi)密度差異影響，將每個(gè)簇中密度較小的點(diǎn)劃分為同一個(gè)簇，導(dǎo)致簇中部分點(diǎn)被錯(cuò)誤劃分。相似地，OPTICS則將同一個(gè)簇中密度相對(duì)較小的點(diǎn)錯(cuò)誤地識(shí)別為異常點(diǎn)。同樣，BOOL和CLASP也沒能很好地檢測(cè)出真實(shí)簇。

Fig.3 Comparison results on data set R15圖3 R15數(shù)據(jù)集上的比對(duì)結(jié)果圖

Table 2 Comparison results on multi-dimensional data sets表2 多維數(shù)據(jù)集上的對(duì)比結(jié)果

3.4 多維數(shù)據(jù)集實(shí)驗(yàn)分析

表2描述了本文算法與六種對(duì)比算法在數(shù)據(jù)集Ecoli、Glass和Iris上的聚類結(jié)果。Ecoli數(shù)據(jù)集用于預(yù)測(cè)細(xì)胞蛋白質(zhì)定位位點(diǎn)，七個(gè)屬性分別為Mc-Geoch信號(hào)序列識(shí)別方法、von Heijne信號(hào)序列識(shí)別方法、von Heijne信號(hào)肽酶II共有序列評(píng)分、預(yù)測(cè)的脂蛋白的N-末端存在電荷、外膜和周質(zhì)蛋白的氨基酸含量的判別分析得分、ALOM膜跨越區(qū)域預(yù)測(cè)程序的評(píng)分和從序列中排除可能的可切割信號(hào)區(qū)域之后的ALOM程序得分。Glass是對(duì)玻璃種類進(jìn)行分類的數(shù)據(jù)集，九個(gè)屬性包括折射率、鈉、鎂、鋁、硅、鉀、鈣、鋇和鐵含量。Iris描述了鳶尾植物類，四個(gè)屬性分別為：萼片長度、萼片寬度、花瓣長度和花瓣寬度。明顯地，在二維數(shù)據(jù)集上CFDP的聚類性能與本文算法相當(dāng)，在多維數(shù)據(jù)集上，本文算法的聚類結(jié)果評(píng)價(jià)指標(biāo)均高于其他算法，說明其能更好地發(fā)現(xiàn)數(shù)據(jù)集中真實(shí)情況。

最后，將七種算法在六個(gè)數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)結(jié)果值用箱線圖直觀地表示，如圖4、圖5所示。二者分別描述了每種算法的六個(gè)ARI和NNI統(tǒng)計(jì)值的對(duì)比情況。其中，每個(gè)箱形有以下特征，分別為：箱體上下邊界位置對(duì)應(yīng)數(shù)據(jù)的上下四分位數(shù)（Q3和Q1）；箱內(nèi)的虛線段為中位線位置，表示六個(gè)指標(biāo)值的中位數(shù)；箱體最上方和最下方的實(shí)線稱為內(nèi)限，分別表示數(shù)據(jù)的最大和最小非異常值；+表示異常值。

從圖4、圖5可以看出，本文算法對(duì)應(yīng)的箱線圖中各條線段所處位置（包含異常點(diǎn)）幾乎都高于其他算法對(duì)應(yīng)的箱線圖，說明該算法的聚類性能優(yōu)于其他對(duì)比算法。綜上所述，新算法采用互近鄰的方法使關(guān)系緊湊的點(diǎn)聚集到一起，同時(shí)使用密度引力的思想在不論維度和形狀的情況下自動(dòng)發(fā)現(xiàn)任意簇，算法整體具有魯棒性。

Fig.4 ARI comparison result of 7 kinds of algorithms圖4 7種算法聚類ARI值的對(duì)比圖

4 結(jié)束語

Fig.5 NMI comparison result of 7 kinds of algorithms圖5 7種算法聚類NMI值的對(duì)比圖

為了解決聚類中精確性不高、執(zhí)行效率低等問題，本文提出了一個(gè)基于數(shù)據(jù)點(diǎn)的密度引力聚類算法。該算法根據(jù)數(shù)據(jù)點(diǎn)的分布情況定義了密度引力的概念，通過密度引力使得自動(dòng)發(fā)現(xiàn)數(shù)據(jù)集中真實(shí)簇。為驗(yàn)證算法的高效性，使用六種先進(jìn)算法在六種不同維度和類型的數(shù)據(jù)集上與新算法進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果發(fā)現(xiàn)本文提出的新算法在性能上優(yōu)于其他算法。在未來的研究中，擬嘗試研究出更多高效的算法以便于聚類分析。