孫 璐，梁永全

山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590

近年來(lái)，信息技術(shù)的快速發(fā)展使得可用數(shù)據(jù)爆炸式增長(zhǎng)，數(shù)據(jù)分析在現(xiàn)實(shí)生活場(chǎng)景中的應(yīng)用范圍不斷被拓展，這對(duì)數(shù)據(jù)分析技術(shù)的精度和效率都提出了更高的要求，如何對(duì)大規(guī)模數(shù)據(jù)集進(jìn)行快速、有效的分析和處理變得越來(lái)越重要。聚類(lèi)是一種重要的數(shù)據(jù)分析技術(shù)，是最早研究空間數(shù)據(jù)集中數(shù)據(jù)結(jié)構(gòu)和模式的數(shù)據(jù)挖掘技術(shù)之一[1-2]，在圖像分析[3]、模式識(shí)別[4]、知識(shí)發(fā)現(xiàn)[5]和生物信息學(xué)[6]等多個(gè)學(xué)科領(lǐng)域具有一定的應(yīng)用價(jià)值。隨著國(guó)內(nèi)外研究人員對(duì)聚類(lèi)算法研究的不斷深入，產(chǎn)生了許多優(yōu)秀的算法。根據(jù)算法實(shí)現(xiàn)原理和探究方向不同，目前五種主流的聚類(lèi)算法為基于劃分的方法、基于密度的方法、基于層次的方法、基于網(wǎng)格的方法和基于模型的方法[7]。

DBSCAN是最經(jīng)典的基于密度的聚類(lèi)算法之一，其根據(jù)數(shù)據(jù)集的空間分布密度對(duì)樣本點(diǎn)進(jìn)行聚類(lèi)，可以在有噪聲的數(shù)據(jù)中發(fā)現(xiàn)任意形狀的類(lèi)簇[8-9]，在真實(shí)應(yīng)用場(chǎng)景中處理復(fù)雜數(shù)據(jù)時(shí)算法性能優(yōu)越，得到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。然而，DBSCAN算法也存在一些缺陷：（1）采用全局參數(shù)導(dǎo)致其在密度不均勻數(shù)據(jù)集中的聚類(lèi)質(zhì)量不高；（2）采用暴力破解法為每個(gè)樣本點(diǎn)計(jì)算鄰域密度，計(jì)算復(fù)雜度較高[10]，傳統(tǒng)DBSCAN算法在最差情況下的時(shí)間復(fù)雜度為O(n2)，在運(yùn)行時(shí)間為O(nlogn)時(shí)，隨著數(shù)據(jù)集的維度或者規(guī)模的增加，平方級(jí)的時(shí)間開(kāi)銷(xiāo)逐漸顯現(xiàn)[11]，這極大地限制了其在大規(guī)模數(shù)據(jù)集中的應(yīng)用。近年來(lái)，很多學(xué)者從不同角度針對(duì)這些問(wèn)題做出了改進(jìn)。文獻(xiàn)[12]通過(guò)確定密度峰值點(diǎn)來(lái)自適應(yīng)地選擇聚類(lèi)的局部半徑，并據(jù)此擴(kuò)展密度峰值點(diǎn)進(jìn)行聚類(lèi)，提高了聚類(lèi)結(jié)果的質(zhì)量。文獻(xiàn)[13]通過(guò)貪心策略自適應(yīng)確定局部最優(yōu)鄰域半徑，并通過(guò)比較鄰域內(nèi)點(diǎn)之間的平均距離與半徑參數(shù)發(fā)現(xiàn)噪聲，提升聚類(lèi)精度。文獻(xiàn)[14-15]通過(guò)減少為數(shù)據(jù)集中每個(gè)點(diǎn)計(jì)算鄰域密度時(shí)的冗余計(jì)算量，提高算法執(zhí)行速度。文獻(xiàn)[16-17]通過(guò)選擇幾個(gè)代表性的核心點(diǎn)作為種子來(lái)擴(kuò)展類(lèi)的方式，減少重復(fù)的鄰域檢索，加快聚類(lèi)。文獻(xiàn)[18-20]利用圖形處理單元（GPU）、空間分區(qū)數(shù)據(jù)結(jié)構(gòu)（如R樹(shù)和KD樹(shù)）或并行算法提出了基于密度的快速、可擴(kuò)展的聚類(lèi)方法，用于處理大型數(shù)據(jù)集。這些方法都在一定程度上提升了DBSCAN算法的性能，降低了算法的時(shí)間復(fù)雜度，但是這些方法大多無(wú)法較好地兼顧時(shí)間開(kāi)銷(xiāo)與算法性能。

