用于實時異常檢測的樹突狀細胞算法

袁 嵩，陳啟卷

（1.武漢大學 動力與機械學院，湖北 武漢430072；2.武漢科技大學計算機科學與技術學院，湖北 武漢430065）

0 引 言

樹突狀細胞（dendritic cell，DC）［1－2］作為先天性免疫系統(tǒng)中專職的抗原提呈細胞，能夠融合處理多種環(huán)境信號，并將信號與抗原相關聯(lián)，分析得到抗原的異常指標。樹突狀細胞算法（dendritic cell algorithm，DCA）［3］作為人工免疫學中危險理論的最新研究成果，已用于解決各類問題，特別是應用于異常檢測領域［4］。理想上說異常檢測應該實時地進行以便在問題出現(xiàn)時能盡早地發(fā)現(xiàn)并響應。因此，由異常檢測系統(tǒng)執(zhí)行的分析程序就必須實時或者盡可能地接近實時。然而目前DCA的分析程序基本上都是脫機進行的，要提高異常檢測系統(tǒng)的性能，就要針對DCA的實時分析進行研究。Gu在文獻［5］中將分割（segmentation）應用到DCA中，讓分析在檢測過程中周期性地執(zhí)行，突破了傳統(tǒng)的離線分析，但仍存在不同程度的延遲。檢測速度和檢測精度作為實時異常檢測系統(tǒng)的兩個重要性能指標必須同時考慮。本文設計了一個和檢測過程并行的分析機制，在檢測過程中不斷地將達到輸出條件的抗原及時輸出，在保證檢測精度的同時實現(xiàn)了最大可能的實時。

1 標準DCA

DCA是從生物免疫系統(tǒng)中抗原提呈的角度出發(fā)，對輸入抗原抽象出輸入信號進行計算得到輸出信號決定DC的狀態(tài)，再根據(jù)DC的狀態(tài)評價抗原的異常程度，最后與預先設定的異常閾值比較輸出結(jié)果。輸入信號包括：病原體相關分子模式（pathogen associated molecular patterns，PAMP）表示絕對的異常；危險信號（danger signals，DS）表示異常的可能性非常大；安全信號（safe signals，SS）表示異常的可能性非常小；致炎細胞因子（inflammatory cytokines，IC）用于放大前3種信號的影響。DC在免疫過程中有3種狀態(tài)即未成熟、半成熟和成熟狀態(tài)。未成熟DC處理輸入信號得到3種輸出信號：協(xié)同刺激分子csm（costimulatory molecules）用于決定DC是否進行狀態(tài)轉(zhuǎn)換；半成熟樹突狀細胞因子semi（semi－mature DC cytokines）表示抗原所處組織環(huán)境的安全程度；成熟樹突狀細胞因子mat（mature DC cytokines）表示抗原所處組織環(huán)境的危險程度。未成熟DC每處理一組輸入信號都將得到的3個輸出信號分別進行累加，當DC內(nèi)∑csm達到遷移閾值時則比較∑semi和∑mat：如果∑semi＞∑mat，DC轉(zhuǎn)化為半成熟狀態(tài)，表示細胞環(huán)境安全，意味著抗原是在正常狀態(tài)下采集的；否則DC轉(zhuǎn)化為成熟狀態(tài)，表示細胞環(huán)境危險，意味著抗原是在異常狀態(tài)下采集的。細胞環(huán)境用于對DC內(nèi)采集的所有抗原進行標記。組織不斷更新信號、抗原和DC細胞，系統(tǒng)記錄DC所采樣的抗原和DC的狀態(tài)產(chǎn)生了一個信息序列。標準DCA的離線分析就是根據(jù)這個信息序列對抗原進行綜合評價，計算每個抗原的MCAV（mature context antigen value，上下文環(huán)境成熟抗原值），通過該值反映抗原的異常程度來檢測是否存在異常。更多算法細節(jié)參見文獻［6］。

2 實時DCA

