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

(閩江學(xué)院)

0 引言

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

1 陰性選擇算法及其分析

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

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

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

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

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

2 改進(jìn)模型E-NSA

2．1 模型定義

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

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

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

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

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

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

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

定義6 分類器融合，即利用第二層的強(qiáng)分類器h'，對第一層分類器的預(yù)測結(jié)果再進(jìn)行一次的預(yù)測分類，即分類器融合，描述如下所示:

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

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

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

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

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

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

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

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

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

3 仿真實驗

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

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

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

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

3．2 實驗結(jié)果及分析

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

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

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

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

圖2 黑洞覆蓋空間比較圖

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

4 結(jié)語

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

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

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

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

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

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

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