DBSCAN算法中存在大量無(wú)用的距離計(jì)算，可以通過(guò)減少這些無(wú)用計(jì)算來(lái)降低算法的時(shí)間復(fù)雜度。基于此，本文提出了一種網(wǎng)格聚類(lèi)與DBSCAN相結(jié)合的融合聚類(lèi)算法（G_FDBSCAN），使用網(wǎng)格劃分技術(shù)將數(shù)據(jù)集劃分為密集區(qū)域和稀疏區(qū)域，分而治之，既緩解了全局參數(shù)導(dǎo)致DBSCAN算法在密度不均勻數(shù)據(jù)集上的聚類(lèi)精度不佳問(wèn)題，又顯著降低了算法的時(shí)間復(fù)雜度，同時(shí)還可以在一定程度上解決網(wǎng)格聚類(lèi)受網(wǎng)格劃分參數(shù)影響較大，只能發(fā)現(xiàn)邊界是水平或垂直的簇而不能檢測(cè)到斜邊界的問(wèn)題。

1快速DBSCAN算法（fast DBSCAN，F(xiàn)DBSCAN）

1.1傳統(tǒng)DBSCAN聚類(lèi)算法

傳統(tǒng)DBSCAN算法將簇定義為由非密集區(qū)域間隔開(kāi)的密集區(qū)域的集合。如果用歐幾里德距離作為相似性度量，這些密集區(qū)域是以給定點(diǎn)p為中心以ε為半徑的超球體。假設(shè)有n個(gè)d維F分布的i.i.d.樣本點(diǎn)的集合X={x1,x2,…,xn}。根據(jù)DBSCAN的兩個(gè)超參數(shù)：核心點(diǎn)的鄰域半徑ε和密度閾值δ，給出DBSCAN的一些相關(guān)定義。

定義1（ε-鄰域）對(duì)于樣本點(diǎn)p∈X，其ε-鄰域是樣本集X中與p的距離不大于ε的樣本點(diǎn)集合，即Nε(p)={q∈X:|p-q|≤ε}。

定義2（核心點(diǎn)）對(duì)于任意樣本點(diǎn)p∈X，若p的ε-鄰域中至少包含δ個(gè)樣本點(diǎn)，即若|Nε(p)?X|≥δ，則p是一個(gè)核心點(diǎn)。

定義3（邊界點(diǎn)）對(duì)于任意樣本點(diǎn)p∈X，若p的ε-鄰域中包含小于δ個(gè)樣本點(diǎn)，即若|Nε(p)?X|＜δ，則p是一個(gè)邊界點(diǎn)。

定義4（噪聲點(diǎn)）噪聲點(diǎn)是在其ε鄰域內(nèi)點(diǎn)的個(gè)數(shù)少于δ且鄰域內(nèi)的點(diǎn)均為邊界點(diǎn)的點(diǎn)。

定義5（密度直達(dá)）如果p位于q的ε-鄰域中，且q是核心點(diǎn)，則稱(chēng)p由q密度直達(dá)。

定義6（密度可達(dá)）如果存在一個(gè)樣本點(diǎn)鏈p1,p2,…,pi,pi+1,…,pn滿(mǎn)足p1=p和pn=q,pi是由pi+1關(guān)于ε和δ密度直達(dá)的，則點(diǎn)p是由點(diǎn)q關(guān)于ε和δ密度可達(dá)的。

定義7（密度相連）對(duì)于p和q，如果存在核心點(diǎn)h，使p和q均由h密度可達(dá)，則稱(chēng)p和q密度相連。

在DBSCAN中簇的定義是從一個(gè)核心點(diǎn)出發(fā)由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連點(diǎn)的集合，即為最終聚類(lèi)的一個(gè)簇。

1.2快速DBSCAN算法

