基于離群點(diǎn)檢測(cè)和自適應(yīng)參數(shù)的三支DBSCAN算法

摘 要：針對(duì)經(jīng)典的DBSCAN算法存在難以確定全局最優(yōu)參數(shù)和誤判離群點(diǎn)的問(wèn)題，該算法首先從選擇最優(yōu)參數(shù)角度出發(fā)，通過(guò)數(shù)據(jù)集的分布特征生成Eps和MinPts列表，將兩個(gè)列表中的參數(shù)進(jìn)行全組合操作，把不同的參數(shù)組合依次進(jìn)行聚類，從而尋找準(zhǔn)確率最高點(diǎn)對(duì)應(yīng)的參數(shù)。最后從離群點(diǎn)角度出發(fā)，將三支決策思想與離群點(diǎn)檢測(cè)LOF算法進(jìn)行結(jié)合。該算法與多種聚類算法進(jìn)行效果對(duì)比分析，結(jié)果表明該算法能夠全自動(dòng)化選擇全局最優(yōu)參數(shù)，并提高聚類算法的準(zhǔn)確性。

關(guān)鍵詞：DBSCAN算法； 三支聚類； 自適應(yīng)參數(shù)； 離群點(diǎn)檢測(cè)

中圖分類號(hào)：TP393.09 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2024）07-011-1999-06

doi：10.19734/j.issn.1001-3695.2023.11.0569

Three-ways DBSCAN algorithm based on outlierdetection and adaptive parameters

Abstract：Aiming at the problems of the classical DBSCAN algorithm that it is difficult to determine the global optimal para-meters and misjudge the outliers， the algorithm firstly started from the perspective of selecting the optimal parameters， generated the Eps and MinPts lists by the distribution characteristics of the data set， and then carried out the full combination operation of the parameters in the two lists， and then performed the clustering of the different combinations of the parameters in order， so as to search for the parameter corresponding to the point of the highest accuracy rate. Finally， from the perspective of outlier， the three-branch decision-making idea was combined with the outlier detection LOF algorithm. This algorithm was compared and analysed with a variety of clustering algorithms， and the results show that this algorithm can achieve the fully automated selection of the global optimal parameters as well as improve the accuracy of the clustering algorithm.

Key words：DBSCAN algorithm; three-ways clustering; adaptive parameters; outlier detection

0 引言

互聯(lián)網(wǎng)的快速發(fā)展導(dǎo)致每天都會(huì)產(chǎn)生海量的數(shù)據(jù)，如何從海量數(shù)據(jù)中準(zhǔn)確地找出有價(jià)值的數(shù)據(jù)，是當(dāng)今研究的方向之一[1]。聚類分析是數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)重要技術(shù)，已經(jīng)廣泛地成功應(yīng)用于多個(gè)領(lǐng)域，其中包括圖像處理[2]、統(tǒng)計(jì)學(xué)[3]、知識(shí)圖譜[4]、醫(yī)療健康[5]等。

傳統(tǒng)的DBSCAN聚類都屬于硬聚類，即對(duì)象要么確定屬于某個(gè)類，要么確定不屬于某個(gè)類，傳統(tǒng)聚類結(jié)果中類簇之間必須具有清晰的邊界。當(dāng)處理具有不確定性的數(shù)據(jù)對(duì)象時(shí)，硬聚類會(huì)強(qiáng)制地將其中的數(shù)據(jù)劃分到某一個(gè)類中，通常會(huì)導(dǎo)致聚類結(jié)果出現(xiàn)較高的錯(cuò)誤率。為了解決上述存在的問(wèn)題。H-ppner等人[6]將模糊集思想與聚類分析相結(jié)合，提出了模糊聚類方法。Lingras等人[7]提出粗糙集思想并應(yīng)用到聚類中，通過(guò)粗糙集的正域、邊界域和負(fù)域的概念來(lái)表示聚類的最終結(jié)果。對(duì)于三支聚類方法，是將三支決策理論[8]融入到了聚類方法中。對(duì)于相同的類簇，將確定的對(duì)象劃分到核心域中，將不確定的對(duì)象劃分到邊界域中，這樣劃分有效地降低了聚類過(guò)程中的錯(cuò)誤率。

針對(duì)數(shù)據(jù)集中判斷離群點(diǎn)的問(wèn)題，許多學(xué)者也提出了相應(yīng)的研究方法。Shaith等人[9]在具有混合屬性數(shù)據(jù)集中提出有關(guān)離群點(diǎn)檢測(cè)的方法。該方法主要根據(jù)數(shù)據(jù)對(duì)象屬性的質(zhì)心以及分類屬性的頻率來(lái)判斷數(shù)據(jù)之間的差別，但該方法需要再一次研究并定義新的距離度量方式，來(lái)判斷不同數(shù)據(jù)之間的差異性。鄒云峰等人[10]提出了LDBO算法，該算法使用了強(qiáng)Ｋ近鄰點(diǎn)和弱Ｋ近鄰點(diǎn)的方法來(lái)處理具有異常數(shù)據(jù)分布的離群點(diǎn)問(wèn)題。但是，基于密度的離群點(diǎn)判斷則需要復(fù)雜的距離計(jì)算公式，在高維數(shù)據(jù)中，該算法的效果并不理想。緱鵬飛等人[11]提出了ANGOD算法，該算法根據(jù)計(jì)算節(jié)點(diǎn)的距離度量，構(gòu)造出自適應(yīng)鄰居圖并提取數(shù)據(jù)特征，進(jìn)而識(shí)別數(shù)據(jù)集中的離群點(diǎn)，但其存在處理某些結(jié)構(gòu)化數(shù)據(jù)集準(zhǔn)確率不理想的問(wèn)題。雖然許多算法對(duì)離群點(diǎn)檢測(cè)LOF算法都進(jìn)行了改進(jìn)，但依舊強(qiáng)制性判斷數(shù)據(jù)對(duì)象是否為離群點(diǎn)，這對(duì)于數(shù)據(jù)集中不確定信息的判斷是不準(zhǔn)確的。依據(jù)上述判斷不確定性信息的問(wèn)題，本文將三支決策思想融入到LOF算法中，利用邊界域來(lái)對(duì)具有不確定性的離群點(diǎn)作進(jìn)一步的判斷，提高針對(duì)判斷離群點(diǎn)的準(zhǔn)確性。

