毛亞瓊,田立勤,2,王 艷,毛亞萍,王志剛

(1.青海師范大學(xué) 計(jì)算機(jī)學(xué)院,西寧 810008; 2.華北科技學(xué)院 計(jì)算機(jī)學(xué)院,北京 065201; 3.青海省基礎(chǔ)測繪院,西寧 810000)

0 概述

在離群數(shù)據(jù)中可能隱含有價(jià)值的知識(shí),并且其價(jià)值甚至可能超過正常數(shù)據(jù),因此,離群點(diǎn)檢測(也稱為異常點(diǎn)檢測)是數(shù)據(jù)挖掘領(lǐng)域一項(xiàng)重要的研究課題。離群點(diǎn)檢測最主要的目的是檢測數(shù)據(jù)集中不滿足數(shù)據(jù)一般行為或模式的數(shù)據(jù)對(duì)象[1],其被廣泛應(yīng)用于網(wǎng)絡(luò)入侵檢測、WSN異常檢測、醫(yī)療與電網(wǎng)監(jiān)控[2]等領(lǐng)域。目前傳統(tǒng)的離群點(diǎn)檢測技術(shù)有基于統(tǒng)計(jì)、基于深度、基于距離、基于聚類、基于密度、基于分類等多種方法[3]。隨著模式識(shí)別、機(jī)器學(xué)習(xí)和人工智能技術(shù)的不斷發(fā)展,空間數(shù)據(jù)、高維數(shù)據(jù)以及時(shí)間序列數(shù)據(jù)的離群點(diǎn)檢測被研究者關(guān)注,更多新穎且有效的離群點(diǎn)檢測方法被提出,如基于密度偏倚抽樣的離群點(diǎn)檢測方法[4]、基于分區(qū)的離群點(diǎn)檢測方法[5]、基于角度分布的離群點(diǎn)檢測方法[6]、基于向量點(diǎn)積密度的離群點(diǎn)檢測方法[7]、結(jié)合模糊粗糙集的檢測技術(shù)以及結(jié)合自組織映射方法的離群點(diǎn)檢測技術(shù)[8]等。

隨著物聯(lián)網(wǎng)技術(shù)的興起,數(shù)據(jù)量和維度均呈上升趨勢,高速、無限且動(dòng)態(tài)的高維數(shù)據(jù)流在許多領(lǐng)域產(chǎn)生,同時(shí)數(shù)據(jù)流中數(shù)據(jù)的分布特征也隨時(shí)間動(dòng)態(tài)變化。這些特征要求數(shù)據(jù)流離群挖掘算法在有限內(nèi)存下檢測時(shí)僅能用一次或較少次數(shù)遍歷數(shù)據(jù),而傳統(tǒng)針對(duì)靜態(tài)數(shù)據(jù)集的方法需要多次掃描數(shù)據(jù)集才能完成檢測,很難擴(kuò)展到數(shù)據(jù)流的離群點(diǎn)挖掘[9]?，F(xiàn)有的一些針對(duì)數(shù)據(jù)流的檢測方法[10-12]由于“維度災(zāi)難”問題而對(duì)高維數(shù)據(jù)流的檢測效果欠佳?；诮嵌萚13]和基于局部向量點(diǎn)積密度的算法在高維空間中比基于距離的方法更穩(wěn)定,但計(jì)算復(fù)雜度高達(dá)O(d2n2)甚至O(d2n3)(d為維度,n為數(shù)據(jù)點(diǎn)個(gè)數(shù)),計(jì)算開銷太大。因此,提高高維數(shù)據(jù)流離群點(diǎn)檢測的準(zhǔn)確性和計(jì)算效率是當(dāng)前研究的熱點(diǎn)。

本文提出一種引入局部向量點(diǎn)積密度的數(shù)據(jù)流離群點(diǎn)快速檢測(Fast outlier detection in data stream with Local Density of Vector dot Product,FASTLDVP)算法。當(dāng)滑動(dòng)窗口內(nèi)有數(shù)據(jù)更新時(shí),設(shè)計(jì)一種增量算法,在原有計(jì)算結(jié)果的基礎(chǔ)上,只對(duì)受到影響的數(shù)據(jù)點(diǎn)進(jìn)行增量更新,從而避免對(duì)全部數(shù)據(jù)點(diǎn)進(jìn)行重新計(jì)算。此外,還設(shè)計(jì)2種優(yōu)化策略和1條剪枝規(guī)則來減少r-鄰域更新時(shí)窗口內(nèi)各點(diǎn)之間距離計(jì)算的次數(shù)。本文擬通過設(shè)計(jì)FASTLDVP算法,以較小的計(jì)算代價(jià)達(dá)到與LDVP-OD算法相同的檢測效果。

