安云哲,吳東翰,夏秀峰,周大海,朱睿

（沈陽航空航天大學(xué)計算機學(xué)院,遼寧 沈陽 110136）

隨著現(xiàn)代社會的發(fā)展,工業(yè)互聯(lián)網(wǎng)、制造行業(yè)等領(lǐng)域產(chǎn)生了大量的數(shù)據(jù),人們在關(guān)注數(shù)據(jù)整體趨勢的同時,也開始越來越關(guān)注那些表現(xiàn)與數(shù)據(jù)集中其他數(shù)據(jù)存在明顯不同的異常值,因為這些數(shù)據(jù)點往往蘊含著更加有用的信息.為了從這些數(shù)據(jù)中發(fā)掘到更有價值的信息,許多應(yīng)用都依賴于數(shù)據(jù)流[1]上的離群點檢測技術(shù).而隨著有關(guān)離群點檢測的需求增多,用戶不再滿足單一的離群點檢測,想要從數(shù)據(jù)中找到更多有價值的信息,從而產(chǎn)生許多離群點的查詢?nèi)蝿?wù).然而,對于這個問題,現(xiàn)有的離群點檢測算法大多是面向單查詢的檢測,不能解決用戶需求.因此,本文提出面向流數(shù)據(jù)的多離群點檢測算法來解決這個問題.

離群點檢測問題是由Knorr和Ng[2-3]先提出的.離群點檢測查詢旨在數(shù)據(jù)集中查找鄰居個數(shù)少于k的對象.在此基礎(chǔ)上Ramaswamy[4]修改了Knorr和Ng提出的方法,引入基于k近鄰的定義,它將對象與其k近鄰的距離作為對象的分?jǐn)?shù),向系統(tǒng)返回分值最高的n個對象.為支持該查詢,該工作提出了一種基于分區(qū)的算法,來增加查詢效率.但是,該工作沒有考慮到一個點的k-鄰域中包含的信息,因此不能正確的適用于分布密集或稀疏的鄰域.所以針對這一問題,本文采取分區(qū)的方式對數(shù)據(jù)進行處理,來解決數(shù)據(jù)分布的問題,以此來提高查詢效率,減少不必要的查詢損失.

針對流數(shù)據(jù)上的基于距離的離群點檢測算法的相關(guān)研究[4-5]中,一般采用索引的方式來對數(shù)據(jù)進行管理.基于索引的算法被Jiawei等[6]提出,該算法依賴于構(gòu)建出索引（R樹[7],M樹[8],KD樹[9]等）的性能.但是當(dāng)數(shù)據(jù)的維度增加的時候,算法的性能也會降低.Bay等[10]提出了基于嵌套循環(huán)的ORCA算法,這個算法是對于基于分區(qū)的算法的改進.在該算法中,運用簡單的剪枝策略和數(shù)據(jù)點隨機化,可以有效的檢測出符合離群點的定義.由于ORCA是基于磁盤處理的算法,而無法從內(nèi)存中進行數(shù)據(jù)的讀取操作,因此在大的數(shù)據(jù)集中無法使用.在文獻[11]中朱利等人基于最小生成樹提出了相關(guān)算法,能夠自動辨認簇的數(shù)量并挖掘出不同類別的異常數(shù)據(jù).在文獻[12]中使用了KD樹作為索引.雖然在使用索引結(jié)構(gòu)后能夠加快檢測的執(zhí)行時間,但是由于索引結(jié)構(gòu)會隨著屬性數(shù)量的增加,索引的更新和維護效率下降,會影響到算法檢測的效率.但是這些算法只能針對單查詢問題進行解決,而且索引結(jié)構(gòu)會隨著屬性數(shù)量的增加,索引的更新和維護效率下降,會影響到算法檢測的效率.針對這一問題,本文提出一種基于網(wǎng)格索引的查詢框架,將數(shù)據(jù)點按照維度信息進行存儲.在進行查詢時可以直接找到查詢數(shù)據(jù)所在位置,直接返回即可.通過該方法,增加查詢效率,減少維度對查詢效率的影響,極大的提高了離群點檢測算法的查詢效率.

