基于密度的Top-n局部異常點快速檢測算法

劉 芳 齊建鵬 于彥偉 曹 磊 趙金東

近年來,隨著各類智能移動設(shè)備的廣泛普及,社交網(wǎng)絡(luò)、網(wǎng)上購物、移動支付、位置服務(wù)等新興應(yīng)用不斷涌現(xiàn),各類海量大數(shù)據(jù)被采集和處理,而面向這些大數(shù)據(jù)的挖掘分析服務(wù)已儼然成為一大獨具特色的新興產(chǎn)業(yè).異常檢測作為數(shù)據(jù)挖掘最重要的任務(wù)之一,在網(wǎng)絡(luò)監(jiān)測、信用卡欺詐、電信詐騙、金融證券服務(wù)、電子商務(wù)等各種應(yīng)用領(lǐng)域都被認為是至關(guān)重要的內(nèi)容.因此,異常檢測在學術(shù)界與工業(yè)界都受到了越來越多的關(guān)注,在大數(shù)據(jù)與人工智能應(yīng)用中,異常檢測也發(fā)揮了越來越重要的作用,例如在北京,通過對地鐵和公交乘車記錄的異常檢測分析可幫助安保系統(tǒng)識別出潛在的小偷[1].

異常檢測旨在從海量數(shù)據(jù)中識別出與大多數(shù)數(shù)據(jù)樣本差異較大的數(shù)據(jù)對象.目前已存在很多異常檢測研究工作[2?4],如基于距離的異常檢測[5?7]、基于鄰居的異常檢測[8?10]、基于分布的異常檢測[11?13]和基于聚類的異常檢測[14?15]等.然而,這些異常檢測方法都無法處理數(shù)據(jù)傾斜分布下的異常檢測問題,因為在傾斜分布的數(shù)據(jù)中,不同區(qū)域的異常數(shù)據(jù)可能具有不同的數(shù)據(jù)特征,而上述方法都采用全局的異常標準來處理數(shù)據(jù)對象.基于密度的LOF[16]有效解決了在數(shù)據(jù)傾斜分布下的異常檢測問題.局部異常檢測利用每個數(shù)據(jù)對象相對于其周圍鄰居的相對密度衡量異常因子,這樣的相對密度反映了局部的數(shù)據(jù)分布,也就是說,對異常的檢測是相對于局部數(shù)據(jù)的,因此可以處理傾斜分布下的異常檢測問題.在實際應(yīng)用中,尤其是在大數(shù)據(jù)系統(tǒng)中,數(shù)據(jù)的分布往往是傾斜的,基于LOF 的局部異常檢測方法相比其他檢測方法在很多應(yīng)用領(lǐng)域都表現(xiàn)出了較好的異常檢測效果[17?18].

局部異常檢測方法[16]需要計算每個數(shù)據(jù)對象的LOF 異常因子,然后通過排序找出LOF 值較大的數(shù)據(jù)點作為異常對象,而LOF 定義了相對密度,要求查找每個數(shù)據(jù)的k近鄰及可達距離,因此檢測計算成本非常高,很難滿足對大規(guī)模數(shù)據(jù)的異常檢測效率需求.最新研究[19]針對Top-n局部異常點檢測,提出了一種基于LOF 上界剪枝的檢測算法(Top-nLOF,TOLF),利用Cell 索引和LOF 上界對數(shù)據(jù)對象進行剪枝,較大地提升了局部異常點檢測的效率.盡管如此,TOLF 在Cell 剪枝中僅采用了一個全局的兩點間最小距離cpmin進行剪枝,當全局cpmin較小時,將嚴重影響Cell 剪枝效果,甚至失效,此外,針對數(shù)據(jù)對象剪枝的LOF 上界相比真實LOF 值較大且計算復雜度較高,使得剪枝效果也有限.

針對這些問題,本文提出了一種改進的Top-n局部異常點檢測算法MTLOF,融合索引結(jié)構(gòu)和多層LOF 上界設(shè)計剪枝策略,實現(xiàn)了高效的局部異常點檢測.1)為避免直接計算LOF 值,提出了四個更接近真實LOF 值的LOF 上界(UB1?UB4),并對它們的計算復雜度進行了理論分析;2)利用索引結(jié)構(gòu)和UB1、UB2上界,提出了兩層的Cell 剪枝策略,不僅采用全局Cell 剪枝策略,還引入了基于Cell 內(nèi)部數(shù)據(jù)對象分布的局部剪枝策略,有效解決了高密度區(qū)域的剪枝問題;3)利用提出的UB3和UB4上界,提出了兩個更加合理有效的數(shù)據(jù)對象剪枝策略,UB3和UB4上界更加接近于真實LOF 值,有利于剪枝更多數(shù)據(jù)對象,而基于計算復用的LOF上界計算方法,大大降低了計算成本;4)優(yōu)化了初始候選Top-n局部異常點的選擇方法,利用均勻區(qū)域劃分和建立的索引結(jié)構(gòu),在數(shù)據(jù)分布的稀疏區(qū)域選擇初始局部異常點,有利于選擇LOF 值較大的數(shù)據(jù)對象作為初始局部異常點,有效提升初始臨界值(Cutoff threshold)ct,使得在初始階段剪枝掉更多的Cell 和數(shù)據(jù)對象.5)在六個不同維度的真實數(shù)據(jù)集上的綜合實驗評估驗證了MTLOF 算法的高效性和可擴展性,相比最新的TOLF 算法,提升的效率可高達3.5 倍.

本文結(jié)構(gòu)如下:第1 節(jié)討論相關(guān)工作;第2 節(jié)定義基本概念和問題;第3 節(jié)給出詳細的檢測算法;第4 節(jié)進行實驗驗證和分析;第5 節(jié)總結(jié)全文.

1 相關(guān)工作

Breunig 等[16]最早提出了局部異常因子LOF的概念,相對基于距離的異常檢測[5?6]和KNN 異常檢測[9],LOF 采用相對密度衡量每個數(shù)據(jù)對象的異常程度,LOF 越高表示數(shù)據(jù)對象相對于其鄰居的密度差異較大,異常的可能性也就越高.異常通常只是數(shù)據(jù)集的極少部分,因此Jin 等[20]首次提出了Top-n局部異常的概念,從數(shù)據(jù)集中選取n個LOF 值最大的數(shù)據(jù)對象,即為Top-n局部異常.傳統(tǒng)LOF 挖掘方法[16]主要分為兩步:首先計算出所有數(shù)據(jù)對象的LOF 值,然后對所有數(shù)據(jù)按LOF 值降序排序,前n個數(shù)據(jù)對象即為Top-n局部異常.文獻[20]首先利用Birch 算法[21]對數(shù)據(jù)對象進行聚類,利用聚簇的半徑和聚簇間的距離關(guān)系計算每個聚簇的LOF 界值,對聚簇進行排序,然后在最可能包含異常的聚簇中檢測Top-n局部異常點.雖然該方法通過聚類方法剪枝掉了部分數(shù)據(jù)對象,但是數(shù)據(jù)預處理計算成本昂貴,不適用于大數(shù)據(jù)的處理.此外,算法的剪枝策略也具有較大局限性,并沒有表現(xiàn)很好的剪枝效果.

