改進(jìn)的DBSCAN聚類(lèi)和LAOF兩階段混合數(shù)據(jù)離群點(diǎn)檢測(cè)方法

石鴻雁,馬曉娟

(沈陽(yáng)工業(yè)大學(xué),沈陽(yáng) 110870)

1 引 言

離群點(diǎn)[1]檢測(cè)的目的是在大量的、復(fù)雜的數(shù)據(jù)集合中消除噪聲數(shù)據(jù)或發(fā)現(xiàn)潛在有意義的規(guī)律.當(dāng)今人類(lèi)社會(huì)每時(shí)每刻都產(chǎn)生大量的數(shù)據(jù),這些數(shù)據(jù)大多同時(shí)具有數(shù)值屬性和分類(lèi)屬性,于是混合屬性數(shù)據(jù)的離群點(diǎn)檢測(cè)問(wèn)題便引起了研究學(xué)者的關(guān)注.聚類(lèi)和離群點(diǎn)檢測(cè)緊密相關(guān),DBSCAN聚類(lèi)算法[2]具有一定的離群處理能力,它可以在較少的先驗(yàn)知識(shí)下進(jìn)行無(wú)監(jiān)督的分類(lèi),獲得對(duì)象有效的聚類(lèi)結(jié)果,而不被聚類(lèi)的點(diǎn)則是離群點(diǎn),但其聚類(lèi)半徑ε和參數(shù)閾值Minpts設(shè)置困難;Breuing等人提出了局部離群因子的概念LOF[3,4],它是基于密度的一種方法,基于密度的局部離群點(diǎn)檢測(cè)方法[5]不再將離群點(diǎn)看做一個(gè)二值屬性,而是量化地描述數(shù)據(jù)對(duì)象的離群程度,其能在數(shù)據(jù)分布不均的情況下準(zhǔn)確發(fā)現(xiàn)離群點(diǎn),但由于離群點(diǎn)在數(shù)據(jù)集中所占的比重較小,直接計(jì)算數(shù)據(jù)對(duì)象的離群度會(huì)增大計(jì)算量;文獻(xiàn)[6]提出了FCBOD算法,它是一種能夠處理混合屬性數(shù)據(jù)集的離群點(diǎn)檢測(cè)方法,它將數(shù)值屬性的質(zhì)心和分類(lèi)屬性的頻率信息作為差異性度量的主要方式,但需要進(jìn)一步研究新的距離定義來(lái)準(zhǔn)確度量不同對(duì)象間的差異性;Chen[7]等人提出了基于粗糙集理論的混合數(shù)據(jù)離群點(diǎn)檢測(cè)算法,首先指定數(shù)據(jù)對(duì)象每個(gè)屬性的粗糙鄰域,再利用屬性值的差異性計(jì)算對(duì)象的離群程度,但該算法的檢測(cè)效果對(duì)人工指定的屬性粗糙鄰域范圍參數(shù)非常敏感;針對(duì)上述存在的問(wèn)題,現(xiàn)提出了一種改進(jìn)的DBSCAN聚類(lèi)和新局部離群因子LAOF兩階段混合數(shù)據(jù)離群點(diǎn)檢測(cè)算法.在第一階段中對(duì)DBSCAN聚類(lèi)算法設(shè)定唯一參數(shù)k近鄰[8]對(duì)數(shù)據(jù)集進(jìn)行初步篩選;在第二階段中由于LOF算法重復(fù)計(jì)算k距離的計(jì)算量較大,因此構(gòu)造了新的離群因子LAOF度量篩選后數(shù)據(jù)的異常程度.

2 混合數(shù)據(jù)對(duì)象的距離度量

2.1 除一化信息熵

信息熵[9]可用于度量數(shù)據(jù)集無(wú)序和雜亂的程度.熵值越大,說(shuō)明數(shù)據(jù)集無(wú)序和雜亂程度越高;反之,說(shuō)明數(shù)據(jù)集越有序和純凈.基于此可以通過(guò)熵值的變化來(lái)確定數(shù)據(jù)對(duì)象的屬性權(quán)重,突出離群屬性.設(shè)x為隨機(jī)變量,其取值集合為s(x),p(x)表示x可能取值的概率,則x的信息熵定義為:

(1)

(2)

(3)

式(3)中Δ(Ai)為集合A除去對(duì)象Ai后的信息熵增量,Δ(Ai)越大表示把對(duì)象Ai從集合A中除去后使得整個(gè)數(shù)據(jù)集的混亂或不確定性減少得越多.本文則用Δ(Ai)表示屬性Ai的權(quán)重.

