基于密度的孤立點檢測算法改進研究

呂奔，高茂庭

（上海海事大學信息工程學院，上海 201306）

基于密度的孤立點檢測算法改進研究

呂奔，高茂庭

（上海海事大學信息工程學院，上海 201306）

0　引言

孤立點檢測是數據挖掘領域的一個重要分支，在數據集中，孤立點數據通常被定義為與其他數據對象有著明顯差異的數據。Hawkins在20世紀80年代給出了一個比較接近孤立點本質的定義［1］：“孤立點與其他點如此不同，以至于讓人們懷疑它是由另一個不同的機制產生的。”孤立點檢測在實際生活中有很多重要的應用，如網絡入侵檢測、金融欺詐檢測、運動員比賽分析、醫學領域中發現病人對新的治療方案的異常反應等［2］。

為了有效地刻劃孤立點的孤立程度，Breunig等人提出了局部異常因子（LOF，Local Outlier Factor）的概念與算法［3］，LOF是一種基于密度的孤立點檢測算法，它的優點在于考察的是數據對象與其周圍鄰居相比的孤立程度，而不是從全局的角度來考慮數據的孤立特性。LOF算法不是去界定哪些數據對象是孤立點或者哪些數據對象不是孤立點，而是去量化地描述數據對象的孤立程度，通過賦予每個數據對象一個表示它孤立程度的指標，并以此作為對孤立點進行檢測的依據。數據對象的LOF值越大，則它是孤立點的可能性就越大。LOF算法只需要確定最近鄰的個數k，不需要對數據獲取過多的先驗知識［4］。

然而，在計算LOF的時候需要對全部數據依次計算，沒有針對性，計算復雜度很大。為了解決LOF時間復雜度較大的問題，本文利用DBSCAN聚類算法具有處理速度快、有效處理噪聲點的特點［5］，將DBSCAN引入進行數據的預處理，從而提出一種改進的基于密度的LOF孤立點檢測算法DBLOF（Density Based Local Outlier Factor）。DBLOF算法首先運用DBSCAN進行數據異常點的篩選，減少在孤立點檢測階段的處理數據，使得檢測數據更有針對性，然后，在計算LOF時，盡可能使用已知信息對鄰近數據對象進行優化操作，從而提高算法的執行效率。

1　DBLOF算法

傳統LOF算法的核心思想是給每一個數據對象賦予一個衡量該數據對象孤立程度的因子，這個孤立因子值并不是明確判定哪些數據對象是孤立點哪些不是孤立點，它只是用來反映數據對象是否分布在較為集中的區域中。

為使表達更清楚，在介紹LOF算法之前，先介紹幾個相關的概念，設D為數據對象集，p為D中的數據對象。

p的k距離：定義為對象p與離它第k近的對象q之間的距離，記為k-dist（p）。這樣的對象可能只有一個也可能有多個，若p與q之間的距離用d（p，q）表示，則對象q需要滿足的條件為：

①至少存在k個對象q'∈D-｛p｝，滿足d（p，q'）≤d （p，q）。

②至多存在k-1個對象q'∈D-｛p｝，滿足d（p，q'）≤d（p，q）。

p的k距離鄰域：是指所有與對象p的距離不大于k-dist（p）的數據對象的集合，即：

p與q的可達距離：指對象 p到對象 q的距離和q 的k距離兩者中的最大值，其中對象q∈Nk（p），即：

p的局部可達密度：定義為對象p與它的Nk（p）內各對象的平均可達距離的倒數，按式（3）計算：

局部異常因子（LOF）：表征數據對象p在k距離鄰域內的孤立（異常）程度，按式（4）計算：

LOF算法的實現步驟如下［6］：

①計算數據對象p的k距離k-dist（p）。

②計算p的k距離鄰域Nk（p）和可達距離。

③計算數據元素p的局部可達密度lrdk（p）。

④計算p的局部異常因子LOF。

LOF值越大，該對象越有可能就是孤立點，LOF值越小，該對象p越不可能是孤立點［7］。

LOF算法的缺點是計算復雜度大，根據以上LOF的計算過程，主要是由于第二步計算過程復雜。在p的k距離鄰域Nk（p）內，要計算該鄰域內每個對象的可達距離，包括在p的k距離鄰域Nk（p）計算所有對象的k-dist和p與每個鄰居對象之間的距離，每種情況下選出最大值。由于每個對象都至少有k個最近鄰數據對象，因此要得到所有對象的局部可達距離至少要做kn次比較，n越大的話，計算和比較的次數越大，時間就越長。為此，需要在鄰域查詢操作中進行優化［8］。

