許　琳， 趙茂先

(山東科技大學 數學與系統工程學院，山東 青島 266590)

?

基于密度的局部離群數據挖掘算法研究

許琳， 趙茂先

(山東科技大學 數學與系統工程學院，山東 青島 266590)

為了研究局部離群數據挖掘方法，將K均值聚類算法和基于影響空間的局部離群因子算法相結合，構造了一種基于K均值和影響空間的局部離群因子的方法.該方法首先通過聚類把靠近簇中心密集區(qū)域的正常數據剔除，然后再調用INFLOF算法對剩余數據進行挖掘，從而減少了中間結果的存儲，大大減少了算法的運行時間.最后分別通過隨機數據和實際數據實驗，驗證了K-INFLOF算法在離群數據挖掘中的準確性和運行效率.

離群數據挖掘；INFLOF算法；K-means算法；時間復雜度

數據挖掘是在諸多實際問題中挖掘出隱藏在內的有效信息的過程[1].數據挖掘的研究主要聚焦在尋求數據集中大部分數據遵從適用的模式，但是，現實中那些偏離正常數據模式的數據點往往隱藏了更多有價值的信息，更值得去挖掘.離群數據挖掘在很多領域中得到應用，比如入侵檢測[2]、金融欺詐檢測[3]、醫(yī)療與公共衛(wèi)生檢測[4]、工業(yè)損檢[5]等.自20世紀以來，各學術領域的專家提出了眾多離群數據挖掘方法，最經典的方法有：基于統計的方法、基于聚類的方法、基于距離的方法和基于密度的方法.基于統計的方法[6]是假設待測數據符合已知特定的分布模型，凡是與該模型不吻合的數據點被當作離群數據.該方法需事先獲得待測數據的分布模型，現實中這個條件往往無法滿足.基于聚類的離群數據挖掘方法[7]是把離群數據挖掘當做聚類過程的附屬工作，離群數據則是聚類過程中產生的副產品.該方法比較直觀，而且有較長的研究歷史，理論體系完整.基于距離的離群數據挖掘方法[8]是諾爾等人在20世紀90年代年提出的，該方法對離群點定義如下：如果待測數據中的某個對象o與大部分數據的距離較遠，那么這個對象o被當作離群點.該方法不能挖掘出那些位于兩個簇中間的離群點，即局部離群點.為了解決這個問題，21世紀初Breunig[9]提出了局部離群因子LOF(LocalOutlierFactor)的方法，該方法是以待測數據中每個數據對象的最近鄰居為出發(fā)點，計算每個對象的鄰居與該對象的密度比，即LOF值，數據對象的離群程度隨著LOF值的增大而增大. 但是，當待測數據集中兩個密度差別較大的簇靠近時，位于簇之間的臨界數據點就會被容易誤判成離群點.2006年Jen等人[10]提出了一種基于影響空間的局部離群挖掘INFLOF(InfluencedLocalOutlierFactor)方法. 該方法不僅考慮了數據點的最近鄰居，還考慮了數據點的逆最近鄰居，最近鄰居和逆最近鄰居的并集稱為影響空間，然后再考察影響空間中數據與該數據的密度之比，即INFLOF值.數據對象的離群程度隨著INFLOF值增大而增大.由于INFLOF算法需要計算每個數據點的INFLOF值，所以增加了中間計算結果的存儲，降低了算法的運行效率.為提高算法效率，本文提出一種K均值和INFLOF算法相結合的方法.

1　相關概念

1.1K均值算法

1.2INFLOF算法的基本概念

下面給出關于INFLOF算法的相關概念，為了敘述方便，公式中符號定義如下：D為假定的數據集，n表示數據集D的數據個數，o和p為數據集D中的對象.

定義2[10]對象p的距離鄰域.數據集D中所有與對象p距離小于等于k-distance(p)的對象的集合，叫做對象p的k距離鄰域，記作Nk(p).

定義3[10]對象p的逆k距離鄰域. 數據對象p的逆k距離鄰域為數據集D中k距離鄰域含有數據對象p的數據集合，記作RNNk(p)，用符號表示為：RNNk(p)={q|q∈D,p∈Nk(p)}.

定義4[10]對象p的影響空間.對象p的影響空間的定義是對象p的k距離鄰域和逆k距離鄰域的合并，記作ISk(p)，即