由于DBSCAN聚類算法依賴兩個(gè)參數(shù)才能實(shí)現(xiàn)聚類的全過(guò)程，參數(shù)的選擇要人為輸入，所以參數(shù)的選擇具有主觀性，不同的參數(shù)會(huì)導(dǎo)致聚類結(jié)果的不同，自適應(yīng)選取參數(shù)也是聚類研究的方向之一。周治平等人[12]提出的AF-DBSCAN算法是根據(jù)k距離的曲線、描述數(shù)據(jù)對(duì)象的全局分布，該方法會(huì)存在一定的誤差。Hu等人[13]依據(jù)反向最近鄰和影響空間的判斷條件，提出了KR-DBSCAN算法，該算法根據(jù)條件判斷不同密度間的相鄰類簇。Yu等人[14]利用縮放函數(shù)，將距離矩陣進(jìn)行規(guī)范化操作，并將改進(jìn)的DBSCAN算法與三支決策理論相結(jié)合，提出了3W-DBSCAN算法。王光等人[15]提出自適應(yīng)選擇參數(shù)的方法并應(yīng)用到DBSCAN算法中，得到KLS-DBSCAN聚類算法。該算法根據(jù)數(shù)據(jù)集中數(shù)據(jù)的分布特點(diǎn)計(jì)算出參數(shù)范圍，再根據(jù)聚類內(nèi)部度量的最大值來(lái)確定全局最優(yōu)參數(shù)值，但該方法對(duì)于多密度的數(shù)據(jù)集聚類效果一般。申秋萍等人[16]提出基于局部半徑的三支DBSCAN聚類算法，雖然該算法自適應(yīng)Eps參數(shù)，但是仍然需要人為手動(dòng)輸入MinPts參數(shù)和近鄰次序k。蘭紅等人[17]提出HODG-DBSCAN算法，使用高階差分算法自動(dòng)獲取聚類參數(shù)，并利用網(wǎng)格劃分方法構(gòu)建索引。該算法雖然實(shí)現(xiàn)了聚類全自動(dòng)化并提高了聚類算法的效率，但針對(duì)多密度的數(shù)據(jù)集，依舊存在準(zhǔn)確率較低的問(wèn)題。

依據(jù)上述問(wèn)題，本文提出一種基于離群點(diǎn)檢測(cè)和自適應(yīng)參數(shù)的三支DBSCAN聚類算法，本文簡(jiǎn)稱為AL3W-DBSCAN算法。該算法首先根據(jù)數(shù)據(jù)對(duì)象的分布特點(diǎn)來(lái)計(jì)算相應(yīng)的參數(shù)列表，對(duì)于列表中的待選參數(shù)進(jìn)行全組合的操作，目的是增加參數(shù)選擇的可能性，以便找出全局最優(yōu)參數(shù)。其次是針對(duì)DBSCAN算法中判斷離群點(diǎn)的問(wèn)題，將三支決策思想與離群點(diǎn)檢測(cè)算法相結(jié)合，利用三支決策中的邊界域來(lái)存放不確定性的離群點(diǎn)，從而進(jìn)行進(jìn)一步的判斷。本文算法實(shí)現(xiàn)了聚類參數(shù)的自適應(yīng)選擇，并提高了聚類算法的準(zhǔn)確性。

1 相關(guān)工作

1.1 LOF算法

2000年由慕尼黑大學(xué)的Breunig等人[18]提出有關(guān)LOF離群點(diǎn)檢測(cè)算法的思想。LOF算法的核心思想為：通過(guò)算法將數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)對(duì)象都賦予一個(gè)孤立程度的數(shù)值。下面將介紹LOF算法的有關(guān)基本概念，如圖1所示。

定義1 p的第k距離。對(duì)任意的正整數(shù)k，定義對(duì)象p的第k距離為p與某個(gè)對(duì)象q之間的距離，記為k-distance（p），用d（p，q）表示對(duì)象p到對(duì)象q的距離，則對(duì)象q要滿足存在至少k個(gè)對(duì)象q′∈U＼{p}，滿足d（p，q′）≤d（p，q）。

定義2 p的第k距離鄰域。已知數(shù)據(jù)對(duì)象p的第k距離k-distance（p），滿足與對(duì)象p之間的距離小于等于k-distance（p）的所有數(shù)據(jù)對(duì)象的集合，即

Nk（p）={q∈U|d（p，q）≤k-distance（p）}（1）

定義3 p與q的可達(dá)距離。是指對(duì)象p與q之間的距離和對(duì)象q的k-distance（p）之間的最大值，其中對(duì)象q∈Nk（p），即

reach-dist（p，q）=max{q∈U|k-distance（p），d（p，q）}（2）

定義4 p的局部可達(dá)密度。定義對(duì)象p與它的Nk（p）內(nèi)各對(duì)象的平均可達(dá)距離之和的倒數(shù)，即

定義5 局部異常因子（LOF）。表示對(duì)象p在k-distance（p）鄰域內(nèi)的孤立程度，即

