一種使用最近鄰自體耐受的否定選擇算法

楊韜++鄧紅莉

摘要：本文提出一種采用最近鄰自體耐受的否定選擇算法（Nearest Neighbor Self Tolerance Negative selection algorithm， NST-NSA），該算法在通過數據預處理階段將所有樣本壓縮進單位特征空間，并利用N維數組記錄自體位置；在訓練階段根據候選檢測器坐標在N維數組中搜索最近近鄰自體進行計算。實驗結果表明，想對于傳統的否定選擇算法NST-NSA能以更短的時間達到更高的檢測率。

關鍵詞：人工免疫 否定選擇算法 檢測器

中圖分類號：TP274.5 文獻標識碼：A 文章編號：1007-9416（2014）12-0124-01

1 引言

受到生物免疫系統的啟發，計算機人工免疫系統利用檢測器來代替抗體，在計算機系統內來區分自體與非自體抗原。傳統的否定選擇算法在自體耐受階段（消除免疫自反應），每一個新生成候選檢測器要進化成為成熟檢測器必須要與所有自體進行距離計算，這樣的距離計算耗費了大量的時間代價極大地降低了算法的效率，限制了否定選擇算法的應用。而事實上，候選檢測器只要沒有覆蓋距離自己空間距離最近。自體樣本就必然不會覆蓋更遠距離的自體樣本，因此本文利用N維數組在預處理階段記錄下訓練樣本的空間信息，當候選檢測器生成時根據檢測器的空間信息直接在數組中查找最近鄰自體來進行距離計算，這將有效地縮短計算時間提高算法效率。

2 NST-NSA實現策略

本文采用線性函數轉化將所有抗原（數據樣本）歸一化到[0，1]n特征空間在歸一化全部完成之后，根據最小歸一化精度與訓練數據維度，生成N維數組A用于記錄訓練樣本的空間信息。例如樣本有2維， 即N=2；在每一位上歸一化后小數取值均為小數點后1位，即精度為0.1，因此空間數組應為10*10的2維數組。為了方便快速遍歷，數組A中有樣本點的位置將置“1”，其余位置將置“0”，當空間數組A生成后，根據候選檢測器的實際位置就能夠快速檢索到最鄰近自體距離，假設有候選檢測器d（x，y），首先在根據檢測器的第一位坐標在數據A中查找非零位置（可能最近鄰點）， 如果沒有發現根據第二維繼續查找；均未發現的情況下開始近鄰區域查找。

需要說明的是，雖然NST-NSA在計算前經過了多次遍歷，然而這些遍歷操作僅僅是簡單的查找并不涵蓋復雜的數值計算。特別地，若采用歐式距離公式，當樣本數量M巨大，樣本維度N偏高時，傳統的否定選擇算法將進行M*N次乘方運算，而NST-NSA最壞情況下只進行（M+N）/2次0/1比較運算，與M0*N次乘方運算，其中M0為可能近鄰點數量，由于M0遠小于M因此NST-NSA的時間復雜度迅速下降。同時使用NST-NSA，候選檢測器僅僅被限制在了局部范圍進行比較，從而有效地減少了“孔洞“，在一定程度上提高算法檢測率。

3 實驗設置

本節通過實驗驗證NST-NSA算法性能。實驗數據集采用UCI標準數據集中廣泛應用于模式識別與異常檢測等研究的BCW數據集。為說明算法性能，NST-NSA將與經典的V-Detector算法在上述數據集上進行對比實驗，實驗獨立重復20輪，每輪實驗在兩種數據集上均隨機采用60%的自體樣本作為訓練集，余下40%的自體樣本以及全部非自體樣本作為測試集，相關實驗結果取均值，最后用檢測率DR與訓練時間TR-T作為衡量算法性能的指標。

如圖1所示，與V-Detector算法相比NST-NSA在相同的期望覆蓋率下都能達到較高的檢測率。如圖2所示，當期望覆蓋率上升時，否定選擇選擇算法需要產生更多的檢測器來覆蓋非自體空間，此時候選檢測器數量迅速上升，因此距離運算的時間代價也隨之上升。可以看出V-Detector算法在期望覆蓋率增加的情況下，訓練時間呈指數級增加；而NST-NSA由于事先記錄了樣本空間信息，每次只需要與最近鄰自體進行距離運算，從而訓練時間受期望覆蓋率影響不大，擁有更高的計算效率。

4 結語

否定選擇算法是人工免疫理論中重要的檢測器生成算法，單傳統的否定選擇算法需要進行大量的計算才能消除候選檢測器免疫自反應，巨大的時間代價限制了否定選擇算法的應用。為此，本文提出了最近鄰自體耐受的否定選擇算法，在預處理階段利用N維數組來記錄訓練樣本的空間信息，在訓練階段可以幫助候選檢測器迅速搜索到最近鄰自體，從而極大地降低了消除免疫自反應的計算代價。理論分析與實驗結果表明NST-NSA相較于經典的V-detector算法能以較低的時間代價達到更高的檢測率。

參考文獻

[1]BRETSCHER P， COHN M.A， A theory of self-noself discrimination[J].Science， 1970，169：1042-1049.

[2]A. S. PERELSON，G. WEISBUCH.Immunology for physicists[J].Reviews of Modern Physics，1997，69（4）：1219-1267.

[3]陳文，李濤，劉曉潔.一種基于自體集層次聚類的否定選擇算法[J].中國科學：信息科學，2013，43（5）：611-625.

[4]李濤.計算機免疫學[M].電子工業出版社，2004.endprint