融合網(wǎng)格劃分和DBSCAN的改進(jìn)聚類算法

孫 璐，梁永全

山東科技大學(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)越重要。聚類是一種重要的數(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ì)聚類算法研究的不斷深入，產(chǎn)生了許多優(yōu)秀的算法。根據(jù)算法實(shí)現(xiàn)原理和探究方向不同，目前五種主流的聚類算法為基于劃分的方法、基于密度的方法、基于層次的方法、基于網(wǎng)格的方法和基于模型的方法[7]。

DBSCAN是最經(jīng)典的基于密度的聚類算法之一，其根據(jù)數(shù)據(jù)集的空間分布密度對(duì)樣本點(diǎn)進(jìn)行聚類，可以在有噪聲的數(shù)據(jù)中發(fā)現(xiàn)任意形狀的類簇[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ù)集中的聚類質(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)地選擇聚類的局部半徑，并據(jù)此擴(kuò)展密度峰值點(diǎn)進(jìn)行聚類，提高了聚類結(jié)果的質(zhì)量。文獻(xiàn)[13]通過(guò)貪心策略自適應(yīng)確定局部最優(yōu)鄰域半徑，并通過(guò)比較鄰域內(nèi)點(diǎn)之間的平均距離與半徑參數(shù)發(fā)現(xiàn)噪聲，提升聚類精度。文獻(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ò)展類的方式，減少重復(fù)的鄰域檢索，加快聚類。文獻(xiàn)[18-20]利用圖形處理單元（GPU）、空間分區(qū)數(shù)據(jù)結(jié)構(gòu)（如R樹(shù)和KD樹(shù)）或并行算法提出了基于密度的快速、可擴(kuò)展的聚類方法，用于處理大型數(shù)據(jù)集。這些方法都在一定程度上提升了DBSCAN算法的性能，降低了算法的時(shí)間復(fù)雜度，但是這些方法大多無(wú)法較好地兼顧時(shí)間開(kāi)銷(xiāo)與算法性能。

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

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

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

傳統(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)，則稱p由q密度直達(dá)。

定義6（密度可達(dá)）如果存在一個(gè)樣本點(diǎn)鏈p1,p2,…,pi,pi+1,…,pn滿足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á)，則稱p和q密度相連。

在DBSCAN中簇的定義是從一個(gè)核心點(diǎn)出發(fā)由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連點(diǎn)的集合，即為最終聚類的一個(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)一定屬于不同的類。傳統(tǒng)DBSCAN算法中假設(shè)同一個(gè)核心點(diǎn)鄰域內(nèi)的點(diǎn)屬于同一類。據(jù)此，本文對(duì)傳統(tǒng)的DBSCAN算法進(jìn)行了改進(jìn)，提出了一種DBSCAN的改進(jìn)算法——快速DBSCAN算法（FDBSCAN）。該算法以子類簇間交疊部分存在核心點(diǎn)為類簇合并依據(jù)，基于此擴(kuò)展類簇完成聚類，避免了類簇?cái)U(kuò)展過(guò)程中鄰域的冗余檢索，從而加快聚類速度。具體算法步驟如下：

FDBSCAN算法步驟如下：

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

輸出：樣本點(diǎn)類標(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è)新的類簇C，然后將p從S中刪除；對(duì)于p的ε鄰域內(nèi)已有類標(biāo)號(hào)的點(diǎn)，將X中與該點(diǎn)類別相同的點(diǎn)全部標(biāo)記類別C；將p的ε鄰域內(nèi)其余點(diǎn)的類標(biāo)號(hào)記為C；將p的ε鄰域內(nèi)的核心點(diǎn)從S中刪除。

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

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

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

基于網(wǎng)格的聚類采用空間驅(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í)別為簇。聚類質(zhì)量取決于網(wǎng)格單元的劃分粒度，如果劃分粒度很細(xì)，則網(wǎng)格單元的數(shù)量會(huì)顯著增加，從而使處理代價(jià)顯著增加；如果劃分粒度太粗，則屬于不同類中的對(duì)象被劃分到同一網(wǎng)格中概率會(huì)顯著增加，從而降低聚類精度。這種方法具有線性的時(shí)間復(fù)雜度，對(duì)大規(guī)模數(shù)據(jù)集有很好的擴(kuò)展性，但是，以網(wǎng)格取代數(shù)據(jù)點(diǎn)作為聚類基本單元，丟失了大部分點(diǎn)的信息，導(dǎo)致聚類質(zhì)量下降。

