鄧澤林譚冠政何 锫李 峰

①（長沙理工大學計算機與通信工程學院 長沙 410076）

②（中南大學信息科學與工程學院 長沙 410083）

③（廣州大學計算機科學與教育軟件學院 廣州 510006）

一種基于動態(tài)識別鄰域的免疫網(wǎng)絡分類算法及其性能分析

鄧澤林*①譚冠政②何 锫③李 峰①

①（長沙理工大學計算機與通信工程學院 長沙 410076）

②（中南大學信息科學與工程學院 長沙 410083）

③（廣州大學計算機科學與教育軟件學院 廣州 510006）

針對傳統(tǒng)免疫網(wǎng)絡分類算法在記憶細胞確定上缺乏有效的指導，該文提出一種基于動態(tài)識別鄰域的免疫網(wǎng)絡分類算法。算法采用核函數(shù)表示機制來描述抗體-抗原之間的親和度；利用抗原對構(gòu)造動態(tài)識別鄰域來指導抗體群體的進化，并選擇鄰域中距離對偶抗原最近的抗體為記憶細胞。算法被應用于多分類問題及高維分類問題來進行算法性能分析，同時，算法被應用于多個標準數(shù)據(jù)集的分類來評估算法的整體性能。分類結(jié)果表明該算法對于標準測試數(shù)據(jù)集有良好的分類性能，這說明基于動態(tài)識別鄰域的訓練方法能夠有效地指導記憶細胞的生成，顯著地改善分類器的性能。

人工智能；人工免疫系統(tǒng)；免疫網(wǎng)絡；抗原對；動態(tài)識別鄰域

1 引言

人工免疫系統(tǒng) （Artificial Immune Systems，A IS）在過去的十多年間得到了長足的發(fā)展，成為一門比較成熟的軟計算技術(shù)。A IS啟發(fā)于自然免疫理論，遵從免疫原理和模型，適用于問題求解［1］。AIS強大的信息處理能力被成功應用于各種復雜問題的求解。文獻［2］提出基于A IS的學習算法進行字符的識別、函數(shù)優(yōu)化以及組合優(yōu)化問題的求解；文獻［3，4］提出使用免疫算法來求解混合多目標優(yōu)化問題；文獻［5］提出構(gòu)建免疫分類器來分析保險行業(yè)數(shù)據(jù)，該分類器利用多層免疫系統(tǒng)來創(chuàng)建和存儲抗體群體，并利用遺傳算法對抗體的學習過程進行優(yōu)化；文獻［6］提出用于銀行業(yè)數(shù)據(jù)分析的免疫分類器；文獻［7］提出利用決策超平面信息來指導記憶細胞的生成，構(gòu)建高效的免疫分類器；文獻［8］提出用于SAR圖像分割的AIS算法，算法基于高斯核聚類指數(shù)來搜索SAR圖像的優(yōu)化分割，并使用直方圖統(tǒng)計來加速SAR圖像的分割；文獻［9］利用A IS和多目標優(yōu)化算法進行SAR圖像的改變檢測；文獻［10］提出基于協(xié)同策略的模糊A IS來防御無線感知網(wǎng)絡中的阻斷服務攻擊。

