基于網(wǎng)格耦合的數(shù)據(jù)流異常檢測*

楊 杰，張東月，周麗華，黃 皓，丁海燕

(云南大學(xué)信息學(xué)院,云南 昆明 650504)

1 引言

數(shù)據(jù)流是一種隨著時間增加而順序、快速、大量、連續(xù)到達(dá)的數(shù)據(jù)序列。近年來，隨著計(jì)算機(jī)技術(shù)的發(fā)展，大量的數(shù)據(jù)流不斷產(chǎn)生，如網(wǎng)絡(luò)流量、金融數(shù)據(jù)、氣象數(shù)據(jù)等。數(shù)據(jù)流中存在一些對象與其他數(shù)據(jù)對象顯著不同，好像它們是由不同的機(jī)制產(chǎn)生的，這些對象被稱作異常[1]。對數(shù)據(jù)流中異常進(jìn)行檢測可以預(yù)測數(shù)據(jù)對象的行為和發(fā)展趨勢，對于人們的工作、生活具有重要意義。數(shù)據(jù)流的異常檢測廣泛應(yīng)用于網(wǎng)絡(luò)入侵檢測、金融風(fēng)險分析和異常天氣檢測等領(lǐng)域，已經(jīng)成為數(shù)據(jù)挖掘中的一個重要研究熱點(diǎn)[2 - 5]。然而，由于數(shù)據(jù)流具有連續(xù)、無限和時變等特點(diǎn)，數(shù)據(jù)流的異常檢測仍面臨許多挑戰(zhàn)，比如數(shù)據(jù)流不能以有限內(nèi)存進(jìn)行存儲，流中的數(shù)據(jù)對象不能隨機(jī)訪問，數(shù)據(jù)對象對于決策的影響隨時間的流逝逐漸衰減，如何提高數(shù)據(jù)流異常檢測的精確度和效率等。

針對數(shù)據(jù)流異常檢測存在的諸多挑戰(zhàn)，許多數(shù)據(jù)流異常檢測算法被提出[4,6,7]。這些算法利用距離、密度或聚類等手段來區(qū)分正常數(shù)據(jù)和異常，雖然能夠較精確地檢測數(shù)據(jù)流中的異常，但是它們均以數(shù)據(jù)對象為處理單元，需要對數(shù)據(jù)流中每個數(shù)據(jù)應(yīng)用詳盡的策略進(jìn)行異常判斷，這大大降低了算法處理數(shù)據(jù)流的速度，影響了算法的效率。而為了快速處理數(shù)據(jù)流，Chen等人[8]將網(wǎng)格引入到了數(shù)據(jù)流聚類中，將不斷到達(dá)的數(shù)據(jù)流映射到一組支持快速查找的網(wǎng)格結(jié)構(gòu)中，以此匯總數(shù)據(jù)流并提取數(shù)據(jù)流的概要信息，然后以網(wǎng)格為單元進(jìn)行后續(xù)處理。與以數(shù)據(jù)對象為處理單元的算法相比，網(wǎng)格的應(yīng)用大大加快了數(shù)據(jù)流的處理速度，進(jìn)而提高了算法的效率。但是，Chen等人[8]在將數(shù)據(jù)對象映射到網(wǎng)格并增量更新網(wǎng)格時，獨(dú)立處理每個網(wǎng)格，忽略了網(wǎng)格之間的相互影響,使得提取的數(shù)據(jù)流概要不夠精確,從而影響了算法的精確度。張東月等人[9]也采用了網(wǎng)格的方式進(jìn)行數(shù)據(jù)流的聚類，但是在將數(shù)據(jù)對象映射到網(wǎng)格后不是獨(dú)立處理網(wǎng)格，而是考慮了網(wǎng)格之間的相互影響(即網(wǎng)格耦合)，該方法有效提高了聚類的精確度。

受此啟發(fā)，本文提出了一種基于網(wǎng)格耦合的數(shù)據(jù)流異常檢測算法GCStream-OD(Grid Coupling based data Stream Outlier Detection)。首先，基于網(wǎng)格內(nèi)的數(shù)據(jù)對象定義網(wǎng)格權(quán)重，并在數(shù)據(jù)映射到網(wǎng)格的過程中不再獨(dú)立處理網(wǎng)格，而是基于網(wǎng)格內(nèi)數(shù)據(jù)對象的分布狀態(tài)考慮網(wǎng)格之間權(quán)重的相互影響，即一個網(wǎng)格權(quán)重的變化會使相鄰網(wǎng)格的權(quán)重增加或減小。網(wǎng)格的耦合能更加準(zhǔn)確地捕捉數(shù)據(jù)之間的相關(guān)性，從而提高檢測精確度。其次，基于網(wǎng)格內(nèi)數(shù)據(jù)分布的密度和網(wǎng)格間的距離度量每個網(wǎng)格的異常程度，使得異常度量更為準(zhǔn)確。最后，在實(shí)時映射數(shù)據(jù)流更新網(wǎng)格的過程中，通過剪枝策略周期性地去除那些數(shù)據(jù)量較多、不可能為異常的網(wǎng)格，縮小了異常的查找范圍，從而提高算法的效率。

本文的主要貢獻(xiàn)包括：

(1)提出了一種基于網(wǎng)格耦合的數(shù)據(jù)流異常檢測算法GCStream-OD。該算法以網(wǎng)格為處理單元，以網(wǎng)格耦合的思想更新網(wǎng)格，并基于網(wǎng)格內(nèi)數(shù)據(jù)分布的密度和網(wǎng)格間的距離度量每個網(wǎng)格的異常程度。網(wǎng)格的耦合以及網(wǎng)格內(nèi)數(shù)據(jù)分布的密度和網(wǎng)格間距離的融合，更為精確地捕捉了數(shù)據(jù)之間的相關(guān)性，從而提高檢測精確度。