2.2 混合數(shù)據(jù)加權(quán)距離

在混合數(shù)據(jù)進(jìn)行距離度量時(shí)采用了屬性加權(quán)距離,提高離群屬性在距離度量中的作用.給定混合數(shù)據(jù)對(duì)象p={pi|i∈[1,m]},q={qi|i∈[1,m]},m為屬性數(shù),兩個(gè)對(duì)象p,q間的距離dist(p,q)為:

(4)

其中A[i]為屬性權(quán)重,由于每一個(gè)數(shù)值屬性的取值范圍不同,為了防止具有較大初始值域的數(shù)值屬性與具有較小初始值域的數(shù)值屬性相比權(quán)重過(guò)大的情況發(fā)生,對(duì)于數(shù)值屬性采用Min-max標(biāo)準(zhǔn)化處理[10],距離度量值為d(pi,qi)=|pi-qi|;

3 改進(jìn)的聚類(lèi)和局部離群因子LAOF兩階段算法的介紹

由于混合數(shù)據(jù)中離群點(diǎn)的個(gè)數(shù)占總體數(shù)據(jù)集的比重較小,為了使離群點(diǎn)挖掘更有針對(duì)性,首先通過(guò)聚類(lèi)的方法對(duì)總體數(shù)據(jù)集進(jìn)行初步的篩選.基于密度聚類(lèi)的方法不需要預(yù)先指定聚類(lèi)的簇?cái)?shù),而且能夠在含有噪聲的數(shù)據(jù)集中發(fā)現(xiàn)任意數(shù)量和形狀的簇,DBSCAN是一種經(jīng)典的基于密度的聚類(lèi)算法,但該算法需要用戶在沒(méi)有先驗(yàn)知識(shí)的情況下設(shè)定參數(shù)ε和Minpts,參數(shù)對(duì)于最終聚類(lèi)結(jié)果的質(zhì)量影響很大,為了克服輸入?yún)?shù)的敏感性,采用了輸入K近鄰代替參數(shù)ε和Minpts的方法.在對(duì)篩選后的混合數(shù)據(jù)進(jìn)行離群點(diǎn)判斷時(shí),由于局部離群因子LOF計(jì)算復(fù)雜且計(jì)算量較大,為此構(gòu)造新的局部離群因子LAOF對(duì)篩選后的數(shù)據(jù)進(jìn)行異常度的度量.

3.1 DBSCAN輸入?yún)?shù)的處理

在DBSCAN算法聚類(lèi)的過(guò)程中我們發(fā)現(xiàn),聚類(lèi)結(jié)果的好壞直接受參數(shù)ε和Minpts的影響,參數(shù)的確定往往需要專(zhuān)家的分析或大量的實(shí)驗(yàn)驗(yàn)證,這樣會(huì)造成時(shí)間的消耗和資源的浪費(fèi),為了提高聚類(lèi)質(zhì)量降低資源消耗,將k近鄰的思想引入到DBSCAN聚類(lèi)算法中,在計(jì)算k距離(k-dist)的同時(shí)獲取數(shù)據(jù)集的分布情況,在獲得數(shù)據(jù)集的先驗(yàn)知識(shí)時(shí)通過(guò)分析輸入k鄰居數(shù)代替密度閾值Minpts,并取一定數(shù)目數(shù)據(jù)對(duì)象的k-dist來(lái)計(jì)算均值k-mean代替空間半徑ε,減少多參數(shù)輸入對(duì)聚類(lèi)結(jié)果的影響并根據(jù)改進(jìn)的方法對(duì)核心點(diǎn)進(jìn)行了新的定義.數(shù)據(jù)對(duì)象數(shù)目的選取根據(jù)數(shù)據(jù)集獲取的先驗(yàn)知識(shí)確定.

3.2 DBSCAN新核心點(diǎn)的定義

改進(jìn)前的DBSCAN聚類(lèi)算法判斷核心點(diǎn)的參數(shù)需要人為輸入,在改進(jìn)后的聚類(lèi)算法中則根據(jù)計(jì)算每個(gè)數(shù)據(jù)對(duì)象的K距離有依據(jù)性的確定核心點(diǎn).

定義1.(新的核心對(duì)象)對(duì)于數(shù)據(jù)集中任意一個(gè)數(shù)據(jù)對(duì)象p∈D,如果p的第k距離k-dist (p)小于k-mean,則p為核心對(duì)象.

