用于实时异常检测的树突状细胞算法

袁 嵩，陈启卷

（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.