(2)提出了一種剪枝策略。該策略在實(shí)時映射數(shù)據(jù)流更新網(wǎng)格的過程中，周期性地去除不可能成為異常網(wǎng)格的網(wǎng)格，從而縮小異常的查找范圍，提高算法效率。

(3)在5個真實(shí)數(shù)據(jù)集上，分別對GCStream-OD算法的檢測質(zhì)量和效率進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明GCStream-OD算法具有較高的檢測質(zhì)量和效率。

2 相關(guān)工作

數(shù)據(jù)流異常檢測是檢驗(yàn)數(shù)據(jù)流中是否有不符合常理的數(shù)據(jù)對象的過程。這些異常如果不被檢測出來，會對數(shù)據(jù)流的挖掘分析結(jié)果產(chǎn)生負(fù)面影響。近年來，提出了一些針對數(shù)據(jù)流的異常檢測算法[10,11]。這些算法主要分為4類：基于距離的算法、基于密度的算法、基于統(tǒng)計(jì)的算法和基于聚類的算法。

基于距離的異常檢測算法最早是由Knorr等人[12]提出的，其主要思想是計(jì)算數(shù)據(jù)對象之間的距離，然后以距離定義它們之間的鄰近度，而異常往往是那些遠(yuǎn)離大部分?jǐn)?shù)據(jù)的對象。基于密度的異常檢測算法是根據(jù)對象的密度定義異常，如果某些點(diǎn)周圍的數(shù)據(jù)點(diǎn)比較稀疏，則這些點(diǎn)會被算法視為異常進(jìn)而從數(shù)據(jù)流中過濾出來。最典型的算法為局部異常因子LOF(Local Outlier Factor)算法[13]，它根據(jù)每個數(shù)據(jù)對象的k近鄰密度，為每個數(shù)據(jù)對象分配了1個表示異?？赡苄源笮〉腖OF得分。iLOF算法[14]為LOF算法的增量版本。MiLOF算法[15]是一種能夠在有限的內(nèi)存環(huán)境中完成數(shù)據(jù)流的異常檢測的基于密度的數(shù)據(jù)流異常檢測算法。基于統(tǒng)計(jì)的異常檢測算法最早是由Barnett等人[16]和Hawkins[17]提出的。這類算法的主要思想是利用平均值、方差等對數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，進(jìn)而確定那些明顯不同于大部分?jǐn)?shù)據(jù)的對象。基于聚類的異常檢測對數(shù)據(jù)對象進(jìn)行聚類，以此來獲取不屬于簇的點(diǎn)或者一些明顯小于其它簇的數(shù)據(jù)集合。這種方法的主要過程是將數(shù)據(jù)聚集成簇，并判斷簇的大小，將小于閾值的簇視為異常。典型的算法有CORM(Cluster based OutlieR Miner)[6]、ROCK(RObust Clustering using linKs)[18]、CLARANS(Clustering Large Applications based on RANdomized Search)[19]等。CORM算法利用滑動窗口將數(shù)據(jù)流分塊，對于第1個窗口中的數(shù)據(jù)流，該算法先使用K-means算法將其劃分為k個簇，只保留每個簇的中心。對于后續(xù)窗口中的數(shù)據(jù)，首先根據(jù)數(shù)據(jù)對象到各個簇中心的距離進(jìn)行對象所屬簇的劃分，然后每個簇根據(jù)其分得的新數(shù)據(jù)更新簇中心。根據(jù)當(dāng)前窗口中的數(shù)據(jù)對象和更新后的簇中心距離得到候選異常數(shù)據(jù)。當(dāng)候選異常數(shù)據(jù)經(jīng)過L個窗口后仍為候選異常值時，則將其聲明為異常。CORM并沒有使用網(wǎng)格或微簇匯總數(shù)據(jù)流，而是以數(shù)據(jù)流中的每個數(shù)據(jù)對象為處理單元，這會降低算法的效率，并占用較大的內(nèi)存。

iForest(isolation Forest)算法[20]使用稱為隔離樹的二叉樹結(jié)構(gòu)，它可以有效構(gòu)建并且隔離數(shù)據(jù)對象。異常更容易被分離到更靠近隔離樹的根部，而正常點(diǎn)更可能在隔離樹的更深層被隔離掉。與其他異常檢測算法通過距離、密度等量化指標(biāo)來刻畫樣本間的疏離程度不同，iForest算法純粹基于隔離概念檢測異常。該算法大致可以分為2個階段；第1個階段需要訓(xùn)練出多棵孤立樹，組成孤立森林；第2階段將每個樣本點(diǎn)代入森林中的每棵孤立樹，計(jì)算平均高度，然后再計(jì)算每個樣本點(diǎn)的異常值分?jǐn)?shù)。iForest算法是一種半監(jiān)督的算法，需要一定的訓(xùn)練數(shù)據(jù)，這在一些應(yīng)用場景下是不適用的。

3 基于網(wǎng)格耦合的異常檢測算法

本節(jié)首先介紹網(wǎng)格耦合的思想及概念，然后給出基于網(wǎng)格耦合的異常檢測算法GCStream-OD。

3.1 網(wǎng)格耦合

輸入數(shù)據(jù)流中的每個數(shù)據(jù)對象x=(x1,x2,…,xd)都是d維空間中的一個點(diǎn)，xi表示數(shù)據(jù)對象在空間的第i維上的取值。如果x1屬于s1的j1區(qū)間，x2屬于s2的j2區(qū)間，以此類推xd屬于sd的jd區(qū)間，則可以將數(shù)據(jù)對象x映射到空間S的網(wǎng)格g=(j1,j2,…,jd)中。映射到同一網(wǎng)格中的數(shù)據(jù)對象距離相近，因此可以對各個網(wǎng)格內(nèi)的數(shù)據(jù)進(jìn)行匯總，形成概要。后續(xù)的數(shù)據(jù)分析可以只針對概要進(jìn)行處理，從而降低存儲空間和計(jì)算成本。