iVMh1/TFpwWIHcpgGUjkoA==通過(guò)LOF算法計(jì)算得到的孤立程度越大，表示數(shù)據(jù)對(duì)象越有可能是離群點(diǎn)。孤立值越小，表示數(shù)據(jù)對(duì)象的孤立程度越小，越不可能是離群點(diǎn)。

1.2 DBSCAN聚類算法

DBSCAN算法[19]是一種基于密度的經(jīng)典聚類方法，該算法通過(guò)將符合一定密度條件的數(shù)據(jù)對(duì)象分配到一個(gè)類簇中，其具備挖掘任意形狀的類簇以及對(duì)離群點(diǎn)不敏感的優(yōu)勢(shì)。DBSCAN相關(guān)概念如圖2所示。

定義6 p的Eps鄰域。對(duì)象p的Eps鄰域NEps（p）是指以對(duì)象p為圓心，在d維空間內(nèi)小于等于Eps參數(shù)的所有數(shù)據(jù)對(duì)象的數(shù)量，即NEps（p）={q∈U|dist（p，q）≤Eps}，其中U為數(shù)據(jù)集，對(duì)象p和q之間的距離用dist（p，q）表示。

定義7 核心數(shù)據(jù)對(duì)象。根據(jù)參數(shù)Eps和MinPts，如果p的Eps鄰域內(nèi)對(duì)象數(shù)量滿足 |NEps（p）|≥MinPts的條件，則稱p為核心對(duì)象。

定義8 直接密度可達(dá)。數(shù)據(jù)集中存在任意數(shù)據(jù)對(duì)象p和q，如果對(duì)象q滿足q∈NEps（p）且|NEps（p）|≥MinPts，則稱q是從p根據(jù)參數(shù)Eps、MinPts直接密度可達(dá)的。

定義9 密度可達(dá)。數(shù)據(jù)集中存在任意數(shù)據(jù)對(duì)象q和p，如果數(shù)據(jù)對(duì)象排列符合p1，p2，…，pn∈U，其中p1=p，pn=q，并且pi+1是根據(jù)pi直接密度可達(dá)的條件，則稱對(duì)象q是從對(duì)象p密度可達(dá)的。

定義10 密度相連。在數(shù)據(jù)集U中，假設(shè)對(duì)象a為起點(diǎn)，存在對(duì)象p和q都是與對(duì)象a密度可達(dá)的，則認(rèn)為對(duì)象p和q是密度相連的。

1.3 三支聚類

Yao[20，21]在決策粗糙集和概率粗糙集的假設(shè)中提出了三支決策理論，理論核心思想是將決策項(xiàng)擴(kuò)展為正域、邊界域和負(fù)域。正域中的規(guī)則稱為正規(guī)則，表示接收。邊界域中的規(guī)則稱為邊界規(guī)則，表示不做或推遲決定。負(fù)域中的規(guī)則稱為負(fù)規(guī)則，表示不接收。

Yu等人[22]將三支決策理論結(jié)合到聚類方法中，提出了三支聚類方法。三支聚類分別利用三個(gè)互不相交的區(qū)域Cpi、CBi和CNi代表類簇i的核心域、邊界域以及瑣碎域。核心域中的數(shù)據(jù)對(duì)象代表確定劃分到類簇i，邊界域中的數(shù)據(jù)對(duì)象代表不確定是否劃分到類簇i，而瑣碎域中的數(shù)據(jù)對(duì)象代表確定不劃分到類簇i。

與硬聚類的表示相比，本文用二元集合來(lái)表示三支聚類C：

C={Co（C），F(xiàn)r（C）}（5）

CoreRegion（C）=Co（C）FringeRegion（C）=Fr（C）

TrivialRegion（C）=U-Co（C）-Fr（C）（6）

如果x∈CoreRegion（C），則對(duì)象x只屬于類簇C；如果對(duì)象x∈FringeRegion（C），則對(duì)象x可能屬于類簇C；如果x∈TrivialRegion（C），則對(duì)象x不屬于類簇C。

三支聚類中所有類簇都滿足以下性質(zhì)：

此外，通過(guò)上述公式了解到，使用核心域和邊界域就能表示一個(gè)完整的類簇。

在三支聚類結(jié)果中的核心域和邊界域需要滿足不同的條件，具體滿足的條件如下：

條件1描述所有類簇的核心域必須含有數(shù)據(jù)對(duì)象。條件2描述數(shù)據(jù)集合U中的數(shù)據(jù)對(duì)象要么屬于某個(gè)類的核心域，要么屬于某個(gè)類的邊界域。條件3描述類簇之間的核心域不能出現(xiàn)交集，不同核心域中不能存在重復(fù)的樣本對(duì)象。根據(jù)上述的三個(gè)條件，得出三支聚類結(jié)果表達(dá)式為

C={（Co（C1），F(xiàn)r（C1）），…，（Co（Ck），F(xiàn)r（Ck））}（9）

二支聚類與三支聚類的區(qū)別如圖3所示。

1.4 自適應(yīng)確定參數(shù)

在DBSCAN聚類算法過(guò)程中依賴Eps和MinPts兩個(gè)全局參數(shù)，人工指定的Eps和MinPts這兩個(gè)參數(shù)具有主觀性。因此，DBSCAN聚類算法對(duì)參數(shù)的選擇十分敏感，參數(shù)選擇的不同會(huì)導(dǎo)致不同的聚類結(jié)果。

