周 鵬，程艷云

(南京郵電大學(xué) 自動化學(xué)院，江蘇 南京 210023)

一種改進的LOF異常點檢測算法

周 鵬，程艷云

(南京郵電大學(xué) 自動化學(xué)院，江蘇 南京 210023)

LOF異常點檢測算法在實際應(yīng)用中有兩個缺陷：一是離群因子值只與參數(shù)K有關(guān)，當K取值不同時，離群因子的值將不同，之前是異常點的數(shù)據(jù)可能不再是異常點。二是對于未知異常點個數(shù)的數(shù)據(jù)集，選擇參數(shù)K以保證離群點的挖掘數(shù)量合理難以做到。因此，提出一種結(jié)合平均密度的改進LOF異常點檢測算法。首先分析數(shù)據(jù)集中數(shù)據(jù)點的平均密度，根據(jù)密度的分布情況確定數(shù)據(jù)集的異常點個數(shù)M1及異常集D1，然后通過計算離群因子確定M2(M2=M1)個異常點及異常集D2。取D1與D2的交集作為最終的離群集。實驗結(jié)果表明，改進算法在檢測精準性方面有顯著提高，誤報率較低，綜合評價指標F值比LOF算法有顯著增強。

LOF算法；平均密度；異常點集；離群因子

0 引 言

LOF(Local Outlier Factor)是一種常用的異常點檢測算法。該算法通過計算數(shù)據(jù)集中每個數(shù)據(jù)點的離群因子值來確定異常點集，通常選取離群因子最大的若干個點作為異常點[1]。這種用離群因子來確定異常點的方法在已知異常點個數(shù)的情況下檢測精確度很高。但實際應(yīng)用中，異常點的個數(shù)可能事先并不知道，因此使用LOF算法來確定異常點集時，參數(shù)K的選擇將顯得十分重要[2]。當K選擇不合適時，可能將大量正常的數(shù)據(jù)當作異常值，或?qū)⒃S多異常值歸為正常值[3]。針對LOF算法的改進主要有三個方向：通過改進距離度量使密度更加合理；通過減枝降低算法的復(fù)雜度[4]；人工獲取最佳的K值[5]。這些改進算法提高了離群點檢測的精確度，但對于離群點個數(shù)未知時，如何確定離群點的個數(shù)及離群集顯得蒼白無力。

1 LOF離群點檢測算法

LOF算法是一種非常經(jīng)典的異常數(shù)據(jù)挖掘算法，通過計算每個樣本數(shù)據(jù)點的異常程度值來確定該點是否是異常點[6]。基于文獻[7]的研究成果，局部異常點的異常程度和周圍樣本的分布情況有關(guān)。涉及到的幾個定義如下：

定義1(K距離)：數(shù)據(jù)對象q的k距離定義為數(shù)據(jù)集中到數(shù)據(jù)對象q距離最近的第k個點到q的距離，記作k-distance(q),這里的距離指歐氏距離即直線距離。

定義2(K距離鄰域)：數(shù)據(jù)集中與數(shù)據(jù)對象q之間的距離不大于k距離的數(shù)據(jù)點組成的集合，即

Nk-distance(q)(p)={p∈D{q}|d(q,p)≤

k-distance(q)}

(1)

定義3(可達距離)：p,q為數(shù)據(jù)集中的任意兩點，p到q的可達距離定義為：

reach-distk(p,q)=

max{d(p,q),k-distance(q)}

(2)

其中，d(p,q)表示點p和點q之間的歐氏距離。

定義4(局部可達密度)：q的局部可達密度指q到其鄰域內(nèi)的所有點的平均可達距離的倒數(shù)。常用密度表示，計算方法如下：

(3)

其中，|Nk(q)|為q的k鄰域內(nèi)的點的個數(shù)。由于可能存在若干個點到q的距離相等，故k近鄰的點可能不止一個，所以有|Nk(q)|≥k。若lrdk(q)越大，表明q的密度越大，q點越正常。

定義5(局部離群因子)：表征數(shù)據(jù)的離群程度，計算方法如下：

(4)

若LOF值遠遠大于1，表明q點的密度與整體數(shù)據(jù)密度差異較大，被視為離群點。LOF值越接近于1，表明點q越正常。

LOF算法的優(yōu)點有[8]:

(1)算法將數(shù)據(jù)點q與周圍k個點相結(jié)合進行分析，使最終獲得的離群因子值更加合理，降低了密度極大值和密度極小值對整體數(shù)據(jù)的影響。

(2)采用數(shù)值的形式表示數(shù)據(jù)點的離群程度，更易于理解。

(3)只需設(shè)置一個參數(shù)k，易于操作和實現(xiàn)。

LOF算法的缺點包括[9]：