網(wǎng)格權(quán)重定義為網(wǎng)格內(nèi)各個數(shù)據(jù)對象的權(quán)重之和，數(shù)據(jù)的權(quán)重用于體現(xiàn)數(shù)據(jù)對象的“新鮮”程度。隨著時間的推移數(shù)據(jù)對象的“新鮮”程度越來越低，因此網(wǎng)格權(quán)重的大小是對網(wǎng)格內(nèi)數(shù)據(jù)對象的數(shù)目和“新鮮”程度的反映。數(shù)據(jù)對象權(quán)重和網(wǎng)格權(quán)重的定義分別如定義1和定義2所示。

定義1(數(shù)據(jù)對象權(quán)重[9]) 如果數(shù)據(jù)對象x在tp時刻到達(dá)，那么x在t時刻的權(quán)重W(x,t)的計(jì)算公式如式(1)所示：

W(x,t)=λ-a(t-tp)

(1)

其中，λ-a(0<λ-a<1)為衰減因子。參數(shù)λ和a控制衰減因子的衰減速度，a的絕對值越大，衰減速度越快。

定義2(網(wǎng)格權(quán)重[9]) 設(shè)E(g,t)表示到時刻t為止，映射到網(wǎng)格g中的數(shù)據(jù)對象集合，則網(wǎng)格g在時刻t的權(quán)重W(g,t)定義為網(wǎng)格g內(nèi)所有數(shù)據(jù)對象的權(quán)重之和。W(g,t)的計(jì)算如式(2)所示：

(2)

數(shù)據(jù)流中的數(shù)據(jù)對象順序到達(dá)，因此各個網(wǎng)格映射的數(shù)據(jù)隨時間不斷變化，每個網(wǎng)格的概要需要隨時間不斷更新。網(wǎng)格耦合的思想是在更新網(wǎng)格的概要時，根據(jù)網(wǎng)格中數(shù)據(jù)的分布狀態(tài)考慮網(wǎng)格之間的相互影響。網(wǎng)格之間的相互影響是由網(wǎng)格內(nèi)的數(shù)據(jù)分布來決定的。為了表示網(wǎng)格內(nèi)數(shù)據(jù)對象的分布狀態(tài)，張東月等人[9]將網(wǎng)格內(nèi)帶權(quán)數(shù)據(jù)對象的中心定義為網(wǎng)格質(zhì)心，利用網(wǎng)格質(zhì)心的位置來表示網(wǎng)格內(nèi)的數(shù)據(jù)分布狀態(tài)。數(shù)據(jù)流的動態(tài)性使得網(wǎng)格質(zhì)心是隨時間變化的。網(wǎng)格質(zhì)心的定義如定義3所示。

定義3(網(wǎng)格質(zhì)心[9]) 網(wǎng)格g在t時刻的質(zhì)心C(g,t)定義為網(wǎng)格g內(nèi)帶權(quán)數(shù)據(jù)對象的加權(quán)平均[9]。根據(jù)式(3)進(jìn)行計(jì)算可以得到C(g,t):

(3)

網(wǎng)格之間的相互影響與網(wǎng)格的質(zhì)心距離有關(guān)，網(wǎng)格質(zhì)心距離越近，網(wǎng)格之間的影響越大，反之越小。網(wǎng)格質(zhì)心之間的距離disC(gi,gj)使用質(zhì)心之間的歐氏距離進(jìn)行度量。設(shè)網(wǎng)格的影響區(qū)域閾值為Dislen，disC(gi,gj)≤Dislen表示網(wǎng)格gi對網(wǎng)格gj產(chǎn)生正影響，反之表示產(chǎn)生負(fù)影響。當(dāng)網(wǎng)格gi對網(wǎng)格gj產(chǎn)生正影響時，網(wǎng)格gj的權(quán)重會隨著網(wǎng)格gi權(quán)重的增大而增大，當(dāng)產(chǎn)生負(fù)影響時，網(wǎng)格gj的權(quán)重會隨著網(wǎng)格gi權(quán)重的增加而減小。設(shè)網(wǎng)格gi的權(quán)重增量為ΔW(gi)，則對網(wǎng)格gj的權(quán)重影響按式(4)進(jìn)行更新。

(4)

其中,MaxCdis是相鄰網(wǎng)格質(zhì)心間的最大距離，MaxCdis可以按式(5)計(jì)算：

(5)

其中，len為網(wǎng)格邊長，Dim為數(shù)據(jù)維度。

另外，為體現(xiàn)Dislen影響范圍內(nèi)網(wǎng)格之間的權(quán)重關(guān)系，引入了核心網(wǎng)格的概念。

定義4(核心網(wǎng)格[9]) 設(shè)L(g,t)是網(wǎng)格g在Dislen影響范圍內(nèi)的網(wǎng)格集合，如果L(g,t)內(nèi)所有網(wǎng)格的權(quán)重之和大于閾值θ，即LW(g,t)=∑g′∈L(g,t)W(g′,t)>θ，則稱網(wǎng)格g為核心網(wǎng)格。所有核心網(wǎng)格的集合表示為LD。

3.2 GCStream-OD算法

本節(jié)分別從相關(guān)定義、算法框架、剪枝策略以及算法描述4個方面對GCStream-OD算法進(jìn)行闡述。

3.2.1 相關(guān)定義

