鄧澤林，譚冠政，何锫

1.長沙理工大學計算機與通信工程學院，長沙 410076

2.中南大學信息科學與工程學院，長沙 410083

3.廣州大學計算機科學與教育軟件學院，廣州 510006

改進的人工免疫識別系統(tǒng)及其性能分析

鄧澤林1，譚冠政2，何锫3

1.長沙理工大學計算機與通信工程學院，長沙 410076

2.中南大學信息科學與工程學院，長沙 410083

3.廣州大學計算機科學與教育軟件學院，廣州 510006

為了改善人工免疫識別系統(tǒng)的非線性能力,進一步優(yōu)化分類器性能，提出了一種改進的人工免疫識別系統(tǒng)。新算法采用混合核函數(shù)來提升算法的非線性能力，同時，對記憶細個體進行適應度評估，淘汰低適應度的細胞來優(yōu)化免疫分類器。改進的算法被應用于復雜UCI數(shù)據(jù)集的分類，分類結果與其他經典的分類算法的結果進行比較，結果顯示該算法具有更好的分類性能。

人工免疫識別系統(tǒng)；混合核函數(shù)；適應度；復雜數(shù)據(jù)

1 引言

人工免疫系統(tǒng)（Artificial Immune Systems，AIS）啟發(fā)于脊椎動物的免疫系統(tǒng)，遵從免疫系統(tǒng)功能、原理和模型[1]，其主要特點是學習和記憶[2]。由于具有強大的學習能力，AIS被廣泛應用于各種問題，如優(yōu)化[3-4]、聚類[5-6]、異常檢測[7-8]、圖像處理[9-10]等。

AIS具有眾多的理論和模型，目前的研究主要集中于免疫網絡、克隆選擇和陰性選擇這3種理論[11]?；谶@3種理論的算法被廣泛應用于不同的領域，尤其是機器學習中的分類問題。由于免疫網絡具有強大的學習能力，大多數(shù)分類器都是基于免疫網絡模型來設計的。不同的免疫網絡分類算法在分類表示機制上采用不同的方法，其中免疫網絡分類器（Artificial Immune Network Classifier，AINC）[12]采用固定數(shù)量B細胞來表示分類器，該分類器雖然在具有混合特征數(shù)據(jù)的分類中表現(xiàn)出良好的性能，但每個類采用單個B細胞來表示難以有效地表示比較復雜的問題。另一種表示方法采用不固定數(shù)量的B細胞來表示分類器，代表性的算法是人工免疫識別系統(tǒng)（Artificial Immune Recognition System，AIRS）[13]。AIRS是一個強大的免疫分類器，在與其他經典的分類算法，如支持向量機SVM、隨機森林等，比較時表現(xiàn)出強大的競爭能力。AIRS算法的主要問題有兩個：（1）AIRS中樣本之間的相似度通過兩者之間的Euclidean距離來量化，由于Euclidean距離是線性空間的測量方法，這使得算法的非線性能力受到限制。為了改善算法的非線性能力，文獻[14]提出使用核函數(shù)來改善免疫算法的非線性能力，核函數(shù)將輸入空間中非線性可分樣本映射至高維空間，使得樣本在高維空間中線性可分[15]。大量的研究只關注使用單一核函數(shù)的效果，這樣雖然利用了單個核函數(shù)的優(yōu)點，但不能同時發(fā)揮多個核函數(shù)的優(yōu)勢來更好地提高算法性能。（2）AIRS在刺激度計算時采用相對刺激度，這導致少數(shù)相對刺激度高的細胞可能距離訓練抗原距離較遠，不能很好地表示訓練樣本，從而造成樣本誤分。

針對AIRS算法的這兩個問題，本文提出了改進的方法。通過將多個核函數(shù)進行結合來構造新的混合核函數(shù)，這樣就可以同時利用多個核函數(shù)的優(yōu)勢。同時，對記憶細胞群體中的個體細胞進行適應度評估，通過剪切適應度低的細胞來優(yōu)化分類器。這個改進的算法記為KPAIRS，并將KPAIRS應用于復雜數(shù)據(jù)的分類，將得到的結果與AIRS、AINC和SVM等算法的結果進行比較來評估算法的性能。

2 KPAIRS算法

2.1 混合核函數(shù)

對于復雜的分類問題，樣本空間呈現(xiàn)非線性特征，使得樣本難以被有效地分類。對于非線性可分的數(shù)據(jù)，通過找到一個合適的映射函數(shù)φ將樣本映射至高維特征空間H，使得樣本在H中可以進行線性分類。設x，y∈X，X屬于Rn空間，非線性函數(shù)φ實現(xiàn)輸入空間X到高維特征空間H的映射，其中H屬于Rm，n＜m。

