基于邊界點(diǎn)檢測的變密度聚類算法

陳延偉，趙興旺*

（1.山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006；2.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室（山西大學(xué)），太原 030006）

0 引言

聚類分析依據(jù)一定的準(zhǔn)則將數(shù)據(jù)對(duì)象劃分為不同的類，使同一類別中的對(duì)象具有較高的相似度，而不同類中的對(duì)象之間相似度較低。作為一種重要的數(shù)據(jù)挖掘技術(shù)，聚類分析已經(jīng)在社交網(wǎng)絡(luò)分析、模式識(shí)別、生物信息學(xué)等諸多領(lǐng)域得到了廣泛應(yīng)用［1-3］。

經(jīng)過數(shù)十年的發(fā)展，研究者針對(duì)不同的領(lǐng)域提出了大量聚類分析算法，主要分為以下幾類：基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法以及基于圖的聚類算法等［4］。其中，密度聚類算法由于具有對(duì)噪聲魯棒、善于處理結(jié)構(gòu)復(fù)雜數(shù)據(jù)且事先不需要指定類個(gè)數(shù)等優(yōu)勢，近年來得到研究者的大量關(guān)注［5］。1996 年Ester 等［6］提出基于密度的噪聲應(yīng)用空間聚類（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）算法，通過將高密度區(qū)域劃分為類，能夠在含“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的類。1999 年Ankerst 等［7］提出通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)（Ordering Points To Identify the Clustering Structure，OPTICS）算法，得到一個(gè)有序的對(duì)象列表用于提取聚類信息，但不顯式地生成數(shù)據(jù)聚類結(jié)果。2014 年Rodriguez 等［8］提出一種新型的基于密度峰值的聚類算法（Density Peaks Clustering Algorithm，DPCA），該算法基于類中心的密度大于周圍鄰居點(diǎn)的密度和類中心與更高密度點(diǎn)之間的距離相對(duì)較大的假設(shè)，用于尋找被低密度點(diǎn)隔離的高密度區(qū)域以達(dá)到對(duì)數(shù)據(jù)聚類的目的。盡管經(jīng)典的密度聚類算法在處理形狀復(fù)雜、包含噪聲的數(shù)據(jù)方面具有一定優(yōu)勢，但是，該類算法面臨著由于數(shù)據(jù)集中不同類的密度分布不均，且類與類之間邊界難以區(qū)分等導(dǎo)致聚類效果較差的問題。

針對(duì)以上問題，本文提出了一種基于邊界點(diǎn)檢測的變密度聚類算法（Varied Density Clustering algorithm based on Border point Detection，VDCBD）。算法主要包括以下步驟：1）基于給出的相對(duì)密度度量方法識(shí)別變密度類之間的邊界點(diǎn)，以此增強(qiáng)相鄰類的可分性；2）對(duì)非邊界區(qū)域的點(diǎn)進(jìn)行聚類以找到數(shù)據(jù)集的核心類結(jié)構(gòu)；3）依據(jù)高密度近鄰分配原則將檢測到的邊界點(diǎn)分配到核心類結(jié)構(gòu)中；4）基于類結(jié)構(gòu)信息識(shí)別數(shù)據(jù)集中的噪聲點(diǎn)。在人造數(shù)據(jù)集和UCI 數(shù)據(jù)集上與已有的經(jīng)典聚類算法進(jìn)行了比較分析。實(shí)驗(yàn)結(jié)果表明，本文算法可以有效解決類分布密度不均、邊界難以區(qū)分的問題，并在4 個(gè)評(píng)價(jià)指標(biāo)上優(yōu)于已有算法。

1 相關(guān)工作

本章主要對(duì)已有的變密度聚類算法進(jìn)行介紹。

