王躍飛 于 炯 蘇國平 錢育蓉 廖 彬 劉 粟

聚類算法在計算機(jī)科學(xué)、交通運(yùn)輸、電子商務(wù)[1?3]等越來越多的學(xué)科、領(lǐng)域中均有重要應(yīng)用.特別在計算機(jī)領(lǐng)域,聚類算法是機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘及人工智能的基礎(chǔ).相應(yīng)的,各類豐富的聚類思想及其衍生算法應(yīng)運(yùn)而生.總體上,聚類可分為基于劃分、密度、網(wǎng)格、層次等方法,不同的方法采用了不同的聚類思想和技術(shù),致使聚類結(jié)果具備多樣化特征.

聚類技術(shù)同樣是孤立點(diǎn)檢測的重要手段.孤立點(diǎn)概念的提出[4]不僅使各行業(yè)的數(shù)據(jù)純度得以有效保障,同樣為新知識的探索和挖掘提供了重要依據(jù).

在目前的研究進(jìn)展中,有基于統(tǒng)計學(xué)[5?6],基于距離[7?8],基于密度[9?10]與基于聚類等不同的檢測思想,在聚類技術(shù)的檢測手段中,一般是將生成的簇外點(diǎn)置為孤立點(diǎn).

然而,主流方法一般聚焦于簇間的孤立點(diǎn)檢測,而忽略了簇內(nèi)的孤立點(diǎn),聚類算法更是將簇范圍下的點(diǎn)均默認(rèn)為正常點(diǎn),不啟用二次審查.實(shí)際上,簇內(nèi)的孤立點(diǎn)是有可能存在的,主要原因是聚類屬于無監(jiān)督學(xué)習(xí)(Unsupervised learning),在沒有指示標(biāo)簽的情況下,不同的聚類方法可能產(chǎn)生多種結(jié)果,包括簇的數(shù)目不同;另一方面,在大部分行業(yè)中孤立點(diǎn)是動態(tài)生成的,如在醫(yī)學(xué)領(lǐng)域中,病變早期細(xì)胞組織的位置由正常區(qū)域逐漸位移,使聚類的幾何中心產(chǎn)生偏移,因此及早地發(fā)現(xiàn)簇內(nèi)異常對這類現(xiàn)象具有重大意義.

圖1 的3 種現(xiàn)象描述了簇內(nèi)孤立點(diǎn)的產(chǎn)生原因.

圖1 簇內(nèi)孤立點(diǎn)產(chǎn)出原因Fig.1 The cause of inliers

現(xiàn)象1:當(dāng)使用不同方法或參數(shù),使原先多個簇發(fā)生融合時,先前在多簇間被判定為孤立點(diǎn)的對象會被判定為正常點(diǎn),產(chǎn)生誤判.

現(xiàn)象2:當(dāng)多個簇發(fā)生融合時,若匯聚的一面為簇的邊緣,則匯聚后簇存在松散域,其中的點(diǎn)可能具有孤立性質(zhì).

現(xiàn)象3:當(dāng)點(diǎn)集緊密投影在區(qū)域內(nèi)部時,若有一處存在明顯稀疏或空白,則該區(qū)域下的點(diǎn)需要重點(diǎn)考證研究.

以上三類典型現(xiàn)象不僅描述了具有孤立性質(zhì)的點(diǎn)被判定為正常點(diǎn)的情況,同時可以將簇內(nèi)孤立點(diǎn)按產(chǎn)生原因分為兩類:1)聚類技術(shù)中,不同的參數(shù)使簇發(fā)生融合時產(chǎn)生;2)數(shù)據(jù)的原始分布造成.以上誤判的出現(xiàn)影響了聚類效果,污染了數(shù)據(jù)純度,降低了數(shù)據(jù)質(zhì)量.在聚類計算中,忽略簇內(nèi)孤立點(diǎn)容易造成簇中心位置的誤判;在各類生產(chǎn)生活以及應(yīng)用中,由于參數(shù)或方法的不當(dāng)使用,孤立點(diǎn)的忽略更可能會帶來安全隱患.為避免上述現(xiàn)象的出現(xiàn),需要對簇內(nèi)孤立點(diǎn)進(jìn)行更加深入的研究,設(shè)計更為有效的簇內(nèi)孤立點(diǎn)判定算法.該算法需具有以下3 方面的功能:

1)能夠分析簇間孤立點(diǎn);

2)能夠分析簇內(nèi)孤立點(diǎn);

3)不影響聚類效果且時間復(fù)雜度較低.

本文提出一種對簇內(nèi)孤立點(diǎn)敏感的方法:ODIC-DBSCAN,該方法考慮到不同半徑下密度間的關(guān)系,通過有效相鄰半徑構(gòu)成的多維體能夠覆蓋點(diǎn)集的思想,計算在不同密度下的相關(guān)參數(shù),重構(gòu)了DBSCAN 框架,查找出簇內(nèi)孤立點(diǎn).本文的主要工作有以下幾方面:

1)獲取有效半徑.為檢測簇內(nèi)部的孤立點(diǎn),首先對數(shù)據(jù)集的密度進(jìn)行層次劃分,并提出半徑獲取策略.該方法能夠根據(jù)點(diǎn)與點(diǎn)間的距離關(guān)系對任意數(shù)據(jù)集提取有效半徑.

2)提出點(diǎn)集覆蓋的思想.該思想以有效半徑為基礎(chǔ),分割覆蓋為原則,表示為相鄰有效半徑能將數(shù)據(jù)集完整覆蓋.在此基礎(chǔ)上,通過相鄰有效半徑構(gòu)造出多條無差別曲線,每一條曲線的點(diǎn)均能描述數(shù)據(jù)集被覆蓋的情況,并使用拉格朗日乘子法求取了最優(yōu)值.

3)從兩方面重構(gòu)了DBSCAN 算法.第一,修改了DBSCAN 中核心對象的定義,以相鄰半徑間點(diǎn)數(shù)的比值代替了半徑下點(diǎn)的數(shù)目.第二,提出了算法的終止條件,以簇間是否發(fā)生融合現(xiàn)象作為聚類效果的依據(jù).

本文第1 節(jié)簡要概述相關(guān)工作.第2 節(jié)首先介紹了DBSCAN 的缺陷,提出了解決方法;并在后續(xù)的小節(jié)中詳細(xì)介紹了ODIC-DBSCAN 的模型研究,依序包括半徑獲取策略(第2.2 節(jié))與點(diǎn)集覆蓋模型(第2.3 節(jié)),并在第2.4 節(jié)中展開聚類算法的重構(gòu)工作;最后分析了算法時間復(fù)雜度.實(shí)驗(yàn)部分在第3 節(jié)中展開,該部分展示了ODIC-DBSCAN 算法的運(yùn)行細(xì)節(jié);分析了算法的兩項(xiàng)性能指標(biāo);驗(yàn)證了算法對簇內(nèi)孤立點(diǎn)辨別的優(yōu)勢,并與其他同類算法的運(yùn)行效果進(jìn)行了對比.

1 相關(guān)工作

當(dāng)前大部分聚類算法對簇內(nèi)或簇間的孤立點(diǎn)檢測均有一定的效果,但傳統(tǒng)算法由于關(guān)注聚類的思想、結(jié)果、效率、以及孤立程度等問題,并未專注于簇內(nèi)孤立點(diǎn)的發(fā)現(xiàn),因此對簇內(nèi)孤立點(diǎn)并不敏感.總體上,孤立點(diǎn)的研究是一個寬廣的領(lǐng)域,針對各個類型的數(shù)據(jù),孤立點(diǎn)檢測有不同的方法[11],如高維數(shù)據(jù)[12]、不確定數(shù)據(jù)[13]、流式數(shù)據(jù)[14]、網(wǎng)絡(luò)數(shù)據(jù)[15].目前在基礎(chǔ)研究中,孤立點(diǎn)的分析與進(jìn)展有以下方面:文獻(xiàn)[9]在密度聚類的基礎(chǔ)上,提出了一種將點(diǎn)數(shù)據(jù)分為多個層次的思想,使同一層的數(shù)據(jù)在全局具有相似的特性,ISDBSCAN (Influence space DBSCAN)思想與距離有關(guān),算法在目標(biāo)對象的一定范圍內(nèi)根據(jù)鄰居點(diǎn)距離的總和使目標(biāo)對象分層.Duan 等[16]針對密度聚類,對個別小規(guī)模的簇被判定為孤立點(diǎn)的現(xiàn)象提出優(yōu)化方法,所提出的LDBSCAN (Local-density based spatial clustering algorithm with noise)方法能達(dá)到分離簇與點(diǎn)的目的;文獻(xiàn)[16]認(rèn)為,孤立點(diǎn)的現(xiàn)象不應(yīng)僅僅是單獨(dú)點(diǎn)離群的狀態(tài),在較小的簇偏離點(diǎn)集主體區(qū)域時,該簇內(nèi)的點(diǎn)均應(yīng)被認(rèn)作孤立點(diǎn);在基于簇的孤立點(diǎn)(Cluster-based outlier)檢測中,文章提出了LDBSCAN 算法,并提出了離群簇孤立程度的計算方式.文獻(xiàn)[17]針對傳統(tǒng)孤立點(diǎn)檢測在大規(guī)模數(shù)據(jù)集中效果差強(qiáng)人意的現(xiàn)象,提出了一種基于統(tǒng)計的孤立點(diǎn)檢測方法.首先通過三倍標(biāo)準(zhǔn)差法記錄密度峰值,其次將剩余數(shù)據(jù)以近鄰原則指定到相應(yīng)的簇中,最后使用切比雪夫不等式與密度可達(dá)性來判定目標(biāo)點(diǎn)是否為孤立點(diǎn).文獻(xiàn)[18]使用分治思想(Divide-and-conquer strategy)提出一種孤立點(diǎn)識別策略:初始時數(shù)據(jù)集被分為兩個簇,然后算法在全局過程中通過迭代來檢查兩個密度波峰是否密度可達(dá),以驗(yàn)證二者是否為同一個簇,循環(huán)后最終將點(diǎn)指定到所屬簇中.上述工作計算了邊緣密度,因此當(dāng)點(diǎn)的邊緣密度低于閾值時被認(rèn)作孤立點(diǎn).文獻(xiàn)[19]提出了不再將孤立點(diǎn)定義為二值屬性,而是根據(jù)被孤立的程度給予不同的局部異常因子,對于模糊點(diǎn),給定了LOF (Local outlier factor)的值邊界.在基于非二值屬性的宏觀思想下,面向角度[20],面向距離[7]等檢測方法應(yīng)運(yùn)而生.以上方法能對任意數(shù)據(jù)對象賦予孤立程度(Outlier-ness),只是檢測的思想不同.文獻(xiàn)[20]考慮角度因素,并論證了角度特征對高維空間下的數(shù)據(jù)衡量更加精準(zhǔn);F-ABOD 方法比對任意三點(diǎn)構(gòu)成的兩個向量間夾角大小,通過角度確定點(diǎn)距簇心的遠(yuǎn)近.文獻(xiàn)[7]著重距離因素,對數(shù)據(jù)點(diǎn)建立雙層鄰居系統(tǒng)(Neighborhood system),并通過雙層鄰居的距離關(guān)系反饋核心點(diǎn)的孤立性.