然而，孤立點只是整個數據集的一小部分，可以用DBSCAN算法進行預處理，去除不包含孤立點的類，以減少計算復雜度。

局部異常因子LOF［9］用于表征數據集中每個數據對象的異常程度，并且這種異常是局部的，與所求數據對象的鄰域分布有關。但是LOF算法并沒有將這一思想應用到計算局部異常因子的實際操作中。在LOF算法的鄰域查詢過程中，一個對象p的鄰域查詢信息僅僅用于處理對象自己，在該鄰域查詢結束后這些信息就被丟棄。實際操作中，這些信息對于Nk（p）中所有對象的鄰域查詢都是非常有用的，為了說明這點，以二維平面的數據點為例，假設參數k的取值為4，圓1和圓3以p為圓心，半徑分別為k-dist（p）和3×k-dist（p），圓2是以對象d為圓心，半徑為2×k-dist（p），如圖1所示。

圖1　鄰域優化查詢示意圖

圖1中，Nk（p）中至少包含4個對象，Nk（p）=｛a，b，c，d｝。按照LOF算法，獲得Nk（p）與相關的距離之后，對象p的鄰域查詢過程結束，應該選取另外一個點比如a再次進行鄰域查詢。實際上，對象a，b，c，d的鄰域查詢范圍只需要在圓3的區域內進行［10］，不必在整個數據集中查詢。不難想到，要對a進行鄰域查詢，目的是找到在a鄰域附近k個對象就可以，因為a在圓1中，而圓1中至少包含了k+1的對象（含p對象）。如果以a為圓心，2×k-dist（p）為半徑的范圍內已經包含圓1的區域了，這就可以確保該范圍內至少包含k+1個對象。考慮邊界對象的情況，可以確定以p為圓心，3×k-dist（p）為半徑構造出的圓3就是適合Nk（p）中所有對象的鄰域查詢范圍，而不必在整個數據集中進行查詢，顯著地減少了計算量。

優化后鄰域查詢步驟如下：

①從數據集中選擇一個尚未處理的對象p，在數據集D內進行查詢，獲得k-dist（p）、Nk（p）和所有其他對象與p之間的距離。

②在Nk（p）內選取與p的距離最小且沒有處理過的對象q，再以3×k-dist（p）為半徑的范圍內進行查詢。然后從與p的距離次小且沒有處理過的對象循環上述鄰域查詢過程，直到滿足查詢區域內對象數量超過指定閾值。

③若數據集中還有未處理的對象，則轉到①，繼續下一輪循環，否則，結束循環，優化查詢完成。

孤立點的數目比一般數據的數目要少很多，所以計算數據集中絕大多數非孤立點的LOF是低效的，為了提高效率，通過減少用于計算的數據集的大小來減少不必要的計算。DBSCAN算法具有聚類速度快、發現任意形狀類簇和有效處理噪聲的優點［11］，本文選取DBSCAN算法進行數據預處理。但是DBSCAN算法的聚類結果受參數ε和MinPts影響較大［12］，為了減少孤立點被聚到簇中的可能性，利用不同組參數ε和MinPts的設置得到聚類模型來過濾數據對象，然后集成得到結果：只有數據對象在每組參數ε和MinPts都被聚集到某個簇時，才認為該數據對象是被聚集的簇對象，否則被認為是初步異常數據集，將其加入到異常數據集中。預處理過程如圖2所示。

圖2　數據預處理過程

預處理的策略是：首先確定DBSCAN參數，例如MinPts的大小設置為數據集對象總數的5%左右，ε可以根據排序的k-dist圖確定。然后保持參數ε不變，以經驗參數MinPts為中心選取MinPts-i，類似地，保持MinPts不變，以ε為中心選取ε-j。預處理的過程如下

①DBSCAN算法通過檢查數據集中每個對象的ε鄰域來尋找聚類，鄰域查詢采用1.2節中的鄰域優化查詢算法，使用不同組參數（ε-i，MinPts-j）分別對數據進行聚類，其中i和j不同時為0。每組的聚類按照②和③進行。