2014 年在Science上發(fā)表了快速搜索和發(fā)現(xiàn)密度峰值聚類算法（DPCA）［8］。該算法結(jié)合了劃分聚類算法和密度聚類算法的優(yōu)點(diǎn)，通過尋找合適的聚類中心點(diǎn)以得到理想的聚類結(jié)果，但不能保證每個(gè)類中有且僅有一個(gè)密度峰，因此DPCA 對(duì)變密度數(shù)據(jù)的聚類效果有限。為了解決變密度聚類問題，一些學(xué)者從不同角度對(duì)DPCA 進(jìn)行了改進(jìn)［9-10］。2016 年Du 等［11］介紹了一種基于k近鄰和主成分分析的密度峰值（Density Peak Clustering based onk-Nearest Neighbors，DPC-kNN）算法，該算法引入k最近鄰重新定義局部密度以考慮數(shù)據(jù)集的局部分布情況，減少了截?cái)嗑嚯x對(duì)聚類結(jié)果的影響，并引入了主成分分析（Principal Component Analysis，PCA）以處理高維數(shù)據(jù)集；2016 年，Xie 等［12］提出了一種模糊加權(quán)k近鄰的密度峰值聚類（Fuzzy weightedk-Nearest Neighbors Density Peak Clustering，F(xiàn)kNN-DPC）算法，該算法通過引入k最近鄰給出了一種新穎的局部密度度量方法，并使用兩種新的點(diǎn)分配策略將剩余點(diǎn)分配到最可能的類以消除DPCA 點(diǎn)的分配策略導(dǎo)致的“多米諾效應(yīng)”［13］；2018 年Liu等［14］提出了一種基于共享鄰居的密度峰值聚類（Shared Nearest Neighbor based Density Peaks Clustering，SNN-DPC）算法，該算法基于共享鄰居重新定義數(shù)據(jù)對(duì)象的局部密度和相對(duì)距離，并引入兩種基于共享鄰居信息的分配策略提高非中心點(diǎn)分配的準(zhǔn)確性；2020 年Flores 等［15］提出了一種基于中心點(diǎn)自動(dòng)檢測的密度峰值（Density Peak Clustering with Gap-Based automatic center detection，GBDPC）算法，通過對(duì)一維決策圖中數(shù)據(jù)點(diǎn)連續(xù)對(duì)之間的距離處理以自動(dòng)確定聚類中心點(diǎn)個(gè)數(shù)，以解決多密度峰值的問題；2020 年Wang 等［16］提出了一種多中心密度峰值聚類（Multi-center Density Peak Clustering，McDPC）算法，該算法通過對(duì)決策圖進(jìn)行再規(guī)劃，將樣本劃分為不同的密度層用來識(shí)別低密度區(qū)域的類，并對(duì)參數(shù)δ（與更高密度點(diǎn)的最近距離）進(jìn)行類似的劃分以識(shí)別包含多個(gè)密度峰值的類。

另一部分學(xué)者提出新的聚類算法用于處理變密度數(shù)據(jù)。2016 年Chen 等［17］提出了一種有效識(shí)別密度主干的聚類（CLUstering based on Backbone，CLUB）算法，該算法通過將DPCA 中尋找聚類中心的策略轉(zhuǎn)換為尋找密度主干，并利用k近鄰生成初始類以此定義基本密度骨架，然后根據(jù)高密度近鄰原則分配其余點(diǎn)并識(shí)別噪聲點(diǎn)以獲得最終的聚類結(jié)果；2016 年，Zhu 等［18］提出了基于密度比的聚類算法解決變密度問題，該算法通過使用密度估計(jì)器計(jì)算密度比和對(duì)現(xiàn)有數(shù)據(jù)進(jìn)行自適應(yīng)的縮放兩種方法用于對(duì)變密度數(shù)據(jù)的處理；2017年Louhichi 等［19］提出了一種基于樣條的無監(jiān)督變密度聚類（Multi Density ClUsTering，MDCUT）算法，該算法利用k最近鄰距離的指數(shù)樣條尋找合理的密度層次，并利用這些密度層次作為局部密度閾值獲取不同密度的類；2020 年Averbuch-Elor 等［20］提出一種邊界剝離聚類（Border Peeling clustering，BP）算法，通過迭代剝離邊界點(diǎn)并建立邊界點(diǎn)與其相鄰非邊界點(diǎn)的聯(lián)系，之后利用核心點(diǎn)間的可達(dá)性進(jìn)行核心點(diǎn)的聚類并通過建立的聯(lián)系分配剝離的邊界點(diǎn)?，F(xiàn)有算法在不同程度上可以識(shí)別變密度數(shù)據(jù)集的類結(jié)構(gòu)，但是仍然面臨著相鄰類之間的邊界難以區(qū)分等導(dǎo)致聚類效果較差的問題。

2 基于邊界點(diǎn)檢測的變密度聚類算法

假設(shè)D={x1，x2，…，xn}表示由n個(gè)數(shù)據(jù)對(duì)象組成的數(shù)據(jù)集，其中xi表示數(shù)據(jù)集中第i個(gè)對(duì)象。

定義1k最近鄰：對(duì)于D中的每個(gè)數(shù)據(jù)對(duì)象xi，在歐氏距離下與xi最相似的k個(gè)數(shù)據(jù)對(duì)象稱為xi的k最近鄰，表示為KNk(xi)，其中KNk(xi) ?D。

定義2逆k最近鄰：對(duì)于D中的數(shù)據(jù)對(duì)象xi，如果其余任一對(duì)象xj的k最近鄰中包含xi，則xj為xi的逆k最近鄰，形式化描述如下：

