ODIC-DBSCAN:一種新的簇內孤立點分析算法

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

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

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

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

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

圖1 的3 種現象描述了簇內孤立點的產生原因.

圖1 簇內孤立點產出原因Fig.1 The cause of inliers

現象1:當使用不同方法或參數,使原先多個簇發生融合時,先前在多簇間被判定為孤立點的對象會被判定為正常點,產生誤判.

現象2:當多個簇發生融合時,若匯聚的一面為簇的邊緣,則匯聚后簇存在松散域,其中的點可能具有孤立性質.

現象3:當點集緊密投影在區域內部時,若有一處存在明顯稀疏或空白,則該區域下的點需要重點考證研究.

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

1)能夠分析簇間孤立點;

2)能夠分析簇內孤立點;

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

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

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

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

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

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

1 相關工作

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

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

2 模型與策略

2.1 問題分析

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

簇內孤立點的特性在于目標點與周圍的鄰居具有密度差異,該差異可能由點的分布直接造成,也可能由聚類算法的參數使用不當生成.在點集中,由于其與周圍鄰居密度差異較小而經常被忽視,因而簇內孤立點的檢驗需要算法對微小的密度差異具備敏感性.

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

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

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

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

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

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

上述思想能夠有效判斷以目標點為中心,在多重半徑范圍內的數據點密度的變化情況,并以此作為依據推斷該點的位置,確定該點是否具有孤立性質.

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

2.2 半徑獲取策略

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

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

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

定義3.密度矩陣.密度矩陣宏觀統計點集P中每個點在一定范圍內的點數量與面積之比.

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

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

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

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

圖5 點集內的距離關系Fig.5 The relationship of distance within the point set

算法1.半徑獲取策略

輸入:距離矩陣dist1×t.

輸出:有效半徑集合Radius.

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

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

步驟3.區間統計.遍歷集合,逐一統計區間內元素的數目.

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

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

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

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

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

步驟5.分區細化.自頂向下的思想是在步驟4的粗略劃分基礎上,按相同的方法繼續細化.

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

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

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

2.3 點集覆蓋模型

覆蓋模型的思路是指在Radius下的相鄰有效半徑構成的覆蓋區域能夠覆蓋整個點集的情況下,計算覆蓋多維體數目的比值.具體地說,點集覆蓋模型給出了點集與Radius相鄰半徑的描述關系.

2.3.1 覆蓋多維體

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

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

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

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

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

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

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

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

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

通過引入覆蓋多維體的相關概念,針對簇內孤立點的判定問題提出如下的解決思路.

目標問題:在密度矩陣中,確定并選擇合適的一至多種密度,或確定多種密度間的關聯,使推導出的參數在輸入至DBSCAN 算法后能夠有效聚類,并甄別孤立點.

轉化結果:如何選擇半徑,使其構成的覆蓋多維體在覆蓋點集的條件下密度達到最高.

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

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

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

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

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

討論3.覆蓋點集空間時,半徑應滿足的條件.

在半徑r較小的條件下,覆蓋多維體能夠完全覆蓋點集,有n·πr2np.若存在,則存在由此同樣能夠實現點集的空間覆蓋,這不僅表明覆蓋多維體的覆蓋結果是多樣的,同樣證明了當半徑r小于某一條件時,點集會被覆蓋多維體完全覆蓋.

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

設點集P在所處歐氏空間的任意維度dimensiond的最大最小值分別為MaxVd,MinVd,則認為P在該維度下的值域為[MaxVd,MinVd].因此,d維空間的每一維度下均有范圍為[MaxVd,MinVd]的多維歐氏空間.

當存在多維體,半徑R,且0

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

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

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

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

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

2.3.2 點比閾值

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

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

對U上的任意一點p,滿足:

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

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

定義函數U以描述密度間的均衡狀態,該均衡狀態表示相鄰半徑間的偏向關系.函數U應具備以下兩點性質:1)函數為單調減函數;2)函數圖像為下凹形狀.這兩點性質符合無差別曲線的特性,并以反比關系的形式展現.

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

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

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

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

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

2.4 ODIC-DBSCAN

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

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

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

步驟1.通過算法3 確立點集存在的簇群.

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

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

步驟2.迭代執行ODIC-DBSCAN 算法,每次增加不同半徑下點數目的比例,直至發現簇產生融合現象時停止.

孤立點的檢測關心首次確立的簇群是否發生了融合現象,如果沒有發生融合,則記錄相關數據,循環算法;否則返回上一次的IDX,作為聚類的最終結果.算法通過獲取并匹配IDX的分布,確認簇是否發生融合,并返回結果.其流程如圖9 所示.

圖9 孤立點檢測流程Fig.9 The procession of outlier detection

2.5 時間復雜度分析

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

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

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

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

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

5)計算點比閾值,線性時間復雜度.

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

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

3 實驗與分析

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

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

3.1 半徑獲取策略

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

圖10 構造數據集散點圖Fig.10 The constructed point sets scatters

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

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

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

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

通過圖11、12 的數據,可驗證半徑獲取策略能夠選擇適應于數據集的幾組重要距離,輸出的結果也具有針對性.

