面向異常檢測的時間序列樹突狀細胞算法

田玉玲

(太原理工大學 計算機科學與技術學院，山西 太原 030024)

樹突狀細胞算法(Dendritic Cell Algorithm，DCA)是針對免疫學中的樹突狀細胞抽象出的一個與之相對應的數據結構，使用一組異構agent來支持一個二元選擇，能夠將抗原序列和一系列信號進行組合，實現異常檢測．它的根本原理是對抗原數據流和抽象信號形式的多維時間序列進行相關檢測，以獲得與給定的上下文環境相關度最大的輸出結果[1]．樹突狀細胞算法對未知入侵具有快速、準確的識別能力，適用于對分布式系統進行實時異常檢測．樹突狀細胞算法已經應用于故障診斷、圖像分類[2]和異常檢測[3]等多種領域中．例如，Amaral[4]提出基于樹突狀細胞算法的故障檢測系統，用于線性非時變電路中的故障檢測；Hart等[5]建立了用于自組織無線傳感器網絡的樹突狀細胞模型；文獻[6]在樹突狀細胞算法的數據預處理階段，采用主成分分析(PCA)方法進行降維，自動提取重要特征向量分類到各種指定的信號類型中；文獻[7]提出用粗糙集理論中核與約簡的概念對樹突狀細胞算法進行信號特征提取及分類．以上算法的缺點是信號的提取不能根據數據流的變化及時更新，因此不適合用于實時檢測系統．

在實際應用中，樹突狀細胞算法包含較多相互作用的參數，其中各種輸入“信號”和“抗原”的概念太抽象和隨意，缺乏一個量化的定義．并且隨機抽取若干細胞對當前抗原進行采樣，隨著輸入抗原的增加而成熟分化，這種設計策略對抗原的評價計算具有滯后性，導致抗原環境發生轉變時誤檢率較高、檢測率降低．

針對異常檢測問題，筆者提出了基于時間序列的樹突狀細胞算法．抗原的定義是全部檢測信息構成的矩陣序列，基于多維數據流相關性分析，采用滑動時間窗的變化點檢測方法對數據進行檢測;利用子空間追蹤算法實現抗原數據的采樣過程，并通過在算法中加入動態遷移閾值的概念改進算法的識別效率．算法強調對檢測數據流的關鍵變化點的檢測分析以及對輸入信號的降維處理，使算法能夠利用最小的計算空間獲得更高的穩定性和檢測率．

1 基于時間序列的樹突狀細胞算法

基于免疫學的樹突狀細胞算法能夠將抗原序列以及一系列信號進行融合，實現異常檢測．筆者提出的改進樹突狀細胞算法，采用變化點檢測子空間追蹤方法自動對抗原及原始信號進行規格化處理，避免了由任意映射或專家領域知識給定的外部信號干預．算法旨在忽略某些正常數據，而強調某些關鍵變化點的檢測，不僅能根據輸入數據流的變化及時更新信號子空間，而且能大規模減少檢測數據量，提高了系統的實用性和準確性，為異常檢測系統提供了一種新的理論框架．

圖1 基于時間序列的樹突狀細胞算法框架

首先需要對檢測數據進行預處理，遴選出能夠反映異常狀態的關鍵點數據進行數據流檢測分析，并提取特征子集分配到算法的各類輸入信號，包括危險信號(DS)、安全信號(SS)和抗原的病原體相關分子模式(Pathogen Associated Molecular Pattern，PAMP)．將所有檢測點采集的數據構成矩陣序列作為抗原，并將其標記為變化點的時間序列；截取變化點前后的一個時間段的實時數據，將其定義為當前檢測抗原．樹突狀細胞算法融合處理后的抗原以及各類信號，通過權值計算得到輸出信號，根據評估得到抗原所處環境的危險程度，進而采取相應的措施．按照這個過程，顯然抗原和輸入信號的預處理階段起著至關重要的作用，它直接影響到算法的檢測結果．面向異常檢測的時間序列樹突狀細胞算法的總體框架如圖1所示．

基于時間序列的樹突狀細胞算法主要步驟概括如下:

(1) 基向量壓縮．將n個輸入數據流采用子空間追蹤算法壓縮為r個隱含變量的約簡表示，其中r≤n．數據子空間中排在最前面的r個基向量的壓縮顯示了最大變化值．

(2) 更新．在每個新數據點到達的時候更新這種表示，采用了迭代協方差矩陣來增量更新最前r個基向量和隱含變量．這個過程使用一種近似和迭代的方法，算法可以適時更新數據模式．