目前，國(guó)內(nèi)外許多學(xué)者對(duì)DBSCAN參數(shù)選擇進(jìn)行了研究，Yue等人[23]提出基于數(shù)據(jù)統(tǒng)計(jì)信息確定Eps參數(shù)的算法，以MinPts參數(shù)固定為4作為前提，在較大的范圍內(nèi)尋找合適的Eps參數(shù)。Jahirabadkar等人[24]依據(jù)對(duì)象在每個(gè)維度的密度情況，相應(yīng)地確定Eps參數(shù)，但MinPts參數(shù)仍然需要人為確定。Kim等人[25]提出AA-DBSCAN聚類算法，利用四叉樹(shù)來(lái)描述數(shù)據(jù)集中每個(gè)維度的密度，但該算法仍沒(méi)有實(shí)現(xiàn)自動(dòng)化。

2 AL3W-DBSCAN算法

2.1 算法設(shè)計(jì)

2.1.1 Eps參數(shù)列表

引入自衰減項(xiàng)的K-平均最近鄰法[26]來(lái)計(jì)算生成Eps參數(shù)列表，該算法的過(guò)程要計(jì)算數(shù)據(jù)集中數(shù)據(jù)對(duì)象到第K個(gè)最近的數(shù)據(jù)對(duì)象之間的歐氏距離，然后依次將Eps矩陣的每一行按照從小到大進(jìn)行排序。第i列表示數(shù)據(jù)點(diǎn)p距離最近的第i個(gè)距離值；對(duì)第i列求平均數(shù)，再將求出的第i個(gè)Eps平均距離添加到Eps參數(shù)列表中，即

通過(guò)上述步驟得到Eps參數(shù)列表DEps，然后將自衰減算法對(duì)Eps參數(shù)列表進(jìn)行處理。自衰減公式為

其中：λ為自衰減系數(shù)，取值是0≤λ≤1，本文中令λ為0.5。自衰減算法處理后的Eps列表將其作為最終候選Eps參數(shù)列表，如下所示：

Eps_list={EpsK|1≤K≤n}（13）

2.1.2 MinPts參數(shù)列表

依據(jù)生成的Eps列表DEps，利用每個(gè)Eps參數(shù)值計(jì)算對(duì)應(yīng)鄰域范圍內(nèi)對(duì)象的數(shù)量以及數(shù)學(xué)期望，得到的MinPts列表再用自衰減對(duì)上述步驟提出新的公式，對(duì)MinPts列表進(jìn)行處理，即

其中：n為數(shù)據(jù)集中數(shù)據(jù)對(duì)象的總數(shù)；λ表示自衰減系數(shù)，0≤λ≤1；Pi為第i個(gè)數(shù)據(jù)的Eps鄰域內(nèi)的數(shù)據(jù)個(gè)數(shù)。通過(guò)計(jì)算得到最終MinPts參數(shù)列表，表示為

MinPts_list={MinPtsK|1≤K≤n}（15）

基于自衰減的理論可以有效地縮小MinPts參數(shù)值的范圍，從而得到更優(yōu)的MinPts參數(shù)列表。

2.1.3 自適應(yīng)選擇全局最優(yōu)參數(shù)

根據(jù)自衰減生成的Eps_list參數(shù)列表依次選擇不同的K值（K=1，2，…，n）所對(duì)應(yīng)的參數(shù)值，本文提出依次與MinPts_list參數(shù)列表中的參數(shù)進(jìn)行全組合操作，得到更多的參數(shù)組合，提高算法找到最優(yōu)全局參數(shù)的可能性。

將第i個(gè)Eps參數(shù)與MinPts_list列表中所有參數(shù)的組合稱為第i輪參數(shù)組合，將每一輪的參數(shù)組合依次輸入到DBSCAN算法中進(jìn)行聚類。算法會(huì)記錄每輪聚類最高的準(zhǔn)確率數(shù)值，共記錄n個(gè)準(zhǔn)確率數(shù)值，根據(jù)最高的準(zhǔn)確率數(shù)值找到相應(yīng)的全局最優(yōu)參數(shù)。

圖4為記錄n個(gè)準(zhǔn)確率數(shù)值的曲線圖，其中橫坐標(biāo)表示為不同參數(shù)組合的序號(hào)，縱坐標(biāo)表示在不同參數(shù)條件下聚類的準(zhǔn)確率。從圖中可以看出準(zhǔn)確率數(shù)值的最高點(diǎn)，此點(diǎn)對(duì)應(yīng)的Eps和MinPts參數(shù)則為所有參數(shù)組合中的最優(yōu)參數(shù)。

2.2 基于三支決策的LOF算法

本節(jié)將介紹三支決策思想運(yùn)用到LOF離群點(diǎn)檢測(cè)算法的過(guò)程。將數(shù)據(jù)集中的孤立程度用三個(gè)集合Co（U）、Fr（U）和Tr（U）表示，分別是核心域、邊界域和瑣碎域。本文通過(guò)一對(duì)閾值（a，b）來(lái)判斷離群點(diǎn)，且a≥b。核心域中的數(shù)據(jù)對(duì)象表示確定是離群點(diǎn)，邊界域中的數(shù)據(jù)對(duì)象表示可能是離群點(diǎn)，而瑣碎域中的數(shù)據(jù)對(duì)象表示肯定不是離群點(diǎn)，基于離群點(diǎn)檢測(cè)評(píng)價(jià)函數(shù)s（x），即

Co（U）={x∈U|s（x）＞a}Fr（U）={x∈U|b≤s（x）≤a}Tr（U）={x∈U|s（x）＜b}（16）

