傅龍?zhí)欤愹v林

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

?

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

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

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

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

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

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

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

1　陰性選擇算法及其分析

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

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

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

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

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

2.1模型定義

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

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

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

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

(1)

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

(2)

(3)

(4)

(5)

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

(6)

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

(7)

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

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

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

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é)點的相似度，已標(biāo)記結(jié)點根據(jù)相似度來傳播，并標(biāo)記所有未標(biāo)記的結(jié)點。為實現(xiàn)該過程，先定義相似度矩陣(見式(1))，經(jīng)過一序列的變換處理操作(見式(2)～式(5))，最后根據(jù)傳播公式(見式(6))得到成熟檢測器。其算法描述(偽代碼描述)如下：

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

輸出：成熟檢測器

Procedure TrainOperation ()

Begin

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

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

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

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

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

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

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

End;

2.2.2檢測算法

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

輸入：非自體抗原和成熟檢測器集

輸出：被識別的抗原

Procedure Detection()

Begin

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

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

{

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

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

}

If(Flag == 1)

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

End;

3　仿真實驗

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

3.1實驗環(huán)境

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

本文選取美國哥倫比亞大學(xué)的數(shù)據(jù)測試集(2D Synthetic Data)[13]，從中選取500個病毒樣本，其中250個樣本包含其特征碼作為已標(biāo)記樣本集合，另250個樣本不包含特征碼作為未標(biāo)記樣本集合；300個正常程序樣本作為自體集合；從已標(biāo)記樣本集合隨機(jī)抽取150個樣本，再從未標(biāo)記樣本集合隨機(jī)抽取150個樣本，共同組成300個非自體抗原集合。

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

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

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

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

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

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

4　結(jié)束語

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

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

[13]程春玲,柴倩,徐小龍,熊婧夷.基于免疫協(xié)作的P2P網(wǎng)絡(luò)病毒檢測模型[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)