改進的DBSCAN聚類和LAOF兩階段混合數據離群點檢測方法

石鴻雁,馬曉娟

(沈陽工業大學,沈陽 110870)

1 引 言

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

2 混合數據對象的距離度量

2.1 除一化信息熵

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

(1)

(2)

(3)

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

2.2 混合數據加權距離

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

(4)

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

3 改進的聚類和局部離群因子LAOF兩階段算法的介紹

由于混合數據中離群點的個數占總體數據集的比重較小,為了使離群點挖掘更有針對性,首先通過聚類的方法對總體數據集進行初步的篩選.基于密度聚類的方法不需要預先指定聚類的簇數,而且能夠在含有噪聲的數據集中發現任意數量和形狀的簇,DBSCAN是一種經典的基于密度的聚類算法,但該算法需要用戶在沒有先驗知識的情況下設定參數ε和Minpts,參數對于最終聚類結果的質量影響很大,為了克服輸入參數的敏感性,采用了輸入K近鄰代替參數ε和Minpts的方法.在對篩選后的混合數據進行離群點判斷時,由于局部離群因子LOF計算復雜且計算量較大,為此構造新的局部離群因子LAOF對篩選后的數據進行異常度的度量.

3.1 DBSCAN輸入參數的處理

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

3.2 DBSCAN新核心點的定義

改進前的DBSCAN聚類算法判斷核心點的參數需要人為輸入,在改進后的聚類算法中則根據計算每個數據對象的K距離有依據性的確定核心點.

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

利用定義1對數據集進行聚類.在對新的核心對象進行判斷的過程中設計了以空間換時間的算法,將每個已經計算數據對象的k-dist值保存起來作備用,在算法的執行過程中凡是用到k-dist的地方直接使用預先計算好的值.在該優化中,算法需要增加規模為N的空間存儲,而計算數據對象的第k距離鄰域時算法需要增加規模為N2級的空間開銷,這一步優化可以極大的降低時間復雜度.

3.3 LAOF的定義

定義2.對象p的局部密度

(5)

對象p的局部密度是在以p為圓心以k-dist(p)為半徑的圓面積內,計算單位面積含有數據點的個數,與LOF算法中計算數據對象的局部可達密度相比極大的降低了計算的時間復雜度.

根據LOF算法中局部離群因子求解公式,類推LAOF算法中局部離群因子的計算公式.

定義3.對象p的局部離群因子

(6)

對象p的局部離群因子表示為LA(p)與它的k個鄰居局部密度均值比值的倒數.顯然p的局部密度越小,p的k個鄰居的局部密度均值越大,p的局部異常因子越大,數據對象p的離群程度越高.

3.4 混合數據離群點檢測算法的描述

輸入數據:數據集D,聚類中最近鄰居個數k,計算離群因子鄰居個數k1.

輸出數據:特定數據對象的離群因子.

a)遍歷數據集D,利用加權距離計算每個數據對象p的k-dist(p)和鄰域Nk(p).

b)升序排列數據對象的k-dist,選取適當數目數據對象的k-dist,計算這些數據對象k-dist的均值k-mean,根據定義1確定數據集中的核心點.

c)從任意一個核心點出發找出k-mean鄰域中所有直接密度可達點,通過直接密度可達點找到密度相連對象集合.遞歸循環直到沒有可以處理的核心對象為止.

d)計算未被聚類的數據對象二次加權距離的k1-dist(p)和鄰域Nk1(p).

e)根據新構造的局部異常因子計算每個數據對象的局部密度LA(p).

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

3.5 算法的實現流程

第一階段:利用改進的DBSCAN聚類算法對混合數據做初步的篩選.

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

Shujubiaozhunhua() // 數據集屬性預處理

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

DoDBSCANrecursive()//執行聚類操作采用遞歸的方法

Keypointcluster() //深度優先聚類數據

第二階段利用新構造的局部離群因子LAOF計算數據對象的離群度

Cin k2// 輸入最近鄰

Eentropy1()// 二次權重確定

DensityLAOF() //計算篩選后數據的離群度

Writetofile(char *filename) //將已經處理后的結果寫入并輸出.

4 實驗分析

為了檢驗提出改進的DBSCAN聚類和LAOF兩階段混合數據離群點檢測方法的有效性,下面進行性能測試.實驗數據來自UCI標準數據庫,實驗與改進的LOF算法的檢測結果進行了比較.所有算法均在VS2010中實現,運行環境為Win7下英特爾酷睿TMi3 3240處理器.由于離群點在數據集中數量較少,所以為了符合數據集的分布規律,故將heart和liverdisorder數據集中某一類的部分對象刪除作為離群點.表1為數據集的相關信息描述.

表1 數據集信息描述
Table 1 Information description of data set

數據集樣本個數數值屬性分類屬性類數heart 143762Liverdisorder143512

首先通過改進的DBSCAN算法對上述的數據集進行初步聚類,通過輸入不同的k近鄰得到不同的聚類結果,表2為聚類結果的詳細描述.

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

表2 聚類結果
Table 2 Clustering results

數據集liverdisorderheartk近鄰456789456789聚類數4223221022211待測數938887848282877980716667

圖1 Liver disorder 檢測精度對比Fig.1 Comparison of detection accuracy on liver disorder

圖2 heart 檢測精度對比Fig.2 Comparison of detection accuracy on heart

通過圖1可以看出在liverdisorder數據集中,當k1取6時檢測結果達到最優,在圖2中k1=7時檢測效果最好.表3為基于聚類和LAOF的離群點檢測算法效果最好時參數的取值.

表3 參數的取值描述
Table 3 Parameter value description

數據集聚類k近鄰離群點檢測k1近鄰Heart 87Liverdisorder86

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

表4 檢測結果
Table 4 Detection results

數據集數據集大小異常數據本文算法改進的LOF算法Heart 1431492．86%71．42%liverdisorder1431492．86%64．29%

5 結束語

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

[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.

附中文參考文獻：

[1] Jiawei Han,Micheling Kamber.數據挖掘概念與技術[M].北京:機械工業出版社,2014.

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

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

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

[9] 王敬華,趙新想,張國燕.NLOF:一種新的基于密度的局部離群點檢測算法[J].計算機科學,2013,40(8):181-185.