將兩組點(diǎn)集S1和S2之間的距離定義為d(S1,S2)=min{d(p,q)|p∈S1,q∈S2}。如果兩個(gè)點(diǎn)集之間的距離大于ε，則兩個(gè)點(diǎn)集中的點(diǎn)一定屬于不同的類(lèi)。傳統(tǒng)DBSCAN算法中假設(shè)同一個(gè)核心點(diǎn)鄰域內(nèi)的點(diǎn)屬于同一類(lèi)。據(jù)此，本文對(duì)傳統(tǒng)的DBSCAN算法進(jìn)行了改進(jìn)，提出了一種DBSCAN的改進(jìn)算法——快速DBSCAN算法（FDBSCAN）。該算法以子類(lèi)簇間交疊部分存在核心點(diǎn)為類(lèi)簇合并依據(jù)，基于此擴(kuò)展類(lèi)簇完成聚類(lèi)，避免了類(lèi)簇?cái)U(kuò)展過(guò)程中鄰域的冗余檢索，從而加快聚類(lèi)速度。具體算法步驟如下：

FDBSCAN算法步驟如下：

輸入：數(shù)據(jù)集X={x1,x2,…,xn}，半徑參數(shù)ε，鄰域密度閾值δ

輸出：樣本點(diǎn)類(lèi)標(biāo)簽

步驟1根據(jù)給定超參數(shù)ε和δ，求出數(shù)據(jù)集X中的核心點(diǎn)，并將這些核心點(diǎn)按密度大小降序排序后存入集合S。

步驟2每次選擇S中當(dāng)前的第一個(gè)點(diǎn)p（即為當(dāng)前密度最大的核心點(diǎn)），為p創(chuàng)建一個(gè)新的類(lèi)簇C，然后將p從S中刪除；對(duì)于p的ε鄰域內(nèi)已有類(lèi)標(biāo)號(hào)的點(diǎn)，將X中與該點(diǎn)類(lèi)別相同的點(diǎn)全部標(biāo)記類(lèi)別C；將p的ε鄰域內(nèi)其余點(diǎn)的類(lèi)標(biāo)號(hào)記為C；將p的ε鄰域內(nèi)的核心點(diǎn)從S中刪除。

步驟3將數(shù)據(jù)集X中剩余點(diǎn)聚類(lèi)至鄰域內(nèi)最近的核心點(diǎn)所在類(lèi)；鄰域內(nèi)無(wú)核心點(diǎn)的標(biāo)記為噪聲點(diǎn)。

2 融合網(wǎng)格劃分與FDBSCAN的改進(jìn)聚類(lèi)算法（fusion of grid partition and FDBSCAN clustering algorithm，G_FDBSCAN）

2.1 改進(jìn)的網(wǎng)格聚類(lèi)算法

基于網(wǎng)格的聚類(lèi)采用空間驅(qū)動(dòng)的方法，把嵌入空間劃分成獨(dú)立于輸入對(duì)象分布的單元[21]。該方法使用一種多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，將數(shù)據(jù)空間量化成有限數(shù)目的互不相交的網(wǎng)格單元，根據(jù)密度閾值將網(wǎng)格識(shí)別為高、低密度網(wǎng)格，將相連的高密度網(wǎng)格識(shí)別為簇。聚類(lèi)質(zhì)量取決于網(wǎng)格單元的劃分粒度，如果劃分粒度很細(xì)，則網(wǎng)格單元的數(shù)量會(huì)顯著增加，從而使處理代價(jià)顯著增加；如果劃分粒度太粗，則屬于不同類(lèi)中的對(duì)象被劃分到同一網(wǎng)格中概率會(huì)顯著增加，從而降低聚類(lèi)精度。這種方法具有線(xiàn)性的時(shí)間復(fù)雜度，對(duì)大規(guī)模數(shù)據(jù)集有很好的擴(kuò)展性，但是，以網(wǎng)格取代數(shù)據(jù)點(diǎn)作為聚類(lèi)基本單元，丟失了大部分點(diǎn)的信息，導(dǎo)致聚類(lèi)質(zhì)量下降。

有許多經(jīng)典的基于網(wǎng)格的聚類(lèi)算法。本文選擇了基于網(wǎng)格和密度相結(jié)合的CLIQUE聚類(lèi)算法。根據(jù)后面與DBSCAN算法融合的需要，對(duì)CLIQUE算法進(jìn)行改進(jìn)，提出一種改進(jìn)的CLIQUE算法。下面根據(jù)兩個(gè)超參數(shù)：網(wǎng)格寬度ε和密度閾值δ，給出網(wǎng)格聚類(lèi)的一些相關(guān)定義。