AIS主要包括人工免疫網(wǎng)絡、克隆選擇和陰性選擇這3個理論和模型，這些理論和模型適用于分類問題求解。人工免疫網(wǎng)絡是通過訓練抗體群體并確定少數(shù)記憶細胞來表示較大訓練空間的一種方法，因此，免疫網(wǎng)絡是否有效地歸納抗原空間對于改善分類性能是至關(guān)重要的。文獻［11］提出人工免疫網(wǎng)絡分類器 （Artificial Immune Network Classifier，A INC）。 在AINC中，每個類用單個B細胞表示，這樣細胞群體中就不存在冗余的B細胞，節(jié)省了計算時間并降低了網(wǎng)絡復雜度。然而，每個類采用單個B細胞的表示機制難以有效地表示復雜的問題。文獻［12］ 提出了基于局部特征選擇的免疫分類算法（Artificial Immune System w ith Local Feature Selection， AISLFS）。A ISLFS 通過局部特征選擇有效地進行了局部維數(shù)壓縮，顯著地降低分類所需的數(shù)據(jù)量。文獻［13］ 提出了基于抗原對的免疫網(wǎng)絡分類算法（Pair w ise antigens based Immune Network Classifier， PINC）。PINC利用抗原對指導抗體群體進化，使得記憶細胞能夠靠近類域分界線，從而具備較好的預測能力。但PINC中抗體群體的進化缺乏優(yōu)化機制，難以有效地進行記憶細胞群體的搜索。文獻［14］基于免疫網(wǎng)絡和模因算法（Memetic algorithm）提出了混合算法（Modified op t-aiNet w ith Local Search Strategy of Mem etic A lgorithm，M op t-aiNetLS）。文獻［15］進行了克隆選擇學習能力的研究，提出了基于克隆選擇的精簡免疫系統(tǒng)分類算法（Simp le A IS， SA IS）。在SAIS中，整個分類器用一個B細胞表示，在B細胞中為每個類別維持固定數(shù)量的抗體，這樣就不需要進行抗體群體規(guī)?？刂?。其主要問題是算法缺乏跳出局部最優(yōu)點的機制，使得算法難以搜索到全局優(yōu)化的分類器。文獻［16］在SAIS模型的基礎(chǔ)上提出基于粒群智能的免疫分類器（A rtificial Immune Classifier w ith Swarm Learning， AICSL）。在AICSL中，抗體通過粒群智能的指導在抗原空間中移動，搜索最優(yōu)化的抗體群體組合。目前，使用陰性選擇原理來設計分類器的研究很少，主要的研究是陰性選擇分類器（Artificial Negative Selection Classifier， ANSC）［17］。ANSC由人工淋巴細胞組成，這些細胞通過訓練來完全覆蓋訓練空間。顯然，完全覆蓋訓練空間是一件非常耗時的工作。

通過分析已有分類器的問題，本文發(fā)現(xiàn)高效的抗體群體進化特別是有指導的記憶細胞生成策略對于改善免疫分類器的性能是非常重要的，為此，提出了一種基于動態(tài)識別鄰域的分類算法。算法的性能通過對標準數(shù)據(jù)集的分類測試結(jié)果來進行評估，并與其他著名分類器進行對比以顯示算法的性能。

2 算法關(guān)鍵技術(shù)

記樣本，x=［x1， x2，…， xl］其中l(wèi)表示樣本的屬性數(shù)量，樣本中每個屬性為實數(shù)編碼。算法中，抗體與抗原的編碼方式與樣本x的編碼方式相同。所有樣本構(gòu)成數(shù)據(jù)集S。對于?x∈ S，按式（1）進行屬性歸一化處理。

其中yi和zi分別表示S中所有樣本第i個屬性的最小值和最大值。

2.1 親和度計算及免疫操作

2.1.1 親和度計算 親和度是用于量化抗體-抗原之間相互作用力的表示方法。一般的親和度量化機制是采用抗體與抗原之間的歐式（Euclid）距離來表示的，其問題在于Euclid距離是線性空間表示方法，這不僅影響了算法的非線性能力，而且對于不同的問題，抗體-抗原的親和度僅由兩點坐標決定，不能根據(jù)不同問題進行親和度優(yōu)化來對免疫進化過程產(chǎn)生積極的影響。為此，引入基于徑向基核函數(shù)（Radial Basis Function， RBF）的距離測量方法，如式（2）所示。

從式（3）可知，通過優(yōu)化核參數(shù)c可以實現(xiàn)對抗體-抗原之間親和度的優(yōu)化，從而對后續(xù)免疫操作施以積極的影響。

2.1.2 免疫操作 人工免疫系統(tǒng)的主要操作包括克隆、變異。對于訓練抗原g，計算抗體群體B中每個抗體b與g的親和度?？寺〔僮髦忻總€抗體b應克隆的數(shù)量為

其中參數(shù)α表示克隆速率，fb表示抗體b與訓練抗原的親和度值，round（·）表示四舍五入取整。

抗體b被克隆Nb個后代抗體，每個后代抗體在克隆的過程中根據(jù)式（5）進行變異操作。其中 b（t）表示進化過程中的第t代抗體。

2.2 基于動態(tài)識別鄰域的訓練方法