1 相關(guān)工作

文獻(xiàn)[14]針對(duì)靜態(tài)環(huán)境提出一種基于密度的局部離群點(diǎn)檢測算法,其通過引入局部異常因子(Local Outlier Factor,LOF)表示每個(gè)數(shù)據(jù)對(duì)象的局部異常程度,即數(shù)據(jù)點(diǎn)的異常程度與其一定范圍內(nèi)鄰居(kdist-鄰域內(nèi)的點(diǎn))分布有關(guān),kdist-鄰域密度越大,該點(diǎn)成為離群點(diǎn)的可能性越小。算法中最耗時(shí)的是數(shù)據(jù)集中各數(shù)據(jù)點(diǎn)之間距離的計(jì)算,復(fù)雜度為O(d2n2)。文獻(xiàn)[15]通過引入滑動(dòng)窗口的思想提出n-INCLOF算法,僅更新當(dāng)前滑動(dòng)窗口內(nèi)受影響數(shù)據(jù)點(diǎn)的LOF值。文獻(xiàn)[16]提出一種基于加權(quán)聚類的數(shù)據(jù)流離群點(diǎn)檢測算法。該算法對(duì)數(shù)據(jù)流的數(shù)據(jù)分布特征適應(yīng)性較強(qiáng),準(zhǔn)確度較高,但是閾值設(shè)定較多,可能會(huì)對(duì)算法的有效性產(chǎn)生較大影響。上述算法能適應(yīng)分布復(fù)雜的數(shù)據(jù)流,但是當(dāng)數(shù)據(jù)流的維度或者kdist值不斷增大時(shí),需要進(jìn)行大量的數(shù)據(jù)點(diǎn)之間距離的計(jì)算。

研究表明,在高維空間中角度比距離更加穩(wěn)定[17]。文獻(xiàn)[6] 引入角度方差異常因子(Angle-based Outlier Factor,ABOF)的概念,提出一種基于角度的離群點(diǎn)檢測(Angle-based Outlier Detection,ABOD)算法。文獻(xiàn)[13]將ABOD算法擴(kuò)展至動(dòng)態(tài)數(shù)據(jù)流應(yīng)用中,提出基于角度的數(shù)據(jù)流離群點(diǎn)快速檢測算法FASTDSABOD,其通過增量計(jì)算的方法動(dòng)態(tài)更新每個(gè)數(shù)據(jù)點(diǎn)的ABOF,從而將時(shí)間復(fù)雜度從O(d2n3)降至O(d2n2)。雖然復(fù)雜度有所下降,但是其在有限的內(nèi)存空間中依然無法處理大規(guī)模的數(shù)據(jù)集,并且對(duì)數(shù)據(jù)分布不規(guī)則的數(shù)據(jù)集識(shí)別效果欠佳。文獻(xiàn)[18]在ABOD算法的基礎(chǔ)上提出一種隨機(jī)投影技術(shù)和乘積域AMS Sketch相結(jié)合的近似估計(jì)角度方差的方法FastVOA。該方法計(jì)算復(fù)雜度近似線性,但沒有考慮任何權(quán)重因素的近似理解,雖然降低了計(jì)算復(fù)雜度,但是不能保證離群檢測結(jié)果的準(zhǔn)確性。

文獻(xiàn)[7]提出度量數(shù)據(jù)離群程度的局部向量點(diǎn)積密度算法LDVP-OD。該算法同時(shí)結(jié)合密度、距離和角度的離群度量方式的優(yōu)點(diǎn),在數(shù)據(jù)流離群點(diǎn)檢測上有較高的準(zhǔn)確性,但存在計(jì)算復(fù)雜度過高的問題(復(fù)雜度為O(d2n2))。

