基于陰性選擇算法的改進(jìn)模型

傅龍?zhí)?，陳騰林

(1.福州外語(yǔ)外貿(mào)學(xué)院,福建 福州 350011；2.閩江學(xué)院，福建 福州 350011)

?

基于陰性選擇算法的改進(jìn)模型

傅龍?zhí)?，陳騰林2

(1.福州外語(yǔ)外貿(mào)學(xué)院,福建 福州 350011；2.閩江學(xué)院，福建 福州 350011)

人工免疫學(xué)中的陰性選擇算法是其核心算法，在各行業(yè)應(yīng)用廣泛。但其不足之處也越來(lái)越明顯，例如在訓(xùn)練樣本選擇方面、訓(xùn)練學(xué)習(xí)算法方面，都有可能影響檢測(cè)精度。訓(xùn)練學(xué)習(xí)算法中引入半監(jiān)督學(xué)習(xí)機(jī)制，并在樣本選擇上擴(kuò)展訓(xùn)練樣本來(lái)源，使訓(xùn)練學(xué)習(xí)更有針對(duì)性。仿真實(shí)驗(yàn)證明改進(jìn)后的模型能提高檢測(cè)率，并具備較強(qiáng)的自適應(yīng)能力。

陰性選擇算法；人工免疫；半監(jiān)督學(xué)習(xí)

1974年丹麥學(xué)者Jeme提出了第一個(gè)人工免疫數(shù)學(xué)模型[1]，后來(lái)Forrest等[2-3]提出了陰性選擇算法和計(jì)算機(jī)免疫學(xué)概念，Lee等[4-5]人通過(guò)從程序入口點(diǎn)開(kāi)始提取一系列字符串區(qū)分自體與非自體，以實(shí)現(xiàn)病毒檢測(cè)，推動(dòng)了計(jì)算機(jī)免疫系統(tǒng)的全面發(fā)展。雖然到目前為止陰性選擇算法在各領(lǐng)域解決了很多問(wèn)題，但算法本身仍然存在一些不足之處，例如訓(xùn)練成熟檢測(cè)器時(shí)，當(dāng)訓(xùn)練樣本(已知的自我集)比較少，即訓(xùn)練學(xué)習(xí)不夠充分，可直接影響檢測(cè)精度。只有在理想狀態(tài)下，隨機(jī)生成的未成熟檢測(cè)器，經(jīng)過(guò)自體耐受學(xué)習(xí)，經(jīng)歷淘汰后存活的成為成熟檢測(cè)器，并不斷迭代該過(guò)程，獲得足夠的成熟檢測(cè)器才能取得良好的檢測(cè)效果。但在實(shí)際應(yīng)用中是不現(xiàn)實(shí)的，用于訓(xùn)練學(xué)習(xí)的樣本往往很少，并且有標(biāo)記的更少或較為昂貴，這就導(dǎo)致陰性選擇算法的誤檢、漏檢現(xiàn)象。

目前，Watkins和Timmis[6]對(duì)人工免疫算法進(jìn)行了并行性改造，增強(qiáng)了算法的并行能力；舒才良等[7]提出了在數(shù)據(jù)不完備情況下的改進(jìn)算法，引入了分類(lèi)器融合投票決策思想；翟宏群等[8]利用模糊思想，采用最優(yōu)搜索原理有效地減低了黑洞數(shù)量；伍海波[9]通過(guò)改進(jìn)成熟檢測(cè)器的生成機(jī)制及改變匹配閥值，來(lái)解決成熟檢測(cè)器生成效率低和容易產(chǎn)生黑洞問(wèn)題。上述學(xué)者的各種改進(jìn)措施都起到了一定的效果，但未考慮訓(xùn)練樣本較少的情況下如何提高檢測(cè)率問(wèn)題，為了解決該問(wèn)題本文在自體耐受學(xué)習(xí)過(guò)程中引入半監(jiān)督學(xué)習(xí)算法，通過(guò)少量已標(biāo)記的樣本和若干未標(biāo)記樣本的學(xué)習(xí)，提高檢測(cè)精度。

1　陰性選擇算法及其分析

自然界大部分生物存在天然的免疫機(jī)制，當(dāng)生物體第一次遭遇抗原時(shí)將發(fā)生初次應(yīng)答，生物體通過(guò)學(xué)習(xí)，完成自體耐受過(guò)程，產(chǎn)生免疫記憶；當(dāng)?shù)诙卧庥鱿嗤乖瓡r(shí)激發(fā)二次應(yīng)答，識(shí)別該抗原[10]。計(jì)算機(jī)領(lǐng)域借鑒該免疫機(jī)制形成了人工免疫識(shí)別系統(tǒng)(AIRS)，陰性選擇算法是其核心算法之一，算法描述如下：