現(xiàn)有的多離群點檢測算法大都通過在索引或者單查詢方面進行改進.Konkaki等[13]初步探討了在流數(shù)據(jù)的環(huán)境下多查詢的離群點的檢測方法.提出的算法通過減少內(nèi)存的開銷來增加查詢效率.但是進行范圍查詢來搜索其鄰居集合是需要花費昂貴的代價,而當(dāng)滑動窗口內(nèi)的數(shù)據(jù)增加的情況下,這個算法中單離群點檢測的查詢處理的效率也會隨之下降.而Georgiadis等[14]在此基礎(chǔ)上提出了一個可拓展的框架,雖然在運行時間和算法的靈活性上面有著較好的改進,但是對于多離群點檢測的多查詢處理方面還沒有一個較好的方式.Gao等[15]提出的SOP方法.該算法考慮到用戶不同的檢測需求而衍生出多種的查詢條件.該算法將多離群點檢測問題轉(zhuǎn)換成skyline問題,通過從滑動窗口從后向前來為每一個查詢點來構(gòu)建一個skyline表來進行查詢.再通過每個點鄰居到其的距離和到達時間的前后來回答每一個查詢檢測.判讀查詢點是否是離群點.這種方法避免了上述文獻中的常規(guī)范圍搜索.但是由于需要維護每個查詢點的skyband點鄰居表,在滑動窗口數(shù)據(jù)流入流出時對鄰居表進行維護和更新,所需開銷較大.針對多離群點檢測方面,本文考慮到多查詢?nèi)蝿?wù)增多的情況.因此通過多查詢檢測任務(wù)之間的包含關(guān)系,利用多查詢之間的共享機制來支持多查詢的檢測問題,來降低查詢規(guī)模對算法性能的影響.在查詢點過程中采用索引的方式來提高查詢效率,來解決多離群點檢測問題.

1 多離群點檢測相關(guān)定義

一般情況下,基于距離的離群點檢測可以分為基于閾值、基于kmax和基于ksum的檢測.本文主要關(guān)注基于閾值的離群點檢測.具體地,給定兩個參數(shù)閾值k和查詢半徑r,以及兩個對象o1,o2,如果它們之間的距離小于參數(shù)r,則稱o1為o2的鄰居.此外,如果一個對象在查詢半徑內(nèi)r的鄰居數(shù)量大于另一個參數(shù)閾值k,則將這個對象視為非離群點,否則將其視為離群點.在滑動窗口環(huán)境中,離群點檢測對窗口進行監(jiān)控,并在窗口滑動時報告窗口中的所有離群點.如下圖所示:D（o1,o2）=l,長度小于查詢半徑r,那么它們就是彼此的鄰居.給定對象o3和o4,其中o3有2個鄰居,少于閾值k（=3）,所以o3是離群點,而o4有三個鄰居,鄰居的數(shù)量不小于3.因此,o4是非離群點.多離群點檢測示意見圖1.

圖1 多離群點檢測示意Fig.1 Schematic diagram of multiple outlier detection

定義1歐式距離:給定由一組d維數(shù)據(jù)對象組成的集合D,對象oi和oj屬于集合D,對象oi和對象oj的歐式距離的計算如下式

定義2鄰居點:給定一組由d維數(shù)據(jù)對象組成的集合D,距離參數(shù)l,對象oi和oj屬于集合D,如果對象oi和oj之間的歐式距離dist( oi, oj)≤l,則表示對象oi與對象oj互為對方的鄰居.

定義3離群點:給定由一組d維數(shù)據(jù)對象組成的集合D,查詢閾值k和查詢半徑r,對象o屬于集合D,如果查詢對象o在查詢半徑r的范圍內(nèi)的鄰居數(shù)量少于查詢閾值k,則查詢對象o表示為離群點.反之則稱為非離群點.

在圖1中,D（o1,o2）=l,表示的是對象之間的歐氏距離為l,但是兩個點之間的距離都小于給定的查詢半徑r,那么它們之間就是彼此的鄰居.在離群點的概念中,圖中o3,o4兩個數(shù)據(jù)點,其中o3在查詢半徑的范圍內(nèi)的鄰居的數(shù)量少于判斷閾值k,根據(jù)離群點定義,o3是離群點,而o4根據(jù)定義則是非離群點.

定義4滑動窗口:給定滑動窗口W（N,S）,它存在兩種定義形式:分別為基于窗口容量的窗口和基于時間間隔的窗口.基于窗口容量的窗口包含N個最新到達窗口的對象,每次流入和流出窗口的對象個數(shù)為S;基于時間的窗口包含最近N個時刻到達窗口的對象,窗口每滑動一次的時間間隔為S.

