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

楊韜++鄧紅莉

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

關(guān)鍵詞：人工免疫 否定選擇算法 檢測(cè)器

中圖分類號(hào)：TP274.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）12-0124-01

1 引言

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

2 NST-NSA實(shí)現(xiàn)策略

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

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

3 實(shí)驗(yàn)設(shè)置

本節(jié)通過(guò)實(shí)驗(yàn)驗(yàn)證NST-NSA算法性能。實(shí)驗(yàn)數(shù)據(jù)集采用UCI標(biāo)準(zhǔn)數(shù)據(jù)集中廣泛應(yīng)用于模式識(shí)別與異常檢測(cè)等研究的BCW數(shù)據(jù)集。為說(shuō)明算法性能，NST-NSA將與經(jīng)典的V-Detector算法在上述數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)獨(dú)立重復(fù)20輪，每輪實(shí)驗(yàn)在兩種數(shù)據(jù)集上均隨機(jī)采用60%的自體樣本作為訓(xùn)練集，余下40%的自體樣本以及全部非自體樣本作為測(cè)試集，相關(guān)實(shí)驗(yàn)結(jié)果取均值，最后用檢測(cè)率DR與訓(xùn)練時(shí)間TR-T作為衡量算法性能的指標(biāo)。

如圖1所示，與V-Detector算法相比NST-NSA在相同的期望覆蓋率下都能達(dá)到較高的檢測(cè)率。如圖2所示，當(dāng)期望覆蓋率上升時(shí)，否定選擇選擇算法需要產(chǎn)生更多的檢測(cè)器來(lái)覆蓋非自體空間，此時(shí)候選檢測(cè)器數(shù)量迅速上升，因此距離運(yùn)算的時(shí)間代價(jià)也隨之上升?？梢钥闯鯲-Detector算法在期望覆蓋率增加的情況下，訓(xùn)練時(shí)間呈指數(shù)級(jí)增加；而NST-NSA由于事先記錄了樣本空間信息，每次只需要與最近鄰自體進(jìn)行距離運(yùn)算，從而訓(xùn)練時(shí)間受期望覆蓋率影響不大，擁有更高的計(jì)算效率。

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

[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].中國(guó)科學(xué)：信息科學(xué)，2013，43（5）：611-625.

[4]李濤.計(jì)算機(jī)免疫學(xué)[M].電子工業(yè)出版社，2004.endprint