采用奇異值分解和信息增益的樹突狀細胞模型

楊信民，董紅斌，譚成予，周 雯

1.武漢大學 國家網(wǎng)絡安全學院，武漢 430072

2.武漢大學 計算機學院，武漢 430072

人工免疫系統(tǒng)是模擬人體免疫系統(tǒng)工作機理的計算機免疫系統(tǒng)[1]，包括反向選擇、危險理論、克隆選擇、免疫網(wǎng)絡等理論分支[2]，由于繼承了免疫系統(tǒng)的生物智能特性，人工免疫系統(tǒng)被廣泛應用于機器學習[3]、優(yōu)化計算[4]、入侵檢測[5]、異常檢測[6]、故障檢測[7]等領域。最新的免疫學理論稱為危險理論（Danger Theory，DT）[8]。根據(jù)DT 的思想，從樹突狀細胞（Dendritic Cell，DC）的行為特征中獲得的啟發(fā)導致了稱為DCA的免疫算法的發(fā)展[9]。

DCA是受生物危險理論啟發(fā)，模擬DC生物機制的人工免疫算法，用于對人體內(nèi)危險抗原的最初識別。但DCA 從本質(zhì)上還是屬于先天性免疫范疇，在設計之初就沒有過多的考慮適應性。在實際的應用中如何將輸入的特征映射到具體的信號特征，存在著嚴重依賴人工經(jīng)驗的問題，始終沒有一個統(tǒng)一的、一般性的方法，嚴重影響DCA的適應性。

SVD能將原數(shù)據(jù)集規(guī)約成最相關特征子集，且能最大限度地保留分類信息，減弱數(shù)據(jù)混亂給算法帶來的影響，然后根據(jù)IG得到最相關特征子集中的最相關特征，自適應地提取信號。根據(jù)以上特征，本文在DCA 的基礎上，結(jié)合SVD 和IG 的思想，改進了DCA 算法中數(shù)據(jù)預處理和信號選擇的部分，建立了一個基于SVD 和IG的樹突狀細胞模型——SIDCA，并將SIDCA 與經(jīng)典DCA，優(yōu)化版本的dDCA進行了比較。

1 相關工作

1.1 樹突狀細胞算法

1994年，生物免疫學家Matzinger提出了DT[8]，認為免疫系統(tǒng)是感知機體組織內(nèi)的潛在危險，所有引發(fā)危險的抗原才是免疫識別的對象，而那些沒有引發(fā)危險的抗原，免疫系統(tǒng)不會做出免疫反應。

DC 能夠?qū)Σ蓸拥降亩喾N生物信號進行融合、分析并轉(zhuǎn)換為輸出信號，然后根據(jù)輸出信號的濃度從機體組織遷移到淋巴系統(tǒng)中，將采集到的抗原信息提呈給淋巴細胞，以此激活淋巴細胞來處理潛在的危險。

借鑒DT的思想和DC的行為特征，Greensmith等人在2005 年提出了DC 的人工抗原提呈模型及DCA[9]。隨后，Greensmith 團隊針對原DCA 算法參數(shù)較多、隨機性太強的問題提出了dDCA[10]，簡化了算法中所使用的信號，使得算法參數(shù)可控。為了提高DCA 的可用性和通用性該團隊還提出了hDCA[11]，采用Haskell函數(shù)編程語言描述和規(guī)范DCA 算法。Gu 和Greensmith 提出了PCA-DCA[12]，采用PCA方法處理抗原數(shù)據(jù)，實現(xiàn)輸入信號的自動分類；Chelly 提出了基于粗糙集、模糊集的DCA 算法[13-14]，實現(xiàn)信號特征自動選取和分類，提高了DCA算法在信號定義上的自適應性。

DCA 已經(jīng)成功應用于諸多計算機安全相關的領域，解決了常見的異常檢測問題，包括端口掃描檢測[15]、僵尸網(wǎng)絡檢測[16]、機器人安全分類器[17]、ping 掃描檢測[18]、服務器攻擊檢測[19]、服務器異常檢測[20]、電網(wǎng)攻擊檢測[21]等；近年來也被應用于地震預測[22]、網(wǎng)絡水軍檢測[23]等領域。

1.2 奇異值分解

