一種基于隨機空間樹的數據流異常檢測算法

覃偉榮+王寧

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

關鍵詞： 數據流； 異常檢測； 隨機空間樹； 單窗口策略； AUC得分； 運行時間

中圖分類號： TN915.08?34； TP393 文獻標識碼： A 文章編號： 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 引 言

異常或離群點是指與正常點或預期點不吻合或偏離正常點的罕見事件或罕見點。對于軍事偵查、網絡安全管理、工業系統監控等眾多領域，如果不能立即檢測出這些異常事件，便有可能造成嚴重后果。隨著近些年硬件技術的迅速發展，上述領域的持續性數據采集能力獲得顯著提升，采集到的大部分數據不再是有限的或靜態數據，而是無限制的大容量高速實時數據，稱其為數據流。

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

1 本文算法

1.1 基本定義

定義1：隨機空間樹，它是一種完全二叉樹，可通過隨機選擇一種屬性及被選屬性的割點來構建。

深度為[HH≥0]的RS?Tree共有[2H+1-1]個節點，其中葉節點的深度均為[H]。RS?Tree起源于隨機決策樹[10]，不用數據便可構建出樹結構。在構建RS?Tree時，算法不斷從特征集中選擇一種屬性，然后隨機確定這種屬性的分割點來實現樹的分割，直至到達樹深[H]。

定義2：RS?Tree中的節點剖度，已知數據樣本后，該節點表示相應區域中落入的實例數量。

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

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

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

定義4：基于RS森林[F]的密度估計，其表達式為：

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

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

1.2 RS樹的構建

（1） 樹節點的初始化。深度為[H]的RS樹包含[2H+1-1]個節點。在部署時，每個節點包含如下元素：

① 變量[ml]和[mr]，用于交替記錄預測模型或窗口內數據流的節點剖度；

② 3個節點指針，分別指向當前節點的左子節點，右子節點及母節點；

③ 變量[v，]用于存儲當前節點容積與整個特征空間容積之比的對數。

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

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

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

[e：]當前樹的深度，[H：]樹深界限；

輸出：一棵RS樹

1：if [e≥H] then

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

3：else

4： 對非葉節點[root]初始化；

5： 隨機選擇一個屬性[q∈Q]；

6： 在0～1之間隨機選擇一個數[r]；