ISk(p)=Nk(p)∨RNNk(p)

定義5[10]對象p的局部密度.對象p的局部密度為對象p的k距離的倒數，記作den(p)，即

(1)

根據上述定義，對象p的INFLOF值的計算公式定義如下：

(2)

如果對象p的影響空間中數據點的密度比對象p的局部密度大，那么INFLOF值越大，那么對象p成為離群點的幾率越大.

由此可以得出INFLOF算法基本思想為:首先計算數據集中每個數據oi的INFLOF值，然后將對象oi的INFLOF值進行降序排序，排在前面的數據對象oi離群性更強.

2　K-INFLOF算法

INFLOF算法是一種典型的基于密度的離群數據挖掘方法，該方法不僅可以有效挖掘出“局部”[13]和“全局”離群點，也可以挖掘出密度相差很大的數據集彼此靠近情況下的臨界離群點.但INFLOF算法在對數據挖掘的過程中需要遍歷整個數據集以計算每個數據點的INFLOF值，然而實際上具有較高密度的數據點一般不是離群點，所以算法運行過程中會產生龐大的結果存儲，使算法的運行效率較低. K-INFLOF算法從這一點出發(fā)，由兩個算法組成.首先調用K-means算法對數據集聚類，將那些非離群點剪枝，從而提高INFLOF算法的運行效率.剪枝規(guī)則為：對于每個類的數據對象計算其到類中心的距離，如果距離大于等于類半徑Ri，相應的數據就被提取出來，組成離群數據候選集Q.其中，離群數據篩選條件為

(3)

式中：pi為類Ci中待測的離群數據；d(pi,mi)是pi到類Ci中心mi的距離；Ri是類Ci的半徑.然后再對離群候選集Q中的數據對象調用INFLOF算法.

綜上所述，K-INFLOF算法步驟如下：

(1)在數據集D中的n個數據對象中選取k個數據點當做最初類中心；

(2)計算每一個數據對象到類均值的距離，并根據最小距離對相應數據進行劃分；

(3) 重新計算每個類的均值，更新為類中心；

(4) 重復步驟(2)、(3)，直到目標函數最優(yōu)；

(5)將數據集D中每個類中的對象按照公式(3)進行剪枝，得到離群候選集Q；

(6) 遍歷數據集Q，求得每個數據對象的距離，從而得到相應的k距離鄰域和逆k距離鄰域；

(7) 遍歷每個數據對象的k距離鄰域和逆k距離鄰域得到數據對象的影響空間；

(8) 根據公式(1)計算離群候選集中數據對象的局部可達密度；

(9)根據公式(2)計算離群候選集中數據對象的INFLOF值；

(10)對所有對象的INFLOF值降序排序，得到前m個INFLOF值最大的數據點.

3　數值實驗

數值實驗分別采用模擬數據集和實際數據集驗證，將K-INFLOF算法、傳統的LOF算法和INFLOF算法進行對比.所有算法均在Matlab2013a中實現，運行環(huán)境為Win8系統下Intel Core i3CPU 2.90Hz，4.00GB內存.

3.1模擬數據實驗

模擬數據實驗采用隨機生成的模擬數據集，如圖1所示，待測數據集包括兩個密度不同的隨機生成的正態(tài)分布簇，其中“十字星”數據點簇有1 500個數據點，“八角星”數據點簇有500個數據點，5個“四角星”代表的是離群點.

圖1　實驗數據集中的散點圖

算法首先要對模擬數據集進行聚類，聚類數目k值選取2～5分別運行K-means算法，當k取3時K-means算法運行效率最高，并且與數據集的擬合度最好. 因此，在本次實驗中，聚類個數k取值為3.

為了驗證K-INFLOF算法的準確性，首先假定取離群值最大的5個數據點，即m的值為5.下面引出算法準確性的評價指標，即檢測誤差率ρ，且

式中：rn為要挖掘的離群點的個數，在本次實驗中rn取5；rt為挖掘到的離群數據點是真正的離群數據的個數；Rn表示待測數據集中離群點的個數；R表示樣本數據集中的總數.LOF算法和K-INFLOF算法的結果對比見表1.