現(xiàn)有數(shù)據(jù)流局部離群點(diǎn)檢測方法的主要區(qū)別在于離群程度度量方法和r-鄰域確定方法的差異[19]。上述算法均存在對(duì)索引數(shù)據(jù)結(jié)構(gòu)及鄰域方法存在依賴性、重復(fù)計(jì)算和檢測結(jié)果準(zhǔn)確性依賴于參數(shù)設(shè)定和計(jì)算復(fù)雜度過高的問題,難以保證較高的運(yùn)行效率。本文算法的改進(jìn)主要是優(yōu)化鄰域的確定方法和離群因子的計(jì)算方法。

2 預(yù)備知識(shí)

定義1[7]r-鄰域(r-neighborhood)

Dd中數(shù)據(jù)點(diǎn)o的r-鄰域由與o點(diǎn)之間距離小于r的數(shù)據(jù)點(diǎn)組成,即:

Nr(o)={o′∈Dd|dist(o,o′)≤r}

(1)

本文運(yùn)用基于斜率和最大距離的思想,實(shí)時(shí)確定滑動(dòng)窗口中數(shù)據(jù)點(diǎn)鄰域半徑的值。設(shè)kdist為數(shù)據(jù)點(diǎn)o與其第k個(gè)最近鄰點(diǎn)的距離,所有數(shù)據(jù)點(diǎn)的kdist降序排列,取“谷底點(diǎn)”對(duì)應(yīng)的kdist為鄰域半徑r,在一般情況下,k確定為4。當(dāng)滑動(dòng)窗口向前移動(dòng)時(shí),舊數(shù)據(jù)移除同時(shí)新數(shù)據(jù)流入,滑動(dòng)窗口內(nèi)數(shù)據(jù)點(diǎn)的鄰域半徑r變?yōu)閞′,r′相對(duì)于r會(huì)出現(xiàn)r′>r、r′

定義2[7]向量點(diǎn)積均值(Mean of Vector dot Product,MVP)

(2)

定義3[7]局部向量點(diǎn)積密度(LDVP)

數(shù)據(jù)點(diǎn)o的局部向量點(diǎn)積密度定義為:

(3)

3 FASTLDVP算法

3.1 設(shè)計(jì)思想

在LDVP-OD算法中,每個(gè)數(shù)據(jù)點(diǎn)的LDVP值都與所處的r-鄰域有關(guān),當(dāng)滑動(dòng)窗口向前移動(dòng)一位,舊的數(shù)據(jù)點(diǎn)被移除,新的數(shù)據(jù)點(diǎn)流入,窗口內(nèi)數(shù)據(jù)點(diǎn)的r-鄰域就會(huì)發(fā)生變化,相關(guān)數(shù)據(jù)點(diǎn)的異常程度也會(huì)受到影響。LDVP-OD算法對(duì)此的處理方式是:一旦窗口中有數(shù)據(jù)被移除或者新數(shù)據(jù)流入,重新查詢窗口內(nèi)所有數(shù)據(jù)點(diǎn)的r-鄰域并重新計(jì)算LDVP。然而,由于LDVP的局部特性,滑動(dòng)窗口的更新只會(huì)影響到少數(shù)數(shù)據(jù)點(diǎn)的LDVP值,而不會(huì)影響所有數(shù)據(jù)點(diǎn)的LDVP值。因此,本文提出一種增量算法,只對(duì)窗口內(nèi)受影響數(shù)據(jù)點(diǎn)的LDVP值進(jìn)行更新,并且受影響的數(shù)據(jù)點(diǎn)也不需要代價(jià)高昂地重新計(jì)算,只需在原有結(jié)果(包括r-鄰域更新和局部向量點(diǎn)積密度計(jì)算)的基礎(chǔ)上進(jìn)行更新查詢或累加計(jì)算即可。此外,在r-鄰域查詢時(shí)不可避免地會(huì)出現(xiàn)大量的距離計(jì)算,尤其當(dāng)數(shù)據(jù)量很大或數(shù)據(jù)維度很高時(shí),計(jì)算開銷很大。為此,本文在r-鄰域查詢時(shí)增加2個(gè)優(yōu)化策略和1條剪枝規(guī)則來減少窗口內(nèi)各點(diǎn)之間距離計(jì)算的次數(shù)。FASTLDVP算法流程如圖1所示。為方便理解,本文將算法分成r-鄰域更新和局部向量點(diǎn)積密度LDVP計(jì)算兩部分分別進(jìn)行論述。