2.2.1 動態(tài)識別鄰域的構(gòu)建與記憶細胞的確定 免疫分類器由記憶細胞群體組成，群體中靠近類域分界線的細胞對分類器的性能有顯著的影響，因此，搜索類域分界線附近的優(yōu)良細胞對于改善分類器性能是至關(guān)重要的。為此，算法需要知道類域分界線位置并在其附近產(chǎn)生記憶細胞。對于訓練抗原g，確定距離g最近的不同類別的抗原g'為其對偶抗原，g與g'稱為抗原對。顯然，類域分界線存在于抗原對之間的位置。

定義1 記識別訓練抗原g的抗體群體構(gòu)成g的動態(tài)識別鄰域H（ g）， H（ g）根據(jù)式（6）確定。

其中θ為鄰域控制因子。顯然，對于不同的訓練抗原，其動態(tài)識別鄰域的大小是不同的，因此，H（ g）是一種范圍可變的識別鄰域。圖1是一個動態(tài)識別鄰域示例，其中以g為中心、r為半徑的圓標示了該鄰域的最大范圍。

H（ g）中任意抗體細胞都能識別抗原g，在進化的過程中，當H（ g）中出現(xiàn)抗體細胞時，抗原g即可被識別，此時，根據(jù)式（7）來確定記憶細胞m。

圖1 動態(tài)識別鄰域示

在圖1所示的動態(tài)識別鄰域H（ g）中，抗體細胞m被確定為抗原g的記憶細胞。顯然，m是H（ g）中距離分界線最近的抗體細胞。

參數(shù)θ是一個優(yōu)化參數(shù)，它能通過控制動態(tài)識別鄰域大小來實現(xiàn)對記憶細胞質(zhì)量的優(yōu)化，以圖2、圖3所示情形來說明，其中θ1＞θ2。

圖2中g(shù)與g'互為對偶抗原，g'的記憶細胞為m1。當θ較大時，抗體群體能快速進入H（ g），但抗體群體經(jīng)歷克隆、變異的次數(shù)少，容易導致記憶細胞離分界線較遠，如圖2中的記憶細胞m2。因為m1和m2與分界線的距離差別較大，當使用它們進行分類時比較容易造成誤分。而當θ取值較小時，抗體群體難以快速進入H（ g），因此，抗體群體需要在g的附近進行較多的克隆、變異操作，導致識別鄰域H（ g）中存在較多的抗體細胞，如圖3所示。

此時，在H（ g）中可能獲得更靠近分界線的記憶細胞m3，比較易知m3的質(zhì)量高于m2的質(zhì)量。由此可知，通過優(yōu)化參數(shù)θ可以搜索類域分界線附近的優(yōu)良記憶細胞群體，實現(xiàn)對分類器的優(yōu)化。

圖2 較大的動態(tài)識別鄰域

圖3 較小的動態(tài)識別鄰域

3 算法描述

參數(shù)：抗體群體大小s， 選擇抗體數(shù)量σ， 克隆速率α， 重新選擇系數(shù)ξ， k近鄰，核函數(shù)參數(shù)c，網(wǎng)絡抑制因子β，鄰域控制因子θ。

步驟1 初始化。讀取數(shù)據(jù)集S，歸一化樣本屬性。初始化M=φ，加載訓練集至G中，T= S- G為測試集。隨機產(chǎn)生s個抗體來初始化抗體群體B。

步驟2 循環(huán)。如果所有抗原訓練完畢，跳至步驟3執(zhí)行分類，否則選擇一個抗原為當前訓練抗原g按如下步驟訓練。

（a）抗體選擇。對于?b∈ B，其與g的親和度依式（3）計算得到。從集合B中選出與g同類且親和度最高的σ個抗體形成臨時集合P。如果P=φ，置M= M∪｛ g｝，B= B∪｛ g｝，跳至步驟2繼續(xù)訓練。

（b）克隆與變異。對于?b∈ P，其克隆數(shù)量根據(jù)式（4）得到。將克隆體全部放入集合P中。對于每個克隆體，根據(jù)式（5）進行變異。

（c）記憶細胞的確定及網(wǎng)絡抑制。定義空集Q，找出g的對偶抗原g'，并構(gòu)造H（ g）。如果?b∈ P且b∈ H（ g），置Q= Q∪｛ b｝。 如果Q≠φ，據(jù)式（7）確定記憶細胞并進行網(wǎng)絡抑制，然后跳至步驟2繼續(xù)訓練。