定義8（網(wǎng)格單元）給定一個(gè)d維的數(shù)據(jù)集X，其屬性(A1,A2,…,Ad)都是有界的，將d維數(shù)據(jù)空間的每一維劃分成長(zhǎng)度為ε的等長(zhǎng)區(qū)間段，這樣d個(gè)來(lái)自不同維度的區(qū)間段相交成一個(gè)（超）矩形，即為網(wǎng)格單元。

定義9（相鄰網(wǎng)格）相鄰網(wǎng)格是指有共同邊的網(wǎng)格單元。

定義10（網(wǎng)格單元密度）網(wǎng)格單元u中數(shù)據(jù)點(diǎn)的個(gè)數(shù)稱(chēng)為該網(wǎng)格單元的密度，記作N(u)。

定義11（稠密網(wǎng)格）給定一個(gè)網(wǎng)格單元u,若N(u)≥δ,則u為稠密網(wǎng)格。

定義12（稀疏網(wǎng)格）給定一個(gè)網(wǎng)格單元u,若N(u)＜δ,則u為稀疏網(wǎng)格。

改進(jìn)的CLIQUE算法步驟如下：

輸入：數(shù)據(jù)集X={x1,x2,…,xn}，網(wǎng)格寬度ε，密度閾值δ

輸出：樣本點(diǎn)類(lèi)標(biāo)簽

步驟1根據(jù)給定超參數(shù)ε和δ，將數(shù)據(jù)集X中的點(diǎn)映射到網(wǎng)格中，將所有網(wǎng)格劃分為稠密網(wǎng)格和稀疏網(wǎng)格。

步驟2將相鄰的稠密網(wǎng)格連接成簇；將稀疏網(wǎng)格中的點(diǎn)標(biāo)記為噪聲點(diǎn)。

2.2 G_FDBSCAN算法

通過(guò)結(jié)合網(wǎng)格劃分方法，并改進(jìn)原DBSCAN算法的執(zhí)行步驟（FDBSCAN算法），提出了一種精確高效的聚類(lèi)算法G_FDBSCAN算法。采用基于網(wǎng)格的聚類(lèi)算法作為數(shù)據(jù)集分布度量，給出數(shù)據(jù)集密度分布特征，分而治之，從而在一定程度上避免DBSCAN采用全局參數(shù)引起的誤差；僅對(duì)稀疏區(qū)域的點(diǎn)運(yùn)用FDBSCAN聚類(lèi)，將使用FDBSCAN聚類(lèi)的對(duì)象數(shù)控制在平方的時(shí)間復(fù)雜度到達(dá)之前的數(shù)量級(jí)范圍內(nèi)，也可以在一定程度避免基于網(wǎng)格的聚類(lèi)算法采用硬網(wǎng)格劃分技術(shù)破壞聚類(lèi)邊緣造成的聚類(lèi)精度差的問(wèn)題。通過(guò)改進(jìn)，在優(yōu)化傳統(tǒng)DBSCAN算法聚類(lèi)結(jié)果的同時(shí)，大大降低了算法的時(shí)間復(fù)雜度。

采用網(wǎng)格劃分技術(shù)將數(shù)據(jù)空間劃分為多個(gè)網(wǎng)格單元，稠密網(wǎng)格所在區(qū)域稱(chēng)為密集區(qū)域，稀疏網(wǎng)格所在區(qū)域稱(chēng)為稀疏區(qū)域，分而治之。首先，對(duì)密集區(qū)域內(nèi)的點(diǎn)進(jìn)行預(yù)聚類(lèi)，這些點(diǎn)位于類(lèi)簇中心區(qū)域，通過(guò)合理調(diào)整用戶(hù)參數(shù)，基本可以保證同一網(wǎng)格單元中的數(shù)據(jù)點(diǎn)屬于同一類(lèi)簇，數(shù)量大且易于識(shí)別。應(yīng)用基于網(wǎng)格的聚類(lèi)算法，可以快速、準(zhǔn)確地獲得初始聚類(lèi)結(jié)果。稀疏區(qū)域中的點(diǎn)通常位于類(lèi)簇的邊緣區(qū)域，且其中可能存在噪聲容易被誤分類(lèi)，數(shù)據(jù)量遠(yuǎn)少于密集區(qū)域，聚類(lèi)難度較大。因此，針對(duì)稀疏區(qū)域的點(diǎn)，本文在現(xiàn)有網(wǎng)格劃分的基礎(chǔ)上，采用本文提出的FDBSCAN算法進(jìn)行處理。