聚類是一種檢測孤立點(diǎn)的有效手段,基于密度的檢測思想是檢驗(yàn)點(diǎn)間關(guān)系的有效方法.在這些方法中,Rodriguez 等提出一種基于密度峰值聚類的方法DPC (Density peaks clustering,DPC)[21],該方法認(rèn)為,簇中心的密度一定比邊緣處高,且與距它密度更高的簇心距離較大;在此思想上,算法不斷尋找被低密區(qū)域分離的高密區(qū)域.該方法的優(yōu)勢是不需迭代,因此運(yùn)行時間短.在此基礎(chǔ)上,相關(guān)的研究工作陸續(xù)展開,包括參數(shù)優(yōu)化[22],聚類的集成[23],自適應(yīng)模糊聚類[24],以及社交網(wǎng)絡(luò)下的聚類應(yīng)用[25]等.另一種基于密度的方法是通過數(shù)據(jù)點(diǎn)間執(zhí)行“信息傳遞”而進(jìn)行聚類[26].AP (Affinity propagation)算法不需指定簇的數(shù)目,而是通過建立吸引信息(Responsibility)與歸屬信息(Availability)兩類矩陣,并引入衰減系數(shù)對兩類信息進(jìn)行衰減迭代,當(dāng)矩陣值穩(wěn)定時,聚類結(jié)束.在AP 技術(shù)的研究基礎(chǔ)上,一些相關(guān)的工作也被相繼提出,如圖像中半監(jiān)督的AP 聚類方法[27],基于層次劃分的AP 聚類[28]等.OPTICS (Ordering points to identify the clustering structure)是將空間數(shù)據(jù)依據(jù)密度執(zhí)行聚類的一種方法[29],在DBSCAN 的基礎(chǔ)上,OPTICS 的聚類對象能應(yīng)用于多密度點(diǎn)集,但算法生成的可達(dá)距離RD (Reachability distance)不能顯示的生成聚類結(jié)果,僅生成包含聚類信息的有序?qū)ο罅斜?另外,針對一種密度閾值無法滿足全局?jǐn)?shù)據(jù)分布的需要,文獻(xiàn)[30]提出一種基于密度比(Density-ratio)的思想,并將其應(yīng)用于DBSCAN、OPTICS 等方法.該思想包含Reconditioning approach 與Rescaling approach 兩類方法,前者提出使用密度比而非密度閾值的解決辦法,可以植入相關(guān)的密度聚類;后者對數(shù)據(jù)集的坐標(biāo)進(jìn)行重投射,使生成的范圍點(diǎn)集密度接近預(yù)設(shè)的密度比參數(shù),這樣,使原數(shù)據(jù)集的密度標(biāo)準(zhǔn)化之后再進(jìn)行聚類.另外,在算法的應(yīng)用研究中,孤立點(diǎn)的識別在不同領(lǐng)域中已經(jīng)有了較大程度的進(jìn)展.在關(guān)于圖像的孤立點(diǎn)判定識別中,文獻(xiàn)[31]通過計算簇內(nèi)圖像數(shù)據(jù)偏離的評分確定孤立程度,這個評分根據(jù)將簇內(nèi)點(diǎn)抽離后圖像信息的變化量來確定.文獻(xiàn)[32]通過使用隨機(jī)森林與DBSCAN 聚類方法對類似姓名等文本做出識別處理.在無線傳感器網(wǎng)絡(luò)的孤立點(diǎn)檢測中,借用DBSCAN 方法,在計算參數(shù),空間時態(tài)數(shù)據(jù)庫下識別出具體的類信息,且能夠識別出離群點(diǎn)[33].

2 模型與策略

2.1 問題分析

基于密度的聚類(Density-based clustering)能根據(jù)樣本間的密度關(guān)系確定簇的形成,通過鄰域大小與該區(qū)域內(nèi)點(diǎn)數(shù)目的關(guān)系考察點(diǎn)之間的連通性,刻畫簇的構(gòu)成.DBSCAN 算法能將接收到的核心對象(Core object)按不同密度,以不同形狀執(zhí)行聚類,但忽略了點(diǎn)集不同密度間的聯(lián)系.1)DBSCAN算法僅能接受一種密度條件,并且在沒有先驗(yàn)知識的條件下,半徑無法明確指定.2)局部數(shù)據(jù)并非遵循高斯分布,在圖1 中的分布現(xiàn)象中,由于輸入?yún)?shù)的限制,DBSCAN 不能很好地處理離散點(diǎn)的分析工作.3)密度聚類錯過了微觀角度下點(diǎn)與點(diǎn)之間的關(guān)系.在一個簇中,雖然宏觀角度下呈現(xiàn)高密特征,但微觀下個別特殊的點(diǎn)與點(diǎn)間可能包含差異較大的距離,遺憾的是,DBSCAN 不能識別類似的特殊點(diǎn).在簇擴(kuò)充的工作中,DBSCAN 通過epsilon鄰域中點(diǎn)的個數(shù)確定該點(diǎn)是否為核心對象;該方法能夠計算目標(biāo)點(diǎn)的密度狀態(tài),但忽略了不同密度條件下的不同結(jié)果.

簇內(nèi)孤立點(diǎn)的特性在于目標(biāo)點(diǎn)與周圍的鄰居具有密度差異,該差異可能由點(diǎn)的分布直接造成,也可能由聚類算法的參數(shù)使用不當(dāng)生成.在點(diǎn)集中,由于其與周圍鄰居密度差異較小而經(jīng)常被忽視,因而簇內(nèi)孤立點(diǎn)的檢驗(yàn)需要算法對微小的密度差異具備敏感性.

定義1.簇內(nèi)孤立點(diǎn)(Inlier).表示在數(shù)據(jù)集下的任意簇中,當(dāng)前目標(biāo)點(diǎn)的空間密度較鄰居點(diǎn)更稀疏的一類對象.由數(shù)據(jù)的原始分布,或不當(dāng)參數(shù)造成簇融合時算法對簇間點(diǎn)的誤判兩類原因產(chǎn)生.

當(dāng)簇發(fā)生融合時,簇內(nèi)與簇間孤立點(diǎn)容易被算法錯誤判定.如圖1 所展示的孤立點(diǎn)與正常點(diǎn)相互轉(zhuǎn)換的情況.為解決以上問題,算法改進(jìn)的核心是點(diǎn)在不同半徑下的密度關(guān)系,因此本文關(guān)注于點(diǎn)在不同范圍下的密度關(guān)聯(lián),并重定義DBSCAN 的核心對象.具體技術(shù)是根據(jù)點(diǎn)集的分布情況提取若干由小到大的有效半徑,在密度聚類中根據(jù)該點(diǎn)在兩個半徑下密度之比是否大于數(shù)據(jù)預(yù)處理輸出的閾值來判定該點(diǎn)是否屬于核心對象.

如圖2 所示,左部為DBSCAN 算法的核心對象確定方法.當(dāng)在epsilon半徑下,覆蓋面下的點(diǎn)數(shù)目超過MinPts時,該點(diǎn)(圖中為圓心黑色點(diǎn))為核心對象.右部為ODIC-DBSCAN 的確定方法:通過前期數(shù)據(jù)預(yù)處理輸出的典型半徑ri、rj,確定兩個半徑下覆蓋面積的密度比值,通過比值是否大于前期數(shù)據(jù)預(yù)處理輸出的閾值來確定該點(diǎn)是否為核心對象.

