基于角度的多數據流異常檢測方法*

黃東東 徐 建 張 宏

（南京理工大學計算機科學與工程學院 南京 210049）

1 引言

隨著云計算技術以及大數據技術的發展，單個計算節點的計算能力難于快速、有效地處理大數據，所以大規模數據的計算任務越來越依靠同構計算系統，比如Map Reduce［1～3］、Bulk Synchronous Parallel（BSP）［4］等來完成。同構［4～5］計算系統運行過程中，計算節點會受到網絡攻擊，軟件衰退［5～6］等因素影響而產生異常。因此，通過計算節點的監測數據發現異常節點對于快速的系統恢復和管理有重要作用［7］。

每個計算節點持續采集的數據可以視為一個由多個維度，如CPU、內存、I/O信息、網絡等構成的高維數據流，而整個計算系統的多個節點產生的數據流則可視為多條高維數據流。針對多數據流中的異常檢測一直是異常檢測領域中的研究熱點。面臨的挑戰主要包括：1）動態性［8］，與傳統靜態數據不同，數據流異常檢測的研究對象是不斷輸入數據的數據流，具有動態的；2）無限性［9］，數據流會源源不斷地輸入數據，存儲資源的限制使得考慮所有歷史數據的可能性是不存在的；3）遷移性［8］，數據流的異常檢測更加注重數據流的當前數據，歷史數據包含的信息價值會隨著時間的推移而逐漸減弱。

數據流的異常檢測的難點是如何度量多數據流間的相似性，與整體相似性較高的數據流被視為正常數據流，與整體相似性較低的則被視為異常數據流。基于不同的理論和應用，提出了不同數據流異常檢測方法，主要有基于密度的異常檢測［7，10，15］，基于網格的異常檢測［11］和基于距離的異常檢測［12～16］。

上述方法在實際應用過程中存在以下問題：1）閾值難以設定［18］。上述異常檢測方法要么采用top-k方式把異常量化值最高的k個數據流作為異常，要么把異常量化值超過預定義閾值的數據流作為異常。閾值的合理設定需要對應用程序的底層機制非常熟悉，這對于一般應用者而言，難度太大；2）異常的數目一直在變化［17］。某個時刻可能存在超過k個異常數據流，采用top-k方式會遺漏這些真實存在的異常；3）在數據流為高維的情況下，以上的異常檢測方法不夠穩定。針對以上問題，本文以角度作為相似性度量指標，提出了一種基于上下文的高維多數據流異常檢測方法，并在其中采用了無指導的學習方法自動獲取閾值，盡量減少了參數的設定。

本文的貢獻在于：

1）使用了在高維下表現更加穩定的角度作為高維數據流相似性度量，從而避免了基于歐式距離等其他度量方式的缺陷。

2）充分考慮高維多數據流的特點，結合歷史信息以及當前多數據流之間的相似性，計算并比較數據流之間的整體相似性，并且考慮到數據流歷史信息的遷移性對數據流歷史信息進行衰減，提高異常數據流檢測的準確率。

3）采用無指導的學習方法自動獲取動態變化的異常檢測閾值，能夠更好地適應異常頻繁改變的場景，同時減少了人為干預。

2 相關技術

Kriegel等［22］提出一種基于角度的異常點檢測算法ABOD（Angle-based Outlier Detection）。該算法的基本思想是以角度分布度量高維數據間的相似性：如果數據集中某點與數據集中其他點構成的向量與基準向量夾角角度方差值越小，該點就越有可能是異常點，反之則很有可能為正常點。如圖1所示，以分布在空間中的2維數據集為例，圖中的坐標軸數值僅僅表示數據點的位置信息，沒有實際含義。觀察圖1（a）中離群點O到數據集中其它數據點構成的向量，這些向量與基準向量所構成的角的大小較為接近，即這些角度的方差較??；而圖1（b）中點O處于數據集內部，比較其與數據集中其他點構成的向量與基準向量夾角，角度差異較大，即這些角度的方差較大。基準向量可以隨機選取，但必須統一。實驗結果表明由于在高維空間中，角度比距離更加穩定［23］，并且不會出現實質性惡化，所以運用基于角度分布的方法來度量高維數據的相似性相對于基于距離的方法表現更加穩定。

圖1 數據分布圖

3 多數據流異常檢測方法

3.1 框架

本文提出了一種基于上下文以角度作為相似性度量指標的高維多數據流異常檢測方法，其框架如圖2所示，所采用的基本思想如下。

