田玉玲

(太原理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

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

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

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

1 基于時間序列的樹突狀細(xì)胞算法

基于免疫學(xué)的樹突狀細(xì)胞算法能夠?qū)⒖乖蛄幸约耙幌盗行盘栠M(jìn)行融合，實現(xiàn)異常檢測．筆者提出的改進(jìn)樹突狀細(xì)胞算法，采用變化點檢測子空間追蹤方法自動對抗原及原始信號進(jìn)行規(guī)格化處理，避免了由任意映射或?qū)＜翌I(lǐng)域知識給定的外部信號干預(yù)．算法旨在忽略某些正常數(shù)據(jù)，而強(qiáng)調(diào)某些關(guān)鍵變化點的檢測，不僅能根據(jù)輸入數(shù)據(jù)流的變化及時更新信號子空間，而且能大規(guī)模減少檢測數(shù)據(jù)量，提高了系統(tǒng)的實用性和準(zhǔn)確性，為異常檢測系統(tǒng)提供了一種新的理論框架．

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

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

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

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

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

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

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

(5) 樹突狀細(xì)胞算法的權(quán)值求和．當(dāng)檢測到數(shù)據(jù)流的相對變化時，標(biāo)記時間序列的變化點，并將標(biāo)記變化點的時間序列定義為當(dāng)前抗原，將當(dāng)前抗原和輸入信號進(jìn)行權(quán)值求和運(yùn)算，判定異常．

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

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

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

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

(1)

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

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

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

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

(3)

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

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

(4)

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

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

(5)

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

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

(6)

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

將式(1)和式(3)代入式(2a)中，并經(jīng)過約簡可得輔助矩陣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)

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

1.2 變化點檢測的抗原定義

異?？偸桥c輸入數(shù)據(jù)的變化相關(guān)聯(lián)，變化點是候選的異常事件，但是一些變化點也對應(yīng)著輸入數(shù)據(jù)中正常的周期性變化．采用時間序列變化點檢測，對一個隨機(jī)過程{Xn}，以順序的方式獲得時間序列，檢測時間序列是否在統(tǒng)計分布規(guī)律上發(fā)生變化．當(dāng)異常發(fā)生時，網(wǎng)絡(luò)數(shù)據(jù)的多個特征通常會同時發(fā)生變化，通過標(biāo)記特征變化情況，能夠有效地放大異常數(shù)據(jù)流與正常數(shù)據(jù)流之間的差異，提高檢測精度．

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

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

(9)

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

(10)

其中，y0=0，yn表示在窗口時間T內(nèi)出現(xiàn)的變化點個數(shù)，x+定義為

(11)

設(shè)報警閾值為λ，則判斷異常的函數(shù)為

(12)

當(dāng)yn超過閾值λ時，檢測到變化，在這個時間步長中標(biāo)記變化，并且所有累積變量復(fù)位．

1.3 輸入輸出信號關(guān)聯(lián)關(guān)系

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

(1) 協(xié)同刺激分子值(csm): 用于判定細(xì)胞是否進(jìn)行狀態(tài)轉(zhuǎn)換;

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

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

根據(jù)輸入信號計算輸出信號，采用標(biāo)準(zhǔn)樹突狀細(xì)胞算法的加權(quán)求和方法進(jìn)行輸入輸出信號相關(guān)性處理，利用以下帶權(quán)計算公式:

(13)

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

1.4 上下文評估

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

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

設(shè)動態(tài)遷移閾值為mt，樹突狀細(xì)胞的遷移狀態(tài)由評估系數(shù)β進(jìn)行調(diào)節(jié)．若評估系數(shù)β很小，則后續(xù)抗原延續(xù)了當(dāng)前變化點抗原的變化狀態(tài)，上調(diào)mt以減緩未成熟樹突狀細(xì)胞的成熟，繼續(xù)采樣后續(xù)抗原．動態(tài)遷移閾值定義為

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

(16)

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

下一步，計算成熟環(huán)境抗原值V，并對當(dāng)前抗原進(jìn)行評價:

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

(17)

2 實驗及仿真

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

2.1 信號預(yù)處理測試

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

圖2 不同算法降維結(jié)果的數(shù)據(jù)分布圖

2.2 檢測測試

表1 改進(jìn)樹突狀細(xì)胞算法的檢測實驗結(jié)果

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

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

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

3 總 結(jié)

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

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

[2] 王凌霞, 焦李成, 顏學(xué)穎, 等. 利用免疫克隆進(jìn)行小波域遙感圖像變化檢測[J]. 西安電子科技大學(xué)學(xué)報, 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.