另外一類相關(guān)工作就是LOF 的變種方法,Tang 等[22]提出了一種基于連通性的異常檢測方法(Connectivity-based outlier factor,COF),COF首先利用最小生成樹衡量每個數(shù)據(jù)對象與它k近鄰的連通度,然后與LOF 相似,利用相對k近鄰連通度定義每個數(shù)據(jù)對象的COF.為了優(yōu)化基于最小生成樹聚類的異常檢測,朱利等[23]提出了一種快速構(gòu)建最小生成樹的優(yōu)化方法,可同時檢測基于距離的全局異常和基于密度的局部異常,但是這類基于掃描樹的聚類方法無法處理大規(guī)模數(shù)據(jù),如文獻[23]中性能驗證,在處理1 800 個數(shù)據(jù)點時已消耗近60秒.Papadimitriou 等[24]提出了一種局部相關(guān)度方法(Local correlation integral,LOCI),LOCI 采用一個區(qū)域半徑r定義數(shù)據(jù)對象的本地鄰居區(qū)域,以代替k近鄰.雖然LOCI 相比LOF 具有較低計算復雜度,但是在數(shù)據(jù)傾斜分布下,通過固定區(qū)域半徑定義局部異常并不合理,可能導致稀疏區(qū)域的數(shù)據(jù)對象沒有鄰居點而高密度區(qū)域的數(shù)據(jù)對象包含過多的鄰居點.楊宜東等[25]為了減少計算時間,還提出了一種動態(tài)網(wǎng)格劃分的數(shù)據(jù)流下的LOCI 異常檢測方法.Zhang 等[26]提出了一種基于距離的局部異常點檢測(Local distance-based outlier factor,LDOF),LDOF 采用數(shù)據(jù)對象到其k近鄰距離的均值定義數(shù)據(jù)對象的局部密度,然后相對k近鄰計算相對密度獲得異常因子.與文獻[26]相似,Krieget 等[27]則使用數(shù)據(jù)對象到其k近鄰距離的平方和的均值來定義局部密度.最近,Schubert 等[28?29]又提出了一種更為簡單的LOF 變種方法,稱為Simplified-LOF,該方法直接使用k-距離代替可達距離,也就是說,直接使用k-距離的倒數(shù)定義局部密度.該方法雖然簡化了LOF 方法,但是僅考慮每個數(shù)據(jù)對象到第k個近鄰的距離,將導致異常檢測效果嚴重依賴于參數(shù)k的選取.此外,Liu 等[30]將局部異常檢測擴展到了不確定數(shù)據(jù)領(lǐng)域上,研究了在概率密度表示的不確定數(shù)據(jù)模型上的異常檢測方法.最近Cao 等[31?32]還考慮了在屬性級不確定數(shù)據(jù)上的Top-n局部異常點檢測方法.

Liu 等[33?34]提出一種基于隔離樹的快速異常檢測算法(Isolation forest,Iforest),該方法首先隨機采樣m個數(shù)據(jù)對象樣本,構(gòu)建多棵Itree 隔離樹(Isolation trees),然后對每個數(shù)據(jù)對象來遍歷這些Itree,根據(jù)數(shù)據(jù)對象經(jīng)過的平均路徑長度來判斷是否為異常對象.Iforest 雖具有線性的時間復雜度,但并不適用于特別高維數(shù)據(jù),因為每次切割數(shù)據(jù)空間都是隨機選取一個維度,建立隔離樹后仍有大量維度信息沒有使用,導致算法可靠性降低.此外,Iforest 算法也僅對全局異常敏感,不擅長處理局部的相對稀疏點,即本文處理的局部異常點.為了加快Top-n局部異常點檢測,最新研究[19]提出了一種基于Cell 索引和LOF 上界剪枝的TOLF 算法,TOLF 首先將數(shù)據(jù)集劃分成多個相對均勻的區(qū)域,并對相對密集的區(qū)域建立Cell 索引,然后利用Cell索引和LOF 上界對Cell 和數(shù)據(jù)對象進行剪枝.盡管TOLF 有效提升了Top-n局部異常點的檢測效率,但是采用全局最小距離的Cell 剪枝策略具有一定局限性,當存在較多過密區(qū)域時(最小距離非常小),將嚴重影響Cell 剪枝效果,甚至失效.此外,TOLF 所采用的面向單個數(shù)據(jù)對象剪枝的LOF 上界相比數(shù)據(jù)對象真實LOF 值較大,導致數(shù)據(jù)對象的剪枝空間有限.

2 問題定義

本節(jié)首先介紹LOF[16]相關(guān)定義,然后給出Top-n局部異常點檢測的問題定義.

基于密度的局部異常根據(jù)每個數(shù)據(jù)對象本地的密度與它k近鄰的密度的比值判斷該數(shù)據(jù)對象是否是一個局部異常點.對于兩個數(shù)據(jù)對象p和q,本文使用dist(p,q)表示它們間的距離.所有數(shù)據(jù)對象集合表示為D.

定義1(k 近鄰).給定數(shù)據(jù)對象p和任意正整數(shù)k,數(shù)據(jù)對象p的k近鄰集合由到p距離最近的k個數(shù)據(jù)對象組成,表示為Nk(p).

定義2(k-距離).給定數(shù)據(jù)對象p和任意正整數(shù)k,距離p第k個最近的數(shù)據(jù)對象記為qk,p的k-距離則是p到qk的距離,記為distk(p).

也就是說,對于任意q ∈Nk(p),dist(p,q)≤distk(p).

定義3(可達距離).給定數(shù)據(jù)對象p和q ∈Nk(p),數(shù)據(jù)對象p相對于q的可達距離distr(p,q)定義如下:distr(p,q)=max{dist(p,q),distk(q)}.

根據(jù)定義3,如果對象p也是q的k近鄰,也就是說p ∈Nk(q),則p相對于q的可達距離就是distk(q);反之,則為兩對象的距離dist(p,q).

定義4(k 近鄰可達距離和).給定數(shù)據(jù)對象p,數(shù)據(jù)對象p的k近鄰可達距離和distkr(p)定義如下:

定義5(局部可達密度).數(shù)據(jù)對象p的局部可達密度(Local reachability density,LRD)表示為:

從定義5 可知,LRD(p)就是數(shù)據(jù)對象p相對于其k近鄰的可達距離的均值的倒數(shù),也就是說,局部可達密度主要通過數(shù)據(jù)對象相對于其k近鄰的可達距離來估計它的局部密度.數(shù)據(jù)對象相對于其k近鄰的可達距離均值越小,也就是說相對越密集,它的局部可達密度就越高.接下來根據(jù)LRD(p)來定義數(shù)據(jù)對象的局部異常因子LOF.

定義6(局部異常因子).數(shù)據(jù)對象p的局部異常因子表示為:

很明顯,LOF(p)就是數(shù)據(jù)對象p的所有k近鄰的局部可達密度與p的局部可達密度比值的均值.因此,LOF(p)越接近于1,說明對象p與其k近鄰的局部密度越接近,p的異常程度越小;LOF(p)小于1 時,則說明對象p處于一個高密度區(qū)域.相反,LOF(p)值越大,則表示p是異常點的可能性越大.所以本文的關(guān)注點在于快速檢測出具有較高LOF的數(shù)據(jù)對象,下面給出本文所要解決的Top-n局部異常點檢測的問題定義.

問題1(Top-n 局部異常點檢測).給定數(shù)據(jù)集合D,對象近鄰數(shù)k,和異常點數(shù)量n,Top-n局部異常點檢測則是返回數(shù)據(jù)集D中LOF 值最大的前n個數(shù)據(jù)對象.