圖2 DBSCAN 與ODIC-DBSCAN 的核心對象確定方法Fig.2 The core object confirmation method of DBSCAN and ODIC-DBSCAN

通過上述方法,能夠確定目標(biāo)點(diǎn)在有效的、逐漸擴(kuò)大的兩個范圍內(nèi)相鄰數(shù)據(jù)量的變化情況.在孤立點(diǎn)分析中,ODIC-DBSCAN 算法循環(huán)地輸入有效半徑集合Radius內(nèi)由小到大相鄰半徑構(gòu)成的開圓密度比,并將此作為聚類核心對象判定的閾值.當(dāng)真實(shí)情況超過該閾值,表示該點(diǎn)的范圍密度較高,為簇內(nèi)點(diǎn);反之該點(diǎn)周圍密度較低,為偏邊緣點(diǎn).當(dāng)選擇Radius的半徑由小至大時(如圖3 所示),簇內(nèi)孤立點(diǎn)的判定逐漸變得粗略,容易產(chǎn)生融合現(xiàn)象,這表示閾值過于寬泛;為避免融合,應(yīng)選擇簇發(fā)生融合之前的結(jié)果作為聚類結(jié)果.

圖3 ODIC-DBSCAN 核心對象在半徑集合Radius 下的遴選Fig.3 The selection of ODIC-DBSCAN core objects from Radius set

上述思想能夠有效判斷以目標(biāo)點(diǎn)為中心,在多重半徑范圍內(nèi)的數(shù)據(jù)點(diǎn)密度的變化情況,并以此作為依據(jù)推斷該點(diǎn)的位置,確定該點(diǎn)是否具有孤立性質(zhì).

ODIC-DBSCAN 算法包含兩個參數(shù),分別位于算法流程下數(shù)據(jù)預(yù)處理、簇內(nèi)孤立點(diǎn)分析這兩個部分.如圖4 所示,在數(shù)據(jù)預(yù)處理部分,首先根據(jù)數(shù)據(jù)集的距離分布狀況,提出一種半徑獲取策略,該策略能夠?qū)?shù)據(jù)集的關(guān)鍵距離遴選出作為半徑集合Radius,并構(gòu)建密度矩陣.當(dāng)獲取到Radius后,提出一種思想,證明任意點(diǎn)集能夠由集合Radius構(gòu)成的覆蓋多維體完全覆蓋;基于此思想,使Radius內(nèi)相鄰半徑ri,rj構(gòu)成的覆蓋多維體覆蓋點(diǎn)集,并計算對應(yīng)半徑構(gòu)成覆蓋多維體的數(shù)目,最終構(gòu)造出點(diǎn)比閾值組.在ODIC-DBSCAN 算法處理部分,重新定義了DBSCAN 中的核心對象,并提供了一種孤立點(diǎn)分析檢測的方法.在以上兩部分順序進(jìn)行后,算法最終輸出簇內(nèi)的孤立點(diǎn)并生成圖像.

2.2 半徑獲取策略

定義2.距離矩陣.描述了點(diǎn)集P中任意兩點(diǎn)之間的歐氏距離.

圖4 ODIC-DBSCAN 處理流程Fig.4 The processing flow of ODIC-DBSCAN

distm×m是距離矩陣的表現(xiàn)形式,在實(shí)際操作中,需要將其轉(zhuǎn)化為一行多列的矩陣格式.因此距離矩陣也被記為dist1×t,其中t為式(1)中對角線以上距離元素的個數(shù).

定義3.密度矩陣.密度矩陣宏觀統(tǒng)計點(diǎn)集P中每個點(diǎn)在一定范圍內(nèi)的點(diǎn)數(shù)量與面積之比.

式(2)的密度矩陣中,列數(shù)m代表數(shù)據(jù)集的點(diǎn)對象,行表示根據(jù)點(diǎn)集的分布而規(guī)劃的k個半徑距離.具體地說,在矩陣元素中,xm表示點(diǎn)對象,rk表示該研究點(diǎn)的密度度量是在以半徑為rk下的開圓中,其中r1

在數(shù)據(jù)集的距離矩陣內(nèi),所有距離元素在長度范圍下的數(shù)目分布中,其波峰一般不少于一個.這表明,多個波峰與波谷的存在形式使距離矩陣的數(shù)據(jù)密集程度具有較強(qiáng)不確定性,不能簡單地通過數(shù)據(jù)邊緣或中心分布確定距離集合具備正態(tài)分布、卡方分布、t分布等分布曲線形態(tài).為有效確定數(shù)據(jù)集內(nèi)點(diǎn)與點(diǎn)間的距離分布情況,提出半徑獲取策略(Radius obtaining strategy).

該策略的主要思想是:自頂向下,逐漸細(xì)化分割,刪去距離為空的范圍.

如圖5～6 所示,在數(shù)據(jù)分布中有簇A 與簇B,共計距離45 個.其中簇內(nèi)距離21 個(實(shí)線),簇間距離24 個(虛線),一般地,簇內(nèi)距離小于簇間距離.設(shè)置一條標(biāo)準(zhǔn)線作為基準(zhǔn),將距離元素的分布劃分為稠密處與稀疏處.稠密處為波峰1、2,分別匯聚了簇內(nèi)點(diǎn)的相互距離元素,以及簇間的距離元素;波谷1 處存在極少該范圍內(nèi)的距離.取出波峰1,執(zhí)行同樣步驟,劃分若干區(qū)間后重新制定新的標(biāo)準(zhǔn),將波峰1 劃分為子波谷1、子波峰1、子波谷2;持續(xù)以上工作,直至波峰波谷細(xì)化完畢,最終確定若干區(qū)間,并確定區(qū)間內(nèi)平均值的大小.

圖5 點(diǎn)集內(nèi)的距離關(guān)系Fig.5 The relationship of distance within the point set

算法1.半徑獲取策略

輸入:距離矩陣dist1×t.

輸出:有效半徑集合Radius.

步驟1.數(shù)據(jù)預(yù)處理.加載數(shù)據(jù)集,并置入集合OriginalDist.在獲取原始數(shù)據(jù)的歐氏距離后可將向量轉(zhuǎn)化為式(1)的距離矩陣.

步驟2.算法背景說明.設(shè)OriginalDist最大元素MaxDist,集合元素數(shù)目num,區(qū)間 (Range)數(shù)目RangeNum,則步長StepSizeMaxDist/RangeNum.制定一個標(biāo)準(zhǔn)StandardScore,該標(biāo)準(zhǔn)表示每個區(qū)間平均應(yīng)具有多少個距離元素.如MaxDist100,若區(qū)間數(shù)目為5,則以步長20 為單位,劃分區(qū)間分別是(0,20],(20,40],(40,60],(60,80],(80,100],若共有距離數(shù)目為100 個,則StandardScore為20.

步驟3.區(qū)間統(tǒng)計.遍歷集合,逐一統(tǒng)計區(qū)間內(nèi)元素的數(shù)目.

步驟4.核心計算.在掃描區(qū)間時,1)遴選區(qū)間;2)確定波峰波谷線.當(dāng)掃描區(qū)間內(nèi)無元素時,直接刪除該元素數(shù)目為零的區(qū)間.當(dāng)掃描區(qū)間內(nèi)包含元素時,逐一計算區(qū)間的得分:

圖6 距離元素分布的劃分過程Fig.6 The division process of distance distribution

若得分高于標(biāo)準(zhǔn)值StandardScore,則記錄并掃描下一區(qū)間,直至遇到低于標(biāo)準(zhǔn)值區(qū)間(或元素為零區(qū)間)而終結(jié).合并以上區(qū)間為一大區(qū)間(Combined range),確認(rèn)為波峰(波谷),并計算、標(biāo)記該大區(qū)間得分score.

定義一個得分矩陣Score,該矩陣接收核心方法的返回結(jié)果.得分矩陣每一行表示一個大區(qū)間,矩陣序列SEQ作為標(biāo)識自動生成,lb(Lower bound)、ub(Upper bound)分別表示區(qū)間的下界與上界,布爾類型數(shù)據(jù)根據(jù)該區(qū)間得分高于或低于標(biāo)準(zhǔn)而確定,score表示該區(qū)間的分?jǐn)?shù).

至此,通過第一步劃分,得到了cr個新的區(qū)間,記為RangeSecond.其中,每個區(qū)間代表一個波峰或波谷,并且有一個得分,得分越高表示該區(qū)間內(nèi)關(guān)于距離的元素更加密集.

步驟5.分區(qū)細(xì)化.自頂向下的思想是在步驟4的粗略劃分基礎(chǔ)上,按相同的方法繼續(xù)細(xì)化.

步驟6.按得分比例,分配式(2)中的k.

通過上述工作,獲得集合Radius,并完善式(2).

半徑獲取策略分為三部分,首先確定在每個區(qū)間內(nèi)的距離數(shù)目,其次確定距離出現(xiàn)頻率的波峰波谷;最后執(zhí)行距離的細(xì)化.通過算法1,能獲取針對數(shù)據(jù)集的幾組重要距離值,并記錄在式(2)中.

2.3 點(diǎn)集覆蓋模型

