覃偉榮+王寧

摘 要： 針對(duì)現(xiàn)有的數(shù)據(jù)流異常檢測(cè)算法的不足，提出一種基于隨機(jī)空間樹的數(shù)據(jù)流異常檢測(cè)算法。首先，采取統(tǒng)計(jì)策略對(duì)數(shù)據(jù)流特征范圍進(jìn)行估計(jì)，分割得到多棵隨機(jī)空間樹（RS?Tree），形成RS森林（RS?Forest）。然后，RS?Forest采用單窗口策略對(duì)數(shù)據(jù)流進(jìn)行處理，通過(guò)打分和模型更新來(lái)實(shí)現(xiàn)異常檢測(cè)。針對(duì)實(shí)例落入的樹節(jié)點(diǎn)，定義分段恒定密度，求取密度估計(jì)值相對(duì)于森林中所有樹的平均值，并將其作為數(shù)據(jù)流中每個(gè)新來(lái)實(shí)例的得分。利用相對(duì)于森林中所有樹的平均得分對(duì)每個(gè)新來(lái)實(shí)例進(jìn)行排序。窗口滿后則采用對(duì)偶式節(jié)點(diǎn)剖度技術(shù)進(jìn)行模型更新，并利用采集的節(jié)點(diǎn)尺寸信息對(duì)下一輪到達(dá)窗口的數(shù)據(jù)進(jìn)行打分。利用多種基準(zhǔn)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明RS?Forest算法在大部分?jǐn)?shù)據(jù)集下的AUC得分和運(yùn)行時(shí)間性能均優(yōu)于當(dāng)前其他基準(zhǔn)算法。

關(guān)鍵詞： 數(shù)據(jù)流； 異常檢測(cè)； 隨機(jī)空間樹； 單窗口策略； AUC得分； 運(yùn)行時(shí)間

中圖分類號(hào)： TN915.08?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）19?0056?06

A data stream anomaly detection algorithm based on randomized space tree

QIN Weirong1， WANG Ning2

（1. School of Electronics and Information Engineering， Qinzhou University， Qinzhou 535000， China；

2. School of Information Engineering， Zhengzhou University， Zhengzhou 450001， China）

Abstract： Aiming at the shortcomings of the available data stream anomaly detection algorithms， a data stream anomaly detection algorithm based on randomized space tree （RS?Tree） is proposed. The statistical strategy is adopted to estimate the characteristic range of data stream， by which several randomized space trees are obtained by means of segmentation to form RS?Forest. The single window policy is used by RS?Forest to process the data stream， and realize anomaly detection by means of scoring and model updating. According to the tree node that an instance falls in， the piecewise constant density is defined to get the average value of the density estimation values relative to all the trees in forest， which is taken as the score of each new instance in data stream. The average score of all the trees relative to forest is employed to sort each new instance. When the windows are occupied， the antithetic node dissection technology is used to update the model， and the acquired node size information is used to mark the data arriving at the window in the next round. The simulation experiments were carried out with variety of benchmark datasets. Its results show that the AUC scoring and run time performance of RS?Forest algorithm for most datasets are superior to those of other benchmark algorithms.

Keywords： data stream； anomaly detection； randomized space tree； single window policy； AUC scoring； run time

0 引 言

異?；螂x群點(diǎn)是指與正常點(diǎn)或預(yù)期點(diǎn)不吻合或偏離正常點(diǎn)的罕見事件或罕見點(diǎn)。對(duì)于軍事偵查、網(wǎng)絡(luò)安全管理、工業(yè)系統(tǒng)監(jiān)控等眾多領(lǐng)域，如果不能立即檢測(cè)出這些異常事件，便有可能造成嚴(yán)重后果。隨著近些年硬件技術(shù)的迅速發(fā)展，上述領(lǐng)域的持續(xù)性數(shù)據(jù)采集能力獲得顯著提升，采集到的大部分?jǐn)?shù)據(jù)不再是有限的或靜態(tài)數(shù)據(jù)，而是無(wú)限制的大容量高速實(shí)時(shí)數(shù)據(jù)，稱其為數(shù)據(jù)流。