3 基于密度的Top-n局部異常點檢測

本節(jié)將詳細介紹本文所提出的Top-n局部異常點檢測的優(yōu)化算法,首先介紹基于臨界值剪枝的檢測算法,然后介紹優(yōu)化算法用到的四個LOF 上界,接著介紹基于LOF 上界的剪枝策略,最后給出優(yōu)化的檢測算法.

3.1 基于臨界值剪枝的檢測算法

為了獲取LOF 值最大的前n個數(shù)據(jù)對象,即Top-n局部異常點,傳統(tǒng)的基本方法將計算出所有數(shù)據(jù)對象的LOF 值,然后按照LOF 值排序,返回前n個數(shù)據(jù)對象.然而,對于Top-n局部異常點,并不需要計算出所有數(shù)據(jù)對象的LOF 值,我們僅關(guān)心LOF 值最大的n個數(shù)據(jù)對象,因此,只需要維護LOF 值最大的n個數(shù)據(jù)對象即可.

給定數(shù)據(jù)集D,從中隨機選取n個數(shù)據(jù)對象,并計算它們的LOF 值,選取最小的LOF 值作為臨界值(Cutoff threshold,ct).可以發(fā)現(xiàn),對于數(shù)據(jù)集D中任意的數(shù)據(jù)對象p,如果LOF(p)ct,則p可能是Top-n局部異常點,將p放入維護隊列,剔除隊列中LOF 最小的數(shù)據(jù)對象,并更新臨界值ct.依次遍歷一遍數(shù)據(jù)集,即可獲取到Top-n局部異常點.這種剪枝檢測方法我們稱之為基于臨界值剪枝的檢測算法.

從定義6 可知,直接計算數(shù)據(jù)對象LOF 值的成本較高,為了更高效地檢測出Top-n局部異常點,我們將從四個方面優(yōu)化基于臨界值剪枝的檢測方法:1)如何快速獲取到LOF 值較大的n個數(shù)據(jù)對象作為初始維護的候選異常對象;2)選取更合理有效的LOF 值上界進行剪枝判斷,以避免直接計算數(shù)據(jù)對象的LOF 值;3)如何使用數(shù)據(jù)對象的這些LOF 值上界,使得計算量盡量小,且被剪枝掉的數(shù)據(jù)對象數(shù)量盡量多;4)如何結(jié)合索引技術(shù)和LOF 上界快速剪枝掉高密度區(qū)域的所有數(shù)據(jù)對象.

3.2 LOF 上界

本小節(jié)將首先介紹數(shù)據(jù)對象LOF 值的四個上界,然后分析四個上界的計算時間復雜度.

3.2.1 四個LOF 上界

根據(jù)定義5 和定義6 可以得出:

LOF(p)被表示成了兩個部分的乘積,第一部分表示p的局部可達密度的倒數(shù),第二部分表示p所有k近鄰的k近鄰可達距離和的倒數(shù)和.下面由定理1 引出數(shù)據(jù)對象p的第一個LOF 上界UB1(p).

定理1(LOF 的上界一).給定數(shù)據(jù)集D中的一個數(shù)據(jù)對象p,p的LOF 值滿足以下上界:

其中,cpmin表示D中所有數(shù)據(jù)對象間最小的距離.

定理2(LOF 的上界二).給定數(shù)據(jù)集D中的一個數(shù)據(jù)對象p,p的LOF 值滿足以下上界:

圖1 distr(q,o)與dist(q,o)的關(guān)系示例Fig.1 The relationships between distr(q,o)and dist(q,o)

定理3(LOF 的上界三).給定數(shù)據(jù)集D中的一個數(shù)據(jù)對象p,p的LOF 值滿足以下上界:

接下來只需證明distkr(p)/|Nk(p)| ≤2· distk(p)即 可.設(shè) 定directmax(p)=max{distr(p,q)|q ∈Nk(p)}[16],所以directmax(p)大于等于對象p的k近鄰可達距離和的均值,即distkr(p)/|Nk(p)| ≤directmax(p),所以只需證明directmax(p)≤2·distk(p)即可.

directmax(p)是取對象p相對于它的k近鄰最大的可達距離,根據(jù)定義3 可知,這等價于求解?q ∈Nk(p),返回dist(p,q)和distk(q)的最大值,所以只需證明maxq∈Nk(p)dist(p,q)≤2·distk(p)和maxq∈Nk(p)distk(q)≤2·distk(p)即可.

由定義2 可知,?q ∈ Nk(p),dist(p,q)≤distk(p),所以maxq∈Nk(p)dist(p,q)≤2·distk(p);對于q ∈Nk(p)來說,它的k近鄰分布可分為圖2(a)和圖2(b)兩種情況,一種情況為q附近有很多數(shù)據(jù)對象,q的k-距離小于2·distk(p),甚至小于distk(p),如圖2(a)所示;另一種情況為q附近存在較少的數(shù)據(jù)對象,在最極端情況下,不存在任何數(shù)據(jù)對象,但是,當q搜索鄰居的范圍擴大到2·distk(p)時,一定能夠涵蓋p以及p的k近鄰,如圖2(b)所示,也就說,distk(q)≤2·distk(p).因此,maxq∈Nk(p)distk(q)≤2·distk(p).

圖2 distk(p)與distk(q)的關(guān)系示例Fig.2 The relationships between distk(p)and distk(q)

接下來,我們給出最后一個更加接近于LOF 值的上界UB4(p).

定理4(LOF 的上界四).給定數(shù)據(jù)集D中的一個數(shù)據(jù)對象p,p的LOF 值滿足以下上界:

由定理3、定理4 及它們證明過程可以得出,LOF(p)≤UB4(p)≤UB3(p).

3.2.2 時間復雜度分析

根據(jù)定理1～4,四個上界的大小順序為:LOF(p)≤ UB4(p)≤ UB2(p)≤ UB1(p)和LOF(p)≤UB4(p)≤UB3(p).由于UB3(p)的第一部分相對于UB1(p)、UB2(p)的第一部分變大,而第二部分相對變小,因此,不能確定UB3(p)和UB1(p)、UB2(p)的相對大小.

設(shè)定數(shù)據(jù)集D中數(shù)據(jù)對象總數(shù)為N,一般情況下,,查詢每個數(shù)據(jù)對象k近鄰的時間復雜度為O(Nlogk),計算distkr(p)時,首先查詢到p的k個近鄰,時間復雜度為O(Nlogk),然后求出所有k近鄰的k近鄰,時間復雜度為O(k·Nlogk),求得k個可達距離并相加,時間復雜度為O(k),所以計算distkr(p)的復雜度為O[(k+1)Nlogk+k].計算時,同樣,首先獲得p的k近鄰,然后求每個k近鄰q的k近鄰,并計算每個q與其近鄰的距離和,時間復雜度為O[(k+1)·Nlogk+k],最后,求取k個距離和中的最小值或倒數(shù)和,時間復雜度為O(k),因此,和的時間復雜度為O((k+1)Nlogk+2k).

1)UB1(p):獲取全局cpmin的時間復雜度為O(N2);但整個檢測算法僅需計算一次,所以平均到每個數(shù)據(jù)對象的計算時間為O(N);計算distkr(p)的時間復雜度為O((k+1)Nlogk+k),因此,計算UB1(p)的平均復雜度為O(UB1(p))=O(N+(k+1)Nlogk+k).