由表1可得，當最近鄰居取值較小時，K-INFLOF算法的檢測誤差率較小，由此可得K-INFLOF算法使挖掘結果更為精準.

表1LOF算法和K-INFLOF算法實驗結果對比

MinptsLOF算法K-INFLOF算法rtρ/%rtρ/%23456789112355550.200.200.150.100000235555550.150.10000000

然后在該數據集上運行INFLOF算法和K-INFLOF算法.由表2可知，本次實驗中數據集被剪枝掉1 189個數據后，K-INFLOF算法的運行時間要遠小于INFLOF算法的運行時間.

表2 Minpts=8時INFLOF算法和K-INFLOF算法運行時間對比

算法被去除數據個數運行時間/msK-INFLOF算法118962INFLOF算法0578

圖2展示的是兩種算法的運行時間的對比，由圖2可知，K-INFLOF算法和INFLOF算法的運行時間都隨著參數Minpts的增長而增長，但是K-INFLOF算法的運行時間遠小于INFLOF算法.

圖2　兩種算法隨著Minpts變化時運行時間對比圖

3.2實際數據實驗

本次實驗數據是美國NBA2014-2015常規(guī)賽季球員技術數據，實驗將取3個屬性(分別是場均三分球命中率，場均三分球得分和場均總得分)，共369個數據進行研究. 在運行K-INFLOF算法時，聚類數目選取3～7，分別進行5次獨立重復的實驗，最終結果取5次實驗結果的平均值. 為了便于比較，取每種算法離群因子值最高的前五名球員進行對比[14]，最近鄰居個數取17.表3～表5為三種算法的運算結果.

表3LOF算法挖掘結果

離群因子值球員場均三分命中率/%場均三分球得分場均總得分3.53拉塞爾-維斯布魯克29.93.828.13.17J.J.-雷迪克43.75.516.43.09馬克-加索爾17.60.710.72.93安東尼-莫羅43.46.917.42.60德里克-羅斯282.819.7

表4INFLOF算法挖掘結果

離群因子值球員場均三分命中率/%場均三分球得分場均總得分5.37凱里-歐文41.57.921.74.99拉塞爾-維斯布魯克29.93.828.14.71馬克-加索爾17.60.710.74.25J.J.-雷迪克43.75.516.44.07安東尼-莫羅43.46.917.4

表5K-INFLOF算法挖掘結果

離群因子值球員場均三分命中率/%場均三分球得分場均總得分5.37凱里-歐文41.57.921.74.69拉塞爾-維斯布魯克29.93.828.14.29J.J.-雷迪克43.75.516.43.91馬克-加索爾17.60.710.74.07安東尼-莫羅43.46.917.4

通過三種算法的挖掘結果發(fā)現，在LOF算法中，排名前五的球員，都是某一個屬性表現了離群性，例如排名第一的拉塞爾-維斯布魯克和排名第五的德里克-羅斯都是場均總得分高的球員，說明該類型球員不善于投三分球，但是其他得分方式更為高效，同時有效地避開了自己的弱項；排名第二的J.J.-雷迪克和排名第四的安東尼-莫羅在場均三分命中率上表現突出，說明該類球員是一名優(yōu)秀的三分球投手，較高的場均三分得分也表明了他們優(yōu)秀的投籃選擇；排名第三的馬克-加索爾場均三分球命中率和場均三分得分都非常低，但是場均得分較高，他作為一名內線球員把主要的攻擊點放到了內線，并沒有開發(fā)自己的射程.而在INFLOF和K-INFLOF算法中除了能將LOF算法中各種類型的球員挖掘出來外，還可以挖掘專業(yè)三分球投手，例如在兩個算法中均排名第一的凱里-歐文，該類型的球員三項數據都比較高，在球隊中表現出一定的離群性，是一名典型的球隊當家球星.由此可得，K-INFLOF算法相較于LOF算法可以挖掘出更多類型的球員.

圖3是三種算法運行時間對比圖，K-INFLOF算法將231個數據剪枝掉，由圖3可以看出，K-INFLOF算法的運行時間遠小于LOF算法和INFLOF算法，說明K-INFLOF算法的復雜度大大減少.

圖3　三種算法運行時間對比圖

4　結束語