1）基于角度的方法計算出同構計算系統中每一個計算節點當前時刻的異常值。

2）考慮計算節點的歷史異常值，度量該計算節點對應的數據流整體異常值。由于數據流具有遷移性，所以隨著時間的推移，越是久遠的數據所攜帶的信息越少，計算時對于數據流歷史異常值進行衰減處理。

3）建立數據流整體異常值的動態閾值機制，即根據當前時刻數據流的整體異常值動態的決定異常數據流的異常閾值。

圖2 基于角度的高維多數據流異常檢測算法框架

3.2 數據流當前異常量化階段

根據基于角度的數據相似性度量理論，本節提出了數據流當前異常值的概念，定義如下。

對于一個包含n個節點的同構計算系統，該系統中每個計算節點都在源源不斷地產生數據，每個計算節點對應著一條數據流，整個計算系統中包含了n條數據流。

采集每一個計算節點的m個維度的數據，并對每一個計算節點的m個維度的數據每隔一段時間便進行一次快照。

每個計算節點的m個維度的數據形成一個m維矩陣，整個系統能夠形成n個m維矩陣；第j次快照所形成的數據矩陣為，矩陣Fj中的數據fji為第i個節點第j次快照所得到的m維數據矩陣。

根據定義1計算出該同構計算系統所產生數據流在第j次快照時的當前異常值矩陣，其中valji表示第i個節點在第j次快照時的當前異常值。的具體計算過程如下：

即

3.3 數據流整體異常量化階段

由于數據流數據的動態性，無限性，而數據流的當前異常值僅僅顯示了數據流當前時刻的異常情況，所以只根據數據流當前某個時間點的異常值來判斷數據流是否異常容易產生誤報和漏報。因此在對數據流進行異常度量時，考慮歷史信息顯得很有必要。

傳統的解決方法是設定滑動窗口［25～26］，以滑動窗口內的信息來代表整個數據流的異常情況。但是這樣的方法存在如下缺陷：1）窗口長度難以確定。窗口過短不能真正表示出整體數據流的異常情況而窗口太長又很可能將真正的異常信息掩蓋；2）窗口內信息具有遷移性。窗口內不同時間出現的信息的價值不同；3）窗口外的信息被忽略?；诨瑒哟翱诘漠惓６攘恐荒芸紤]到滑動窗口內部的信息，而對于更早產生的信息則會忽略，這是不符合實際的。

所以本文提出了結合數據流歷史異常值，從整體考慮數據流的異常情況，定義了數據流整體異常值的概念。其具體定義如下：

數據流i的第j次快照時總體異常值vali'j具體計算過程如下：

其中λ為衰減系數。

由此可以構造出j次快照時整個同構系統中數據流的整體異常值矩陣。

根據以上理論數據流整體異常值VAL'j考慮了全部的歷史信息，并對歷史信息進行了衰減，越久的信息對數據流整體異常值的影響越小。因為考慮了歷史信息，所以該計算模型能夠抵抗數據流的瞬時波動，大大降低了誤報的可能。另外根據式（4），該方法只需要儲存每個時間點的數據流整體異常值，數據流整體異常值的更新的空間和時間復雜度都為O（1），那么更新數據流整體異常值矩陣的時間復雜度則為O（n），所以以上算法可以高效地計算出數據流的整體異常值。

3.4 告警階段

根據以上方法，可以計算出每一個計算節點的整體異常值，異常值越高的節點越有可能是異常節點。本文提出了一種無指導的學習方法來自動獲取動態變化的異常檢測閾值，能夠更好地適應異常頻繁改變的場景，并且減少人為干預，避免對于異常閾值的設定。

3.5 算法

本節說明算法的實現流程。具體算法如下。

輸入：為預處理后得到數據集合Fj，j為快照次數輸出：異常節點

2）取數據集合Fj中任意點，計算該點與數據集中其他所有點形成的向量同基準向量夾角的余弦值；

3）根據式（3）計算2）中所有余弦值的方差，取倒數，存入數據流當前異常值矩陣中；

4）取數據集合Fj其他點重復2）、3）步驟；

5）根據式（4）計算出j次快照時整個同構計算系統中數據流的整體異常值矩陣。

6）對數據流整體異常度進行排序，根據公式（5）判定異常點。