2)UB2(p):根據(jù)distkr(p)和的時間復雜度知,UB2(p)的時間復雜度為O(2(k+1)Nlogk+3k).

5)LOF(p):獲取distkr(p)/|Nk(p)|的復雜度為O((k+1)Nlogk+k),所以計算LRD(p)的復雜度為O((k+1)Nlogk+k+1);計算p每個k近鄰q的LRD 的時間復雜度為O(k·Nlogk+k+1);因此,計算LOF(p)的時間復雜度為O((k+1)Nlogk+k+1)+k·O(k·Nlogk+k+1)+O(k)≈O((k2+k+1)Nlogk+k2+3k).

根據(jù)以上時間復雜度分析,LOF(p)的時間復雜度遠大于四個上界的時間復雜度,因此,計算上界的時間遠小于計算LOF 值的時間.

3.3 融合索引和LOF 上界的剪枝方法

盡管利用LOF 上界剪枝數(shù)據(jù)對象可減少計算成本,但是對于每個數(shù)據(jù)對象仍需計算k近鄰可達距離和.為了快速剪枝掉高密度區(qū)域的數(shù)據(jù)對象,下面介紹融合Cell 索引和LOF 上界的剪枝方法,無需對每個數(shù)據(jù)對象進行計算即可剪枝掉高密度區(qū)域內(nèi)的所有數(shù)據(jù)對象.

3.3.1 基于Cell 的全局剪枝

對于某一高密度區(qū)域內(nèi)的數(shù)據(jù)對象,如果能夠保證所有數(shù)據(jù)對象的LOF 值上界UBi小于臨界值ct,則該區(qū)域內(nèi)的所有數(shù)據(jù)對象都可以直接被剪枝掉.給定邊長lenside,將整個數(shù)據(jù)空間按照lenside為單位長度劃分,得到的每個子空間劃分稱為一個Cell,如圖3 所示,包括了9 個Cell,中間Cell 記為C.

考慮使用上界UB1(p),給定一個高密度的CellC,如果對于?p ∈C,UB1(p)

引理1(基于Cell的全局剪枝).給定一個Cell,記為C,LOF 剪枝臨界值ct,如果C包含的數(shù)據(jù)對象多于k個,并且其邊長(d為數(shù)據(jù)的維度),那么C中所有的數(shù)據(jù)對象可以直接被剪枝.

證明.由定理1 可知,LOF(p)≤UB1(p)=distkr(p)/|Nk(p)|·cpmin,只 需 證 明?p ∈ C,UB1(p)≤ct即可,也就是證明distkr(p)/|Nk(p)|≤ct·cpmin.

由于C包括多于k個對象,所以對于任一對象p ∈C都可以在Cell 對角線范圍內(nèi)找到k近鄰,即對于p的k近鄰,在最壞情況下,都可以在范圍內(nèi)找到k近鄰,即如圖3 所示,當p處于C的右上角時(極端情況),假設(shè)C中僅包含k+1 個數(shù)據(jù)點,p的k近鄰可能會取到C外的q點,在最壞情況下,q仍能在范圍內(nèi)找到k個近鄰.因此,

圖3 基于Cell 索引的剪枝示例Fig.3 An example of pruning based on Cell index

傳統(tǒng)Cell 劃分方法將整個數(shù)據(jù)空間按照全局的邊長劃分,從引理1 可知,高密度區(qū)域的剪枝條件除了與Cell 內(nèi)的數(shù)據(jù)對象數(shù)量有關(guān),還要求Cell 的邊長不大于很明顯,該邊長條件與cpmin有關(guān),當全局cpmin較小時,將嚴重影響被剪枝掉的高密度區(qū)域的數(shù)量.

基于上述考慮,本文采用文獻[19]提出的均勻區(qū)域生成方法,首先將整個數(shù)據(jù)集按照數(shù)據(jù)對象分布劃分成幾個相對獨立的數(shù)據(jù)分布相對均勻的區(qū)域,每個區(qū)域獨自處理數(shù)據(jù)對象,即分區(qū)自治.具體的劃分方法分為兩步,1)首先將整個數(shù)據(jù)空間看成根節(jié)點,然后按照二叉樹迭代地劃分數(shù)據(jù)空間,直到每個葉子節(jié)點至少包括k個數(shù)據(jù)對象且不可再分;2)從葉子節(jié)點向上合并節(jié)點,如果兩個子節(jié)點內(nèi)部數(shù)據(jù)對象間最小的距離的大小比例小于diff,即則合并這兩個子節(jié)點,直到不能再向上合并,一個獨立的區(qū)域被生成.通過設(shè)定適當?shù)谋壤齞iff,可以將兩個分布相似的子節(jié)點合并,因此,可以得到相對分布均勻的區(qū)域.如圖4 所示,根據(jù)數(shù)據(jù)密度分布生成4個均勻區(qū)域,每個區(qū)域內(nèi)即可采用一個執(zhí)行基于Cell 的全局剪枝策略.

圖4 區(qū)域劃分示例Fig.4 An example of area partition

雖然基于Cell 索引方法可以用于剪枝掉高密度的區(qū)域,但Cell 索引采用統(tǒng)一的邊長劃分數(shù)據(jù)空間,雖然實現(xiàn)簡單,但是限制了大塊的高密度區(qū)域的剪枝,除此之外,固定的邊長也不夠靈活,不便于檢驗不同密度的高密度區(qū)域,例如,給定邊長下的某個Cell 內(nèi)少于k個數(shù)據(jù)對象,但是若適當增加邊長(仍滿足剪枝限定條件),該Cell 即可包含多于k個數(shù)據(jù)對象.因此,本文在每個數(shù)據(jù)對象較多的區(qū)域內(nèi)(|Ai| ≥t·k),建立一顆Rtree 索引,使用簡單的層次索引Rtree 代替Cell 索引,Rtree 索引從上向下索引數(shù)據(jù)對象,每個葉子節(jié)點包含小于等于k個數(shù)據(jù)對象.雖然Rtree 索引的節(jié)點區(qū)域為矩形,但是可以按矩形中較長的邊等同于Cell 的邊長來處理,上述的引理1 依然可以適用.Rtree 索引為層次索引結(jié)構(gòu),節(jié)點的矩形大小不固定,這樣,我們就可以從上向下快速剪枝掉最大塊的符合邊長條件的高密度區(qū)域.為了便于描述,在下文仍采用Cell 來表述Rtree 索引中的一個樹節(jié)點.

3.3.2 基于Cell 的局部剪枝

從引理1 可以看出,對于被剪枝掉的Cell 需要滿足全局條件雖然該方法只需計算出cpmin,但是僅考慮到上界UB1(p),忽略了Cell 內(nèi)部數(shù)據(jù)對象的分布情況,下面給出考慮到Cell 內(nèi)數(shù)據(jù)對象分布的局部剪枝方法.

引理2(基于Cell的局部剪枝).給定一個Cell,記為C,LOF 剪枝臨界值ct,如果C包含的數(shù)據(jù)對象多于k個,并且其邊長那么C中所有的數(shù)據(jù)對象可以直接被剪枝,其中

證明.與引理1 相似,只需證明?p ∈ C,LOF(p)≤ UB2(p)≤ ct即可,也就是證明參見引理1 證明,得出