改進(jìn)后的LOF算法判斷數(shù)據(jù)對(duì)象是否為離群點(diǎn)時(shí)，當(dāng)對(duì)象x孤立值小于閾值a，則表示對(duì)象x周?chē)膶?duì)象分布較為緊湊，排除是離群點(diǎn)的可能。當(dāng)對(duì)象x孤立值大于閾值b，則表示對(duì)象x周?chē)膶?duì)象分布較為分散，對(duì)象屬性之間差距較大，則改進(jìn)后的LOF算法認(rèn)為該對(duì)象不屬于任何類簇，并且將對(duì)象x標(biāo)記為離群點(diǎn)。當(dāng)對(duì)象x的孤立值介于閾值a和b之間，改進(jìn)后的LOF算法不會(huì)立即作出判斷，當(dāng)聚類結(jié)果與真實(shí)結(jié)果進(jìn)行比較的時(shí)候，算法會(huì)對(duì)邊界域中的對(duì)象作進(jìn)一步的判斷，這樣可以減少算法對(duì)數(shù)據(jù)的誤判風(fēng)險(xiǎn)。

將三支決策思想與LOF算法相結(jié)合，很好地優(yōu)化了判斷離群點(diǎn)的條件，降低了決策的錯(cuò)誤率，能夠提高聚類結(jié)果的準(zhǔn)確率，解決了傳統(tǒng)LOF離群點(diǎn)算法強(qiáng)行判斷數(shù)據(jù)對(duì)象是否為離群點(diǎn)的問(wèn)題，針對(duì)數(shù)據(jù)集中的不確定信息也作進(jìn)一步的判斷，提高了判別離群點(diǎn)的準(zhǔn)確性，從而提高了聚類整體的準(zhǔn)確性。

2.3 AL3W-DBSCAN算法

本文首先提出了自適應(yīng)確定全局最優(yōu)參數(shù)的方法，實(shí)現(xiàn)全自動(dòng)化聚類過(guò)程，用于解決經(jīng)典DBSCAN算法對(duì)于參數(shù)依賴的問(wèn)題。在自適應(yīng)確定參數(shù)的基礎(chǔ)上考慮將三支決策思想分別與DBSCAN聚類算法和LOF離群點(diǎn)檢測(cè)算法相結(jié)合，并提出AL3W-DBSCAN聚類算法思想。

AL3W-DBSCAN聚類算法不需要人工輸入最少點(diǎn)數(shù)MinPts、全局半徑Eps和近鄰次序k，解決了聚類算法對(duì)參數(shù)的依賴。首先用基于三支決策思想的LOF算法對(duì)數(shù)據(jù)集中計(jì)算所有數(shù)據(jù)對(duì)象的孤立程度，然后利用自適應(yīng)確定的參數(shù)輸入到基于三支決策思想的DBSCAN聚類算法中，聚類時(shí)根據(jù)三支決策思想將數(shù)據(jù)集分為不同類簇，每個(gè)類簇由核心域、邊界域和瑣碎域區(qū)域組成。此時(shí)聚類結(jié)果不能作為最終結(jié)果，如果數(shù)據(jù)集中有離群點(diǎn)q，則根據(jù)數(shù)據(jù)對(duì)象q的孤立程度屬性作進(jìn)一步的推斷。如果孤立程度大于閾值a，確認(rèn)對(duì)象q為離群點(diǎn)。如果孤立程度介于閾值a和b之間，則將對(duì)象q劃分到最近類簇的邊界域。如果孤立程度小于等于閾值b，則將對(duì)象劃分到最近類簇的核心域中。當(dāng)聚類過(guò)程結(jié)束后，輸出最終結(jié)果數(shù)據(jù)集C。

算法1 AL3W-DBSCAN算法

3 聚類評(píng)價(jià)指標(biāo)

為了更細(xì)致地評(píng)價(jià)聚類算法的優(yōu)劣，本文參考了二支聚類評(píng)價(jià)指標(biāo)和三支聚類評(píng)價(jià)指標(biāo)，分別對(duì)DBSCAN、3W-DBSCAN以及AL3W-DBSCAN算法進(jìn)行實(shí)驗(yàn)數(shù)據(jù)對(duì)比。

3.1 硬聚類評(píng)價(jià)指標(biāo)

a）準(zhǔn)確率ACC（accuracy）是一種判斷聚類算法優(yōu)劣的經(jīng)典指標(biāo)。這個(gè)評(píng)價(jià)指標(biāo)就是依據(jù)聚類結(jié)果與真實(shí)情況作對(duì)比，ACC的值越高說(shuō)明聚類結(jié)果評(píng)價(jià)越好。

定義11 ACC。

其中：N表示數(shù)據(jù)對(duì)象的個(gè)數(shù)；Ci表示類簇i的正確數(shù)據(jù)對(duì)象個(gè)數(shù)；k表示類簇個(gè)數(shù)。本文評(píng)價(jià)三支聚類的結(jié)果是利用核心域中的數(shù)據(jù)對(duì)象加邊界域中正確的對(duì)象來(lái)計(jì)算的。

b）F1分?jǐn)?shù)（F1 score）是一種衡量聚類結(jié)果精確度的指標(biāo)，它兼顧了精確率和召回率的評(píng)價(jià)指標(biāo)，F(xiàn)1 score取值為0～1，數(shù)值越大表示聚類結(jié)果越好。

定義12 F1 score。

其中：precision表示精確率；recall表示召回率。計(jì)算三支聚類結(jié)果是用核心域加邊界域中正確的對(duì)象來(lái)計(jì)算的。

c）調(diào)整蘭德系數(shù)（ARI）是一種常見(jiàn)的聚類外部評(píng)價(jià)指標(biāo)，通過(guò)計(jì)算在真實(shí)數(shù)據(jù)情況和聚類結(jié)果中被分配在不同類簇的數(shù)據(jù)個(gè)數(shù)來(lái)進(jìn)行聚類效果的評(píng)價(jià)。

定義13 ARI。