SVD 能夠用小得多的數(shù)據(jù)集來表示原始數(shù)據(jù)集，即可以將SVD看成是從噪聲數(shù)據(jù)中抽取相關特征。文獻[24]用SVD 降維提高了反向傳播神經(jīng)網(wǎng)絡用于文件分類的性能。在文獻[25]中，提出了基于奇異值分解的特征選擇算法，并將算法與11 個常用特征選擇算法在統(tǒng)一的評判標準下進行對比，結(jié)果顯示，奇異值分解可以用于特征選擇算法并有很高的精確度。

SVD定義為：

其中，M是一個m×n階矩陣，U是m×m階酉矩陣，U的列組成一套對M正交“輸入”或“分析”的基向量，這些向量是MMT的特征向量；VT是V的共軛轉(zhuǎn)置，是n×n階酉矩陣，V的列（columns）組成一套對M的正交“輸出”的基向量，這些向量是MTM的特征向量；Σ是半正定m×n階對角矩陣，其對角線上的元素即為M的奇異值。

在之前研究中，DCA 錯誤的分類常發(fā)生在過渡邊界。因此，當環(huán)境連續(xù)多次變化時DCA 會產(chǎn)生更多錯誤。SIDCA 采用SVD 產(chǎn)生相關子集，減弱數(shù)據(jù)混亂帶來的影響。

1.3 信息增益

香農(nóng)在1948 年提出了“信息熵”的概念，它具有量化信息的能力[26]。設X是一個取有限值的離散型隨機變量，概率分布為：

則隨機變量X的熵為：

設有隨機變量(X,Y)，其聯(lián)合概率分布為P(X=xi,Y=yj)=pij,i=1,2,…,n,j=1,2,…,m。

條件熵（conditionalentropy）H(Y|X)表示隨機變量X的條件下隨機變量Y的不確定性。

基于以上對信息熵的理解，出現(xiàn)了信息增益的概念[27]。設特征A對訓練集D的信息增益為g(D,A)，則：

信息增益可以視為某個特征帶給整個系統(tǒng)的信息量。在DCA 中，不同信號對算法最終分類結(jié)果的影響比重不同。借助信息增益，能夠根據(jù)不同信號對分類結(jié)果影響程度的不同，自適應地去提取信號。

2 基于奇異值分解的樹突狀細胞模型

2.1 模型框架

該模型共有四個模塊：基于奇異值分解的數(shù)據(jù)預處理模塊、基于奇異值分解和信息增益的信號選擇模塊、信號處理模塊和分類模塊。圖1 展示了基于奇異值分解的樹突狀細胞模型。

圖1 改進的樹突狀細胞模型Fig.1 Improved dendritic cell model

模型從實際應用環(huán)境中獲得所有特征建立原始抗原庫，采用奇異值分解對數(shù)據(jù)進行降噪處理，并對特征進行降維操作，將所有特征映射到樹突狀細胞算法所需要的維度中。

接著，對降維后的數(shù)據(jù)集進行信號選擇，采用基于信息增益的方法自適應地提取病原體相關模式分子信號（Pathogen-Associated Molecular Patterns，PAMP）、危險信號（Danger Signal，DS）以及安全信號（Safe Signal，SS）。當樹突狀細胞成熟時，通過累積輸出信號濃度來確定抗原環(huán)境。

在最后的分類模塊，通過每次累積的數(shù)據(jù)，計算環(huán)境評估的度量值MCAV，來確定當前的抗原環(huán)境是正常還是異常。

2.2 算法流程

2.2.1 數(shù)據(jù)預處理階段

在數(shù)據(jù)預處理階段的主要目的是將數(shù)據(jù)集（假設數(shù)據(jù)集已經(jīng)將非數(shù)值型處理為數(shù)值型）降噪和降維，并使算法處理過的數(shù)據(jù)集能正確地被信號選擇階段的算法接收和處理。數(shù)據(jù)預處理算法的偽代碼如下所示：

算法1數(shù)據(jù)預處理算法

一般數(shù)據(jù)集可視為一個二維矩陣。假設將目標數(shù)據(jù)集視為矩陣M，M為m×n階矩陣。設矩陣M任意位置的值為vali,j，每列屬性最大值為max，最小值為min，此階段矩陣由以下公式進行標準化：

再由奇異值分解的定義：

奇異值分解去除噪聲的一個典型的做法是保留矩陣中90%的信息，為了計算信息總量，將Σm×n中所有的奇異值求其平方和，即：

