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

周 鵬，程艷云

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

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

周 鵬，程艷云

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

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

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

0 引 言

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

1 LOF離群點檢測算法

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

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

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

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

k-distance(q)}

(1)

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

reach-distk(p,q)=

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

(2)

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

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

(3)

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

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

(4)

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

LOF算法的優點有[8]:

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

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

(3)只需設置一個參數k，易于操作和實現。

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

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

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

2 LOF相關改進算法分析

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

(5)

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

(6)

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

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

(7)

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

(8)

(9)

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

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

(10)

則數據點p和數據點q之間的最大相異度為：

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

(11)

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

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

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

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

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

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

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

定義6(R鄰域)：以數據點q為中心，R為半徑所構成的區域。

定義7(R鄰域平均距離)：R鄰域內數據點到點q的距離的均值。

(12)

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

(13)

其中，|NR(q)|是q的R鄰域內點的個數。

具體的算法步驟如下：

Step1:輸入參數R，計算每個數據對象的R鄰域點個數、R鄰域平均距離及點密度。

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

Step3:調節參數K，使離群因子值大于1的點個數為M1。

Step4:獲取對應的M1個離群點集D2。

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

4 實驗仿真

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

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

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

表1 LOF算法及改進算法的檢測結果

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

(14)

(15)

(16)

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

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

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

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

圖1 評價指標值F曲線

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

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

5 結束語

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

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

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

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

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

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

[6] 楊風召,朱揚勇,施伯樂.IncLOF:動態環境下局部異常的增量挖掘算法[J].計算機研究與發展,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].計算機系統應用,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] 楊茂林,盧炎生.基于剪枝的海量數據離群點挖掘[J].計算機科學,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] 閆 偉,張 浩,陸劍峰.一種離群數據挖掘新方法的研究與應用[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">網絡出版時間

時間：2017-09-27

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

周 鵬(1991-)，男，碩士研究生，研究方向為數據挖掘與智能計算；程艷云，副教授，碩士生導師，從事自動控制原理、網絡優化的教學科研工作。

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