一種優(yōu)化黑洞覆蓋的陰性選擇算法*

傅龍?zhí)?，?戈，陳滕林

(閩江學院)

0 引言

丹麥學者Jeme［1］在1974年提出了一個人工免疫模型，F(xiàn)orrest等［2-3］后來提出了陰性選擇算法和計算機免疫學概念，從此推動了計算機免疫學的全面發(fā)展，例如Lee等［4-5］學者利用免疫學原理實現(xiàn)計算機病毒檢測．雖然人工免疫原理在各個領域獲得很大的成功，但本身仍然存在一些不足之處，例如自體耐受過程在初始階段學習不充分，匹配規(guī)則采用固定閥值導致黑洞問題等．Watkins和 Timmis［6］對陰性選擇算法(Negative Selection Algorithm)進行了并行性改造，增強了算法的并行能力;舒才良等［7］提出了在數(shù)據(jù)不完備情況下的改進算法，引入了分類器融合投票決策思想;翟宏群等［8］利用模糊思想，采用最優(yōu)搜索原理對降低黑洞數(shù)量起了一定的作用;伍海波［9］通過改進成熟檢測器的生成機制及改變匹配閥值，來解決成熟檢測器生成效率低和容易產(chǎn)生黑洞問題．上述學者的各種改進措施都起到了一定的效果，但多數(shù)只考慮了問題局部，未做全局考慮，例如黑洞的產(chǎn)生根源不只是匹配閥值的問題，還和訓練樣本來源有關系．該文首先擴展訓練樣本來源;其次在自體耐受學習中過程引入集成學習中的Stacking算法;匹配規(guī)則調(diào)整為可變閥值．通過三個方面的改進來提高檢測精度，優(yōu)化黑洞覆蓋空間．

1 陰性選擇算法及其分析

自然界的生物經(jīng)過進化大部分形成了天然的免疫機制，當抗原第一次入侵免疫系統(tǒng)時，生物體產(chǎn)生應激反應作出第一次應答，并學習完成自體耐受過程，產(chǎn)生免疫記憶;當抗原再次入侵時激發(fā)二次應答，識別該抗原［10］．這種學習防御機制引入計算機領域后，形成了人工免疫識別系統(tǒng)(AIRS)，陰性選擇算法是其核心算法之一，算法描述如下:

步驟1:從系統(tǒng)自動隨機生成初始化訓練樣本，形成初始的未成熟檢測器，當未成熟檢測器與自體集中的樣本匹配，如果匹配成功則淘汰，否則存活，形成若干成熟檢測器．

步驟2:經(jīng)過步驟1的多次重復迭代，生成數(shù)量足夠的成熟檢測器．

步驟3:利用步驟2獲得的成熟檢測器檢測待檢樣本，采用r-連續(xù)位匹配規(guī)則檢測待檢樣本，如果匹配成功，則認為識別了該待檢樣本．

陰性選擇算法從誕生到現(xiàn)在成功地應用到了各行各業(yè)，取得了良好的效果，但也暴露出了其不足之處，主要表現(xiàn)在三個方面:首先訓練樣本較少時生成的成熟檢測器也較少，這對檢測精度有很大的影響，只有在成熟檢測器越來越多的情況下，檢測精度才令人滿意;其次未成熟檢測器的來源是隨機生成的，訓練樣本不夠典型，代表性不強，這樣將不可避免地產(chǎn)生黑洞;再次陰性選擇算法采用r-連續(xù)位(r-contiguousbits)匹配規(guī)則，匹配閥值固定不變，這也是產(chǎn)生黑洞的重要原因．該文針對陰性選擇算法的不足提出一個改進模型E-NSA，即在訓練學習過程引入集成學習(Ensemble Learning)算法的Stacking算法，改善自體耐受學習過程;擴展訓練樣本來源，把非自體抗原加入到訓練樣本中，使訓練樣本更具代表性;把原算法的固定匹配閥值改成閥值可變，使得匹配過程更靈活，降低黑洞數(shù)量．

2 改進模型E-NSA

2．1 模型定義

Stacking算法分為兩層［11］，第一層首先構造多個弱分類器，產(chǎn)生一個與原數(shù)據(jù)集大小相同的新數(shù)據(jù)集，用這個新數(shù)據(jù)集和一個新算法構成第二層的強分類器，然后融合．該文把自體集和非自體集作為訓練樣本，其形式化定義如下所示:

定義1 訓練樣本數(shù)據(jù)集D(其中包含了自體集和非自體抗原集中的數(shù)據(jù)樣本)，作為多分類器融合算法的輸入，描述如下所示:

D={(x(1)，y(1))，(x(2)，y(2))，…，(x(N)，y(N)}其中N為樣本的數(shù)量

定義2 構造Stacking算法的第一層弱分類器h1，表示第t個不同的分類器，用于對訓練樣本數(shù)據(jù)集D進行預測分類．其中Lt函數(shù)表示通過訓練樣本集D的學習得到第t個分類器ht，描述如下所示:

定義3 構造矩陣Zit為Nxt的矩陣，用于計算樣本x(i)對于分類器ht的分類結果，該結果可以是樣本x(i)屬于分類ht的概率，描述如下所示:

定義4 構造一個新數(shù)據(jù)集D'，通過定義3的循環(huán)迭代計算，可獲得樣本x(i)對于分類器ht的預測結果，數(shù)據(jù)集D'用于記錄預測結果，描述如下所示:

定義5 構造Stacking算法的第二層強分類器h'，即利用數(shù)據(jù)集D'形成新的分類器，用于融合弱分類器的預測結果，描述如下所示:

定義6 分類器融合，即利用第二層的強分類器h'，對第一層分類器的預測結果再進行一次的預測分類，即分類器融合，描述如下所示:

定義7 匹配度，設I是長度為L的二進制字符，P和Q是長度相等的二進制字符串，描述如下所示:

其中MatchRate(P，Q)表示P和Q的匹配程度，Len(Pi，Qj)表示P在Q上相應位置上匹配的長度，Len(P)表示字符串 P的長度，當MatchRate(P，Q)的值為1是，表示P和Q完全相等，即完全匹配．

定義8 連續(xù)匹配度con_MatchRate(P，Q)，函數(shù)max(Len(Pi，Qj))表示字符串P在字符串Q上相應位置連續(xù)匹配的最大長度，描述如下所示:

定義9 字符匹配函數(shù)，Match(P，Q)表示兩字符串P和Q的匹配操作函數(shù)，其中r表示匹配閥值，描述如下所示:

當匹配函數(shù)Match(P，Q)為1時表示兩個字符串匹配，在匹配操作過程中，匹配閥值r是可變的，當連續(xù)匹配度大于r/len(P)時，調(diào)整ri=ri-1+1．

2．2 模型算法實現(xiàn)

該模型由學習訓練算法和匹配算法組成，學習算法引入Stacking算法用于改善耐受過程;匹配算法目的在于調(diào)整匹配閥值，實現(xiàn)靈活匹配降低黑洞數(shù)量．

學習訓練算法是陰性選擇算法的重要組成部分，首先把自體集合非自體抗原集作為訓練樣本，根據(jù)式(1)循環(huán)t次構造分類器(弱分類器)，利用式(2)循環(huán)計算概率矩陣，即計算樣本x(i)的分類結果;然后把分類結果構造成新的數(shù)據(jù)集D'，并構造新的分類器(強分類器);最后根據(jù)式(5)利用新構造的分類器進行融合，從而得到熟檢測器．

匹配算法采用自適應模糊策略，首先根據(jù)式(6)(7)計算匹配度和連續(xù)匹配度;再根據(jù)式(8)判斷是否匹配．在實際應用中，出現(xiàn)連續(xù)匹配時(即循環(huán)執(zhí)行本算法)，匹配閥值可自動調(diào)整，即當連續(xù)匹配度大于r/len(P)時，匹配閥值調(diào)整為ri=ri-1+1．

3 仿真實驗

為了驗證本模型的有效性，該文做了兩組實驗用于比較陰性選擇算法和E-NSA模型的性能，并分析實驗現(xiàn)象．

3．1 實驗環(huán)境

使用IBM服務器X3650M4 7915i31作為實驗機，主要配置:CPU為Intel至強E5-2600，內(nèi)存 8GB，500GB硬盤，操作系統(tǒng)為 Microsoft Windows2003，云平臺使用 Google Compute Engine，開發(fā)工具為Visual Studio2010．為了保證實驗機純凈環(huán)境，除操作系統(tǒng)自帶軟件外，不再安裝其他軟件．

該文選取美國哥倫比亞大學的數(shù)據(jù)測試集(2D Synthetic Data)［12］，從中選取 2000 個病毒樣本作為非自體抗原集合，1500個正常程序樣本作為自體集合．從自體集合隨機選取500個樣本，從非自體抗原集合隨機抽取500個樣本，共同組成訓練樣本集合;從病毒樣本中隨機選取1500個，再從正常程序樣本中隨機選取1000個作為待檢測樣本集合．

3．2 實驗結果及分析

為了得到真實可靠數(shù)據(jù)，進行了兩組實驗，每組實驗進行50次，取平均值．第一組實驗從訓練樣本集合中隨機選取200個樣本，用于比較陰性選擇算法和E-NSA模型的檢測率和誤檢率，實驗結果如圖1所示．

從圖1(a)可以看出該文提出的E-NSA模型相對陰性選擇算法檢測率更高，特別是在成熟檢測器數(shù)量較少時檢測率的差距較大．因為ENSA模型引入了Stacking算法，改善了學習過程，并且訓練樣本加入了非自體抗原，使得訓練樣本更具有代表性，提高了檢測精度陰性選擇算法的斜率，隨著成熟檢測器數(shù)量增加斜率減小程度越來越少，說明成熟檢測器的數(shù)量對檢測精度的影響很大，而E-NSA模型的檢測精度對成熟檢測器的數(shù)量的依賴明顯更小，因為其斜率變化較小．從圖1(b)可以看出E-NSA模型的誤檢率也相對低的多．

圖1 檢測率和誤檢率比較圖

第二組實驗從訓練樣本集合中隨機選取200個樣本，用于比較陰性選擇算法和E-NSA模型的黑洞數(shù)量，實驗結果如圖2所示．

圖2 黑洞覆蓋空間比較圖

從圖2可以看出E-NSA模型相對陰性選擇算法黑洞覆蓋空間更高一些，這是因為E-NSA模型采用了可變匹配閥值，在獲得成熟檢測器和樣本檢測這個兩個過程中都有明顯的優(yōu)勢;另外E-NSA模型擴展了學習訓練樣本，生成的成熟檢測器更具代表性，黑洞覆蓋空間自然也更高．

4 結語

針對性陰性選擇算法的不足提出了一個改進模型 E-AIRS，該模型引入集成學習的Stacking算法;擴展了訓練樣本來源，使訓練樣本更具代表性，改善了訓練學習過程;采用可變匹配閥值，使得黑洞覆蓋空間明顯提高．通過仿真實驗證明E-AIRS模型相對于陰性選擇算法，具備檢測精度較高、誤檢率較低、黑洞覆蓋空間更高的優(yōu)勢;另外本模型對訓練樣本的要求較低(把自體集和非自體抗原集作為訓練樣本)更貼近現(xiàn)實，增加了進一步應用推廣的可能性．

［1］ Aydin I，Karakose M ，Akin E．An adaptive artificial immune system for fault classification ［J］．Journal of Intelligent Manufacturing，2012，23(5):1489-1499．

［2］ Chang S Y，Yeh T Y．An artificial immune classifier for credit scoring analysis［J］．Applied Soft Computing，2012，12(2):611-618．

［3］ Nicholas，W．，Pradeep，R．，Greg S．，Lundy，L．Artificial immune systems for the detection of credit card fraud:an architecture，prototype and preliminary results［J］．Information Systems Journal，2012，22(1):53-76．

［4］ Binh L N，Huynh T L，Pang K K．Combating Mobile Spam through Botnet Detection using Artificial Immune Systems［J］．Journal ofUniversal Computer Science，2012，18(6):750-774．

［5］ Samigulina G A．Development of decision support systems based on intellectual technology of artificial immune systems［J］．Automation and Remote Control，2012，73(2):397-403．

［6］ Watkins A，Timmis J．Exploiting parallelism inherent in AIRS，an artificial immune classifier ［EB/0L］． (2012)［2012-01］．http://www．cs．kent．a(chǎn)c．uk/?abw5/．

［7］ 舒才良，嚴宣輝，曾慶盛．不完備數(shù)據(jù)下的免疫分類算法［J］．計算機工程與應用，2012，48(20):172-176．

［8］ 翟宏群，馮茂巖．一種改進的變閾值陰性選擇免疫算法［J］．南京師范大學學報:工程技術版，2011，11(3):78-82．

［9］ 伍海波．一種改進的否定選擇算法在入侵檢測中的應用［J］．計算機應用與軟件，2013，30(2):174-176．

［10］郭蓉，姜童子，黃葵．Aβ3-10s基因疫苗免疫AD小鼠誘導Th2型免疫反應的研究［J］．中風與神經(jīng)疾病雜志，2013，30(5):112-118．

［11］ 侯勇，鄭雪峰．集成學習算法的研究與應用［J］．計算機工程與應用，2012，48(34):17-22．

［12］ 程春玲，柴倩，徐小龍，熊婧夷．基于免疫協(xié)作的P2P網(wǎng)絡病毒檢測模型［J］．計算機科學，2011，38(10):60-63．