可以看出,引理1 采用了上界UB2(p)對Cell進行剪枝處理,雖然剪枝的邊長條件放松了,但是該剪枝需要計算Cell 內(nèi)部所有數(shù)據(jù)對象的k近鄰距離和的均值.因此,本文設(shè)計了一個兩層的Cell 剪枝策略,首先使用邊長條件進行剪枝,若不能被剪枝掉,再使用邊長條件進一步地進行剪枝判斷.

3.4 基于LOF 上界的數(shù)據(jù)對象剪枝

經(jīng)過兩層Cell 的剪枝檢測后,對于沒有被剪枝掉的Cell,為了避免直接計算LOF 值,將首先對每個數(shù)據(jù)對象進行基于上界的剪枝判斷,若不能被剪枝,再計算LOF 值,最后判斷是否為Top-n異常候選項,若是,則更新臨界值ct.

基于UB3(p)和UB4(p)的數(shù)據(jù)對象剪枝:根據(jù)引理1 和引理2,被剪枝的Cell 內(nèi)的數(shù)據(jù)對象一般滿足小于等于上界UB1(p)和UB2(p),因此,對于不滿足Cell 剪枝條件的數(shù)據(jù)對象,需要采用更加小的上界來進行剪枝.根據(jù)3.2.2 節(jié)分析可知,UB4(p)≤UB2(p)≤UB1(p),UB4(p)≤UB3(p),可使用UB4(p)進一步對數(shù)據(jù)對象進行剪枝檢測,但是,計算UB4(p)的時間復雜度是UB3(p)的近兩倍.此外,計算每個數(shù)據(jù)對象p的UB3(p)時,可直接復用之前對該Cell 進行局部剪枝時已計算過的也就是說,可直接復用之前計算過的每個數(shù)據(jù)對象的k近鄰距離和結(jié)果直接獲得該Cell 內(nèi)每個對象的UB3(p).因此,我們先使用上界UB3(p)對數(shù)據(jù)對象進行剪枝檢測,若不滿足剪枝條件,再使用更小的上界UB4(p)進行剪枝檢測.

計算復用:除了計算UB3(p)時可直接復用之前的計算結(jié)果,在計算UB4(p)同樣可以復用之前計算UB3(p)和時的結(jié)果.對于最終未能被上界剪枝的數(shù)據(jù)對象,在計算真實LOF 值時,也可以復用之前已經(jīng)計算得到所有數(shù)據(jù)對象的k近鄰和k-距離.因此,本文的檢測算法對每個數(shù)據(jù)對象最多僅執(zhí)行一次k近鄰查詢.

3.5 選取初始候選局部異常點

第3.2 節(jié)～3.4 節(jié)詳細描述第3.1 節(jié)提出的優(yōu)化方法,第3.2 節(jié)回答了可利用哪些LOF 上界進行剪枝判斷,而避免直接計算LOF 值,第3.3 節(jié)回答了如何結(jié)合索引技術(shù)和LOF 上界快速剪枝高密度區(qū)域內(nèi)的所有數(shù)據(jù)對象,第3.3 和第3.4 節(jié)共同回答了如何使用LOF 上界,使得上界的計算盡量小,而剪枝掉的數(shù)據(jù)對象盡量多,接下來本節(jié)來回答第一個優(yōu)化問題:如何快速獲取到LOF 值較大的n個對象作為初始維護的候選異常對象?

初始Top-n候選異常對象的選取嚴重影響著檢測算法的執(zhí)行效率,當選擇的初始數(shù)據(jù)對象的LOF值偏大時,可快速剪枝掉大量的Cell 區(qū)域或數(shù)據(jù)對象,但是,當選擇的初始數(shù)據(jù)對象包括高密度區(qū)域的數(shù)據(jù)對象時,將導致初始臨界值ct非常低,初始階段將幾乎沒有Cell 或數(shù)據(jù)對象被剪枝.因此,在選擇初始Top-n候選異常對象時應(yīng)盡量避免選取高密度區(qū)域的數(shù)據(jù)對象,顯然隨機選擇方法并不適合,因為在LOF 異常檢測場景中,通常情況下異常對象是極少數(shù)的,隨機選擇方法更容易選取到非異常對象或高密度區(qū)域內(nèi)的數(shù)據(jù)對象.

本文針對采用的區(qū)域劃分和索引結(jié)構(gòu)選取初始Top-n候選異常對象,Rtree 索引利用空間區(qū)域索引數(shù)據(jù)對象,每個節(jié)點記錄了所包含的數(shù)據(jù)對象及覆蓋的區(qū)域.對于高密度區(qū)域,通常節(jié)點包括數(shù)據(jù)對象較多,且覆蓋區(qū)域較小,而局部異常點通常分散在稀疏區(qū)域.因此,本文首先在區(qū)域劃分中,選擇較大且數(shù)據(jù)對象較少的區(qū)域,在這些區(qū)域內(nèi)隨機選取初始Top-n局部異常點;如果這些區(qū)域不足n個數(shù)據(jù)對象,接著在Rtree 索引的葉子節(jié)點中,根據(jù)節(jié)點的覆蓋區(qū)域,選擇區(qū)域最大的個節(jié)點,在這些區(qū)域和葉子節(jié)點內(nèi)部隨機選取n個節(jié)點作為初始Top-n局部異常點.

3.6 MTLOF:Top-n局部異常點檢測算法

本節(jié)給出本文提出的基于多粒度上界剪枝的Top-n局部異常點檢測算法(Multi-granularity upper bound pruning based t op-nLOFdetection,MTLOF),MTLOF 算法的偽代碼如算法1 所示.

算法1.MTLOF 算法

首先,采用均勻區(qū)域劃分方法將數(shù)據(jù)空間劃分成多個區(qū)域(如行1)所示),對于內(nèi)部數(shù)據(jù)對象數(shù)量大于等于t·k的區(qū)域,建立一顆Rtree 索引(如行3)～5)所示),否則,如果該區(qū)域的為SetareaSetini的最大者,將區(qū)域內(nèi)的數(shù)據(jù)對象放入初始候選異常點集合Setini(如行6)～7)所示).在數(shù)據(jù)對象較多的區(qū)域內(nèi)建立Rtree 的目的有兩個:一是為了進行基于Cell 的剪枝判斷,二是快速查找每個數(shù)據(jù)對象的k近鄰.

然后,在Setini集合中隨機選擇n個數(shù)據(jù)對象作為初始Top-n局部異常點,如果Setini內(nèi)少于n個數(shù)據(jù)對象,則從Rtree 集合中選擇覆蓋區(qū)域最大的葉子節(jié)點,從中再隨機選擇初始Top-n局部異常點,并獲取初始臨界值ct,過程如行8)～12)所示.

之后,開始遍歷所有數(shù)據(jù)對象.首先遍歷Setini剩余的數(shù)據(jù)對象,這是因為這些數(shù)據(jù)對象被Cell 剪枝的可能性較小.如行13)～19)所示,首先利用上界UB3(p)和UB4(p)進行剪枝判斷,若不行,再計算LOF 值,若不能被剪枝,則將p放入Topn取代LOF 值最小的數(shù)據(jù)對象,并更新臨界值ct.接下來開始遍歷Rtree 集合,對于每棵Rtree,從上向下遍歷節(jié)點.根據(jù)引理1 和引理2,如果節(jié)點內(nèi)包含多于k個數(shù)據(jù)對象,并且其邊長則該節(jié)點可被剪枝掉,因此,它的所有子節(jié)點都可以被剪枝掉(行21)～29)所示).對于不能被兩層Cell剪枝策略剪枝的節(jié)點,則需要對內(nèi)部每個數(shù)據(jù)對象進行基于LOF 上界的剪枝判斷,如行31)～37)所示,首先執(zhí)行兩層LOF 上界UB3(p)和UB4(p)的剪枝判斷,若不能通過上界剪枝,再計算LOF 值,若仍大于臨界值ct,則更新Topn和ct.最后,返回最終的Top-n局部異常點集合.