（d）抗體重新選擇。選擇P中ξ%個親和度最高的抗體放入B，并隨機產(chǎn)生s個抗體放入B中。跳至步驟（a）繼續(xù)訓練。

步驟3 分類。對于任意測試樣本t∈ T， 使用M進行k近鄰分類。當所有測試樣本分類完畢，即可得到分類準確率。

4 實驗與討論

本文實驗使用的數(shù)據(jù)集都來自UCI（Irvine machine learning repository of California University）機器學習數(shù)據(jù)庫，這些數(shù)據(jù)集包括Iris，W ine， Sonar，威斯康星乳腺癌數(shù)據(jù)集（W isconsin Breast Cancer Dataset， WBCD）和Diabetes。本文所有實驗使用10折交叉驗證（10-fold crossvalidation）獲取分類結(jié)果。

4.1 多分類問題

選擇Iris來測試算法對多分類問題的分類性能。Iris共有150個樣本，3個類別，每個類別有50個樣本。Iris的3個類別分別是Setosa， Versicolor和V irginica。為了解免疫分類器中細胞群體的空間分布特征，對Iris全集進行分類訓練，關(guān)鍵參數(shù)設置為c=0.6， θ=0.93， α=13， k=3。抗原群體及記憶細胞群體采用3維點圖的形式輸出，繪圖時使用樣本集的3個屬性：花瓣寬度（petalw idth）、花瓣長度（petallength）和萼片寬度（sepalw idth），這些屬性值通過屬性歸一化后成為［0， 1］之間的標量。Iris的抗原群體及記憶細胞群體分布特征如圖4所示。

同時，對Iris進行10折交叉驗證，10次獨立分類運算將Iris中的每個樣本分類測試1次。最終150個樣本中有149個樣本被正確分類，分類準確率為99.33%，標準差為2.0。

4.2 高維數(shù)據(jù)集

為了評估算法對高維數(shù)據(jù)集的分類性能，選擇60維數(shù)據(jù)集Sonar來測試算法的分類性能。Sonar是一個2分類問題，兩個類別分別記為R和M。評價2分類問題分類性能的標準除了分類準確率外，還廣泛使用敏感度（Sen）和特異性（Spe），它們可以分別依據(jù)式（8）和式（9）計算得到。

其中，TP， FP， TN和FN分別表示真陽性樣本數(shù)量、假陽性樣本數(shù)量、真陰性樣本數(shù)量和假陰性樣本數(shù)量［18］。

實驗時主要參數(shù)設置：c=1.7， θ=0.93， α=21，k=1。對Sonar 的分類混淆矩陣如表1所示。

表1 對Sonar分類得到的混淆矩陣

由此可得敏感度和特異性：分類準確率為90.38%。由此可知，算法不僅獲得了較高的分類準確率，而且敏感度和特異性數(shù)值比較接近，說明算法為陽性樣本和陰性樣本進行了較為均衡的分類。

圖4 Iris的訓練抗原群體及記憶細胞群體的空間分布特征

4.3 算法整體性能評估

4.3.1 與免疫網(wǎng)絡分類器的比較 免疫網(wǎng)絡分類算法性能比較見表2，其中參與比較的分類算法為A INC［11］、A ISLFS［12］、PINC［13］和M op t-aiNetLS［14］。

表2 與免疫網(wǎng)絡分類算法的比較（%）

4.3.2 與其他免疫原理分類器的比較 算法與克隆選擇分類算法A ICSL［16］和陰性選擇分類算法ANSC［17］進行了比較，結(jié)果見表3。

表3 與克隆選擇分類器和陰性選擇分類器的比較（%）

4.3.3 與其他分類器的比較 同時，將本文算法與k近鄰分類算法（k-Nearest Neighbor， KNN）、隨機森林算法（Random Forest， RF）和支持向量機（Support Vector Machine， SVM）進行比較。比較結(jié)果如表4所示，參與比較的算法獲得的分類準確率來自文獻［12］。

表4 與其他分類器性能比較（%）

4.4 參數(shù)敏感性分析

本文算法中，對分類性能有重要影響的參數(shù)包括RBF函數(shù)參數(shù)c和鄰域控制因子θ。