G_FDBSCAN算法步驟如下，流程圖如圖1所示。

輸入：數(shù)據(jù)集X={x1,x2,…,xn}，半徑參數(shù)ε，鄰域密度閾值δ

輸出：樣本點(diǎn)類(lèi)標(biāo)簽

步驟1根據(jù)給定的半徑參數(shù)ε和鄰域密度閾值δ，利用網(wǎng)格劃分技術(shù)將數(shù)據(jù)集劃分為密集網(wǎng)格和稀疏網(wǎng)格。

步驟2對(duì)密集網(wǎng)格所在區(qū)域的點(diǎn)利用改進(jìn)的CLIQUE算法進(jìn)行預(yù)聚類(lèi)。

步驟3將密集區(qū)域中網(wǎng)格聚類(lèi)得到的每一個(gè)子類(lèi)作為一個(gè)整體與網(wǎng)格聚類(lèi)后剩余未聚類(lèi)的點(diǎn)一起運(yùn)用基于網(wǎng)格劃分的FDBSCAN算法（確定核心點(diǎn)的鄰域檢索只在相鄰網(wǎng)格范圍內(nèi)執(zhí)行）進(jìn)行聚類(lèi)，同時(shí)識(shí)別噪聲點(diǎn)，得到最終的聚類(lèi)結(jié)果。

2.3 G_FDBSCAN的時(shí)間復(fù)雜度

該算法的時(shí)間復(fù)雜度為O(n)。假設(shè)n是數(shù)據(jù)集中點(diǎn)的數(shù)量，該算法的時(shí)間復(fù)雜度主要由兩部分決定：（1）網(wǎng)格聚類(lèi)，時(shí)間復(fù)雜度O(n)。此部分的時(shí)間復(fù)雜度由兩部分組成：①劃分?jǐn)?shù)據(jù)空間，將每個(gè)數(shù)據(jù)點(diǎn)映射到網(wǎng)格單元中需要線(xiàn)性時(shí)間復(fù)雜度O(n)；②篩選出高密度網(wǎng)格需要O(u)，u是網(wǎng)格單元數(shù)，u?n。（2）FDBSCAN聚類(lèi)，即對(duì)網(wǎng)格聚類(lèi)后剩余未聚類(lèi)的點(diǎn)的聚類(lèi)，時(shí)間復(fù)雜度O(ml)。此部分的時(shí)間復(fù)雜度由兩部分組成：①計(jì)算核心點(diǎn)，鄰域檢索只在相鄰網(wǎng)格范圍內(nèi)執(zhí)行，時(shí)間復(fù)雜度為O(ml)，m是網(wǎng)格聚類(lèi)后剩余未聚類(lèi)的點(diǎn)的總數(shù)，m?n；l是近鄰網(wǎng)格中的點(diǎn)數(shù)，l?m。②掃描剩余的未聚類(lèi)點(diǎn)就近歸類(lèi)，該部分的點(diǎn)數(shù)量很少，且基本都是位于類(lèi)簇邊界上，每個(gè)點(diǎn)就近歸類(lèi)時(shí)執(zhí)行鄰域檢索所需掃描的點(diǎn)也很少，因此這部分的時(shí)間復(fù)雜度可以忽略不計(jì)。

綜上所述，G_FDBSCAN算法的時(shí)間復(fù)雜度為O(n)+O(ml)=O(n)。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)集及設(shè)置

通過(guò)在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)來(lái)綜合評(píng)估分析G_FDBSCAN算法的聚類(lèi)效果和效率。人工數(shù)據(jù)集選取了5個(gè)不同形狀、大小和密度的有一定結(jié)構(gòu)復(fù)雜度的數(shù)據(jù)集（表1）。真實(shí)數(shù)據(jù)集選了7個(gè)不同大小、維度和類(lèi)別數(shù)目的UCI（http：//archive.ics.uci.edu/ml/datasets.php）數(shù)據(jù)集（表2）。對(duì)比算法包括BIRCH算法、KMEANS算法、DPC算法、CBSCAN算法[14]以及傳統(tǒng)DBSCAN算法。