定義5滑動窗口的連續(xù)離群點檢測:給定一個滑動窗口W,以及參數(shù)為k、r.基于離群點的概念,我們監(jiān)測窗口W,如果查詢對象的鄰居數(shù)量少于參數(shù)k,則在窗口滑動時判定為離群點.

下面通過例子來對滑動窗口上的離群點檢測進行說明,如圖2所示,同樣給定兩個參數(shù)k=3、r不變和兩個對象o1,o2.S1虛線部分表示的是當(dāng)前的滑動窗口,S2實線部分是滑動后的S1,滑動數(shù)量為5.當(dāng)前窗口S1中,在o1的查詢半徑r的范圍內(nèi)有三個鄰居分別是點.而o2點周圍有兩個鄰居,分別是.此時,在S1中,因為o1的周圍的鄰居數(shù)為3個大于等于判斷閾值k個,所以o1在S1中是非離群點,與之相對的點o2的鄰居數(shù)量是2個,小于閾值k,則在S1中是中是離群點.但當(dāng)窗口從S1滑到S2的時候,S1窗口中的白色的點為過期點,流出窗口,S2窗口中黑色的點表示的是新進來的點.在新的當(dāng)前窗口S2（實體框）中,這時原o1的鄰居中的點o3過期,流出窗口,o1的鄰居變?yōu)?o4,o5>,其鄰居數(shù)量小于閾值k（=3）,則在當(dāng)前窗口S2中隨著滑動窗口滑動變成了離群點.而查詢點o2,隨著窗口滑動,點o8和o9成為它的新鄰居點,此時其鄰居集合為,數(shù)量為4大于查詢閾值k,則它在當(dāng)前窗口S2中為非離群點.

圖2 滑動窗口上的離群點檢測Fig.2 Outlier detection on sliding windows

定義6q（k,r）查詢定義:給定一組離群點檢測參數(shù)閾值k,和查詢范圍r.在一次離群點檢測操作中返回滿足查詢條件為k和r的離群點的處理過程稱為一次查詢,用q（k,r）來表示.

定義7多查詢定義:基于定義6,多離群點檢測是指,返回滿足一組不同的參數(shù)k與r的查詢Q={q1( k1, r1),q2( k2, r2),...,qm(km,rm)}的離群點檢測過程,可以定義為大Q( ki, ri).

對于基于滑動窗口的離群點檢測來說,返回一次查詢的結(jié)果,表示的是單查詢.即給定查詢閾值k和r,在滑動窗口上檢測查詢點r的半徑范圍內(nèi)所包含的點數(shù),如果包含的點數(shù)大于閾值k的話,則表示是非群群點,而這樣的過程就是一個查詢.那么對于多查詢來說,就是多組這樣閾值一次掃描來進行離群點檢測的集合.如圖1所示,給定兩個參數(shù)k=3、r不變,表示是其中的一個查詢q（k,r）,另兩個參數(shù)k=3、r1不變表示的是另一個查詢q1（k,r1）.這兩個查詢的查詢結(jié)果一次掃描而得到.

2 多離群點檢測算法

為了更好地進行離群點的檢測,本文提出了一種查詢處理框架MQOD（Multiple Query of Outlier Detection）支持多離群點檢測.首先利用多查詢集合中子查詢?nèi)蝿?wù)間的包含關(guān)系減少查詢次數(shù).其次,再采用分片技術(shù)對于查詢點進行搜索,減少查詢次數(shù),提高查詢效率.

2.1 MQOD查詢算法框架

由介紹的多查詢的定義可知,多離群點檢測就是多個單查詢?nèi)蝿?wù)組成的離群點檢測問題.對于單個查詢的離群點檢測問題,可以通過遍歷數(shù)據(jù)集來判斷是否查詢點是否是離群點.但是這種方式不適合多查詢?nèi)蝿?wù),這種方式會造成資源的浪費.

正如前文提到的問題,在多離群點檢測的問題中需要解決多查詢?nèi)蝿?wù)的問題.在檢測過程中不能對每個查詢都進行一次查詢,這個過于浪費時間.算法的思想是:利用多查詢之間的共享機制,可以減少不必要的時間開銷.在多查詢?nèi)蝿?wù)進行離群點檢測時,有些查詢?nèi)蝿?wù)在檢測時,會查找到并計算其他查詢?nèi)蝿?wù)所需要的鄰居集合的部分?jǐn)?shù)據(jù)點,而如果直接再重新對剩下的查詢?nèi)蝿?wù)進行檢測的話,就會造成這方面的計算的浪費.