定義1對于輸入空間中的向量x，y∈X，核函數(shù)K定義為[15]：

這里＜·＞表示內積。式（1）說明輸入樣本x和y在高維特征空間中的內積可以通過核函數(shù)計算得到，而不需要知道具體的φ映射或者是H的維數(shù)，從而避免了高維特征空間中的“維數(shù)災難”等問題。

在核函數(shù)應用時，同時使用多個核函數(shù)可以利用多個核函數(shù)的優(yōu)點，相比于使用單一核函數(shù)來說能更好地發(fā)揮核函數(shù)的優(yōu)勢，進一步改善算法性能。文獻中介紹了多種核函數(shù)，本文采用兩個核函數(shù)，即高斯徑向基核函數(shù)和逆多元二次核函數(shù)[14]來構造混合核函數(shù)：

（1）高斯徑向基核函數(shù)（Radial Basis Function，RBF）

（2）逆多元二次核函數(shù)（Inverse M ultiquadratic Kernel Function，IMKF）

選擇這兩個核函數(shù)構造混合核函數(shù)的原因有兩個：

（1）這兩個核函數(shù)都只有一個參數(shù)，方便搜索到優(yōu)化的參數(shù)。

（2）這兩個核函數(shù)都可以通過x，y的歐氏距離計算得到，方便算法的實現(xiàn)。

將RBF核函數(shù)與IMKF核函數(shù)進行組合，得到如下混合核函數(shù)，其中θ是加權系數(shù)。

通過引入核函數(shù)，輸入空間被映射至高維核空間，此時，輸入空間中的樣本x，y在核空間中的相似度D(x，y)可根據(jù)式（5）計算得到。

其中υ是用戶定義的系數(shù)用于控制D(x，y)≤1。此處定義υ=，可得輸入空間中樣本x，y在核空間中的相似度為：

顯然，通過使用混合核函數(shù)，樣本之間的相似度會根據(jù)參數(shù)的不同而有所不同，這必然會影響到分類決策，從而實現(xiàn)對分類決策的優(yōu)化。因此，引入多個核函數(shù)可以擴大算法的搜索空間，進一步優(yōu)化分類器性能。

2.2 細胞剪切

AIRS在計算抗體的刺激度時進行了歸一化處理，處理方法如式（7）所示。

其中，sb表示抗體b的真實刺激度，表示歸一化刺激度，smax表示抗體群體中刺激度的最大值，smin表示抗體群體中刺激度的最小值。

顯然，歸一化刺激度是一種相對刺激度，不能反映抗體與抗原之間真實的距離，可能導致算法確定的記憶細胞與訓練抗原的距離過遠而失去歸納能力，這將會降低分類器的預測能力，顯著影響分類器的分類性能。因此，需要對記憶細胞個體進行質量評估并淘汰識別能力較差的細胞。

定義2中M表示記憶細胞群體。根據(jù)定義2可知，抗原g被距離最近的細胞識別。如果cm=cg，則說明抗原g被記憶細胞m正確識別，否則，錯誤識別。其中cm和cg分別表示m與g的類別。

定義3記憶細胞m的正確識別鄰域為：

定義4記憶細胞m的錯誤識別鄰域為：

定義5記憶細胞m的適應度為：

計算每個記憶細胞的適應度，如果細胞fm＜γ，說明細胞m的適應度低于閾值，則從細胞群體M中刪除細胞m。其中γ是剪切閾值。

2.3 KPAIRS算法描述

記G表示抗原群體，B表示抗體群體，g∈G表示訓練抗原樣本，M表示記憶細胞群體。

步驟1初始化。歸一化數(shù)據(jù)集中所有樣本的屬性，使得任何兩個樣本的距離不大于1。親和度閾值f根據(jù)式（11）計算得到。

然后，隨機選擇若干抗原放入記憶細胞群體M中，并從G任意選擇一個抗原為當前訓練抗原g。

步驟2記憶細胞的發(fā)現(xiàn)和抗體的產生。根據(jù)式（13）找出與訓練抗原g刺激度最高的記憶細胞m。

記g與m的刺激度為s，按式（15）計算克隆細胞數(shù)量σ。

其中μ是超級克隆速率，λ是克隆速率。并以概率η來變異每個克隆體，克隆體放入B中。

步驟3競爭資源并形成候選記憶細胞。計算B中每個抗體b與g的刺激度，并按式（16）為每個抗體b分配資源。

