鄒云峰,張 昕,宋世淵,倪巍偉

(1.國(guó)網(wǎng)江蘇省電力公司 電力科學(xué)研究院,南京 210036; 2.東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,南京 211189) (*通信作者電子郵箱2293515844@qq.com)

基于局部密度的快速離群點(diǎn)檢測(cè)算法

鄒云峰1,張 昕1,宋世淵2*,倪巍偉2

(1.國(guó)網(wǎng)江蘇省電力公司 電力科學(xué)研究院,南京 210036; 2.東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,南京 211189) (*通信作者電子郵箱2293515844@qq.com)

已有的密度離群點(diǎn)檢測(cè)算法LOF不能適應(yīng)數(shù)據(jù)分布異常情況離群點(diǎn)檢測(cè)，INFLO算法雖引入反向k近鄰點(diǎn)集有效地解決了數(shù)據(jù)分布異常情況的離群點(diǎn)檢測(cè)問(wèn)題，但存在需要對(duì)所有數(shù)據(jù)點(diǎn)不加區(qū)分地分析其k近鄰和反向k近鄰點(diǎn)集導(dǎo)致的效率降低問(wèn)題。針對(duì)該問(wèn)題，提出局部密度離群點(diǎn)檢測(cè)算法——LDBO，引入強(qiáng)k近鄰點(diǎn)和弱k近鄰點(diǎn)概念，通過(guò)分析鄰近數(shù)據(jù)點(diǎn)的離群相關(guān)性，對(duì)數(shù)據(jù)點(diǎn)區(qū)別對(duì)待；并提出數(shù)據(jù)點(diǎn)離群性預(yù)判斷策略，盡可能避免不必要的反向k近鄰分析，有效提高數(shù)據(jù)分布異常情況離群點(diǎn)檢測(cè)算法的效率。理論分析和實(shí)驗(yàn)結(jié)果表明，LDBO算法效率優(yōu)于INFLO，算法是有效可行的。

離群點(diǎn)檢測(cè);局部密度;強(qiáng)k近鄰點(diǎn);弱k近鄰點(diǎn);反向k近鄰點(diǎn)集

0 引言

離群點(diǎn)檢測(cè)(Outlier Detection)作為數(shù)據(jù)挖掘技術(shù)的重要研究領(lǐng)域之一,是從大量事物中發(fā)現(xiàn)少量與多數(shù)事物具有明顯區(qū)別的異常個(gè)體的過(guò)程[1]。離群點(diǎn)檢測(cè)在很多領(lǐng)域有著廣泛的應(yīng)用前景，例如,電子商務(wù)中的欺詐行為、金融領(lǐng)域中信用卡惡意透支、網(wǎng)絡(luò)安全中的惡意攻擊、地震預(yù)報(bào)中的異常波形、網(wǎng)絡(luò)入侵抵御等。

離群點(diǎn)檢測(cè)技術(shù)由于其獨(dú)特的知識(shí)發(fā)現(xiàn)功能而得到了較深入的研究。近年來(lái)提出了一系列檢測(cè)方法,Johnson等[2]提出基于深度的算法, Knorr等[3]提出基于距離的算法FindAllOutsD,Breunig等[4]提出帶離群度的離群點(diǎn)檢測(cè)算法LOF(Local Outlier Factor),Papadimitirou等[5-13]提出LOCI(LOcal Correlation Integral)算法等。局部離群點(diǎn)檢測(cè)是離群點(diǎn)檢測(cè)的一個(gè)重要研究方向,文獻(xiàn)[11]針對(duì)LOF算法的不足,提出了基于反向k近鄰(ReversekNearest Neighbors, RkNN)的局部離群度判別方法INFLO(INFLuenced Outlierness),不同于LOF算法只考慮數(shù)據(jù)點(diǎn)的k近鄰,算法同時(shí)考慮數(shù)據(jù)點(diǎn)的反向k近鄰對(duì)數(shù)據(jù)點(diǎn)離群度的影響,從而避免數(shù)據(jù)分布異常情況下LOF算法可能出現(xiàn)的錯(cuò)判。例如,圖1中,根據(jù)LOF算法對(duì)數(shù)據(jù)點(diǎn)離群度的定義,可能出現(xiàn)屬于聚類C2的數(shù)據(jù)點(diǎn)p的離群度高于數(shù)據(jù)點(diǎn)q和r的離群度,出現(xiàn)p比數(shù)據(jù)點(diǎn)q和r更易被判定為離群點(diǎn)的錯(cuò)判現(xiàn)象。采用INFLO方法后,在分析p、q、r的k近鄰(k-Nearest Neighbors, KNN) 的同時(shí),進(jìn)一步分析各個(gè)數(shù)據(jù)點(diǎn)反向k近鄰。INFLO方法結(jié)合數(shù)據(jù)點(diǎn)p的反向k近鄰數(shù)據(jù)點(diǎn)對(duì)p的影響,可以得出p的離群度小于q和r的離群度的正確結(jié)果。

INFLO方法可以解決LOF算法不適應(yīng)數(shù)據(jù)分布異常情況下離群點(diǎn)判定的缺陷,但仍然存在以下不足:

1)算法既要查詢生成每個(gè)數(shù)據(jù)點(diǎn)p的k近鄰,又要查詢p的反向k近鄰(RkNN),頻繁的RkNN查詢對(duì)算法的性能影響很大,盡管文獻(xiàn)[11]中采用R樹等索引結(jié)構(gòu)來(lái)提高查詢效率,但并不能從根本上解決效率問(wèn)題；另一方面,當(dāng)數(shù)據(jù)集維度較高時(shí),R樹等索引結(jié)構(gòu)的效率比順序遍歷查詢還要差,也無(wú)法實(shí)現(xiàn)其提高效率的目的。

2)算法需要對(duì)每一個(gè)數(shù)據(jù)點(diǎn)的離群度進(jìn)行分析計(jì)算,判斷其是否可能是離群點(diǎn),導(dǎo)致時(shí)間開銷很大,大量反向k近鄰查詢加劇了這種負(fù)擔(dān);實(shí)際數(shù)據(jù)集中,異常分布點(diǎn)僅占數(shù)據(jù)集的很小部分,例如圖1中,只有聚類C1和C2的邊緣點(diǎn),以及諸如q和r這樣的數(shù)據(jù)點(diǎn)分布異常,對(duì)數(shù)據(jù)集中的大多數(shù)數(shù)據(jù)點(diǎn)(C1和C2中的數(shù)據(jù)點(diǎn))無(wú)需分析其RkNN,就可以得出正確的離群判斷。

針對(duì)上述問(wèn)題,本文提出一種基于局部密度的快速離群點(diǎn)檢測(cè)方法LDBO(Local Density Based Outlier detection),算法無(wú)需對(duì)數(shù)據(jù)集中所有數(shù)據(jù)點(diǎn)進(jìn)行離群與否分析,在僅需對(duì)部分?jǐn)?shù)據(jù)點(diǎn)計(jì)算反向k近鄰的情況下,有效地解決數(shù)據(jù)分布異常環(huán)境下離群點(diǎn)檢測(cè)問(wèn)題。

圖1 數(shù)局分布異常情況

圖2 反向k近鄰分析實(shí)例

1 相關(guān)工作

1.1 LOF算法

基于密度的離群點(diǎn)檢測(cè)算法LOF[4],提出基于密度的數(shù)據(jù)點(diǎn)離群度計(jì)算方法,主要定義如下:

定義1[4]ε-鄰域和數(shù)據(jù)點(diǎn)p的k-距離。p為數(shù)據(jù)集D中數(shù)據(jù)點(diǎn),ε為距離參數(shù)值,k為自然數(shù),d為歐氏距離函數(shù):

1)p的ε-鄰域Nε(p)={x∈D|d(p,x)≤ε}。

2)數(shù)據(jù)點(diǎn)p的k-距離k-dist(p)定義為p與距其第k近的數(shù)據(jù)點(diǎn)的距離,p的k-鄰域簡(jiǎn)寫為Nk(p),Nk(p)={x∈D|d(p,x)≤k-dist(p)}。

ε-鄰域用于確定數(shù)據(jù)點(diǎn)的密度特征比較范圍,即每個(gè)數(shù)據(jù)點(diǎn)的密度特征與其ε-鄰域內(nèi)的數(shù)據(jù)點(diǎn)比較。

定義2[4]p的核心距離。p為數(shù)據(jù)集D中數(shù)據(jù)點(diǎn),ε為距離參數(shù)值,MinPts為給定自然數(shù),p的核心距離定義如下：

core-distanceε,MinPts(p)=

即當(dāng)p的ε-鄰域內(nèi)數(shù)據(jù)點(diǎn)數(shù)目大于MinPts時(shí),p的核心距離定義為p的MinPts-距離。

定義3[4]p關(guān)于o的可達(dá)距離。p與o為D中數(shù)據(jù)點(diǎn),p∈Nε(o),則p關(guān)于o的可達(dá)距離定義為:

reachability-distanceε,MinPts(p,o)=

定義4[4]p的局部可達(dá)密度。p為D中數(shù)據(jù)點(diǎn),參數(shù)定義如上,p的局部可達(dá)密度定義為:

lrdMinPts(p)=

p的局部可達(dá)密度表征了p的局部密度,值越大,p所代表的局部區(qū)域越稠密。

定義5[4]p的離群因子。p為D中數(shù)據(jù)點(diǎn),p的離群因子定義如下:

p的離群因子定義為p的k-鄰域內(nèi)數(shù)據(jù)點(diǎn)與p點(diǎn)局部可達(dá)密度的平均比值,數(shù)據(jù)點(diǎn)的離群因子值越高,說(shuō)明p點(diǎn)與其鄰域內(nèi)數(shù)據(jù)點(diǎn)密度特征差異越顯著,其成為離群點(diǎn)的可能性也就越大。

