融合網格劃分和DBSCAN的改進聚類算法

孫 璐，梁永全

山東科技大學 計算機科學與工程學院，山東 青島 266590

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

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

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

1快速DBSCAN算法（fast DBSCAN，FDBSCAN）

1.1傳統DBSCAN聚類算法

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

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

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

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

定義4（噪聲點）噪聲點是在其ε鄰域內點的個數少于δ且鄰域內的點均為邊界點的點。

定義5（密度直達）如果p位于q的ε-鄰域中，且q是核心點，則稱p由q密度直達。

定義6（密度可達）如果存在一個樣本點鏈p1,p2,…,pi,pi+1,…,pn滿足p1=p和pn=q,pi是由pi+1關于ε和δ密度直達的，則點p是由點q關于ε和δ密度可達的。

定義7（密度相連）對于p和q，如果存在核心點h，使p和q均由h密度可達，則稱p和q密度相連。

在DBSCAN中簇的定義是從一個核心點出發由密度可達關系導出的最大密度相連點的集合，即為最終聚類的一個簇。

1.2快速DBSCAN算法

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

FDBSCAN算法步驟如下：

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

輸出：樣本點類標簽

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

步驟2每次選擇S中當前的第一個點p（即為當前密度最大的核心點），為p創建一個新的類簇C，然后將p從S中刪除；對于p的ε鄰域內已有類標號的點，將X中與該點類別相同的點全部標記類別C；將p的ε鄰域內其余點的類標號記為C；將p的ε鄰域內的核心點從S中刪除。

步驟3將數據集X中剩余點聚類至鄰域內最近的核心點所在類；鄰域內無核心點的標記為噪聲點。

2 融合網格劃分與FDBSCAN的改進聚類算法（fusion of grid partition and FDBSCAN clustering algorithm，G_FDBSCAN）

2.1 改進的網格聚類算法

基于網格的聚類采用空間驅動的方法，把嵌入空間劃分成獨立于輸入對象分布的單元[21]。該方法使用一種多分辨率的網格數據結構，將數據空間量化成有限數目的互不相交的網格單元，根據密度閾值將網格識別為高、低密度網格，將相連的高密度網格識別為簇。聚類質量取決于網格單元的劃分粒度，如果劃分粒度很細，則網格單元的數量會顯著增加，從而使處理代價顯著增加；如果劃分粒度太粗，則屬于不同類中的對象被劃分到同一網格中概率會顯著增加，從而降低聚類精度。這種方法具有線性的時間復雜度，對大規模數據集有很好的擴展性，但是，以網格取代數據點作為聚類基本單元，丟失了大部分點的信息，導致聚類質量下降。

有許多經典的基于網格的聚類算法。本文選擇了基于網格和密度相結合的CLIQUE聚類算法。根據后面與DBSCAN算法融合的需要，對CLIQUE算法進行改進，提出一種改進的CLIQUE算法。下面根據兩個超參數：網格寬度ε和密度閾值δ，給出網格聚類的一些相關定義。

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

定義9（相鄰網格）相鄰網格是指有共同邊的網格單元。

定義10（網格單元密度）網格單元u中數據點的個數稱為該網格單元的密度，記作N(u)。

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

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

改進的CLIQUE算法步驟如下：

輸入：數據集X={x1,x2,…,xn}，網格寬度ε，密度閾值δ

輸出：樣本點類標簽

步驟1根據給定超參數ε和δ，將數據集X中的點映射到網格中，將所有網格劃分為稠密網格和稀疏網格。

步驟2將相鄰的稠密網格連接成簇；將稀疏網格中的點標記為噪聲點。

2.2 G_FDBSCAN算法

通過結合網格劃分方法，并改進原DBSCAN算法的執行步驟（FDBSCAN算法），提出了一種精確高效的聚類算法G_FDBSCAN算法。采用基于網格的聚類算法作為數據集分布度量，給出數據集密度分布特征，分而治之，從而在一定程度上避免DBSCAN采用全局參數引起的誤差；僅對稀疏區域的點運用FDBSCAN聚類，將使用FDBSCAN聚類的對象數控制在平方的時間復雜度到達之前的數量級范圍內，也可以在一定程度避免基于網格的聚類算法采用硬網格劃分技術破壞聚類邊緣造成的聚類精度差的問題。通過改進，在優化傳統DBSCAN算法聚類結果的同時，大大降低了算法的時間復雜度。

采用網格劃分技術將數據空間劃分為多個網格單元，稠密網格所在區域稱為密集區域，稀疏網格所在區域稱為稀疏區域，分而治之。首先，對密集區域內的點進行預聚類，這些點位于類簇中心區域，通過合理調整用戶參數，基本可以保證同一網格單元中的數據點屬于同一類簇，數量大且易于識別。應用基于網格的聚類算法，可以快速、準確地獲得初始聚類結果。稀疏區域中的點通常位于類簇的邊緣區域，且其中可能存在噪聲容易被誤分類，數據量遠少于密集區域，聚類難度較大。因此，針對稀疏區域的點，本文在現有網格劃分的基礎上，采用本文提出的FDBSCAN算法進行處理。

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

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

輸出：樣本點類標簽

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

步驟2對密集網格所在區域的點利用改進的CLIQUE算法進行預聚類。

步驟3將密集區域中網格聚類得到的每一個子類作為一個整體與網格聚類后剩余未聚類的點一起運用基于網格劃分的FDBSCAN算法（確定核心點的鄰域檢索只在相鄰網格范圍內執行）進行聚類，同時識別噪聲點，得到最終的聚類結果。