GCStream-OD算法在使用網(wǎng)格來檢測異常時，從網(wǎng)格密度和網(wǎng)格距離2個因素進(jìn)行考慮。密度因素從網(wǎng)格的鄰居網(wǎng)格數(shù)目和網(wǎng)格本身密度2個方面度量網(wǎng)格是異常網(wǎng)格的可能性，如果1個網(wǎng)格周圍含有數(shù)據(jù)的鄰居網(wǎng)格數(shù)較少且本身密度較低，則該網(wǎng)格中的數(shù)據(jù)對象是異常的可能性較大。距離因素從網(wǎng)格與其它網(wǎng)格的距離方面度量網(wǎng)格是異常網(wǎng)格的可能性，如果1個網(wǎng)格距離其它大部分網(wǎng)格較遠(yuǎn)，則該網(wǎng)格中的數(shù)據(jù)對象為異常的可能性較大。

GCStream-OD算法為每個網(wǎng)格分配1個異常因子，每個異常因子由密度異常因子和距離異常因子2部分組成。異常因子的定義如定義5所示。

定義5(網(wǎng)格異常因子(GOF)) 每個網(wǎng)格的異常因子的計(jì)算如式(6)所示：

GOF(g)=denF(g)+disF(g)

(6)

其中,denF為密度異常因子，disF為距離異常因子。GOF值表示網(wǎng)格的異常程度，值越大表示其越可能為異常網(wǎng)格，值越小表示其越不可能為異常網(wǎng)格。

密度異常因子denF的計(jì)算類似于LOF[13]的計(jì)算，因此需要定義網(wǎng)格的k距離、網(wǎng)格k距離鄰域、網(wǎng)格可達(dá)距離、網(wǎng)格局部可達(dá)密度等概念。

定義6(網(wǎng)格的k距離) 對于網(wǎng)格gp，如果存在網(wǎng)格go滿足至少存在k個網(wǎng)格gq使得disC(gp,gq)≤disC(gp,go)和至多存在k-1個網(wǎng)格gq使得disC(gp,gq)

k-distance(gp)用來度量網(wǎng)格gp局部區(qū)域的密度，其值越小，局部區(qū)域密度越大；其值越大，局部區(qū)域密度越小。

定義7(網(wǎng)格的k距離鄰域) 與網(wǎng)格gp之間距離小于或等于k-distance(gp)的網(wǎng)格集合稱為gp的k距離鄰域，記為Nk(gp)，如式(7)所示：

Nk(gp)={go|disC(gp,go)≤k-distance(gp)}

(7)

定義8(網(wǎng)格可達(dá)距離) 網(wǎng)格gp和go之間的可達(dá)距離的定義如式(8)所示：

reachdist(gp,go)=

max(k-distance(go),disC(gp,go))

(8)

定義9(網(wǎng)格局部可達(dá)密度) 網(wǎng)格gp的局部可達(dá)密度為Nk(gp)中所有網(wǎng)格平均可達(dá)距離的倒數(shù)，可以通過式(9)計(jì)算得到：

(9)

定義10(網(wǎng)格密度異常因子) 網(wǎng)格gp密度異常因子定義為其k距離鄰域Nk(gp)內(nèi)網(wǎng)格的局部可達(dá)密度與網(wǎng)格gp局部可達(dá)密度之比的平均數(shù)，如式(10)所示：

(10)

其中，局部異常因子denF(gp)越大，表示網(wǎng)格gp為異常的可能性越大，反之成立。

denF(gp)從密度的角度表征了網(wǎng)格gp為異常的程度。從距離角度表征1個網(wǎng)格異常的程度的距離異常因子disF由定義11給出。

定義11(距離異常因子disF) 設(shè)gc是1個核心網(wǎng)格，L(gc,t)是與網(wǎng)格gc最近的低權(quán)重網(wǎng)格集合，gi∈L(gc,t)，則網(wǎng)格gi的距離異常因子定義為gi與gc之間的距離與L(gc,t)內(nèi)的網(wǎng)格與gc之間的最大距離之比，通過式(11)計(jì)算得到:

(11)

其中，任意網(wǎng)格g的距離因子滿足0

定義12(異常網(wǎng)格) 在當(dāng)前時刻t如果網(wǎng)格g的異常因子大于一定閾值εo，即GOF(g)>εo，則將網(wǎng)格g視為異常網(wǎng)格。異常網(wǎng)格中的數(shù)據(jù)對象即為異常。

3.2.2 算法框架

由于數(shù)據(jù)流具有快速、大量、連續(xù)到達(dá)的特性，為了更好地處理數(shù)據(jù)流，GCStream-OD算法采用在線/離線的框架。在線階段處理源源不斷到達(dá)的數(shù)據(jù)，離線階段進(jìn)行離群點(diǎn)檢測。GCStream-OD算法流程圖如圖1所示。

Figure 1 Flow chart of GCStream-OD algorithm圖1 GCStream-OD算法流程圖

GCStream-OD算法分為在線階段和離線階段2個部分。在線階段的主要工作是將隨時間到達(dá)的數(shù)據(jù)流映射到網(wǎng)格中，然后根據(jù)網(wǎng)格耦合思想更新網(wǎng)格，最后周期性地檢測網(wǎng)格權(quán)重并保留低權(quán)重網(wǎng)格作為異常的候選集合。離線階段的主要工作是計(jì)算每個低權(quán)重網(wǎng)格的異常因子，并根據(jù)異常因子判斷網(wǎng)格是否為異常網(wǎng)格。具體操作將在后面2節(jié)進(jìn)行介紹。

3.2.3 剪枝策略