異常檢測(cè)一直是數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)[1?3]。然而，數(shù)據(jù)流的內(nèi)在特點(diǎn)對(duì)當(dāng)前大部分異常檢測(cè)技術(shù)（如HSTa[4]，LOADED[5]，Hoeffding Trees（HT）[6]以及BoostHT[7]等）構(gòu)成嚴(yán)重挑戰(zhàn)。首先，數(shù)據(jù)流的生成速度前所未有，因此需要迅速處理。這便要求檢測(cè)模型的更新速度快于數(shù)據(jù)率，而且檢測(cè)器必須能夠適應(yīng)數(shù)據(jù)流信息生成速度較快這一特點(diǎn)。其次，傳統(tǒng)的異常檢測(cè)算法[8?9]在構(gòu)建模型時(shí)需要將數(shù)據(jù)保存于內(nèi)存中。由于數(shù)據(jù)流的數(shù)據(jù)量極大，容易將內(nèi)存耗盡，所以傳統(tǒng)方法將會(huì)失效。再次，對(duì)數(shù)據(jù)流來(lái)說(shuō)，無(wú)論是正常事件還是異常事件均處于不斷變化之中，容易使利用老舊數(shù)據(jù)學(xué)習(xí)而得到的檢測(cè)模型過(guò)時(shí)。因此，檢測(cè)算法應(yīng)該能夠適應(yīng)于正常行為隨時(shí)間不斷變化這一特點(diǎn)。最后，實(shí)踐中數(shù)據(jù)流的異常實(shí)例非常罕見，甚至無(wú)法獲得。這就要求異常檢測(cè)技術(shù)即使只利用正常事件進(jìn)行訓(xùn)練，也應(yīng)該能夠準(zhǔn)確地檢測(cè)出可疑行為。針對(duì)以上方法的不足，本文提出一種基于隨機(jī)空間樹（Randomized Space Tree，RS?Tree）的數(shù)據(jù)流異常檢測(cè)算法，并通過(guò)理論分析和仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

1 本文算法

1.1 基本定義

定義1：隨機(jī)空間樹，它是一種完全二叉樹，可通過(guò)隨機(jī)選擇一種屬性及被選屬性的割點(diǎn)來(lái)構(gòu)建。

深度為[HH≥0]的RS?Tree共有[2H+1-1]個(gè)節(jié)點(diǎn)，其中葉節(jié)點(diǎn)的深度均為[H]。RS?Tree起源于隨機(jī)決策樹[10]，不用數(shù)據(jù)便可構(gòu)建出樹結(jié)構(gòu)。在構(gòu)建RS?Tree時(shí)，算法不斷從特征集中選擇一種屬性，然后隨機(jī)確定這種屬性的分割點(diǎn)來(lái)實(shí)現(xiàn)樹的分割，直至到達(dá)樹深[H]。

定義2：RS?Tree中的節(jié)點(diǎn)剖度，已知數(shù)據(jù)樣本后，該節(jié)點(diǎn)表示相應(yīng)區(qū)域中落入的實(shí)例數(shù)量。

定義3：基于隨機(jī)空間樹[T]的分段恒定密度估計(jì)，其表達(dá)式為：

[fx；T=?x，TNV?x，T] （1）

式中：[?x，T]表示終止節(jié)點(diǎn)；[?]表示節(jié)點(diǎn)尺寸或節(jié)點(diǎn)剖度；[V?]為節(jié)點(diǎn)所表示的超矩形的容積。在RS?Tree中，終止節(jié)點(diǎn)是指用于密度估計(jì)的節(jié)點(diǎn)，它可為葉節(jié)點(diǎn)，或者是首個(gè)滿足節(jié)點(diǎn)尺寸約束（即小于等于）的節(jié)點(diǎn)。

定義4：基于RS森林[F]的密度估計(jì)，其表達(dá)式為：

[fx；F=1Mt=1Mfx；Tt] （2）

式中：[fx；Tt]表示第[t]棵樹的密度估計(jì)；[M]表示RS樹的數(shù)量。

1.2 RS樹的構(gòu)建

（1） 樹節(jié)點(diǎn)的初始化。深度為[H]的RS樹包含[2H+1-1]個(gè)節(jié)點(diǎn)。在部署時(shí)，每個(gè)節(jié)點(diǎn)包含如下元素：

① 變量[ml]和[mr]，用于交替記錄預(yù)測(cè)模型或窗口內(nèi)數(shù)據(jù)流的節(jié)點(diǎn)剖度；

② 3個(gè)節(jié)點(diǎn)指針，分別指向當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)，右子節(jié)點(diǎn)及母節(jié)點(diǎn)；