(3) 信號分類．分別選擇包含正常、異常類型相關度高的數據集進行訓練，采用變化點子空間追蹤方法提取出每一類輸入信號的特征子空間向量．

(4) 抗原變化點檢測．定義Δ時間內滑動窗口，統計時間序列數據流特征的變化情況，并在下一時間間隔內對上一時間窗口序列值進行修正，從而達到實時檢測的目的．

(5) 樹突狀細胞算法的權值求和．當檢測到數據流的相對變化時，標記時間序列的變化點，并將標記變化點的時間序列定義為當前抗原，將當前抗原和輸入信號進行權值求和運算，判定異常．

1.1 子空間追蹤的信號壓縮方法

樹突狀細胞算法中的“采樣”過程，即對當前抗原攝取危險信號、抗原的病原體相關分子模式和安全信號的過程．筆者利用子空間追蹤算法實現抗原的“采樣”過程，對輸入信號進行預處理．使用特征子空間方法，必須在信號數據變化時，能夠追蹤時變數據和協方差矩陣的特征值和特征向量．算法通過監測所有的n個數據流之間的協方差矩陣Φ的估計值來實現關鍵變化點的檢測[8]．使用降維來構造數據的約簡表示，然后當新的數據點到達時，將迭代地更新該子空間，并隨著時間的推移逐漸遺忘舊的數據樣本．因此，它檢測到的變化是所有數據流的相對變化，而不是每個單獨數據流的歷史變化．

定義一個獨立隨機序列{Xn}，表示在T時間內出現的檢測數據流，對X1，X2，…，Xi，…，Xn進行檢測，其中i為未知變化點，1≤i≤n．設k=n-i，表示時間窗為n的具有p個屬性的多維數據流．子空間追蹤算法大部分都是基于正交迭代的原則，將正交迭代應用于協方差矩陣中．子空間追蹤的主要目標是遞歸r個主要特征值以及時間遞歸更新協方差矩陣相關的特征向量，如下所示:

Φ(t)=αΦ(t-1)+X(t)XT(t) ,

(1)

其中，t時刻數據流之間的協方差矩陣為Φ，X(t)是在t時刻n個數據流的輸入數據向量；α是一個正的指數遺忘因子，0<α<1．然后，在每個時間步長利用一個正交迭代，即

其中，A(t)是一個p×r的輔助矩陣，Q(t)是包含r個估計主特征向量的n×r矩陣，S(t)是以降序排列的估計特征向量的r×r上三角矩陣．

為了獲得一個適度的子空間傳播模型來完成遞歸，引入下面的狀態空間形式:

Q(t)=Q(t-1)Θ(t)+Δ(t) ,

(3)

其中，Δ(t)是一個滿足

QT(t-1)Δ(t)=0

(4)

的修正矩陣；Θ(t)是子空間轉置矩陣，將其表示為

Θ(t)=QT(t-1)Q(t) ．

(5)

給定主特征的基向量，數據向量X(t)可以被壓縮到一個低維表示，即

h(t)=QT(t-1)X(t) ,

(6)

其中，h(t)向量描述了r個隱含變量．

將式(1)和式(3)代入式(2a)中，并經過約簡可得輔助矩陣A(t)，即

A(t)=αA(t-1)Θ(t-1)+X(t)hT(t) ．

(7)

由式(2b)可知輔助矩陣A(t)也是一個正交分解問題，則可用以下公式更新正交分解:

Q(t)S(t)=αQ(t-1)S(t-1)Θ(t-1)+X(t)hT(t) ．

(8)

根據以上描述，在每個時間步長迭代地更新Q，S矩陣，用這些結果來計算壓縮投影或隱含變量h(t)；然后，使用這些主特征向量將原始數據約簡，從而得到原始數據的低秩近似值．

1.2 變化點檢測的抗原定義

異常總是與輸入數據的變化相關聯，變化點是候選的異常事件，但是一些變化點也對應著輸入數據中正常的周期性變化．采用時間序列變化點檢測，對一個隨機過程{Xn}，以順序的方式獲得時間序列，檢測時間序列是否在統計分布規律上發生變化．當異常發生時，網絡數據的多個特征通常會同時發生變化，通過標記特征變化情況，能夠有效地放大異常數據流與正常數據流之間的差異，提高檢測精度．