表1 人工數(shù)據(jù)集Table 1 Artificial datasets

本文通過(guò)兩種常用的聚類(lèi)評(píng)估指標(biāo)對(duì)算法的性能進(jìn)行評(píng)價(jià)：調(diào)整蘭德系數(shù)[22（]adjusted Rand Index，ARI）和調(diào)整互信息[23（]adjusted mutual information，AMI），兩種指標(biāo)的取值范圍為[-1,1]，取值越大表示聚類(lèi)結(jié)果和真實(shí)情況越吻合。實(shí)驗(yàn)基礎(chǔ)環(huán)境為Intel?CoreTMi5-7500 CPU@3.40 GHz，8 GB內(nèi)存，Windows10操作系統(tǒng)和anaconda3 Python。

表2 真實(shí)數(shù)據(jù)集Table 2 Real datasets

3.2 超參數(shù)對(duì)算法性能的影響

本節(jié)在impossible數(shù)據(jù)集和pendigits數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，運(yùn)用控制變量法，分別將超參數(shù)ε和δ固定為最佳調(diào)整值，改變另一個(gè)參數(shù)的取值，來(lái)測(cè)試和評(píng)估這兩個(gè)參數(shù)對(duì)新算法性能的影響。

每個(gè)超參數(shù)對(duì)算法評(píng)分的影響情況如圖2。可以看出，ε和δ值的變化都會(huì)引起算法評(píng)分的波動(dòng)，在兩個(gè)數(shù)據(jù)集的最佳參數(shù)附近（impossible數(shù)據(jù)集：ε=1.0，δ=20；pendigits數(shù)據(jù)集：ε=42，δ=10），算法評(píng)分隨ε值變化而產(chǎn)生的波動(dòng)較大，隨δ值變化而產(chǎn)生的波動(dòng)較小。這是因?yàn)?，ε的大小決定了每個(gè)數(shù)據(jù)點(diǎn)在網(wǎng)格劃分中的區(qū)域定位，從而決定了數(shù)據(jù)對(duì)象在網(wǎng)格空間的整體布局，而δ的大小僅決定一個(gè)網(wǎng)格是否是高密度網(wǎng)格。因此，G_FDBSCAN算法評(píng)分對(duì)ε更為敏感。

圖3展示了算法運(yùn)行時(shí)間對(duì)兩個(gè)超參數(shù)的敏感性?？梢钥闯靓藕挺亩紩?huì)影響算法的運(yùn)行時(shí)間，但是運(yùn)行時(shí)間對(duì)兩個(gè)超參數(shù)的敏感性沒(méi)有明顯的偏向。原因是，G_FDBSCAN的運(yùn)行時(shí)間主要受測(cè)試數(shù)據(jù)集中使用網(wǎng)格聚類(lèi)的點(diǎn)的數(shù)量的影響。使用網(wǎng)格聚類(lèi)的點(diǎn)越多，則使用FDBSCAN的點(diǎn)越少，時(shí)間效率就越高。因此，這一過(guò)程受到ε和δ的聯(lián)合作用的影響。

3.3 復(fù)雜數(shù)據(jù)集中應(yīng)用的魯棒性

對(duì)表1所給出的人工數(shù)據(jù)集，使用5種聚類(lèi)算法進(jìn)行實(shí)驗(yàn)，這5個(gè)數(shù)據(jù)集的類(lèi)簇分布情況和聚類(lèi)的數(shù)目是截然不同的，它們可以更直觀地反映出5種聚類(lèi)算法的魯棒性。聚類(lèi)結(jié)果可視化描述如圖4～圖8所示，圖中不同顏色（形狀）的數(shù)據(jù)點(diǎn)代表不同類(lèi)別。

圖2 算法評(píng)分對(duì)ε/δ敏感性分析Fig.2 Sensitivity analysis of algorithm score toε/δ

圖3 算法運(yùn)行時(shí)間對(duì)ε/δ敏感性分析Fig.3 Sensitivity analysis of algorithm running time to ε/δ

圖4 5種聚類(lèi)算法對(duì)數(shù)據(jù)集flame的聚類(lèi)結(jié)果Fig.4 Clustering results of five clustering algorithms on flame dataset

