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

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

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

1 引言

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

針對(duì)數(shù)據(jù)流異常檢測(cè)存在的諸多挑戰(zhàn)，許多數(shù)據(jù)流異常檢測(cè)算法被提出[4,6,7]。這些算法利用距離、密度或聚類等手段來(lái)區(qū)分正常數(shù)據(jù)和異常，雖然能夠較精確地檢測(cè)數(shù)據(jù)流中的異常，但是它們均以數(shù)據(jù)對(duì)象為處理單元，需要對(duì)數(shù)據(jù)流中每個(gè)數(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ù)對(duì)象為處理單元的算法相比，網(wǎng)格的應(yīng)用大大加快了數(shù)據(jù)流的處理速度，進(jìn)而提高了算法的效率。但是，Chen等人[8]在將數(shù)據(jù)對(duì)象映射到網(wǎng)格并增量更新網(wǎng)格時(shí)，獨(dú)立處理每個(gè)網(wǎng)格，忽略了網(wǎng)格之間的相互影響,使得提取的數(shù)據(jù)流概要不夠精確,從而影響了算法的精確度。張東月等人[9]也采用了網(wǎng)格的方式進(jìn)行數(shù)據(jù)流的聚類，但是在將數(shù)據(jù)對(duì)象映射到網(wǎng)格后不是獨(dú)立處理網(wǎng)格，而是考慮了網(wǎng)格之間的相互影響(即網(wǎng)格耦合)，該方法有效提高了聚類的精確度。

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3.1 網(wǎng)格耦合

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

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

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

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

(1)

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

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

(2)

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