在算法計算數據流當前異常值的階段，假設數據集合中共有n個數據流，選定數據集中某一條數據流，計算該點與數據集中其他點連成的向量同標準向量之間夾角的余弦值，并通過方差求出該點當前異常值的時間復雜度為O(n-1)，遍歷數據集合中的所有數據點計算所有點的當前異常值的時間復雜度為O(n(n-1))；而在計算數據流的整體異常值矩陣階段，根據3.2節式（4），我們只需要儲存每個時間點的數據流整體異常值，數據流整體異常值的更新的空間和時間復雜度都為O（1），那么更新數據流整體異常值矩陣的時間復雜度則為O(n)；在異常數據流的判定階段，主要是對于數據流整體異常值的排序，采用快速排序算法平均時間復雜度為O(n log n)。綜合以上基于角度的高維多數據流異常檢測算法的時間復雜度為O(n2)。而以往的基于角度的異常數據檢測方法如ABOD（Angle-based Outlier Detection）算法采用的計算某點與數據集中任意兩點連成向量所構成的角，所以其時間復雜度為O(n3)。相比于以往的算法，本文的算法效率更高。本文在后續的實驗結果也表明該算法的效率較高。

4 實驗

本節針對基于角度的高維多數據流異常檢測方法進行測試分析，通過不同類型的數據集進行實驗對比。本文所有的實驗都運行在3.1GHz Intel處理器、內存2GB的Windows平臺上，算法均由Java實現。

4.1 實驗數據集

本節仿照真實同構計算系統的實際情況生成了人造數據集，以測試算法的性能。人造數據集中包含1000個數據流，每個數據流包含50個維度，每個維度的數據均為隨機生成，相同維度的數據生成策略相同，分別在空間上符合高斯分布、正弦變化、泊松分布等。圖3是一條示例數據流的前6屬性數據，6個維度的數據分別符合不同分布，并且在500s時該數據流的第1和第4維度的數據開始出現異常。本文在該數據集上對異常數據流檢測準確性進行測試。

圖3 示例數據流

4.2 實驗結果分析

評價多數據流異常檢測方法的重要指標就是告警的準確性。實驗中關于準確率的定義如下。

實驗中將本文提出的基于角度的高維多數據流異常檢測方法同基于距離的k-means異常檢測方法進行對比試驗，采用的數據集如圖5所示，圖7展示了兩種方法在時間段1～100的對比效果，其中橫軸代表時間，縱軸代表準確率，虛線和實線分別代表基于角度和基于距離兩種異常檢測方法。

圖4 高維情況下異常數據流檢測效果

從圖4的實驗結果中可以看出：

1）基于角度的方法表現優于基于距離的方法。由此可以得出結論：在數據為高維的情況下，相比于基于距離的方法，基于角度的高維多數據流異常檢測方法準確性更高；

2）基于距離的異常檢測方法的準確率出現不穩定波動（如時間點6，8，17，61，96等），而基于角度的異常檢測方法則表現相對較為穩定。由此可以得出結論：在高維多數據流的情況下，基于角度的異常檢測方法表現的更加穩定；

3）在數據流剛抵達（時間點1）或者（時間點50）異常剛出現的時候，兩者的準確率都出現了較大程度的下降。這是數據流整體異常值計算機制導致的，充分考慮了歷史信息，可以抵抗數據流的瞬時波動，當數據流出現持續異常（時間點50～100），準確率逐漸升高并趨于穩定。

5 結語

在同構計算環境中，每一個計算節點承擔的計算任務較為類似，所以每一計算節點的運行狀態也較為類似。每一計算節點在運行過程中源源不斷產生的信息可以看成一條包含多個維度數據（例如，CPU、內存、I/O信息等）的信息數據流，而整個計算系統產生的信息數據則可以看成多條高維數據流。為此，本文以角度作為相似性度量指標結合上下文以及同一時間點下的同構數據流，提出了一種基于上下文以角度作為差異衡量指標的高維多數據流異常檢測方法，并在其中采用了無指導的學習方法來自動獲取閾值，盡量減少了參數的設定。實驗表明該方法有效地解決了高維多數據流的異常檢測問題，并且具備高準確性，抗干擾性等特點。

在后續的研究工作中，將圍繞以下幾個方面進行研究。比如，對于異常數據流檢測精度的合理性選擇進行更加詳細的討論，提出更加有效合理的精度選擇方法；對于數據流中不同維度數據不同權重的討論，加入對于數據流維度數據權值的討論；提出增強該算法對于不同類型數據的適用性的詳細方法等等。此外，還可以利用更加有效的采樣技術、降維等技術提高算法的效率，進一步降低算法的時間和空間復雜度，從而更好地應用于實際問題中。