有許多經(jīng)典的基于網(wǎng)格的聚類算法。本文選擇了基于網(wǎng)格和密度相結(jié)合的CLIQUE聚類算法。根據(jù)后面與DBSCAN算法融合的需要，對(duì)CLIQUE算法進(jìn)行改進(jìn)，提出一種改進(jìn)的CLIQUE算法。下面根據(jù)兩個(gè)超參數(shù)：網(wǎng)格寬度ε和密度閾值δ，給出網(wǎng)格聚類的一些相關(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ù)稱為該網(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)類標(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算法），提出了一種精確高效的聚類算法G_FDBSCAN算法。采用基于網(wǎng)格的聚類算法作為數(shù)據(jù)集分布度量，給出數(shù)據(jù)集密度分布特征，分而治之，從而在一定程度上避免DBSCAN采用全局參數(shù)引起的誤差；僅對(duì)稀疏區(qū)域的點(diǎn)運(yùn)用FDBSCAN聚類，將使用FDBSCAN聚類的對(duì)象數(shù)控制在平方的時(shí)間復(fù)雜度到達(dá)之前的數(shù)量級(jí)范圍內(nèi)，也可以在一定程度避免基于網(wǎng)格的聚類算法采用硬網(wǎng)格劃分技術(shù)破壞聚類邊緣造成的聚類精度差的問(wèn)題。通過(guò)改進(jìn)，在優(yōu)化傳統(tǒng)DBSCAN算法聚類結(jié)果的同時(shí)，大大降低了算法的時(shí)間復(fù)雜度。

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

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

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

輸出：樣本點(diǎn)類標(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ù)聚類。

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

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

該算法的時(shí)間復(fù)雜度為O(n)。假設(shè)n是數(shù)據(jù)集中點(diǎn)的數(shù)量，該算法的時(shí)間復(fù)雜度主要由兩部分決定：（1）網(wǎng)格聚類，時(shí)間復(fù)雜度O(n)。此部分的時(shí)間復(fù)雜度由兩部分組成：①劃分?jǐn)?shù)據(jù)空間，將每個(gè)數(shù)據(jù)點(diǎn)映射到網(wǎng)格單元中需要線性時(shí)間復(fù)雜度O(n)；②篩選出高密度網(wǎng)格需要O(u)，u是網(wǎng)格單元數(shù)，u?n。（2）FDBSCAN聚類，即對(duì)網(wǎng)格聚類后剩余未聚類的點(diǎn)的聚類，時(shí)間復(fù)雜度O(ml)。此部分的時(shí)間復(fù)雜度由兩部分組成：①計(jì)算核心點(diǎn)，鄰域檢索只在相鄰網(wǎng)格范圍內(nèi)執(zhí)行，時(shí)間復(fù)雜度為O(ml)，m是網(wǎng)格聚類后剩余未聚類的點(diǎn)的總數(shù)，m?n；l是近鄰網(wǎng)格中的點(diǎn)數(shù)，l?m。②掃描剩余的未聚類點(diǎn)就近歸類，該部分的點(diǎn)數(shù)量很少，且基本都是位于類簇邊界上，每個(gè)點(diǎn)就近歸類時(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算法的聚類效果和效率。人工數(shù)據(jù)集選取了5個(gè)不同形狀、大小和密度的有一定結(jié)構(gòu)復(fù)雜度的數(shù)據(jù)集（表1）。真實(shí)數(shù)據(jù)集選了7個(gè)不同大小、維度和類別數(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ò)兩種常用的聚類評(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]，取值越大表示聚類結(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)椋诺拇笮Q定了每個(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)格聚類的點(diǎn)的數(shù)量的影響。使用網(wǎng)格聚類的點(diǎn)越多，則使用FDBSCAN的點(diǎn)越少，時(shí)間效率就越高。因此，這一過(guò)程受到ε和δ的聯(lián)合作用的影響。

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

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

圖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種聚類算法對(duì)數(shù)據(jù)集flame的聚類結(jié)果Fig.4 Clustering results of five clustering algorithms on flame dataset

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

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

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

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

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

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

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

聚類結(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算法的綜合性能最佳，不僅聚類速度快，而且對(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)整下各算法的聚類結(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算法聚類效果較好但算法時(shí)間開(kāi)銷(xiāo)很大，在pendigits這樣的大規(guī)模數(shù)據(jù)集上對(duì)比更加明顯；BIRCH算法和KMEANS算法聚類速度較快，但在不同數(shù)據(jù)集上聚類結(jié)果差異大，在wine數(shù)據(jù)集上ARI和AMI指標(biāo)值和G_FDBSCAN算法相差接近100倍。這表明，G_FDBSCAN算法能較好地平衡算法的聚類效果和時(shí)間開(kāi)銷(xiāo)，算法性能優(yōu)越，實(shí)際應(yīng)用中能更好地?cái)U(kuò)展到各種復(fù)雜的大規(guī)模數(shù)據(jù)集。

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

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

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

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