③ 變量[v，]用于存儲(chǔ)當(dāng)前節(jié)點(diǎn)容積與整個(gè)特征空間容積之比的對(duì)數(shù)。

（2） 屬性范圍估計(jì)。確定每個(gè)屬性的正確范圍是構(gòu)建RS樹結(jié)構(gòu)的重要步驟。如果范圍過(guò)緊（比如從數(shù)據(jù)樣本中直接確定的范圍），則無(wú)法適應(yīng)整個(gè)數(shù)據(jù)流的潛在變化。另一方面，如果范圍過(guò)寬，則會(huì)引入不必要的噪聲及沒有意義的空間分割。因此，本文采用如下的統(tǒng)計(jì)策略來(lái)估計(jì)每個(gè)屬性的合理范圍：首先，針對(duì)屬性[i]的均值，計(jì)算90%的最高后驗(yàn)密度（Highest Posterior Density，HPD）置信區(qū)間[LMi，UMi]。然后，根據(jù)[3σ]準(zhǔn)則擴(kuò)大上述置信區(qū)間。即將下界設(shè)置為[LBi=LMi-3σ，]將上界設(shè)置為[UBi=UMi+3σ，]其中[σ]表示屬性[i]的標(biāo)準(zhǔn)差。這種方式生成的下界和上界值（即LB和UB）作為算法1的輸入，進(jìn)而生成單個(gè)RS樹的結(jié)構(gòu)。

算法1 BuildRS?TreeStructure[LBs，UBs，e，H]

輸入：[LBsUBs]：屬性的下（上）界列表，

[e：]當(dāng)前樹的深度，[H：]樹深界限；

輸出：一棵RS樹

1：if [e≥H] then

2： Return [leaf（ml←0，mr←0）]；

3：else

4： 對(duì)非葉節(jié)點(diǎn)[root]初始化；

5： 隨機(jī)選擇一個(gè)屬性[q∈Q]；

6： 在0～1之間隨機(jī)選擇一個(gè)數(shù)[r]；

7： 割點(diǎn)[p=LBsq+r?UBsq-LBsq]；

8： [t←UBsq]；[UBsq←p]；

9： left[←]BuildTreeStructure[LBs，UBs，e+1，H]；

10： [left.v←r]；[left.parent←root]；

11： [UBsq←t]；[LBsq←p]；

12： [right←]BuildTreeStructure[LBs，UBs，e+1，H]；

13： [right.v←1-r]；[right.parent←root]；

14： return

[root（leftChild←left，rightChild←right，splitAtt←q，cutPoint←p，][ml←0，mr←0）]

15：end if

