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

萬(wàn) 佳，胡大裟，蔣玉明

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

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

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

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

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

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

1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

2.1 基本思想

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

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

針對(duì)問(wèn)題（2），KANN-DBSCAN算法的密度閾值是作用于全局的，這使得稀疏數(shù)據(jù)形成的簇被識(shí)別為噪聲，為了正確地識(shí)別簇，本文引入多密度閾值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è)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

MDA-DBSCAN算法采用Python3.7實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為64位的Windows10系統(tǒng)，實(shí)驗(yàn)運(yùn)行在i7-10710U，CPU為1.1 GHz，內(nèi)存16 GB的筆記本上。為了進(jìn)一步驗(yà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è)定兩個(gè)參數(shù)：半徑Eps和最小樣本數(shù)MinPts。RNN-DBSCAN算法需要設(shè)定一個(gè)參數(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í)驗(yàn)，包括密度分布均勻和不均勻的數(shù)據(jù)集，并用F值[12]對(duì)結(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é)果對(duì)比Fig.7 Comparison of clustering results

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

表3 聚類結(jié)果簇?cái)?shù)和指標(biāo)評(píng)價(jià)Table 3 Cluster number of clustering results and index evaluation

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

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

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

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

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

4 結(jié)束語(yǔ)

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