4 實驗評估

本節(jié)在6 個真實數(shù)據(jù)集(第4.1 節(jié))上對所提算法進行了綜合評估.首先,在第4.2 節(jié)評估了所提算法的總體效率,然后,在第4.3 節(jié)分別評估了基于Cell 剪枝和基于數(shù)據(jù)對象剪枝的效率,在第4.4節(jié)分別證明了所提的四個上界在剪枝方面的有效性以及初始化優(yōu)化方法的有效性,之后,在第4.5 節(jié)評估了LOF 類算法(MTLOF、LOF、MC、TOLF)與Iforest、Simplified-LOF 算法的異常檢測準確率和效率,在第4.6 節(jié)分析了參數(shù)k和n對所提的MTLOF 及對比算法的效率影響,最后,在第4.7 節(jié)驗證了所提算法在多維數(shù)據(jù)集上的有效性.

4.1 實驗數(shù)據(jù)與測試方法

實驗平臺采用Intel Xeon E5-2660 處理器,8核,48 GB 內(nèi)存,Windows sever 2012 操作系統(tǒng).所有算法采用Java 實現(xiàn),MTLOF 源代碼已在Github1https://github.com/LiuFang0812/TopNDetection公開.

實驗數(shù)據(jù).實驗采用了6 個真實數(shù)據(jù)集,詳細統(tǒng)計信息如表1所示.

1)Mobike:通過摩拜單車平臺上2https://api.mobike.com/爬取的北京市六環(huán)內(nèi)所有摩拜單車的真實Gps 位置數(shù)據(jù),單車數(shù)量多達五萬輛,該數(shù)據(jù)集僅提取了一天的數(shù)據(jù).

2)Gowalla[35]:該數(shù)據(jù)集來自移動社交網(wǎng)站Gowalla,包括了19.6 萬用戶在2009 年2 月到2010年10 月的簽到位置數(shù)據(jù),共計644 萬條位置信息,本實驗提取了在北美范圍內(nèi)的數(shù)據(jù),約510 萬條位置信息.

表1 實驗數(shù)據(jù)集統(tǒng)計信息Table 1 The statistical information of experimental data sets

3)Geolife[36]:該數(shù)據(jù)集來自微軟亞洲研究院的Geolife 項目,收集了182 名用戶在2007 年4 月至2012 年8 月間的Gps 軌跡數(shù)據(jù),每條Gps 軌跡由帶有時間戳的經(jīng)緯度位置點序列組成.

4)Massachusetts(Mass)[37]:該數(shù)據(jù)集通過Openstreemap3https://www.openstreetmap.org采集,在美國馬薩諸塞州范圍內(nèi)所有的建筑物的地理位置,數(shù)據(jù)集中的每一行代表一棟建筑物,地理位置采用經(jīng)度和緯度兩個屬性表示.

5)Skinseg[38]:該數(shù)據(jù)集從不同年齡組(青年、中年、老年)、不同種族(白人、黑人、亞洲人)以及不同性別的人臉照片中隨機采樣的B、G、R 數(shù)值的數(shù)據(jù)集,包含三維特征屬性.

6)Forestcover[39]:該數(shù)據(jù)集來自科羅拉多北部羅斯福國家森林的四個荒野森林(Neota、Rawah、Comanche Peak 和Cache La Poudre),共包括58 萬多個30×30 平方米的區(qū)域,每個區(qū)域包含了各種樹種的海拔高度、數(shù)量以及坡度等十個屬性.

7)Subforestcover[39]:該數(shù)據(jù)集選取了Forestcover 數(shù)據(jù)集中所有帶標簽的數(shù)據(jù),共包括28 萬多個對象.Rawah 和Comanche Peak 森林主要生長的物種為黑松,它們的物種和特征變量的范圍(如海拔范圍等)都比較典型,于是把標記為黑松的數(shù)據(jù)記錄視為正常對象,標記類別為2,Cache La Poudre森林主要生長黃松、花旗松和楊木/柳樹,由于相對較低的海拔和物種組成,該森林相比其他森林更為獨特,數(shù)據(jù)集中將標記為楊木/柳樹的數(shù)據(jù)記錄視為異常對象,類別標記為4,異常對象數(shù)量的比例為Subforestcover 數(shù)據(jù)的7%.

對比算法.為了驗證所提MTLOF 算法的有效性,實驗結(jié)果與LOF 算法[16]、MC 算法[20]以及最新的TOLF 算法[19]、Iforest 算法[33?34]、Simplified-LOF[28?29]進行了對比分析.

評估指標.針對算法的效率評估,測量了每個算法總的檢測時間,同時還分別測量了數(shù)據(jù)預處理和檢測計算的CPU 時間.為了更好地評估算法性能,實驗部分還對算法的剪枝效果進行了評價.

4.2 總體效率評估

首先,在表1 所示的四個二維數(shù)據(jù)集上,評估了我們提出的MTLOF 的效率,并與LOF、MC、TOLF 算法進行了對比分析.

實驗結(jié)果如圖5 所示,參數(shù)n取0.001%·|D|,由于各數(shù)據(jù)集的數(shù)據(jù)對象數(shù)量及分布不同,在Mobike、Gowalla、Geolife 和Mass 數(shù)據(jù)集,k分別取6、20、20 和30,與TOLF 算法設(shè)置一致,固定diff為10,t為6.

從圖5 可以看出,MTLOF 算法在四個數(shù)據(jù)集上都表現(xiàn)出了最好的檢測效率,相比LOF、MC 和TOLF 算法,分別平均提升了30、18 和2.6 倍的效率.特別是在大規(guī)模的Geolife 數(shù)據(jù)集,相比最新的TOLF,MTLOF 算法提升的效率高達3.5 倍.MTLOF 和TOLF 都采用了均勻區(qū)域劃分的預處理方法,還對區(qū)域內(nèi)數(shù)據(jù)對象建立了索引結(jié)構(gòu),極大地加快了k近鄰的搜索,減少了數(shù)據(jù)預處理的時間.雖然MC 算法也通過聚類的方法對數(shù)據(jù)進行預處理,在聚類結(jié)果上進行相應(yīng)的剪枝,但是數(shù)據(jù)對象聚類所消耗的預處理時間遠高于建立索引的預處理時間.最新的TOLF 在劃分的區(qū)域內(nèi)建立Cell 網(wǎng)格索引,利用cpmin進行一次Cell 剪枝,然后利用較大的兩個上界進行兩次數(shù)據(jù)點剪枝,然而當區(qū)域內(nèi)的cpmin較小時,幾乎沒有Cell 被剪枝掉,而且執(zhí)行數(shù)據(jù)點剪枝的兩個上界相比真實LOF 值較大且計算量較高.而本文所提的MTLOF 采用了兩層Cell 剪枝策略,除了使用全局的cpmin剪枝,還利用基于Cell 內(nèi)部數(shù)據(jù)對象分布的局部剪枝策略,當cpmin較小時,仍能通過剪枝掉高密度的Cell,此外,我們使用層次的Rtree 代替Cell 網(wǎng)格索引,可以更快速地剪枝掉較大塊的高密度節(jié)點.對于不能被剪枝的節(jié)點內(nèi)的數(shù)據(jù)對象,我們采用了兩個更加接近LOF 值的上界進行剪枝判斷,從而使得被剪枝掉的數(shù)據(jù)對象更多,同時,基于我們的復用計算優(yōu)化,對UB3(p)和UB4(p)的計算完全可復用Cell 剪枝過程中的計算,有效減少了檢測計算成本.MTLOF 效率遠高于TOLF 的另外一個重要原因還在于,我們優(yōu)化了對初始局部異常點的選取,利用預處理過程的區(qū)域劃分和數(shù)據(jù)索引,優(yōu)先在稀疏區(qū)域和Rtree 中覆蓋區(qū)域較大的葉子節(jié)點內(nèi)部選擇初始候選局部異常點,相比隨機選擇方法,大大提升了初始異常點的LOF值,相應(yīng)地,也提升了初始臨界值ct,使得更多的樹節(jié)點在初始階段被快速剪枝.