為了檢測網絡異常，采用滑動窗口無參數CUSUM檢測算法在線檢測并行的多維數據流[9]．CUSUM方法能夠快速地反映出數據流特征的變化情況，無須建立數學模型，并在下一時間間隔內對序列值進行修正，得到更準確的檢測序列值．算法只累積一定窗口時間內的輸入數據流和在此期間出現的異常變化點個數，當它們超過一定的閾值時，則表明有異常發生．

設在一定時間窗T內，共包含有m個Δt，則滑動窗口內Xn的累積值yn表示為

(9)

用以下遞歸定義提高計算效率:

(10)

其中，y0=0，yn表示在窗口時間T內出現的變化點個數，x+定義為

(11)

設報警閾值為λ，則判斷異常的函數為

(12)

當yn超過閾值λ時，檢測到變化，在這個時間步長中標記變化，并且所有累積變量復位．

1.3 輸入輸出信號關聯關系

一旦預處理信號類型的特征被確定，下一步進行樹突狀細胞算法的輸入輸出關聯、上下文評價和樹突狀細胞分類等過程．對輸入信號進行預處理是為了獲得以下輸出信號:

(1) 協同刺激分子值(csm): 用于判定細胞是否進行狀態轉換;

(2) 半成熟細胞因子(semi): 用于判定細胞的“安全程度”;

(3) 成熟細胞因子(mat): 用于判定細胞的“危險程度”．

根據輸入信號計算輸出信號，采用標準樹突狀細胞算法的加權求和方法進行輸入輸出信號相關性處理，利用以下帶權計算公式:

(13)

其中，O[k]表示輸出信號(O[0]～O[2]依次表示csm、semi、mat)，Si表示輸入信號(S0～S2依次表示抗原的病原體相關分子模式、DS、SS)，Wij表示從Si到Oj的相應信號權值．權值可以根據具體的應用環境進行調整．

1.4 上下文評估

樹突狀細胞是根據協同刺激分子值O[0]的大小進行狀態轉換，并進一步對抗原進行危險度判定的．O[0]值的計算需要一個累加的過程．對于排在細胞集尾部的數據，有可能因O[0]值未達到遷移閾值而導致細胞無法成熟，因此需多次迭代運行．然而樹突狀細胞算法的多次迭代并不能有效地提高檢測精度，只是為了完成對邊界數據的評價處理．

筆者對樹突狀細胞算法的評估方法進行改進，在算法中加入動態遷移閾值的概念，通過控制未成熟樹突狀細胞(iDC)的遷移閾值，加速或者減緩未成熟樹突狀細胞的分化成熟，有效改進算法的檢測效率．加入數據變化點之后的 (n-i) 個抗原數據為Xi+1，Xi+2，…，Xn．設當前抗原的評估系數為β，Ai為抗原特征向量，計算每個后續抗原與當前變化點抗原的親和力D為

設動態遷移閾值為mt，樹突狀細胞的遷移狀態由評估系數β進行調節．若評估系數β很小，則后續抗原延續了當前變化點抗原的變化狀態，上調mt以減緩未成熟樹突狀細胞的成熟，繼續采樣后續抗原．動態遷移閾值定義為

mt(t)=mt(t-1)+Δ(β) ,

(16)

其中，Δ(β)是β的相關增量．β越大，表示后續抗原與當前抗原的狀態越相異，根據式(16)調整mt，加速未成熟樹突狀細胞成熟，防止其截取到后續抗原，從而有效地降低了數據誤分類的可能．設輸出信號O[0]的值為Zcsm，若Zcsm>mt(t)，則當前未成熟樹突狀細胞成熟并遷移出細胞庫．

下一步，計算成熟環境抗原值V，并對當前抗原進行評價:

V=O[2]/(O[1]+O[2]) ．

(17)

2 實驗及仿真

實驗數據采用KDD CUP 1999入侵檢測標準數據集[10]．其中異常數據分為39種入侵類型，訓練集中包含22種入侵類型，另外的17種預先未知的入侵類型包含在測試集中．網絡連接記錄包含41個屬性，其中包括34個連續形式的屬性和7個離散形式的屬性．實驗采用了該數據集的一個10%的子集(kddcup.data10percentcorrected)，選取 2 396 條測試數據，選擇12 種入侵模式，使用41個屬性．實驗環境采用Matlab 2011a、windows 7、Visual C++6.0 作為仿真測試工具平臺．

2.1 信號預處理測試

首先對變化點特征提取的子空間算法進行驗證．設定數據流數目n=20，指數遺忘因子α=0.996，每個時間步長t=3 000，分別用主成分分析算法、基于壓縮的投影近似子空間跟蹤算法(PASTd)和筆者提出的變化點子空間追蹤(CPD)算法對測試數據流進行降維處理，分析了3種算法的降維效果，并進行了對比，圖2的(a)～(d)分別顯示了原始數據集分布和各種算法降維結果的數據分布．