信號和抗原隨著時間的推移被DC融合處理得到一個信息序列。如上所述，傳統(tǒng)DCA的分析階段是在最后進行的，是當整個信息序列產(chǎn)生之后再對其進行分析，這樣無法實現(xiàn)實時檢測。因此必須設計一個實時分析機制執(zhí)行于檢測過程中以取代傳統(tǒng)的離線分析。Gu在文獻［5］提出的分割是根據(jù)一定的輸出數(shù)據(jù)量或一定的時間間隔將這個信息序列劃分成相對較小的片段，當采樣的抗原數(shù)量達到了片段的大小或達到了一定的時間間隔，分析就在這個片段內(nèi)執(zhí)行，從而達到了接近實時的目的。但問題是片段中的信息量是否為分析提供了足夠的依據(jù)。片段太小，依據(jù)不足，影響檢測精確度；片段太大，系統(tǒng)敏感度降低，失去了實時檢測的目的。并且無論怎么分割，總存在已達到輸出條件的抗原被滯留而未達到輸出條件的抗原被盲目判斷的可能。

我們提出了一個更容易理解也易于實現(xiàn)的實時分析算法，在信息序列產(chǎn)生的過程中，只要得到了某抗原足夠的檢測依據(jù)，就立刻進行分析并輸出檢測結(jié)果，大致思路如下：初始化一個大小為m的抗原信號池存放抗原和信號，每一個DC分配一個隨機的遷移閾值后從抗原信號池中隨機采樣抗原和信號，即對輸入信號進行融合處理。信號的融合是非常復雜的，至今仍有許多未知領域［7］。為了簡化計算我們忽略了IC的影響，采用的信號轉(zhuǎn)化處理公式如下所示

式中：Oj——輸出信號（O0－O2依次表示csm、semi、mat），Si——輸入信號（S0－S2依次表示 PAMP、DS、SS），Wij——從Si到Oj的權(quán)重，權(quán)值矩陣見表1。

表1 DCA權(quán)值矩陣

表1中的權(quán)值數(shù)據(jù)是由免疫學家通過對生物免疫的實驗得出，其中權(quán)值可以根據(jù)具體的應用場景進行調(diào)整，但是輸入輸出信號之間的相互影響關系應該滿足：PAMP影響csm、mat；DS影響csm、mat；SS影響csm、semi和mat。

DC對采樣的抗原提取3個輸入信號并通過權(quán)值公式和權(quán)值矩陣計算得到3個輸出信號并分別進行累加。當∑csm達到遷移閾值則根據(jù)∑semi和∑mat的濃度轉(zhuǎn)換為半成熟或成熟狀態(tài)，然后對DC中所采樣的抗原進行標記，半成熟DC標記采樣的所有抗原為正常，成熟DC標記采樣的所有抗原為異常，這就好比是DC為抗原進行投票，一個DC就是一個評委，我們?yōu)槊總€抗原記下2個數(shù)據(jù)，一個是投票總數(shù)，一個是異常票數(shù)，當投票總數(shù)達到一個閾值N，計算該抗原的MCAV，即異常票數(shù)與投票總數(shù)的比值，再與異常閾值進行比較得到最終評價及時輸出，然后更新抗原信號池，從池中移除被評價的抗原，加入新的抗原，直到所有抗原被判別完，算法結(jié)束。算法流程如圖1所示。

算法的具體描述如下：

步驟1 初始化一個長度為m的抗原信號池，將數(shù)據(jù)集前m項放入池中；

步驟2 初始化DC細胞，設置一定范圍內(nèi)的隨機遷移閾值和生命期限；

步驟3 DC細胞在生命期限內(nèi)從抗原信號池中隨機采樣，累計3個輸出值：csm、semi、mat，超過生命期限的DC細胞重新初始化，轉(zhuǎn)步驟2；

步驟4 判斷DC細胞的累計csm是否達到遷移閾值，沒有則轉(zhuǎn)步驟3繼續(xù)采樣；

步驟5 對DC細胞中所采樣的抗原進行分析，記錄每種抗原的判別次數(shù)和異常次數(shù)；

步驟6 判斷是否存在已達到預先設定判別次數(shù)N的抗原，是則計算出抗原的MCAV，評價抗原的異常程度實時輸出，并從抗原信號池中移除，否則轉(zhuǎn)步驟2；

圖1 實時DCA算法流程

步驟7 判斷是否存在新抗原，是則將新抗原加入采樣池中填補移除的空缺，轉(zhuǎn)步驟2；

步驟8 判斷池中是否還有抗原未被評估，是則轉(zhuǎn)步驟2，否則算法終止。

3 實驗與結(jié)果分析

