基于密度的孤立點(diǎn)檢測(cè)算法改進(jìn)研究

呂奔，高茂庭

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

基于密度的孤立點(diǎn)檢測(cè)算法改進(jìn)研究

呂奔，高茂庭

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0　引言

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

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

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

1　DBLOF算法

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

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

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

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

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

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

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

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

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

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

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

②計(jì)算p的k距離鄰域Nk（p）和可達(dá)距離。

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

④計(jì)算p的局部異常因子LOF。

LOF值越大，該對(duì)象越有可能就是孤立點(diǎn)，LOF值越小，該對(duì)象p越不可能是孤立點(diǎn)［7］。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

③當(dāng)沒(méi)有新的對(duì)象可以添加到任何簇時(shí)，則聚類算法結(jié)束。

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

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

DBLOF算法的描述如下：

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

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

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

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

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

④計(jì)算各個(gè)數(shù)據(jù)點(diǎn)的局部可達(dá)密度和局部異常因子。

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

2　實(shí)驗(yàn)與分析

為了驗(yàn)證本文提出的DBLOF算法在孤立點(diǎn)檢測(cè)中的有效性，將其與傳統(tǒng)的LOF孤立點(diǎn)檢測(cè)算法進(jìn)行對(duì)比。

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

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

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

為了更直觀的展示DBLOF算法和LOF算法的檢測(cè)結(jié)果，本文從兩個(gè)方面進(jìn)行評(píng)價(jià)：

首先，為了衡量算法的檢測(cè)性能，使用精確度進(jìn)行衡量。

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

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

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

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

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

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

表1　LOF算法的檢測(cè)順序

表2　DBLOF算法的檢測(cè)順序

圖6　DBLOF和LOF運(yùn)行時(shí)間對(duì)比圖

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

3　結(jié)語(yǔ)

本文在基于密度的孤立點(diǎn)檢測(cè)LOF算法的基礎(chǔ)上提出了DBLOF算法。改進(jìn)算法利用鄰域優(yōu)化查詢方法降低鄰域查詢時(shí)計(jì)算復(fù)雜度，并且通過(guò)聚類DBSCAN算法對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，得到初步異常數(shù)據(jù)集，使得孤立點(diǎn)的檢測(cè)對(duì)象更具有針對(duì)性。在采用二維點(diǎn)集的實(shí)驗(yàn)中，改進(jìn)算法取得了較好的檢測(cè)效果。但是在改進(jìn)的算法中，參數(shù)k和MinPts的關(guān)系以及取值，直接影響到臨近點(diǎn)的查詢范圍。因此，下一步將研究參數(shù)之間的關(guān)系對(duì)運(yùn)行時(shí)間和精確度的影響，期望找出自動(dòng)提供合理參數(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ù)挖掘中孤立點(diǎn)檢測(cè)算法的研究［D］.中南大學(xué)，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］胡彩平，秦小麟.一種基于密度的局部離群點(diǎn)檢測(cè)算法DLOF［J］.計(jì)算機(jī)研究與發(fā)展，2010，12：2110-2116.

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

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

［7］鄢團(tuán)軍，劉勇.孤立點(diǎn)檢測(cè)算法與應(yīng)用［J］.三峽大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，01：98-103.

［8］劉大任，孫煥良，牛志成等.一種新的基于密度的聚類與孤立點(diǎn)檢測(cè)算法［J］.沈陽(yáng)建筑大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，01：149-153.

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

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

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

［12］馮少榮，肖文俊.DBSCAN聚類算法的研究與改進(jìn)［J］.中國(guó)礦業(yè)大學(xué)學(xué)報(bào)，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）

國(guó)家自然科學(xué)基金項(xiàng)目（No.61202022）、上海海事大學(xué)科研項(xiàng)目

1007-1423（2015）17-0062-06

10.3969/j.issn.1007-1423.2015.17.014

呂奔（1989-），男，江蘇徐州人，碩士研究生，研究方向?yàn)闉閿?shù)據(jù)挖掘

2015-04-27

2015-06-25

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

孤立點(diǎn)檢測(cè)；LOF；DBSCAN；聚類；數(shù)據(jù)挖掘

高茂庭（1963-），男，江西九江人，博士，教授，系統(tǒng)分析員，CCF高級(jí)會(huì)員，研究方向?yàn)橹悄苄畔⑻幚?、?shù)據(jù)庫(kù)與信息系統(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.