覆蓋模型的思路是指在Radius下的相鄰有效半徑構(gòu)成的覆蓋區(qū)域能夠覆蓋整個點(diǎn)集的情況下,計算覆蓋多維體數(shù)目的比值.具體地說,點(diǎn)集覆蓋模型給出了點(diǎn)集與Radius相鄰半徑的描述關(guān)系.

2.3.1 覆蓋多維體

定義4.覆蓋多維體(Covering multidimensional cube).覆蓋多維體是指能夠覆蓋在點(diǎn)集歐氏空間Rd的一系列多維體,表示為CMC(r).點(diǎn)向量為二維時,覆蓋多維體為開圓;點(diǎn)向量為三維時,覆蓋多維體為開球.

如點(diǎn)集為二維向量,目標(biāo)點(diǎn)x為(d1,d2),則空間內(nèi)該點(diǎn)覆蓋多維體涵蓋的范圍是以半徑r形成的一個圓,范圍內(nèi)的點(diǎn)符合;點(diǎn)集向量為d維,則空間內(nèi)該點(diǎn)覆蓋多維體涵蓋的范圍是以半徑r形成的多維空間,范圍內(nèi)的點(diǎn)

討論1.覆蓋多維體的覆蓋原則.

覆蓋原則為分割覆蓋(Division cover),這是由于點(diǎn)分布的無序性造成的.

若覆蓋多維體占據(jù)的空間為Space,則在點(diǎn)集中可尋找若干類覆蓋多維體:space1,space2,···,spaces使:

其中任意覆蓋多維體space可由若干半徑較小的子覆蓋多維體(SubSpace)構(gòu)成,需要滿足:

覆蓋多維體與覆蓋原則如圖7 所示.

在圖7 中,通過不同種類覆蓋多維體,使點(diǎn)集中的大部分點(diǎn)(除孤立點(diǎn)外)均被覆蓋.圖7 中的覆蓋結(jié)果屬于多種覆蓋方法的結(jié)果之一.

需要注意的是:分割覆蓋原則使原先半徑為r1,r2的覆蓋圓分割為若干小的覆蓋圓,圖7 中被覆蓋多維體劃分后的點(diǎn)集被多種類型的覆蓋圓C覆蓋.若規(guī)定則該點(diǎn)集由確定的兩類覆蓋多維體CMC1,CMC2覆蓋.

通過引入覆蓋多維體的相關(guān)概念,針對簇內(nèi)孤立點(diǎn)的判定問題提出如下的解決思路.

目標(biāo)問題:在密度矩陣中,確定并選擇合適的一至多種密度,或確定多種密度間的關(guān)聯(lián),使推導(dǎo)出的參數(shù)在輸入至DBSCAN 算法后能夠有效聚類,并甄別孤立點(diǎn).

轉(zhuǎn)化結(jié)果:如何選擇半徑,使其構(gòu)成的覆蓋多維體在覆蓋點(diǎn)集的條件下密度達(dá)到最高.

思路正確性探究:將點(diǎn)集P視為含有多種密度混合的數(shù)據(jù)集根據(jù)密度矩陣性質(zhì),不同密度的覆蓋多維體數(shù)量具有遞減性,即并且每一個密度具有相對應(yīng)的半徑r,二元組(ρδ,rn)展示了該半徑下密度分布的主要區(qū)間.因此,點(diǎn)集存在等式:該等式由各類半徑構(gòu)成的覆蓋多維體組成.其中,m為點(diǎn)的數(shù)目,(Sr·ρr)為該密度覆蓋多維體內(nèi)點(diǎn)的數(shù)目,nr為對應(yīng)覆蓋多維體數(shù)量.因式項(xiàng)1 為點(diǎn)集中大部分正常點(diǎn)所占空間,因式項(xiàng)2 為松散或孤立點(diǎn)所占空間.考慮因式項(xiàng)1 作為主要研究目標(biāo),使該組合達(dá)到數(shù)量nr最小,密度ρr最大.為選擇合適密度,或確定密度間關(guān)聯(lián),需要分析不同覆蓋多維體數(shù)目的關(guān)系.

討論2.點(diǎn)集空間能否被一類以上的覆蓋多維體覆蓋.

引理1.設(shè)點(diǎn)集P在Rd中是有界閉集,C是覆蓋多維體集合,且C 覆蓋了點(diǎn)集P.則在點(diǎn)集P中必存在有限個覆蓋多維體CMC1,CMC2,···,CMCs,同樣完全覆蓋點(diǎn)集P.

解釋:1)條件中,C 覆蓋點(diǎn)集P,指,存在覆蓋多維體C,使得(r).2)C 是指歐氏空間中的一系列鄰域,如0,1,2,···,N},實(shí)際就是覆蓋多維體下的不同半徑集合Radius.

引理的證明與有限覆蓋定理 (Heine-Boreltheorem)證明相似,本文不再證明.最終可得到不同半徑集合Radius可覆蓋點(diǎn)集P所在空間的結(jié)論.因此需要討論半徑集合Radius中不同半徑覆蓋點(diǎn)集的能力.

討論3.覆蓋點(diǎn)集空間時,半徑應(yīng)滿足的條件.

在半徑r較小的條件下,覆蓋多維體能夠完全覆蓋點(diǎn)集,有n·πr2np.若存在,則存在由此同樣能夠?qū)崿F(xiàn)點(diǎn)集的空間覆蓋,這不僅表明覆蓋多維體的覆蓋結(jié)果是多樣的,同樣證明了當(dāng)半徑r小于某一條件時,點(diǎn)集會被覆蓋多維體完全覆蓋.

圖7 覆蓋多維體分割覆蓋原則示意Fig.7 The example of division cover in covering multidimensional cube

設(shè)點(diǎn)集P在所處歐氏空間的任意維度dimensiond的最大最小值分別為MaxVd,MinVd,則認(rèn)為P在該維度下的值域?yàn)閇MaxVd,MinVd].因此,d維空間的每一維度下均有范圍為[MaxVd,MinVd]的多維歐氏空間.

當(dāng)存在多維體,半徑R,且0

1)當(dāng)r1/2Max(MaxVd?MinVd),則Spacecmc ∩SpacepSpacep,表示該多維體能覆蓋點(diǎn)集空間.

2)當(dāng)1/4Max(MaxVd?MinVd)≤ r <1/2Max(MaxVd?MinVd),則2· Spacecmc ∩SpacepSpacep,表示兩個多維體能覆蓋點(diǎn)集空間.

3)當(dāng)r <1/4Max(MaxVd?MinVd),或1/4Max(MaxVd?MinVd),則n·Spacecmc∩SpacepSpacep,表示n個多維體能覆蓋點(diǎn)集空間.

其中Spacecmc與Spacep分別表示覆蓋多維體與點(diǎn)集所占據(jù)的空間.且當(dāng)半徑r小于最大維度值域1/4 時,覆蓋的密度更高,點(diǎn)集更加逼近P集合總數(shù);為此,需要將計算的距離矩陣進(jìn)行篩選,留取較小的點(diǎn)間距離,作為半徑獲取的學(xué)習(xí)數(shù)據(jù).

這里將r的選擇稱為距離篩選(Distance filter),是ODIC-DBSCAN 的第一項(xiàng)輸入?yún)?shù),用來控制覆蓋多維體的半徑大小.通過討論2,討論3 可知,任意點(diǎn)集P可由一類以上的覆蓋多維體覆蓋,且為使覆蓋密度更高,半徑也應(yīng)具備一定的條件.但點(diǎn)集被覆蓋的方式具有多樣性,第2.3.2 節(jié)將在滿足點(diǎn)集被覆蓋的條件下,對不同類型覆蓋多維體的數(shù)目關(guān)系展開討論.

2.3.2 點(diǎn)比閾值

若僅僅表述第k密度與第k+1 密度的關(guān)系,可以描述為以下一系列無差別曲線族,定義為E,k ≥0,其中E為常數(shù).該曲線族描述了密度矩陣ρk×m相鄰密度間的關(guān)系,如圖8所示.

若設(shè)兩類覆蓋多維體的密度與對應(yīng)半徑分別為(ρ1,ρ2)與(r1,r2),則當(dāng)兩類覆蓋多維體能夠共同覆蓋點(diǎn)集時,所滿足的數(shù)量關(guān)系如圖8 所示.在圖8 中,設(shè)曲線上任意點(diǎn)p為二元組(1,r12,r2)構(gòu)成,則圖中p1與p2在覆蓋點(diǎn)集效果中是等價的.

對U上的任意一點(diǎn)p,滿足:

表示每一行密度矩陣的平均密度;其中等式左邊第一個因式項(xiàng)表示以為密度,以rk為半徑的圓總共覆蓋的點(diǎn)數(shù)目;因式項(xiàng)2 同理.兩個因式項(xiàng)之和等于點(diǎn)數(shù)目m.在這個約束條件下,需要掌握不同覆蓋多維體的關(guān)系.

圖8 無差別曲線族Fig.8 Indiscriminate curve

定義函數(shù)U以描述密度間的均衡狀態(tài),該均衡狀態(tài)表示相鄰半徑間的偏向關(guān)系.函數(shù)U應(yīng)具備以下兩點(diǎn)性質(zhì):1)函數(shù)為單調(diào)減函數(shù);2)函數(shù)圖像為下凹形狀.這兩點(diǎn)性質(zhì)符合無差別曲線的特性,并以反比關(guān)系的形式展現(xiàn).