3.2 ODIC-DBSCAN 性能測試

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

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

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

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

3.2.1 參數敏感性分析

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

表2 展示了在真實的高維數據集下,調整不同參數下的孤立點檢測結果.從表中數據可知,ODICDBSCAN 在不同參數的影響下,對數據分析較為穩定,檢測結果對參數并不敏感.

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

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

3.2.2 算法運行時間分析

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

1)不同規模

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

2)不同簇數目與不同維度

在不同簇數、維度的數據下,各類算法的運行時間如圖14、15,且三類benchmark 在數據規模上相同.

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

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

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

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

表3 ODIC-DBSCAN 在相同規模不同分布的數據集下時間運行細節Table 3 Time details of ODIC-DBSCAN on the point sets that have same scale but different distributions

圖13 不同算法在不同規模benchmark 下的運行時間Fig.13 Time of algorithms on scale benchmark

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

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

3.3 孤立點的檢測與對比

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

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

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

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

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

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

3.3.1 簇內孤立點檢測對比

數據集設計:為了檢驗ODIC-DBSCAN 在上述條件下的簇內孤立點檢測效果,重新制定了三個模擬數據集,該數據集的形態如圖16 所示.

圖16 構造數據集Fig.16 Construction of point sets

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

1)ODIC-DBSCAN

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

圖17 數據集1 下的ODIC-DBSCAN 算法結果Fig.17 Results of ODIC-DBSCAN in point set 1

圖18 數據集2 下的ODIC-DBSCAN 算法結果Fig.18 Results of ODIC-DBSCAN in point set 2

圖19 數據集3 下的ODIC-DBSCAN 算法結果Fig.19 Results of ODIC-DBSCAN in point set 3

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

2)DBSCAN

圖20 展示了在不同參數(不同MinPts)下模擬數據集1～3 的DBSCAN 聚類結果.DBSCAN在不斷調參(控制epsilon不變,調整MinPts)后,三類數據集均產生了分裂的現象.當數據密集區越為緊密,裂變的效果越明顯.這是因為DBSCAN 的核心注重簇的擴充,而由于MinPts條件限制,導致密集區被分裂為多個簇.而在這之間,預設的孤立點始終不能被檢測出,這是因為算法僅能接收一種密度條件.而ODIC-DBSCAN 具有較強的檢測能力,是由于我們對DBSCAN 算法的核心對象重新進行了定義,優化了簇擴充的條件,從點的數量,轉移到點周圍密度的變化.不僅如此,ODIC-DBSCAN 算法能夠自學習整個點集中的密度分布,提供合理的距離測試與密度變化.通過以上支持,使孤立點的檢測結果較為理想.

3)DPC 與AP

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

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

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

圖20 不同參數下對模擬數據集1 ～3 的DBSCAN 聚類結果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 數據集中的檢測結果.該方法是由于Reconditioning approach 提供了一種基于密度比的策略,與本文提出的ODIC-DBSCAN 具有相近之處.表中參數為該方法的輸入,參數對表示構造密度比所需的不同大小半徑.

從表6 中的數據可知,算法在不同參數的影響下效果不同,隨著閾值的增加,檢測出的孤立點數目也逐漸增加,且對預設的簇內孤立點有一定的鑒別能力.這是因為該方法采用的密度比思想能夠針對不同密度抽取不同的密度閾值,并能夠阻隔多重密度帶來的干擾;但是,該方法對參數具有依賴性,體現在表中相同數據集下不同參數的結果.另外,由于預設的簇內孤立點空間空白區域較小,且受到密度稀疏區域的干擾,因此給定的密度閾值不能滿足簇內孤立點密度的特殊條件.

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

對比表6 與表7 可發現,OPTICS 的密度比算法對簇內孤立點并不敏感,若將密度比閾值增加,預設的簇內孤立點與周圍點的密度因為不滿足較大的閾值而被算法忽略;若將密度比閾值減小,則模擬數據集的低密區域內部分點會被認作正常數據,導致算法檢測能力降低.

3.3.2 簇間孤立點檢測對比

本節為比較ODIC-DBSCAN 與其他幾種密度聚類方法以及孤立點檢測方法對簇間孤立點的檢驗能力,使用LOF、LDOF、F-ABOD 三類孤立點檢測算法,與OPTICS、DPC、ReCon-DBSCAN、ReCon-OPTICS 四類密度聚類方法進行對比.在數據集的采用上,選擇第3.2 節所述三類公開高維數據集.對比實驗結果如表8 所示.

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

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

表6 Re-Con DBSCAN 算法在模擬數據集1 ～3 的檢驗結果Table 6 Detection results of Re-Con DBSCAN on synthetic point sets 1 ～3

表7 Re-Con OPTICS 算法在模擬數據集1 ～3 的檢驗結果Table 7 Detection results of Re-Con OPTICS on synthetic point sets 1 ～3

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

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

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

4 結語

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

附錄

算法2.ODIC-DBSCAN

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

輸出. IDX

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

算法3.簇群建立