其中：n為樣本總個(gè)數(shù)；nij表示數(shù)據(jù)對(duì)象被劃分到正確類簇中的個(gè)數(shù)；ai表示被劃分到類簇i的數(shù)據(jù)對(duì)象個(gè)數(shù)；a表示被劃分到不同類簇的對(duì)象總個(gè)數(shù)；bi表示類簇i中實(shí)際數(shù)據(jù)對(duì)象的個(gè)數(shù)；b表示在實(shí)際相同類簇被劃分為不同類簇的對(duì)象總個(gè)數(shù)。

3.2 軟聚類評(píng)價(jià)指標(biāo)

由于硬聚類評(píng)價(jià)指標(biāo)的提出較早，所以軟聚類評(píng)價(jià)指標(biāo)較少，現(xiàn)在仍有許多用硬聚類評(píng)價(jià)指標(biāo)來(lái)評(píng)價(jià)三支聚類結(jié)果。本文引入軟聚類方法對(duì)聚類結(jié)果進(jìn)行更細(xì)致的評(píng)價(jià)。

第一個(gè)軟聚類評(píng)價(jià)指標(biāo)是由Maji等人[27]提出的，其公式的定義為

其中：n代表數(shù)據(jù)對(duì)象的個(gè)數(shù)；c代表聚類的個(gè)數(shù);|Cpi|代表的是第i個(gè)類的核心域中數(shù)據(jù)對(duì)象的個(gè)數(shù)。式（20）表示所有類簇中核心域的平均質(zhì)量，計(jì)算的結(jié)果與聚類效果正相關(guān)。

第二個(gè)評(píng)價(jià)指標(biāo)是由Zhang[28]提出的兩個(gè)評(píng)價(jià)指標(biāo)，其公式的定義為

其中：c代表類簇的個(gè)數(shù)；|Cpi|表示第i個(gè)類的核心域中對(duì)象的個(gè)數(shù);|Cpi|表示第i個(gè)類簇邊界域中對(duì)象的個(gè)數(shù)。式（21）（22）分別表示第i個(gè)類簇的平均效果和整體效果，計(jì)算結(jié)果與聚類效果成正相關(guān)。

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

AL3W-DBSCAN聚類算法得到的實(shí)驗(yàn)結(jié)果與其他算法的聚類結(jié)果進(jìn)行比較，對(duì)比方式采用ACC、F1和ARI硬聚類評(píng)價(jià)指標(biāo)和引入的軟聚類評(píng)價(jià)指標(biāo)進(jìn)行度量。

4.1 人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

依據(jù)本文中自適應(yīng)確定參數(shù)方法，下面將列出各個(gè)算法在不同數(shù)據(jù)集中所需的參數(shù)。具體內(nèi)容如表1所示。

圖5為AL3W-DBSCAN聚類算法與其他聚類算法在不同數(shù)據(jù)集上的對(duì)比圖。AL3W-DBSCAN算法在聚類結(jié)果的準(zhǔn)確性上有著不同程度的提升，同時(shí)也很好地解決了數(shù)據(jù)對(duì)象被錯(cuò)誤地判斷成離群點(diǎn)的問(wèn)題。

從圖5可以看出，本文算法有效地緩解了錯(cuò)誤判斷離群點(diǎn)的問(wèn)題，從而提高了聚類算法的準(zhǔn)確率。同時(shí)為了驗(yàn)證AL3W-DBSCAN算法對(duì)于其他聚類算法的優(yōu)勢(shì)，本文利用在人工數(shù)據(jù)集上的聚類結(jié)果數(shù)據(jù)作對(duì)比，通過(guò)數(shù)據(jù)表明本文算法在不同人工數(shù)據(jù)集上的效果均優(yōu)于經(jīng)典的DBSCAN聚類算法和3W-DBSCAN聚類算法。詳細(xì)的硬聚類評(píng)價(jià)結(jié)果數(shù)據(jù)如表2所示。

4.2 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

本文將AL3W-DBSCAN算法和其他算法對(duì)UCI數(shù)據(jù)集進(jìn)行聚類分析。由于UCI真實(shí)數(shù)據(jù)集中的數(shù)據(jù)分布情況復(fù)雜，從而導(dǎo)致傳統(tǒng)聚類算法在真實(shí)數(shù)據(jù)集的效果較差。AL3W-DBSCAN聚類算法在真實(shí)數(shù)據(jù)集中的效果提升顯著。在wine真實(shí)數(shù)據(jù)集中，依據(jù)ACC準(zhǔn)確率的評(píng)價(jià)指標(biāo)，AL3W-DBSCAN算法準(zhǔn)確率比經(jīng)典DBSCAN算法準(zhǔn)確率高將近20%。在其他數(shù)據(jù)集方面，本文聚類算法的評(píng)價(jià)指標(biāo)結(jié)果也有不同程度的提高，表明本文算法在真實(shí)數(shù)據(jù)集中優(yōu)勢(shì)更加明顯。其中評(píng)價(jià)指標(biāo)的數(shù)值越接近于1，表示聚類算法的結(jié)果越準(zhǔn)確。聚類結(jié)果硬聚類評(píng)價(jià)指標(biāo)信息如表3所示。

AL3W-DBSCAN聚類算法將一些誤判為離群點(diǎn)的樣本重新劃分到某類簇的邊界域或者核心域，會(huì)影響軟聚類的聚類效果，但對(duì)于硬聚類效果來(lái)講是整體上升的，這也說(shuō)明了本文算法的有效性。聚類結(jié)果軟聚類評(píng)價(jià)指標(biāo)信息如表4所示。

4.3 本文算法與其他算法比較研究