分析圖1中p、q、r的數(shù)據(jù)分布特征發(fā)現(xiàn),由于q較p更靠近聚類C1,因而q的局部密度高于p,而p與q的k近鄰點(diǎn)集均由分布均勻的C1中數(shù)據(jù)點(diǎn)構(gòu)成,得出p的離群因子高于q的錯(cuò)誤判斷;對(duì)r與p也可進(jìn)行類似分析,發(fā)現(xiàn)LOF方法對(duì)數(shù)據(jù)分布異常情況下數(shù)據(jù)點(diǎn)的離群因子確實(shí)存在錯(cuò)判的可能。

1.2 INFLO算法

在LOF方法的基礎(chǔ)上,文獻(xiàn)[11]提出了新的判定數(shù)據(jù)點(diǎn)離群因子的方法,相關(guān)定義如下:

定義6[11]p的反向k近鄰。p的反向k近鄰定義如下:RNNk(p)={q|q∈D,p∈NNk(q)}。

定義7[11]p的局部密度。den(p)=1/k-dist(p)。

定義8[11]p的離群影響因子INFLOk(p)。p的離群影響因子INFLOk(p)定義如下:

其中：

ISk(p)=NNk(p)∪RNNk(p)

相對(duì)于LOF算法,INFLO算法既考慮數(shù)據(jù)點(diǎn)的k近鄰,又兼顧數(shù)據(jù)點(diǎn)的反向k近鄰,可以更好地表征數(shù)據(jù)點(diǎn)所在區(qū)域的密度特征。

重新分析圖2所示數(shù)據(jù)分布異常的情況可以發(fā)現(xiàn),考慮了反向k近鄰后,p的離群因子明顯小于q與r的離群因子,符合數(shù)據(jù)實(shí)際分布情況。

2 離群點(diǎn)檢測(cè)算法LDBO

2.1 算法思想

盡管INFLO算法通過(guò)引入反向k近鄰有效地解決了數(shù)據(jù)分布異常情況下的離群點(diǎn)檢測(cè)問(wèn)題。但對(duì)每個(gè)數(shù)據(jù)點(diǎn)計(jì)算反向k近鄰使得算法的時(shí)間消耗激增?？紤]現(xiàn)實(shí)世界,分布異常的數(shù)據(jù)通常只占數(shù)據(jù)集的一小部分,大多數(shù)數(shù)據(jù)點(diǎn)都屬于正常模式(非離群點(diǎn)),大量數(shù)據(jù)點(diǎn)無(wú)需反向k近鄰計(jì)算即可進(jìn)行離群判別。

因此,考慮基于INFLO算法,從數(shù)據(jù)點(diǎn)密度特征角度研究數(shù)據(jù)點(diǎn)與其鄰域內(nèi)數(shù)據(jù)的離群關(guān)系,設(shè)計(jì)判斷策略,在不影響INFLO算法判段正確性的前提下,盡可能減少需進(jìn)行反向k近鄰分析的數(shù)據(jù)點(diǎn)規(guī)模,提升離群分析效率。

2.2 局部密度聚類與離群判定

聚類分析和離群點(diǎn)檢測(cè)有著密切聯(lián)系, LOF算法和INFLO算法均借助密度聚類的重要概念k近鄰距離來(lái)衡量數(shù)據(jù)集中各個(gè)數(shù)據(jù)點(diǎn)是否為離群點(diǎn)。而實(shí)際數(shù)據(jù)集中離群點(diǎn)所占的比例很小,占數(shù)據(jù)集主體的各個(gè)聚簇內(nèi)的大多數(shù)數(shù)據(jù)點(diǎn)都不屬于離群點(diǎn),但是為了避免離群點(diǎn)檢測(cè)中“拒真”(false negative)現(xiàn)象的出現(xiàn)(即漏判聚簇內(nèi)部可能存在的離群點(diǎn)),LOF算法和INFLO算法都要對(duì)各個(gè)聚簇內(nèi)部的數(shù)據(jù)點(diǎn)進(jìn)行逐一判斷,嚴(yán)重影響了基于密度的離群點(diǎn)檢測(cè)算法效率。

為了解決這一問(wèn)題,引入下述定義:

定義9 核心影響點(diǎn)集(Kernel Infection Set, KIS)。p為數(shù)據(jù)集D中數(shù)據(jù)點(diǎn),p的核心影響點(diǎn)集稱KISk(p)={o|o∈NNk(p)∧p∈NNk(o)}。

由定義可知,若p為強(qiáng)k近鄰點(diǎn),意味著p的k近鄰內(nèi)至少占比不小于μ的數(shù)據(jù)點(diǎn)的k近鄰也包含p,即p的k近鄰內(nèi)有較大比例μ的數(shù)據(jù)點(diǎn)周圍區(qū)域的密度分布趨于p周圍數(shù)據(jù)密度分布。滿足μgt;0,則圖1中的p、q、r點(diǎn)不可能為強(qiáng)k近鄰點(diǎn)。

定義11 局部核心點(diǎn)。若p∈D,且

稱p為局部核心點(diǎn)。p的k近鄰距離不大于其k近鄰內(nèi)數(shù)據(jù)點(diǎn)k近鄰距離的均值,說(shuō)明p的k近鄰內(nèi)數(shù)據(jù)點(diǎn)總體上向p收斂,p的局部密度高于其k近鄰數(shù)據(jù)點(diǎn)的平均密度。