本文算法主要包括邊界點(diǎn)檢測、非邊界點(diǎn)聚類、邊界點(diǎn)分配以及噪聲點(diǎn)識(shí)別4 個(gè)步驟。

2.1 邊界點(diǎn)檢測

邊界點(diǎn)位于每個(gè)類的邊緣位置，當(dāng)兩個(gè)類相距較近時(shí)，兩者之間的邊界很難識(shí)別，受INFLO（INFLuenced Outlierness）算法［21］思想的啟發(fā)，提出了一種基于相對(duì)密度的邊界檢測方法，用于識(shí)別不同變密度類難以區(qū)分的邊界點(diǎn)，增強(qiáng)數(shù)據(jù)類結(jié)構(gòu)的可分性。為了提高的運(yùn)行效率，檢測邊界點(diǎn)過程中僅考慮所有數(shù)據(jù)點(diǎn)密度排序后一半低密度的數(shù)據(jù)點(diǎn)。

定義3數(shù)據(jù)點(diǎn)密度：一個(gè)數(shù)據(jù)集中每個(gè)數(shù)據(jù)點(diǎn)的密集程度可以表示為該點(diǎn)到與它最近的k個(gè)鄰居間的距離之和。通常來說，距離和越大，該點(diǎn)與它的鄰居間的距離越遠(yuǎn)，因此，這個(gè)點(diǎn)的密度也就越小?？紤]到兩個(gè)類中數(shù)據(jù)密度為變密度時(shí)，該方法不能有效體現(xiàn)兩個(gè)類中密度的關(guān)系，因此，通過增加一個(gè)權(quán)重提升稀疏類中相對(duì)密集點(diǎn)的密度大小。給定一個(gè)數(shù)據(jù)點(diǎn)x與它的k最近鄰間的距離集合為{d1，d2，…，dk}，數(shù)據(jù)點(diǎn)x的密度形式化描述如下：

其中：den(x)代表點(diǎn)x的密度；k代表最近鄰的個(gè)數(shù)；di表示數(shù)據(jù)點(diǎn)x與第i個(gè)最近鄰點(diǎn)的距離；count(RKN(x))表示數(shù)據(jù)點(diǎn)x的逆k最近鄰個(gè)數(shù)。

定義4相對(duì)密度：將該點(diǎn)的密度與其周圍點(diǎn)的密度的均值作比較。比值越小，該點(diǎn)的相對(duì)密度越小，即該點(diǎn)成為邊界點(diǎn)的可能性越大，數(shù)據(jù)點(diǎn)x的相對(duì)密度形式化描述如下：

其中：RDx表示數(shù)據(jù)點(diǎn)x的相對(duì)密度；RKKN(x)表示數(shù)據(jù)點(diǎn)x的k最近鄰和逆k最近鄰的并集。

定義5邊界點(diǎn)：將該點(diǎn)的相對(duì)密度與其k最近鄰點(diǎn)的相對(duì)密度作比較，如果該點(diǎn)的相對(duì)密度小于其k最近鄰的均值，則該點(diǎn)為邊界點(diǎn)。形式化描述如下：

為了更直觀地體現(xiàn)每個(gè)步驟的效果，下面分別以在Flame 和Jain 數(shù)據(jù)集上處理的結(jié)果為例進(jìn)行介紹，其中Flame數(shù)據(jù)集由兩個(gè)相距較近的類組成，Jain 數(shù)據(jù)集則由兩個(gè)密度不同的類構(gòu)成。圖1 為Flame 和Jain 數(shù)據(jù)集上的邊界檢測結(jié)果，邊界點(diǎn)使用藍(lán)色空白點(diǎn)表示。由圖1 可知，通過該步驟可以有效識(shí)別出類與類之間的邊界點(diǎn)，進(jìn)而增強(qiáng)類之間的可分性。

圖1 Flame數(shù)據(jù)集和Jain數(shù)據(jù)集上的邊界識(shí)別結(jié)果Fig.1 Border recognition results on Flame dataset and Jain dataset

2.2 非邊界點(diǎn)的初始聚類

通過對(duì)原始數(shù)據(jù)進(jìn)行邊界點(diǎn)識(shí)別，相鄰類之間的間距因排除邊界點(diǎn)而增大，使類結(jié)構(gòu)探測更為容易。該步驟主要通過對(duì)非邊界點(diǎn)進(jìn)行聚類進(jìn)而找到數(shù)據(jù)集的核心類結(jié)構(gòu)。首先，從非邊界點(diǎn)找到密度最大點(diǎn)，將該點(diǎn)放入一個(gè)新的隊(duì)列中；然后將該點(diǎn)的k最近鄰點(diǎn)中尚未分配標(biāo)簽的點(diǎn)加入到該隊(duì)列中，遍歷隊(duì)列中的下一個(gè)點(diǎn)，也將其尚未分配標(biāo)簽的k最近鄰點(diǎn)加入隊(duì)列中，依次遍歷隊(duì)列，直到?jīng)]有尚未分配的非邊界點(diǎn)與隊(duì)列中數(shù)據(jù)點(diǎn)存在k最近鄰關(guān)系；最后給隊(duì)列中數(shù)據(jù)點(diǎn)分配新的類標(biāo)簽。以這種方式，訪問剩余尚未分配的非邊界點(diǎn)，直到所有非邊界點(diǎn)類標(biāo)簽分配完畢。

