改進的自適應參數DBSCAN 聚類算法

王 光，林國宇

遼寧工程技術大學 軟件學院，遼寧 葫蘆島 125105

1 引言

聚類算法是在無標簽的數據中發現數據的內部聯系，若數據的屬性相同則聚成一個簇。針對這一特性，聚類算法被廣泛應用于用戶畫像[1]、文本處理[2]、圖像分割[3]等領域。

DBSCAN算法是密度聚類中最經典的算法之一，它可以有效地尋找到被低密度區域分隔的高密度區域，并在具有噪聲的數據中發現任意形狀的簇。DBSCAN通過鄰域(Eps)和鄰域內最少樣本的數量(MinPts)來識別數據集中有較高密度的樣本點，并將其劃分為簇。然而DBSCAN對Eps和MinPts兩個參數的選擇非常敏感，若選取不當可能會出現錯誤的聚類甚至無法聚類的情況。針對DBSCAN參數的自適應選擇，國內外學者進行了一系列的研究。周紅芳等[4]提出的I-DBSCAN算法運用極大似然估計和泊松分布來估計Eps的取值，用求數學期望的方法來求MinPts，該方法依賴數據自身的分布特點，依靠人為觀察噪聲和聚類個數與K的關系圖，導致結果存在一定誤差。李文杰等[5]提出的KANN-DBSCAN算法根據K-近鄰求出Eps的候選集合，選取不同的K值根據數學期望得到MinPts，再把參數輸入DBSCAN繼續聚類，當取三次K值，若簇數穩定則記為最優簇數，通過循環迭代求出最優參數，該方法雖然精確度相對較高，但是隨著數據量的增大，時間消耗也逐漸增大。周治平等[6]提出的AF-DBSCAN根據k-dist分布進行分析，該方法用一條曲線描述全局分布，主觀性較強同時存在一定的誤差。秦佳睿等[7]提出的SALE-DBSCAN通過尋找密度峰值點，自動選擇聚類的局部鄰域半徑，該方法需要計算所有點的局部密度來尋找密度峰值點，再擴張密度峰值點鄰域、合并聚類結果等，使該算法的復雜度較高。李宗林等[8]提出利用非參數核密度估計來確定Eps和MinPts，該算法雖然實現了參數的全程自適應選擇，但是針對不同類型的數據進行聚類時魯棒性較差，且計算復雜度較高。

鑒于此，本文提出一種自適應選擇DBSCAN參數的KLS-DBSCAN聚類算法，該算法利用數據自身的分布特點找出合理的參數范圍，再通過尋找聚類內部度量最大值的方法確定最佳的Eps和MinPts參數值，該算法有運算簡單、聚類結果準確率高的優點。

2 DBSCAN算法

DBSCAN算法由Ester M、Kriegel H P等人[9]在1996年提出，它不需要預先指定簇的個數，但需要給定兩個參數。該算法是基于一組：“鄰域”參數(Eps,MinPts)來描述樣本分布的緊密度，假設給定數據集D={x1,x2,…,xm}定義如下概念：