②如果一個對象p的ε鄰域包含多余MinPts個對象，則創建以p為核心對象的新簇。反復尋找這些核心對象直接密度可達的對象，這一個過程可能會涉及到一些密度可達簇的合并。

③當沒有新的對象可以添加到任何簇時，則聚類算法結束。

④多組聚類結束后會得到多組簇，只有數據對象在每組參數下都被聚集到某個簇時，才認為該對象是被聚集的簇對象，否則就被認為是初步異常數據，將其加入到初步異常數據集中。

通過以上分析，本文對基于密度的孤立點檢測算法做了一些改進，基本思想是：首先通過DBSCAN算法對數據集進行預處理，處理過程中使用不同組參數來避免位于簇邊緣的孤立點錯剪（計算ε-鄰域的時候使用鄰域查詢優化算法），得到初步異常數據集。然后利用LOF算法中計算局部異常因子的方法計算初步異常數據集中數據的孤立程度。最后根據要求選出孤立程度最大的前n個數據點作為孤立點。

DBLOF算法的描述如下：

輸入：數據集D，參數k，ε，MinPts，n

輸出：數據集D的孤立點集合

①數據初始化。分類數據數值化，連續型數據離散化。

②數據預處理。在DBSCAN算法中，利用不同組ε和MinPts參數對數據集進行聚類，用鄰域查詢優化思想來查詢數據集中每個對象的ε-鄰域。當且僅當數據對象在每組參數下都被聚集時，才認為該對象是被聚集的簇對象，將其去除。否則認為是非簇對象，將其加入到初步異常數據集。

③在初步異常數據集中選擇一個沒有被處理過的對象。若MinPts＞k，則在ε-鄰域尋找該對象的k距離鄰域，否則在整個數據集中尋找k距離鄰域。

④計算各個數據點的局部可達密度和局部異常因子。

⑤輸出局部異常因子的最大的n個點，將其加入到孤立點集中。

2　實驗與分析

為了驗證本文提出的DBLOF算法在孤立點檢測中的有效性，將其與傳統的LOF孤立點檢測算法進行對比。

實驗環境為：Intel Pentium CPU主頻2.2GHz，內存2GB，操作系統為 Windows XP，工具為 MATLAB 7.12.0。

實驗所用的數據集為隨機生成的二維點集，該數據集包含148個數據點，其中有兩個簇集和6個明顯偏離簇的異常點。數據集的可視化顯示見圖3。

圖3　數據集和孤立點分布圖

為了更直觀的展示DBLOF算法和LOF算法的檢測結果，本文從兩個方面進行評價：

首先，為了衡量算法的檢測性能，使用精確度進行衡量。

其次，從實驗運行的時間上進行對比，以此證明DBLOF算法的計算復雜度更低。

實驗參數的設定：參數ε取值在0.4～0.6之間；因為k和MinPts都是表示數據點個數，且含義相近，所以參數k和MinPts的取值設為相同；又因為數據集中有6條真實的孤立點（孤立點的編號依次為51、101、102、 136、146、148），所以參數n從6開始選取，且每次加1，直到選取的前n個最大的孤立點中全部包含6條真實的孤立點。

實驗參數ε=0.6，k和MinPts均為4，實驗結果如圖4和圖5所示，從圖中看出要檢測出全部6個孤立點，LOF算法的n為11，DBLOF算法的n為7。具體的實驗結果見表1和表2。

圖4　LOF算法檢測結果

圖5　DBLOF算法檢測結果

根據圖4、圖5的檢測結果，DBLOF算法檢測的7個孤立點中包含了全部6個真實的孤立點，LOF算法檢測的11個孤立點中也包含了全部的6個孤立點。但是，對比兩張表可以看到，在檢測出最后一個編號為136的孤立點時，LOF算法是在第11個才檢測出來，DBLOF算法在第7個就可以檢測到。因此，DBLOF算法相比LOF算法只需要更短的計算過程，也就是說DBLOF算法比LOF算法降低了孤立點檢測的計算復雜度。從圖6的時間對比圖中，可以看出DBLOF算法的運行效率明顯優于LOF算法。

表1　LOF算法的檢測順序

表2　DBLOF算法的檢測順序

圖6　DBLOF和LOF運行時間對比圖