(1)若數(shù)據(jù)集確定，最終的離群因子值只和參數(shù)k有關(guān)。當k選擇不同時，可能之前是離群點的數(shù)據(jù)樣本現(xiàn)在不再是離群點。

(2)對于未知離群點個數(shù)的數(shù)據(jù)集，選擇參數(shù)k以保證離群點的挖掘數(shù)量合理難以做到。

2 LOF相關(guān)改進算法分析

針對LOF算法的改進算法有很多。文獻[10]將LOF算法的距離度量由歐氏距離改為和向量的內(nèi)積有關(guān)的度量。將數(shù)據(jù)點x={x1,x2,…,xn}和y={y1,y2,…,yn}看成兩個向量，則有

(5)

dist(x,y)=1-sim(x,y)

(6)

其中，dist(x,y)是數(shù)據(jù)對象x和y之間的距離。

同時對參數(shù)k設(shè)定一個范圍，k∈[Minpts,Maxpts]。對于每一個k值，算法執(zhí)行一次之后會獲得一個離群因子值。針對k取所有可能值的情況下分別運行之后，對每個點獲得的離群因子求均值。

(7)

文獻[11]針對k距離的定義提出了改進，將k距離值定義為k個近鄰點到中心點距離的均值。并對lrdk(q)重新定義，將q的k鄰域內(nèi)所有點的離群因子值的均值作為點q的離群因子值，如下所示：

(8)

(9)

文獻[12]采用剪枝的方式來檢測離群點，改進了LOF算法的lrdk(q)，并將其定義為數(shù)據(jù)點q的點密度，然后計算數(shù)據(jù)點q與其他數(shù)據(jù)點p的相異度。p到q的相異度為：

ddp→q=ρp·d(p,q)

(10)

則數(shù)據(jù)點p和數(shù)據(jù)點q之間的最大相異度為：

dpq=max{ddp→q,ddq→p}

(11)

然后表示出相異度矩陣DSM并生成無向連通圖，根據(jù)相異度原理，若兩個數(shù)據(jù)對象之間的相異度越大，則在無向連通圖中它們之間的距離越遠。接下來開始剪枝，首先剪距離最大的兩個數(shù)據(jù)點，將其分成兩個子樹。遍歷左右兩個子樹并繼續(xù)剪枝。若最后削成的子樹包含的節(jié)點小于k，則視為離群點。

相關(guān)的改進算法大多都是從距離度量方面以及最終離群因子的計算方面進行改進。文獻[10]將密度和向量內(nèi)積相結(jié)合，并給了k一定的范圍。讓k從最小值到最大值依次變化進行實驗。優(yōu)點是削弱k值對整個實驗的影響，缺點是當k值變化范圍較廣時，實驗次數(shù)較多，且當數(shù)據(jù)量巨大時，算法的時間復(fù)雜度會異常龐大。文獻[11]提出的算法，用k個距離的均值作為k近鄰，這樣可以降低當數(shù)據(jù)中心點選擇到那些可能是離群點的數(shù)據(jù)點時帶來的誤差。但當數(shù)據(jù)集的離群點個數(shù)未知時，該算法對如何選擇合適的k值沒有提出改進。文獻[12]通過剪枝的方式獲取離群點。依據(jù)數(shù)據(jù)點之間的相異度，將數(shù)據(jù)集表示成無向連通圖，剪枝當前相異度最大的兩個數(shù)據(jù)點。這種算法在剪枝的同時，還能獲得不同類的數(shù)據(jù)集。該算法適合數(shù)據(jù)量較小的數(shù)據(jù)集。當數(shù)據(jù)量較大時，生成無向連通圖的工作量將會很大，同時每一步只剪一枝。若離群點個數(shù)相對較少，則剪枝的次數(shù)將會很多，大部分的工作量將花在剪枝方面，算法效率不高。

當前的改進算法一定程度上提高了離群點檢測算法的精確度，但對如何確定離群點的大致個數(shù)，即選擇合適的k值，并沒有提出改進方案。因此，文中接下來的內(nèi)容是針對如何確定大致的離群點個數(shù)，以提高檢測精確率。

3 基于平均密度和離群因子的LOF算法

對于一個只包含數(shù)值型數(shù)據(jù)的數(shù)據(jù)集D，若將每一條數(shù)據(jù)的屬性看成是一個維度的話，則每一條數(shù)據(jù)可以映射成空間中的一個點。將數(shù)據(jù)集D中的所有數(shù)據(jù)進行映射，會得到分布在m維空間中的N個數(shù)據(jù)點。不同數(shù)據(jù)點周圍的點分布多少并不相同，這就產(chǎn)生了一個數(shù)據(jù)分布點數(shù)差，即密度差。從數(shù)據(jù)的整體分布來看，數(shù)據(jù)點的密度不全相同，有的點密度較大，有的點密度較小。密度較大的點的個數(shù)會隨著密度的增大而減少，而密度較小的點的個數(shù)也會很少(通常離群點都是存在于密度較小的點中)。大部分數(shù)據(jù)點的密度處于中間位置。

