可調(diào)控誤報率和漏報率的樹突狀細胞算法＊

袁 嵩

（1.武漢科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，湖北 武漢430065；

2.智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室，湖北 武漢430065）

1 引言

樹突狀細胞算法 DCA（Dendritic Cell Algo－rithm）［1］是受自然免疫系統(tǒng)中樹突狀細胞DC（Dendritic Cell）［2，3］的功能啟發(fā)，對其抗原提呈行為進行抽象建模而衍生的人工免疫算法，已用于解決各類問題，特別是應(yīng)用于異常檢測領(lǐng)域［4，5］。DC的整個生物機制中存在著大量的生物要素，其中危險信號的融合及內(nèi)部信號的生成是非常復(fù)雜的過程，至今仍有許多未知領(lǐng)域［6］。DCA是基于如此復(fù)雜生物機制的高度隨機算法，涉及較多的相互作用成分和參數(shù)，所以難以對算法進行分析和控制。目前，對DCA的研究主要集中于提高檢測精度和簡化參數(shù)等方面［7，8］，針對 DCA參數(shù)敏感性分析和對檢測結(jié)果靈活控制的研究還很少。

為了對檢測結(jié)果誤報率和漏報率進行有效的調(diào)控，本文從DCA權(quán)值矩陣對檢測結(jié)果的影響入手，針對DC對細胞環(huán)境的評判準則提出傾向因子的概念，并將其融入到DC的狀態(tài)轉(zhuǎn)化機制中，設(shè)計一種改進的“投票制”DCA；作為投票制DCA設(shè)計思路的自然延伸，將DC對細胞環(huán)境的評判方式從投票改為打分，設(shè)計一個“評分制”DCA。本文給出了兩種算法的設(shè)計思路和調(diào)控機制，并通過實驗驗證了算法的有效性和可控性。

2 傳統(tǒng)DCA

DC在免疫過程中根據(jù)不同的生存環(huán)境呈現(xiàn)出三種不同的狀態(tài)：未成熟狀態(tài)、半成熟狀態(tài)和成熟狀態(tài)。DC被抽象為一個信號處理器，對輸入信號進行融合處理得到輸出信號來決定DC的狀態(tài)，再根據(jù)DC的狀態(tài)評價抗原的異常程度。其中，輸入信號包括：病原體相關(guān)分子模式PAMP（Pathogen Associated Molecular Patterns）、危險信號 DS（Danger Signals）、安全信號SS（Safe Signals）、致炎細胞因子IC（Inflammatory Cytokines）；輸出信號包括：協(xié)同刺激分子csm（co－stimulatory molecules）、半成熟樹突狀細胞因子semi（semi－mature DC cytokines）、成熟樹突狀細胞因子 mat（mature DC cytokines）。

DCA算法流程如下：

步驟1 DC攝取環(huán)境信號（PAMP、DS、SS、IC）和抗原。

步驟2 DC處理輸入信號產(chǎn)生三種輸出信號（csm、semi、mat）并分別進行累加。

步驟3 如果∑csm小于設(shè)定的遷移閾值MT（Migration Threshold）則繼續(xù)進行步驟1和步驟2的操作；否則進行下一步。

步驟4 如果∑semi＞∑mat，DC轉(zhuǎn)化為半成熟狀態(tài)，抗原環(huán)境值標記為0；否則，DC轉(zhuǎn)化為成熟狀態(tài)，抗原環(huán)境值標記為1。

半成熟狀態(tài)的抗原環(huán)境意味著抗原是在正常狀態(tài)下收集的，而成熟環(huán)境則表示存在潛在的異常。通過計算每個抗原的成熟環(huán)境抗原值MCAV（Mature Context Antigen Value），即抗原被提呈為成熟環(huán)境抗原次數(shù)與被提呈的總次數(shù)的比值（反映抗原的異常程度），來檢測是否存在異常。更多的算法細節(jié)參見文獻［9，10］。

半成熟DC標記采樣的所有抗原為正常，成熟DC標記采樣的所有抗原為異常，這就好比DC作為評委，根據(jù)自身的狀態(tài)為其采樣的抗原投正常票或異常票，最后綜合多個DC評判的結(jié)果得到抗原的異常程度。為此為每個抗原記下兩個數(shù)據(jù)：投票總數(shù)和異常票數(shù)，當投票總數(shù)達到一個閾值N，計算該抗原的MCAV，即異常票數(shù)與投票總數(shù)的比值，再與異常閾值進行比較得到最終評價。本文把傳統(tǒng)DCA稱為投票制DCA，投票的準則即比較DC內(nèi)累加的semi和mat濃度，是否公平取決于信號的融合處理機制。

