黃東東 徐 建 張 宏

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

1 引言

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

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

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

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

本文的貢獻(xiàn)在于：

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

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

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

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

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

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

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

3.1 框架

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

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

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

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

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

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

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

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

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

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

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

即

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

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

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

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

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

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

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

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

3.4 告警階段

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

3.5 算法

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

從圖4的實(shí)驗(yàn)結(jié)果中可以看出：

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

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

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

5 結(jié)語

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

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