步驟4記憶細胞的確定。確定與g刺激度最高的抗體b′，如果刺激度sm＜sb′，則把b′加入至M中成為記憶細胞。如果affinity(m，b′)＜δf，則執(zhí)行網絡抑制，刪除m，其中δ是親和度標量。

步驟5循環(huán)。選擇未訓練的抗原為訓練抗原g，從步驟2開始循環(huán)訓練。當抗原群體訓練完畢，跳至步驟6。

步驟6細胞剪切。計算每個細胞的適應度，如果細胞的適應度低于剪切閾值，則執(zhí)行細胞剪切。

步驟7分類。對于?t∈T，找出與之最近的k個記憶細胞，t的類別由這k個細胞投票決定。

3 實驗與討論

為了獲得更客觀的分類性能，分類結果采用10次交叉驗證（10-fold cross-validation）方法獲得。

3.1 數(shù)據(jù)集

用于測試的復雜數(shù)據(jù)集是German Credit Data（GC）、Australian Credit（AC）、Cleveland Heart Disease（CHD）和Hepatitis（HP），這4個數(shù)據(jù)集來自UCI。這4個數(shù)據(jù)集不僅包含連續(xù)屬性，還包含離散屬性、名義屬性，這些不同類型的屬性構成了復雜的具有混合特征的數(shù)據(jù)集，能很好地檢驗分類器的性能。數(shù)據(jù)集詳情見表1所示。

表1 數(shù)據(jù)集信息

3.2 參數(shù)設置

對于4個實驗數(shù)據(jù)集，KPAIRS在測試時設置了相應的參數(shù)，其中克隆速率λ、變異概率η、剪切閾值γ等參數(shù)設置相同，分別為10、0.1和0.5，其他重要的參數(shù)設置如表2所示。

表2 參數(shù)設置

3.3 核函數(shù)對分類性能的影響

為了比較不同的核函數(shù)對分類性能的影響，分類實驗使用了不同的核函數(shù)，得到的分類結果進行了比較，包括準確率、細胞數(shù)量和算法運行時間的比較，具體情況見表3所示。

表3 核函數(shù)對分類性能的影響

從表3可知，對于AC、GC、HP和CHD這4個問題，算法在采用混合核函數(shù)時達到了最高的分類準確率，而相應的細胞數(shù)量和運行時間只與使用單一核函數(shù)時存在微小的差異。表3的比較說明混合核函數(shù)能夠更有效地搜索優(yōu)化的分類器，因此，分類準確率有一定程度的提高。

3.4 分類性能比較

同時，KPAIRS與其他分類算法進行了比較，這些算法包括AIRS、SVM和AINC。比較結果見表4所示。其中AIRS和AINC對4個數(shù)據(jù)集的分類結果直接來自文獻[12]，SVM對AC和GC的分類結果來自文獻[16]，SVM對HP和CHD的分類結果通過運行Weka中的SMO算法得到，其中對HP分類時采用多項式核函數(shù)，關鍵參數(shù)是C=3.0，E=1.0；對CHD分類時采用RBF核函數(shù)，關鍵參數(shù)是C=1.0，G=0.07。

表4 分類算法準確率比較（%）

從表4的比較可知，采用混合核函數(shù)的免疫識別系統(tǒng)KPAIRS的性能顯著優(yōu)于采用線性表示機制的免疫識別系統(tǒng)AIRS；從AINC與KPAIRS的比較可知，KPAIRS對具有混合特征樣本的復雜問題具有更高的分類準確率；從KPAIRS與SVM的比較可知，相對于優(yōu)秀的分類器SVM而言，KPAIRS也表現(xiàn)出了相當?shù)母偁幠芰Α?/p>

4 結論

針對人工免疫系統(tǒng)AIRS的問題，提出了相應的改進方法。通過構造混合核函數(shù)來更好地改善算法的非線性能力，通過記憶細胞個體質量評估來淘汰適應度低的細胞，進一步優(yōu)化分類器。將改進的算法應用于GC、AC、HP和CHD這4個具有混合特征的復雜問題，比較使用不同核函數(shù)時算法的分類性能，結果表明算法在使用混合核函數(shù)時達到了最高的分類性能。同時，將改進的算法與AIRS、AINC和SVM分類器進行比較，結果表明改進的算法獲得了非常具有競爭力的分類結果，說明相應的改進策略很好地提升了算法的性能，使得KPAIRS成為一個非常具有潛力的分類器。

[1]Timmis J，Hone A，Stibor T，et al.Theoretical advances in artificial immune systems[J].Theoretical Computer Science，2008，403（1）：11-32.