7： 割點[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）節點容積的計算。節點容積的計算對RS樹的密度估計具有重要作用。只要RS樹構建完畢，每個節點的容積便已固定。RS樹可對空間[Ω]進行分割。每個節點表示有[2d]個不等式（[eTx

引理1 設[δij]表示形成由節點[i]表示的超矩形時屬性[j]的長度，有[δij=ljk=1hijrijk，]其中[lj]表示屬性[j]的長度，[rijk∈0，1]表示屬性[j]第[k]個分支在從根節點到節點[i]路徑上隨機選擇的數值，[hij]表示屬性[j]在從根節點到節點[i]路徑上進行分割的分支總量，且[k=10rijk=1]。

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

限于篇幅，證明過程略。上述引理表明，利用內部節點在從根節點到節點[i]的路徑上隨機選擇的數值，可計算出節點[i]的容積。為了計算出節點容積，只需記錄構建RS樹時隨機選擇的這些數值即可。算法2給出了部署詳情。

算法2 ComputeNodeVolRatio （T）

1：對隊列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為內部節點 then

12： nodeQueue.Enqueue（curNode.leftChild）；

13： nodeQueue.Enqueue（curNode.rightChild）；

14： end if

15：end while

1.3 數據流異常檢測算法（RS?Forest）

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

根據RS森林的密度估計對新來實例[x]進行打分。一個實例的密度越低，該實例異常的程度越高。結合定義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]。在實踐中，由于[M]和[V]為常數，所以在對異常排序時只需利用[t=1MScorex，Tt]即可。為了避免計算時出現下溢現象，對數值采用對數標度。

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

輸入：[M]：RS樹的數量；[H]：樹深界限；[ψ]：窗口大小；[ζ]：節點尺寸界限

輸出：[s]：每個新來實例[x]的異常得分；

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

2：利用[X]對[F]中每個RS樹的節點剖度[ml]進行更新；

3：[B←]；

4：[LR←False]；

5： while 數據流持續 do

6： 接收到新的數據點[x：b.X=x]，[b.nodeList=]；

7： [s←0]

8： for [F]中的每個樹[T] do //預測階段

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

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

11： end for

12： [B.Enqueue（b）]；

13： 給出數據點[x]的異常得分[s]；

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

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

16： [LR←！LR]；

17： [B.clear]；

18： 對[F]中每個樹[T]的非零節點，[LR？node.ml←0：]

[node.mr←0]；

19： end if

20： end while

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

算法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方法的關鍵步驟之一，模型更新的內容見算法5。總體來說，模型更新算法分為兩部分：第一部分針對異常實例（第3～9行），另一部分針對正常實例（第10～19行）。在異常實例部分，通過沿著從終止節點到根節點的路徑使所有節點的剖度下降1來更新各個RS樹。在正常實例部分，如果終止節點不是葉節點且節點尺寸約束未被滿足，則通過沿著從終止節點到葉節點（或滿足節點尺寸約束的首個節點）的路徑使所有節點的剖度上升1來更新各個RS樹。此時，[NextChildchild，x]表示[x]落入的下個子節點。

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

輸入：[F]：RS森林；[B]：每個實例的緩沖；LR：關于哪個剖度將被更新的指示器；[ζ]：節點尺寸界限

輸出：無

1： 根據標簽信息將[B]分割為[N]和[A]；//[NA]包含最新窗口內正常（異常）實例的相關信息；

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

3： for [A]中[nodeList]列表的每個[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]列表的每個[x] do

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

12： if [n>ζ]&&[nodeList[i]]不是葉節點 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 范圍估計的可靠性

數據流的各個屬性的范圍是構建RS樹結構的重要輸入之一。如果RS樹構建于[d]維空間且該[d]維空間的邊界即為屬性范圍，則RS樹需要適應整個待學習數據流的潛在特征變化。因此，引入如下定理來分析本文采用的范圍估計策略的可靠性。

定理1 當分布未知時，有：

[pL

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

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

2.2 復雜度分析

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

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

3 仿真實驗

3.1 實驗設置

利用如表1所示的6種合成基準數據集 [11?12]和7種真實基準數據集[4，13]作為測試對象，將本文提出的RS?Forest方法與如下基準方法：HSTa[4]，LOADED[5]，Hoeffding Trees（HT）[6]及基于HT的在線協作加速算法（BoostHT）進行性能比較。利用機器學習和數據挖掘中最為常見的AUC（ROC曲線下的面積） [14]作為各種算法的評估指標。每個算法對各個數據集單獨運行30次，然后取平均值作為最終結果。所有實驗的實驗平臺均為2.6 GHz Intel Core i7 MacBook Pro，8 GB內存。

表1 基準數據集

3.2 實驗結果

表2給出了各種算法對各個基準數據集的平均AUC面積。很顯然，從統計學角度講，RS?Forest方法對大部分數據集表現出來的性能均優于其他算法。根據置信度為95%的成對[t]檢驗，RS?Forest與HSTa，LOADED，HT和BoostHT的成對win?loss?tie統計數據分別為10?0?3，10?3?0，13?0?0，11?1?1。這是因為本文方法對數據流的異常檢測效果更優。HSTa無疑也是一種高性能檢測算法，對所有數據的AUC平均值在各種算法中排名第二。BoostHT對大部分真實數據集也展現出優異性能，但它對Syn_cond和Syn_dual等合成數據集的AUC得分要低于HT算法。BoostHT算法的性能出現下降，表明有條件類別分布發生變化時BoostHT很容易發生過擬合。LOADED和HT是兩種單模型算法，在AUC面積方面的排名墊底。與BoostHT不同，LOADED對服從高斯分布的多個合成數據集展現出優異性能。這是因為LOADED的模型假設非常嚴格。

圖1給出了不同算法在3種數據集的數據流發生變化時的AUC性能比較。總體來說，隨著時間的推進以及各個數據流的演變，RS?Forest方法對Mulcross和HyperP1數據集的AUC面積總是優于HSTa和BoostHT。不同算法在Covertype數據集上的性能波動較大。具體來說，當異常實例發生于Covertype演變過程的中間階段時（用虛線表示），RS?Forest和HSTa的性能趨于下降，而BoostHT的性能迅速上升。HSTa的下降趨勢大于RS?Forest方法。

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

4 結 語

本文提出一種新的數據流異常檢測算法RS?Forest。該算法滿足了持續演變數據流對異常檢測算法的關鍵要求：

（1） 該算法為一次通過型檢測算法，具有恒定的空間復雜度和線性時間復雜度；

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

（3） 采用一種對偶節點剖度技術，響應時間極快；

（4） 訓練時只需要正常實例即可，可實現高效有序的異常檢測和模型更新。

另外，還進行了嚴格的理論分析，為本文算法提供了堅實的理論基礎。基于多個基準數據集的實驗仿真評估結果表明，與當前其他最新算法相比，RS?Forest方法的AUC得分較高，運行時間較短。下一步的主要工作包括：對RS?Forest方法適當改進后，適用于部分數據丟失的混合特征空間；在保持檢測率的同時降低算法的空間消耗。

參考文獻

[1] 彭勇，向憧，張淼，等.工業控制系統場景指紋及異常檢測[J].清華大學學報（自然科學版），2016，56（1）：14?21.

[2] 嚴英杰，盛戈皞，陳玉峰，等.基于大數據分析的輸變電設備狀態數據異常檢測方法[J].中國電機工程學報，2015，35（1）：52?59.

[3] 蔡瑞初，謝偉浩，郝志峰，等.基于多尺度時間遞歸神經網絡的人群異常檢測[J].軟件學報，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.