定義1(Eps-鄰域）對 xj∈D,Eps-鄰域包含樣本集D中與xj之間的距離小于等于Eps的樣本，即：

定義3（直接密度可達）如果xj在 xi的Eps-鄰域中，并且xi是核心對象，稱xj由xi直接密度可達。

定義4（密度可達）對于xi和xj，如果存在一個序列 p1,p2,…,pn，其中 p1=xi,pn=xj并且 pn+1由 pi直接密度可達，稱xj由xi密度可達。

定義5（密度相連）對于 xi和 xj，如果存在 xk使

定義2（核心對象）如果 xj的Eps-領域至少包含MinPts個樣本，即：xi和xj均由xk密度可達，則稱xi和xj密度相連，密度相連具有對稱性。

定義6（簇和噪聲）從數據集D中任取一點 p，從p點開始在D中搜索滿足Eps和MinPts條件且密度可達的所有點構成一個簇，不屬于任何簇的對象則被標記為噪聲點。

在具體的DBSCAN聚類過程中首先將數據集D中的樣本標記為未處理對象，對每個樣本點計算Eps半徑內點的集合，集合內多于MinPts個數的點標記為核心點，剩余的點如果在核心點的鄰域內則被標記為邊界點，否則標記為噪聲點。

3 自適應確定DBSCAN算法參數

3.1 基本思想

密度聚類算法的實質是根據空間中數據分布的緊密程度進行聚類。DBSCAN算法通過Eps和MinPts兩個參數來刻畫數據的緊密程度，在傳統的DBSCAN算法中，Eps和MinPts兩個參數的選擇往往通過經驗判斷，再根據結果調整，因為Eps和MinPts兩個參數具有全局性，在分布不均的數據上采用經驗數據很難達到預期效果。

本文通過DBSCAN算法在不同數據集上的實驗發現，達到預期聚類效果時Eps和MinPts兩個參數值并不唯一，但一定在某個區間內變化。無論數據疏密程度、形狀，數據的局部密度往往存在一定的變化，因此可以預知數據分成幾個簇比較合理，基于以上研究采用核密度估計確定參數合理區間，根據局部密度分析確定聚類簇數，通過計算輪廓系數求出最優的Eps和MinPts兩個參數值。

3.2 確定參數Eps和MinPts的合理區間

根據數據分布特征來判斷參數范圍，能有效地將參數確定在一個相對合理的區間。核密度估計能夠刻畫數據分布特征[10]，并且能有效地檢測出噪聲點[11]，是一種非參數方法，假設獨立分布F包含x1,x2,…,xn個樣本點，概率密度函數為 f，核密度估計如下：

其中，h表示帶寬，K(x)表示核函數，同時K(x)滿足以下條件：

然而帶寬的選擇往往比較困難，不同的帶寬會導致擬合的結果有很大的差異，通常在聚類分析中，一般選擇均平方積分誤差函數(MISE)來優化帶寬。具體定義如下：

在弱假設下：

其中：

最小化MISE(h)等價于最小化AMISE(h)，求偏導并令導數等于0有：

其中m、R根據核函數確定。

然而，核密度估計并不能找到實例中的最優參數，但是可以估計一個合理的參數選取區間。下面通過一個實例進行具體分析。

生成包含2 000個數據點4個聚類中心的數據集SampleD，分布情況如圖1所示，計算所有樣本之間的距離，生成距離矩陣Dist，通過核密度估計的方法繪制曲線圖，如圖2所示，可以發現密度曲線出現了兩次峰值，第一次峰值的出現代表簇內密度較高的距離，第二次峰值的出現代表簇間密度較高的距離。所以本例中應該取簇內距離作為Eps的取值，當Eps∈( )0,0.2時可以作為Eps取值的候選范圍。

圖1 SampleD的數據點分布圖

圖2 核密度估計曲線圖

根據Eps的預估值范圍，采用數學期望的方法，根據距離矩陣Dist，在給定數據集中求出MinPts的合理區間，公式如下：

其中，Pi表示對象i的Eps鄰域內包含的樣本個數。

3.3 確定聚類簇數

通過核密度估計對全局數據進行分析只能粗略地得到數據集的疏密程度，然而對局部密度特點分析可以計算出數據集合理的聚類簇數[12]，密度峰值聚類算法（DP）正是利用這樣的特性確定聚類中心，然而DP算法仍然需要人工指定截斷距離(dc)，并且最終的聚類中心的選擇通過觀察得到。本文利用帶寬參數自適應選擇截斷距離，通過計算決策圖中樣本點之間的斜率，分析比較疑似中心點之間的距離關系確定聚類中心，具體描述如下：

在給定的數據集D中隨機取一點g，可以定義兩個值：局部密度ρi和到較高局部密度點的距離δi。

局部密度 ρi：

其中，dij表示兩點間距離，dc表示截斷距離，dc可根據上文中提到的帶寬參數自適應確定[10]。

集合D中每一個樣本點 xi通過(ρi,δi),i∈ID抽象表示，并繪制如圖3所示決策圖。

圖3 聚類中心決策圖

為了更精確選擇聚類簇數，綜合考慮ρi和δi的影響，定義 γi=ρiδi,i∈Is,γi值越大，越有可能是聚類中心[13]。對 {γ}Ni=1進行降序排列，p 表示 γ[1～p]與 γ[p～n]之間變化程度最大的點，點p滿足：

其中，ki表示第i個點到i+1個點之間線段的斜率，φ表示相鄰點斜率差的平均值，θ(j)表示相鄰點斜率差的總和。疑似聚類中心定義為：

根據密度峰值算法的性質，真實的聚類中心一般分布在密度較高的區域，且中心之間相對距離較遠。如果在一個高密度區域中存在多個疑似聚類中心點，通常這些點會比較接近。因此依次判斷最大值的γi和剩余點之間的最短距離，如果小于截斷距離dc，則不是聚類中心，如果大于截斷距離dc，則是聚類中心。

3.4 參數尋優

在真實分類標簽未知的情況下可以通過內部度量來描述聚類的質量，計算輪廓系數是常用的聚類內部度量方法[14]，它是衡量一個樣本點與它所在簇相比于其他簇的相似度，具體公式定義如下：其中，a(i)表示第i個對象到所在簇中其他對象的平均距離，b(i)表示第i個對象到除了i所在簇以外的其他簇內對象的平均距離。s(i)∈[-1,1]該數值越接近于1說明分類越合理。

本文引入輪廓系數作為衡量聚類效果的重要指標，因為它不需要在明確聚類中心的情況下就能計算出簇與簇之間的密集與分散程度，并且具有魯棒性。利用輪廓系數的這一特點計算出DBSCAN中最優的Eps和MinPts參數值，對數據集SampleD進行聚類的結果如圖4所示，通過自適應選擇參數能夠識別密度較高的區域，并作出正確的聚類，說明本文算法選擇了合適的Eps和MinPts兩個參數。

圖4 基于KLS-DBSCAN的SampleD聚類結果

3.5KLS-DBSCAN算法描述

（1）根據原始數據分布特征，利用核密度估計確定Eps范圍，采用數學期望法確定MinPts范圍。

（2）通過分析局部密度特點計算出數據集合理的聚類個數。

（3）采用輪廓系數作為衡量聚類質量的依據，從而確定最優的Eps和MinPts兩個參數。

（4）利用最優的Eps和MinPts進行聚類。

具體計算過程如下所示。

算法 KLS-DBSCAN算法

輸入：Eps的區間(eps_list)、Minpts的區間(Minpts_list)、最優的聚類個數(label_num)。

計算：

步驟1對eps_list、Minpts_list按最小間隔進行分割。

步驟2按照eps_list和Minpts_list的取值計算聚類個數。

步驟3如果所計算的聚類個數等于label_num，則計算輪廓系數。

步驟4比較輪廓系數，選取最大值。

步驟5儲存輪廓系數的最大值所對應的Eps和MinPts值。

輸出：全局最優的Eps和MinPts。

4 實驗及結果分析

KLS-DBSCAN算法采用Python語言實現，在Windows10系統下運行，PC硬件配置：Inter?CoreTMi5-3337U CPU@1.80 GHz，8 GB內存，1 TB硬盤。為了證明本文算法具有較高的聚類準確率，實驗通過對不同形狀且密度分布不均的人工數據集和真實的UCI數據集進行分析。同時與KNN-DBSCAN、AF-DBSCAN及DBSCAN算法進行對比，其中KNN-DBSCAN基于K-平均最近鄰法和數學期望生產密度閾值列表，通過參數尋優策略尋找聚類結果穩定區間，自適應選擇最佳參數。AF-DBSCAN基于數學統計方法與密度聚類相結合，通過改進區域查詢方法，搜索最優擬合模型，從而得到最佳參數。

4.1 人工數據集的準備及實驗

為了驗證KLS-DBSCAN算法的可行性，采用四種典型人工數據集進行實驗分析，并用F值[15]對結果進行分析，F值綜合了準確率和召回率，取值范圍在(0,1]，越接近于1表示聚類效果越好。數據集可視化后如圖5所示，R15是包含600個對象的二維數據集，Flame是包含240個對象的二維數據集，Aggregation[16]是包含788個對象的二維數據集，Spiral[17]是包含312個對象的二維數據集。

DBSCAN算法Eps參數的選擇通過繪制k-距離曲線觀察后得到，MinPts則根據經驗采用數據集內樣本數量的1/25[18]。通過聚類結果對比，如圖6所示，發現KLS-DBSCAN和KNN-DBSCAN算法的聚類準確率更高，并且在不同數據集上都有良好的表現。具體的評價指標如表1所示。

從二維數據集上的聚類結果分析來看，在R15、Flame、Aggregation、Spiral數據集上，KLS-DBSCAN 和KNN-DBSCAN算法能夠有效地識別橋接簇和非球形簇，同時F值接近于1。AF-DBSCAN和DBSCAN由于Eps的選擇通過繪制k-距離曲線觀察后得到，所以帶有一定的主觀性，傳統DBSCAN算法的MinPts采用了經驗數據，不能很好地適應不同的數據集，聚類過程不能有效識別其聚類簇。從總體分析，KLS-DBSCAN算法的聚類結果要明顯優于AF-DBSCAN和DBSCAN算法，證明了其在不同形狀、不同密度的數據集上有相對較高的準確率。

4.2 真實數據集的實驗結果及分析

圖5 人工數據集散點圖

圖6 KLS-DBSCAN與其他算法聚類結果對比

表1 人工數據集聚類指標對比

為了驗證KLS-DBSCAN算法在真實數據集上的性能，通過真實的UCI數據集進行實驗，并采用準確率（ACC）[19]、互信息評分（AMI）、調整蘭德系數（ARI）[20]三個指標做綜合評價，其中ACC的取值范圍在[0,1]，AMI和ARI的取值范圍在[-1,1]，值越接近于1說明與真實聚類結果越吻合。Iris是包含150個對象的4維數據集，Wine是包含178個對象的13維數據集，Sym是包含350個對象的2維數據集，Heart是包含303個對象的13維數據集。

真實數據集聚類指標如表2所示，可以看出本文算法KLS-DBSCAN克服了傳統算法的人工選取參數的主觀性，并在高維度數據集上也有良好的表現，在Sym、Wine、Heart數據集上的指標整體上優于KNN-DBSCAN、AF-DBSCAN和DBSCAN。

表2 真實數據集聚類指標對比

在Iris數據集上AF-DBSCAN算法表現更好，但該算法在不同分布不同維度的數據集上的性能不穩定，魯棒性較差。KNN-DBSCAN算法雖然在二維的人工數據集上有良好的表現，但是在高維真實數據集上表現一般，因為其通過觀察聚類結果簇數與K的關系圖來選擇Eps和MinPts，但是在分布不均的高維真實數據集上關系曲線很難進入穩定區間，K值的選擇對聚類結果影響很大，本文算法則不會出現類似情況，即使通過核密度估計圖選擇了過大的Eps范圍，也可以通過增加迭代次數確定最優的參數。

4.3 算法復雜度分析

對于二維數據集，傳統的DBSCAN算法的時間復雜度為O(n2)[21]，本文算法基于DBSCAN，其時間復雜度主要來自于：（1）在選取最優參數時需要對Eps和MinPts參數范圍同時循環計算；（2）局部密度ρi和到較高局部密度點的距離δi；（3）選擇全局最優的Eps和MinPts參數。各部分的時間復雜度均為O(n2)，因此總的時間復雜度為O(n2)。

DBSCAN算法的空間復雜度為O(n2)，KLS-DBSCAN算法的空間復雜度主要來自于存儲距離矩陣Dist，其空間復雜度為O(n2)。所以KLS-DBSCAN算法總的空間復雜度為O(n2)+O(n2)。

綜上所述，KLS-DBSCAN算法的復雜度比傳統的DBSCAN算法略有提升，但是保證了在一般場景情況下聚類的準確率。

5 結束語

傳統的DBSCAN算法對參數的選擇十分敏感，本文提出改進的自適應參數KLS-DBSCAN密度聚類算法，通過數學統計方法，建立數學模型，自動選擇全局最優的Eps和MinPts兩個參數。實驗表明，本文算法實現了參數的自適應選擇，同時準確率平均提高6.1%。但也存在不足之處：提高了聚類準確率的同時也犧牲了時間復雜度；對于密度差異大，維度比較高的數據集聚類效果一般。有效解決這些問題是下一步研究的方向。