圖5 總體效率對比評估Fig.5 Comparison evaluation of overall efficiency

4.3 剪枝效率評估

為了驗證算法剪枝的有效性,在上一個實驗的同時,我們還在四個數(shù)據(jù)集上統(tǒng)計了MTLOF 和TOLF 算法的Cell 剪枝及對象剪枝中被剪枝的數(shù)據(jù)對象數(shù)量.MTLOF 算法的統(tǒng)計結(jié)果如表2 所示,TOLF 算法的統(tǒng)計結(jié)果如表3 所示.

表2 MTLOF 剪枝數(shù)量(%)Table 2 The pruning number of MTLOF(%)

表3 TOLF 剪枝數(shù)量(%)Table 3 The pruning number of TOLF(%)

從表2 和表3 可以看到,在四個數(shù)據(jù)集上,MTLOF 的總剪枝的數(shù)據(jù)對象數(shù)量都遠多于TOLF 的總剪枝數(shù)量.在Mobike 和Mass 數(shù)據(jù)集上,MTLOF 算法直接剪枝掉的數(shù)據(jù)對象總量高達98% 以上,在TOLF 剪枝較少的Gowalla 數(shù)據(jù)集上,MTLOF 也直接剪枝了61.8% 的數(shù)據(jù)對象.更為明顯地是,MTLOF 的Cell 剪枝的數(shù)據(jù)量比例都在20%以上,甚至高達40% 以上,而TOLF 的Cell 剪枝比例相對較少,在Mobike 和Gowalla 數(shù)據(jù)集上,TOLF 的Cell 剪枝甚至為0%,這是因為在Mobike和Gowalla 數(shù)據(jù)集的高密度區(qū)域內(nèi),數(shù)據(jù)對象間的最小距離往往非常小甚至為零,在TOLF 的Cell 剪枝中,始終采用為Cell 邊長,當每個區(qū)域的cpmin都很小時,就使得Cell 剪枝失效.而本文所提的MTLOF 除了基于Cell 的全局剪枝,還引入了基于Cell 的局部剪枝,當區(qū)域內(nèi)的cpmin較小時,仍能通過每個節(jié)點(Cell)內(nèi)數(shù)據(jù)對象的進行Cell 剪枝.此外,在同一數(shù)據(jù)集上,MTLOF的數(shù)據(jù)對象剪枝的數(shù)量比例也高于TOLF 的數(shù)據(jù)對象剪枝比例,這是因為MTLOF 采用的兩個上界UB3(p)和UB4(p)更加接近于真實LOF 值,因此,被剪枝掉的數(shù)據(jù)對象更多,這也說明了本文所提的LOF 上界更加合理有效.優(yōu)化的初始局部異常點選擇方法也是MTLOF 算法具有較高的剪枝比例的重要原因,初始臨界值ct越高,被剪枝掉Cell 和數(shù)據(jù)對象數(shù)量也就越多.

4.4 優(yōu)化有效性評估

為了評估UB1、UB2、UB3和UB4四個上界在剪枝方面的有效性,本節(jié)在四個二維數(shù)據(jù)集上,分別統(tǒng)計了UB1、UB1+UB2、UB1+UB2+UB3和UB1+UB2+UB3+UB4四種組合情況下的被剪枝的對象數(shù)量,實驗結(jié)果如表4 所示.第二行表示在每個數(shù)據(jù)集上僅利用上界UB1剪枝的對象數(shù)量,第三行表示同時采用UB1和UB2剪枝的對象數(shù)量,第四行表示通過UB1、UB2和UB3總共剪枝的對象數(shù)量,最后一行表示同時使用四個上界時的總剪枝數(shù)量.可以看到,隨著采用上界個數(shù)的增加,表中每行剪枝數(shù)量比例都有所增加,這證明了每個上界剪枝都是有效的.利用上界UB1的Cell 全局剪枝,雖然計算成本較小,但是剪枝的數(shù)量也相對有限.基于UB2的Cell 局部剪枝,雖然需要計算本地所有數(shù)據(jù)對象的k近鄰距離和的均值,但剪枝掉的數(shù)量也相對較多.上界UB3和UB4主要用于剪枝Cell 過程中未被剪枝的對象.根據(jù)第3.2.2 節(jié)分析可知,UB4(p)

此外,我們還在Mobike 和Gowalla 數(shù)據(jù)集上統(tǒng)計了MTLOF 在采用初始Top-n異常對象優(yōu)化選取方法和沒有采用優(yōu)化選取方法時分別所需的運行時間,實驗結(jié)果如圖6 所示.相比TOLF 算法,沒有采用初始化優(yōu)化方法的MTLOF 在兩個數(shù)據(jù)集上分別提升2.1 和2.5 倍,而采用初始化優(yōu)化的MTLOF 分別提升2.6 和3.4 倍.也就是說,本文所提的剪枝策略在兩個數(shù)據(jù)集上提升2.1 和2.5 倍效率,而初始化優(yōu)化方法又進一步提升1.3 倍和1.4倍.

表4 MTLOF 每個上界剪枝數(shù)量(%)Table 4 The pruning number of each upper bound in MTLOF(%)

圖6 初始化優(yōu)化方法有效性評估Fig.6 Effectiveness evaluation of initialization optimization

4.5 正確性評估

本節(jié)在Subforestcover 數(shù)據(jù)集上評估了MTLOF 算法以及對比算法LOF、MC、TOLF、Iforest、Simplified-LOF 的準確率和效率.準確率=(R ∩D)/R,其中D表示數(shù)據(jù)集中真實的異常對象集合,R指檢測算法發(fā)現(xiàn)的異常對象集合.