3 信號的融合處理

其中，Oj表示輸出信號（O0～O2依次表示csm、semi、mat），Si表示輸入信號（S0～S2依次表示PAMP、DS、SS），Wij表示從Si到Oj的權(quán)重。權(quán)值數(shù)據(jù)是由免疫學(xué)家通過對生物免疫的實驗得出的，其中權(quán)值可以根據(jù)具體的應(yīng)用場景進行調(diào)整，但是，輸入、輸出信號之間的相互影響關(guān)系應(yīng)該滿足：PAMP 影響csm、mat；DS 影響csm、mat；SS影響csm、semi和mat，并且SS對mat是負影響。目前常見的權(quán)值矩陣如表1～表3所示。

Table 1 Weight matric 1for DCA表1 DCA權(quán)值矩陣1

3.1 DCA信號轉(zhuǎn)換處理公式和權(quán)值矩陣

信號的融合處理是非常復(fù)雜的過程，為了避免對復(fù)雜的實際生物信號轉(zhuǎn)換機制進行建模，目前大多采用加權(quán)求和公式進行信號融合處理［11］。本文忽略了IC的影響，采用最簡單的信號轉(zhuǎn)換處理方式，如公式（1）所示，目的是為了更清晰地分析細胞環(huán)境轉(zhuǎn)換的公平程度。

Table 2 Weight matric 2for DCA表2 DCA權(quán)值矩陣2

Table 3 Weight matric 3for DCA表3 DCA權(quán)值矩陣3

這三種權(quán)值矩陣的不同之處就在于SS對semi和mat的影響權(quán)重。

3.2 權(quán)值矩陣對檢測結(jié)果的影響

本文選用文獻［9］中提到的標準UCI Wisconsin Breast Cancer數(shù)據(jù)集，包括700條數(shù)據(jù)，其中240條標記為Class 1（正常），另外460條標記為Class 2（異常），數(shù)據(jù)的部分屬性被抽象作為輸入信號，將以上三種權(quán)值矩陣代入信號轉(zhuǎn)換公式（1），并分別使用不同順序的數(shù)據(jù)集進行實驗：

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

（2）順序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）順序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)換。

DCA是一個高度隨機的算法，為了讓實驗結(jié)果具有可比性，所有參數(shù)設(shè)置相同，包括DC的遷移閾值也設(shè)置為一個固定值。但是，由于DC抗原采樣的隨機性，每種實驗的每次結(jié)果仍不盡相同，表4是每種實驗運行20次的平均精確度、誤報率和漏報率。

表4中的實驗數(shù)據(jù)反映出三種權(quán)值矩陣對檢測結(jié)果的影響：權(quán)值矩陣1效果最好，檢測精度最高，漏報率最低；權(quán)值矩陣3效果最差，雖然誤報率最低，但漏報率最高；權(quán)值矩陣2效果居中。究其原因，正是這三種權(quán)值矩陣中SS對semi和mat的影響權(quán)重的不同導(dǎo)致了分類結(jié)果的差異。

以權(quán)值矩陣2為例，將700條數(shù)據(jù)的輸入信號和權(quán)值矩陣2中的權(quán)重代入信號轉(zhuǎn)換公式（1）可得到三種輸出700組信號，分別求240個正常抗原的三種輸出信號的平均值和460個異常抗原的三種輸出信號的平均值，最后將這兩組數(shù)據(jù)再求平均，本文稱其為中性數(shù)據(jù)，如表5所示。

Table 5 Average output values of normal and abnormal antigens表5 正常、異常抗原的平均輸出值

從表5可以看出，中性數(shù)據(jù)中semi＞mat，表明了DC對semi的傾向，也就是說，DC作為評委對于中性數(shù)據(jù)的評判偏向于安全，這也是導(dǎo)致最終漏報率偏高的原因所在。將中性數(shù)據(jù)的mat減去semi：1.785－3.640＝－1.855，該值表明了DC對semi的傾向程度，為此本文提出傾向因子的概念。

定義1 將輸入信號和權(quán)值矩陣代入信號轉(zhuǎn)換公式得到輸出信號，分別求出正常抗原的三種輸出信號的平均值和異常抗原的三種輸出信號的平均值，將這兩組數(shù)據(jù)再求平均得到中性數(shù)據(jù)的三個輸出值，其mat與semi的差叫做傾向因子TF（Tendency Factor），反映了DC對安全或危險的傾向程度。