（3）節(jié)點(diǎn)容積的計(jì)算。節(jié)點(diǎn)容積的計(jì)算對(duì)RS樹的密度估計(jì)具有重要作用。只要RS樹構(gòu)建完畢，每個(gè)節(jié)點(diǎn)的容積便已固定。RS樹可對(duì)空間[Ω]進(jìn)行分割。每個(gè)節(jié)點(diǎn)表示有[2d]個(gè)不等式（[eTx

引理1 設(shè)[δij]表示形成由節(jié)點(diǎn)[i]表示的超矩形時(shí)屬性[j]的長(zhǎng)度，有[δij=ljk=1hijrijk，]其中[lj]表示屬性[j]的長(zhǎng)度，[rijk∈0，1]表示屬性[j]第[k]個(gè)分支在從根節(jié)點(diǎn)到節(jié)點(diǎn)[i]路徑上隨機(jī)選擇的數(shù)值，[hij]表示屬性[j]在從根節(jié)點(diǎn)到節(jié)點(diǎn)[i]路徑上進(jìn)行分割的分支總量，且[k=10rijk=1]。

引理2 [Vi]表示由節(jié)點(diǎn)[i]表示的超矩形區(qū)域的容積，于是有[Vi=V?k=1hirik，]其中[rik∈0，1，]表示內(nèi)部節(jié)點(diǎn)在從根節(jié)點(diǎn)到節(jié)點(diǎn)[i]的路徑上隨機(jī)選擇的數(shù)值，[V=j=1dlj，][hi=j=1dhij]且[k=10rik=1]。

限于篇幅，證明過(guò)程略。上述引理表明，利用內(nèi)部節(jié)點(diǎn)在從根節(jié)點(diǎn)到節(jié)點(diǎn)[i]的路徑上隨機(jī)選擇的數(shù)值，可計(jì)算出節(jié)點(diǎn)[i]的容積。為了計(jì)算出節(jié)點(diǎn)容積，只需記錄構(gòu)建RS樹時(shí)隨機(jī)選擇的這些數(shù)值即可。算法2給出了部署詳情。

算法2 ComputeNodeVolRatio （T）

1：對(duì)隊(duì)列node_queue初始化；

2：nodeQueue.Enqueue（T）；

3：while ！ nodeQueue.empty（） do

4： curNode ← nodeQueue.Dequeue（）；

5： parentNode ← curNode.parent；

6： if parentNode is NULL then

7： curNode.v ← 0；

8： else

9： curNode.v ← parentNode.v+ log（curNode.v）；

10： end if

11： if curNode為內(nèi)部節(jié)點(diǎn) then

12： nodeQueue.Enqueue（curNode.leftChild）；

13： nodeQueue.Enqueue（curNode.rightChild）；

14： end if

15：end while

1.3 數(shù)據(jù)流異常檢測(cè)算法（RS?Forest）

本文提出的數(shù)據(jù)流異常檢測(cè)算法是利用多棵RS樹形成RS?Forest，然后RS?Forest對(duì)數(shù)據(jù)流采用單窗口策略對(duì)新到達(dá)實(shí)例進(jìn)行打分，并與一種周期性快速更新模型方法相結(jié)合。算法在具體部署時(shí)，需要將數(shù)據(jù)流分割為多個(gè)窗口。每個(gè)窗口的尺寸可以相同，也可以不同，具體視應(yīng)用要求而定。算法在運(yùn)行時(shí)只針對(duì)一個(gè)窗口，該窗口稱為最新窗口。在異常檢測(cè)方法的初始階段，系統(tǒng)在構(gòu)建樹（模型）結(jié)構(gòu)的同時(shí)，利用正常數(shù)據(jù)樣本記錄節(jié)點(diǎn)剖度。然后，系統(tǒng)對(duì)最新窗口內(nèi)的新來(lái)實(shí)例進(jìn)行打分，同時(shí)記錄從這些實(shí)例中獲得的節(jié)點(diǎn)剖度。窗口滿后，觸發(fā)模型更新過(guò)程，利用對(duì)偶節(jié)點(diǎn)剖度實(shí)現(xiàn)快速模型更新。模型更新完畢后，刪除原來(lái)的節(jié)點(diǎn)剖度，將最新窗口清空，為新來(lái)數(shù)據(jù)做好準(zhǔn)備。上述過(guò)程一直持續(xù)至數(shù)據(jù)流結(jié)束為止。

根據(jù)RS森林的密度估計(jì)對(duì)新來(lái)實(shí)例[x]進(jìn)行打分。一個(gè)實(shí)例的密度越低，該實(shí)例異常的程度越高。結(jié)合定義3和定義4，可將[x]的異常得分定義如下：

[1Mt=1M?x，TtNV?x，Tt] （3）

利用引理2，可將式（3）重寫為：

[1MVt=1MScorex，Tt] （4）

式中：[Scorex，Tt=explog?x，Tt-?x，Tt?v-logN；][V=j=1dlj]。在實(shí)踐中，由于[M]和[V]為常數(shù)，所以在對(duì)異常排序時(shí)只需利用[t=1MScorex，Tt]即可。為了避免計(jì)算時(shí)出現(xiàn)下溢現(xiàn)象，對(duì)數(shù)值采用對(duì)數(shù)標(biāo)度。

算法3 StreamingRS?Forest[X，M，H，ψ，ζ]

輸入：[M]：RS樹的數(shù)量；[H]：樹深界限；[ψ]：窗口大??；[ζ]：節(jié)點(diǎn)尺寸界限

輸出：[s]：每個(gè)新來(lái)實(shí)例[x]的異常得分；

1：[F=BuildForestX，M，H]；

2：利用[X]對(duì)[F]中每個(gè)RS樹的節(jié)點(diǎn)剖度[ml]進(jìn)行更新；

3：[B←]；

4：[LR←False]；

5： while 數(shù)據(jù)流持續(xù) do

6： 接收到新的數(shù)據(jù)點(diǎn)[x：b.X=x]，[b.nodeList=]；

7： [s←0]

8： for [F]中的每個(gè)樹[T] do //預(yù)測(cè)階段

9： [s←s+Scorex，T]；

10： [b.nodeList.Enqueue][?x，T]；

11： end for

12： [B.Enqueue（b）]；

13： 給出數(shù)據(jù)點(diǎn)[x]的異常得分[s]；

14： if [B==ψ] then //模型更新階段

15： UpdateModel[F，B，LR，ζ]；

16： [LR←！LR]；

17： [B.clear]；

18： 對(duì)[F]中每個(gè)樹[T]的非零節(jié)點(diǎn)，[LR？node.ml←0：]

[node.mr←0]；

19： end if

20： end while

算法3給出了數(shù)據(jù)流RS?Forest方法的詳情。第1行負(fù)責(zé)對(duì)RS?Forest初始化。在初始化時(shí)（算法4），obtainRange（[X]）的作用是利用樣本[X]獲得每個(gè)屬性[qi]的范圍估計(jì)值。[X]既可以是正常實(shí)例樣本，也可以是數(shù)據(jù)流的前[ψ]個(gè)正常實(shí)例。算法在對(duì)節(jié)點(diǎn)剖度初始化的同時(shí)，構(gòu)建每個(gè)RS樹的結(jié)構(gòu)。算法3的第2行利用[X]更新森林中每個(gè)樹的節(jié)點(diǎn)剖度[ml]。在本文模型中，估計(jì)（或打分）步驟與模型更新步驟交替進(jìn)行。在整個(gè)運(yùn)行期間，每個(gè)樹的結(jié)構(gòu)保持不變，數(shù)據(jù)打分后獲得的節(jié)點(diǎn)剖度可用于下一輪的模型更新。因此，這兩個(gè)步驟有部分操作重合。于是，采用一種對(duì)偶式節(jié)點(diǎn)剖度技術(shù)來(lái)保存預(yù)測(cè)階段已經(jīng)執(zhí)行過(guò)、模型更新階段同樣需要執(zhí)行的相同操作。具體來(lái)說(shuō)，交替使用節(jié)點(diǎn)剖度[ml]和[mr]來(lái)存儲(chǔ)當(dāng)前模型（用于存儲(chǔ)新來(lái)數(shù)據(jù)）的節(jié)點(diǎn)剖度，以及從最新窗口內(nèi)新來(lái)數(shù)據(jù)獲得的節(jié)點(diǎn)剖度（用于下一輪更新模型）。[ψ]個(gè)數(shù)據(jù)點(diǎn)處理過(guò)后，[ml]和[mr]的角色變化，并利用變量LR作為這一變化的標(biāo)志。

算法4 BuildForest[X，M，H]

1：[LBs，UBs=obtainRange（X）]；

2：初始化：[F=]

3：for [t=1]to[M] do

4： [T=BuildTreeStructureLBs，UBs，0，H]；

5： ComputeNodeVol[T]；

6： [F=F?T]；

7： end for

8：return [F]

如上文所示，模型更新是RS?Forest方法的關(guān)鍵步驟之一，模型更新的內(nèi)容見算法5。總體來(lái)說(shuō)，模型更新算法分為兩部分：第一部分針對(duì)異常實(shí)例（第3～9行），另一部分針對(duì)正常實(shí)例（第10～19行）。在異常實(shí)例部分，通過(guò)沿著從終止節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑使所有節(jié)點(diǎn)的剖度下降1來(lái)更新各個(gè)RS樹。在正常實(shí)例部分，如果終止節(jié)點(diǎn)不是葉節(jié)點(diǎn)且節(jié)點(diǎn)尺寸約束未被滿足，則通過(guò)沿著從終止節(jié)點(diǎn)到葉節(jié)點(diǎn)（或滿足節(jié)點(diǎn)尺寸約束的首個(gè)節(jié)點(diǎn)）的路徑使所有節(jié)點(diǎn)的剖度上升1來(lái)更新各個(gè)RS樹。此時(shí)，[NextChildchild，x]表示[x]落入的下個(gè)子節(jié)點(diǎn)。

算法5 UpdateModel[F，B，LR，ζ]

輸入：[F]：RS森林；[B]：每個(gè)實(shí)例的緩沖；LR：關(guān)于哪個(gè)剖度將被更新的指示器；[ζ]：節(jié)點(diǎn)尺寸界限

輸出：無(wú)

1： 根據(jù)標(biāo)簽信息將[B]分割為[N]和[A]；//[NA]包含最新窗口內(nèi)正常（異常）實(shí)例的相關(guān)信息；

2： for [i=1]to[M]do

3： for [A]中[nodeList]列表的每個(gè)[x] do

4： [ancestor=nodeList[i]]；

5： while （不存在ancestor） do

6： [LR？ancestor.ml--：ancestor.mr--]；

7： [ancestor←ancestor.parent]；

8： end while

9： end for

10： for [N]中[nodeList]列表的每個(gè)[x] do

11： [LR？n=nodeList[i].ml：n=nodeList[i].mr]；

12： if [n>ζ]&&[nodeList[i]]不是葉節(jié)點(diǎn) then

13： [Child=NextChild（child，x）]；

14： while [child]不為空 do

15： [LR？child.ml++：child.mr++]；

16： [child=NextChild（child，x）]；

17： end while

18： end if

19： end for

20： end for

2 理論分析

2.1 范圍估計(jì)的可靠性

數(shù)據(jù)流的各個(gè)屬性的范圍是構(gòu)建RS樹結(jié)構(gòu)的重要輸入之一。如果RS樹構(gòu)建于[d]維空間且該[d]維空間的邊界即為屬性范圍，則RS樹需要適應(yīng)整個(gè)待學(xué)習(xí)數(shù)據(jù)流的潛在特征變化。因此，引入如下定理來(lái)分析本文采用的范圍估計(jì)策略的可靠性。

定理1 當(dāng)分布未知時(shí)，有：

[pL

式中：[Z]表示隨機(jī)變量；[L]和[U]為常量，[L<μσ2，][μ]是均值；[σ2]是方差。

上述定理為變量均值滿足[μ-LU-μ>σ2]條件的范圍提供了概率保證。此時(shí)，變量可服從任何分布。在本文算法中定義屬性的范圍為[LMi-3σ，UMi+3σ]。對(duì)于正態(tài)分布，均值的90% HPD置信區(qū)間大約為[μ-1.645σ，μ+1.645σ。]在本文中，[L=μ-4.645σ， U=μ+][4.645σ。]根據(jù)[3σ]準(zhǔn)則，[pμ-4.645σ

2.2 復(fù)雜度分析

本文提出的數(shù)據(jù)流異常檢測(cè)算法的主循環(huán)涉及三大操作（如算法3所示），分別是第9行的預(yù)測(cè)或打分，第15行的模型更新，以及第18行的節(jié)點(diǎn)剖度重置。在基于當(dāng)前模型的預(yù)測(cè)步驟中，每個(gè)實(shí)例均需對(duì)各個(gè)樹中從根節(jié)點(diǎn)到終止節(jié)點(diǎn)的所有節(jié)點(diǎn)進(jìn)行遍歷。在模型更新時(shí)，針對(duì)各個(gè)異常實(shí)例或正常實(shí)例采取兩種不同步驟。因?yàn)楫惓?shí)例比較罕見，所以對(duì)于每個(gè)實(shí)例而言，用于打分和模型更新的時(shí)間應(yīng)該相等，或低于[MH。]于是，最壞情況下的運(yùn)行時(shí)間為[OnMH]，其中[n]表示數(shù)據(jù)流中數(shù)據(jù)點(diǎn)的數(shù)量。每次觸發(fā)模型更新步驟時(shí)，節(jié)點(diǎn)剖度重置最多在[M?2H+1]時(shí)間內(nèi)完成，所以其最差運(yùn)行時(shí)間為[OnψM?2H+1]。考慮到運(yùn)行期間[M，][H]和[ψ]固定，所以可以將數(shù)據(jù)流RS森林方法的最差復(fù)雜度看成[On]。

對(duì)于空間復(fù)雜度，RS?Forest本身占據(jù)空間[OM2H]。最新窗口內(nèi)的數(shù)據(jù)緩存[B]最多占用[OψM]。因?yàn)閇ψ]和[M]均是常數(shù)且數(shù)值較小，所以占用的空間可以忽略。因此，空間復(fù)雜度為[O2H]。在運(yùn)行期間，[H]固定，于是數(shù)據(jù)流RS森林方法的內(nèi)存消耗量恒定。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