鑒于上述討論，離群點總是存在于密度較小的數(shù)據(jù)點中。且由于離群點的個數(shù)相對整個數(shù)據(jù)集來說較少，故低密度點的個數(shù)也相對較少。因此，如果能夠知道數(shù)據(jù)集中所有數(shù)據(jù)點的密度，做出密度個數(shù)分布圖，就可以大致知道離群點的個數(shù)，同時可以獲得離群點集D1。接下來調(diào)節(jié)LOF算法的參數(shù)k，使離群因子大于1的個數(shù)與密度個數(shù)分布圖獲得的離群點個數(shù)相當。這樣，通過離群因子的計算可以獲得離群點集D2。取D1與D2的交集作為最終的離群點集。

改進算法涉及到的定義及公式如下：

定義6(R鄰域)：以數(shù)據(jù)點q為中心，R為半徑所構(gòu)成的區(qū)域。

定義7(R鄰域平均距離)：R鄰域內(nèi)數(shù)據(jù)點到點q的距離的均值。

(12)

定義8(點密度)：R鄰域內(nèi)點的個數(shù)與R鄰域平均距離的比值。

(13)

其中，|NR(q)|是q的R鄰域內(nèi)點的個數(shù)。

具體的算法步驟如下：

Step1:輸入?yún)?shù)R，計算每個數(shù)據(jù)對象的R鄰域點個數(shù)、R鄰域平均距離及點密度。

Step2:找到密度跳變較大或密度對應(yīng)的點個數(shù)跳變較大的位置。獲取離群點個數(shù)M1及離群點集D1。

Step3:調(diào)節(jié)參數(shù)K，使離群因子值大于1的點個數(shù)為M1。

Step4:獲取對應(yīng)的M1個離群點集D2。

Step5:輸出最終離群點集，D'=D1∩D2。

4 實驗仿真

仿真使用開源數(shù)據(jù)集。開源數(shù)據(jù)集具有明確的標識，因此可以用來檢測聚類、分類或離群點算法的精確度。

“牌手”數(shù)據(jù)集，是UCI數(shù)據(jù)庫中用于檢測分類算法精確度的數(shù)據(jù)集。它依據(jù)數(shù)據(jù)的密度分布將所有數(shù)據(jù)記錄分為4類。為了驗證文中離群點檢測算法的有效性，隨機取出500條第1類數(shù)據(jù)，然后從第2類數(shù)據(jù)集依次向第1類數(shù)據(jù)集中加入10、20、30、40條數(shù)據(jù)進行實驗，由于第2類數(shù)據(jù)相比第1類數(shù)據(jù)具有異常特性，可以看作是異常數(shù)據(jù)進行挖掘。實驗的測試環(huán)境是個人PC機，配置Intel Core2,T6500 2.10 GHz,2G內(nèi)存，操作系統(tǒng)為Window7,編程環(huán)境為JAVA 8.0。

LOF算法與文中算法的檢測結(jié)果如表1所示。

表1 LOF算法及改進算法的檢測結(jié)果

計算兩種檢測算法的精確率P和召回率R以及加權(quán)評價指標值F[13]。有：

(14)

(15)

(16)

其中，TP為檢索到的正確個數(shù)；FP為檢索到的錯誤個數(shù)；FN為未檢索到的正確個數(shù)；TN為未檢索到的錯誤個數(shù)。

表2列出了兩種算法的檢測指標。

表2 LOF算法及改進算法的檢測指標 %

圖1為兩種算法在不同異常數(shù)據(jù)下的F值曲線。

圖1 評價指標值F曲線

文中改進算法根據(jù)數(shù)據(jù)的密度個數(shù)分布情況確定大致的離群點個數(shù)M1，并獲得此時的離群點數(shù)據(jù)集D1。然后調(diào)節(jié)LOF算法的參數(shù)K，根據(jù)離群因子值確定M2(M2=M1)個離群點及離群數(shù)據(jù)集D2(離群因子大于1的M2個數(shù)據(jù)點)。取D1與D2的交集作為最終的離群集。

由實驗結(jié)果可知，文中改進算法的精確率高于LOF算法，即誤報率更低。但召回率略低于LOF算法，這僅僅說明LOF算法能夠找到更多的異常值，但同時也引入了大量的非異常值。在許多關(guān)于離群點檢測的應(yīng)用中，要求快速檢測出真實的離群點[14]，從這方面而言，LOF算法雖然能夠盡可能多地確定離群點，但其檢測精度卻不夠高，這對于離群點檢測而言是致命的打擊。從圖1可以看出，改進后的算法相比于LOF算法檢測效率更高。加權(quán)評價指標值F越大，檢測效果越好。此外，改進算法在確定異常數(shù)據(jù)的個數(shù)時，并不受真實離群點個數(shù)的影響，但結(jié)果卻相對準確。因此表明改進的離群點檢測算法同樣適用于離群點個數(shù)未知的數(shù)據(jù)集。

