多密度自適應確定DBSCAN算法參數的算法研究

萬 佳，胡大裟，蔣玉明

1.四川大學 計算機學院，成都 610065

2.四川省大數據分析與融合應用技術工程實驗室，成都 610065

數據挖掘指從數據中發現知識，其目的是從大量數據中發現有價值的隱含信息。目前，隨著互聯網技術的快速發展，數據呈爆炸式增長，人們迎來了大數據時代。在大數據的眾多方向中，聚類分析是數據挖掘重要的研究方向之一。聚類分析研究的是無監督模式識別問題，它在圖像分析、遙感、生物信息學和文本分析等領域都有應用[1]。聚類主要用于將數據分組為有用的簇，使得每個簇內的對象相似度高，簇間相似度低。聚類算法在傳統上可以分為基于劃分的方法、基于層次的方法、基于模型的方法、基于密度的方法和基于網格的方法。

基于劃分的方法中，k-means[2]算法是經典的聚類算法，該算法經過多次迭代找到最佳聚類中心，再根據樣本點到聚類中心的距離對樣本進行劃分。由于該算法是將樣本分配到最近的簇中，因此不能發現任意形狀的簇，并且容易陷入局部最優，導致聚類結果不穩定。

在基于密度的聚類中，DBSCAN[3]是一種經典的聚類算法，可以將高密度區域劃分為簇，并在含有噪聲的數據集中實現任意形狀的聚類。但是該算法存在兩方面的問題，首先需要在無先驗知識的情況下人工指定Eps（Epsilon）和MinPts（Minimum Points）這兩個參數，且參數選取對聚類結果影響很大，另外，DBSCAN算法在密度分布不均勻的數據集上，聚類效果不佳。許多學者對DBSCAN算法進行了各種研究和改進。文獻[4]提出了VDBSCAN算法，它使用k-dist圖對不同密度選擇合適的參數，找到具有不同密度的簇。文獻[5]提出了一種基于改進的元啟發算法MVO（multi-verse optimizer）的參數確定方法，該方法可以快速找到DBSCAN算法的最高聚類精度以及精度最高的Eps對應的區間。Kim等[6]提出AA-DBSCAN算法，基于四叉樹的結構來定義密度層次，實現不均勻密度數據集的聚類。Bryant等[7]提出RNN-DBSCAN算法，該算法使用逆近鄰計數作為密度的估計，改進了密度分布差異大的數據集的聚類效果。文獻[8]提出一種新的基于相似性度量的改進DBSCAN算法，更好地刻畫了數據集的分布特征。文獻[9]提出了一種自適應選擇DBSCAN參數的KLS-DBSCAN算法，該算法利用數據自身的分布特點找出合理的參數范圍，再通過尋找聚類內部度量最大值的方法確定最佳參數。李文杰[10]等提出KANN-DBSCAN算法，該算法能夠實現聚類過程的全自動化并且能夠選擇合理的參數，得到高準確度的聚類結果，但在密度分布差異大的數據集上效果較差。

鑒于此，本文提出了一種多密度自適應確定DBSCAN算法參數的MDA-DBSCAN算法，該算法通過去噪衰減后的數據集自身分布特性生成初始候選Eps和MinPts參數列表，并在簇類結果趨于穩定時得到初始密度閾值，之后對該密度閾值條件下識別出的噪聲數據進行相同操作，得到新密度閾值，最終合并不同密度閾值下的聚類結果，整個聚類過程無需人為干預，且聚類效果在密度分布差異大的數據集上得到了明顯的提升。

1 相關定義

DBSCAN算法是1996年由Ester[11]提出的基于密度的空間聚類算法，為了準確描述該算法，給出以下定義。

定義1（Eps鄰域）一個數據對象p,p的鄰域NEps(p)定義為以p為中心，以Eps為半徑的區域內，即：

其中，D為數據集；dist(p,q)表示D中兩個數據對象p和q之間的距離；NEps(p)包含了數據集D中與對象p距離不大于Eps的所有對象。

定義2（核心點和邊界點）對于數據對象p∈D，設定MinPts閾值，若|NEps(p)|≥MinPts，則稱p為核心點；非核心點但在某核心點的Eps鄰域內的對象稱為邊界點。

定義3（直接密度可達）若p在點q的Eps鄰域內，即p∈NEps(q)，且對象q是核心點，即|NEps(q)|≥MinPts，則稱對象p是從對象q密度直達的。