本文分析對(duì)當(dāng)前領(lǐng)域其他最新算法的總結(jié)，介紹了其他算法的優(yōu)缺點(diǎn)。在人工數(shù)據(jù)集flame、aggregation和UCI數(shù)據(jù)集iris、wine的基礎(chǔ)上，表5中的數(shù)據(jù)均借鑒文獻(xiàn)中其他最新聚類算法的實(shí)驗(yàn)數(shù)據(jù)與本文算法的數(shù)據(jù)進(jìn)行對(duì)比。其中對(duì)比的最新算法包括AF-DBSCAN、KR-DBSCAN、KLS-DBSCAN和LE-DBSCAN。通過(guò)對(duì)比發(fā)現(xiàn)，本文算法在ACC和ARI評(píng)價(jià)指標(biāo)上，絕大部分都優(yōu)于表中的其他算法，證明了AL3W-DBSCAN聚類算法的有效性與優(yōu)越性。但在aggregation數(shù)據(jù)集中，聚類效果最優(yōu)的是KR-DBSCAN和LE-DBSCAN算法。詳細(xì)對(duì)比數(shù)據(jù)如表5所示。

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

通過(guò)上述聚類結(jié)果圖和聚類結(jié)果的對(duì)比發(fā)現(xiàn)，AL3W-DBSCAN算法在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上都是優(yōu)于經(jīng)典DBSCAN和3W-DBSCAN算法的。雖然在軟聚類評(píng)價(jià)方面3W-DBSCAN算法優(yōu)于本文算法，但軟聚類是以核心域的數(shù)據(jù)數(shù)量來(lái)計(jì)算的，在三支決策思想中是把核心域和邊界域作為一個(gè)類。整體來(lái)說(shuō)，AL3W-DBSCAN算法依舊優(yōu)于3W-DBSCAN算法。通過(guò)與借鑒文獻(xiàn)中最新方法的數(shù)據(jù)作對(duì)比，除了在aggregation數(shù)據(jù)上KR-DBSCAN和LE-DBSCAN算法最優(yōu)的情況，其余情況AL3W-DBSCAN算法聚類效果最好。如今許多聚類算法存在對(duì)高維數(shù)據(jù)聚類效果不好的問(wèn)題，通過(guò)本文的實(shí)驗(yàn)發(fā)現(xiàn)，所對(duì)比的算法在高維數(shù)據(jù)聚類效果不好，是因?yàn)楦呔S數(shù)據(jù)本身分析更加復(fù)雜，并且高維數(shù)據(jù)集都是真實(shí)數(shù)據(jù)集，數(shù)據(jù)對(duì)象分布不具有規(guī)律性。但是AL3W-DBSCAN算法在判斷離群點(diǎn)的過(guò)程中，利用三支決策在LOF算法上的改進(jìn)，提高了算法判斷離群點(diǎn)的準(zhǔn)確性，同時(shí)也提高了算法整體的準(zhǔn)確性。因此AL3W-DBSCAN聚類算法相較其他算法具有在高維數(shù)據(jù)集聚類的優(yōu)勢(shì)。

AL3W-DBSCAN算法在聚類的過(guò)程中能夠選擇符合數(shù)據(jù)對(duì)象分布特性的全局最優(yōu)參數(shù)，克服了傳統(tǒng)算法需要人工輸入具有主觀性參數(shù)的問(wèn)題，以及實(shí)現(xiàn)了聚類過(guò)程全自動(dòng)化的過(guò)程，并在多維度數(shù)據(jù)方面也具有良好的表現(xiàn)。本文算法利用三支決策的思想有效地處理了數(shù)據(jù)集內(nèi)不確定信息的聚類問(wèn)題，對(duì)聚類后產(chǎn)生的離群點(diǎn)作出了進(jìn)一步的判斷，使得聚類的準(zhǔn)確率有著明顯的提高。

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

經(jīng)典的DBSCAN算法具有挖掘任意形狀的類簇以及對(duì)離群點(diǎn)不敏感的優(yōu)勢(shì)，但DBSCAN算法存在依賴人為輸入Eps和MinPts參數(shù)，以及誤判離群點(diǎn)的問(wèn)題。針對(duì)上述問(wèn)題，AL3W-DBSCAN聚類算法利用自衰減項(xiàng)以及ACC評(píng)價(jià)指標(biāo)來(lái)尋找全局最優(yōu)參數(shù)，同時(shí)將三支決策理論與離群點(diǎn)檢測(cè)LOF算法結(jié)合，完善了在判斷離群點(diǎn)時(shí)的條件。通過(guò)實(shí)驗(yàn)結(jié)果表明，AL3W-DBSCAN算法有效地解決了上述問(wèn)題。但是在三支決策思想上閾值的選擇還有待討論，如何有效選取最優(yōu)閾值是今后工作研究的重點(diǎn)。

參考文獻(xiàn)：

[1]Agudelo-Castaeda D M， Teixeira E C， Braga M， et al. Cluster analysis of urban ultrafine particles size distributions[J]. Atmospheric Pollution Research， 2019，10（1）： 45-52.

[2]Xu Chaoyang， Lin Renjie， Cai Jinyu， et al. Deep image clustering by fusing contrastive learning and neighbor relation mining[J]. Know-ledge Based Systems， 2022， 238： 107967.

[3]Brown D， Japa A， Shi Yong. A fast density-grid based clustering method[C]//Proc of the 9th IEEE Annual Computing and Communication Workshop and Conference.Piscataway，NJ： IEEE Press， 2019： 48-54.

[4]Huang Jinjing， Chen Wei， Liu An， et al. Cluster query： a new query pattern on temporal knowledge graph[J]. World Wide Web， 2020， 23： 755-779.

[5]Xu Zhaozhao， Shen Derong， Nie Tiezheng， et al. A cluster-based oversampling algorithm combining SMOTE and K-means for imba-lanced medical data[J]. Information Sciences， 2021， 572： 574-589.

[6]H-ppner F， Klawonn F， Kruse R，et al. Fuzzy cluster analysis： me-thods for classification， data analysis and image recognition[M].[S.l.]： Wiley， 1999.