利用如表1所示的6種合成基準(zhǔn)數(shù)據(jù)集 [11?12]和7種真實(shí)基準(zhǔn)數(shù)據(jù)集[4，13]作為測(cè)試對(duì)象，將本文提出的RS?Forest方法與如下基準(zhǔn)方法：HSTa[4]，LOADED[5]，Hoeffding Trees（HT）[6]及基于HT的在線協(xié)作加速算法（BoostHT）進(jìn)行性能比較。利用機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中最為常見的AUC（ROC曲線下的面積） [14]作為各種算法的評(píng)估指標(biāo)。每個(gè)算法對(duì)各個(gè)數(shù)據(jù)集單獨(dú)運(yùn)行30次，然后取平均值作為最終結(jié)果。所有實(shí)驗(yàn)的實(shí)驗(yàn)平臺(tái)均為2.6 GHz Intel Core i7 MacBook Pro，8 GB內(nèi)存。

表1 基準(zhǔn)數(shù)據(jù)集

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

表2給出了各種算法對(duì)各個(gè)基準(zhǔn)數(shù)據(jù)集的平均AUC面積。很顯然，從統(tǒng)計(jì)學(xué)角度講，RS?Forest方法對(duì)大部分?jǐn)?shù)據(jù)集表現(xiàn)出來(lái)的性能均優(yōu)于其他算法。根據(jù)置信度為95%的成對(duì)[t]檢驗(yàn)，RS?Forest與HSTa，LOADED，HT和BoostHT的成對(duì)win?loss?tie統(tǒng)計(jì)數(shù)據(jù)分別為10?0?3，10?3?0，13?0?0，11?1?1。這是因?yàn)楸疚姆椒▽?duì)數(shù)據(jù)流的異常檢測(cè)效果更優(yōu)。HSTa無(wú)疑也是一種高性能檢測(cè)算法，對(duì)所有數(shù)據(jù)的AUC平均值在各種算法中排名第二。BoostHT對(duì)大部分真實(shí)數(shù)據(jù)集也展現(xiàn)出優(yōu)異性能，但它對(duì)Syn_cond和Syn_dual等合成數(shù)據(jù)集的AUC得分要低于HT算法。BoostHT算法的性能出現(xiàn)下降，表明有條件類別分布發(fā)生變化時(shí)BoostHT很容易發(fā)生過(guò)擬合。LOADED和HT是兩種單模型算法，在AUC面積方面的排名墊底。與BoostHT不同，LOADED對(duì)服從高斯分布的多個(gè)合成數(shù)據(jù)集展現(xiàn)出優(yōu)異性能。這是因?yàn)長(zhǎng)OADED的模型假設(shè)非常嚴(yán)格。

