王 光，林國宇

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

1 引言

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

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

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

2 DBSCAN算法

DBSCAN算法由Ester M、Kriegel H P等人[9]在1996年提出，它不需要預先指定簇的個數(shù)，但需要給定兩個參數(shù)。該算法是基于一組：“鄰域”參數(shù)(Eps,MinPts)來描述樣本分布的緊密度，假設給定數(shù)據(jù)集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（簇和噪聲）從數(shù)據(jù)集D中任取一點 p，從p點開始在D中搜索滿足Eps和MinPts條件且密度可達的所有點構成一個簇，不屬于任何簇的對象則被標記為噪聲點。

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

3 自適應確定DBSCAN算法參數(shù)

3.1 基本思想

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

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

3.2 確定參數(shù)Eps和MinPts的合理區(qū)間

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

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

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

在弱假設下：

其中：

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

其中m、R根據(jù)核函數(shù)確定。

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

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

圖1 SampleD的數(shù)據(jù)點分布圖

圖2 核密度估計曲線圖

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

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

3.3 確定聚類簇數(shù)

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

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

局部密度 ρi：

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

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

圖3 聚類中心決策圖

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

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

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

3.4 參數(shù)尋優(yōu)

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

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

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

3.5KLS-DBSCAN算法描述

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

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

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

（4）利用最優(yōu)的Eps和MinPts進行聚類。

具體計算過程如下所示。

算法 KLS-DBSCAN算法

輸入：Eps的區(qū)間(eps_list)、Minpts的區(qū)間(Minpts_list)、最優(yōu)的聚類個數(shù)(label_num)。

計算：

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

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

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

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

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

輸出：全局最優(yōu)的Eps和MinPts。

4 實驗及結果分析

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

4.1 人工數(shù)據(jù)集的準備及實驗

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

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

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

4.2 真實數(shù)據(jù)集的實驗結果及分析

圖5 人工數(shù)據(jù)集散點圖

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

表1 人工數(shù)據(jù)集聚類指標對比

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

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

表2 真實數(shù)據(jù)集聚類指標對比

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

4.3 算法復雜度分析

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

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

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

5 結束語

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