圖5 5種聚類(lèi)算法對(duì)數(shù)據(jù)集pathbased的聚類(lèi)結(jié)果Fig.5 Clustering results of five clustering algorithms on pathbased dataset

圖6 5種聚類(lèi)算法對(duì)數(shù)據(jù)集aggregation的聚類(lèi)結(jié)果Fig.6 Clustering results of five clustering algorithms on aggregation dataset

圖7 5種聚類(lèi)算法對(duì)數(shù)據(jù)集jain的聚類(lèi)結(jié)果Fig.7 Clustering results of five clustering algorithms on jain dataset

圖8 5種聚類(lèi)算法對(duì)數(shù)據(jù)集impossible的聚類(lèi)結(jié)果Fig.8 Clustering results of five clustering algorithms on impossible dataset

圖4～圖6是對(duì)3種密度均勻但類(lèi)簇其他分布情況和聚類(lèi)數(shù)目各不相同的非凸數(shù)據(jù)集聚類(lèi)的結(jié)果?？梢钥闯?，KMEANS算法在3個(gè)數(shù)據(jù)集上的聚類(lèi)效果都不理想；BIRCH僅在flame數(shù)據(jù)集上可以得到正確聚類(lèi)數(shù)目而在pathbased和aggregation數(shù)據(jù)集上均出現(xiàn)了明顯錯(cuò)誤，將同一類(lèi)簇中的點(diǎn)識(shí)別成了多個(gè)類(lèi)；CBSCAN算法在flame和aggregation上聚類(lèi)結(jié)果都很好，但在pathbased上聚類(lèi)效果不佳；DBSCAN和G_FDBSCAN算法都可以正確劃分?jǐn)?shù)據(jù)類(lèi)別。這表明KMEANS算法和BIRCH算法不能很好地對(duì)非凸數(shù)據(jù)集進(jìn)行聚類(lèi)。CBSCAN算法不能很好地聚類(lèi)鄰接的帶環(huán)簇結(jié)構(gòu)。同時(shí)，也可以看出G_FDBSCAN算法比DBSCAN算法對(duì)類(lèi)簇邊界點(diǎn)的識(shí)別更為精準(zhǔn)。

圖7是兩個(gè)弧形且同一類(lèi)簇內(nèi)存在密度不均勻分布的數(shù)據(jù)集。從圖中結(jié)果可以看出，BIRCH算法和KMEANS算法均存在將一個(gè)弧形簇的一部分劃分到另一個(gè)類(lèi)簇中的問(wèn)題，CBSCAN算法和DBSCAN算法將存在密度不均勻分布的弧形簇劃分成了兩個(gè)類(lèi)，G_FDBSCAN算法由于對(duì)數(shù)據(jù)集的不同密度區(qū)域采用分而治之的策略得到了正確聚類(lèi)結(jié)果，聚類(lèi)效果最好。

圖8是類(lèi)簇形狀和密度分布情況復(fù)雜的數(shù)據(jù)集。在圖8的聚類(lèi)結(jié)果圖中，G_FDBSCAN算法和CBSCAN算法均得到了正確的聚類(lèi)結(jié)果，其他三種算法均有一定偏差。BIRCH算法和KMEANS算法聚類(lèi)效果都很差，將同一類(lèi)簇識(shí)別成多個(gè)類(lèi)，DBSCAN算法在類(lèi)簇邊緣處的識(shí)別效果不佳，這主要是由于其使用全局參數(shù)所致。

聚類(lèi)結(jié)果量化描述如表3所示。從表3可以看出，在ARI和AMI指標(biāo)值方面，BIRCH算法和KMEANS算法在5個(gè)數(shù)據(jù)集上的指標(biāo)值大多在0.5或0.5以下，且在不同數(shù)據(jù)集上波動(dòng)較大；G_FDBSCAN算法、CBSCAN算法和DBSCAN算法在不同數(shù)據(jù)集上的指標(biāo)值都接近于1，算法性能穩(wěn)定，且G_FDBSCAN算法在各種復(fù)雜數(shù)據(jù)集上的魯棒性最強(qiáng)，在所有測(cè)試數(shù)據(jù)集都是最優(yōu)值或非常接近最優(yōu)值。在時(shí)間性能方面，G_FDBSCAN算法所需時(shí)間最短，CBSCAN算法次之，BIRCH和KMEANS算法時(shí)間開(kāi)銷(xiāo)也較小但在一些數(shù)據(jù)集上有波動(dòng)，DBSCAN算法所需時(shí)間最久且和其他3種算法所需時(shí)間明顯不在同一量級(jí)，這在數(shù)量較大的aggregation和impossible數(shù)據(jù)集上尤為明顯。