根據(jù)以上傾向因子的概念，將權(quán)值矩陣3代入信號轉(zhuǎn)換公式（1），求得的傾向因子為－5.5，這說明DC對環(huán)境的判斷更加偏向于安全，因此漏報率更高。將權(quán)值矩陣1代入信號轉(zhuǎn)換公式（1），求得的傾向因子為＋0.87，這說明DC對環(huán)境的判斷偏向于危險，因此漏報率低，并且該值最接近于0，說明DC對環(huán)境的評判較為公平。

Table 4 Effects of weight matrixs on detection results表4 權(quán)值矩陣對檢測結(jié)果的影響 %

由以上分析得出結(jié)論：不同的權(quán)值矩陣產(chǎn)生不同的傾向因子，反映了DC對安全或危險的傾向程度，隨意的權(quán)值設(shè)置將導(dǎo)致DC對環(huán)境的盲目判斷，因此傳統(tǒng)DCA中DC的狀態(tài)轉(zhuǎn)換準則是有待改進的。

4 改進的投票制DCA

傳統(tǒng)DCA中，當DC采樣了足夠的抗原達到遷移閾值時，通過比較∑mat和∑semi的大小來決定DC的轉(zhuǎn)換狀態(tài)存在一定局限性。因為通過不同的權(quán)值矩陣和不同的信號轉(zhuǎn)換公式進行的信號融合處理得到的細胞環(huán)境評判具有不同的傾向程度。為了保證對細胞環(huán)境評判的公平，并可以靈活調(diào)控檢測結(jié)果的誤報率和漏報率，將傾向因子融入到DC狀態(tài)轉(zhuǎn)換機制中，改進DC狀態(tài)轉(zhuǎn)換準則，思路如下：

（1）數(shù)據(jù)集預(yù)處理，根據(jù)權(quán)值矩陣和信號轉(zhuǎn)換公式求得傾向因子TF；

（2）初始化DC時增設(shè)一個變量n＝0，記載DC所采樣的抗原個數(shù)，DC每采樣1個抗原，該值加1；

（3）當DC內(nèi)累加的csm達到遷移閾值時判斷：如果∑mat－∑semi＞n＊TF，DC轉(zhuǎn)化為成熟狀態(tài)，否則DC轉(zhuǎn)化為半成熟狀態(tài)。

傳統(tǒng)DCA中，DC狀態(tài)轉(zhuǎn)換的準則是判斷∑mat與∑semi的差值是否大于0；改進的DC狀態(tài)轉(zhuǎn)換準則是判斷∑mat與∑semi的差值是否大于n倍的傾向因子，其中，n指的是DC所采樣的抗原個數(shù)。試想，如果DC采樣一個抗原將引起一倍的TF傾向，若DC采樣了n個抗原將引起n倍的TF傾向，用n＊TF作為標準來衡量∑mat與∑semi的差，目的是為了保證對環(huán)境是否安全或危險評判的公平。

采用改進的DC狀態(tài)轉(zhuǎn)換準則，重做以上三個實驗，實驗二和實驗三取得了明顯的改善效果，結(jié)果如表6所示。

由于實驗一中求得的傾向因子為＋0.87，該值最接近于0，說明DC對環(huán)境的評判已經(jīng)比較公平了，改進的實驗效果并不明顯，甚至稍遜于以前的實驗效果，這說明融入傾向因子并非一定達到最優(yōu)，但可作為尋求最優(yōu)的參考。進一步的實驗說明了這一點，表7為最優(yōu)解的傾向因子調(diào)整范圍。

Table 7 Adjust range of TFfor optimal solution表7 最優(yōu)解的傾向因子調(diào)整范圍

更進一步，將（n＊TF）看作是安全或危險的臨界值，設(shè)置一個稍大于（n＊TF）的值作為評判標準則偏向于安全，可適度降低誤報率；反之設(shè)置一個稍小于（n＊TF）的值作為評判標準則偏向于危險，可適度降低漏報率。由此可以根據(jù)具體應(yīng)用需求設(shè)置TF的值，調(diào)控檢測結(jié)果的誤報率和漏報率。

5 評分制DCA

5.1 算法思路