在上述框架中，周期性檢測過程中若簡單地將除核心網(wǎng)格外的所有網(wǎng)格作為低權(quán)重網(wǎng)格存至lwGirdList，將會使離線階段需要大量的計(jì)算，影響算法效率。針對這一問題，本文根據(jù)異常數(shù)據(jù)量較少、密度較低的特點(diǎn)，提出了一種剪枝策略。剪枝策略的主要思想是在周期性檢測過程中判定低權(quán)重網(wǎng)格時，根據(jù)網(wǎng)格權(quán)重的大小篩選網(wǎng)格，保留權(quán)重較小的網(wǎng)格，去除網(wǎng)格權(quán)重大的非核心網(wǎng)格，判定標(biāo)準(zhǔn)為將網(wǎng)格權(quán)重低于μθ的網(wǎng)格劃為低權(quán)重網(wǎng)格，其中θ為判斷核心網(wǎng)格時所取的閾值，μ∈(0,1)。一個網(wǎng)格如果權(quán)重較大，表示該網(wǎng)格內(nèi)數(shù)據(jù)對象數(shù)目多或權(quán)重高，則該網(wǎng)格內(nèi)的數(shù)據(jù)對象為異常的可能性小，其被剪枝后對算法的精確度基本沒有影響，但能很好地提升算法的效率。如圖2所示，在ta時刻數(shù)據(jù)流映射到網(wǎng)格1～12，網(wǎng)格3是核心網(wǎng)格，其余網(wǎng)格均是非核心網(wǎng)格。經(jīng)過剪枝之后，權(quán)重較大的網(wǎng)格1、2、4、5和6會被去除，而網(wǎng)格權(quán)重較小的網(wǎng)格7～12以及核心網(wǎng)格3會被保留。進(jìn)行異常檢測時，只需對網(wǎng)格7～12進(jìn)行處理，減少了離線階段的計(jì)算量，極大地提高算法運(yùn)行效率。

經(jīng)過剪枝之后，一些權(quán)重較低的網(wǎng)格，原本距離高權(quán)重網(wǎng)格較近不屬于異常，但這類網(wǎng)格由于高權(quán)重鄰居網(wǎng)格的剪枝使得周圍鄰居網(wǎng)格數(shù)驟減、密度降低，很容易被視為異常，進(jìn)而影響算法精確度。距離異常因子的引入可以避免這種問題。比如，圖2b中網(wǎng)格7，圖中五角星表示每個網(wǎng)格的質(zhì)心位置。網(wǎng)格7周圍數(shù)據(jù)量較少，其密度比較低，但是網(wǎng)格7與網(wǎng)格3質(zhì)心距離較近，即denF(7)較大,disF(7)較小，所以網(wǎng)格7的異常因子不會太高。圖2b中只有網(wǎng)格12為異常。由于考慮了網(wǎng)格耦合，圖2b中只有網(wǎng)格12為異常，若不考慮網(wǎng)格耦合，網(wǎng)格8、9、10和11均為異常。因此，該剪枝策略適用于GCStream-OD算法。

Figure 2 Data distribution within the grid up to time ta圖2 截止到ta時刻網(wǎng)格內(nèi)的數(shù)據(jù)分布

3.2.4 算法描述

GCStream-OD算法在線階段將到來的數(shù)據(jù)流映射到對應(yīng)網(wǎng)格并通過周期性檢測得到低權(quán)重網(wǎng)格，具體細(xì)節(jié)如算法1所示。算法1需要1個數(shù)據(jù)流和1個檢測周期tp作為輸入。算法1首先初始化網(wǎng)格列表為空和tc=0，之后開始接收數(shù)據(jù)流中的數(shù)據(jù)，直到數(shù)據(jù)流結(jié)束后停止算法執(zhí)行。每當(dāng)從數(shù)據(jù)流中獲得1個新數(shù)據(jù)對象x，先將對象x映射到對應(yīng)的網(wǎng)格gx。若網(wǎng)格gx不存在，則創(chuàng)建網(wǎng)格gx并將其插入到網(wǎng)格列表中，再將對象x映射在所屬的網(wǎng)格gx。之后根據(jù)網(wǎng)格耦合思想更新網(wǎng)格gx的屬性：(1)根據(jù)式(2)計(jì)算網(wǎng)格權(quán)重；(2)根據(jù)式(3)計(jì)算網(wǎng)格質(zhì)心；(3)根據(jù)式(4)更新gx周邊網(wǎng)格的權(quán)重。更新網(wǎng)格后可能造成核心網(wǎng)格的變更，因此需要更新核心網(wǎng)格。每當(dāng)處理完1個數(shù)據(jù)對象x后，tc加1，同時判斷1個周期是否結(jié)束，若結(jié)束，先更新核心網(wǎng)格，再將通過剪枝策略得到的低權(quán)重網(wǎng)格存至lwGirdList，之后觸發(fā)執(zhí)行離線階段。

算法1GCStream-OD在線階段

輸入：數(shù)據(jù)流，檢測周期tp。

輸出：低權(quán)重網(wǎng)格列表lwGirdList。

1.初始化網(wǎng)格列表，tc=0;

2.while(數(shù)據(jù)流沒有結(jié)束)

3. 從流中獲取數(shù)據(jù)對象x=(x1,x2,…,xd);

4. 確定數(shù)據(jù)對象x所屬的網(wǎng)格gx;

5. if(網(wǎng)格gx不存在于網(wǎng)格列表)

6. 創(chuàng)建網(wǎng)格gx并將其插入到網(wǎng)格列表;

7. end if

8. 將數(shù)據(jù)對象x映射到網(wǎng)格gx；

9. 更新網(wǎng)格gx；

10.tc=tc+1;

11. if (tcmodtp==0)

12. 更新核心網(wǎng)格；

13. 通過剪枝策略得到低權(quán)重網(wǎng)格并將其存至lwGirdList;

14. end if

15.end while

GCStream-OD算法在離線階段為每個網(wǎng)格分配1個異常因子來定量度量網(wǎng)格的異常程度，具體細(xì)節(jié)如算法2所示。算法2需要低權(quán)重網(wǎng)格列表lwGirdList作為輸入，對于lwGirdList中的每一個網(wǎng)格g，先根據(jù)式(10)計(jì)算密度因子denF(g)，再根據(jù)式(11)計(jì)算距離因子disF(g)，之后根據(jù)式(6)計(jì)算低權(quán)重網(wǎng)格的異常因子GOF(g)，最后比較異常因子與異常閾值εo，若GOF(g)>εo將網(wǎng)格g加入到異常網(wǎng)格列表，反之不做處理。異常網(wǎng)格列表中的網(wǎng)格所對應(yīng)的數(shù)據(jù)對象都是異常。