利用定義1對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi).在對(duì)新的核心對(duì)象進(jìn)行判斷的過(guò)程中設(shè)計(jì)了以空間換時(shí)間的算法,將每個(gè)已經(jīng)計(jì)算數(shù)據(jù)對(duì)象的k-dist值保存起來(lái)作備用,在算法的執(zhí)行過(guò)程中凡是用到k-dist的地方直接使用預(yù)先計(jì)算好的值.在該優(yōu)化中,算法需要增加規(guī)模為N的空間存儲(chǔ),而計(jì)算數(shù)據(jù)對(duì)象的第k距離鄰域時(shí)算法需要增加規(guī)模為N2級(jí)的空間開(kāi)銷(xiāo),這一步優(yōu)化可以極大的降低時(shí)間復(fù)雜度.

3.3 LAOF的定義

定義2.對(duì)象p的局部密度

(5)

對(duì)象p的局部密度是在以p為圓心以k-dist(p)為半徑的圓面積內(nèi),計(jì)算單位面積含有數(shù)據(jù)點(diǎn)的個(gè)數(shù),與LOF算法中計(jì)算數(shù)據(jù)對(duì)象的局部可達(dá)密度相比極大的降低了計(jì)算的時(shí)間復(fù)雜度.

根據(jù)LOF算法中局部離群因子求解公式,類(lèi)推LAOF算法中局部離群因子的計(jì)算公式.

定義3.對(duì)象p的局部離群因子

(6)

對(duì)象p的局部離群因子表示為L(zhǎng)A(p)與它的k個(gè)鄰居局部密度均值比值的倒數(shù).顯然p的局部密度越小,p的k個(gè)鄰居的局部密度均值越大,p的局部異常因子越大,數(shù)據(jù)對(duì)象p的離群程度越高.

3.4 混合數(shù)據(jù)離群點(diǎn)檢測(cè)算法的描述

輸入數(shù)據(jù):數(shù)據(jù)集D,聚類(lèi)中最近鄰居個(gè)數(shù)k,計(jì)算離群因子鄰居個(gè)數(shù)k1.

輸出數(shù)據(jù):特定數(shù)據(jù)對(duì)象的離群因子.

a)遍歷數(shù)據(jù)集D,利用加權(quán)距離計(jì)算每個(gè)數(shù)據(jù)對(duì)象p的k-dist(p)和鄰域Nk(p).

b)升序排列數(shù)據(jù)對(duì)象的k-dist,選取適當(dāng)數(shù)目數(shù)據(jù)對(duì)象的k-dist,計(jì)算這些數(shù)據(jù)對(duì)象k-dist的均值k-mean,根據(jù)定義1確定數(shù)據(jù)集中的核心點(diǎn).

c)從任意一個(gè)核心點(diǎn)出發(fā)找出k-mean鄰域中所有直接密度可達(dá)點(diǎn),通過(guò)直接密度可達(dá)點(diǎn)找到密度相連對(duì)象集合.遞歸循環(huán)直到?jīng)]有可以處理的核心對(duì)象為止.

d)計(jì)算未被聚類(lèi)的數(shù)據(jù)對(duì)象二次加權(quán)距離的k1-dist(p)和鄰域Nk1(p).

e)根據(jù)新構(gòu)造的局部異常因子計(jì)算每個(gè)數(shù)據(jù)對(duì)象的局部密度LA(p).

f)由定義3得數(shù)據(jù)對(duì)象p的LAOF(p)降序排列輸出.

3.5 算法的實(shí)現(xiàn)流程

第一階段:利用改進(jìn)的DBSCAN聚類(lèi)算法對(duì)混合數(shù)據(jù)做初步的篩選.

Init(char *filename,int k,int t)//讀入數(shù)據(jù)輸入K近鄰和分類(lèi)屬性;

Shujubiaozhunhua() // 數(shù)據(jù)集屬性預(yù)處理

Entropy()// 屬性權(quán)重除一劃處理

DoDBSCANrecursive()//執(zhí)行聚類(lèi)操作采用遞歸的方法

Keypointcluster() //深度優(yōu)先聚類(lèi)數(shù)據(jù)

第二階段利用新構(gòu)造的局部離群因子LAOF計(jì)算數(shù)據(jù)對(duì)象的離群度

Cin k2// 輸入最近鄰

Eentropy1()// 二次權(quán)重確定

DensityLAOF() //計(jì)算篩選后數(shù)據(jù)的離群度