投票制DCA中，傾向因子的融入正是針對DC評判的公平準則，通過調(diào)整DC狀態(tài)轉(zhuǎn)換準則可控制異常檢測的誤報率和漏報率，但調(diào)控范圍（如表7所示）是采用試探法通過大量實驗得出的，并不直觀，若能根據(jù)最后抗原的異常程度加以調(diào)控可獲得更加直觀的效果。因此，本節(jié)并不在DC狀態(tài)轉(zhuǎn)換機制上進行調(diào)控，而是忽略DC的狀態(tài)轉(zhuǎn)換，改投票制DCA為評分制DCA，具體思路如下：DC在抗原信號池采集信號和抗原，當DC內(nèi)∑csm達到遷移閾值時，將∑mat與∑semi的差值當作分數(shù)評分給DC所采集的每一個抗原。為此為每一個抗原記下兩個數(shù)據(jù)：評分次數(shù)和累計得分，當評分次數(shù)達到一個閾值N，計算該抗原的平均得分，即將累計得分／N作為抗原的MCAV，反映抗原的異常程度。也就是說，評分制DCA中DC不再為抗原投票，而是評分，也不存在DC的狀態(tài)轉(zhuǎn)換機制，最后根據(jù)得分情況確定分數(shù)線（即異常閾值）來調(diào)控檢測結(jié)果的誤報率和漏報率。

Table 6 Detecton results of the improved DC state transition rule表6 改進的DC狀態(tài)轉(zhuǎn)換準則的檢測結(jié)果 %

5.2 評分制DCA的偽代碼

輸入：抗原和信號特征向量。

輸出：每個抗原的平均分。

初始化一個長度為m的抗原信號池；

將數(shù)據(jù)集前m項數(shù)據(jù)放入池中；

while（抗原未全被檢測完）

｛

初始化DC；

while（DC的∑csm＜遷移閾值MT）

｛

DC從抗原信號池中隨機采樣；

累計三個輸出值：∑csm、∑semi、∑mat；

｝

對于DC采樣的每一個抗原，評分次數(shù)加1，累計得分加上∑mat－∑semi的值；

處理評分次數(shù)達到N的抗原，平均分＝累計得分／

N，從抗原信號池中移除，加入新抗原；

｝

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

設(shè)置m＝20，N＝10，MT＝39，分別代入三種權(quán)值矩陣對順序3數(shù)據(jù)集（115條異常數(shù)據(jù)＋120條正常數(shù)據(jù)＋115條異常數(shù)據(jù)＋120條正常數(shù)據(jù)＋230條異常數(shù)據(jù)）進行實驗，效果如圖1～圖3所示，橫坐標是700個抗原的ID，縱坐標是每個抗原的平均分。

Figure 1 Experiment result using weight matrix 1of scoring DCA圖1 評分制DCA代入權(quán)值矩陣1的實驗結(jié)果

Figure 2 Experiment result using weight matrix 2of scoring DCA圖2 評分制DCA代入權(quán)值矩陣2的實驗結(jié)果

從三個實驗的效果圖可以看出：異常抗原的平均分主要分布在上部10～45，重心依次稍許下移；正常抗原的平均分主要分布在下部，重心依次明顯

Figure 3 Experiment result using weight matrix 3of scoring DCA圖3 評分制DCA代入權(quán)值矩陣3的實驗結(jié)果

表5中的數(shù)據(jù)是以權(quán)值矩陣2代入信號轉(zhuǎn)換公式（1）求得的正常、異常抗原的平均輸出值，根據(jù)公式（2）可求得異常抗原的平均分約為（7.42－0.59）＊39／8.6＝30.97；正常抗原的平均分約為（－3.85－6.69）＊39／9.53＝－43.13。

另外，分別以權(quán)值矩陣1和權(quán)值矩陣3計算得到的平均分匯總?cè)绫?所示。下移。這是因為在危險環(huán)境中，SS一般為0，主要是PAMP和DS對輸出信號產(chǎn)生影響，三種權(quán)值矩陣中PAMP和DS對輸出信號的影響權(quán)值是一樣的，所以對異常抗原的分值影響不大；在安全環(huán)境中，影響輸出信號的主要因素是SS，三種權(quán)值矩陣的不同正是SS對semi和mat的影響權(quán)重，并且依次加大對semi的正影響和對mat的負影響，導(dǎo)致正常抗原的平均分重心依次明顯下移。

根據(jù)抗原的平均輸出值計算同種抗原的平均分的公式如下所示：

Table 8 Estimated values of average scores of normal and abnormal antigens表8 正常、異常抗原的平均分估算值

表8中的值是根據(jù)抗原的平均輸出值計算得到的，實際抗原的分值會以此為基準上下波動，如圖1～圖3所示。