圖1 FASTLDVP算法流程

3.2 r-鄰域更新

r-鄰域更新的計(jì)算量來源于數(shù)據(jù)點(diǎn)之間的距離計(jì)算,本文使用歐式距離作為距離度量的方式。在該階段,只對(duì)滑動(dòng)窗口內(nèi)有影響的數(shù)據(jù)點(diǎn)進(jìn)行增量更新,并且使用2種優(yōu)化策略縮小數(shù)據(jù)點(diǎn)鄰域查詢的范圍,使用1個(gè)剪枝規(guī)則減少數(shù)據(jù)點(diǎn)之間距離計(jì)算的次數(shù)。

3.2.1 相關(guān)定義

定義4歐式距離

設(shè)d維空間中任意兩點(diǎn)o=(o1,o2,…,od),o′=(o′1,o′2,…,o′d),兩點(diǎn)間的歐式距離可定義為:

(4)

定義5數(shù)據(jù)向量的模

數(shù)據(jù)集中每一個(gè)數(shù)據(jù)點(diǎn)映射到空間中可以看作1個(gè)d維向量,設(shè)o=(o1,o2,…,od)為數(shù)據(jù)集D中的數(shù)據(jù)點(diǎn),則點(diǎn)o的模定義為:

(5)

3.2.2 算法描述

以窗口內(nèi)受影響數(shù)據(jù)點(diǎn)o為例討論Nr′(o)的更新,即判斷窗口內(nèi)某點(diǎn)o′(o′∈D)是否屬于Nr′(o)(o∈D)。算法主要步驟如下:

步驟1移除舊數(shù)據(jù)點(diǎn)p對(duì)窗口內(nèi)數(shù)據(jù)的影響。僅點(diǎn)o的鄰域Nr(o)(o∈Nr(p),p∈D)受影響。

步驟2將窗口內(nèi)已有數(shù)據(jù)點(diǎn)相互之間的影響分為以下3種情況:

1)當(dāng)r′>r時(shí),點(diǎn)o更新后的鄰域?yàn)镹r′(o)=Nr(o)+o′,o′?Nr(o),o′∈D。利用優(yōu)化策略1縮小點(diǎn)o′查詢范圍,同時(shí)使用剪枝規(guī)則1減小距離計(jì)算次數(shù)。

優(yōu)化策略1新增點(diǎn)o′分布在Nr(o)中這些數(shù)據(jù)點(diǎn)的周圍,即o′一定分布在Nr(o)中數(shù)據(jù)點(diǎn)的鄰域內(nèi)。因此,只需在Nr(o)中數(shù)據(jù)點(diǎn)的鄰域內(nèi)搜索,即可找到點(diǎn)o鄰域新增的數(shù)據(jù)點(diǎn)。

剪枝規(guī)則1由定理1可以得出dist(o,o′)≥|M(o)-M(o′)|,則當(dāng)|M(o)-M(o′)|>r′時(shí),必定有o′?Nr′(o),此時(shí)可直接對(duì)o′剪枝而無需計(jì)算dist(o,o′)。只有當(dāng)|M(o)-M(o′)|≤r′時(shí)才需要計(jì)算dist(o,o′),通過dist(o,o′)≤r′進(jìn)一步判斷是否屬于鄰域。對(duì)于|M(o)-M(o′)|,M(o)已知,M(o′)可以在數(shù)據(jù)點(diǎn)o′流入滑動(dòng)窗口時(shí)計(jì)算(每個(gè)數(shù)據(jù)點(diǎn)只需計(jì)算一次,計(jì)算復(fù)雜度為O(d2),d<

定理1設(shè)d維數(shù)據(jù)集D中任意兩個(gè)數(shù)據(jù)點(diǎn)o、o′,〈·,·〉表示兩向量的點(diǎn)積,則o、o′之間的距離dist(o,o′)滿足:

dist(o,o′)≥|M(o)-M(o′)|

(6)

證明:

展開歐氏距離公式(見定義4):

將其代入式(5),得到:

又由:

可得:

因此:

dist(o,o′)≥|M(o)-M(o′)|

證畢。

2)當(dāng)r′