圖5顯示了參數(shù)c對分類性能的影響。從圖5可知，當c取值較小時，分類準確率有較大幅度的變化，這說明當c較小時，RBF核函數(shù)具有較強的非線性能力，使得算法能夠有效地搜索記憶細胞群體組合，最終搜索到優(yōu)化的分類器；而當c取值過大時，分類準確率之間僅存較小的差異，這說明當c過大時，RBF核函數(shù)的非線性能力減弱，算法表現(xiàn)出較強的線性特征而失去了優(yōu)化的能力。

同時，鄰域控制因子θ能夠有效地控制抗體動態(tài)識別鄰域的大小，從而影響最終分類器的質(zhì)量。本文實驗中參數(shù)θ的取值范圍在［0.90， 1.00］之間，θ與分類準確率之間的關(guān)系如圖6所示。

5 結(jié)束語

傳統(tǒng)的免疫分類算法在抗體群體進化和記憶細胞確定時缺乏有效的指導，影響了算法的性能。為了改善這一問題，本文提出了一種基于動態(tài)識別鄰域的免疫網(wǎng)絡分類算法。算法被應用于多分類問題，3維分布圖顯示了組成分類器的記憶細胞群體有效地歸納了抗原空間，從而獲得了很高的分類準確率；同時，算法被應用于高維問題的分類，混淆矩陣顯示算法不僅獲得了理想的分類準確率，而且算法為陰性樣本和陽性樣本進行了較為均衡的分類；最后，算法對多個數(shù)據(jù)集進行了分類，分類結(jié)果與其他著名的分類算法進行了廣泛的比較，結(jié)果顯示本文算法表現(xiàn)出了較好的分類性能和有力的競爭能力。

圖5 核函數(shù)參數(shù)c與分類準確率之間的關(guān)系

圖6 鄰域控制因子θ與分類準確率之間的關(guān)系

為了充分挖掘本文訓練方法的潛力，接下來我們將對算法進行深入的分析和改進，如對于不同的問題引入不同的核函數(shù)、通過空間幾何的知識來確定更好的記憶細胞等。最后，改進的算法將會被應用于圖像分類等類別更多、樣本數(shù)量更大的問題，進一步驗證分類器的分類性能。

［1］ T imm is J， Honec A， Stibord T， et al.. Theoretical advances in artificial immune system s［J］. Theoretical Com puter Science，2008， 403（1）: 11-32.

［2］ De Castro L and Von Zuben F. Learning and op tim ization using the clonal selection p rinciple［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（3）: 239-251.

［3］ 戚玉濤， 劉芳， 劉靜樂， 等. 基于免疫算法和EDA的混合多目標優(yōu)化算法［J］. 軟件學報， 2013， 24（10）: 2251-2266. Qi Yu-tao， Liu Fang， liu Jing-Le， et al.. Hybrid immune algorithm w ith EDA for multi-ob jective optim ization［J］. Journal of Software， 2013， 24（10）: 2251-2266.

［4］ Lin Qiu-zhen and Chen Jian-yong. A novel m icro-population immune multiob jective optim ization algorithm［J］.Computers & Operations Research， 2013， 40（6）: 1590-1601.

［5］ M lungisi D， Tsh ilidzi M， and Bhekisipho T. Partial im putation of unseen records to imp rove classification using a hybrid multi-layered artificial immune system and genetic algorithm［J］. Applied Soft Computing， 2013， 13（12）: 4461-4480.

［6］ Chang S and Yeh T. An artificial immune classifier for cred it scoring analysis［J］. Applied Soft Com puting， 2012， 12（2）: 611-618.

［7］ Deng Ze-lin， Tan Guan-zheng， He Pei， et al.. A decsision hyper p lane heuristic based artificial immune network classification algorithm［J］. Journal of Cen tral South University， 2013， 20（7）: 1852-1860.

［8］ Yang Dong-dong， Wang Lei， Hei Xin-hong， et al. An efficient autom atic SAR im age segm entation fram ework in A IS using kernel clustering index and histogram statistics［J］. Applied Soft Computing， 2014， 16（3）: 63-79.

［9］ Shang Rong-hua， Qi Li-p ing， Jiao Li-cheng， et al.. Change detection in SAR im ages by artificial immune multi-ob jective clustering［J］. Engineering Applications of Artificial Intelligence， 2014， 31（1）: 53-67.