基于此,本文提出一種利用查詢?nèi)蝿?wù)之間的共享機制,提出一種基于面向流數(shù)據(jù)的多離群點檢測算法MQOD.給一組多查詢集合Q={q1( k1, r1),q2( k2, r2),...,qm(km,rm)},為了減少多查詢的離群點檢測的次數(shù),提高查詢效率.由于每個查詢在搜索的過程中都會去在查詢半徑的范圍內(nèi)找到自身所需要的鄰居集合來判斷查詢點是不是離群點,因此如果能夠通過一次查詢操作,就能找到其滿足他查詢?nèi)蝿?wù)所需要的鄰居集合,就不需要再進行多次查詢來操作尋找各自的鄰居集合.因此,利用查詢?nèi)蝿?wù)范圍閾值的關(guān)系來進行解決這個問題,即在每組構(gòu)建一個最大的子查詢,這個最大的子查詢范圍閾值內(nèi)的鄰居集合,通過這個集合去支持其他所有查詢?nèi)蝿?wù)的判定.

基于上述思想,通過構(gòu)建一個范圍查詢Range（r）來找到所需要的鄰居集,其中范圍閾值r的大小為分組查詢中查詢半徑最大的那個.這樣,只需要對查詢點進行一次范圍查詢就能得到所有查詢?nèi)蝿?wù)所需要的鄰居集合,再通過這個集合去判斷查詢點對于查詢?nèi)蝿?wù)是否為離群點即可.

如圖3所示,在二維空間中,給定三個查詢q1（k1,r1）,q2（k2,r2）,q3（k3,r3）,分別對點o進行離群點檢測.其中查詢q3（k3,r3）的鄰居閾值k與范圍閾值r最大,所以這里所需選擇的最大的查詢半徑是r3.因此構(gòu)建查詢?nèi)蝿?wù)Range（r3）.如圖所示,在查詢Range（r3）范圍閾值r3的范圍內(nèi)包含查詢點o的12個鄰居,其中包含三個查詢?nèi)蝿?wù)的鄰居集合.q1（k1,r1）,q2（k2,r2）,q3（k3,r3）可以在這12個鄰居中找到其查詢半徑內(nèi)的鄰居,來判斷查詢點是否為離群點.

圖3 范圍查詢的鄰居集合Fig.3 Neighbor set for range query

下面介紹范圍查詢算法.

算法1是離群點的范圍查詢,返回的是第一次范圍查詢后的鄰居點集合.算法首先計算查詢范圍,在查詢集合Q={q1( k1, r1),q2( k2, r2),...,qm(km,rm)}中找到其中查詢半徑最大的當(dāng)作查詢范圍,并構(gòu)建范圍查詢集合（詳見算法3-6行）.算法的7到10行說明了范圍查詢的具體執(zhí)行過程,第一次范圍查詢是從滑動窗口的后半部分,然后依次從后向前進行查找.算法先計算流入點oin的空間位置信息,再通過該點的位置信息得到其周圍網(wǎng)格的位置,最后在這些網(wǎng)格中進行搜索其鄰居點,并得到查詢點的鄰居集合.最后,按照鄰居點和查詢點之間的距離進行排序并返回鄰居集合.

2.2 MQOD查詢算法索引結(jié)構(gòu)

為了更高效地進行離群點檢測,本文提出HT-Grid索引結(jié)構(gòu)來管理滑動窗口上的數(shù)據(jù).該索引結(jié)構(gòu)是將離群點在空間中的位置特性和網(wǎng)格索引相結(jié)合,再利用hash表進行快速更新與查找的一種索引結(jié)構(gòu),它能夠幫助算法實現(xiàn)離群點的快速檢測.其次,該索引結(jié)構(gòu)的實現(xiàn)主要是利用數(shù)據(jù)點的維度信息,將這些維度空間位置的信息進行換算,得到數(shù)據(jù)點在HT-Grid索引的存儲位置,然后再進行插入或刪除操作.由于HT-Grid索引和hash相結(jié)合,只需要在hash表HT上O（1）的時間復(fù)雜度內(nèi)進行查找就能直接確定數(shù)據(jù)所處位置,減少了搜索的時間.此外,該索引還能夠通過hash表降低維度增加所引發(fā)的空間代價.