圖1給出了不同算法在3種數(shù)據(jù)集的數(shù)據(jù)流發(fā)生變化時(shí)的AUC性能比較。總體來(lái)說(shuō)，隨著時(shí)間的推進(jìn)以及各個(gè)數(shù)據(jù)流的演變，RS?Forest方法對(duì)Mulcross和HyperP1數(shù)據(jù)集的AUC面積總是優(yōu)于HSTa和BoostHT。不同算法在Covertype數(shù)據(jù)集上的性能波動(dòng)較大。具體來(lái)說(shuō)，當(dāng)異常實(shí)例發(fā)生于Covertype演變過(guò)程的中間階段時(shí)（用虛線表示），RS?Forest和HSTa的性能趨于下降，而BoostHT的性能迅速上升。HSTa的下降趨勢(shì)大于RS?Forest方法。

（HT）必須計(jì)算Hoeffding才能確定分割樹的最佳屬性，因此消耗的時(shí)間最多。HSTa的運(yùn)行速度快于BoostHT，但其平均運(yùn)行時(shí)間仍然是RS?Forest方法的5倍左右。RS?Forest方法中的數(shù)據(jù)結(jié)構(gòu)與HSTa類似。然而，與HSTa不同的是，RS?Forest方法從預(yù)測(cè)過(guò)程和模型更新過(guò)程的共同操作入手，進(jìn)一步降低了模型更新時(shí)間。因此，RS?Forest方法的運(yùn)行時(shí)間在各種算法中是最低的，甚至還要低于單模型方法。