圖2 為該步驟對(duì)非邊界點(diǎn)進(jìn)行聚類的結(jié)果，可以看出通過第一步的邊界區(qū)域識(shí)別后，可以對(duì)非邊界點(diǎn)進(jìn)行有效的聚類（空白點(diǎn)是邊界點(diǎn)），得到數(shù)據(jù)集的核心類結(jié)構(gòu)。

圖2 Flame數(shù)據(jù)集和Jain數(shù)據(jù)集上的非邊界點(diǎn)聚類Fig.2 Non-border point clustering on Flame dataset and Jain dataset

2.3 邊界點(diǎn)分配

在該步驟中，對(duì)第一步中識(shí)別的邊界點(diǎn)進(jìn)行分配。分配時(shí)，將每個(gè)邊界點(diǎn)分配到它的最近鄰且密度比其大的數(shù)據(jù)點(diǎn)所在的類中。該方法通過先識(shí)別核心類結(jié)構(gòu)再分配邊界點(diǎn)的方法，有效地解決了DPCA 聚類中心點(diǎn)難以確定、因數(shù)據(jù)點(diǎn)的單步分配策略的容錯(cuò)性較差產(chǎn)生的“多米諾骨牌效應(yīng)”等問題。圖3 為經(jīng)過邊界點(diǎn)的分配后得到的最終類結(jié)構(gòu)。

2.4 噪聲點(diǎn)識(shí)別

經(jīng)過邊界點(diǎn)分配后的聚類結(jié)果中可能包含噪聲點(diǎn)。例如，圖3（a）為Flame 數(shù)據(jù)集的聚類結(jié)果，在左上方有兩個(gè)明顯遠(yuǎn)離大多數(shù)數(shù)據(jù)點(diǎn)的點(diǎn)，應(yīng)為噪聲點(diǎn)。該步驟通過對(duì)噪聲點(diǎn)有效識(shí)別的過程進(jìn)一步對(duì)聚類結(jié)果進(jìn)行提升。根據(jù)數(shù)據(jù)異常校驗(yàn)中常用的拉依達(dá)準(zhǔn)則（PauTa 準(zhǔn)則），該步驟通過對(duì)各類中邊界點(diǎn)的密度與所屬類的密度信息比較判斷是否為噪聲點(diǎn)，噪聲點(diǎn)的形式化描述如下：

圖3 Flame數(shù)據(jù)集和Jain數(shù)據(jù)集上的邊界點(diǎn)分配Fig.3 Border point allocation on Flame dataset and Jain dataset

其中：noise表示滿足條件的噪聲點(diǎn)集合；den(xi)表示數(shù)據(jù)點(diǎn)xi的密度；cl(xi)表示數(shù)據(jù)點(diǎn)xi所在類的標(biāo)號(hào)；mean(cl(xi))表示數(shù)據(jù)點(diǎn)xi所在類cl中點(diǎn)的密度均值；std(cl(xi))表示數(shù)據(jù)點(diǎn)xi所在類cl中點(diǎn)的標(biāo)準(zhǔn)差。

如圖4 所示，該步驟在有噪聲的Flame 和無噪聲的Jain數(shù)據(jù)集上進(jìn)行了噪聲識(shí)別結(jié)果。通過圖4（a）中可以看出左上角的兩個(gè)噪聲點(diǎn)可以被成功識(shí)別出來，并得到最終的聚類結(jié)果。

圖4 Flame數(shù)據(jù)集和Jain數(shù)據(jù)集上的噪聲點(diǎn)識(shí)別Fig.4 Noise point recognition on Flame dataset and Jain dataset

因此，基于上述思想，本文提出一種基于邊界點(diǎn)檢測的變密度聚類算法，如算法1 所示。

算法1 基于邊界點(diǎn)檢測的變密度聚類算法（VDCBD）。

輸入數(shù)據(jù)集D；最近鄰數(shù)k。

輸出聚類結(jié)果cluster。

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