如圖4所示,HT-Grid索引結(jié)構(gòu)由兩個部分構(gòu)成,分別是管理滑動窗口W內(nèi)的數(shù)據(jù)點的空間位置的虛擬網(wǎng)格,以及管理虛擬網(wǎng)格相對位置的HT索引.使用HT索引的目的是為了更加快速的找到查詢點所在的位置,方便查詢操作.在虛擬網(wǎng)格內(nèi),為了方便離群點檢測時鄰居集合的范圍查詢,在邏輯上將網(wǎng)格窗口按照時間順序進行分割,對應(yīng)滑動窗口劃分的位置.圖4中,網(wǎng)格中有一個查詢點o,它的二維空間信息是（x,y）,計算可知:查詢點o位于ID為（3,3）的單元格中.算法可根據(jù)單元格id信息計算該單元格的Z-地址,進而通過哈希函數(shù)將點o映射到相應(yīng)的桶內(nèi).如果該桶尚為空,算法初始化一個空桶,將該空桶插入索引,隨后將對象插入該桶.否則,算法可直接將對象o插入該桶.

圖4 HT-Grid索引構(gòu)造Fig.4 HT-Grid Index Construction

為了更好地進行范圍搜索,算法在邏輯上將網(wǎng)格內(nèi)的點按照時間順序進行分組,利用滑動窗口的開始和結(jié)束的位置,將網(wǎng)格分成4組.在查詢的時候,優(yōu)先從時間排在后面的組進行搜索,盡量搜索到查詢點后面的鄰居,如果能找到滿足使一個查詢點成為安全點的鄰居數(shù)量,那么對于一些查詢來說就不需要再考慮這個點了.這樣一來,訪問對象數(shù)目可有效降低.

正是由于滑動窗口內(nèi)的點的時間特性,該算法在離群點檢測的時候采取從后向前的方式對于滑動窗口內(nèi)的點進行搜索.首先,算法用分片技術(shù)對滑動窗口進行分片,將窗口分成4部分,分別在窗口的1/2,1/4,1/8處進行劃分.這樣在進行鄰居查詢的時候,首先在窗口的后1/2部分開始,從后向前的順序在網(wǎng)格中進行查找判斷.如果窗口后1/2部分的點,能夠找到支持所有查詢的鄰居集合的時候就停止搜索.相反的話,如果沒有找到這樣的鄰居集合的話,就繼續(xù)向前查找窗口1/4長度的數(shù)據(jù)點.再進行判斷,依然不足的話,最后再去尋找窗口長度為1/8的點,直至窗口最后剩下的部分.

如圖5所示,圖中的數(shù)據(jù)為二維數(shù)據(jù),其中X,Y表示數(shù)據(jù)點的鄰居閾值和范圍閾值兩個維度的信息.圖5-a表示的是滑動窗口內(nèi)部的點所存儲的網(wǎng)格結(jié)構(gòu),當(dāng)查詢點o進行查詢時,首先通過hash計算得到其所在的網(wǎng)格位置并且得到其周圍鄰居網(wǎng)格的hash位置,然后在這些網(wǎng)格中利用流數(shù)據(jù)的時間屬性來從后向前找到查詢點的鄰居集合,如果網(wǎng)格內(nèi)部沒有點則直接可以濾過,只需要找有點的網(wǎng)格即可.圖5-b表示的是每次查找的范圍,網(wǎng)格中設(shè)有標(biāo)簽,每次查詢遞進剩余窗口大小的一半,最小為窗口長度的1/8,如果剛開始就在滑動窗口的后一半就能找到所需要的鄰居點集合那么就不需要再向前遞進查找了,這樣減少不必要的搜索次數(shù).

圖5 HT-Grid索引范圍查詢Fig.5 HT-Grid Index Range Query

2.3 MQOD多查詢檢測算法

在得到每組最大的范圍內(nèi)的鄰居集合之后,需要對所有的支配的集合查詢進行離群點判定問題.在這里,使用k鄰近距離的概念去解決這個問題.

定義8k-鄰近距離（k-distance）：給定一組數(shù)據(jù)集,集合中在距離數(shù)據(jù)點o最近的幾個點中,第k個最近的點跟點o之間的距離,則稱為點o的k-鄰近距離,記為k-distance（o）.