步驟1：初始化訓(xùn)練樣本，未成熟檢測(cè)器由系統(tǒng)隨機(jī)生成，然后與自體集匹配，如果匹配成功則淘汰，存活則加入成熟檢測(cè)器。

步驟2：重復(fù)迭代步驟1，直到生成足夠的成熟檢測(cè)器。

步驟3：利用成熟檢測(cè)器集檢測(cè)待檢樣本，如果匹配成功，則識(shí)別成功。

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

2.1模型定義

陰性選擇算法的訓(xùn)練樣本來(lái)源于隨機(jī)生成的數(shù)據(jù)，大量的非自體集合數(shù)據(jù)未參與訓(xùn)練。半監(jiān)督學(xué)習(xí)是利用未標(biāo)記數(shù)據(jù)的一種主流學(xué)習(xí)技術(shù)，它能夠在不加外界干預(yù)的情況下，自動(dòng)地利用少量已標(biāo)記數(shù)據(jù)和大量未標(biāo)記數(shù)據(jù)進(jìn)行學(xué)習(xí)[11-12]。本文引入自體集和非自體集作為訓(xùn)練樣本，使訓(xùn)練樣本來(lái)源更具代表性。把少量的自體集定義為已標(biāo)記(Labeled)集合，若干非自體抗原定義為未標(biāo)記(Unlabeled)集合。利用這兩種集合進(jìn)行訓(xùn)練學(xué)習(xí)。其形式化定義如下所示：

定義1：設(shè)已標(biāo)記集合為L(zhǎng)、未標(biāo)記集合為U，描述如下：

其中:對(duì)于已標(biāo)記樣本，yi為xi的標(biāo)記。L為已標(biāo)記樣本數(shù)，n為所有樣本數(shù)。

定義2:相似度(Similarity)矩陣，定義一個(gè)n×n的矩陣W，用于計(jì)算任意兩個(gè)樣本之間的相似度，描述如下：

(1)

定義3：設(shè)概率轉(zhuǎn)移(ProbabilityTransition)矩陣T為n×n的矩陣，用于計(jì)算xj到xi的概率，然后歸一化(Row-normalized)，其中k表示累計(jì)求和的下標(biāo)變量，描述如下：

(2)

(3)

(4)

(5)

定義5:傳播公式，通過(guò)T和Y相乘，迭代多次后，如果Y矩陣中第i列值接近1，則可把xj劃歸為ci分類(lèi)，加入到已標(biāo)記集合中。描述如式(6)所示，其中t表示迭代指數(shù)，Y為第t次迭代結(jié)果。

(6)

定義6：檢測(cè)函數(shù)采用陰性選擇算法原有的匹配規(guī)則，即r連續(xù)位(r-contiguousbits)匹配規(guī)則。成熟檢測(cè)器與非自體抗原匹配操作描述如下：

(7)

式中：Ag表示非自體抗原，fmatch(L,Ag,r)表示r連續(xù)位匹配函數(shù)，r表示匹配閥值。當(dāng)fdetect(L,Ag)返回1時(shí)表示檢測(cè)器識(shí)別了該抗原。

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

本模型涉及兩個(gè)算法：訓(xùn)練學(xué)習(xí)算法和檢測(cè)算法。訓(xùn)練學(xué)習(xí)過(guò)程引入半監(jiān)督學(xué)習(xí)機(jī)制，把訓(xùn)練樣本分成已標(biāo)記(自體集)和未標(biāo)記樣本(非自體抗原)，通過(guò)學(xué)習(xí)訓(xùn)練，產(chǎn)生成熟檢測(cè)器，然后利用r連續(xù)位匹配函數(shù)實(shí)現(xiàn)樣本檢測(cè)。

2.2.1訓(xùn)練學(xué)習(xí)算法

