傅龍?zhí)?，陳騰林

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

?

基于陰性選擇算法的改進模型

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

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

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

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

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

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

1　陰性選擇算法及其分析

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

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

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

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

2　改進模型E-AIRS

2.1模型定義

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

定義1：設已標記集合為L、未標記集合為U，描述如下：

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

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

(1)

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

(2)

(3)

(4)

(5)

定義5:傳播公式，通過T和Y相乘，迭代多次后，如果Y矩陣中第i列值接近1，則可把xj劃歸為ci分類，加入到已標記集合中。描述如式(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表示匹配閥值。當fdetect(L,Ag)返回1時表示檢測器識別了該抗原。

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

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

2.2.1訓練學習算法

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

輸入：已標記集合和未標記集合

輸出：成熟檢測器

Procedure TrainOperation ()

Begin

BuildGraph(); //根據(jù)已標記集合L和未標記集合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檢測算法

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

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

輸出：被識別的抗原

Procedure Detection()

Begin

Flag = 0; //定義是否識別的標記

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

{

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

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

}

If(Flag == 1)

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

End;

3　仿真實驗

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

3.1實驗環(huán)境

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

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

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

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

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

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

圖1　已標記樣本占20%的檢測率比較

圖2　已標記樣本占80%的檢測率比較

4　結(jié)束語

本文針對陰性選擇算法的不足提出了一個改進模型E-AIRS，該模型引入半監(jiān)督學習機制，擴展了訓練樣本來源，使訓練樣本更具代表性，改善了訓練學習過程。通過仿真實驗證明E-AIRS模型相對于陰性選擇算法，在已標記樣本較少的情況下檢測精度較高，并且誤檢率較低；另外，本模型對訓練樣本的要求較低(只需要少量的已標記樣本)，更貼近現(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,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]舒才良,嚴宣輝,曾慶盛.不完備數(shù)據(jù)下的免疫分類算法[J].計算機工程與應用,2012,48(20):172-176.

[8]翟宏群,馮茂巖.一種改進的變閾值陰性選擇免疫算法[J].南京師范大學學報(工程技術(shù)版),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]周志華.基于分歧的半監(jiān)督學習[J].自動化學報,2013,30(11):123-129.

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

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

[責任編輯：郝麗英]

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)