[2]de Castro L N，Von Zuben F J.Learning and optimization using the clonal selection principle[J].IEEE Transactions on Evolutionary Computation，2002，6（3）：239-251.

[3]Li Zhonghua，Zhang Yunong，Tan Hongzhou.IA-AIS：an improved adaptive artificial immune system applied to complex optimization problems[J].Applied Soft Computing，2011，11（8）：4692-4700.

[4]趙云豐，付冬梅，尹怡欣，等.一種改進的人工免疫網絡優(yōu)化算法及其性能分析[J].自然科學進展，2009，19（4）：434-445.

[5]Graaff A J，Engelbrecht A P.Clustering data in an uncertain environment using an artificial immune system[J].Pattern Recognition Letters，2011，32（2）：342-351.

[6]陶新民，付丹丹，劉福榮，等.基于多尺度并行免疫克隆優(yōu)化聚類算法[J].控制與決策，2012，27（6）：819-825.

[7]Laurentys C A，Ronacher G，Palhares R M，et al.Design of an artificial immune system for fault detection：a negative selection approach[J].Expert Systems with Applications，2010，37（7）：5507-5513.

[8]Gong Tao，Cai Zixing.Normal model and BPNN-based immunization of anti-worm Web system[J].International Journal of Multimedia and Ubiquitous Engineering，2006，1（3）：23-26.

[9]Oguz F，Ismail B，Erkan U.A color image watermarking scheme based on artificial immune recognition system[J].Expert Systems with Applications，2011，38（3）：1942-1946.

[10]Konstantinos K D，Pantelis A A，George K M.Automatic point correspondence using an artificial immune system optimization technique for medical image registration[J].Computerized Medical Imaging and Graphics，2011，35（1）：31-41.

[11]Aydin I，Karakose M，Akin E.Artificial immune classifier with swarm learning[J].Engineering Applications of Artificial Intelligence，2010，23（8）：1291-1302.

[12]劉若辰，鈕滿春，焦李成.一種新的人工免疫網絡算法及其在復雜數(shù)據(jù)分類中的應用[J].電子與信息學報，2010，32（3）：515-521.

[13]Andrew B W.AIRS：a resource limited artificial immune classifier[D].Mississippi State：Department of Computer Science and Engineering，Mississippi State University，2001.

[14]Ozsen S，Gunes S，Kara S，et al.Use of kernel functions in artificial immune systems for the nonlinear classification problems[J].IEEE Transactions on Information Technology in Biomedicine，2009，13（4）：621-628. [15]Muller K R，Mika S，Ratsch G T，et al.An introduction to kernel-based learning algorithms[J].IEEE Trans on Neural Network，2001，12（2）：181-201.

[16]Chang S Y，Yeh T Y.An artificial immune classifier for credit scoring analysis[J].Applied Soft Computing，2012，12（2）：611-618.

DENG Zelin1,TAN Guanzheng2,HE Pei3

1.School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410076, China
2.School of Information Science and Engineering, Central South University, Changsha 410083, China
3.School of Computer Science and Educational Software, Guangzhou University, Guangzhou 510006, China

In order to improve the nonlinearity of Artificial Immune Recognition System（AIRS）and optimize the classifier,an improved AIRS algorithm is proposed. The new algorithm adopts hybrid kernel function to improve its nonlinearity,moreover, the individual memory cell is evaluated by its fitness score and the cells with low fitness scores are pruned to optimize the classifier. The improved algorithm has been applied to the complex UCI datasets classification, the results have been compared with the results achieved by other classic classifiers. The comparison shows that the algorithm achieves better classification performances.

artificial immune recognition system; hybrid kernel function; fitness score; complex data

DENG Zelin, TAN Guanzheng, HE Pei. Improved artificial immune recognition system and its performance analysis.Computer Engineering and Applications, 2014, 50（17）：16-19.

A

TP301

10.3778/j.issn.1002-8331.1402-0247

國家自然科學基金（No.61170199）；湖南省教育廳重點項目（No.11A 004）。

鄧澤林（1977—），男，工學博士，主要研究方向：人工免疫系統(tǒng)、模式識別；譚冠政（1962—），男，工學博士，教授，博士生導師，研究方向：智能機器人系統(tǒng)與控制、人工智能與認知系統(tǒng)；何锫（1963—），男，博士，教授，研究方向：軟件工程、人工智能。E-mail：zl_deng@sina.com

2014-02-24

2014-04-28

1002-8331（2014）17-0016-04

CNKI網絡優(yōu)先出版：2014-05-05,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0247.htm l