2.3 G_FDBSCAN的時間復雜度

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

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

3 實驗

3.1 實驗數據集及設置

通過在人工數據集和真實數據集上進行對比實驗來綜合評估分析G_FDBSCAN算法的聚類效果和效率。人工數據集選取了5個不同形狀、大小和密度的有一定結構復雜度的數據集（表1）。真實數據集選了7個不同大小、維度和類別數目的UCI（http：//archive.ics.uci.edu/ml/datasets.php）數據集（表2）。對比算法包括BIRCH算法、KMEANS算法、DPC算法、CBSCAN算法[14]以及傳統DBSCAN算法。

表1 人工數據集Table 1 Artificial datasets

本文通過兩種常用的聚類評估指標對算法的性能進行評價：調整蘭德系數[22（]adjusted Rand Index，ARI）和調整互信息[23（]adjusted mutual information，AMI），兩種指標的取值范圍為[-1,1]，取值越大表示聚類結果和真實情況越吻合。實驗基礎環境為Intel?CoreTMi5-7500 CPU@3.40 GHz，8 GB內存，Windows10操作系統和anaconda3 Python。

表2 真實數據集Table 2 Real datasets

3.2 超參數對算法性能的影響

本節在impossible數據集和pendigits數據集上進行對比實驗，運用控制變量法，分別將超參數ε和δ固定為最佳調整值，改變另一個參數的取值，來測試和評估這兩個參數對新算法性能的影響。

每個超參數對算法評分的影響情況如圖2。可以看出，ε和δ值的變化都會引起算法評分的波動，在兩個數據集的最佳參數附近（impossible數據集：ε=1.0，δ=20；pendigits數據集：ε=42，δ=10），算法評分隨ε值變化而產生的波動較大，隨δ值變化而產生的波動較小。這是因為，ε的大小決定了每個數據點在網格劃分中的區域定位，從而決定了數據對象在網格空間的整體布局，而δ的大小僅決定一個網格是否是高密度網格。因此，G_FDBSCAN算法評分對ε更為敏感。

圖3展示了算法運行時間對兩個超參數的敏感性。可以看出ε和δ都會影響算法的運行時間，但是運行時間對兩個超參數的敏感性沒有明顯的偏向。原因是，G_FDBSCAN的運行時間主要受測試數據集中使用網格聚類的點的數量的影響。使用網格聚類的點越多，則使用FDBSCAN的點越少，時間效率就越高。因此，這一過程受到ε和δ的聯合作用的影響。

3.3 復雜數據集中應用的魯棒性

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

圖2 算法評分對ε/δ敏感性分析Fig.2 Sensitivity analysis of algorithm score toε/δ

圖3 算法運行時間對ε/δ敏感性分析Fig.3 Sensitivity analysis of algorithm running time to ε/δ

圖4 5種聚類算法對數據集flame的聚類結果Fig.4 Clustering results of five clustering algorithms on flame dataset

圖5 5種聚類算法對數據集pathbased的聚類結果Fig.5 Clustering results of five clustering algorithms on pathbased dataset

圖6 5種聚類算法對數據集aggregation的聚類結果Fig.6 Clustering results of five clustering algorithms on aggregation dataset

圖7 5種聚類算法對數據集jain的聚類結果Fig.7 Clustering results of five clustering algorithms on jain dataset

圖8 5種聚類算法對數據集impossible的聚類結果Fig.8 Clustering results of five clustering algorithms on impossible dataset

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

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

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

聚類結果量化描述如表3所示。從表3可以看出，在ARI和AMI指標值方面，BIRCH算法和KMEANS算法在5個數據集上的指標值大多在0.5或0.5以下，且在不同數據集上波動較大；G_FDBSCAN算法、CBSCAN算法和DBSCAN算法在不同數據集上的指標值都接近于1，算法性能穩定，且G_FDBSCAN算法在各種復雜數據集上的魯棒性最強，在所有測試數據集都是最優值或非常接近最優值。在時間性能方面，G_FDBSCAN算法所需時間最短，CBSCAN算法次之，BIRCH和KMEANS算法時間開銷也較小但在一些數據集上有波動，DBSCAN算法所需時間最久且和其他3種算法所需時間明顯不在同一量級，這在數量較大的aggregation和impossible數據集上尤為明顯。

綜合分析可知，G_FDBSCAN算法的綜合性能最佳，不僅聚類速度快，而且對于各種分布復雜的數據集具有最強的魯棒性。

3.4（超參數）最佳調整下的性能

本節在7個UCI數據集上測試，因為CBSCAN算法不支持高維數據，所以選擇增加和DPC算法的對比實驗，參數最優化調整下各算法的聚類結果如表4所示。為減少實驗誤差，每個數據集獨立運行10次，取平均值作為最終實驗結果。通過實驗結果可以看出，在參數最優調整下，G_FDBSCAN算法的ARI和AMI指標值和運行時間均是最優值或接近最優值，且在不同數據集上性能穩定；DPC算法和DBSCAN算法聚類效果較好但算法時間開銷很大，在pendigits這樣的大規模數據集上對比更加明顯；BIRCH算法和KMEANS算法聚類速度較快，但在不同數據集上聚類結果差異大，在wine數據集上ARI和AMI指標值和G_FDBSCAN算法相差接近100倍。這表明，G_FDBSCAN算法能較好地平衡算法的聚類效果和時間開銷，算法性能優越，實際應用中能更好地擴展到各種復雜的大規模數據集。

4 結束語

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

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

表4 5種聚類算法在真實數據集上的性能對比Table 4 Performance comparison of five clustering algorithms on real datasets