半監(jiān)督學(xué)習(xí)算法包括多種學(xué)習(xí)算法，本文采用基于圖(graph-based)的半監(jiān)督學(xué)習(xí)。利用已標(biāo)記和未標(biāo)記的樣本構(gòu)造圖(graph)，邊緣(edges)表示結(jié)點(diǎn)的相似度，已標(biāo)記結(jié)點(diǎn)根據(jù)相似度來(lái)傳播，并標(biāo)記所有未標(biāo)記的結(jié)點(diǎn)。為實(shí)現(xiàn)該過(guò)程，先定義相似度矩陣(見(jiàn)式(1))，經(jīng)過(guò)一序列的變換處理操作(見(jiàn)式(2)～式(5))，最后根據(jù)傳播公式(見(jiàn)式(6))得到成熟檢測(cè)器。其算法描述(偽代碼描述)如下：

輸入：已標(biāo)記集合和未標(biāo)記集合

輸出：成熟檢測(cè)器

Procedure TrainOperation ()

Begin

BuildGraph(); //根據(jù)已標(biāo)記集合L和未標(biāo)記集合U構(gòu)造圖

ComputeSimilarityValue()；//根據(jù)式(1)計(jì)算相似度

ComputeProbability(); //根據(jù)式(2)計(jì)算概率

RowNormalized(); //根據(jù)式(3)歸一化

BuildVertices(); //根據(jù)式(4)、式(5)構(gòu)造矩陣Y，用于初始化頂點(diǎn)

Propagate(); //根據(jù)式(6)循環(huán)迭代，生成成熟檢測(cè)器

Output(); //返回成熟檢測(cè)器

End;

2.2.2檢測(cè)算法

從訓(xùn)練學(xué)習(xí)算法獲得了足夠的成熟檢測(cè)器后，可對(duì)外來(lái)非自體抗原進(jìn)行檢測(cè)。檢測(cè)算法采用原陰性選擇算法的匹配規(guī)則，即r連續(xù)位(r-contiguousbits)匹配規(guī)則。預(yù)先設(shè)置匹配閥值r，r的值大一些匹配精度較高，但樣本檢測(cè)時(shí)容易出現(xiàn)漏檢現(xiàn)象，在實(shí)際應(yīng)用中可根據(jù)需要設(shè)定，其偽代碼描述如下：

輸入：非自體抗原和成熟檢測(cè)器集

輸出：被識(shí)別的抗原

Procedure Detection()

Begin

Flag = 0; //定義是否識(shí)別的標(biāo)記

While 循環(huán)變量 do //在成熟檢測(cè)器中循環(huán)匹配

{

If(Detect()) //根據(jù)式(7)進(jìn)行匹配。

Flag = 1; //如果非自體抗原與成熟檢測(cè)器匹配，則標(biāo)記變成1

}

If(Flag == 1)

Output(); //返回已識(shí)別的抗原

End;

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

為了驗(yàn)證本模型的性能，本文設(shè)計(jì)了一個(gè)模擬仿真實(shí)驗(yàn)，以收集的真實(shí)實(shí)驗(yàn)數(shù)據(jù)為基礎(chǔ)，并與陰性選擇算法進(jìn)行對(duì)比，來(lái)分析E-AIRS模型的性能。

3.1實(shí)驗(yàn)環(huán)境

使用IBM服務(wù)器X3650M4 7915i31作為實(shí)驗(yàn)機(jī)，主要配置：CPU為Intel至強(qiáng)E5-2600，內(nèi)存4 GB，500 GB硬盤(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)[13]，從中選取500個(gè)病毒樣本，其中250個(gè)樣本包含其特征碼作為已標(biāo)記樣本集合，另250個(gè)樣本不包含特征碼作為未標(biāo)記樣本集合；300個(gè)正常程序樣本作為自體集合；從已標(biāo)記樣本集合隨機(jī)抽取150個(gè)樣本，再?gòu)奈礃?biāo)記樣本集合隨機(jī)抽取150個(gè)樣本，共同組成300個(gè)非自體抗原集合。

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

為了得到真實(shí)可靠數(shù)據(jù)，進(jìn)行了兩組實(shí)驗(yàn)，每組實(shí)驗(yàn)進(jìn)行50次，取平均值。第一組實(shí)驗(yàn)隨機(jī)選取已標(biāo)記樣本40個(gè)，未標(biāo)記樣本160個(gè)，共200個(gè)訓(xùn)練樣本，即已標(biāo)記樣本占20%，實(shí)驗(yàn)得到的檢測(cè)率和誤檢率如圖1所示；第二組實(shí)驗(yàn)隨機(jī)選取已標(biāo)記樣本160個(gè)，未標(biāo)記樣本40個(gè)，共200個(gè)訓(xùn)練樣本，即已標(biāo)記樣本占80%，實(shí)驗(yàn)得到的檢測(cè)率和誤檢率如圖2所示。