優(yōu)化策略2當(dāng)鄰域半徑變小時(shí),Nr(o)以外的所有數(shù)據(jù)點(diǎn)都不可能出現(xiàn)在Nr′(o)內(nèi),因此,只需將Nr(o)中滿足dist(o,o′)>r′的點(diǎn)o′刪除,即為Nr′(o)。

3)當(dāng)r′=r時(shí),窗口中任何數(shù)據(jù)點(diǎn)的鄰域都不受r′影響。

步驟3新數(shù)據(jù)q流入時(shí)對(duì)窗口內(nèi)數(shù)據(jù)的影響及自身鄰域查詢。由于o和q互為鄰域,因此更新Nr′(o),o∈D同時(shí)可得到Nr′(q)。在距離計(jì)算時(shí)同樣使用剪枝規(guī)則1。

r-鄰域更新算法代碼如下:

輸入D,舊數(shù)據(jù)p,新數(shù)據(jù)q、r

輸出N′r(o)

1.for each o(o∈D) do

//步驟1,滑動(dòng)窗口移除舊數(shù)據(jù)p

2.for each o∈Nr(p)do

3.N′r(o)←Nr(o)-p

4.N′r(p)←Nr(p)-o

5.end for

//步驟2,將窗口內(nèi)已有點(diǎn)的相互影響分為3種情況

6.if r′>r do//鄰域增大

7.for each o′?Nr(o),o′∈D do

8.if |M(o)-M(o′)|≤r′ do

10.if dist(o,o′)≤r′ do

11.N′r(o)←Nr(o)+o

12.N′r(o′)←Nr(o′)+o//兩點(diǎn)互為鄰域

13.end if

14.end if

15.end for

16.end if

17.if r′

18.for each o′∈Nr(o),o′≠o do

19.if |M(o)-M(o′)|>r′ do

20.N′r(o)←Nr(o)-o′

21.N′r(o′)←Nr(o′)-o//兩點(diǎn)互為鄰域

22.end if

23.if |M(o)-M(o′)|≤r′ do

25.if dist(o,o′)>r′ do

26.N′r(o)←Nr(o)-o′

27.N′r(o′)←Nr(o′)-o//兩點(diǎn)互為鄰域

28.end if

29.end if

30.end for

31.end if

32.if r′=r do//鄰域不變

33.nothing need to do

34.end if

//步驟3,滑動(dòng)窗口流入數(shù)據(jù)點(diǎn)q

35.if |M(o)-M(q)|≤r′ do

37.if dist(o,q)≤r′ do

38.N′r(o)←Nr(o)+q

39.N′r(q)←Nr(q)+o//一個(gè)循環(huán),同時(shí)可得到新增點(diǎn)//p的鄰域

40.end if

41.end if

42.end for

3.3 局部向量點(diǎn)積密度計(jì)算

局部向量點(diǎn)積密度(LDVP)計(jì)算的過程中存在大量重復(fù)計(jì)算。本文通過設(shè)計(jì)一種增量算法,將MVP增量計(jì)算公式(見定義6)中重復(fù)計(jì)算的部分保存為中間結(jié)果,方便下次直接使用。該算法并不改變定義2中MVP的計(jì)算結(jié)果,核心思想是用運(yùn)算規(guī)則的分配率合并同類項(xiàng)來避免重復(fù)計(jì)算,對(duì)計(jì)算過程做一種簡單而有效的優(yōu)化。

3.3.1 相關(guān)定義及推理

定義6MVP增量計(jì)算公式

ACC-MVP(o′)=

(7)

其中,pi,pj∈Nr(o){o′},pi≠pj。

推理1增量計(jì)算公式ACC-MVP的計(jì)算結(jié)果與向量點(diǎn)積均值MVP完全等價(jià)。

通過給出從MVP公式(定義2)到ACC-MVP公式(定義6)等價(jià)的推導(dǎo)過程,可驗(yàn)證此定理,具體如下:

3.3.2 算法描述

表1列出了FASTLDVP算法在連續(xù)檢測期間用于存儲(chǔ)中間結(jié)果的數(shù)據(jù)結(jié)構(gòu)。

表1 增量計(jì)算數(shù)據(jù)結(jié)構(gòu)

將MVP累加計(jì)算公式(見定義6)中重復(fù)計(jì)算部分存儲(chǔ)在中間結(jié)果數(shù)據(jù)結(jié)構(gòu)中,如式(8)和式(9)所示:

(8)

(9)

由此,點(diǎn)o′的向量點(diǎn)積均值通過以下公式計(jì)算:

(10)

對(duì)于鄰域內(nèi)任意點(diǎn)o′的向量點(diǎn)積均值,當(dāng)鄰域內(nèi)有數(shù)據(jù)點(diǎn)被刪除時(shí),點(diǎn)o′的中間結(jié)果只更新與刪除點(diǎn)pi有關(guān)的計(jì)算。同樣地,當(dāng)鄰域內(nèi)有數(shù)據(jù)點(diǎn)新增時(shí),點(diǎn)o′的中間結(jié)果只更新與新增點(diǎn)pj有關(guān)的計(jì)算。更新中間結(jié)果后使用式(10)計(jì)算向量點(diǎn)積均值,最后使用定義4對(duì)鄰域中各數(shù)據(jù)點(diǎn)的局部向量點(diǎn)積密度進(jìn)行計(jì)算。算法偽代碼中沒有提及的還有新增點(diǎn)的向量點(diǎn)積密度計(jì)算,新增點(diǎn)的計(jì)算通過定義2和定義3進(jìn)行常規(guī)計(jì)算。FASTLDVP算法代碼如下:

輸入舊數(shù)據(jù)pi,新數(shù)據(jù)pj;

輸出LDVP(o)

1.for each o′(o′∈Nr′(o))

2.if point pideleted from Nr′(o) do

3.tempart1-=(o′k-pjk)

5.end if

6.If point pjinsert into Nr′(o) do

7.tempart1 +=(o′k-pjk)

9.end if

11.LDVP(o)+=e-ACC-EMP(o′)

12.end for

3.4 復(fù)雜度分析

3.4.1r-鄰域更新算法復(fù)雜度

當(dāng)v,p,q,p′,q′,d,n′<

3.4.2 LDVP計(jì)算算法復(fù)雜度

滑動(dòng)窗口內(nèi)所有數(shù)據(jù)點(diǎn)的LDVP計(jì)算算法復(fù)雜度為O(wn′d)+O(n′2),其中,n′表示鄰域內(nèi)數(shù)據(jù)點(diǎn)個(gè)數(shù),w表示受影響數(shù)據(jù)點(diǎn)個(gè)數(shù)。

綜上所述,本文利用優(yōu)化策略縮小受影響數(shù)據(jù)點(diǎn)鄰域查詢范圍,使得v,p,q,p′,q′,d,w,n′<

4 實(shí)驗(yàn)與結(jié)果分析

理論推導(dǎo)本文算法可以在不影響準(zhǔn)確率的情況下提高算法效率。本節(jié)主要針對(duì)FASTLDVP算法的運(yùn)行效率,利用3組實(shí)驗(yàn)對(duì)其進(jìn)行驗(yàn)證。實(shí)驗(yàn)環(huán)境為Pentium?Dual-core CPU,主頻2.2 GHz,內(nèi)存4 GB,操作系統(tǒng)為Window7。實(shí)驗(yàn)數(shù)據(jù)包括仿真數(shù)據(jù)集和真實(shí)數(shù)據(jù)集。算法采用Java語言實(shí)現(xiàn)。用文獻(xiàn)[20]中所提到的數(shù)據(jù)集產(chǎn)生方法生成5 000條維度為(10,50,100,200)的仿真數(shù)據(jù)集,分析算法中剪枝過程對(duì)不同維度數(shù)據(jù)的影響,同時(shí)使用真實(shí)數(shù)據(jù)集分析算法中剪枝過程對(duì)大數(shù)據(jù)量數(shù)據(jù)執(zhí)行效率的影響,并分別對(duì)LDVP-OD[7]、FASTDSABOD[13]以及文獻(xiàn)[16]算法的運(yùn)行效率進(jìn)行對(duì)比。真實(shí)數(shù)據(jù)集選用KDD CPU99數(shù)據(jù)集中的5×104條數(shù)據(jù)。為使評(píng)估結(jié)果更準(zhǔn)確可信,對(duì)FASTLDVP算法的實(shí)驗(yàn)結(jié)果取100次運(yùn)行結(jié)果的均值。

4.1 剪枝策略和優(yōu)化策略對(duì)算法的影響