算法2GCStream-OD離線階段

輸入：lwGirdList。

輸出：異常值檢測結(jié)果。

1.for (lwGirdList中的所有網(wǎng)格g)

2. 計(jì)算denF(g);

3. 計(jì)算disF(g);

4.GOF(g)=denF(g)+disF(g);

5. ifGOF(g)>εo

6. 將網(wǎng)格g加入到異常網(wǎng)格列表;

7. end if

8.end for

假設(shè)當(dāng)前時刻tc進(jìn)行異常檢測，此時低權(quán)重網(wǎng)格列表lwGirdList中的網(wǎng)格數(shù)據(jù)為N，核心網(wǎng)格集合LD的大小為Ncg。GCStream-OD算法首先計(jì)算密度因子，由于此步驟是將LOF算法擴(kuò)展到網(wǎng)格，所以該步驟的時間復(fù)雜度為O(N2)。然后計(jì)算距離因子，在此步驟中需要先計(jì)算低權(quán)重網(wǎng)格與核心網(wǎng)格的距離，時間復(fù)雜度為O(Ncg×N)。緊接著遍歷低權(quán)重網(wǎng)格列表lwGirdList，計(jì)算距離因子，時間復(fù)雜度為O(N)。綜上所述，GCStream-OD算法的時間復(fù)雜度為：O(N2+Ncg×N+N)。在GCStream-OD算法中處理單位為網(wǎng)格，因?yàn)榈蜋?quán)重網(wǎng)格數(shù)N和核心網(wǎng)格集合LD的大小Ncg都是非常小的，使得該算法具有較高的效率。GCStream-OD算法最糟糕的情況是為每個到達(dá)的數(shù)據(jù)創(chuàng)造1個網(wǎng)格，因此GCStream-OD算法的空間復(fù)雜度最高為O(n)，其中n為到達(dá)數(shù)據(jù)的總數(shù)。

4 實(shí)驗(yàn)評估

本節(jié)包含GCStream-OD 算法的實(shí)驗(yàn)準(zhǔn)備、參數(shù)選擇以及實(shí)驗(yàn)結(jié)果3個部分。

4.1 實(shí)驗(yàn)準(zhǔn)備

數(shù)據(jù)集：實(shí)驗(yàn)使用了KDD CUP99[21]、CoverType[22]、Poker Hand[23]、data_http[20]、data_OD共5個數(shù)據(jù)集來測試GCStream-OD算法的檢測質(zhì)量和效率。KDD CUP99、CoverType、Poker Hand 數(shù)據(jù)集均來自UCI數(shù)據(jù)集。KDD CUP99是一種網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集，由原始數(shù)據(jù)集抽樣10%形成，包含494 020個數(shù)據(jù)對象，每個數(shù)據(jù)對象有34種連續(xù)屬性。CoverType是一種森林植被數(shù)據(jù)集，包含581 012個數(shù)據(jù)對象，并且每個數(shù)據(jù)對象記錄1塊30*30平方英尺上的54個地理數(shù)據(jù)。Poker Hand共有1 000 000個數(shù)據(jù)對象，其中每個數(shù)據(jù)對象表示由5張從52張標(biāo)準(zhǔn)牌組中抽出的撲克牌組成的手牌記錄，每張卡片使用2種屬性(花色和大小)進(jìn)行描述，因此共10個預(yù)測屬性。data_http[20]數(shù)據(jù)集和data_OD數(shù)據(jù)集由原始KDD CUP99數(shù)據(jù)集中567 497個相同的數(shù)據(jù)對象保留不同的屬性組成，data_http數(shù)據(jù)集保留了duration、src_bytes和dst_bytes屬性，data_OD數(shù)據(jù)集保留了hot、srv_count和dst_host_count屬性。KDD CUP99、data_http、data_OD均由原始KDD CUP99數(shù)據(jù)集抽樣而成，KDD CUP99保留了34種屬性而data_http和 data_OD只保留了3種屬性。

在測試過程中，本文以上述數(shù)據(jù)集中數(shù)據(jù)的輸入順序作為數(shù)據(jù)流的傳輸順序，將所有數(shù)據(jù)集轉(zhuǎn)為流。除此之外，本文將測試數(shù)據(jù)流中規(guī)模小于5%的簇視為噪聲，即當(dāng)一個簇規(guī)模小于數(shù)據(jù)集總數(shù)據(jù)量的5%時被視為噪聲。表1匯總了各個數(shù)據(jù)集的特征。

Figure 3 Influence of different len values on F1 on different data sets of GCStream-OD algorithm圖3 GCStream-OD算法在不同數(shù)據(jù)集上不同len值對F1的影響

表1 數(shù)據(jù)集特征匯總

對比算法：使用CORM算法[6]和iForest算法[20]作為本文的對比算法。CORM算法將數(shù)據(jù)流異常檢測過程分為在線/離線2個階段，這與GCStream-OD算法的處理方式相同，具有可比性。iForest算法基于隔離概念檢測異常，而不采用任何距離、密度測量，是目前很好的數(shù)據(jù)流異常檢測算法。

評價指標(biāo)：使用精確度(Precision)、召回率(Recall)和F-Measure(F1)作為評價指標(biāo)，各項(xiàng)指標(biāo)的定義分別如式(12)～式(14)所示：

Precision=TP/(TP+FP)

(12)

Recall=TP/(TP+FN)

(13)

F1=Precision*Recall*2/(Precision+Recall)

(14)