根據(jù)k臨近距離的概念,來回答其他查詢的判定問題.值得注意的是查詢點o的k-近鄰距離的點并不唯一,有可能有多個數(shù)據(jù)點和查詢點o的距離與k-鄰近距離相同,這些點都是查詢點k-鄰近距離的點.利用這一點,當(dāng) 范圍查詢算法的返回查詢點的鄰居集合后,再根據(jù)分組的各個查詢?nèi)蝿?wù)閾值k來找到查詢點的k-distance（o）.如果對于一個查詢q（k,r）來說,查詢點的o的k-distance（o）不大于查詢半徑r的話,也就是說在查詢半徑范圍內(nèi)至少有k個點是查詢點的鄰居,那么對于查詢q（k,r）來說,查詢點o不是離群點.相反,如果查詢點o的k-distance（o）大于查詢半徑r的話,則表示在查詢范圍內(nèi)的鄰居集合的數(shù)量少于查詢閾值k,查詢點o對于查詢q（k,r）來說是離群點.因為多離群點檢測的查詢之間的順序是按照查詢閾值k從小到大的順序進行排列的,所以只要在范圍查詢的鄰居集合中按照k-distance（o）與需要檢測的查詢半徑進行比較即可.下面將介紹多查詢分組檢測算法.

算法2:多查詢檢測算法

3 實驗驗證

3.1 實驗條件

本文算法均由C++語言編寫,使用VS2019進行編譯.實驗平臺為Win10操作系統(tǒng),CPU型號為Intel（R）Xeon（R）Gold 6226R CPU@2.90GHz,2.89 GHz,內(nèi)存256GB.

3.2 實驗數(shù)據(jù)

（1）數(shù)據(jù)集:為了增加實驗的可信度,本文采取5個數(shù)據(jù)集進行算法的驗證.其中Tao、Stock兩個是真實的數(shù)據(jù)集,其它為合成的數(shù)據(jù)集.其中Tao是一個熱帶海洋項目的數(shù)據(jù),本文只使用了其中較小的一部分,包含了共575 648條記錄數(shù)據(jù),每條數(shù)據(jù)有3個屬性.真實數(shù)據(jù)集Stock為中國深滬兩市2015—2016年約2 300支股票的交易記錄,原始數(shù)據(jù)規(guī)模約為30 GB.實驗對數(shù)據(jù)進行清洗.首先將數(shù)據(jù)中非數(shù)值信息進行剔除,只保留數(shù)值信息;其次對數(shù)據(jù)中缺失數(shù)值的記錄進行刪除,再進行去重后,只保留剩下的數(shù)值記錄.在對數(shù)據(jù)進行清洗之后,取確認數(shù)據(jù)集中的3個屬性,來作為本文實驗數(shù)據(jù)集,數(shù)據(jù)規(guī)模為1 GB左右,60余萬條數(shù)據(jù).最后的三個合成數(shù)據(jù)集SD1、SD2、SD3,最大的SD1數(shù)據(jù)集為100萬條數(shù)據(jù),SD2、SD3分別為30和70萬條數(shù)據(jù),為隨機生成的數(shù)據(jù)集.

（2）參數(shù)設(shè)置:針對多離群點檢測的參數(shù)設(shè)置問題,首先是查詢?nèi)蝿?wù)的數(shù)量的不同,意即查詢?nèi)蝿?wù)中查詢閾值和查詢半徑的不同.其次,針對多查詢索引結(jié)構(gòu)來說,索引的構(gòu)建時間和索引的更新效率也需要被評估.其中參數(shù)設(shè)置中的N是表示滑動窗口的長度,s表示的滑動窗口數(shù)據(jù)每次流入流出的數(shù)量,k和r分別表示的多查詢?nèi)蝿?wù)的查詢閾值和查詢范圍.實驗參數(shù)設(shè)置見表1.

表1 實驗參數(shù)設(shè)置Tab.1 Parameter Settings

（3）實驗方法:本文選用流數(shù)據(jù)上的兩種離群點檢測算法exact-Storm算法和abstract-C作為對比試驗.由于兩種算法僅適用于單查詢,為了更好地與本文的實驗進行對比,對于兩種算法按照順序進行執(zhí)行,以此來保障對比效果.本文將從查詢集合任務(wù)數(shù)量、數(shù)據(jù)量大小、窗口大小三個方面在三個數(shù)據(jù)集上進行實驗對比.