函數(shù)U是y1/x,(x>0)的形式,形態(tài)即以原點(diǎn)為對稱,反比函數(shù)雙曲線的上部分.從函數(shù)的構(gòu)成上,可以發(fā)現(xiàn)的系數(shù)為一對參數(shù)(μ,ν),該參數(shù)考慮了點(diǎn)集密度對相鄰半徑ri,rj的偏向性.如在圖8 中,μ較大時,曲線偏向于n(ri);ν較大時,曲線下凸則偏向于n(rj).參數(shù)通過尋找排序后密度矩陣的相鄰密度差值最大的點(diǎn),并返回其排序序號獲取,表示為式(10):

為求多元函數(shù)(9)在約束條件(8)下的極值,引入拉格朗日乘子法,將2 個變量與1 個約束條件的最優(yōu)化問題轉(zhuǎn)為2+1 個變量的無約束優(yōu)化問題.在本例約束優(yōu)化工作中,構(gòu)造拉格朗日函數(shù):

其中,L為構(gòu)造的拉格朗日函數(shù),U為待求優(yōu)化問題,λ為拉格朗日乘子,為式(8).通過引入函數(shù)U,Ψ 拉格朗日函數(shù)為:

對式(15)的研究從以下幾點(diǎn)分析.

當(dāng)點(diǎn)集存在k層密度曲線,即k個無差曲線族時,則相應(yīng)會出現(xiàn)k?1 個相鄰的點(diǎn)比閾值,稱為點(diǎn)比閾值組(Group of point ratio thresholds,GPRT).

2.4 ODIC-DBSCAN

ODIC-DBSCAN 算法的核心思想是將點(diǎn)比閾值組作為算法的考察閾值,確認(rèn)核心對象在規(guī)定的兩個半徑內(nèi)密度變化是否大于閾值,如果密度變化大于規(guī)定閾值,則說明該點(diǎn)外圍的點(diǎn)較多,該點(diǎn)并非處于簇邊緣;反之則證明該點(diǎn)處于簇邊緣部分,因此不必將其納入擴(kuò)充區(qū)域,也不必將其標(biāo)記為該簇.因此重定義的核心對象如下:

定義5.核心對象(Core object).若以xi為研究對象,在集合Radius中相鄰半徑rα,rβ下點(diǎn)的數(shù)目之比大于預(yù)處理的點(diǎn)比閾值,則稱xi為核心對象.

在任意非均勻分布點(diǎn)集下,無論是否存在模糊邊界,當(dāng)限制條件(如原DBSCAN 中的epsilon與MinPts,或本文提出的點(diǎn)比閾值)逐漸步進(jìn)時,簇間會漸漸產(chǎn)生靠攏、聚合的現(xiàn)象,直至最終匯聚為一個簇.該現(xiàn)象被稱為簇的融合.簇的融合將模糊邊界融聚在一起,因此難免會對簇的聚類結(jié)果產(chǎn)生誤判.因此孤立點(diǎn)判定方法需要不斷循環(huán)、步進(jìn)點(diǎn)比閾值,直到簇發(fā)生了融合現(xiàn)象,便停止迭代.此時對沒有簇號的點(diǎn),可記為孤立點(diǎn).在檢測方法中,包含兩個步驟:

步驟1.通過算法3 確立點(diǎn)集存在的簇群.

在簇群的建立工作中,給定一個有效點(diǎn)閾值(Effective Points Threshold),表示沒有簇編號的點(diǎn)(孤立點(diǎn))占點(diǎn)集數(shù)目的比值,若高于有效點(diǎn)閾值,則確定簇群建立成功,否則失敗(可參照附錄算法3).

有效點(diǎn)閾值Effective Points Threshold是ODIC-DBSCAN 算法的第二個參數(shù).該閾值的取值完全是有限的,可每隔十個百分點(diǎn)取一數(shù)值.實(shí)際上,閾值的大小規(guī)律是有跡可循的,簇的緊密程度與該值有明顯的關(guān)聯(lián):當(dāng)簇的分界清晰,(Effective Points Threshold)取90% 依然無誤;當(dāng)簇間模糊,點(diǎn)分布無明顯規(guī)律,則將該參數(shù)調(diào)至50% 以下即可.

步驟2.迭代執(zhí)行ODIC-DBSCAN 算法,每次增加不同半徑下點(diǎn)數(shù)目的比例,直至發(fā)現(xiàn)簇產(chǎn)生融合現(xiàn)象時停止.

孤立點(diǎn)的檢測關(guān)心首次確立的簇群是否發(fā)生了融合現(xiàn)象,如果沒有發(fā)生融合,則記錄相關(guān)數(shù)據(jù),循環(huán)算法;否則返回上一次的IDX,作為聚類的最終結(jié)果.算法通過獲取并匹配IDX的分布,確認(rèn)簇是否發(fā)生融合,并返回結(jié)果.其流程如圖9 所示.

圖9 孤立點(diǎn)檢測流程Fig.9 The procession of outlier detection

2.5 時間復(fù)雜度分析

程序結(jié)構(gòu)被分為以下幾個部分:1)距離矩陣;2)篩選符合要求的距離;3)半徑獲取策略;4)密度矩陣;5)計算點(diǎn)比閾值;6)ODIC-DBSCAN 算法.

1)距離矩陣時間復(fù)雜度為O(n2).

2)篩選符合要求距離的時間復(fù)雜度為O(n);遍歷距離一次,找出符合要求的距離點(diǎn)并組成數(shù)組.

3)半徑獲取策略的時間復(fù)雜度為O(n);且此時n已遠(yuǎn)小于“篩選符合要求距離”中的n,其時間主要消耗在選定區(qū)域內(nèi)的距離數(shù)量中.

4)密度矩陣時間復(fù)雜度為k·O(n).其中n為點(diǎn)集規(guī)模,k為集合Radius中有效半徑的數(shù)目.

5)計算點(diǎn)比閾值,線性時間復(fù)雜度.

6)ODIC-DBSCAN 算法時間復(fù)雜度為k ·O(n).實(shí)際上,距離矩陣作為參數(shù)直接傳入DBSCAN,無需重復(fù)計算.O(n)為對n個點(diǎn)進(jìn)行遍歷,尋找密度相連的點(diǎn);k為外層循環(huán),循環(huán)體為點(diǎn)比閾值組.

通過以上分析,ODIC-DBSCAN 算法時間復(fù)雜度的數(shù)量級與DBSCAN 相同,均為O(n2).

3 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)分為三個部分:第一部分為半徑獲取策略的效果展示;第二部分為ODIC-DBSCAN 的性能測試:包括在UCI 真實(shí)的高維數(shù)據(jù)中檢測參數(shù)敏感性與時間效率;第三部分為簇內(nèi)與簇間孤立點(diǎn)檢驗(yàn)效果對比.

實(shí)驗(yàn)將DBSCAN、AP、DPC、ReCon-DBSCAN、ReCon-OPTICS 作為簇內(nèi)孤立點(diǎn)檢測的對比算法;此外,將LDOF、F-ABOD、LOF 以及OPTICS 四種算法作為簇間孤立點(diǎn)檢測性能的對比算法,并使用公開數(shù)據(jù)集與模擬數(shù)據(jù)集.在性能測試與簇間孤立點(diǎn)檢測中,選擇UCI 公開的3 個真實(shí)數(shù)據(jù)集與聚類公開的3 類benchmark;在簇內(nèi)孤立點(diǎn)檢測中,制定了相應(yīng)的模擬數(shù)據(jù)集1～3,其數(shù)據(jù)分布將在對應(yīng)部分給予說明.

3.1 半徑獲取策略

在驗(yàn)證半徑獲取策略的方法上,兩個具有代表性的數(shù)據(jù)集.圖10(a)含有兩個簇,且距離差為2.圖10(b)含有三個簇,其左下方兩個簇與圖10(a)相同,最遠(yuǎn)兩個簇之間距離差為10.圖10 中每個簇包含100 個點(diǎn),且均以隨機(jī)數(shù)的方式生成.

圖10 構(gòu)造數(shù)據(jù)集散點(diǎn)圖Fig.10 The constructed point sets scatters

通過圖11,可以觀察距離的數(shù)目與其值的關(guān)系,該圖是由算法產(chǎn)生1×2 000 的矩陣DistRatio構(gòu)成的.圖11 中在1～2 的距離內(nèi),有一個明顯的直線上升.其中,在上升段的左側(cè),是兩個簇內(nèi)各自點(diǎn)之間的兩兩距離;在上升段的右側(cè),是兩個簇之間的相互距離.左右之間的上升躍進(jìn)是半徑獲取策略的主要作用,屏蔽了一些“沒有作用”的距離,這些距離會使算法產(chǎn)生大量的冗余,因此半徑獲取策略將這些距離篩選、排除.相應(yīng)的統(tǒng)計下,在0～1 范圍內(nèi),劃分出的距離數(shù)目為950 個;在1～2 范圍下,算法劃分的距離數(shù)目86 個;而2～3 下,數(shù)目為661個,3～4.5 中,距離數(shù)目為430 個.

圖11 數(shù)據(jù)集1 下的距離分割Fig.11 The distance division of point set 1

圖12 為分割圖10(b),算法劃分的距離產(chǎn)生的結(jié)果.圖中的劃分出現(xiàn)了多層梯度,按從低至高的順序,梯度的解釋如表1 所示.