為了便于統(tǒng)計(jì)，將異常視為正的(Positive)數(shù)據(jù)對象，非異常視為負(fù)的(Negative)數(shù)據(jù)對象。因此，式(12)和式(13)中TP表示被識別為異常的異常數(shù)據(jù)的個數(shù)，F(xiàn)N表示被識別為非異常的異常數(shù)據(jù)的個數(shù)，F(xiàn)P表示被識別為異常的非異常數(shù)據(jù)的個數(shù)。F-Measure是Precision和Recall的加權(quán)調(diào)和平均。

4.2 參數(shù)選擇

為了保證算法結(jié)果更具可比性，在進(jìn)行對比實(shí)驗(yàn)之前，統(tǒng)一環(huán)境變量、調(diào)整算法參數(shù)是非常必要的。環(huán)境變量主要包括：數(shù)據(jù)流的速度、數(shù)據(jù)對象的衰減速度。本文默認(rèn)將數(shù)據(jù)流中數(shù)據(jù)對象的到達(dá)速率設(shè)為1 000 pt/ms，統(tǒng)一算法中數(shù)據(jù)對象的權(quán)重衰減函數(shù)f=λ-a=0.998，而對比算法的參數(shù)設(shè)置參考其原始論文。在GCStream-OD算法中對異常檢測結(jié)果有較大影響的參數(shù)主要有網(wǎng)格邊長len、核心網(wǎng)格集合LD的大小Ncg、網(wǎng)格第k距離中的k值以及異常網(wǎng)格閾值εo。為了對這些參數(shù)進(jìn)行合理選擇，本文對其進(jìn)行了實(shí)驗(yàn)探索。

4.2.1 網(wǎng)格邊長len

GCStream-OD算法中，若len太小，網(wǎng)格切分太小，將會花費(fèi)大量的時間在網(wǎng)格耦合的處理上，不能滿足實(shí)時性要求；若len過大，容易將異常和非異常劃分到同一網(wǎng)格中，對算法精確度會造成影響。對于不同數(shù)據(jù)集，數(shù)據(jù)的最大值與最小值的差值不同，需要對不同數(shù)據(jù)集選取不同的len。圖3展示了在不同數(shù)據(jù)集上，不同len值對算法F1指標(biāo)值的影響。從圖3中可以看出,GCStream-OD算法在數(shù)據(jù)集KDD CUP99上當(dāng)len取值為1 200時F1值最大，所以對于KDD CUP99數(shù)據(jù)集實(shí)驗(yàn)選取len=1000。同理可得，在CoverType數(shù)據(jù)集上選取len=1500，在data_OD數(shù)據(jù)集上選取len=7，在data_http數(shù)據(jù)集上選取len=2000，在Poker Hand數(shù)據(jù)集上選取len=6。

Figure 4 Influence of different Ncg values on F1 on different data sets of GCStream-OD algorithm圖4 GCStream-OD算法在不同數(shù)據(jù)集上不同Ncg值對F1的影響

Figure 5 Influence of different k values on F1 on different data sets of GCStream-OD algorithm圖5 GCStream-OD算法在不同數(shù)據(jù)集上不同k值對F1的影響

4.2.2 核心網(wǎng)格集合大小

核心網(wǎng)格集合由權(quán)重大于閾值的網(wǎng)格組成，并且核心網(wǎng)格集合的大小對GCStream-OD算法的結(jié)果有直接影響。本節(jié)以評估指標(biāo)F1的大小來探索參數(shù)Ncg的最佳取值，實(shí)驗(yàn)結(jié)果如圖4所示。在KDD CUP99數(shù)據(jù)集上,當(dāng)Ncg=7時取得最好的F1值。在CoverType數(shù)據(jù)集上，當(dāng)Ncg=4時取得最好的F1值。對于數(shù)據(jù)集data_OD，當(dāng)Ncg=1時取得最好的F1值。在data_http數(shù)據(jù)集上，當(dāng)Ncg=12時取得最好的F1值。在Poker Hand數(shù)據(jù)集上，當(dāng)Ncg=6時取得最好的F1值。綜上所述，在KDD CUP99、CoverType、data_OD、data_http和Poker Hand數(shù)據(jù)集上，Ncg的取值分別為7,4,1,12和6。

4.2.3 網(wǎng)格第k距離中的k值

網(wǎng)格第k距離用來度量網(wǎng)格局部區(qū)域的密度，k值越小，局部區(qū)域密度越大；反之，k值越大，局部區(qū)域密度越小。不同數(shù)據(jù)集的數(shù)據(jù)映射到網(wǎng)格后所得到的網(wǎng)格局部區(qū)域的密度值不同，因此對于不同的數(shù)據(jù)集需要找到其最佳的網(wǎng)格第k距離。本節(jié)將根據(jù)評估指標(biāo)F1的好壞來探索不同數(shù)據(jù)集的最佳k值，實(shí)驗(yàn)結(jié)果如圖5所示。在KDD CUP99數(shù)據(jù)集上，當(dāng)k=6時取得最好的F1值，因此在KDD CUP99數(shù)據(jù)集上設(shè)置k=6。在CoverType數(shù)據(jù)集上，當(dāng)k=5時取得最好的F1值，因此設(shè)置k=5。對于數(shù)據(jù)集data_OD，當(dāng)k=7時取得最好的F1值，因此設(shè)置k=7。在data_http數(shù)據(jù)集上，當(dāng)k=11時取得最好的F1值，因此設(shè)置k=11。在Poker Hand數(shù)據(jù)集上，當(dāng)k=5時取得最好的F1值，因此設(shè)置k=5。

4.2.4 異常網(wǎng)格閾值εo