實驗結(jié)果如圖7 所示,對于MTLOF、LOF、MC、TOLF 和Simplified-LOF 算法,橫坐標表示參數(shù)k值,對于Iforest 算法,橫坐標表示為訓練Itree 而采樣的對象子集數(shù)量m.圖7(a)展示了所有算法檢測結(jié)果的準確率,由于MTLOF、MC 和TOLF 都是通過計算對象的LOF 值來檢查Top-n異常的,所以這三種算法的準確率與LOF 算法一致,同時,實驗結(jié)果也驗證了本文所提剪枝策略的正確性.從圖中還可以看出,LOF 類算法(MTLOF、LOF、MC、TOLF)的準確率在k(m)≥50以后一直優(yōu)于Iforest 和Simplified-LOF 算法.當k取100 時,LOF 類算法的準確率達到最大的93%.而對于Iforest 算法,準確率最高僅達到86%.Simplified-LOF 算法的準確率相對小,最大值僅達到81%,之后不斷增大k值,準確率反而急劇下降,這是因為Simplified-LOF 直接用k-距離代替可達距離,當k值較大時,采用k-距離所表示的局部密度將變的不準確.

圖7(b)展示了所有算法在參數(shù)變化下的檢測時間,可以發(fā)現(xiàn),MTLOF 的運行時間一直優(yōu)于所有對比算法.隨著k(m)值增加,所有算法所需的運行時間都有所增加,這是因為隨著k的不斷增大,搜索k近鄰的時間不斷增加.盡管如此,MTLOF 在所有測試參數(shù)下的運行時間都少于Iforest 所消耗的時間.MTLOF 相比Simplified-LOF 和Iforest 算法,平均分別提升3.7 和1.5 倍效率.

4.6 參數(shù)敏感性分析

本節(jié)在Mobike 和Mass 數(shù)據(jù)集上評估重要參數(shù)k和n的變化對所提MTLOF 算法以及對比算法的效率影響.

圖7 準確率和效率評估Fig.7 Evaluation of precision and efficiency

4.6.1 參數(shù)k 影響評估

固定參數(shù)n=0.001%·|D|,從1 到80 變化參數(shù)k,圖8 展示了四個算法在兩個數(shù)據(jù)集上隨著參數(shù)k變化的總檢測時間.如圖8 所示,MTLOF的檢測效率在兩個數(shù)據(jù)集上的所有測試都一直優(yōu)于三個對比算法,相比LOF、MC 和TOLF 算法分別平均提升了28,19 和2.7 倍.隨著k值的增大,所有算法消耗的總檢測時間越來越長,這是因為k值的增加,使得所有數(shù)據(jù)對象的k近鄰查詢越來越費時,導致總處理時間直線增加.盡管如此,隨著參數(shù)k的增加,MTLOF 比LOF、MC 和TOLF 算法節(jié)省的CPU 時間越來越多,優(yōu)勢越來越明顯,這是因為k值的增加使得Rtree 索引的葉子節(jié)點不斷增大,同時所提的上界也更加接近于真實的LOF 值,致使MTLOF 剪枝掉更多的節(jié)點和數(shù)據(jù)對象,相對對比算法,效率優(yōu)勢越來越明顯.

4.6.2 參數(shù)n 影響評估

圖9 展示了算法隨參數(shù)n變化的總檢測時間,在Mobike 數(shù)據(jù)集上固定k=5,在Mass 數(shù)據(jù)集上固定k=10,從1 到1 000 變化參數(shù)n.如圖9 所示,MTLOF 算法在所有參數(shù)下的檢測效率都優(yōu)于三個對比算法,相比最新的TOLF 算法,平均提升了2.75 倍.所有算法的檢測時間相對于n的變化并不明顯.基本的LOF 算法檢測Top-n局部異常分為兩個步驟,首先計算所有數(shù)據(jù)對象的LOF 值,然后排序獲取前n個異常對象,隨著n的不斷變化,排序所花費的時間也會不斷地增加,但是這個排序的時間相比計算LOF 的時間要小的多,使得總的檢測時間并沒有明顯增加.MC 算法首先采用Birch聚類獲得聚類簇,然后按照聚簇的半徑和距離關(guān)系排序聚類簇,僅需在最可能包含異常的簇內(nèi)檢測異常,因此,隨著n的增加,需要檢測的聚簇個數(shù)越多,消耗的總檢測時間也越長,但是MC 在n較小時剪枝掉的數(shù)據(jù)數(shù)量都相對較少,因此,總消耗的檢測時間也沒有明顯增加.TOLF 和MTLOF 算法的檢測時間隨著n的增加而緩慢增加,這是因為n的增加使得初始需要計算LOF 值的數(shù)據(jù)對象增加,盡管如此,由于兩個算法都對數(shù)據(jù)進行了均勻區(qū)域劃分并在區(qū)域內(nèi)建立了索引結(jié)構(gòu),即使n不斷增加,仍然可以通過索引快速查找k近鄰,并通過LOF 上界執(zhí)行剪枝,因此,總檢測時間也沒有急劇增加.隨著n的增加,我們MTLOF 能夠通過提出的UB3(p)和UB4(p)上界剪枝掉更多數(shù)據(jù)對象,相比TOLF,節(jié)省更多檢測時間.

圖8 參數(shù)k對檢測時間的影響Fig.8 Impact of parameter kon detection time

圖9 參數(shù)n對檢測時間的影響Fig.9 Impact of parameter non detection time

圖10 多維數(shù)據(jù)集上的效率評估Fig.10 Efficient evaluation on multi-dimensional datasets

4.7 多維數(shù)據(jù)上的有效性評估

最后,在多維數(shù)據(jù)集Skinseg 和Forestcover 上評估了所提算法的有效性.圖10 展示了四個算法在Skinseg 和Forestcover 上的總檢測時間.參數(shù)n固定為0.001%·|D|,k固定為6.在Skinseg 數(shù)據(jù)集上,MTLOF 仍然能比最新的TOLF 算法快了近2.5 倍.雖然Skinseg 數(shù)據(jù)集較小,但本文提出的多粒度的剪枝策略在這個數(shù)據(jù)集上明顯優(yōu)于TOLF 算法.在10 維的Forestcover 數(shù)據(jù)集上,MTLOF 算法也展現(xiàn)了所提剪枝策略的優(yōu)勢,相比LOF、MC和TOLF 算法分別提升了15 倍、12 倍和3 倍的檢測效率,這也說明了MTLOF 在高維數(shù)據(jù)集上具有更高的可擴展性.

5 結(jié)論

本文提出了一個面向大數(shù)據(jù)的高效的Top-n局部異常點檢測算法MTLOF.首先,為了避免直接計算數(shù)據(jù)對象的LOF 值,提出了四個計算復雜度更低并且更接近于真實LOF 值的上界.其次,結(jié)合索引結(jié)構(gòu)和LOF 上界,引入了兩層的Cell 剪枝策略.然后,針對未被剪枝的Cell 內(nèi)部數(shù)據(jù)對象,利用UB3(p)和UB4(p)上界提出了兩個更加合理有效的剪枝策略.此外,還利用均勻區(qū)域劃分和建立的索引結(jié)構(gòu),優(yōu)化了初始候選局部異常點的選取方法,使得LOF 值較大的數(shù)據(jù)對象被選取為初始局部異常點.最后,在六個真實數(shù)據(jù)集上的綜合實驗評估驗證了所提MTLOF 算法的有效性,相比LOF、MC 和TOLF 算法,檢測效率可分別提升30、18 和2.6 倍.

下一步工作將考慮借助分布式計算平臺,設(shè)計分布式異常檢測算法以進一步提升檢測效率,此外,還計劃面向不斷快速增長的海量高速數(shù)據(jù)集,研究實時的Top-n局部異常點檢測方法.