［10］ Shahaboddin S， Nor B， M iss L， et al.. Co-FAIS: Cooperative fuzzy artificial immune system for detecting intrusion in w ireless sensor networks［J］. Journal of Network and Com puter Applications， 2014， 42（1）: 102-117.

［11］ 劉若辰， 鈕滿春， 焦李成. 一種新的人工免疫網(wǎng)絡算法及其在復雜數(shù)據(jù)分類中的應用［J］. 電子與信息學報， 2010， 32（3）: 515-521. Liu Ruo-chen， Niu M an-chun， and Jiao Li-cheng. A new artificial immune network algorithm for classifying com p lex data［J］. Journal of E lectronics & Inform ation Technology，2010， 32（3）: 515-521.

［12］ G rzegorz D. An artificial immune system for classification w ith local feature selection［J］. IEEE Transactions on Evolutionary Computation， 2012， 16（6）: 847-860.

［13］ Deng Ze-lin， Tan Guan-zheng， and He Pei. An imm une network classifier based on pair w ise antigens［J］. ICIC Express Letters， 2014， 8（6）: 1547-1552.

［14］ Ayse M and Ahmet A. A novel app roach for designing adap tive fuzzy classifiers based on the combination of an artificial immune network and a memetic algorithm［J］. Inform ation Sciences， 2014， 264（1）: 158-181.

［15］ Leung K， Cheong F， and Cheong C. Generating com pact classifier system s using a sim p le artificial imm une system［J］. IEEE Transactions on System s， Man， and Cybernetics-Part B: Cybernetics， 2007， 37（5）: 1344-1356.

［16］ Aydin I， Mehmet K， and Erhan A. Artificial immune classifier w ith swarm learning［J］. Engineering Applications of Artificial Intelligence， 2010， 23（8）: 1291-1302.

［17］ Igawa K and Ohashi H. A negative selection algorithm for classification and reduction of the noise effect［J］. Applied Soft Computing， 2009， 9（1）: 431-438.

［18］ Stephen V. Selecting and interpreting measures of thematic classification accu racy［J］. Rem ote Sensing of Environment，1997， 62（1）: 77-89.

鄧澤林： 男，1977年生，博士，講師，研究方向為人工免疫系統(tǒng)、模式識別.

譚冠政： 男，1963年生，博士，教授，研究方向為智能機器人系統(tǒng)與控制、人工智能與認知系統(tǒng).

何 锫： 男，1963年生，博士，教授，研究方向為軟件工程、人工智能.

李 峰： 男，1964年生，博士，教授，研究方向為圖像處理與模式識別.

A Dynam ic Recognition Neighborhood Based Immune Network Classification A lgorithm and Its Performance Analysis

Deng Ze-lin①Tan Guan-zheng②He Pei③Li Feng①①（Schoo l of Com puter and Comm unication Engineering， Changsha University of Science and Technology， Changsha 410076， China）
②（School of Information Science and Engineering， Central South University， Changsha 410083， China）
③（School of Computer Science and Educational Software， Guangzhou University， Guangzhou 510006， China）

For lack of effective methods used by the trad itional immune network algorithm s to guide the m em ory cell determ ination， a dynam ic recognition neighborhood based immune network classification algorithm is proposed. The algorithm uses a kernel function rep resentation scheme to describe the antibody-antigen affinity，and constructs dynam ic recognition neighborhood w ith using pair wise antigens to guide the antibody popu lation evolution， in which the antibody nearest to the pairing antigen is determ ined as the memory cell. The algorithm is app lied to mu lti-class problem and high dim ensional classification problem to analyze the classification performance. Furthermore， the algorithm is used for many standard datasets classification to evaluate the algorithm overall performance. The resu lts show that the proposed algorithm can achieve better classification performance， which indicates that the dynam ic recognition neighborhood based training method is able to guide the memory cell generation effectively and im prove the algorithm performance significantly.

Artificial intelligence； Artificial immune system； Immune network； Pair w ise antigen； Dynam ic recognition neighborhood

TP301

： A

：1009-5896（2015）05-1167-06

10.11999/JEIT141077

2014-08-14收到，2014-12-25改回

國家自然科學基金（61170199）和湖南省教育廳重點項目（11A004）資助課題

*通信作者：鄧澤林 zl_deng@sina.com