在精確度方面，如果n選擇為7的話，DBLOF算法的準確率為100%，LOF算法的準確率僅為67%（4/6），DBLOF算法的準確率比LOF算法的準確率要高。

3　結語

本文在基于密度的孤立點檢測LOF算法的基礎上提出了DBLOF算法。改進算法利用鄰域優化查詢方法降低鄰域查詢時計算復雜度，并且通過聚類DBSCAN算法對數據集進行預處理，得到初步異常數據集，使得孤立點的檢測對象更具有針對性。在采用二維點集的實驗中，改進算法取得了較好的檢測效果。但是在改進的算法中，參數k和MinPts的關系以及取值，直接影響到臨近點的查詢范圍。因此，下一步將研究參數之間的關系對運行時間和精確度的影響，期望找出自動提供合理參數的方法。

［1］Dantong Yu，Gholamhosein Sheikholeslami，Aidong Zhang.FindOut：Finding Outliers in Very Large Datasets［J］.Knowledge and Information Systems，2002（4）

［2］范潔.數據挖掘中孤立點檢測算法的研究［D］.中南大學，2009.

［3］Dutta H，Giannella C，Borne K，et al.Distributed top-k Outlier Detection in Astronomy Catalogs Using the Demac System［C］.Proc of 7th SIAM International Conference on Data Mining，2007.

［4］胡彩平，秦小麟.一種基于密度的局部離群點檢測算法DLOF［J］.計算機研究與發展，2010，12：2110-2116.

［5］姜晗，賈泂.基于聚類的孤立點檢測算法［J］.計算機與現代化，2007，11：37-39.

［6］張衛旭，尉宇.基于密度的局部離群點檢測算法［J］.計算機與數字程，2010，10：11-14.

［7］鄢團軍，劉勇.孤立點檢測算法與應用［J］.三峽大學學報（自然科學版），2009，01：98-103.

［8］劉大任，孫煥良，牛志成等.一種新的基于密度的聚類與孤立點檢測算法［J］.沈陽建筑大學學報（自然科學版），2006，01：149-153.

［9］李健，閻保平，李俊.基于記憶效應的局部異常檢測算法［J］.計算機工程，2008，34（12）：4-6.

［10］李健，閻保平，李俊.MELOF算法的理論分析與拓展［J］.計算機工程，2009，19：94-96

［11］馮少榮，肖文俊.基于密度的DBSCAN聚類算法的研究及應用［J］.計算機工程與應用，2007，43（20）：216-221.

［12］馮少榮，肖文俊.DBSCAN聚類算法的研究與改進［J］.中國礦業大學學報，2008，01：105-111.

Outlier Detection；LOF；DBSCAN；Clustering；Data Mining

Improvement of Detection Algorithm Density-Based Local Outlier

LV Ben，GAO Mao-ting
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

國家自然科學基金項目（No.61202022）、上海海事大學科研項目

1007-1423（2015）17-0062-06

10.3969/j.issn.1007-1423.2015.17.014

呂奔（1989-），男，江蘇徐州人，碩士研究生，研究方向為為數據挖掘

2015-04-27

2015-06-25

針對基于密度的孤立點檢測算法LOF時間復雜度高的問題，通過優化數據對象鄰域查詢過程，提出一種兩階段的改進算法DBLOF，先采用DBSCAN聚類算法對數據集進行預處理，去除大部分的非孤立點，得到可能異常數據集，然后再利用LOF算法計算可能異常數據集中對象的局部異常因子并以此找出真正的孤立點。實驗結果表明，改進算法能實現有效的局部孤立點檢測，并能夠降低算法時間復雜度。

孤立點檢測；LOF；DBSCAN；聚類；數據挖掘

高茂庭（1963-），男，江西九江人，博士，教授，系統分析員，CCF高級會員，研究方向為智能信息處理、數據庫與信息系統

For the high time complexity of the density-based outlier detecting algorithm（LOF algorithms），proposes an improved algorithm DBLOF with two-stage by optimizing the neighborhood query operation of adjacent objects for each data object.Firstly，clustering algorithm DBSCAN is taken to preprocess the dataset and remove the most of the non-outliers data objects to get the dataset of all possible outliers. Then，the local outlier factors are calculated on the possible outliers dataset for each data object to find out the real outliers.The experiments demonstrate that the proposed algorithm can realize the effective local outlier detection and reduce the time complexity of the algorithm.