性質(zhì)1 若p為局部核心點(diǎn),p一定不是離群點(diǎn)。

證明 從局部密度聚類角度考慮,p的k近鄰距離不大于其k近鄰內(nèi)數(shù)據(jù)點(diǎn)k近鄰距離的均值,說(shuō)明p鄰域內(nèi)數(shù)據(jù)點(diǎn)總體上向p聚集,p對(duì)應(yīng)聚簇的核心點(diǎn),以p為起點(diǎn)遍歷其密度相連數(shù)據(jù)點(diǎn),可以生成一個(gè)聚簇;同時(shí),p鄰域內(nèi)不可能出現(xiàn)類似圖1的數(shù)據(jù)分布異常現(xiàn)象,無(wú)需考慮其反向k近鄰數(shù)據(jù)點(diǎn)的形象,根據(jù)LOF算法離群因子定義和局部核心點(diǎn)的定義易得p的離群因子小于1。從這兩方面分析,p都不符合離群點(diǎn)的特征,p不是離群點(diǎn)。

證畢。

性質(zhì)2p為局部核心點(diǎn),且p為強(qiáng)k近鄰點(diǎn),若q∈KISk(p),且k-dist(q)≤k-dist(p),則q也是局部核心點(diǎn)。

證明 由性質(zhì)1,p為局部核心點(diǎn)不是離群點(diǎn),有如下關(guān)系:

(1)

數(shù)據(jù)點(diǎn)q的k近鄰內(nèi)點(diǎn)的k近鄰距離均值為:

由式(1)有:

avg(q)≥

由于k-dist(q)≤k-dist(p),有

對(duì)分子部分的兩個(gè)求和表達(dá)式進(jìn)行分析,對(duì)o∈KISk(p),即同時(shí)屬于點(diǎn)q和點(diǎn)p的k近鄰點(diǎn)集的數(shù)據(jù)點(diǎn)。分析可知,這類數(shù)據(jù)點(diǎn)的數(shù)目很少,因?yàn)樵趒的k近鄰內(nèi),p不可能與q很靠近,這些點(diǎn)又位于q的k近鄰內(nèi),將導(dǎo)致p的k近鄰點(diǎn)集中較多的數(shù)據(jù)點(diǎn)位于以p、q連線為直徑方向的球狀區(qū)域(如圖3中r1和r2)。而題設(shè)中有p為強(qiáng)k近鄰點(diǎn),故而可知p的k近鄰內(nèi)數(shù)據(jù)點(diǎn)總體上密度分布與p相近;且k-dist(p)小于其k近鄰內(nèi)數(shù)據(jù)點(diǎn)k近鄰距離均值,若p的k近鄰點(diǎn)集內(nèi)較多數(shù)據(jù)點(diǎn)位于q的k近鄰點(diǎn)集,將很難同時(shí)滿足這兩點(diǎn)。有進(jìn)一步分析可知,即便p的k近鄰內(nèi)有極少的數(shù)據(jù)點(diǎn)o在q的k近鄰內(nèi),k-dist(o)≤dist(o,q)+k-dist(q)。例如圖示k=5時(shí),有2個(gè)數(shù)據(jù)點(diǎn)屬于KISk(p),同時(shí)p為強(qiáng)k近鄰點(diǎn),則p顯然不滿足局部核心點(diǎn)的條件。

圖3 數(shù)據(jù)分布示意圖

對(duì)于滿足o?NNk(p)∧o∈NNk(q)條件的這類數(shù)據(jù)點(diǎn)一定存在,否則p的k近鄰點(diǎn)集中的部分?jǐn)?shù)據(jù)點(diǎn)和p點(diǎn)將構(gòu)成q的k近鄰點(diǎn)集,這將導(dǎo)致p為局部核心點(diǎn)和p為強(qiáng)k近鄰點(diǎn)兩個(gè)條件的無(wú)法同時(shí)滿足;并且這類數(shù)據(jù)點(diǎn)與可能存在的o∈NNk(p)∧o∈NNk(q)的數(shù)據(jù)點(diǎn)同屬q的k近鄰,其k近鄰距離相近。

通過(guò)上述分析可知,

ηgt;0

q為局部核心點(diǎn)。

證畢。

引入局部離群度定義如下:

定義12 局部離群因子(LOCal Outlierness, LOCO)。若p∈D,0lt;μ≤1,p的局部離群因子為L(zhǎng)OCOk(p)。

通過(guò)引入強(qiáng)k近鄰點(diǎn)和弱k近鄰點(diǎn),若p為強(qiáng)k近鄰點(diǎn),由強(qiáng)近鄰點(diǎn)定義知,此時(shí)p的鄰域內(nèi)不可能出現(xiàn)類似圖1的數(shù)據(jù)分布異常情況,故而無(wú)需考慮p的反向k近鄰內(nèi)點(diǎn)對(duì)p離群判斷的影響;若p為弱k近鄰點(diǎn),則p的鄰域內(nèi)可能存在數(shù)據(jù)分布異?，F(xiàn)象,此時(shí)對(duì)p的離群性判定需進(jìn)一步考慮其反向k近鄰的影響。