本組實(shí)驗(yàn)主要探討r-鄰域更新環(huán)節(jié)中增加的優(yōu)化策略和剪枝策略(簡稱剪枝)對(duì)算法帶來的影響。實(shí)驗(yàn)對(duì)比了相同維度不同數(shù)據(jù)量,以及相同數(shù)據(jù)量不同維度的數(shù)據(jù)在增加剪枝過程前后FASTLDVP算法執(zhí)行效率的變化情況。

如圖2所示,在相同維度(d=15)不同數(shù)據(jù)量的情況下,數(shù)據(jù)量較小時(shí)剪枝前后算法運(yùn)行時(shí)間相差不大,但隨著數(shù)據(jù)量大規(guī)模增大,剪枝后算法的運(yùn)行時(shí)間遠(yuǎn)少于剪枝前算法的運(yùn)行時(shí)間。

圖2 FASTLDVP相同維度不同數(shù)據(jù)量下剪枝前后的運(yùn)行時(shí)間

如圖3所示,在相同數(shù)據(jù)量(n=5 000)不同維度的情況下,剪枝前維度較小算法執(zhí)行速度快,隨著維度增加,距離計(jì)算量增加,算法執(zhí)行效率降低。增加剪枝后,由于剪枝了大量不必要的距離計(jì)算,因此運(yùn)行效率得到提高。

圖3 FASTLDVP相同數(shù)據(jù)量不同維度下剪枝前后的運(yùn)行時(shí)間

4.2 算法整體效率分析

FASTLDVP算法與LDVP-OD、FASTDSABOD、文獻(xiàn)[16]算法在不同數(shù)據(jù)量下的運(yùn)行時(shí)間對(duì)比如圖4所示。

圖4 4種算法的運(yùn)行時(shí)間對(duì)比

圖4結(jié)果表明,當(dāng)數(shù)據(jù)量較小時(shí),FASTLDVP算法和其他算法的運(yùn)行效率相差不大,但是隨著數(shù)據(jù)量的大規(guī)模增加,FASTLDVP算法的運(yùn)行效率逐漸高于LDVP-OD和FASTDSABOD算法。FASTDSABOD與LDVP-OD算法的運(yùn)行時(shí)間更多地消耗在數(shù)據(jù)點(diǎn)間的距離計(jì)算以及復(fù)雜公式的重復(fù)計(jì)算上。FASTLDVP算法由于只計(jì)算受影響數(shù)據(jù)點(diǎn),且增加了數(shù)據(jù)剪枝環(huán)節(jié),因此避免了不必要的距離計(jì)算和向量點(diǎn)積計(jì)算,從而大幅降低了計(jì)算復(fù)雜度,并且較LDVP-OD和FASTDSABOD算法,這種優(yōu)勢將隨數(shù)據(jù)量的增加而表現(xiàn)得更明顯。FASTLDVP和文獻(xiàn)[16]算法運(yùn)行時(shí)間相近,并且隨著數(shù)據(jù)規(guī)模的增大,運(yùn)行時(shí)間的增長也較為相近。但在不同數(shù)據(jù)規(guī)模下,文獻(xiàn)[16]算法的運(yùn)行效率略高于FASTLDVP算法。

5 結(jié)束語

本文提出一種針對(duì)動(dòng)態(tài)數(shù)據(jù)流的離群點(diǎn)檢測算法FASTLDVP。利用局部離群檢測的特點(diǎn),設(shè)計(jì)一種增量計(jì)算方法,只對(duì)受影響數(shù)據(jù)點(diǎn)進(jìn)行增量更新,同時(shí)通過優(yōu)化策略和剪枝規(guī)則減少鄰域查詢時(shí)數(shù)據(jù)點(diǎn)之間距離計(jì)算的復(fù)雜度。理論分析和實(shí)驗(yàn)結(jié)果表明,該算法能以較小的計(jì)算代價(jià)達(dá)到與LDVP-OD算法相同的檢測效果,適合于高維數(shù)據(jù)流的異常檢測。由于數(shù)據(jù)流的數(shù)據(jù)分布是隨時(shí)間變化的,因此如何在動(dòng)態(tài)數(shù)據(jù)流中快速準(zhǔn)確地捕捉到概念漂移,將是下一步的研究方向。