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

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

中圖分類號：TP393.09 文獻標志碼：A 文章編號：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)致每天都會產(chǎn)生海量的數(shù)據(jù)，如何從海量數(shù)據(jù)中準確地找出有價值的數(shù)據(jù)，是當(dāng)今研究的方向之一[1]。聚類分析是數(shù)據(jù)挖掘與機器學(xué)習(xí)領(lǐng)域中的一個重要技術(shù)，已經(jīng)廣泛地成功應(yīng)用于多個領(lǐng)域，其中包括圖像處理[2]、統(tǒng)計學(xué)[3]、知識圖譜[4]、醫(yī)療健康[5]等。

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

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

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

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

1 相關(guān)工作

1.1 LOF算法

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

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

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

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

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

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

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

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

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

1.2 DBSCAN聚類算法

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

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

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

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

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

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

1.3 三支聚類

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

Yu等人[22]將三支決策理論結(jié)合到聚類方法中，提出了三支聚類方法。三支聚類分別利用三個互不相交的區(qū)域Cpi、CBi和CNi代表類簇i的核心域、邊界域以及瑣碎域。核心域中的數(shù)據(jù)對象代表確定劃分到類簇i，邊界域中的數(shù)據(jù)對象代表不確定是否劃分到類簇i，而瑣碎域中的數(shù)據(jù)對象代表確定不劃分到類簇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），則對象x只屬于類簇C；如果對象x∈FringeRegion（C），則對象x可能屬于類簇C；如果x∈TrivialRegion（C），則對象x不屬于類簇C。

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

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

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

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

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

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

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

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

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

2 AL3W-DBSCAN算法

2.1 算法設(shè)計

2.1.1 Eps參數(shù)列表

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

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

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

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

2.1.2 MinPts參數(shù)列表

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

其中：n為數(shù)據(jù)集中數(shù)據(jù)對象的總數(shù)；λ表示自衰減系數(shù)，0≤λ≤1；Pi為第i個數(shù)據(jù)的Eps鄰域內(nèi)的數(shù)據(jù)個數(shù)。通過計算得到最終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）所對應(yīng)的參數(shù)值，本文提出依次與MinPts_list參數(shù)列表中的參數(shù)進行全組合操作，得到更多的參數(shù)組合，提高算法找到最優(yōu)全局參數(shù)的可能性。

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

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

2.2 基于三支決策的LOF算法

本節(jié)將介紹三支決策思想運用到LOF離群點檢測算法的過程。將數(shù)據(jù)集中的孤立程度用三個集合Co（U）、Fr（U）和Tr（U）表示，分別是核心域、邊界域和瑣碎域。本文通過一對閾值（a，b）來判斷離群點，且a≥b。核心域中的數(shù)據(jù)對象表示確定是離群點，邊界域中的數(shù)據(jù)對象表示可能是離群點，而瑣碎域中的數(shù)據(jù)對象表示肯定不是離群點，基于離群點檢測評價函數(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）

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

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

2.3 AL3W-DBSCAN算法

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

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

算法1 AL3W-DBSCAN算法

3 聚類評價指標

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

3.1 硬聚類評價指標

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

定義11 ACC。

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

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

定義12 F1 score。

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

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

定義13 ARI。

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

3.2 軟聚類評價指標

由于硬聚類評價指標的提出較早，所以軟聚類評價指標較少，現(xiàn)在仍有許多用硬聚類評價指標來評價三支聚類結(jié)果。本文引入軟聚類方法對聚類結(jié)果進行更細致的評價。

第一個軟聚類評價指標是由Maji等人[27]提出的，其公式的定義為

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

第二個評價指標是由Zhang[28]提出的兩個評價指標，其公式的定義為

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

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

AL3W-DBSCAN聚類算法得到的實驗結(jié)果與其他算法的聚類結(jié)果進行比較，對比方式采用ACC、F1和ARI硬聚類評價指標和引入的軟聚類評價指標進行度量。

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

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

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

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

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

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

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

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

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

4.4 實驗結(jié)果分析

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

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

5 結(jié)束語

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

參考文獻：

[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]鄒云峰， 張昕， 宋世淵， 等. 基于局部密度的快速離群點檢測算法[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)鄰居圖的離群點檢測方法[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]周治平， 王杰鋒， 朱書偉， 等. 一種改進的自適應(yīng)快速 AF-DBSCAN聚類算法[J]. 智能系統(tǒng)學(xué)報， 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]王光， 林國宇. 改進的自適應(yīng)參數(shù)DBSCAN聚類算法[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]. 計算機科學(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ù)自動選取算法[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]萬佳， 胡大裟， 蔣玉明. 多密度自適應(yīng)確定DBSCAN算法參數(shù)的算法研究[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.