2.3 數(shù)據(jù)點(diǎn)離群判斷策略

根據(jù)定義10,將數(shù)據(jù)點(diǎn)劃分成兩類——強(qiáng)k近鄰點(diǎn)集和弱k近鄰點(diǎn)集。若p為強(qiáng)k近鄰點(diǎn),說(shuō)明p的k近鄰內(nèi)一定數(shù)量的數(shù)據(jù)與p的數(shù)據(jù)分布相近,不存在圖1所示異常的情況;否則,說(shuō)明p的k近鄰內(nèi)數(shù)據(jù)點(diǎn)可能存在分布異常的情況,容易驗(yàn)證圖1中的p、q、r顯然屬于弱k近鄰點(diǎn)。對(duì)這兩類數(shù)據(jù)點(diǎn),分別采用不同的策略進(jìn)行處理。

1)強(qiáng)k近鄰點(diǎn)的離群判別。

若p為強(qiáng)k近鄰點(diǎn),說(shuō)明其k近鄰內(nèi)超過(guò)100×μ%(0.5≤μ≤1)的數(shù)據(jù)分布與p相近,不存在數(shù)據(jù)分布異常情況,對(duì)p的離群判斷,不需要考慮其反向k近鄰的影響。

進(jìn)一步判斷p是否為局部核心點(diǎn),若p不是局部核心點(diǎn),則LOCOk(p)gt;1,可能為離群點(diǎn),若LOCOk(p)gt;t(假設(shè)t為所設(shè)離群因子閾值),則p為離群點(diǎn);若p為局部核心點(diǎn),由性質(zhì)1得p不是離群點(diǎn),進(jìn)一步分析其k近鄰內(nèi)數(shù)據(jù)點(diǎn)。

若p為局部核心點(diǎn),可以將p的k近鄰內(nèi)數(shù)據(jù)點(diǎn)分為三類:

①o∈NNk(p)-KISk(p)。

這一類數(shù)據(jù)點(diǎn)的k近鄰不包含p,對(duì)應(yīng)局部密度高于p的區(qū)域,從密度聚類角度分析,與p可能屬于同一聚簇也可能屬于不同聚簇,其離群性與p沒(méi)有直接關(guān)系,盡管其局部密度高于非離群點(diǎn)p的局部密度,但并不意味這類數(shù)據(jù)點(diǎn)一定都不是離群點(diǎn),仍需進(jìn)一步分析其局部k近鄰內(nèi)數(shù)據(jù)分布情況以判斷這類數(shù)據(jù)點(diǎn)是否為離群點(diǎn)。

②o∈KISk(p),且k-dist(o)≤k-dist(p)。

由性質(zhì)1和性質(zhì)2,o不是離群點(diǎn)。

③o∈KISk(p),且k-dist(o)gt;k-dist(p)。

這類數(shù)據(jù)點(diǎn)同樣屬于p的強(qiáng)影響點(diǎn)集,與情況②的區(qū)別是這些點(diǎn)可能不是局部核心點(diǎn),因而有成為離群點(diǎn)的可能,必須進(jìn)一步分析其k近鄰數(shù)據(jù)點(diǎn)的分布情況,以確定是否為離群點(diǎn)。從而,當(dāng)判斷出強(qiáng)k近鄰點(diǎn)p非離群點(diǎn)的同時(shí),可以根據(jù)性質(zhì)2將p的k近鄰點(diǎn)集中k近鄰距離小于等于p的點(diǎn)標(biāo)注為非離群點(diǎn)。

2)弱k近鄰點(diǎn)的離群判別。

這樣,通過(guò)強(qiáng)k近鄰點(diǎn)與弱k近鄰點(diǎn)的定義,可以將數(shù)據(jù)集中數(shù)據(jù)點(diǎn)劃分為無(wú)需考慮反向k近鄰直接進(jìn)行離群判斷和需要考慮反向k近鄰進(jìn)行離群判斷兩類。數(shù)據(jù)集中的絕大多數(shù)數(shù)據(jù)點(diǎn)屬于前者,從而無(wú)需對(duì)每個(gè)數(shù)據(jù)點(diǎn)分析計(jì)算其反向k近鄰數(shù)據(jù)點(diǎn)的影響,避免了頻繁分析計(jì)算反向k近鄰對(duì)算法效率的影響;另一方面,對(duì)占數(shù)據(jù)集比重較大的強(qiáng)k近鄰點(diǎn),通過(guò)性質(zhì)2,可以對(duì)其k近鄰內(nèi)的部分待判定數(shù)據(jù)點(diǎn)進(jìn)行預(yù)判斷,減少待判定數(shù)據(jù)點(diǎn)的數(shù)量,提高離群點(diǎn)檢測(cè)算法的效率。

2.4 LDBO算法

算法 LDBO。

輸入 維數(shù)據(jù)集D、k; 離群因子閾值t。

輸出 數(shù)據(jù)集D的離群點(diǎn)集合Outlier。

Initialization;