表1 梯度含義Table 1 The meaning of gradient

通過圖11、12 的數(shù)據(jù),可驗(yàn)證半徑獲取策略能夠選擇適應(yīng)于數(shù)據(jù)集的幾組重要距離,輸出的結(jié)果也具有針對性.

3.2 ODIC-DBSCAN 性能測試

本節(jié)將對ODIC-DBSCAN 的性能做一些典型測試,包括1)參數(shù)敏感性分析;2)運(yùn)行時間分析.數(shù)據(jù)集的采用說明如下:

1)實(shí)驗(yàn)選擇UCI 公開的數(shù)據(jù)集(http://archive.ics.uci.edu/ml/datasets.html):Banknote Authentication (BA)、Chess 與Breast Cancer Wisconsin (WDBC).在三類數(shù)據(jù)集的預(yù)處理中采取同樣的方法:刪除反類中(孤立點(diǎn)類)絕大部分?jǐn)?shù)據(jù),僅保留10 條反類樣本作為孤立點(diǎn)進(jìn)行檢測.三個數(shù)據(jù)集的樣本數(shù)目與維度分別為:772 ×4、1 679×36、367 ×30.

圖12 數(shù)據(jù)集2 下的距離分割Fig.12 The distance division of point set 2

2)在時間分析中,選擇聚類的三種benchmark(https://cs.joensuu.fi/sipu/datasets),分別測試不同規(guī)模,不同簇數(shù)目,以及不同維度下的運(yùn)行時間.

3.2.1 參數(shù)敏感性分析

ODIC-DBSCAN 參數(shù)為:1)距離的篩選條件;2)簇形成時的簇閾值.通過3 類數(shù)據(jù)集,在控制兩類參數(shù)的情況下,分析數(shù)據(jù)集產(chǎn)生的孤立點(diǎn)數(shù)目.

表2 展示了在真實(shí)的高維數(shù)據(jù)集下,調(diào)整不同參數(shù)下的孤立點(diǎn)檢測結(jié)果.從表中數(shù)據(jù)可知,ODICDBSCAN 在不同參數(shù)的影響下,對數(shù)據(jù)分析較為穩(wěn)定,檢測結(jié)果對參數(shù)并不敏感.

分析可知:1)距離篩選參數(shù)將距離細(xì)化后再選擇數(shù)據(jù)集中重要半徑,但對不同數(shù)據(jù)集有不同的要求.如數(shù)據(jù)集2,當(dāng)半徑為最大距離的1/5 時,由于半徑過小,則不能產(chǎn)生聚類效果.2)有效點(diǎn)閾值參數(shù)對結(jié)果的影響是具有規(guī)律的,該參數(shù)表示高于有效點(diǎn)占全局點(diǎn)的比例時,簇的產(chǎn)生生效.因此可以發(fā)現(xiàn),隨著該參數(shù)的增加,孤立點(diǎn)在不斷減少,而到達(dá)一定程度時,結(jié)果將保持不變;在該情況下,產(chǎn)生的孤立點(diǎn)數(shù)目是穩(wěn)定且可靠的.

另外,當(dāng)有效點(diǎn)閾值降低時,孤立點(diǎn)數(shù)目增長.實(shí)際上,有效點(diǎn)閾值降低時,簇發(fā)生了融合,而較多被檢測的孤立點(diǎn)來源于簇之間的邊緣點(diǎn)對象.這說明ODIC-DBSCAN 對圖1 中的現(xiàn)象1 和2 具有檢測效果.

3.2.2 算法運(yùn)行時間分析

算法的時間性能關(guān)系到應(yīng)用效率.本節(jié)選擇了:1)三類benchmark,包括不同規(guī)模,簇數(shù)目以及維度的數(shù)據(jù)對象;2)兩種密度聚類算法(DPC 與AP算法),使之作為對比方法,并控制迭代次數(shù).

1)不同規(guī)模

圖13 展示了不同算法在不同規(guī)模數(shù)據(jù)集下的運(yùn)行時間.DPC 算法的運(yùn)行默認(rèn)自動選取所有的簇心,并無需迭代,算法執(zhí)行僅需要計算每個點(diǎn)的局部密度,并尋找該點(diǎn)范圍內(nèi)更高的局部密度對象即可.而AP 算法雖然執(zhí)行時間有限,但為獲得聚類中心的收斂,需要不斷迭代.ODIC-DBSCAN 雖然需要進(jìn)行外層循環(huán)迭代,不斷遍歷全局點(diǎn),并根據(jù)核心對象條件執(zhí)行擴(kuò)充方法;但是該方法在預(yù)處理中選擇了針對數(shù)據(jù)集的重要半徑,因此時間低于AP 算法.

2)不同簇數(shù)目與不同維度

在不同簇數(shù)、維度的數(shù)據(jù)下,各類算法的運(yùn)行時間如圖14、15,且三類benchmark 在數(shù)據(jù)規(guī)模上相同.

從數(shù)據(jù)中可以觀察到,最為重要的變化是ODIC-DBSCAN 的速度在簇數(shù)目與維度的benchmark 中得到了極大的提升,這主要是因?yàn)閿?shù)據(jù)的分布對算法具有較大的影響.因此在相同規(guī)模下,數(shù)據(jù)的分布對運(yùn)行時間的影響不可忽略.在圖13的數(shù)據(jù)中,分布總是包含95 個簇,形狀復(fù)雜;因此ODIC-DBSCAN 在運(yùn)行時需要考慮任意兩個簇之間的距離問題,運(yùn)行時間較長;而在圖14 中,每個benchmark 對應(yīng)的簇數(shù)目較少,分布較簡單,運(yùn)行時間也較短.

為了更清晰地觀察算法在運(yùn)行時間的細(xì)節(jié),啟用了MATLAB 時間運(yùn)行探查器.在此對比圖13 中數(shù)據(jù)量為5 000 的數(shù)據(jù)集,以及圖14 中簇數(shù)目為5的數(shù)據(jù)集;兩個數(shù)據(jù)集的點(diǎn)數(shù)目完全相同,但數(shù)據(jù)分布不同;另外,控制迭代的次數(shù)為1 次.

從表3 中可發(fā)現(xiàn),在同樣規(guī)模的數(shù)據(jù)集下,由于數(shù)據(jù)分布不同,算法運(yùn)行的時間也受到了影響.通過表中數(shù)據(jù),可知時間主要消耗在“合并鄰居”這一條命令行中(算法2 第20 行).該行代碼負(fù)責(zé)擴(kuò)展簇,即確定一個核心對象后,尋找其鄰居,然后將尋找鄰居返回的結(jié)果繼續(xù)作為輸入,并繼續(xù)尋找鄰居,直到結(jié)束條件.可以發(fā)現(xiàn),簇的數(shù)目較多時,合并的次數(shù)也較多,但算法時間消耗也隨之上升,這是因?yàn)樵従訑?shù)組的長度與新納入的點(diǎn)數(shù)組長度都有所增加,合并數(shù)組的時間消耗也大幅度增長.

表2 距離篩選與有效點(diǎn)閾值的敏感性測試Table 2 The sensitivity of distance filter and effective points threshold

表3 ODIC-DBSCAN 在相同規(guī)模不同分布的數(shù)據(jù)集下時間運(yùn)行細(xì)節(jié)Table 3 Time details of ODIC-DBSCAN on the point sets that have same scale but different distributions

圖13 不同算法在不同規(guī)模benchmark 下的運(yùn)行時間Fig.13 Time of algorithms on scale benchmark

圖14 不同算法在不同簇數(shù)目benchmark 下的運(yùn)行時間Fig.14 Time of algorithms on cluster benchmark

圖15 不同算法在不同維度benchmark 下的運(yùn)行時間Fig.15 Time of algorithms on dimension benchmark

3.3 孤立點(diǎn)的檢測與對比

在本節(jié)中,與基于密度聚類的方法進(jìn)行對比,使用DBSCAN、AP、DPC、ReCon-DBSCAN、ReCon-OPTICS 五類算法在參數(shù)不同的情況下分別檢驗(yàn)其是否能檢測出預(yù)設(shè)的孤立點(diǎn),并與ODIC-DBSCAN 進(jìn)行比較.

1)HR(Hit rate).該值表示算法的命中率.設(shè)點(diǎn)集P中所有孤立點(diǎn)構(gòu)成集合Outliers,二值算法檢測出的孤立點(diǎn)為集合DOb(Detected outliers of binary results),非二值檢測出的孤立點(diǎn)為DOnb(Detected outliers of non-binary results),則

2)SRoPO(Sum rank of pre-set outliers).

定義6.預(yù)設(shè)孤立點(diǎn)排序和(SRoPO,Sum rank of pre-set outliers).設(shè)點(diǎn)集P內(nèi)包含no個孤立點(diǎn),非二值檢測算法中任意點(diǎn)與其離群程度構(gòu)成二元組,將P內(nèi)所有點(diǎn)按outlier?ness由高至低排序,則任意點(diǎn)均包含孤立程度的排列序號ranki;此時有SRoPO

表4 展示了第3.3.1 節(jié)與第3.3.2 節(jié)特殊符號的意義.

表4 特殊符號與其意義Table 4 Symbols and its meanning

3.3.1 簇內(nèi)孤立點(diǎn)檢測對比

