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

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

(閩江學(xué)院)

0 引言

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

1 陰性選擇算法及其分析

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

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

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

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

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

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

2．1 模型定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

3．1 實(shí)驗(yàn)環(huán)境

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

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

3．2 實(shí)驗(yàn)結(jié)果及分析

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

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

圖1 檢測(cè)率和誤檢率比較圖

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

圖2 黑洞覆蓋空間比較圖

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

4 結(jié)語(yǔ)

針對(duì)性陰性選擇算法的不足提出了一個(gè)改進(jìn)模型 E-AIRS，該模型引入集成學(xué)習(xí)的Stacking算法;擴(kuò)展了訓(xùn)練樣本來(lái)源，使訓(xùn)練樣本更具代表性，改善了訓(xùn)練學(xué)習(xí)過(guò)程;采用可變匹配閥值，使得黑洞覆蓋空間明顯提高．通過(guò)仿真實(shí)驗(yàn)證明E-AIRS模型相對(duì)于陰性選擇算法，具備檢測(cè)精度較高、誤檢率較低、黑洞覆蓋空間更高的優(yōu)勢(shì);另外本模型對(duì)訓(xùn)練樣本的要求較低(把自體集和非自體抗原集作為訓(xùn)練樣本)更貼近現(xiàn)實(shí)，增加了進(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ù)下的免疫分類(lèi)算法［J］．計(jì)算機(jī)工程與應(yīng)用，2012，48(20):172-176．

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

［9］ 伍海波．一種改進(jìn)的否定選擇算法在入侵檢測(cè)中的應(yīng)用［J］．計(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ì)算機(jī)工程與應(yīng)用，2012，48(34):17-22．

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