綜合分析可知，G_FDBSCAN算法的綜合性能最佳，不僅聚類(lèi)速度快，而且對(duì)于各種分布復(fù)雜的數(shù)據(jù)集具有最強(qiáng)的魯棒性。

3.4（超參數(shù)）最佳調(diào)整下的性能

本節(jié)在7個(gè)UCI數(shù)據(jù)集上測(cè)試，因?yàn)镃BSCAN算法不支持高維數(shù)據(jù)，所以選擇增加和DPC算法的對(duì)比實(shí)驗(yàn)，參數(shù)最優(yōu)化調(diào)整下各算法的聚類(lèi)結(jié)果如表4所示。為減少實(shí)驗(yàn)誤差，每個(gè)數(shù)據(jù)集獨(dú)立運(yùn)行10次，取平均值作為最終實(shí)驗(yàn)結(jié)果。通過(guò)實(shí)驗(yàn)結(jié)果可以看出，在參數(shù)最優(yōu)調(diào)整下，G_FDBSCAN算法的ARI和AMI指標(biāo)值和運(yùn)行時(shí)間均是最優(yōu)值或接近最優(yōu)值，且在不同數(shù)據(jù)集上性能穩(wěn)定；DPC算法和DBSCAN算法聚類(lèi)效果較好但算法時(shí)間開(kāi)銷(xiāo)很大，在pendigits這樣的大規(guī)模數(shù)據(jù)集上對(duì)比更加明顯；BIRCH算法和KMEANS算法聚類(lèi)速度較快，但在不同數(shù)據(jù)集上聚類(lèi)結(jié)果差異大，在wine數(shù)據(jù)集上ARI和AMI指標(biāo)值和G_FDBSCAN算法相差接近100倍。這表明，G_FDBSCAN算法能較好地平衡算法的聚類(lèi)效果和時(shí)間開(kāi)銷(xiāo)，算法性能優(yōu)越，實(shí)際應(yīng)用中能更好地?cái)U(kuò)展到各種復(fù)雜的大規(guī)模數(shù)據(jù)集。

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

G_FDBSCAN算法是一種快速聚類(lèi)算法，該算法通過(guò)將密度聚類(lèi)算法與網(wǎng)格聚類(lèi)算法融合，以及改進(jìn)DBSCAN算法執(zhí)行過(guò)程（FDBSCAN算法），兩方面降低DBSCAN算法的時(shí)間復(fù)雜度，同時(shí)降低了使用全局參數(shù)對(duì)算法性能的折損，優(yōu)化聚類(lèi)結(jié)果。本文通過(guò)理論和實(shí)驗(yàn)分析，證明G_FDBSCAN算法可以在一定程度上減少計(jì)算量，獲得與BIRCH、KMEANS、CBSCAN這些快速算法同一量級(jí)甚至更快的聚類(lèi)速度，以及比DPC算法和DBSCAN算法更優(yōu)的聚類(lèi)結(jié)果，從而在大規(guī)模數(shù)據(jù)上獲得較好的可擴(kuò)展性。此外，改進(jìn)后的算法聚類(lèi)結(jié)果穩(wěn)定、魯棒性強(qiáng)，可以在類(lèi)簇大小、形狀和密度不同的復(fù)雜數(shù)據(jù)集上獲得較好的聚類(lèi)結(jié)果。本文還通過(guò)實(shí)驗(yàn)分析了算法對(duì)不同超參數(shù)的敏感性，得出的結(jié)論可以指導(dǎo)算法實(shí)際應(yīng)用中的參數(shù)調(diào)整。

表3 5種聚類(lèi)算法在人工數(shù)據(jù)集上的性能對(duì)比Table3 Performance comparison of five clustering algorithms on artificial datasets

表4 5種聚類(lèi)算法在真實(shí)數(shù)據(jù)集上的性能對(duì)比Table 4 Performance comparison of five clustering algorithms on real datasets