呂奔，高茂庭

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

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

呂奔，高茂庭

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

0　引言

孤立點檢測是數(shù)據(jù)挖掘領(lǐng)域的一個重要分支，在數(shù)據(jù)集中，孤立點數(shù)據(jù)通常被定義為與其他數(shù)據(jù)對象有著明顯差異的數(shù)據(jù)。Hawkins在20世紀80年代給出了一個比較接近孤立點本質(zhì)的定義［1］：“孤立點與其他點如此不同，以至于讓人們懷疑它是由另一個不同的機制產(chǎn)生的?！惫铝Ⅻc檢測在實際生活中有很多重要的應(yīng)用，如網(wǎng)絡(luò)入侵檢測、金融欺詐檢測、運動員比賽分析、醫(yī)學領(lǐng)域中發(fā)現(xiàn)病人對新的治療方案的異常反應(yīng)等［2］。

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

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

1　DBLOF算法

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

為使表達更清楚，在介紹LOF算法之前，先介紹幾個相關(guān)的概念，設(shè)D為數(shù)據(jù)對象集，p為D中的數(shù)據(jù)對象。

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）的數(shù)據(jù)對象的集合，即：

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

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

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

LOF算法的實現(xiàn)步驟如下［6］：

①計算數(shù)據(jù)對象p的k距離k-dist（p）。

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

③計算數(shù)據(jù)元素p的局部可達密度lrdk（p）。

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

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

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

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

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

圖1　鄰域優(yōu)化查詢示意圖

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

優(yōu)化后鄰域查詢步驟如下：

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

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

③若數(shù)據(jù)集中還有未處理的對象，則轉(zhuǎn)到①，繼續(xù)下一輪循環(huán)，否則，結(jié)束循環(huán)，優(yōu)化查詢完成。

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

圖2　數(shù)據(jù)預(yù)處理過程

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

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

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

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

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

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

DBLOF算法的描述如下：

輸入：數(shù)據(jù)集D，參數(shù)k，ε，MinPts，n

輸出：數(shù)據(jù)集D的孤立點集合

①數(shù)據(jù)初始化。分類數(shù)據(jù)數(shù)值化，連續(xù)型數(shù)據(jù)離散化。

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

③在初步異常數(shù)據(jù)集中選擇一個沒有被處理過的對象。若MinPts＞k，則在ε-鄰域?qū)ふ以搶ο蟮膋距離鄰域，否則在整個數(shù)據(jù)集中尋找k距離鄰域。

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

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

2　實驗與分析

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

實驗環(huán)境為：Intel Pentium CPU主頻2.2GHz，內(nèi)存2GB，操作系統(tǒng)為 Windows XP，工具為 MATLAB 7.12.0。

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

圖3　數(shù)據(jù)集和孤立點分布圖

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

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

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

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

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

圖4　LOF算法檢測結(jié)果

圖5　DBLOF算法檢測結(jié)果

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

表1　LOF算法的檢測順序

表2　DBLOF算法的檢測順序

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

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

3　結(jié)語

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

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

［2］范潔.數(shù)據(jù)挖掘中孤立點檢測算法的研究［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］.計算機研究與發(fā)展，2010，12：2110-2116.

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

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

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

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

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

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

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

［12］馮少榮，肖文俊.DBSCAN聚類算法的研究與改進［J］.中國礦業(yè)大學學報，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-），男，江蘇徐州人，碩士研究生，研究方向為為數(shù)據(jù)挖掘

2015-04-27

2015-06-25

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

孤立點檢測；LOF；DBSCAN；聚類；數(shù)據(jù)挖掘

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

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.