從圖1(a)和圖2(a)可以看出,本文提出的E-AIRS模型在訓(xùn)練樣本比較少的情況下(兩組實(shí)驗(yàn)都只有200個(gè)訓(xùn)練樣本)比陰性選擇算法的檢測(cè)率更高，特別是在訓(xùn)練學(xué)習(xí)不夠充分時(shí)(即成熟檢測(cè)器較少)檢測(cè)率明顯更高，因?yàn)镋-AIRS模型引入半監(jiān)督學(xué)習(xí)算法，其分類(lèi)精度更高，并且在選擇訓(xùn)練樣本時(shí)引入了非自體抗原集中的數(shù)據(jù)(即未標(biāo)記樣本)，因此，訓(xùn)練樣本更具代表性；從圖1(a)和圖2(a)可看出兩條曲線(xiàn)之間的距離，圖1(a)的距離更大，例如：圖1(a)有100個(gè)成熟檢測(cè)器時(shí)檢測(cè)率分別是53%和72%，相差19%，而圖2(a)分別是72%和81%，相差9%，這說(shuō)明已標(biāo)記訓(xùn)練樣本較少時(shí)，E-AIRS模型相對(duì)陰性選擇算法的檢測(cè)效果更好。

從圖1(b)和圖2(b)可以看出，E-AIRS模型相對(duì)陰性選擇算法誤檢率較低一些，而E-AIRS模型只改進(jìn)了訓(xùn)練學(xué)習(xí)過(guò)程，未修改檢測(cè)操作的匹配規(guī)則，所以E-AIRS模型誤檢率低說(shuō)明其訓(xùn)練學(xué)習(xí)過(guò)程更有效；圖1(b)和圖2(b)的兩曲線(xiàn)之間的距離是圖1(b)較大，說(shuō)明在已標(biāo)記訓(xùn)練樣本較少時(shí)誤檢率更低，E-AIRS模型的優(yōu)勢(shì)更明顯。

圖1　已標(biāo)記樣本占20%的檢測(cè)率比較

圖2　已標(biāo)記樣本占80%的檢測(cè)率比較

4　結(jié)束語(yǔ)

本文針對(duì)陰性選擇算法的不足提出了一個(gè)改進(jìn)模型E-AIRS，該模型引入半監(jiān)督學(xué)習(xí)機(jī)制，擴(kuò)展了訓(xùn)練樣本來(lái)源，使訓(xùn)練樣本更具代表性，改善了訓(xùn)練學(xué)習(xí)過(guò)程。通過(guò)仿真實(shí)驗(yàn)證明E-AIRS模型相對(duì)于陰性選擇算法，在已標(biāo)記樣本較少的情況下檢測(cè)精度較高，并且誤檢率較低；另外，本模型對(duì)訓(xùn)練樣本的要求較低(只需要少量的已標(biāo)記樣本)，更貼近現(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,et al.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,HUYHN 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.ac.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]周志華.基于分歧的半監(jiān)督學(xué)習(xí)[J].自動(dòng)化學(xué)報(bào),2013,30(11):123-129.

[12]年素磊,黎銘,杜科,等.基于主動(dòng)半監(jiān)督學(xué)習(xí)的智能電網(wǎng)信調(diào)日志分類(lèi)[J].計(jì)算機(jī)科學(xué),2012,39(12):167-170.

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

[責(zé)任編輯：郝麗英]

The improved model based on negative selection algorithmFU Longtian1,CHEN Tenglin2

Artificial immunology loyalty is the core algorithm of negative selection algorithm,which has been widely applied to various industries.But its deficiency is becoming more and more noticeable,such as the training sample selection and learning algorithm are likely to influence the accuracy of detection.Learning algorithm is introduced in this paper as a semi-supervised learning mechanism,of which the training sample source in the sample selection is expanded to make the training more targeted.Simulation experiment proves that the improved model can improve the detection rate,and have strong adaptive capacity.Key words：negative selection algorithm; artificial immune; semi-supervised learning

10.19352/j.cnki.issn1671-4679.2016.05.014

2016-05-16

傅龍?zhí)?1976-)，男，講師，研究方向：信息安全.

TP301.6

A

1671-4679(2016)05-0050-04

(1.Fuzhou College of International Studies and Trade,Fuzhou 350011,China;2.Minjiang University,Fuzhou 350011,China)