為驗(yàn)證VDCBD 的有效性，與多個(gè)聚類算法在人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了比較。比較算法包括經(jīng)典的K-means 算法［2］、DBSCAN 算法［6］，以及三個(gè)新算法DPCA［8］、CLUB 算法［17］和BP 算法［20］。其中，DPCA 和CLUB 算法可以處理具有任意密度的復(fù)雜數(shù)據(jù)集。對(duì)于每個(gè)算法，通過大量的迭代實(shí)驗(yàn)調(diào)整其相應(yīng)的輸入?yún)?shù)確定最優(yōu)的聚類結(jié)果。其中只有BP 算法基于Python3.8 運(yùn)行，本文所提VDCBD 和其余對(duì)比算法都是基于Matlab 2019b 上運(yùn)行的結(jié)果。實(shí)驗(yàn)環(huán)境為Windows10 操作系統(tǒng)，Intel Core i7-4790 CPU @3.60 GHz。

3.1 人造數(shù)據(jù)集的聚類結(jié)果

VDCBD 和5 個(gè)比較算法在8 個(gè)人造數(shù)據(jù)集上進(jìn)行了聚類結(jié)果的可視化展示并通過幾種評(píng)價(jià)指標(biāo)對(duì)其聚類結(jié)果進(jìn)行了評(píng)價(jià)。8 個(gè)數(shù)據(jù)集的樣本數(shù)、特征數(shù)、真實(shí)類個(gè)數(shù)和來源如表1 所示，其中6 個(gè)都標(biāo)明了來源，S1 和S2 是自制的變密度數(shù)據(jù)集，數(shù)據(jù)集T4、T8、S1 和S2 沒有真實(shí)類別信息。

表1 人造數(shù)據(jù)集描述Tab.1 Description of artificial datasets

8 個(gè)數(shù)據(jù)集的真實(shí)分布如圖5 所示，不同顏色和形狀代表不同的類別，其中黑色空白點(diǎn)表示數(shù)據(jù)集中的噪聲點(diǎn)。

圖5 8個(gè)數(shù)據(jù)集的真實(shí)分布Fig.5 Real distribution of 8 datasets

本文采用4 種不同的指標(biāo)對(duì)算法性能進(jìn)行了度量，包括準(zhǔn)確度（Accuracy，ACC）［23］、F 度量（F-Measure，F(xiàn)M）［24］、標(biāo)準(zhǔn)化互信息（Normalized Mutual Information，NMI）［25］和調(diào)整蘭德指數(shù)（Adjusted Rand Index，ARI）［26］。其中只有ARI取值范圍為［-1，1］，其余三個(gè)評(píng)價(jià)指標(biāo)取值范圍為［0，1］，其值越大，表明算法聚類結(jié)果與真實(shí)標(biāo)簽越吻合，聚類結(jié)果越好。

圖6～13 分別為6 種算法在8 個(gè)人造數(shù)據(jù)集上的聚類結(jié)果。每個(gè)算法都有自己的參數(shù)設(shè)置，其中K-means 算法中參數(shù)K表示數(shù)據(jù)集類的個(gè)數(shù)；DBSCAN 算法中參數(shù)epsion表示數(shù)據(jù)集中每個(gè)對(duì)象的鄰域半徑閾值，參數(shù)MinPts表示對(duì)象的鄰域半徑中對(duì)象個(gè)數(shù)的閾值；DPCA 中參數(shù)percent表示求截?cái)嗑嚯x時(shí)的百分比大??；CLUB 算法和本文VDCBD 的參數(shù)k表示k最近鄰的個(gè)數(shù)。每個(gè)算法名稱后括號(hào)中的數(shù)字表示該最優(yōu)結(jié)果對(duì)應(yīng)的參數(shù)值。

圖6 6種算法在Flame數(shù)據(jù)集上的結(jié)果Fig.6 Results of 6 algorithms on Flame dataset

圖6 為6 種算法對(duì)Flame 數(shù)據(jù)集的聚類結(jié)果。從圖6（a）可以看出，K-means 算法因只能處理球形數(shù)據(jù)集無法對(duì)該數(shù)據(jù)集進(jìn)行有效聚類。從圖6（b）～（c）可以看出，DBSCAN 算法和DPCA 雖然能準(zhǔn)確識(shí)別出數(shù)據(jù)的基本框架，但未能準(zhǔn)確識(shí)別其中的噪聲點(diǎn)，對(duì)后續(xù)的數(shù)據(jù)分析工作造成一定的影響。CLUB 算法、BP 算法和VDCBD 可以得到正確的聚類結(jié)果。