數(shù)據(jù)集設(shè)計:為了檢驗(yàn)ODIC-DBSCAN 在上述條件下的簇內(nèi)孤立點(diǎn)檢測效果,重新制定了三個模擬數(shù)據(jù)集,該數(shù)據(jù)集的形態(tài)如圖16 所示.

圖16 構(gòu)造數(shù)據(jù)集Fig.16 Construction of point sets

在圖16 中,外圓是點(diǎn)集的范圍,在圓內(nèi)設(shè)置一內(nèi)接矩形,矩形內(nèi)部安置了密集的數(shù)據(jù),矩形外部與外圓間安置了松散的數(shù)據(jù).數(shù)據(jù)集1)外圓處點(diǎn)527 個,矩形內(nèi)部安置點(diǎn)5 082 個,將范圍1 下的點(diǎn)清除,并添加點(diǎn)(0.025,0.025).數(shù)據(jù)集2)外圓處點(diǎn)546 個,矩形內(nèi)部點(diǎn)14 385 個,將1～5 范圍內(nèi)的點(diǎn)清除,添加點(diǎn){(0.025,0.025),(?0.725,?0.225),(?0.775,0.225),(0.775,?0.225),(0.775,0.225)},數(shù)據(jù)集2 共計點(diǎn)15 266 個.數(shù)據(jù)集3)外圓處點(diǎn)557個,矩形內(nèi)部19 776 個點(diǎn),該點(diǎn)集的處理方式與點(diǎn)集2 相同,共計點(diǎn)20 078 個.

1)ODIC-DBSCAN

圖17～19 展示了ODBC-DBSCAN 在模擬數(shù)據(jù)集1～3 中的結(jié)果.觀察圖17 結(jié)果可發(fā)現(xiàn),聚類將密集區(qū)的點(diǎn)聚合出來,稀疏點(diǎn)輸出為孤立點(diǎn).在數(shù)據(jù)密集區(qū)中,由于存在點(diǎn)5 552 個,與挖空區(qū)域面積(0.025)相比,數(shù)據(jù)集的點(diǎn)依然有相對稀疏的特性,因此算法產(chǎn)出了與預(yù)設(shè)孤立點(diǎn)相近的點(diǎn).

圖17 數(shù)據(jù)集1 下的ODIC-DBSCAN 算法結(jié)果Fig.17 Results of ODIC-DBSCAN in point set 1

圖18 數(shù)據(jù)集2 下的ODIC-DBSCAN 算法結(jié)果Fig.18 Results of ODIC-DBSCAN in point set 2

圖19 數(shù)據(jù)集3 下的ODIC-DBSCAN 算法結(jié)果Fig.19 Results of ODIC-DBSCAN in point set 3

這些孤立點(diǎn)的環(huán)境相仿,與周圍均有不同程度的空白,因此聚類結(jié)果將他們分離出來.圖18 中,ODIC-DBSCAN 算法不僅提供了正確的聚類結(jié)果,同樣分辨出六個孤立點(diǎn).這六個孤立點(diǎn)中有五個是預(yù)先設(shè)定的,另外一個在簇的邊緣處.這說明隨著簇密集程度的增加,孤立點(diǎn)的分割也顯得越來越清晰.在圖19 中,數(shù)據(jù)集3 密集區(qū)的密度更大,在此情況下,設(shè)定的五個孤立點(diǎn)較為明顯.從聚類結(jié)果可以看出,ODIC-DBSCAN 在高密度下識別出了簇與五個孤立點(diǎn).

2)DBSCAN

圖20 展示了在不同參數(shù)(不同MinPts)下模擬數(shù)據(jù)集1～3 的DBSCAN 聚類結(jié)果.DBSCAN在不斷調(diào)參(控制epsilon不變,調(diào)整MinPts)后,三類數(shù)據(jù)集均產(chǎn)生了分裂的現(xiàn)象.當(dāng)數(shù)據(jù)密集區(qū)越為緊密,裂變的效果越明顯.這是因?yàn)镈BSCAN 的核心注重簇的擴(kuò)充,而由于MinPts條件限制,導(dǎo)致密集區(qū)被分裂為多個簇.而在這之間,預(yù)設(shè)的孤立點(diǎn)始終不能被檢測出,這是因?yàn)樗惴▋H能接收一種密度條件.而ODIC-DBSCAN 具有較強(qiáng)的檢測能力,是由于我們對DBSCAN 算法的核心對象重新進(jìn)行了定義,優(yōu)化了簇擴(kuò)充的條件,從點(diǎn)的數(shù)量,轉(zhuǎn)移到點(diǎn)周圍密度的變化.不僅如此,ODIC-DBSCAN 算法能夠自學(xué)習(xí)整個點(diǎn)集中的密度分布,提供合理的距離測試與密度變化.通過以上支持,使孤立點(diǎn)的檢測結(jié)果較為理想.

3)DPC 與AP

DPC 與AP 聚類下對孤立點(diǎn)的識別結(jié)果如表5 展示.DPC 算法中,選擇ρ較小,δ較大的對象為孤立點(diǎn).在分析中,選擇排序后的ρ/δ最小的n個值作為分析對象.其中position表示預(yù)設(shè)的孤立點(diǎn)的ρ/δ值在正常點(diǎn)內(nèi)的排序號碼.另外,CORE表示屬于每個簇的點(diǎn)數(shù)目.其次,有另外一些點(diǎn)在CORE 集合的邊緣處,這些點(diǎn)被稱為HALO.

實(shí)驗(yàn)發(fā)現(xiàn),調(diào)節(jié)per在1%～2%區(qū)間內(nèi),算法明顯產(chǎn)生了兩個簇心;算法將高密區(qū)域分為不同的部分,而非一個整體.這說明DPC 算法對參數(shù)是敏感的,首先受限于參數(shù)per的調(diào)控,不同的截斷距離dc(Cutoff distance)將數(shù)據(jù)的密度狀態(tài)劃分為不同的結(jié)果;其次是簇心的選擇,完全改變了聚類結(jié)果.在該實(shí)例中,發(fā)現(xiàn)高密與低密區(qū)域的界限很難區(qū)分,而僅用HALO 表述,說明算法的參數(shù)不能很好地適應(yīng)不同密度下的數(shù)據(jù)集聚類結(jié)果.也因而未能有效檢測預(yù)設(shè)孤立點(diǎn).另外,DPC 算法能檢查簇間孤立點(diǎn),但是對簇內(nèi)孤立點(diǎn)難以檢測;這同樣是因?yàn)閐c對檢測具有大的干擾,因?yàn)樵撝禈O大地影響了局部密度,由于簇內(nèi)不同的點(diǎn)密度差較小,因此對該值的敏感很高.而AP 算法的本質(zhì)是不斷更新、計算相似度矩陣中每個點(diǎn)的吸引度信息與歸屬度信息,并尋找簇中心的過程;因此設(shè)置的模擬數(shù)據(jù)集在簇的劃分上具有對稱與均勻的特性;由于算法在迭代中檢查聚類中心的變化,因此對簇內(nèi)的孤立點(diǎn)并不敏感.實(shí)際上,在低密區(qū)域設(shè)置的孤立點(diǎn)也被納入了正常簇中.AP 算法在點(diǎn)與點(diǎn)的信息傳播中具有很強(qiáng)的特性,但是在孤立點(diǎn)的判定中,邊緣點(diǎn)由于對簇內(nèi)點(diǎn)具有歸屬度,因此容易被納入在簇的內(nèi)部.

表5 DPC 與AP 在模擬數(shù)據(jù)集1 ～3 的檢測結(jié)果Table 5 Detection results of DPC and AP on synthetic point sets 1 ～3

圖20 不同參數(shù)下對模擬數(shù)據(jù)集1 ～3 的DBSCAN 聚類結(jié)果Fig.20 DBSCAN Clustering results of point sets 1 ～3 with different parameters

4)Re-Con DBSCAN 與Re-Con OPTICS

表6～7 展示了基于密度比方法中的Re-Con DBSCAN 與Re-Con OPTICS 算法在Synthetic1-3 數(shù)據(jù)集中的檢測結(jié)果.該方法是由于Reconditioning approach 提供了一種基于密度比的策略,與本文提出的ODIC-DBSCAN 具有相近之處.表中參數(shù)為該方法的輸入,參數(shù)對表示構(gòu)造密度比所需的不同大小半徑.

從表6 中的數(shù)據(jù)可知,算法在不同參數(shù)的影響下效果不同,隨著閾值的增加,檢測出的孤立點(diǎn)數(shù)目也逐漸增加,且對預(yù)設(shè)的簇內(nèi)孤立點(diǎn)有一定的鑒別能力.這是因?yàn)樵摲椒ú捎玫拿芏缺人枷肽軌蜥槍Σ煌芏瘸槿〔煌拿芏乳撝?并能夠阻隔多重密度帶來的干擾;但是,該方法對參數(shù)具有依賴性,體現(xiàn)在表中相同數(shù)據(jù)集下不同參數(shù)的結(jié)果.另外,由于預(yù)設(shè)的簇內(nèi)孤立點(diǎn)空間空白區(qū)域較小,且受到密度稀疏區(qū)域的干擾,因此給定的密度閾值不能滿足簇內(nèi)孤立點(diǎn)密度的特殊條件.