4 結(jié) 語(yǔ)

本文提出一種新的數(shù)據(jù)流異常檢測(cè)算法RS?Forest。該算法滿足了持續(xù)演變數(shù)據(jù)流對(duì)異常檢測(cè)算法的關(guān)鍵要求：

（1） 該算法為一次通過(guò)型檢測(cè)算法，具有恒定的空間復(fù)雜度和線性時(shí)間復(fù)雜度；

（2） 該算法作為一種極具多樣性的系統(tǒng)算法，作用于統(tǒng)計(jì)估計(jì)特征空間，可提供較高的概率保證，對(duì)漂移概念具有顯著效果；

（3） 采用一種對(duì)偶節(jié)點(diǎn)剖度技術(shù)，響應(yīng)時(shí)間極快；

（4） 訓(xùn)練時(shí)只需要正常實(shí)例即可，可實(shí)現(xiàn)高效有序的異常檢測(cè)和模型更新。

另外，還進(jìn)行了嚴(yán)格的理論分析，為本文算法提供了堅(jiān)實(shí)的理論基礎(chǔ)。基于多個(gè)基準(zhǔn)數(shù)據(jù)集的實(shí)驗(yàn)仿真評(píng)估結(jié)果表明，與當(dāng)前其他最新算法相比，RS?Forest方法的AUC得分較高，運(yùn)行時(shí)間較短。下一步的主要工作包括：對(duì)RS?Forest方法適當(dāng)改進(jìn)后，適用于部分?jǐn)?shù)據(jù)丟失的混合特征空間；在保持檢測(cè)率的同時(shí)降低算法的空間消耗。