Writetofile(char *filename) //將已經(jīng)處理后的結(jié)果寫(xiě)入并輸出.

4 實(shí)驗(yàn)分析

為了檢驗(yàn)提出改進(jìn)的DBSCAN聚類(lèi)和LAOF兩階段混合數(shù)據(jù)離群點(diǎn)檢測(cè)方法的有效性,下面進(jìn)行性能測(cè)試.實(shí)驗(yàn)數(shù)據(jù)來(lái)自UCI標(biāo)準(zhǔn)數(shù)據(jù)庫(kù),實(shí)驗(yàn)與改進(jìn)的LOF算法的檢測(cè)結(jié)果進(jìn)行了比較.所有算法均在VS2010中實(shí)現(xiàn),運(yùn)行環(huán)境為Win7下英特爾酷睿TMi3 3240處理器.由于離群點(diǎn)在數(shù)據(jù)集中數(shù)量較少,所以為了符合數(shù)據(jù)集的分布規(guī)律,故將heart和liverdisorder數(shù)據(jù)集中某一類(lèi)的部分對(duì)象刪除作為離群點(diǎn).表1為數(shù)據(jù)集的相關(guān)信息描述.

表1 數(shù)據(jù)集信息描述
Table 1 Information description of data set

數(shù)據(jù)集樣本個(gè)數(shù)數(shù)值屬性分類(lèi)屬性類(lèi)數(shù)heart 143762Liverdisorder143512

首先通過(guò)改進(jìn)的DBSCAN算法對(duì)上述的數(shù)據(jù)集進(jìn)行初步聚類(lèi),通過(guò)輸入不同的k近鄰得到不同的聚類(lèi)結(jié)果,表2為聚類(lèi)結(jié)果的詳細(xì)描述.

通過(guò)表2發(fā)現(xiàn)k近鄰的不同取值直接影響著聚類(lèi)的個(gè)數(shù),本階段的聚類(lèi)主要是對(duì)數(shù)據(jù)集做初步的篩選,即把數(shù)據(jù)集中最為稠密的數(shù)據(jù)簇去掉并盡可能使待檢測(cè)數(shù)據(jù)的數(shù)量達(dá)到最小,如果鄰居數(shù)不斷增加可能將部分離群點(diǎn)聚類(lèi)并增大計(jì)算量,由此可知當(dāng)k=8時(shí)聚類(lèi)數(shù)目和待檢測(cè)數(shù)據(jù)個(gè)數(shù)均達(dá)到最優(yōu)狀態(tài).然后對(duì)待檢測(cè)的數(shù)據(jù)利用新的局部離群因子LAOF計(jì)算每一個(gè)數(shù)據(jù)對(duì)象的離群程度,圖1和圖2顯示了當(dāng)聚類(lèi)的鄰居個(gè)數(shù)取定時(shí),不同鄰居個(gè)數(shù)k1對(duì)LAOF和改進(jìn)的LOF算法檢測(cè)精度的影響,在離群點(diǎn)個(gè)數(shù)固定的情況下檢測(cè)出真正的離群點(diǎn)占總數(shù)的百分比.

表2 聚類(lèi)結(jié)果
Table 2 Clustering results

數(shù)據(jù)集liverdisorderheartk近鄰456789456789聚類(lèi)數(shù)4223221022211待測(cè)數(shù)938887848282877980716667

圖1 Liver disorder 檢測(cè)精度對(duì)比Fig.1 Comparison of detection accuracy on liver disorder

圖2 heart 檢測(cè)精度對(duì)比Fig.2 Comparison of detection accuracy on heart

通過(guò)圖1可以看出在liverdisorder數(shù)據(jù)集中,當(dāng)k1取6時(shí)檢測(cè)結(jié)果達(dá)到最優(yōu),在圖2中k1=7時(shí)檢測(cè)效果最好.表3為基于聚類(lèi)和LAOF的離群點(diǎn)檢測(cè)算法效果最好時(shí)參數(shù)的取值.

表3 參數(shù)的取值描述
Table 3 Parameter value description

數(shù)據(jù)集聚類(lèi)k近鄰離群點(diǎn)檢測(cè)k1近鄰Heart 87Liverdisorder86

根據(jù)圖1與圖2的檢測(cè)結(jié)果,表4列出了在輸出離群因子值最高的前十四個(gè)數(shù)據(jù)對(duì)象中,正確找到的離群點(diǎn)占離群點(diǎn)總數(shù)的百分比,LAOF算法對(duì)數(shù)據(jù)集的檢測(cè)精度均達(dá)到90%以上與改進(jìn)的LOF算法相比具有較高的準(zhǔn)確率.由此可知該算法能夠很好地處理既含有數(shù)值屬性又含有分類(lèi)屬性的混合數(shù)據(jù).