本文選用了文獻［6］中提到的標準 UCI Wisconsin Breast Cancer數(shù)據(jù)集，包括700條數(shù)據(jù)，其中240條標記為Class 1（正常），另外460條標記為Class 2（異常），數(shù)據(jù)的部分屬性被抽象作為輸入信號。根據(jù)不同的數(shù)據(jù)順序做了3種實驗。

實驗1：前240條Class 1數(shù)據(jù)，后460條Class 2數(shù)據(jù)，讓算法經(jīng)歷一次環(huán)境狀態(tài)轉(zhuǎn)換；

實驗2：前230條Class 2數(shù)據(jù)，中間240條Class 1數(shù)據(jù)，后230條Class 2數(shù)據(jù)，讓算法經(jīng)歷兩次環(huán)境狀態(tài)轉(zhuǎn)換；

實驗3：115條Class 2數(shù)據(jù)＋120條Class 1數(shù)據(jù)＋115條Class 2數(shù)據(jù)＋120條Class 1數(shù)據(jù)＋230條Class 2數(shù)據(jù)，讓算法經(jīng)歷四次環(huán)境狀態(tài)轉(zhuǎn)換。

3種實驗除數(shù)據(jù)順序外，其它參數(shù)設置不變，抗原信號池大小m設為20，遷移閾值的隨機范圍設為30－50，評估閾值N設為10，異常閾值設為0.65。由于抗原采樣和DC細胞遷移閾值的隨機性，每種實驗的每次結(jié)果不完全一樣，圖2～圖4為3種實驗的某次效果圖，橫坐標是抗原序號，縱坐標是每個抗原的 MCAV值，小于異常閾值0.65的被分類為Class 1，否則分類為Class 2。表2是每種實驗運行20次的平均精確度、誤報率和漏報率。

表2 3種實驗運行20次的平均精確率、誤報率和漏報率

實驗觀察表明，除了個別噪聲數(shù)據(jù)外，絕大部分錯誤均發(fā)生在兩類環(huán)境轉(zhuǎn)換的過渡階段，這是由于DC在采樣池中采樣了多個抗原和多套信號，在轉(zhuǎn)換邊界兩類數(shù)據(jù)的相互干擾所導致的。和文獻［6，8］中提供的實驗數(shù)據(jù)相比，這個實驗結(jié)果是比較理想的。該算法的特點主要體現(xiàn)在以下幾個方面：

（1）DCA是一個高度隨機的算法［9］，DC在抗原信號池中的采樣是隨機的，DC的遷移閾值在一定范圍內(nèi)也是隨機的，一個DC采樣多個抗原，采樣的抗原種類和數(shù)量都是多樣的，這與生物系統(tǒng)的表現(xiàn)一致。一個抗原被多個DC采樣，當達到足夠的評估次數(shù)確定抗原最終的分類后及時輸出以達到最大可能的實時。并且通過多數(shù)正確判斷減少了誤判的影響，保證了算法的精確度。

（2）長度為m的抗原信號池起到了時間窗［10］的作用，它讓時間上相關的抗原信號在池中產(chǎn)生了上下文環(huán)境，消除了時間間隔較大，相隔較遠的不相關數(shù)據(jù)的相互干擾，進一步保證了算法的精確度。

（3）DC遷移閾值的設定影響到檢測精度和響應速度。遷移閾值過小，DC所采樣的抗原較少，細胞環(huán)境就由這些少量的抗原決定，DC對抗原的評價就過于武斷，檢測精度難以保證；遷移閾值過大，DC所采樣的抗原較多，系統(tǒng)響應速度會下降。700條數(shù)據(jù)通過權(quán)值公式和權(quán)值矩陣計算得到的csm值平均為8.9，為了同時保證檢測精度和響應速度，讓一個DC平均采樣5個抗原為宜，遷移閾值的隨機范圍設為30～50以達到最佳效果。從以上實驗效果圖可以看出兩類數(shù)據(jù)的轉(zhuǎn)換是比較干凈利落的。

（4）抗原信號是按時間順序進入抗原信號池的，但由于DC采樣的隨機性，得到最終評判移出抗原信號池的順序并非按照嚴格的隊列先入先出，但越早進入抗原信號池的數(shù)據(jù)，池內(nèi)時間越長，被DC采樣的機會越多，越先達到評估閾值出池的概率越大，從而到達實時分析的目的。下面截取的是某次實驗出池的抗原ID序列：……102 101 105 103 99 108 98 106 100 115 104 107 110 116 121 122 111 112 117 113 109 119 114 124 120 123 128 125 139 118 130 126 131 136 129 137 127 133 135 142 134 138 132 140……