圖7 為6 種算法在Jain 數(shù)據(jù)集上的聚類結(jié)果，Jain 數(shù)據(jù)集是一個(gè)典型的變密度數(shù)據(jù)集。從圖7 可以看出：K-means 算法和DPCA 將下方數(shù)據(jù)集的一部分錯(cuò)誤地分配給了上方的類，而DBSCAN 算法則將數(shù)據(jù)集的一部分錯(cuò)分成為一個(gè)新的類，CLUB 算法則將其上方類錯(cuò)誤地分成三個(gè)小類并將一部分點(diǎn)識(shí)別為噪聲點(diǎn)，BP 算法則將其錯(cuò)誤地分成多個(gè)類并產(chǎn)生了大量的噪聲點(diǎn)，只有VDCBD 對(duì)Jain 數(shù)據(jù)集的聚類效果最好。

圖7 6種算法在Jain數(shù)據(jù)集上的結(jié)果Fig.7 Results of 6 algorithms on Jain dataset

圖8 所示的6 種算法在Aggregation 數(shù)據(jù)集上的聚類結(jié)果表明：大多數(shù)算法可以對(duì)Aggregation 數(shù)據(jù)集進(jìn)行有效聚類，只有K-means 算法無法對(duì)該數(shù)據(jù)集進(jìn)行有效聚類，DBSCAN算法和CLUB 算法則將少量的數(shù)據(jù)點(diǎn)識(shí)別為噪聲點(diǎn)。圖9 為6 種算法在具有典型球形結(jié)構(gòu)的D31 數(shù)據(jù)集上的聚類結(jié)果。從圖9（b）可以看出DBSCAN 算法未能將相鄰的兩個(gè)類分開，且將大量的數(shù)據(jù)點(diǎn)識(shí)別為噪聲點(diǎn)，CLUB 算法和BP 算法將部分的數(shù)據(jù)點(diǎn)識(shí)別為噪聲點(diǎn)，其余算法對(duì)D31 數(shù)據(jù)集的聚類結(jié)果都較好。

圖8 6種算法在Aggregation數(shù)據(jù)集上的結(jié)果Fig.8 Results of 6 algorithms on Aggregation dataset

圖9 6種算法在D31數(shù)據(jù)集上的結(jié)果Fig.9 Results of 6 algorithms on D31 dataset

圖10～11 展示了6 種算法在兩個(gè)數(shù)據(jù)規(guī)模達(dá)到8 000 的數(shù)據(jù)集上的聚類結(jié)果，T4 和T8 均是具有復(fù)雜結(jié)構(gòu)和噪聲點(diǎn)的數(shù)據(jù)集，且T8 數(shù)據(jù)集中包含不同密度的類為典型的變密度數(shù)據(jù)集。從圖10 中可以看出，算法在對(duì)復(fù)雜數(shù)據(jù)集T4 聚類時(shí)，K-means 算法、BP 算法和DPCA 未能識(shí)別真實(shí)類結(jié)構(gòu)，DBSCAN 算法雖能識(shí)別出數(shù)據(jù)的真實(shí)類，但卻有多個(gè)小類被錯(cuò)誤識(shí)別，只有VDCBD 和CLUB 算法可以對(duì)數(shù)據(jù)進(jìn)行有效地聚類且能識(shí)別出噪聲點(diǎn)。從圖11 中可以看出，只有VDCBD 能夠準(zhǔn)確識(shí)別T8 數(shù)據(jù)集的類結(jié)構(gòu)，并能識(shí)別其中的噪聲點(diǎn)，其余算法都不能識(shí)別真實(shí)的類結(jié)構(gòu)。

圖10 6種算法在T4數(shù)據(jù)集上的結(jié)果Fig.10 Results of 6 algorithms on T4 dataset

圖11 6種算法在T8數(shù)據(jù)集上的結(jié)果Fig.11 Results of 6 algorithms on T8 dataset

圖12～13 所用數(shù)據(jù)集為本文提供的兩個(gè)變密度數(shù)據(jù)集。從圖12 所示的6 種算法在S1 數(shù)據(jù)集的聚類結(jié)果可以看出：只有VDCBD 可以得到較好的聚類結(jié)果，DBSCAN 算法錯(cuò)誤地將上方類分為幾個(gè)新類且將大量的點(diǎn)識(shí)別為噪聲點(diǎn)。CLUB 算法可以識(shí)別出三個(gè)真實(shí)類，但將上方類中的部分?jǐn)?shù)據(jù)點(diǎn)錯(cuò)誤劃分為其他類或噪聲點(diǎn)，其余算法均未能識(shí)別真實(shí)的類結(jié)構(gòu)。圖13 的S2 數(shù)據(jù)集相較于S1 相鄰的類之間的密度差更大，從（d）可以看出對(duì)S1 數(shù)據(jù)集有較好聚類效果的CLUB 算法也未能將兩個(gè)密度相差較大的類進(jìn)行準(zhǔn)確地聚類，DPCA 和CLUB 算法無法識(shí)別出上方半環(huán)型的類。只有VDCBD 準(zhǔn)確地識(shí)別了數(shù)據(jù)集的類結(jié)構(gòu)，僅將少量的點(diǎn)識(shí)別為噪聲點(diǎn)。