[7]Lingras P， West C. Interval set clustering of Web users with rough K-means[J]. Journal of Intelligent Information Systems， 2004， 23： 5-16.

[8]Yao Yiyu. An outline of a theory of three-way decisions[C]//Proc of International Conference on Rough Sets and Current Trends in Computing. Berlin： Springer， 2012： 1-17.

[9]Shaikh S A， Kitagawa H. Top-k outlier detection from uncertain data[J]. International Journal of Automation and Computing， 2014，11（2）： 128-142.

[10]鄒云峰， 張昕， 宋世淵， 等. 基于局部密度的快速離群點(diǎn)檢測(cè)算法[J]. 計(jì)算機(jī)應(yīng)用， 2017， 37（10）： 2932-2937. （Zou Yunfeng， Zhang Xin， Song Shiyuan， et al. Fast outlier detection algorithm based on local density[J]. Journal of Computer Applications， 2017， 37（10）： 2932-2937.）

[11]緱鵬飛， 宋承云. 基于自適應(yīng)鄰居圖的離群點(diǎn)檢測(cè)方法[J]. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（11）： 3309-3314. （Gou Pengfei， Song Chengyun. Outlier detection method using adaptive neighbor graph[J]. Application Research of Computers， 2023，40（11）： 3309-3314.）

[12]周治平， 王杰鋒， 朱書(shū)偉， 等. 一種改進(jìn)的自適應(yīng)快速 AF-DBSCAN聚類算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016， 11（1）： 93-98. （Zhou Zhiping， Wang Jiefeng， Zhu Shuwei， et al. An improved adaptive fast AF-DBSCAN clustering algorithm[J]. CAAI Trans on Intelligent Systems， 2016， 11（1）： 93-98.）

[13]Hu Lihua， Liu Hongkai， Zhang Jifu， et al. KR-DBSCAN： a density-based clustering algorithm based on reverse nearest neighbor and influence space[J]. Expert Systems with Applications， 2021，186： 115763.

[14]Yu Hui， Chen Luyuan， Yao Jingtao， et al. A three-way clustering method based on an improved DBSCAN algorithm[J]. Physica A： Statistical Mechanics and its Applications， 2019， 535： 122289.

[15]王光， 林國(guó)宇. 改進(jìn)的自適應(yīng)參數(shù)DBSCAN聚類算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 2020， 56（14）： 45-51. （Wang Guang， Lin Guoyu. Improved adaptive parameter DBSCAN clustering algorithm[J]. Computer Engineering and Applications， 2020， 56（14）： 45-51.）

[16]申秋萍， 張清華， 高滿， 等. 基于局部半徑的三支DBSCAN算法[J]. 計(jì)算機(jī)科學(xué)， 2023， 50（6）： 100-108. （Shen Qiuping， Zhang Qinghua， Gao Man， et al. Three-way DBSCAN algorithm based on local eps[J]. Computer Science， 2023，50（6）： 100-108.）

[17]蘭紅， 朱合隆. 基于高階差分和網(wǎng)格劃分算法的DBSCAN參數(shù)自動(dòng)選取算法[J]. 計(jì)算機(jī)應(yīng)用研究， 2020， 37（11）： 3347-3352. （Lan Hong， Zhu Helong. DBSCAN parameter setting based on higher-order difference and grid partition algorithm[J]. Application Research of Computers， 2020，37（11）： 3347-3352.）

[18]Breunig M M， Kriegel H P， Ng R T，et al. LOF： identifying density-based local outliers[C]//Proc of ACM SIGMOD International Confe-rence on Management of Data. New York：ACM Press， 2000： 93-104.

[19]Ester M， Kriegel H P， Sander J，et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proc of the 2nd International Conference on Knowledge Discovery and Data Mining. Palo Alto， CA： AAAI Press，1996： 226-231.

[20]Yao Yiyu. Three-way decisions with probabilistic rough sets[J]. Information sciences， 2010， 180（3）： 341-353.

[21]Yao Yiyu. The superiority of three-way decisions in probabilistic rough set models[J]. Information Sciences， 2011， 181（6）： 1080-1096.

[22]Yu Hong， Chu Shuangshuang， Yang Dachun. Autonomous knowledge-oriented clustering using decision-theoretic rough set theory[C]//Proc of the 5th International Conference on Rough Set and Knowledge Technology. Berlin：Springer， 2010： 687-694.

[23]Yue Shihong， Li Ping， Guo Jidong， et al. A statistical information-based clustering approach in distance space[J]. Journal of Zhejiang University-Science A， 2005， 6（1）： 71-78.

[24]Jahirabadkar S， Kulkarni P. Algorithm to determine ε-distance parameter in density based clustering[J]. Expert Systems with Applications， 2014， 41（6）： 2939-2946.

[25]Kim J H， Choi J H， Yoo K H，et al. AA-DBSCAN： an approximate adaptive DBSCAN for finding clusters with varying densities[J]. The Journal of Supercomputing， 2019， 75（1）： 142-169.

[26]萬(wàn)佳， 胡大裟， 蔣玉明. 多密度自適應(yīng)確定DBSCAN算法參數(shù)的算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2022， 58（2）： 78-85. （Wan Jia， Hu Dasha， Jiang Yuming. Research on method of multi-density self-adaptive determination of DBSCAN algorithm parameters[J]. Computer Engineering and Applications， 2022，58（2）： 78-85.）

[27]Maji P， Pal S K. RFCM： a hybrid clustering algorithm using rough and fuzzy sets[J]. Fundamenta Informaticae， 2007，80（4）： 475-496.

[28]Zhang Kai. A three-way C-means algorithm[J]. Applied Soft Computing， 2019， 82： 105536.