本文在經典INFLOF算法的基礎上加入了K-means聚類算法，得到K-INFLOF算法.該方法先將類中心非離群點剪枝掉，得到離群候選集，然后再運用INFLOF算法，從而提高了算法的有效性.模擬數據實驗表明，K-INFLOF算法分別在算法準確性和算法的運行效率方面高于LOF算法和INFLOF算法.實際數據實驗表明，K-INFLOF算法不僅能比LOF算法挖掘出類型更加多樣性的球員，而且離群因子差異較大，使離群數據更為明顯；通過三種算法運行時間的對比，可以明顯地看出K-INFLOF算法運行時間遠小于LOF算法和INFLOF算法.因此，K-INFLOF算法在離群數據挖掘中與傳統的基于密度的離群數據挖掘算法相比，提高了算法的運行效率和所挖掘數據的準確性、多樣性.

[1]韓家煒, 裴健. 數據挖掘：概念與技術[M]. 北京: 機械工業(yè)出版社, 2012.

[2]王茜, 唐銳. 基于頻繁模式的離群點挖掘在入侵檢測中的應用[J]. 計算機應用研究, 2013(4): 1 208-1 211.

[3] 吳建. 數據挖掘技術在金融領域的應用研究[J].電腦知識與技術, 2012(9): 1 982-1 984.

[4] Cogoi P, Bhattachariyya D K, Borah B. A survey of outlier detection methods in network anomaly identification[J]. The Computer Journal, 2011, 54(4): 570-588.

[5]Basu S, Meckesheimer M. Automatic outlier detection for time series: An application to sensor data[J]. Knowledge and Information Systems-Special Issue on Mining Low-Quality Data, 2007, 11(2): 137-154.

[6]Chandola V, Banerjee A, Kumar V. Anomaly detection: A survey[J]. ACM Computing Surveys, 2010, 41(3): 15-58.

[7]楊福萍, 王洪國, 董樹霞, 等. 基于聚類劃分的兩階段離群點檢測算法[J], 計算機應用研究, 2013(7): 1 942-1 945.

[8]Cheema M A, Zhang W, Lin X, et al. Continuous reverse k nearest neighbors queries in Euclidean space in spatial networks[J]. The VLDB Journal, 2012, 21(1): 69-95.

[9]Breuning M, Kriegel H P. LOF: Identifying density-based local outliers[C]// Dallas: ACM sigmod record, 2000, 29(2): 93-104.

[10] Jin W, Tung K , Han J, et al. Ranking outliers using symmetric neighborhood relationship[C]// Singapore: Proceedings of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2006, 15(3): 577-593.

[11] 吳進寶. K-means算法研究綜述[J]. 電子技術與軟件工程, 2014(18): 29-33.

[12] 趙京勝, 韓凌霄, 孫宇航.一種優(yōu)化初始中心的改進K-means算法[J], 青島理工大學學報,2015,36(6),22-26.

[13] 王敬華, 趙新想, 張國燕, 等.NLOF:一種新的基于密度的局部離群點檢測算法[J]. 計算機研究與發(fā)展, 2013(8): 16-23.

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

(編輯：郝秀清)

Study of local outliers mining algorithm based on density

XU Lin， ZHAO Mao-xian

(College of Mathematics and Systems Science, Shandong University of Science and Technology,Qingdao266590,China)

Inordertostudytheoutliersminingalgorithm,wecombinedK-meansalgorithmwithinfluencedlocaloutlierfactor(referredtoasINFLOF)algorithm,andgeneratedanalgorithmwhichbasedontheK-meansandinfluencedlocaloutlierfactor(referredtoasK-INFLOF).Firstly,thismethodremovednormaldatafromthedenseareasnearthecenteroftheclass,thencalledINFLOFalgorithmexcavateremainingdata,therebyreducingstorageoftheintermediateresults,greatlyreducedtherunningtimeofthealgorithm.FinallytheaccuracyandefficiencyofK-INFLOFalgorithmindataminingisverifiedbyrandomdataandrealdataexperimentsrespectively.

outiliersdetection；INFLOF(influencedlocaloutlierfactor)algorithm；K-meansalgorithm；timecomplexity

2015-12-07

國家自然科學基金項目(61572128)

許琳, 女, 18954237262@163.com;

趙茂先, 男,sdzmx66@sohu.com.

1672-6197(2016)06-0007-05

TP301.6

A