For eachxinD{

If (xnot be marked as outlier or non-outlier){

GenNNK(x,D,k);

L=NNk(x);

For (i=1;i≤|L|;i++){

Generate(L[i],D,k);

Ifx∈NNk(L[i]){insertL[i] intoKISk(x)}

}

If (|KISk(x)|/NNk(x)≥μ){

//x為強(qiáng)k近鄰點(diǎn)

GenMKDist(L,D,k);

//計(jì)算x的鄰域點(diǎn)k-Dist均值

If (xis local core){

xis marked as non-outlier;

For (i=1;i≤|L|;i++){

If (k-Dist(L[i])≤k-Dist(x))

xis marked as non-outlier;

}

}

else

{ If (LOCOk(x)≤t)xis marked as non-outlier;

Else {xis marked an outlier;}

}

}

else

//x為弱k近鄰點(diǎn)

{ generateRNNk(x);

If (LOCOk(x)gt;t){xis marked an outlier;}

Else{xis marked as non-outlier;}

}

}

}

3 實(shí)驗(yàn)分析

本章對(duì)所提出的LDBO算法進(jìn)行性能測(cè)試。考慮LDBO算法主要基于INFLO算法[11]進(jìn)行改進(jìn),在保持其離群檢測(cè)效果的同時(shí)提升檢測(cè)效率;如文獻(xiàn)[12]指出,INFLO算法[11]至今仍然屬于基于局部密度的離群檢測(cè)算法中效果最好的算法之一。因此,考慮只對(duì)LDBO算法與LOF算法、INFLO算法進(jìn)行實(shí)驗(yàn)分析。

實(shí)驗(yàn)環(huán)境配置如下:Intel 1.8 GHz/512 MB,Windows 2000 Server,所用代碼均用VC++ 6.0實(shí)現(xiàn)。實(shí)驗(yàn)所使用的數(shù)據(jù)共兩種：第一種來(lái)源于網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集 KDD-CUP 99,該數(shù)據(jù)集中的數(shù)據(jù)對(duì)象分為五大類,包括正常的連接、各種入侵和攻擊等。為了進(jìn)行實(shí)驗(yàn),分別選取1 000條記錄和10 000條記錄的兩個(gè)數(shù)據(jù)集(分別稱為KDD-CUP-1000和KDD-CUP-10000),并對(duì)數(shù)據(jù)進(jìn)行適當(dāng)修改,使得攻擊(即離群點(diǎn))占數(shù)據(jù)集的3%,對(duì)非數(shù)值屬性維進(jìn)行數(shù)值化處理。第二種是仿真數(shù)據(jù)集(Synthetic DataSet),包括2 200條數(shù)據(jù)記錄,維度為2。精度采用以下量度對(duì)算法進(jìn)行評(píng)價(jià):

檢測(cè)出的離群點(diǎn)總數(shù)指算法在數(shù)據(jù)集上運(yùn)行后，判定為離群點(diǎn)的數(shù)據(jù)點(diǎn)數(shù)目;判斷正確的離群點(diǎn)數(shù)目指算法判定為離群點(diǎn)的數(shù)據(jù)點(diǎn)中真實(shí)離群點(diǎn)的數(shù)目。

圖4 不同算法的精度對(duì)比

圖5 不同算法的執(zhí)行時(shí)間對(duì)比

圖4～5對(duì)應(yīng)k=5,μ=0.5,t=1.2時(shí),LOF算法、INFLO算法和LDBO算法在兩類實(shí)驗(yàn)數(shù)據(jù)集上的運(yùn)行情況。實(shí)驗(yàn)結(jié)果表明,LDBO算法與INFLO算法對(duì)兩類數(shù)據(jù)集的離群點(diǎn)檢測(cè)精度相似,而基于LOF的離群點(diǎn)檢測(cè)算法檢測(cè)精度相對(duì)較低,特別是對(duì)仿真數(shù)據(jù)集,其離群點(diǎn)檢測(cè)精度遠(yuǎn)低于LDBO算法和INFLO算法;由圖5可知,LDBO算法效率明顯優(yōu)于另兩種算法,這符合第2章理論分析。LDBO算法通過(guò)定義強(qiáng)k近鄰點(diǎn)和弱k近鄰點(diǎn)對(duì)數(shù)據(jù)點(diǎn)進(jìn)行區(qū)分處理,有效地避免了INFLO算法對(duì)所有數(shù)據(jù)點(diǎn)進(jìn)行反向k近鄰計(jì)算分析的不足;進(jìn)一步,通過(guò)性質(zhì)2,對(duì)待檢測(cè)數(shù)據(jù)點(diǎn)進(jìn)行預(yù)判斷,從而在保證檢測(cè)精度的前提下,有效地提高了占數(shù)據(jù)集較大比重的聚簇內(nèi)數(shù)據(jù)點(diǎn)的離群點(diǎn)檢測(cè)效率。仿真測(cè)試數(shù)據(jù)集分布情況如圖6(a)所示，數(shù)據(jù)集包含兩個(gè)大的聚簇,中間區(qū)域存在類似圖1的數(shù)據(jù)分布異常情況。圖6(b)對(duì)應(yīng)LDBO算法在仿真數(shù)據(jù)集上運(yùn)行時(shí),利用性質(zhì)2進(jìn)行預(yù)判斷后,實(shí)際需要分析離群因子判斷是否為離群點(diǎn)的數(shù)據(jù)點(diǎn),與圖6(a)對(duì)比發(fā)現(xiàn)兩個(gè)聚簇內(nèi)部相當(dāng)部分的數(shù)據(jù)點(diǎn)可以根據(jù)性質(zhì)2進(jìn)行預(yù)判斷,無(wú)需作進(jìn)一步的分析處理。