4 結(jié)束語

一個有效的異常檢測系統(tǒng)應該能夠在一定的時間界限內(nèi)對出現(xiàn)的異常做出反應。本文提出的這個實時分析算法，有效地改善了DCA在異常檢測領域的應用性能，除了以實時或接近實時的方式實現(xiàn)了在線分析，同時也達到了可觀的檢測精度，進一步的實驗表明，相關參數(shù)（例如DCA權(quán)值矩陣）的改變可以得到更好的結(jié)果。針對該算法所體現(xiàn)的檢測性能，我們下一步的工作將從以下兩個方面入手：

（1）以上實驗表明在過渡區(qū)間中識別時空上聚集的抗原會有小程度的混亂，可以推論，DCA的檢測精度會隨著上下文環(huán)境快速連續(xù)地轉(zhuǎn)換而降低，初步的實驗證明了這一點，我們讓算法經(jīng)歷39次環(huán)境狀態(tài)轉(zhuǎn)換，精確度下降到80%左右，因此基于DCA的新的算法將被設計用來針對無序數(shù)據(jù)集的異常檢測。

（2）可以考慮犧牲誤報率來獲取最低的漏報率，大量的應用表明及時檢測到真正的異常遠比 “冤枉”正常重要，何況誤報可以通過其它途徑解決，例如管理員二次確認以及適應性免疫系統(tǒng)等。

［1］Greensmith J，Aickelin U，Cayzer S.Introducing dendritic cells as a novel immune－inspired algorithm for anomaly detection［C］／／Proc of the 4th International Conference on Artificial Immune Systems.Banff，Alberta，Canada：Springer，2005：153－167.

［2］Greensmith J，Twycross J，Aickelin U.Dendritic cells for anomaly detection［C］／／Proc of the IEEE Congress on Evolutionary Computation.Vancouver，Canada：IEEE，2006：664－671.

［3］Greensmith J，Aickelin U，Twycross J.Articulation and clarification of the dendritic cell algorithm［C］／／Proc of the 5th International Conference on Artificial Immune Systems.Oeiras，Portugal：Springer，2006：404－417.

［4］Greensmith J，Aickelin U，Tedesco G.Information fusion for anomaly detection with the dendritic cell algorithm［J］.Informarion Fusion，2010，11（1）：21－34.

［5］Gu F，Greensmith J，Aickelin U.Integrating real－time analysis with the dendritic cell algorithm through segmentation［C］／／Proc of the 11th Annual Conference on Genetic and Evolutionary Computation.Montreal，Québec，Canada：ACM，2009：1203－1210.

［6］Greensmith J.The dendritic cell algorithm［D］.Nottingham，UK：University of Nottingham，2007.

［7］NI Jiancheng，LI Zhishu，SUN Jirong，et al.Research on differentiation model and application of dendritic cells in artificial immune system［J］.Acta Electronica Sinica，2008，36（11）：2210－2215（in Chinese）.［倪建成，李志蜀，孫繼榮，等.樹突狀細胞分化模型在人工免疫系統(tǒng)中的應用研究［J］.電子學報，2008，36（11）：2210－2215.］

［8］YANG Chenxu，WU Gengfeng，HU Min.Improved dendritic cells algorithm［J］.Computer Engineering，2009，35（23）：194－200（in Chinese）.［楊晨旭，吳耿鋒，胡珉.一種改進的樹突狀細胞算法［J］.計算機工程，2009，35（23）：194－200.］

［9］CHEN Yuebing，F(xiàn)ENG Chao，ZHANG Quan，et al.Principles and application of dendritic cell algorithm［J］.Computer Engineering，2010，36（8）：173－176（in Chinese）.［陳岳兵，馮超，張權(quán)，等.樹突狀細胞算法原理及其應用［J］.計算機工程，2010，36（8）：173－176.］

［10］Gu F，Greensmith J，Aickelin U.Further exploration of the dendritic cell algorithm：antigen multiplier and moving windows［C］／／Proc of the 7th International Conference on Artificial Immune Systems.Phuket，Thailand：Springer，2008：142－153.