定義3(網(wǎng)格質(zhì)心[9]) 網(wǎng)格g在t時(shí)刻的質(zhì)心C(g,t)定義為網(wǎng)格g內(nèi)帶權(quán)數(shù)據(jù)對(duì)象的加權(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對(duì)網(wǎng)格gj產(chǎn)生正影響，反之表示產(chǎn)生負(fù)影響。當(dāng)網(wǎng)格gi對(duì)網(wǎng)格gj產(chǎn)生正影響時(shí)，網(wǎng)格gj的權(quán)重會(huì)隨著網(wǎng)格gi權(quán)重的增大而增大，當(dāng)產(chǎn)生負(fù)影響時(shí)，網(wǎng)格gj的權(quán)重會(huì)隨著網(wǎng)格gi權(quán)重的增加而減小。設(shè)網(wǎng)格gi的權(quán)重增量為ΔW(gi)，則對(duì)網(wǎng)格gj的權(quán)重影響按式(4)進(jìn)行更新。

(4)

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

(5)

其中，len為網(wǎng)格邊長(zhǎ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)格的集合表示為L(zhǎng)D。

3.2 GCStream-OD算法

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

3.2.1 相關(guān)定義

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

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

定義5(網(wǎng)格異常因子(GOF)) 每個(gè)網(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距離) 對(duì)于網(wǎng)格gp，如果存在網(wǎng)格go滿足至少存在k個(gè)網(wǎng)格gq使得disC(gp,gq)≤disC(gp,go)和至多存在k-1個(gè)網(wǎng)格gq使得disC(gp,gq)

k-distance(gp)用來(lái)度量網(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ù)，可以通過(guò)式(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個(gè)網(wǎng)格異常的程度的距離異常因子disF由定義11給出。

定義11(距離異常因子disF) 設(shè)gc是1個(gè)核心網(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之間的最大距離之比，通過(guò)式(11)計(jì)算得到:

(11)

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

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

3.2.2 算法框架

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

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

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

3.2.3 剪枝策略

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

經(jīng)過(guò)剪枝之后，一些權(quán)重較低的網(wǎng)格，原本距離高權(quán)重網(wǎng)格較近不屬于異常，但這類網(wǎng)格由于高權(quán)重鄰居網(wǎng)格的剪枝使得周圍鄰居網(wǎng)格數(shù)驟減、密度降低，很容易被視為異常，進(jìn)而影響算法精確度。距離異常因子的引入可以避免這種問(wèn)題。比如，圖2b中網(wǎng)格7，圖中五角星表示每個(gè)網(wǎng)格的質(zhì)心位置。網(wǎng)格7周圍數(shù)據(jù)量較少，其密度比較低，但是網(wǎng)格7與網(wǎng)格3質(zhì)心距離較近，即denF(7)較大,disF(7)較小，所以網(wǎng)格7的異常因子不會(huì)太高。圖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時(shí)刻網(wǎng)格內(nèi)的數(shù)據(jù)分布

3.2.4 算法描述

GCStream-OD算法在線階段將到來(lái)的數(shù)據(jù)流映射到對(duì)應(yīng)網(wǎng)格并通過(guò)周期性檢測(cè)得到低權(quán)重網(wǎng)格，具體細(xì)節(jié)如算法1所示。算法1需要1個(gè)數(shù)據(jù)流和1個(gè)檢測(cè)周期tp作為輸入。算法1首先初始化網(wǎng)格列表為空和tc=0，之后開(kāi)始接收數(shù)據(jù)流中的數(shù)據(jù)，直到數(shù)據(jù)流結(jié)束后停止算法執(zhí)行。每當(dāng)從數(shù)據(jù)流中獲得1個(gè)新數(shù)據(jù)對(duì)象x，先將對(duì)象x映射到對(duì)應(yīng)的網(wǎng)格gx。若網(wǎng)格gx不存在，則創(chuàng)建網(wǎng)格gx并將其插入到網(wǎng)格列表中，再將對(duì)象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個(gè)數(shù)據(jù)對(duì)象x后，tc加1，同時(shí)判斷1個(gè)周期是否結(jié)束，若結(jié)束，先更新核心網(wǎng)格，再將通過(guò)剪枝策略得到的低權(quán)重網(wǎng)格存至lwGirdList，之后觸發(fā)執(zhí)行離線階段。

算法1GCStream-OD在線階段

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

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

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

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

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

4. 確定數(shù)據(jù)對(duì)象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ù)對(duì)象x映射到網(wǎng)格gx；

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

10.tc=tc+1;

11. if (tcmodtp==0)

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

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

14. end if

15.end while

GCStream-OD算法在離線階段為每個(gè)網(wǎng)格分配1個(gè)異常因子來(lái)定量度量網(wǎng)格的異常程度，具體細(xì)節(jié)如算法2所示。算法2需要低權(quán)重網(wǎng)格列表lwGirdList作為輸入，對(duì)于lwGirdList中的每一個(gè)網(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)格所對(duì)應(yīng)的數(shù)據(jù)對(duì)象都是異常。

算法2GCStream-OD離線階段

輸入：lwGirdList。

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

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

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

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

在測(cè)試過(guò)程中，本文以上述數(shù)據(jù)集中數(shù)據(jù)的輸入順序作為數(shù)據(jù)流的傳輸順序，將所有數(shù)據(jù)集轉(zhuǎn)為流。除此之外，本文將測(cè)試數(shù)據(jù)流中規(guī)模小于5%的簇視為噪聲，即當(dāng)一個(gè)簇規(guī)模小于數(shù)據(jù)集總數(shù)據(jù)量的5%時(shí)被視為噪聲。表1匯總了各個(gè)數(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值對(duì)F1的影響

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

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

評(píng)價(jià)指標(biāo)：使用精確度(Precision)、召回率(Recall)和F-Measure(F1)作為評(píng)價(jià)指標(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ù)對(duì)象，非異常視為負(fù)的(Negative)數(shù)據(jù)對(duì)象。因此，式(12)和式(13)中TP表示被識(shí)別為異常的異常數(shù)據(jù)的個(gè)數(shù)，F(xiàn)N表示被識(shí)別為非異常的異常數(shù)據(jù)的個(gè)數(shù)，F(xiàn)P表示被識(shí)別為異常的非異常數(shù)據(jù)的個(gè)數(shù)。F-Measure是Precision和Recall的加權(quán)調(diào)和平均。

4.2 參數(shù)選擇

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

4.2.1 網(wǎng)格邊長(zhǎng)len

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

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

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

核心網(wǎng)格集合由權(quán)重大于閾值的網(wǎng)格組成，并且核心網(wǎng)格集合的大小對(duì)GCStream-OD算法的結(jié)果有直接影響。本節(jié)以評(píng)估指標(biāo)F1的大小來(lái)探索參數(shù)Ncg的最佳取值，實(shí)驗(yàn)結(jié)果如圖4所示。在KDD CUP99數(shù)據(jù)集上,當(dāng)Ncg=7時(shí)取得最好的F1值。在CoverType數(shù)據(jù)集上，當(dāng)Ncg=4時(shí)取得最好的F1值。對(duì)于數(shù)據(jù)集data_OD，當(dāng)Ncg=1時(shí)取得最好的F1值。在data_http數(shù)據(jù)集上，當(dāng)Ncg=12時(shí)取得最好的F1值。在Poker Hand數(shù)據(jù)集上，當(dāng)Ncg=6時(shí)取得最好的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距離用來(lái)度量網(wǎng)格局部區(qū)域的密度，k值越小，局部區(qū)域密度越大；反之，k值越大，局部區(qū)域密度越小。不同數(shù)據(jù)集的數(shù)據(jù)映射到網(wǎng)格后所得到的網(wǎng)格局部區(qū)域的密度值不同，因此對(duì)于不同的數(shù)據(jù)集需要找到其最佳的網(wǎng)格第k距離。本節(jié)將根據(jù)評(píng)估指標(biāo)F1的好壞來(lái)探索不同數(shù)據(jù)集的最佳k值，實(shí)驗(yàn)結(jié)果如圖5所示。在KDD CUP99數(shù)據(jù)集上，當(dāng)k=6時(shí)取得最好的F1值，因此在KDD CUP99數(shù)據(jù)集上設(shè)置k=6。在CoverType數(shù)據(jù)集上，當(dāng)k=5時(shí)取得最好的F1值，因此設(shè)置k=5。對(duì)于數(shù)據(jù)集data_OD，當(dāng)k=7時(shí)取得最好的F1值，因此設(shè)置k=7。在data_http數(shù)據(jù)集上，當(dāng)k=11時(shí)取得最好的F1值，因此設(shè)置k=11。在Poker Hand數(shù)據(jù)集上，當(dāng)k=5時(shí)取得最好的F1值，因此設(shè)置k=5。

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

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

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

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

4.3.1 算法檢測(cè)質(zhì)量

圖7展示了GCStream-OD算法與CORM和iForest算法的實(shí)驗(yàn)結(jié)果對(duì)比情況。其中，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對(duì)比

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

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

4.3.2 算法效率

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

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

5 結(jié)束語(yǔ)

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

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