萬 佳，胡大裟，蔣玉明

1.四川大學(xué) 計算機(jī)學(xué)院，成都 610065

2.四川省大數(shù)據(jù)分析與融合應(yīng)用技術(shù)工程實驗室，成都 610065

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

基于劃分的方法中，k-means[2]算法是經(jīng)典的聚類算法，該算法經(jīng)過多次迭代找到最佳聚類中心，再根據(jù)樣本點(diǎn)到聚類中心的距離對樣本進(jìn)行劃分。由于該算法是將樣本分配到最近的簇中，因此不能發(fā)現(xiàn)任意形狀的簇，并且容易陷入局部最優(yōu)，導(dǎo)致聚類結(jié)果不穩(wěn)定。

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

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

1 相關(guān)定義

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

定義1（Eps鄰域）一個數(shù)據(jù)對象p,p的鄰域NEps(p)定義為以p為中心，以Eps為半徑的區(qū)域內(nèi)，即：

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

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

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

定義4（密度可達(dá)）給定數(shù)據(jù)集D，當(dāng)存在對象p1,p2,…,pn∈D，對于pi∈D(0

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

定義6（簇和噪聲）由任意一個核心點(diǎn)對象開始，從該對象密度可達(dá)的所有對象構(gòu)成一個簇，不屬于任何簇的對象為噪聲。

定義7（密度閾值）給定(Eps,MinPts)，以Eps為半徑的圓內(nèi)存在MinPts個數(shù)據(jù)點(diǎn)，即：

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

2 多密度自適應(yīng)確定DBSCAN算法參數(shù)

2.1 基本思想

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

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

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

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

2.2 算法設(shè)計

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

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

圖1 數(shù)據(jù)集散點(diǎn)圖(N=582,C=4)Fig.1 Data point diagram(N=582,C=4)

2.2.1 自衰減生成Eps參數(shù)列表

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

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

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

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

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

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

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

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

2.2.2 自衰減生成MinPts參數(shù)列表

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

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

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

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

2.2.3 多密度自適應(yīng)確定最優(yōu)參數(shù)

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

圖4 密度閾值的優(yōu)化Fig.4 Optimization of density threshold

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

圖5 聚類結(jié)果簇數(shù)與K值的關(guān)系圖Fig.5 Relational diagram of K value and number of clusters of clustering results

當(dāng)聚類結(jié)果的簇數(shù)趨于穩(wěn)定時通過K值反向選取最優(yōu)參數(shù)。本文對結(jié)果趨于穩(wěn)定進(jìn)行了重新定義，X表示聚類結(jié)果簇數(shù)相同的連續(xù)次數(shù)：（1）當(dāng)連續(xù)X（本文設(shè)定初始值為5）次相同時，認(rèn)為聚類結(jié)果趨于穩(wěn)定，得到穩(wěn)定區(qū)間（第一個即可），記該簇數(shù)為最優(yōu)簇數(shù)。若聚類結(jié)果不存在連續(xù)X次相同的簇數(shù)，則尋找連續(xù)X-1次相同的簇數(shù)；（2）若（1）中連續(xù)三次相同的簇數(shù)都找不到，則改為尋找簇數(shù)波動范圍在1內(nèi)的穩(wěn)定區(qū)間。

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

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

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

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

3 實驗與結(jié)果分析

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

表1 人工數(shù)據(jù)集上的參數(shù)設(shè)置Table 1 Parameter settings on artificial data sets

3.1 人工數(shù)據(jù)集

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

表2 人工數(shù)據(jù)集Table 2 Artificial datasets

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

圖7 （續(xù)）

圖7 聚類結(jié)果對比Fig.7 Comparison of clustering results

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

表3 聚類結(jié)果簇數(shù)和指標(biāo)評價Table 3 Cluster number of clustering results and index evaluation

3.2 UCI數(shù)據(jù)集

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

表4 UCI數(shù)據(jù)集Table 4 UCI datasets

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

表5 聚類指標(biāo)對比Table 5 Comparison of clustering index

4 結(jié)束語

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