在表7 OPTICS 密度比算法中,ToDR表示算法構(gòu)造的兩層范圍下近鄰數(shù)目之比,因此約定內(nèi)層范圍鄰居數(shù)目MinPts為8,則ToDR10 時,外層范圍鄰居數(shù)目為80.對數(shù)據(jù)集1～3,構(gòu)造的密度比閾值ToDR越大,命中率HR越大,這是因?yàn)楫?dāng)構(gòu)造的兩層范圍間密度差越大時,低密區(qū)域的孤立點(diǎn)越容易被檢測.另外,命中率漲幅由快變慢,這是由數(shù)據(jù)的分布造成的,模擬數(shù)據(jù)集的密度大致有兩類,因此漲幅在ToDR為10～30 間變化后,孤立點(diǎn)檢測能力的增加逐漸變緩.

對比表6 與表7 可發(fā)現(xiàn),OPTICS 的密度比算法對簇內(nèi)孤立點(diǎn)并不敏感,若將密度比閾值增加,預(yù)設(shè)的簇內(nèi)孤立點(diǎn)與周圍點(diǎn)的密度因?yàn)椴粷M足較大的閾值而被算法忽略;若將密度比閾值減小,則模擬數(shù)據(jù)集的低密區(qū)域內(nèi)部分點(diǎn)會被認(rèn)作正常數(shù)據(jù),導(dǎo)致算法檢測能力降低.

3.3.2 簇間孤立點(diǎn)檢測對比

本節(jié)為比較ODIC-DBSCAN 與其他幾種密度聚類方法以及孤立點(diǎn)檢測方法對簇間孤立點(diǎn)的檢驗(yàn)?zāi)芰?使用LOF、LDOF、F-ABOD 三類孤立點(diǎn)檢測算法,與OPTICS、DPC、ReCon-DBSCAN、ReCon-OPTICS 四類密度聚類方法進(jìn)行對比.在數(shù)據(jù)集的采用上,選擇第3.2 節(jié)所述三類公開高維數(shù)據(jù)集.對比實(shí)驗(yàn)結(jié)果如表8 所示.

表8 展示了二值與非二值檢測的六種方法在公開數(shù)據(jù)集1～3 的檢測結(jié)果.在非二值檢測的四個方法中,LOF,LDOF 與F-ABOD 三類均為孤立點(diǎn)檢測方法;而OPTICS 在密度聚類上有較好的效果.在二值檢測中,選擇了兩類密度聚類方法用來檢測孤立點(diǎn).

不排除三類數(shù)據(jù)集本身具有較大差異,簇與簇之間的界限模糊的因素,總體來說在非二值方法下,隨著參數(shù)k增大,檢測的Top-10 結(jié)果具有上升或保持穩(wěn)定的趨勢.其中,LOF 與OPTICS 能檢測出更多的點(diǎn),且預(yù)設(shè)孤立點(diǎn)排序和(SRoPO)較低,說明其余未檢測到的點(diǎn)的孤立程度也較接近最大的孤立值.LOFD 與F-ABOD 分別是在基于距離與角度的因素下對孤立點(diǎn)進(jìn)行判定,檢測的點(diǎn)數(shù)低于其他兩類非二值檢測方法.其中基于距離的檢測方法在近鄰參數(shù)的調(diào)整下檢測結(jié)果并無較大差異,SRoPO也并非隨k的增加而減少;這說明1)兩類算法產(chǎn)生的結(jié)果對參數(shù)k略顯敏感;2)檢測結(jié)果與k難以成比例,獲取最佳結(jié)果需要不斷調(diào)試參數(shù)試驗(yàn).而Chess 數(shù)據(jù)集中,數(shù)據(jù)的值分布僅為1～7,且均為整數(shù);因此,孤立點(diǎn)的檢測難度較大.在非二值的四類方法下,檢測結(jié)果未及數(shù)據(jù)集1、3 效果良好.

表6 Re-Con DBSCAN 算法在模擬數(shù)據(jù)集1 ～3 的檢驗(yàn)結(jié)果Table 6 Detection results of Re-Con DBSCAN on synthetic point sets 1 ～3

表7 Re-Con OPTICS 算法在模擬數(shù)據(jù)集1 ～3 的檢驗(yàn)結(jié)果Table 7 Detection results of Re-Con OPTICS on synthetic point sets 1 ～3

表8 六種不同檢測方法在三類公開數(shù)據(jù)集上的對比Table 8 Detection results of six OD methods on three public higher dimensional datasets

表9 基于密度比的ReCon-DBSCAN 與ReCon-OPTICS 算法在三類數(shù)據(jù)集上的檢測結(jié)果Table 9 Detection results of density-ratio based ReCon-DBSCAN and ReCon-OPTICS on three real-world point sets

ODIC-DBSCAN 屬于二值檢測,僅對數(shù)據(jù)對象判定是否為孤立點(diǎn),而非測定其孤立程度.對此,該方法顯示出了較強(qiáng)的檢測能力.如數(shù)據(jù)集1 中,當(dāng)有效點(diǎn)閾值在5～6 時,檢測到的9 個孤立點(diǎn)中有8 個是預(yù)設(shè)的點(diǎn).在較難檢測的數(shù)據(jù)集2 中,與其他幾類算法結(jié)果不同之處是,ODIC-DBSCAN 算法檢測出了所有預(yù)設(shè)孤立點(diǎn),但孤立點(diǎn)所在的簇中,同樣包含126 個其他正常點(diǎn).這說明,算法對孤立點(diǎn)的檢測具有一定效果,同時可檢測出的其余點(diǎn)(這些點(diǎn)可能是具有處于正反兩類數(shù)據(jù)模糊邊界的特性),ODIC-DBSCAN 善于捕捉類似的邊界點(diǎn),正如算法對兩個簇在融合之時能夠檢測出簇間點(diǎn)一般.結(jié)合以上各類表的檢測數(shù)據(jù),可以發(fā)現(xiàn)在真實(shí)數(shù)據(jù)集中,ODIC-DBSCAN 對簇間的孤立點(diǎn)檢測依然有效果,這是由于算法考慮了不同密度間的關(guān)聯(lián)關(guān)系,用不同的關(guān)鍵半徑對數(shù)據(jù)集進(jìn)行聚類,因此算法普適性也較強(qiáng).

4 結(jié)語

針對傳統(tǒng)孤立點(diǎn)檢測方法忽略簇內(nèi)孤立點(diǎn)的問題,提出了一種簇內(nèi)孤立點(diǎn)檢測技術(shù)ODICDBSCAN.該方法通過預(yù)處理工作與聚類算法的優(yōu)化,能夠檢測出預(yù)置的若干簇內(nèi)孤立點(diǎn).算法首先依據(jù)數(shù)據(jù)集特性學(xué)習(xí)有效半徑集合并構(gòu)建密度矩陣;然后提出點(diǎn)集覆蓋模型,利用拉格朗日乘子法求取極值,輸出點(diǎn)比閾值;最后修改DBSCAN 的核心對象定義,將預(yù)處理結(jié)果與優(yōu)化DBCSAN 算法相結(jié)合,當(dāng)簇發(fā)生了融合現(xiàn)象時,輸出孤立點(diǎn)檢測結(jié)果.下一步將在此思想的基礎(chǔ)上在廣度與深度上進(jìn)一步提出其他優(yōu)化的方法.該優(yōu)化包含兩個方向:1)思想移植;2)效率優(yōu)化.在思想移植中,工作目標(biāo)致力于將自學(xué)習(xí)思想移植于其他相仿的聚類算法中,使算法對孤立對象具備敏感性;在效率優(yōu)化問題中,需要進(jìn)一步將預(yù)處理思路與其他聚類算法特性相接軌,在保證必備性能的基礎(chǔ)上,正確檢測簇內(nèi)孤立點(diǎn),使類似的檢測方式更加活泛.

附錄

算法2.ODIC-DBSCAN

輸入.點(diǎn)集PPP,距離矩陣dist,點(diǎn)比閾值組GPRT,半徑集合Radius

輸出. IDX

算法主要體現(xiàn)在四方面(在附錄處算法2 中分別標(biāo)記為①、②、③、④).標(biāo)記①(算法2、11 行)在DBSCAN 的基礎(chǔ)上構(gòu)建了一個外層for 循環(huán),該循環(huán)的變量為前述算法規(guī)定的點(diǎn)比閾值組,即該點(diǎn)集中存在無差別曲線族的數(shù)目(一般在10 以內(nèi)),該循環(huán)的作用是漸進(jìn)地逼近簇的最大化.標(biāo)記②(位于27～31 行)為調(diào)用計算點(diǎn)數(shù)比的方法,所調(diào)用的函數(shù)為QueryRatio,是標(biāo)記④的內(nèi)容,計算了目標(biāo)點(diǎn)不同半徑下點(diǎn)數(shù)目的比值.標(biāo)記③(位于19 行)修改了核心點(diǎn)的確認(rèn)方法,原始方法通過確認(rèn)該點(diǎn)鄰居數(shù)目是否大于規(guī)定MinPts來判定是否將該點(diǎn)納入擴(kuò)充區(qū)域;標(biāo)記③通過記錄點(diǎn)j的點(diǎn)數(shù)比與約定的點(diǎn)比閾值關(guān)系確認(rèn)是否能將點(diǎn)j納入簇的擴(kuò)充區(qū)域,修改了簇的擴(kuò)充方法與原理.

算法3.簇群建立