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

袁 嵩，陳啟卷

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

0 引 言

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

1 標準DCA

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

2 實時DCA

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

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

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

表1 DCA權值矩陣

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

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

算法的具體描述如下：

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

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

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

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

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

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

圖1 實時DCA算法流程

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

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

3 實驗與結果分析

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

實驗1：前240條Class 1數據，后460條Class 2數據，讓算法經歷一次環境狀態轉換；

實驗2：前230條Class 2數據，中間240條Class 1數據，后230條Class 2數據，讓算法經歷兩次環境狀態轉換；

實驗3：115條Class 2數據＋120條Class 1數據＋115條Class 2數據＋120條Class 1數據＋230條Class 2數據，讓算法經歷四次環境狀態轉換。

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

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

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

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

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

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

（4）抗原信號是按時間順序進入抗原信號池的，但由于DC采樣的隨機性，得到最終評判移出抗原信號池的順序并非按照嚴格的隊列先入先出，但越早進入抗原信號池的數據，池內時間越長，被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 結束語

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

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

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

［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）.［倪建成，李志蜀，孫繼榮，等.樹突狀細胞分化模型在人工免疫系統中的應用研究［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，FENG Chao，ZHANG Quan，et al.Principles and application of dendritic cell algorithm［J］.Computer Engineering，2010，36（8）：173－176（in Chinese）.［陳岳兵，馮超，張權，等.樹突狀細胞算法原理及其應用［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.