5 結(jié)束語

在分析LOF離群點檢測算法及其相關(guān)改進算法的基礎(chǔ)上，提出結(jié)合數(shù)據(jù)分布平均密度的LOF算法。該算法一定程度上可以確定離群點的個數(shù)，同時取密度分布離群集和LOF異常因子離群集的交集作為最終的離群集。大大提高了檢測的準確率，降低了誤報率。從綜合評價指標值F可以看出，改進后的算法綜合準確率和召回率后，算法性能比單一的LOF離群點檢測算法要好。

[1] 薛安榮,姚 林,鞠時光,等.離群點挖掘方法綜述[J].計算機科學(xué),2008,35(11):13-18.

[2] 閆少華,張 巍,滕少華.基于密度的離群點挖掘在入侵檢測中的應(yīng)用[J].計算機工程,2011,37(18):240-242.

[3] 徐 翔,劉建偉,羅雄麟.離群點挖掘研究[J].計算機應(yīng)用研究,2009,26(1):34-40.

[4] 張衛(wèi)旭,尉 宇.基于密度的局部離群點檢測算法[J].計算機與數(shù)字工程,2010,38(10):11-14.

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

[6] 楊風(fēng)召,朱揚勇,施伯樂.IncLOF:動態(tài)環(huán)境下局部異常的增量挖掘算法[J].計算機研究與發(fā)展,2004,41(3):477-484.

[7] BREUNIG M M,KRIEGEL H P,NG R T,et al.OPTICS-OF:identifying local outliers[M]//Principles of data mining and knowledge discovery.Berlin:Springer,1999.

[8] 王 飛.iLOF*:一種改進的局部異常檢測算法[J].計算機系統(tǒng)應(yīng)用,2015,24(12):233-238.

[9] 肖 輝,龔 薇.基于可達鄰域的異常檢測算法[J].計算機工程,2007,33(17):74-76.

[10] GUAN H,LI Q,YAN Z,et al.SLOF:identify density-based local outliers in big data[C]//Proceedings of web information system and application conference.[s.l.]:IEEE,2015:61-66.

[11] SALEHI M,LECKIE C,BEZDEK J,et al.Fast memory efficient local outlier detection in data streams[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(12):3246-3260.

[12] 楊茂林,盧炎生.基于剪枝的海量數(shù)據(jù)離群點挖掘[J].計算機科學(xué),2012,39(10):152-156.

[13] JIANG M,FALOUTSOS C,HAN J.CatchTartan:representing and summarizing dynamic multicontextual behaviors[C]//ACM SIGKDD international conference on knowledge discovery and data mining.[s.l.]:ACM,2016:945-954.

[14] 閆 偉,張 浩,陸劍峰.一種離群數(shù)據(jù)挖掘新方法的研究與應(yīng)用[J].控制與決策,2006,21(5):563-566.

AnImprovedLOFOutlierDetectionAlgorithm

ZHOU Peng，CHENG Yan-yun

(School of Automation，Nanjing University of Posts and Telecommunications，Nanjing 210023，China)

In practical application,LOF,an anomaly detection algorithm,has two defects.One is the outlier factor value only related to the parameterK.WhenKis changed,the value will be different from before and an abnormal point may be a normal point.Another is for a data set with unknown abnormal points.It is very hard to choose a suitable parameterKto ensure reasonable mining number of outlier points.Therefore,an improved LOF combined with the average density is proposed.Firstly,the average density of each point is analyzed,and the number of abnormal points (M1) and abnormal set (D1) are determined according to the distribution of average density in the data set.ThenM2(M2=M1),another number of abnormal points,andD2,another abnormal set,are ensured through calculating the value of outlier factor.The intersection ofD1andD2is taken as the final result.Experiment shows that the improved algorithm can improve the detection precision remarkably with lower false rate,and is superior to LOF on the comprehensive evaluation indexF.

LOF;average density;abnormal point set;outlier factor

TP181

A

1673-629X(2017)12-0115-04

10.3969/j.issn.1673-629X.2017.12.025

2016-12-19

2017-04-26 < class="emphasis_bold">網(wǎng)絡(luò)出版時間

時間：2017-09-27

江蘇省自然科學(xué)基金(BK20140877，BK2014803)

周 鵬(1991-)，男，碩士研究生，研究方向為數(shù)據(jù)挖掘與智能計算；程艷云，副教授，碩士生導(dǎo)師，從事自動控制原理、網(wǎng)絡(luò)優(yōu)化的教學(xué)科研工作。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170927.0958.030.html