圖12 6種算法在S1數(shù)據(jù)集上的結(jié)果Fig.12 Results of 6 algorithms on S1 dataset

圖13 6種算法在S2數(shù)據(jù)集上的結(jié)果Fig.13 Results of 6 algorithms on S2 dataset

從8 個(gè)人造數(shù)據(jù)集的可視化結(jié)果中可以發(fā)現(xiàn)，本文VDCBD 相較于其他算法在處理具有復(fù)雜結(jié)構(gòu)且密度不均的數(shù)據(jù)集時(shí)更加有效。表2 為VDCBD 與對(duì)比算法在4 個(gè)人造數(shù)據(jù)集上通過四種評(píng)價(jià)指標(biāo)進(jìn)行質(zhì)量評(píng)價(jià)的結(jié)果，其中T4、T8、S1 和S2 數(shù)據(jù)集由于沒有真實(shí)標(biāo)簽，因此這四個(gè)數(shù)據(jù)集沒有出現(xiàn)在表2 中。

從表2 中可以看出，在具有復(fù)雜結(jié)構(gòu)的Flame 數(shù)據(jù)集和Aggregation 數(shù)據(jù)集中，除了K-means 算法外，其余算法均獲得了較好的聚類結(jié)果，VDCBD 達(dá)到了最高的聚類結(jié)果，且參數(shù)k的取值在一定程度上有著不錯(cuò)的魯棒性。在對(duì)變密度數(shù)據(jù)集Jain 的聚類中，VDCBD 可以對(duì)該數(shù)據(jù)集準(zhǔn)確聚類，在四個(gè)評(píng)價(jià)指標(biāo)上均達(dá)到了最高值1，說明了本文算法在處理變密度數(shù)據(jù)集時(shí)的有效性。在典型的球形數(shù)據(jù)集D31 結(jié)果中可以看出，VDCBD 和K-means 算法的聚類結(jié)果相差無幾，僅在ARI 和NMI 評(píng)價(jià)指標(biāo)上略低于K-means 算法，但VDCBD 在四種評(píng)價(jià)指標(biāo)上均高于其余4 種密度聚類算法。綜上所述，本文提出的VDCBD 在處理復(fù)雜結(jié)構(gòu)的人工數(shù)據(jù)集，尤其是在變密度數(shù)據(jù)集時(shí)與其他算法相比可以獲得更優(yōu)的聚類結(jié)果。

表2 6種算法在4個(gè)人造數(shù)據(jù)集上的聚類結(jié)果Tab.2 Clustering results of 6 algorithms on 4 artificial datasets

3.2 真實(shí)數(shù)據(jù)集的聚類結(jié)果

為了驗(yàn)證算法在真實(shí)環(huán)境下的有效性，用6 種聚類算法對(duì)真實(shí)數(shù)據(jù)集進(jìn)行聚類來驗(yàn)證算法的有效性。其中，真實(shí)數(shù)據(jù)集來源于UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫［27］，其詳細(xì)信息可見表3。

表3 真實(shí)數(shù)據(jù)集描述Tab.3 Description of real datasets

在UCI 數(shù)據(jù)集上的聚類結(jié)果仍然采用ARI、NMI、FM 和ACC 四個(gè)評(píng)價(jià)指標(biāo)進(jìn)行質(zhì)量評(píng)價(jià)，并給出了聚類結(jié)果對(duì)應(yīng)的參數(shù)。6 種算法在真實(shí)數(shù)據(jù)集的聚類結(jié)果如表4 所示。

表4 6種算法在8個(gè)真實(shí)數(shù)據(jù)集上的聚類結(jié)果Tab.4 Clustering results of 6 algorithms on 8 real datasets

從6 種算法在真實(shí)數(shù)據(jù)集上的聚類評(píng)價(jià)結(jié)果可以看出，VDCBD 相較于對(duì)比算法在Iris、Leaf 和Ecoli 三個(gè)數(shù)據(jù)集上聚類效果最好；在Wine 數(shù)據(jù)集上雖未達(dá)到最好的聚類結(jié)果，但相較于其余4 種密度聚類算法有不小的提升。在Seeds 數(shù)據(jù)集中，VDCBD 在ARI 評(píng)價(jià)指標(biāo)上達(dá)到了最好結(jié)果，并且在四種評(píng)價(jià)指標(biāo)上均高于K-means、DBSCAN、DPCA 與BP 算法。在Segmentation 數(shù)據(jù)集中，VDCBD 和DBSCAN 算法在該數(shù)據(jù)集的聚類結(jié)果相差無幾，在ARI 和FM 兩個(gè)指標(biāo)上相比DBSCAN 算法略有提升。當(dāng)數(shù)據(jù)規(guī)模達(dá)到5 000 以上時(shí)，VDCBD 與對(duì)比的密度聚類算法相比仍具有一定的競爭力。綜上所知，VDCBD 在處理真實(shí)數(shù)據(jù)集上的聚類結(jié)果相較于對(duì)比算法有一定的提升。