參考文獻(xiàn)

[1] 彭勇，向憧，張淼，等.工業(yè)控制系統(tǒng)場(chǎng)景指紋及異常檢測(cè)[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，56（1）：14?21.

[2] 嚴(yán)英杰，盛戈皞，陳玉峰，等.基于大數(shù)據(jù)分析的輸變電設(shè)備狀態(tài)數(shù)據(jù)異常檢測(cè)方法[J].中國(guó)電機(jī)工程學(xué)報(bào)，2015，35（1）：52?59.

[3] 蔡瑞初，謝偉浩，郝志峰，等.基于多尺度時(shí)間遞歸神經(jīng)網(wǎng)絡(luò)的人群異常檢測(cè)[J].軟件學(xué)報(bào)，2015，26（11）：2884?2896.

[4] TAN S C， TING K M， LIU T F. Fast anomaly detection for streaming data [C]// Proceedings of 2011 International Joint Conference on Artificial Intelligence. Barcelona， Spain： IEEE， 2011： 1511?1516.

[5] GHOTING A， OTEY M E， PARTHASARATHY S. LOADED： link?basedoutlier and anomaly detection in evolving data sets [C]// Proceedings of the 4th IEEE International Conference on Data Mining. Orlando， USA： IEEE， 2014： 387?390.

[6] DOMINGOS P， HULTEN G. Mining high?speed data streams [C]// Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington， DC， USA： ACM， 2010： 71?80.

[7] BIFET A， HOLMES G， PFAHRINGER B， et al. New ensemble methods for evolving data streams [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris， France： ACM， 2009： 139?148.

[8] NIKOLOVA E， JECHEVA V. Some similarity coefficients and application of data mining techniques to the anomaly?based IDS [J]. Telecommunication systems， 2012， 50（2）： 127?135.

[9] DHAKAR M， TIWARI A. A novel data mining based hybrid intrusion detection framework [J]. Journal of information and computing science， 2014， 9（1）： 37?48.

[10] ZHANG K， FAN W. Forecasting skewed biased stochastic ozone days： analyses， solutions and beyond [J]. Knowledge and information systems， 2008， 14（3）： 299?326.

[11] FILZMOSER P. Identification of multivariate outliers： a performance study [J]. Austrian journal of statistics， 2016， 34（2）： 127?138.

[12] WU K， EDWARDS A， FAN W， et al. Classifying imba?lanced data streams via dynamic feature group weighting with importance sampling [C]// Proceedings of 2014 SIAM International Conference on Data Mining （SDM）. Philadelphia， USA： SIAM， 2014： 722?730.

[13] DITZLER G， POLIKAR R. Incremental learning of concept drift from streaming imbalanced data [J]. IEEE transactions on knowledge and data engineering， 2013， 25（10）： 2283?2301.

[14] HUANG J， LING C X. Using AUC and accuracy in evalua?ting learning algorithms [J]. IEEE transactions on knowledge and data engineering， 2005， 17（3）： 299?310.