表4 檢測(cè)結(jié)果
Table 4 Detection results

數(shù)據(jù)集數(shù)據(jù)集大小異常數(shù)據(jù)本文算法改進(jìn)的LOF算法Heart 1431492．86%71．42%liverdisorder1431492．86%64．29%

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

本文在最近鄰的基礎(chǔ)上提出了改進(jìn)的聚類(lèi)和局部離群因子的兩階段混合數(shù)據(jù)的離群點(diǎn)檢測(cè)方法,通過(guò)改進(jìn)的DBSCAN聚類(lèi)算法對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理,通過(guò)輸入鄰居的個(gè)數(shù)代替參數(shù)ε和Minpts的輸入,降低人為因素對(duì)聚類(lèi)結(jié)果的影響,進(jìn)而得到初步的異常數(shù)據(jù).通過(guò)構(gòu)造新的局部異常因子LAOF代替LOF計(jì)算數(shù)據(jù)的異常程度降低計(jì)算量,在進(jìn)行距離度量時(shí)引入除一化信息熵,并對(duì)離群點(diǎn)檢測(cè)的數(shù)據(jù)集進(jìn)行二次權(quán)重確定.經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證該算法能夠有效提高離群點(diǎn)檢測(cè)精度,降低計(jì)算復(fù)雜度.但該算法中參數(shù)k值的選取直接影響聚類(lèi)結(jié)果.因此,下一步將研究參數(shù)的確定方法,找到能夠自動(dòng)提供合理的參數(shù)值的方法.

[1] Han Jia-wei,Micheling Kamber.Data mining concepts and techniques[M].Beijing:Mechanical Industry Press,2014.

[2] An Ji-yong,Han Hai-ying,Hou Xiao-li.An improved DBscan clustering algorithm[J].Microelectronics and Computer,2015,32(7):68-71.

[3] Breuning M,Krigegel H P,Ng R,et al.LOF:identifying density based local outliers[C].Proceeding of the ACM SIGMOD International Conference on Management of Data,Dallas,TX USA,2000:93-104.

[4] Li Lu,Huang Liu-sheng,Yang Wei.Privacy-preserving LOF outlier detection[J].Knowledge and Information Systems,2015,42(3):579-597.

[5] Hu Cai-ping,Qin Xiao-lin.A local outlier detection algorithm based on density DLOF[J].Computer Research and Development,2010,47(12):2110-2116.

[6] Salman Ahmed,Shaikh Hiroyuki Kitagawa.Top-k outlier detection from uncertain data[J].International Journal of Automation and Computing,2014,11(2):128-142.

[7] Chen Yu-min,Miao Duo-qian,Zhang Hong-yun.Neighborhood outlier detection [J].Expert Systems with Applications,2010,37(12):8749-8750.

[8] Wang Qian,Liu Shu-zhi.Improvement of local outlier mining method based on density [J].Computer Application Research,2014,31(6):1693-1696.

[9] Wang Jing-hua,Zhao Xin-xiang,Zhang Guo-yan.NLOF:a new local outlier detection algorithm based on density [J].Computer Science,2013,40(8):181-185.

[10] Gautam Bhattacharya,Koushik Ghosh,Ananda S.Chowdhury.Outlier detection using neighborhood rank difference[J].Pattern Recognition Letters,2015,60(4):24-31.

附中文參考文獻(xiàn)：

[1] Jiawei Han,Micheling Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社,2014.

[2] 安計(jì)勇,韓海英,侯效禮.一種改進(jìn)的DBscan聚類(lèi)算法[J].微電子學(xué)與計(jì)算機(jī),2015,32(7):68-71.

[5] 胡彩平,秦小麟.一種基于密度的局部離群點(diǎn)檢測(cè)算法DLOF[J].計(jì)算機(jī)研究與發(fā)展,2010,47(12):2110-2116.

[8] 王 茜,劉書(shū)志.基于密度的局部離群數(shù)據(jù)挖掘方法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用研究,2014,31(6):1693-1696.

[9] 王敬華,趙新想,張國(guó)燕.NLOF:一種新的基于密度的局部離群點(diǎn)檢測(cè)算法[J].計(jì)算機(jī)科學(xué),2013,40(8):181-185.