異常網(wǎng)格閾值εo直接影響異常數(shù)據(jù)的檢測。當(dāng)εo取值過小時，許多非異常數(shù)據(jù)對象會被劃分為異常數(shù)據(jù)對象，造成精確度過低；當(dāng)εo取值過大時，許多異常數(shù)據(jù)對象會被劃分為非異常數(shù)據(jù)對象，造成召回率過低。對于不同數(shù)據(jù)集，異常網(wǎng)格閾值εo也不盡相同。通過評估指標(biāo)F1的大小，本節(jié)將對不同數(shù)據(jù)集最適合的εo值進(jìn)行探索，實(shí)驗(yàn)結(jié)果如圖6所示。在KDD CUP99數(shù)據(jù)集上，當(dāng)εo=3.5時F1值最高。在CoverType數(shù)據(jù)集上當(dāng)εo=2.4時F1值最高。對于data_OD數(shù)據(jù)集當(dāng)εo=2.4時F1值最高。在data_http數(shù)據(jù)集上，在εo=19時取得最好的F1值；在Poker Hand數(shù)據(jù)集上，在εo=1時F1值最高。綜上所述，在KDD CUP99、CoverType、data_OD、data_http和Poker Hand數(shù)據(jù)集上εo的取值分別為3.5，2.4，2，19和1。

Figure 6 Influence of different εo values on F1 on different data sets of GCStream-OD algorithm圖6 GCStream-OD算法在不同數(shù)據(jù)集上不同εo值對F1的影響

4.3 實(shí)驗(yàn)結(jié)果

本節(jié)主要對GCStream-OD算法的檢測質(zhì)量以及效率進(jìn)行實(shí)驗(yàn)評估。

4.3.1 算法檢測質(zhì)量

圖7展示了GCStream-OD算法與CORM和iForest算法的實(shí)驗(yàn)結(jié)果對比情況。其中，GCStream-OD算法的F1值在CoverType、data_OD和Poker Hand數(shù)據(jù)集上均高于基準(zhǔn)算法。雖然iForest算法在KDD CUP99和data_http上獲得了更好的F1值，但GCStream-OD的F1值仍接近于iForest。

Figure 7 Precision,recall and F1 comparison of different algorithms on different data sets圖7 各算法在不同數(shù)據(jù)集上的Precision、Recall和F1對比

通過對實(shí)驗(yàn)結(jié)果的分析可知，在KDD CUP99數(shù)據(jù)集上，GCStream-OD算法略低于iForest算法的主要原因是部分真實(shí)異常在分布上與非異常數(shù)據(jù)接近，被劃分到非核心的高權(quán)重網(wǎng)格中；且數(shù)量較少，對網(wǎng)格權(quán)重影響小，使得所在網(wǎng)格被剪去而不能被檢測出來，造成Recall值過低。在data_http數(shù)據(jù)集上本文算法的F1略低于iForest算法主要包含2個原因，第1個原因與KDD CUP99數(shù)據(jù)集相同;第2個原因是非異常數(shù)據(jù)被剪去，造成數(shù)據(jù)密度因子denF過高，而距離因子disF不能消除其影響，使得正常數(shù)據(jù)被劃為異常，導(dǎo)致Precision值變低。

CORM算法與本文算法原理類似，首先對數(shù)據(jù)流進(jìn)行劃分，然后丟棄正常值區(qū)域，保留每個簇的中心和候選異常。但是，CORM算法忽略了數(shù)據(jù)對象之間的影響，而GCStream-OD算法采用網(wǎng)格耦合的方式，更多地考慮了數(shù)據(jù)對象之間的相互影響，因此GCStream-OD算法在整體性能上優(yōu)于CORM算法。

4.3.2 算法效率

實(shí)時檢測異常數(shù)據(jù)對于數(shù)據(jù)流異常檢測算法至關(guān)重要，所以本文對GCStream-OD算法、CORM算法以及iForest算法的效率進(jìn)行了對比。實(shí)驗(yàn)結(jié)果如圖8所示，時間單位為ms。從圖8可以看出，本文算法在各個數(shù)據(jù)集上的耗時均較少。這是因?yàn)楸疚囊跃W(wǎng)格匯總數(shù)據(jù)流并采用剪枝策略，最終僅對少量的低權(quán)重網(wǎng)格進(jìn)行處理，大大降低了算法需要處理的對象數(shù)目，提高了算法效率。

Figure 8 Time efficiency comparison of different algorithms on different data sets圖8 各算法在不同數(shù)據(jù)集上的時間效率對比

5 結(jié)束語

本文針對現(xiàn)有數(shù)據(jù)流異常檢測算法大都以每個數(shù)據(jù)對象為處理單元，算法效率較低，而以網(wǎng)格結(jié)構(gòu)匯總并提取數(shù)據(jù)流摘要信息，能夠較快地處理數(shù)據(jù)流，但是假設(shè)網(wǎng)格之間彼此獨(dú)立，忽略數(shù)據(jù)之間的相關(guān)性的不足，提出了一種基于網(wǎng)格耦合的數(shù)據(jù)流異常檢測算法GCStream-OD。首先，通過網(wǎng)格耦合實(shí)現(xiàn)了對數(shù)據(jù)流更精確的匯總，同時配合剪枝策略提高處理效率；其次，本文根據(jù)異常周圍鄰居較少、密度較低并且距正常值較遠(yuǎn)的特點(diǎn)為每個網(wǎng)格分配異常因子度量其異常程度；最后，通過在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，對比了本文算法與其他算法檢測質(zhì)量和效率等，實(shí)驗(yàn)結(jié)果表明，本文所提GCStream-OD算法具有較高的異常檢測質(zhì)量和效率。

GCStream-OD算法以網(wǎng)格為處理單元，采用了網(wǎng)格耦合的思想來提升算法質(zhì)量，并通過實(shí)驗(yàn)證明網(wǎng)格耦合是有效的，但對于一些數(shù)據(jù)集(如Poker Hand)該算法取得的結(jié)果還不盡人意。為了提高GCStream-OD算法的泛化能力，設(shè)計(jì)更好的網(wǎng)格耦合方式和剪枝策略將是我們未來工作的研究重點(diǎn)。