3.3 實驗結(jié)果分析

3.3.1 查詢數(shù)量對于算法的影響 實驗結(jié)果如圖6所示,在圖中分別對兩組數(shù)據(jù)量相近的數(shù)據(jù)集進行實驗,其中圖6-a表示的是數(shù)據(jù)集tao,圖6-b表示的是數(shù)據(jù)集stock.在圖6中的兩個實驗中,設(shè)置的默認窗口長度是10 000,默認的窗口流速為500,設(shè)置了不同的查詢?nèi)蝿?wù)數(shù)量為{10,20,30,40,50}.可以看出,隨著查詢數(shù)量的增加三個算法的時間開銷也相應(yīng)的增多.本文算法MQOD并不會隨著查詢數(shù)量的增多而出現(xiàn)明顯的增長變化,而是保持相對穩(wěn)定的狀態(tài),而算法exact-Storm和算法abstract-C則會隨著查詢數(shù)量的增多呈現(xiàn)明顯的上升趨勢,因而在進行多離群點檢測時,這兩個算法判斷檢測的代價會隨之增加,也會造成不必要的時間成本.與abstract-C算法相比,算法exact-Storm在查詢效率上具有優(yōu)勢.

圖6 查詢數(shù)量對查詢的影響Fig.6 Query efficiency vary Numbers

3.3.2 數(shù)據(jù)集大小對于多查詢的影響 為了更加直觀的對數(shù)據(jù)算法進行驗證,使用合成數(shù)據(jù)30萬個點和70萬個點的兩個集合進行實驗.在實驗中,設(shè)置查詢?nèi)蝿?wù)的數(shù)量為50,其中的查詢閾值和查詢半徑互不相同,滑動窗口的流速與上文相同.實驗結(jié)果如圖7所示.圖7主要是通過數(shù)據(jù)集中點數(shù)的變化來判斷多查詢算法的效率,查詢集合選擇{30,50,70,100}四個數(shù)據(jù)集,單位是103.從圖7中可以看出算法exact-Storm和abstract-C的多離群點的檢測時間會隨著查詢的數(shù)據(jù)集的大小成線性增加,在數(shù)據(jù)集大的時候相應(yīng)的檢測時間也會增多.本文提出的離群點檢測算法,在處理多查詢?nèi)蝿?wù)時會根據(jù)任務(wù)的閾值和查詢半徑來進行分組來減少查詢次數(shù),保障用盡可能少的查詢遍歷次數(shù)來回答所用的查詢?nèi)蝿?wù),因此相對于其他兩個對比算法來說,不會出現(xiàn)時間隨著數(shù)據(jù)集的增大而出現(xiàn)明顯增長情況,多查詢的檢測時間的表現(xiàn)比較穩(wěn)定.

圖7 數(shù)據(jù)集大小對查詢影響Fig.7 Query efficiency of Dataset size

3.3.3 窗口大小對多查詢算法的影響 本文采用stock作為實驗的數(shù)據(jù)集合,實驗結(jié)果如圖8所示.從圖中可以看出,查詢窗口較小的時候,三個算法的效率基本相同.隨著窗口的增大,需要處理的數(shù)據(jù)也相應(yīng)的增多,花費的時間也明顯的增多.算法exact-Storm和算法abstract-C在10 kb窗口大小之前效果基本一致,在窗口增加到一半時,出現(xiàn)明顯變大的趨勢,而本文算法MQOD的表現(xiàn)較為穩(wěn)定.

圖8 窗口大小對查詢的影響Fig.8 Query efficiency vary Windowsize

4 小結(jié)

離群點檢測問題作為數(shù)據(jù)挖掘領(lǐng)域中的一個重要研究,本文提出面向流數(shù)據(jù)的多離群點檢測算法,該算法能夠?qū)?shù)據(jù)流中的離群點進行快速檢測和更新,利用查詢條件之間的包含關(guān)系來減少查詢次數(shù).進一步提出HT-Grid索引結(jié)構(gòu),對數(shù)據(jù)流進行管理,減少搜索代價,增加查詢效率.并通過實驗驗證了該算法的有效性和穩(wěn)定性.下一步工作中,我們將考慮進一步的提高分組查詢方法,從而提高查詢效率.