圖6 測(cè)試數(shù)據(jù)集與LDBO算法實(shí)際處理數(shù)據(jù)對(duì)比

圖7 不同μ值算法執(zhí)行時(shí)間對(duì)比

圖8 不同μ值算法的精度比較

進(jìn)一步分析強(qiáng)k近鄰點(diǎn)和弱k近鄰點(diǎn)參數(shù)μ對(duì)算法性能的影響,采用仿真數(shù)據(jù)集,μ∈[0.1,1],k=5,t=1.2,對(duì)算法LDBO和基于INFLO的算法進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖7～8所示。LDBO算法中,參數(shù)μ設(shè)置將影響對(duì)強(qiáng)近鄰點(diǎn)和弱近鄰點(diǎn)的判定,例如,μ值設(shè)置得比較低,則數(shù)據(jù)集中大部分?jǐn)?shù)據(jù)點(diǎn)都將被判定為強(qiáng)k近鄰點(diǎn),但這并不影響對(duì)數(shù)據(jù)集中數(shù)據(jù)點(diǎn)離群判定的準(zhǔn)確性,只要μ的取值不為0,都可以有效避免圖1所示數(shù)據(jù)分布極端情況對(duì)離群點(diǎn)判定的影響,即使某個(gè)k近鄰內(nèi)數(shù)據(jù)點(diǎn)分布稀疏，甚至離群點(diǎn)的數(shù)據(jù)點(diǎn)被判作強(qiáng)k近鄰點(diǎn),按照LDBO算法思想,仍需進(jìn)一步分析其是否為局部核心點(diǎn)以確定其離群與否, 圖8驗(yàn)證了μ的取值與算法精度無(wú)關(guān)這一點(diǎn)。而當(dāng)μ設(shè)置得很高時(shí),則成為強(qiáng)k近鄰點(diǎn)的數(shù)據(jù)點(diǎn)規(guī)模越來(lái)越小,則LDBO算法對(duì)數(shù)據(jù)點(diǎn)進(jìn)行離群預(yù)判定的作用發(fā)揮得就較少,大多數(shù)數(shù)據(jù)點(diǎn)都被當(dāng)作弱k近鄰點(diǎn)需要分析其反向k近鄰以判定其離群性。由圖7可以清楚地發(fā)現(xiàn)這一現(xiàn)象,當(dāng)μ大于0.6后,隨著μ的增加,LDBO算法與基于INFLO算法的時(shí)間消耗差漸漸減小。

4 結(jié)語(yǔ)

本文研究了基于局部密度的離群點(diǎn)的檢測(cè)問(wèn)題,提出了LDBO算法。算法通過(guò)引入強(qiáng)k近鄰點(diǎn)和弱k近鄰點(diǎn)有效地解決了存在異常數(shù)據(jù)分布的數(shù)據(jù)集離群點(diǎn)檢測(cè)問(wèn)題,將需要借助反向k近鄰點(diǎn)分析以判斷離群性的數(shù)據(jù)點(diǎn)限定在較小范圍內(nèi),進(jìn)一步提出相關(guān)性質(zhì),實(shí)現(xiàn)對(duì)數(shù)據(jù)集中非離群點(diǎn)的預(yù)判定,有效提高了基于密度離群點(diǎn)檢測(cè)算法的效率和對(duì)數(shù)據(jù)集的適應(yīng)性。

References)

[1] HAWKINS D. Identification of Outliers[M]. London: Chapman and Hall, 1980: 1-45.

[2] JOHNSON T, KWOK I, NG R. Fast computation of 2-dimensional depth contours[C]// KDD 1998: Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining. Menlo Park: AAAI Press, 1998: 224-228.

[3] KNORR E M, NG R T. Algorithms for mining distance-based outliers in large datasets[C]// VLDB 1998: Proceedings of the 24rd International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 1998: 392-403.

[4] BREUNIG M M, KRIEGEL H-P, NG R T, et al. LOF: identifying density-based local outliers[J]. ACM SIGMOD Record, 2000, 29(2): 93-104.

[5] PAPADIMITRIOU S, KITAGAWA H, GIBBONS P B. LOCI: fast outlier detection using the local correlation integral[C]// Proceedings of the 19th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2004: 315-326.

[6] AGGARWAL C, YU P. Outlier detection for high dimensional data[J]. ACM SIGMOD Record, 2001, 30(2) : 37-46.