無論選用何種權(quán)值矩陣，都可將正常抗原和異常抗原劃分開來，混亂均發(fā)生在兩類環(huán)境交換的過渡階段，這是由于DC在采樣池中采樣了多個抗原和多套信號，在轉(zhuǎn)換邊界兩類數(shù)據(jù)的相互干擾所導(dǎo)致的。因此，只要根據(jù)正常抗原和異常抗原的分數(shù)分布選取合理的分數(shù)線（即異常閾值），便可靈活調(diào)控檢測結(jié)果的誤報率和漏報率。以圖3為例：正常抗原的最高分為－2.737，異常抗原的最低分為－42.533，選取中間值－21.127作為異常閾值，可達到99%的檢測精度，誤報率為0.571%，漏報率為0.429%。異常閾值向上調(diào)至－2.737可實現(xiàn)0誤報，向下調(diào)至－42.533可實現(xiàn)0漏報。當然這只是評分制DCA的一次實驗結(jié)果，算法中大量的隨機因素將導(dǎo)致不同的實驗結(jié)果，每次實驗的異常閾值上下值可調(diào)范圍雖不盡相同，但中間值差異不大。

根據(jù)抗原的平均輸出值計算中間值的公式如下：

其中，j＝0，1，0表示正常，1表示異常。

中間值可作為異常閾值的參考值，然后根據(jù)具體應(yīng)用調(diào)整異常閾值，可達到控制檢測結(jié)果的誤報率和漏報率的目的。

中間值也可表達為傾向因子的線性函數(shù)，融入傾向因子計算中間值的公式如下所示：

以權(quán)值矩陣2為例將表5中的數(shù)據(jù)代入公式（3）可得：

由于三種權(quán)值矩陣對異常抗原的影響并無太大差異，所以可將（mat1－semi1）當作一個常量，公式（3）可轉(zhuǎn)化為：

median＝n＊TF＋t，n＝4.09，t≈1.55

如此代入三種權(quán)值矩陣的傾向因子，計算中間值分別為5.108、－6.037、－20.945，和表8中的中間值基本吻合。

6 結(jié)束語

本文從DCA權(quán)值矩陣對檢測結(jié)果的影響入手，對信號的融合處理、DC的狀態(tài)轉(zhuǎn)化、抗原的綜合評價等機制進行了分析，設(shè)計了兩種可調(diào)控檢測結(jié)果的DCA：改進的投票制DCA將DC的狀態(tài)轉(zhuǎn)換準則作為調(diào)控機制；評分制DCA通過分數(shù)線的合理劃取調(diào)控誤報率和漏報率。但是，這只是對DCA這種涉及較多相互作用成分和參數(shù)的高度隨機算法進行分析和控制的初步研究，接下來的工作將繼續(xù)深挖相關(guān)參數(shù)對檢測結(jié)果的影響，進一步理解DCA的本質(zhì)，并且根據(jù)檢測結(jié)果進行反饋，動態(tài)調(diào)整參數(shù)，從而優(yōu)化算法。

［1］ 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，2006：404－417.

［2］ Oates R，Kendall G，Garibaldi J.Frequency analysis for dendritic cell population tuning［J］.Evolutionary Intelligence，2009，1（2）：145－157.

［3］ Greensmith J，Aickelin U.Artificial dendritic cells：Multi－faceted perspectives［M］.Berlin：Springer－Verlog，2009.

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

［5］ Twycross J.Integrated innate and adaptive artificial immune systems applied to process anomaly detection［D］.Nottingham：University of Nottingham，2007.

［6］ Ni Jian－cheng，Li Zhi－shu，Sun Ji－rong，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）

［7］ Yang Chen－xu，Wu Geng－feng，Hu Min.Improved dendritic cells algorithm［J］.Computer Engineering，2009，35（23）：194－200.（in Chinese）

［8］ Greensmith J，Aickelin U.The deterministic dendritic cell algorithm［C］∥Proc of the 7th International Conference on Artificial Immune Systems，2008：291－303.

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

［10］ Greensmith J，Aickelin U，Cayzer S.Detecting danger：The dendritic cell algorithm［M］∥Robust Intelligent Systems，London：Springer，2008：89－112.

［11］ Chen Yue－bing，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）

附中文參考文獻：

［6］ 倪建成，李志蜀，孫繼榮，等.樹突狀細胞分化模型在人工免疫系統(tǒng)中的應(yīng)用研究［J］.電子學(xué)報，2008，36（11）：2210－2215.

［7］ 楊晨旭，吳耿鋒，胡珉.一種改進的樹突狀細胞算法［J］.計算機工程，2009，35（23）：194－200.

［11］ 陳岳兵，馮超，張權(quán)，等.樹突狀細胞算法原理及其應(yīng)用［J］.計算機工程，2010，36（8）：173－176.