3.3 時(shí)間復(fù)雜度及運(yùn)行效率分析

本文VDCBD 在計(jì)算數(shù)據(jù)點(diǎn)的密度時(shí)，時(shí)間復(fù)雜度為O（n2），其中n為數(shù)據(jù)集大??；在第一步邊界點(diǎn)的檢測過程中，時(shí)間代價(jià)至多為O（k×n）+O（r×n），其中k為最近鄰個(gè)數(shù)（k?n），r為數(shù)據(jù)點(diǎn)最大的RKKN 的個(gè)數(shù)；在第二步對(duì)非邊界點(diǎn)的識(shí)別過程中，其時(shí)間代價(jià)最大為O（k×m2），其中m為非邊界點(diǎn)的個(gè)數(shù)；第三步對(duì)邊界點(diǎn)的分配過程中，時(shí)間代價(jià)為O（n×（n-m））+O（n）；最后對(duì)各類中噪聲點(diǎn)的識(shí)別過程中，時(shí)間代價(jià)為O（c_count×g）+O（m），其中c_count為類別數(shù)，g為類中的最大數(shù)據(jù)個(gè)數(shù)。綜合以上分析，本文算法的總時(shí)間復(fù)雜度為O（n2）。

K-means 算法的時(shí)間復(fù)雜度為O（t×n×K×ml），為線性時(shí)間復(fù)雜度，其中：t為迭代次數(shù)，K為類的數(shù)目，n為數(shù)據(jù)集總個(gè)數(shù)，ml為數(shù)據(jù)點(diǎn)維度；DPCA 和DBSCAN 算法的時(shí)間復(fù)雜度為O（n2）；BP 算法的時(shí)間復(fù)雜度為O（t×（k×n+fknn）），其中：fknn是k最近鄰的漸進(jìn)時(shí)間復(fù)雜度。CLUB 算法的時(shí)間復(fù)雜度為O（nlogn）。

由于6 種算法在小規(guī)模數(shù)據(jù)集上的運(yùn)行時(shí)間均較小，因此文中只比較了在數(shù)據(jù)規(guī)模達(dá)到5 000 以上的數(shù)據(jù)集的實(shí)際運(yùn)行耗時(shí)。圖14 展示了6 種聚類算法在較大規(guī)模數(shù)據(jù)集上的運(yùn)行時(shí)間比較。為了保證數(shù)據(jù)的穩(wěn)定性，每種算法均獨(dú)立運(yùn)行50 次，取平均值作為算法在該數(shù)據(jù)集上的運(yùn)行時(shí)間。

通過圖14 可以看出，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，VDCBD 的運(yùn)行效率高于DPCA、CLUB 算法和BP 算法。

圖14 6種算法的運(yùn)行時(shí)間比較Fig.14 Comparison of running time of 6 algorithms

4 結(jié)語

本文提出了一種基于邊界點(diǎn)檢測的變密度聚類算法VDCBD，用于更加有效地處理具有復(fù)雜結(jié)構(gòu)、任意密度的數(shù)據(jù)集。不同于以往通過尋找聚類中心點(diǎn)聚類的方法，算法首先識(shí)別各類邊界區(qū)域，擴(kuò)大各類間的距離；第二步，通過對(duì)非邊界區(qū)域的點(diǎn)進(jìn)行聚類獲得數(shù)據(jù)集的核心類結(jié)構(gòu)，之后根據(jù)高密度近鄰分配原則將檢測到的邊界點(diǎn)分配到核心類結(jié)構(gòu)中；最后基于類結(jié)構(gòu)信息識(shí)別數(shù)據(jù)集中的噪聲點(diǎn)，得到最終的聚類結(jié)果。實(shí)驗(yàn)結(jié)果表明，本文所提VDCBD 在人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上具有一定的優(yōu)勢，相較于對(duì)比算法更加準(zhǔn)確有效，尤其在變密度數(shù)據(jù)集上聚類效果更加明顯。

在未來的工作中，考慮將分而治之的思想融入到提出的密度聚類算法中，進(jìn)而使其能夠高效地處理大規(guī)模數(shù)據(jù)。另外，現(xiàn)有數(shù)據(jù)可能存在特征值缺失的情況，給密度聚類算法來了新的挑戰(zhàn)，這也是下一步工作的研究重點(diǎn)。