初始化K為2，若前K個奇異值累加不足信息總量的90%，則將K值加1，直到將奇異值的平方和累加到總值的90%為止。此時得到了保留信息總量90%的去除噪聲的數(shù)據(jù)集，即：

原矩陣的密集總結(jié)矩陣T為原矩陣描述性數(shù)據(jù)子集，定義為：

2.2.2 信號選擇階段

用公式（3）對矩陣T進行數(shù)據(jù)標準化，接下來將整個矩陣T視為數(shù)據(jù)集D，|D|為數(shù)據(jù)集的樣本容量。設有K個類Ck，k=1,2,…,K，|Ck|為屬于類Ck的樣本個數(shù)。設數(shù)據(jù)集D的某個特征A有n個不同的取值{a1,a2,…,an}，將D劃分為n個子集D1,D2,…,Dn，|Di|為Di的樣本個數(shù)。記子集Di中屬于類Ck的樣本集合為Dik，|Dik|為Dik的樣本個數(shù)。

計算數(shù)據(jù)集D的經(jīng)驗熵H(D)：

根據(jù)公式（4）計算信息增益g(D,A)。最后根據(jù)信息增益將特征從大到小進行排序得到排序后的矩陣T′，求得信息增益最大特征列的均值mean。

算法2信號選擇算法

其中pamp、ds、ss分別代表PAMP、DS、SS。

2.2.3 信號處理階段

信號處理階段算法接收上一階段得到的各種信號，并輸出成熟信號（Mature Signal，mat）、半成熟信號（Semi-Mature Signal，semi）以及協(xié)同刺激分子信號（Co-Stimulatory Molecules，CSM）。CSM通過DC的遷移閾值（migration threshold）來判斷iDC 向半成熟或成熟狀態(tài)分化，若累積的CSM大于DC 的遷移閾值則iDC 開始分化。設遷移閾值為mThreshold，信號處理算法的偽代碼如下所示：

算法3信號處理算法

算法實現(xiàn)過程中，關鍵步驟是采集抗原的PAMP、SS和DS通過權(quán)值矩陣來進行信號融合生成CSM、semi和mat輸出信號。權(quán)值矩陣如表1所示。

表1 權(quán)值矩陣的各項參數(shù)Table 1 Parameters of weight matrix

權(quán)值矩陣是多次實驗后得出的經(jīng)驗參數(shù)，具體實現(xiàn)過程中可針對不同用途定義為不同值。信號處理公式如下：

Wp、Ws、Wd分別代表PAMP、SS、DS 對應的權(quán)值，IC為炎癥細胞因子（Inflammatory Cytokines，IC），其功能是用來放大其他信號，本實驗中暫未用到這一信號。

2.2.4 分類階段

分類階段算法對DC 遷移之后進行累積輸出信號評估，設Am為此抗原被標記為成熟的次數(shù)，As表示此抗原被標記為半成熟的次數(shù)。分類階段的偽代碼如下所示：

算法4分類階段算法

樹突狀細胞算法根據(jù)成熟環(huán)境抗原值（Mature Context AntigenValue，MCAV）來確定抗原的異常程度，MCAV的計算方式如下：

當MCAV大于指定的異常閾值時，則表示此抗原為異常，反之則此抗原為正常。MCAV的閾值一般為數(shù)據(jù)集中異?？乖瓕嶋H所占比值。

3 實驗與分析

3.1 實驗設計

進行實驗的兩個數(shù)據(jù)集為：（1）UCI Wisconsin Breast Cancer dataset（WBC），由700 個數(shù)據(jù)實例組成，每個實例有9個標準化屬性，代表潛在癌細胞的各種特征。第10個屬性為類1或類2的分類標簽。此數(shù)據(jù)集按種類排序，為有序數(shù)據(jù)集。（2）KDD99的一個子集，每個實例有32 個標準化屬性，第33 個屬性為分類標簽。由于DCA對大型數(shù)據(jù)集的處理過程過于緩慢，本文所使用的是原數(shù)據(jù)集按照比例隨機抽取的5 000條數(shù)據(jù)。此數(shù)據(jù)集經(jīng)過多次隨機打亂，為無序數(shù)據(jù)集。

在所有對比實驗中DC 總數(shù)都被設置為100，在每次循環(huán)中對10個DC取樣。

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