定義4（密度可達）給定數據集D，當存在對象p1,p2,…,pn∈D，對于pi∈D(0

定義5（密度相連）若存在對象r∈D，使得對象p和q是從r密度可達的，那么稱對象p和q密度相連。密度相連是對稱的。

定義6（簇和噪聲）由任意一個核心點對象開始，從該對象密度可達的所有對象構成一個簇，不屬于任何簇的對象為噪聲。

定義7（密度閾值）給定(Eps,MinPts)，以Eps為半徑的圓內存在MinPts個數據點，即：

其中，Density為密度閾值[10]。

2 多密度自適應確定DBSCAN算法參數

2.1 基本思想

KANN-DBSCAN算法利用數據集自身的空間分布特性，基于K-平均最近鄰算法和數學期望法生成Eps和MinPts參數列表。該算法存在兩個問題：（1）K-平均最近鄰得到的平均值容易受到噪聲數據的影響從而導致生成的參數列表存在誤差；（2）由于DBSCAN算法自身的不足，KANN-DBSCAN算法對密度分布差異較大的數據集進行聚類時存在一定的誤差，導致聚類結果簇數和數據集類別數不一致的情況出現[10]。為了更好地闡述和解決問題，本文假設密度分布差異大的數據集中密集分布的數據比稀疏分布的數據多。

針對問題（1），在密集分布的數據較多的情況下，KANN-DBSCAN算法得到的參數會偏向密集分布的簇進行聚類，在聚類過程中，密集數據的參數取值會受到噪聲數據的影響，即在計算數據點之間的距離時，噪聲點也會參與，涉及到該點的距離會偏大，這使得之后計算出的平均值也偏大，最后導致自適應生成的Eps參數列表的值偏大，所以在密度分布差異大的數據集中，該算法自適應選取的參數不夠準確。Eps的值偏大，可能導致不同簇類之間被合并，所以為了在密度分布差異大的數據集中選取合適的參數，需要對K-平均最近鄰算法得到的Eps參數列表進行二次處理，使其更符合數據的自身分布特性。處理了Eps后，密度閾值會發生改變，為了使其穩定，同時處理數學期望法生成的MinPts列表。本文通過給K-平均最近鄰算法和數學期望法增設自衰減項，使得生成的Eps和MinPts列表的值同時減小，從而減少噪聲數據對參數自適應生成的影響，優化密度閾值的生成。

針對問題（2），KANN-DBSCAN算法的密度閾值是作用于全局的，這使得稀疏數據形成的簇被識別為噪聲，為了正確地識別簇，本文引入多密度閾值Density_i參數概念，如式（3）：

其中，Epsi和MinPtsi為第i次自適應選取的參數，Density_1為第1次自適應選取的參數生成的初始密度閾值，Density_2為在Density_1下聚類產生的噪聲數據的密度閾值，Density_3為在Density_2下聚類產生的噪聲數據的密度閾值，以此類推，直到噪聲數據數量或生成的密度閾值低于一定程度為止，最后將所有密度閾值下的聚類結果進行合并。

2.2 算法設計

MDA-DBSCAN算法的關鍵是能夠在密度分布差異大的數據集上自適應確定具有不同密度的簇的最優密度閾值。本文提出利用數據分布特性，基于自衰減項的K-平均最近鄰算法（K-average nearest neighbor with attenuation term）和自衰減數學期望法生成密度閾值。

為了方便描述該算法，以圖1數據集為例，該數據集是一個含有4種類別共582個對象的二維數據集。數據集中有三個密集的簇C1、C2和C3，包含477個對象，一個稀疏的簇C4，包含85個對象，以及一些噪聲點，包含20個對象。其中C1、C2和C3在同一密度閾值下，且C2和C3簇間間距較小，C4屬于另一個密度閾值。綜上，該數據集的特點包括：（1）存在密度分布差異大的簇；（2）存在簇間間距小的簇；（3）含有一定數量的噪聲點。該數據集的分布與本文要解決的兩個問題一致。下文以該數據集為例進行具體分析。

圖1 數據集散點圖(N=582,C=4)Fig.1 Data point diagram(N=582,C=4)

2.2.1 自衰減生成Eps參數列表

采用基于自衰減項的K-平均最近鄰法生成Eps列表，其中K-平均最近鄰法是平均最近鄰法的拓展，該算法是計算數據集D中每個數據點與其第K個最近的數據點之間的K-最近鄰距離，并對所有數據點的K-最近鄰距離求平均值，得到數據集的K-平均最近鄰距離。生成參數列表的具體步驟如下：

步驟1計算數據集D中每個點到其他點的歐氏距離，形成距離分布矩陣Distn×n，如式（4）：

其中，n是D中的數據點個數；dist(i,j)是數據集中點i和點j之間的距離；Distn×n是n×n的實對稱矩陣。

步驟2將Distn×n的每一行元素進行升序排序。

步驟3對排序后矩陣Distn×n的第K(1≤K≤n)列求平均值，得到----DK，減去自衰減項后，將其作為候選Eps參數。如式（5）：

其中，λ是自衰減系數，0≤λ≤1，本文λ取值為0.3。對所有的K值計算完畢后，得到Eps參數列表，如式（6）：

圖2為圖1數據集分別在KANN-DBSCAN算法和MDA-DBSCAN算法下生成的Eps參數列表對比曲線，可見本文提出的算法可以平穩降低Eps參數的值，從而減少數據噪聲的影響，以得到更優的Eps參數列表。

圖2 Eps參數列表對比圖Fig.2 Comparison diagram of Eps parameter list

2.2.2 自衰減生成MinPts參數列表

采用基于自衰減項的數學期望法生成MinPts列表。如式（7）：

其中，λ是自衰減系數，0≤λ≤1,n為數據集中的對象總數，Pi是第i個對象的Eps鄰域內鄰域對象數量。對所有的K值計算完畢后，得到MinPts參數列表，如式（8）：

圖3為圖1數據集分別在KANN-DBSCAN算法和MDA-DBSCAN算法下生成的MinPts參數列表對比曲線。

圖3 MinPts參數列表對比圖Fig.3 Comparison diagram of MinPts parameter list

2.2.3 多密度自適應確定最優參數

對于圖1數據集，KANN-DBSCAN算法根據數據自身分布特性得到的Eps參數會受到噪聲數據的影響而偏大，這可能導致簇間間距較小的不同簇類被識別為一個簇，比如簇C2和簇C3，另外，由于參數的全局性，稀疏簇C4會被識別為噪聲，如圖4（a）所示。本文設計的算法能夠減少噪聲數據的影響，得到優化后的初始密度閾值Density_1，使得簇C2和簇C3能正確地被識別為不同的簇。具體做法如下文。

圖4 密度閾值的優化Fig.4 Optimization of density threshold

首先通過自衰減改進后的方法得到Eps和MinPts參數列表，選取第K個參數對(1≤K≤n)，即(EpsK,MinPtsK)，輸入DBSCAN算法，對數據集進行聚類分析，得到聚類結果簇數與K值的關系如圖5所示。

圖5 聚類結果簇數與K值的關系圖Fig.5 Relational diagram of K value and number of clusters of clustering results

當聚類結果的簇數趨于穩定時通過K值反向選取最優參數。本文對結果趨于穩定進行了重新定義，X表示聚類結果簇數相同的連續次數：（1）當連續X（本文設定初始值為5）次相同時，認為聚類結果趨于穩定，得到穩定區間（第一個即可），記該簇數為最優簇數。若聚類結果不存在連續X次相同的簇數，則尋找連續X-1次相同的簇數；（2）若（1）中連續三次相同的簇數都找不到，則改為尋找簇數波動范圍在1內的穩定區間。

找到穩定區間后，得到區間端點startK和endK，本文根據識別噪聲程度的需求來選取穩定區間中的K值，通過設置噪聲等級level來實現，設有三個噪聲等級：less（少噪聲）、normal（正常噪聲）和more（多噪聲，默認值）。K值選取如式（9）所示。一般在密度分布均勻的數據集上設置噪聲等級為less，在密度分布差異大的數據集上設置噪聲等級為more，其余情況設置為normal。

利用上述定義對圖1數據集進行分析，如圖5所示，當K=4時，進入穩定區間，直到K=47結束，因此選取K值為4，其對應的Eps1=7.813,MinPts1=8。將該最優參數輸入DBSCAN算法，得到Density_1下的聚類結果如圖4（b）所示，與圖4（a）KANN-DBSCAN算法的聚類結果比較，本文算法能夠正確地識別簇C2和簇C3，將它們歸為不同簇類，可見本文算法處理噪聲數據的有效性。

之后抽取Density_1下聚類后的噪聲數據，即稀疏簇C4和噪聲點，共105個對象，通過同樣的方式自適應確定其最優參數，得到新密度閾值Density_2，此時Eps2=12.267,MinPts2=3,Density_2下噪聲數據的聚類結果如圖6（a），然后抽取Density_2下聚類后的噪聲數據，共21個對象，不滿足本文設定的最小噪聲數量（50），結束聚類，最后將Density_1和Density_2下的聚類結果合并得到如圖6（b）所示結果，聚類結果簇數與數據集標識類別一致，可見本文算法處理密度分布差異大的數據集的有效性。

圖6 基于MDA-DBSCAN的聚類結果Fig.6 Clustering results based on MDA-DBSCAN

3 實驗與結果分析

MDA-DBSCAN算法采用Python3.7實現，實驗環境為64位的Windows10系統，實驗運行在i7-10710U，CPU為1.1 GHz，內存16 GB的筆記本上。為了進一步驗證本文算法的有效性和先進性，在人工數據集和UCI數據集上進行了聚類分析，將本文算法得到的結果與DBSCAN、KANN-DBSCAN、RNN-DBSCAN算法進行比較。其中，本文算法需要提供的參數：多密度閾值Density_i(Di)。DBSCAN算法和KANN-DBSCAN算法都需要設定兩個參數：半徑Eps和最小樣本數MinPts。RNN-DBSCAN算法需要設定一個參數：點的鄰居數K。表1顯示了四種算法在人工數據集上的較優參數的設置。

表1 人工數據集上的參數設置Table 1 Parameter settings on artificial data sets

3.1 人工數據集

本文選用8組人工數據集進行實驗，包括密度分布均勻和不均勻的數據集，并用F值[12]對結果進行分析，F值綜合了準確率和召回率，取值范圍在[0，1]，越接近1表示聚類效果越好。數據集的詳細信息見表2。

表2 人工數據集Table 2 Artificial datasets

圖7為本文算法與其他算法在不同人工數據集上的聚類結果，可見MDA-DBSCAN算法不僅在密度分布均勻的數據集上有效，而且在密度分布差異大的數據集上也有很好的聚類效果。

圖7 （續）

圖7 聚類結果對比Fig.7 Comparison of clustering results

從聚類結果簇數來看，MDA-DBSCAN算法最為準確，即聚類結果簇數與數據集類別數一致。從F值評價指標來看，在密度分布均勻的數據集（Aggregation、Spiral、Flame、R15和D31）上，MDA-DBSCAN算法與其他算法的差異不大，都有較優的結果，但在密度分布差異大的數據集（Compound、Jain和Pathbased）上，MDADBSCAN算法的優勢明顯，具有更高的準確性。表3是幾種算法的聚類結果簇數和指標評價。

表3 聚類結果簇數和指標評價Table 3 Cluster number of clustering results and index evaluation

3.2 UCI數據集

為了驗證MDA-DBSCAN算法在真實數據集上的性能，對UCI數據集進行聚類分析，并采用準確率（ACC）[13]、互信息（AMI）[14]和調整蘭德系數（ARI）[15]作為評價指標，其中ACC的取值范圍在[0，1]，AMI和ARI的取值范圍在[-1,1]，值越接近1說明與真實聚類結果越符合。數據集詳細信息如表4所示。

表4 UCI數據集Table 4 UCI datasets

真實數據集聚類指標如表5所示，可以看出本文算法克服了傳統算法的人工選取參數的主觀性，并在高維數據集上有良好的表現。KANN-DBSCAN算法雖然在二維的人工數據集上有較好的表現，但是在高維UCI數據集上表現一般，因為在分布不均的高維UCI數據集上很難進入連續三次相同的簇數穩定區間，導致聚類結果出現較大誤差。本文算法在利用數據集自身分布特性確定密度閾值前對數據集進行了去噪衰減，減少了噪聲數據的影響，并且重新制定了穩定區間的選取策略，能夠得到更符合數據特性的密度閾值，并進行多次密度閾值計算，合并所有聚類結果，從而提升聚類效果。

表5 聚類指標對比Table 5 Comparison of clustering index

4 結束語

DBSCAN算法可以有效識別噪聲并實現任意形狀的聚類，但是該算法對參數的選取敏感，取值不當會導致聚類效果不佳，且由于參數的全局性，該算法在密度分布步不均勻的數據集上不能正確地識別簇。本文在KANN-DBSCAN算法的基礎上，引入了去噪衰減、多密度閾值以及合并聚類的概念，用例子演示了算法具體實現步驟，通過自衰減項與平均最近鄰和數學期望法結合生成改進的參數列表，找到最優初始密度閾值，得到聚類結果和噪聲數據，對噪聲數據進行相同操作直到其數量或密度閾值不滿足條件為止，最后將所有密度閾值下的聚類結果進行合并。實驗表明，本文算法可以自適應確定具有不同密度的簇的最優密度閾值，在密度分布不均勻的數據集上有很好的聚類結果，但算法時間復雜度較高，如何有效降低算法時間復雜度是以后工作的重點。