基于角度的多數(shù)據(jù)流異常檢測方法*

黃東東 徐 建 張 宏

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

1 引言

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

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

數(shù)據(jù)流的異常檢測的難點是如何度量多數(shù)據(jù)流間的相似性，與整體相似性較高的數(shù)據(jù)流被視為正常數(shù)據(jù)流，與整體相似性較低的則被視為異常數(shù)據(jù)流?；诓煌睦碚摵蛻?yīng)用，提出了不同數(shù)據(jù)流異常檢測方法，主要有基于密度的異常檢測［7，10，15］，基于網(wǎng)格的異常檢測［11］和基于距離的異常檢測［12～16］。

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

本文的貢獻在于：

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

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

3）采用無指導(dǎo)的學(xué)習(xí)方法自動獲取動態(tài)變化的異常檢測閾值，能夠更好地適應(yīng)異常頻繁改變的場景，同時減少了人為干預(yù)。

2 相關(guān)技術(shù)

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

圖1 數(shù)據(jù)分布圖

3 多數(shù)據(jù)流異常檢測方法

3.1 框架

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

1）基于角度的方法計算出同構(gòu)計算系統(tǒng)中每一個計算節(jié)點當(dāng)前時刻的異常值。

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

3）建立數(shù)據(jù)流整體異常值的動態(tài)閾值機制，即根據(jù)當(dāng)前時刻數(shù)據(jù)流的整體異常值動態(tài)的決定異常數(shù)據(jù)流的異常閾值。

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

3.2 數(shù)據(jù)流當(dāng)前異常量化階段

根據(jù)基于角度的數(shù)據(jù)相似性度量理論，本節(jié)提出了數(shù)據(jù)流當(dāng)前異常值的概念，定義如下。

對于一個包含n個節(jié)點的同構(gòu)計算系統(tǒng)，該系統(tǒng)中每個計算節(jié)點都在源源不斷地產(chǎn)生數(shù)據(jù)，每個計算節(jié)點對應(yīng)著一條數(shù)據(jù)流，整個計算系統(tǒng)中包含了n條數(shù)據(jù)流。

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

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

根據(jù)定義1計算出該同構(gòu)計算系統(tǒng)所產(chǎn)生數(shù)據(jù)流在第j次快照時的當(dāng)前異常值矩陣，其中valji表示第i個節(jié)點在第j次快照時的當(dāng)前異常值。的具體計算過程如下：

即

3.3 數(shù)據(jù)流整體異常量化階段

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

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

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

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

其中λ為衰減系數(shù)。

由此可以構(gòu)造出j次快照時整個同構(gòu)系統(tǒng)中數(shù)據(jù)流的整體異常值矩陣。

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

3.4 告警階段

根據(jù)以上方法，可以計算出每一個計算節(jié)點的整體異常值，異常值越高的節(jié)點越有可能是異常節(jié)點。本文提出了一種無指導(dǎo)的學(xué)習(xí)方法來自動獲取動態(tài)變化的異常檢測閾值，能夠更好地適應(yīng)異常頻繁改變的場景，并且減少人為干預(yù)，避免對于異常閾值的設(shè)定。

3.5 算法

本節(jié)說明算法的實現(xiàn)流程。具體算法如下。

輸入：為預(yù)處理后得到數(shù)據(jù)集合Fj，j為快照次數(shù)輸出：異常節(jié)點

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

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

4）取數(shù)據(jù)集合Fj其他點重復(fù)2）、3）步驟；

5）根據(jù)式（4）計算出j次快照時整個同構(gòu)計算系統(tǒng)中數(shù)據(jù)流的整體異常值矩陣。

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

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

4 實驗

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

4.1 實驗數(shù)據(jù)集

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

圖3 示例數(shù)據(jù)流

4.2 實驗結(jié)果分析

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

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

圖4 高維情況下異常數(shù)據(jù)流檢測效果

從圖4的實驗結(jié)果中可以看出：

1）基于角度的方法表現(xiàn)優(yōu)于基于距離的方法。由此可以得出結(jié)論：在數(shù)據(jù)為高維的情況下，相比于基于距離的方法，基于角度的高維多數(shù)據(jù)流異常檢測方法準確性更高；

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

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

5 結(jié)語

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

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