3.2.1 評價指標說明

本實驗所使用的模型評價指標如表2所示。

表2 實驗評價指標Table 2 Experimental evaluation indicators

3.2.2 在有序數(shù)據(jù)集上的實驗

在有序數(shù)據(jù)集WBC 上，SIDCA 在真正類率、召回率、特異度、AUC、AVG和準確率均高于其他兩種算法；真負類率略低于dDCA 算法，但高于DCA；SIDCA 有更低的漏報率；算法耗時SIDCA 與DCA 相近，遠低于dDCA。從AUC 以及ACC 對比圖可以更明確地看出，本文提出的SIDCA 不僅能夠自適應地提取信號，在有序數(shù)據(jù)集上比進行對比的兩種算法有更好的表現(xiàn)。實驗結(jié)果如表3～表5和圖2、圖3所示。

表3 WBC數(shù)據(jù)集10次實驗結(jié)果平均值對比Table 3 Comparison of average effects of 10 executions in WBC dataset %

表4 WBC數(shù)據(jù)集50次實驗結(jié)果平均值對比Table 4 Comparison of average effects of 50 executions in WBC dataset %

表5 WBC數(shù)據(jù)集100次實驗結(jié)果平均值對比Table 5 Comparison of average effects of 100 executions in WBC dataset %

圖2 在WBC數(shù)據(jù)集100次實驗AUC對比圖Fig.2 Comparison of AUC values of 100 executions in WBC dataset

圖3 在WBC數(shù)據(jù)集100次實驗ACC對比圖Fig.3 Comparison of ACC values of 100 executions in WBC dataset

3.2.3 在無序數(shù)據(jù)集上的實驗

在KDD99 數(shù)據(jù)集上，SIDCA 在真正類率、真負類率、召回率、馬修斯相關系數(shù)、AUC、AVG和準確率上均強于DCA 和dDCA；在特異度上SIDCA 略低于dDCA，但高于DCA；SIDCA有更低的漏報率；算法耗時SIDCA略高于DCA，遠低于dDCA。從AUC 以及ACC 對比圖可以更明確地看出，本文提出的SIDCA 不僅能夠自適應地提取信號，在無序數(shù)據(jù)集上也有比進行對比的兩種算法有更好的表現(xiàn)。實驗結(jié)果如表6～表8 和圖4、圖5所示。

圖4 在KDD99數(shù)據(jù)集100次實驗AUC對比圖Fig.4 Comparison of AUC values of 100 executions in KDD99 dataset

圖5 在KDD99數(shù)據(jù)集100次實驗ACC對比圖Fig.5 Comparison of ACC values of 100 executions in KDD99 dataset

表6 KDD99數(shù)據(jù)集10次實驗結(jié)果平均值對比Table 6 Comparison of average effects of 10 executions in KDD99 dataset %

表7 KDD99數(shù)據(jù)集50次實驗結(jié)果平均值對比Table 7 Comparison of average effects of 50 executions in KDD99 dataset %

表8 KDD99數(shù)據(jù)集100次實驗結(jié)果平均值對比Table 8 Comparison of average effects of 100 executions in KDD99 dataset

4 結(jié)束語

本文提出了基于奇異值分解的樹突狀細胞模型，該算法結(jié)合奇異值分解以及均方誤差和信息增益，使得信號提取的過程不再需要人工經(jīng)驗，能夠自適應地提取PAMP、DS以及SS。實驗表明，不論是有序數(shù)據(jù)集還是無序數(shù)據(jù)集，本文提出的SIDCA 有效地提高了算法的精確度，減少了誤報率，且受數(shù)據(jù)順序的影響更小。

受到DCA 本身對無序數(shù)據(jù)處理能力不強、且DCA和SVD 均只適合于微型和小型數(shù)據(jù)集的制約，SIDCA在無序數(shù)據(jù)集和大型數(shù)據(jù)集的表現(xiàn)還不夠優(yōu)秀，下一步的研究目標是繼續(xù)提高該算法在無序數(shù)據(jù)集上的精確度，采用并行算法提高該算法在大型數(shù)據(jù)集上的運算效率。進一步降低算法中的其他參數(shù)對人工經(jīng)驗的依賴，提高算法的普適性。并將SIDCA運用在計算機安全或疾病預測等領域。