[7] 倪巍偉, 陳 耿, 陸介平, 等. 基于局部信息熵的加權(quán)子空間離群點(diǎn)檢測(cè)算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2008, 45(7): 1189-1194. (NI W W, CHEN G, LU J P, et al. Local entropy based weighted subspace outlier mining algorithm[J]. Journal of Computer Research and Development, 2008, 45(7): 1189-1194.)

[8] 劉露, 左萬(wàn)利, 彭濤.異質(zhì)網(wǎng)中基于張量表示的動(dòng)態(tài)離群點(diǎn)檢測(cè)方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(8): 1729-1739. (LIU L, ZUO W L, PENG T. Tensor representation based dynamic outlier detection method in heterogeneous network[J]. Journal of Computer Research and Development, 2016, 53(8): 1729-1739.)

[9] 黃添強(qiáng), 余養(yǎng)強(qiáng), 郭躬德, 等.半監(jiān)督的移動(dòng)對(duì)象離群軌跡檢測(cè)算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(11): 2074-2082. (HUANG T Q, YU Y Q, GUO G D, et al. Trajectory outlier detection based on semi-supervised technology[J]. Journal of Computer Research and Development, 2011, 48(11): 2074-2082.)

[10] 胡彩平, 秦小麟. 一種基于密度的局部離群點(diǎn)檢測(cè)算法DLOF[J]. 計(jì)算機(jī)研究與發(fā)展, 2010, 47(12): 2110-2116. (HU C P, QIN X L. A density-based local outlier detecting algorithm [J]. Journal o f Computer Research and Development, 2010, 47(12): 2110-2116.)

[11] JIN W, TUNG A K H, HAN J, et al. Ranking outliers using symmetric neighborhood relationship[C]// Proceedings of the 10th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Berlin: Springer, 2006: 577-593.

[12] RADOVANOVIC M, NANOPOULOS A, IVANOVIC M. Reverse nearest neighbors in unsupervised distance-based outlier detection[J]. IEEE Transactions on Knowledge amp; Data Engineering, 2014, 27(5): 1369-1382.

[13] 楊慧, 王麗婧. 基于聚類和擬合的QAR數(shù)據(jù)離群點(diǎn)檢測(cè)算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2015, 36(1): 174-177. (YANG H, WANG L J.QAR data outlier detection algorithm based on clustering and fitting[J]. Computer Engineering and Design, 2015, 36(1): 174-177.)

Fastoutlierdetectionalgorithmbasedonlocaldensity

ZOU Yunfeng1, ZHANG Xin1, SONG Shiyuan2*, NI Weiwei2

(1.StateGrid,JiangsuElectronicPowerResearchInstitute,NanjingJiangsu210036,China;2.SchoolofComputerScienceandEngineering,SoutheastUniversity,NanjingJiangsu211189,China)

Mining outliers is to find exceptional objects that deviate from the most rest of the data set. Outlier detection based on density has attracted lots of attention, but the density-based algorithm named Local Outlier Factor (LOF) is not suitable for the data set with abnormal distribution, and the algorithm named INFLuenced Outlierness (INFLO) solves this problem by analyzing bothknearest neighbors and reverseknearest neighbors of each data point at cost of inferior efficiency. To solve this problem, a local density-based algorithm named Local Density Based Outlier detection (LDBO) was proposed, which can improve outlier detection efficiency and effectiveness simultaneously. LDBO introduced definitions of strongknearest neighbors and weakknearest neighbors to realize outlier relation analysis of those data points located nearby. Furthermore, to improve the outlier detection efficiency, prejudgement was applied to avoid unnecessary reverseknearest neighbor analysis as far as possible. Theoretical analysis and experimental results Indicate that LDBO outperforms INFLO in efficiency, and it is effective and feasible.

outlier detection; local density; strongknearest neighbors; weakknearest neighbors; ReversekNearest Neighbors (RkNN)

2017- 04- 12 ;

2017- 07- 02。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61370077)。

鄒云峰(1977—),男,江西豐城人,高級(jí)工程師,主要研究方向:數(shù)據(jù)挖掘、電力信息系統(tǒng); 張昕(1987—),男,江蘇南京人,碩士,主要研究方向:數(shù)據(jù)集成、電力信息系統(tǒng); 宋世淵(1992—),男,河南平頂山人,碩士研究生,主要研究方向:數(shù)據(jù)挖掘、數(shù)據(jù)隱私保護(hù); 倪巍偉(1979-)，男,江蘇淮陰人,教授,博士生導(dǎo)師,博士,主要研究方向:數(shù)據(jù)挖掘、數(shù)據(jù)隱私保護(hù)、復(fù)雜數(shù)據(jù)管理。

1001- 9081(2017)10- 2932- 06

10.11772/j.issn.1001- 9081.2017.10.2932

TP274

A

This work is partially supported by the National Natural Science Foundation of China (61370077).

ZOUYunfeng, born in 1977, senior engineer. His research interests include data mining, electronic information system.

ZHANGXin, born in 1987, M. S. His research interests include data integration, electronic information system.

SONGShiyuan, born in 1992, M. S., candidate. His research interests include data mining, data privacy protection.

NIWeiwei, born in 1979, Ph. D., professor. His research interests include data mining, data privacy protection, complex data management.