圖2 不同算法降維結果的數據分布圖

2.2 檢測測試

表1 改進樹突狀細胞算法的檢測實驗結果

用8組測試數據對標準樹突狀細胞算法、PCA-DCA算法(主成分分析-樹突細胞算法)和筆者提出的CPD-DCA算法進行檢測，對3種算法使用相同的測試數據進行檢測．在經歷環境狀態變化時，抗原數目不斷增加的平均檢測率對比關系如圖3所示．3種算法分別在進化過程中所占存儲空間比例的對比如圖4所示．

圖3 3種檢測算法的檢測率對比圖圖4 3種檢測算法的存儲空間壓縮率對比圖

從圖3可以看出，樹突狀細胞算法和PCA-DCA算法的檢測率有明顯的波動，對比而言，CPD-DCA算法整體檢測率高于其他兩種算法，且穩定性較好，CPD-DCA算法可以維持在一個較高的識別率狀態．由于在算法運行過程中，輸入信號的維數迭代降低(見圖4)，內存消耗隨維數的降低而減少， 主要受維度的影響，CPD-DCA算法的存儲空間利用率明顯高于其他兩種算法．

3 總 結

在樹突狀細胞算法中，由于缺乏一個對信號和抗原的可量化定義，導致在實際應用中對樹突狀細胞算法的各種主觀輸入的指定和人為參數設置．筆者提出了基于變化點子空間追蹤的信號特征降維算法，根據異常訓練數據自動提取相關度最高的特征構成樹突狀細胞算法的輸入信號；采用了滑動時間窗CUSUM檢測方法，對抗原的檢測只強調數據流關鍵變化點的檢測以及在上下文評估中加入遷移閾值的動態性，在很大程度上降低了計算空間，同時保證了更加準確和穩定的檢測效率，具有較好的實際操作性．實驗證明，算法不僅具有準確性高、檢測率高、消耗計算資源少的特點，而且能夠區分正常數據變化與異常，并可以在入侵出現的早期檢測出異常的存在．

[1] Greensmith J. The Dendritic Cell Algorithm [D]. Nottingham: University of Nottingham, 2007.

[2] 王凌霞, 焦李成, 顏學穎, 等. 利用免疫克隆進行小波域遙感圖像變化檢測[J]. 西安電子科技大學學報, 2013, 40(4): 108-113.

Wang Lingxia, Jiao Licheng, Yan Xueying, et al. Change Detection in Multi-temporal Remote Sensing Images Based on the Wavelet-domain Immune Clonal Optimazition[J]. Journal of Xidian University, 2013, 40(4): 108-113.

[3] Gu F. Theoretical and Empirical Extensions of the Dendritic Cell Algorithm [D]. Nottingham: University of Nottingham, 2011.

[4] Amaral J L M. Fault Detection in Analog Circuits Using a Fuzzy Dendritic Cell Algorithm[C]//Proceedings of the 10th International Conference on Artificial Immune Systems: 6825. Heidelberg: Springer, 2011: 294-307.

[5] Hart E, Davoudani D. An Engineering-informed Modelling Approach to AIS[C]//Proceedings of the 10th International Conference on Artificial Immune Systems: 6825. Heidelberg: Springer, 2011: 240-253.

[6] Gu F, Greensmith J, Oates R, et al. PCA 4 DCA: the Application of Principal Component Analysis to the Dendritic Cell Algorithm[C]//Proceedings of the 9th Annual Workshop on Computational Intelligence. Nottingham: University of Nottingham, 2009: 352-358.

[7] Chelly Z, Elouedi Z. RC-DCA: a New Feature Selection and Signal Categorization Technique for the Dendritic Cell Algorithm Based on Rough Set Theory[C]//Proceedings of the 11th International Conference on Artificial Immune Systems: 7597. Heidelberg: Springer, 2012: 152-165.

[8] Strobach P. The Fast Recursive Row-Householder Subspace Tracking Algorithm [J]. Signal Processing, 2009, 89(12): 2514-2528.

[9] Bassevilleand M, Nikiforov I V. Detection of Abrupt Changes: Theory and Application[M]. New Jersey: Prentice Hall, 1993.

[10] Stolfo S J, Fan W, Lee W, et al.KddCup 1999 Data[DB/OL]. [2013-01-30]. http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.