2.3 GB-RNSA的實現

2.3.1 GB-RNSA算法的基本思想

本書提出了一種基于網格的實值否定選擇算法GB-RNSA。該算法將變半徑的檢測器，以及檢測器對非自體空間的覆蓋率作為檢測器生成過程的結束條件。算法首先分析了自體集在實值空間的分布，并把[0,1]n視為最大的網格。然后，通過一步一步分割直到達到最小網格，并采用2n叉樹才存儲網格，這樣一個有限數量的子網格就生成了，同時自體抗原被填入相對應的網格中。隨機生成的候選檢測器只需要與該檢測器所在的網格及鄰居網格中的自體進行匹配，而不是與全部自體匹配，這就減少了距離計算的時間代價。當把該候選檢測器加入成熟檢測器集合中時，其將與該候選檢測器所在網格及鄰居網格中的檢測器進行匹配，來判斷該檢測器是否已在其他成熟檢測器的覆蓋范圍內或者它的覆蓋范圍完全包含了其他檢測器。這一步過濾操作減少了檢測器間的冗余覆蓋，實現了以較少的檢測器覆蓋盡可能多的非自體空間。GB-RNSA算法的主要思想如表2.2所示。

Iris數據集是由California Irvine大學發布的經典的機器學習數據集之一，被廣泛應用于模式識別、數據挖掘、異常檢測等。我們選擇Iris數據集中的“setosa”類別的數據記錄作為自體抗原，選擇“sepalL”和“sepalW”作為第一維和第二維的屬性，并選擇自體抗原中的前25條記錄作為訓練集。這里，我們只采用記錄的兩個屬性在二維空間中展示算法的思想，不會影響對比結果。圖2.1顯示了GB-RNSA算法與經典的否定選擇算法RNSA和V-Detector的對比。RNSA生成固定半徑的檢測器；V-Detector通過計算候選檢測器中心與自體抗原的最近距離，動態確定檢測器的半徑來生成變半徑檢測器。這兩種算法生成的檢測器需要與全部自體抗原進行耐受，隨著覆蓋率的上升將引起成熟檢測器間的冗余覆蓋。GB-RNSA首先分析自體集在空間中的分布情況，形成網格。然后，隨機生成的候選檢測器只與該檢測器所在網格及鄰居網格內的自體進行耐受。通過耐受的檢測器將執行一定的策略來避免重復覆蓋，保證新檢測器能覆蓋之前未覆蓋的區域。

2.3.2 網格生成策略

在網格生成過程中，我們采用了從上到下的方法。首先，GB-RNSA算法把n維[0,1]空間當作最大的網格。如果在此網格中存在自體，那么將每一維分成兩部分，得到2n個子網格。然后，繼續判斷并劃分每個子網格，直到該網格不包含自體或者網格的直徑達到了最小值。最后，空間的網格結構就形成了，該算法搜索每個網格得到各自的鄰居節點。這個過程由表2.3和表2.4來說明。

定義2.9網格的最小直徑。rgs=4rs+ 4rds。其中，rs為自體半徑，rds為檢測器的最小半徑。假設一個網格的直徑小于rgs，劃分這個網格，那么得到的子網格直徑小于2 rs+ 2 rds。如果該子網格中存在自體，那么不可能在該子網格中生成檢測器。所以，設網格的最小直徑為4rs+ 4rds。

定義2.10鄰居網格。如果兩個網格至少在一個維度相鄰，那么這兩個網格即為鄰居，被稱作互為基礎鄰居網格。如果鄰居網格中自體為空，則該鄰居網格的同一方向的基礎鄰居網格為附加鄰居網格。一個網格的鄰居包括基礎鄰居網格和附加鄰居網格。

鄰居網格的填充過程如表2.5所示。

圖2.2描述了網格的劃分過程。自體訓練集仍然來自Iris數據集中的類別的數據記錄，被選擇作為抗原的第一維和第二維屬性。如圖2.2所示，在第一次劃分中二維空間被劃分為4個子網格。當子網格中自體不為空時，繼續劃分，直到子網格不能被劃分為止。

圖2.3描述了鄰居網格的位置。被斜杠覆蓋的網格為[0,0.5,0.5,1]網格的鄰居，分布在空間的左下部分和右上部分。

2.3.3 非自體空間的覆蓋率計算方法

非自體空間覆蓋率P等于檢測器覆蓋的空間Vcovered與全部非自體所占的空間Vnonself的比值，如式（2.4）所示。

由于檢測器間存在冗余覆蓋，所以直接計算（2.4）式是不可能的。本書采用概率估計的方法來計算檢測器覆蓋率P。對檢測器集合D來說，在非自體空間采樣被檢測器覆蓋的概率服從二項分布b（1, P）。采樣次數m的概率服從二項分布b（m, P）。

定理2.1 當持續采樣的非自體樣本數量i≤ N0時，如果，那么檢測器的非自體空間覆蓋率達到了P。Zα是標準正太分布的α位點，x是持續采樣的非自體樣本被檢測器覆蓋的數目，N0是同時大于5/P和5/（1-P）的最小正整數。

證明 隨機變量x～B（i,P）。設。我們考慮兩種情況。

（1）如果持續采樣的非自體樣本的數量i=N0，由De Moivre-Laplace定理可知，當N0＞5/P且N0＞5/（1-P）,x～AN[N0P,N0P(1- P) ]。即，,z～AN（0,1）。下面做假設。H0：檢測器的非自體空間覆蓋率≤P。H1：檢測器的非自體空間覆蓋率＞P。給定顯著性水平α,P{z＞Zα}=α。那么，拒絕域W ={(z1,z2, …,zn):z＞Zα}。因此，當,z屬于拒絕域，拒絕H0，接受H1。即，非自體空間覆蓋率＞P。

（2）如果持續采樣的非自體樣本的數量i＜N0,i·P不是太大，那么x近似服從泊松分布，λ等于i·P。即P{z＞Zα}＜α。當，那么非自體空間覆蓋率＞P。證畢。

從定理2.1知，在檢測器生成過程中，只有持續采樣的非自體樣本數目i和被檢測器覆蓋的非自體樣本數目x需要被記錄。在非自體空間采樣后，確定該非自體樣本是否被檢測器集合D覆蓋。如果沒有被覆蓋的話，以該非自體樣本的位置向量生成一個候選檢測器，然后把它加入到候選檢測器集合CD中。如果被覆蓋的話，計算是否大于Zα。如果大于，那么非自體空間覆蓋率達到了期望覆蓋率P，則停止采樣。如果不大于的話，增加i。當i達到N0，把候選檢測器集合CD加入檢測器集合D來改變非自體空間覆蓋率，然后重置i = 0,x = 0來開始新一輪的采樣。隨著候選檢測器的持續增加，檢測器集合逐漸增大，非自體空間覆蓋率逐漸增長。

2.3.4 候選檢測器的過濾方法

當在非自體空間的采樣次數達到了N0時，候選檢測器集合中的檢測器將加入檢測器集合D。這個時候，并不是所有的候選檢測器都將加入D，我們將對這些檢測器執行過濾操作。過濾操作包含兩個部分。

第一部分為減少候選檢測器間的冗余覆蓋。首先，將候選檢測器集合中的檢測器按照半徑大小降序排列，然后判斷隊列中后面的檢測器是否包含在前面的檢測器覆蓋范圍內。如果是的話，此次非自體空間采樣是無效的，以該次采樣的位置向量生成的候選檢測器將被刪除。這一輪過濾操作后，候選檢測器間將不包含完全覆蓋。

第二部分為降低成熟檢測器與候選檢測器間的冗余覆蓋。當把候選檢測器并入檢測器集合D中時，候選檢測器將與它所在網格及鄰居網格中的檢測器進行匹配，來判斷它是否包含了其他成熟檢測器。如果是的話，該成熟檢測器是冗余的，應該被刪除。此步過濾操作保證了每一個成熟檢測器都覆蓋了一部分未被覆蓋的非自體空間。

候選檢測器的過濾操作過程如表2.6所示。

2.3.5 時間復雜度分析

定理2.2 GB-RNSA中檢測器生成過程的時間復雜度為O{[|D| /（1 -P′）]（Ns+ |D|2）}。其中Ns為訓練集的大小，D為檢測器集合的大小，P′為檢測器的平均自反應率。

證明。在GB-RNSA中，生成一個成熟檢測器主要的時間代價包括調用FindGrid查找網格的時間消耗，候選檢測器自體耐受的時間消耗和調用Filter過濾檢測器的時間消耗。

由2.3.2節可知，2n叉樹的深度為Ceil{log2[1/（4rs+ 4rds）]}。因此，對一個新的檢測器來說，查找該檢測器所在網格grid′的時間復雜度為t1 = O（Ceil（log2（1/（4rs+ 4rds）））n）。n為空間維度，rs為自體半徑，rds為檢測器的最小半徑。因此，t1相對來說，是恒量。

計算新檢測器的半徑需要計算檢測器的中心與它所在網格及鄰居網格包含的自體的最小距離。時間復雜度為，其中為網格grid′及其鄰居內自體的數量。

計算新檢測器是否被已有檢測器覆蓋的時間復雜度為t3 = O（D′）。其中D′為grid′網格及其鄰居內檢測器的數量。

調用Filter掃描檢測器的時間復雜度包括對候選檢測器排序的時間消耗和判斷是否存在冗余覆蓋的時間消耗，即，。

設N′為生成檢測器集合D所需的候選檢測器的數量，那么采樣的時間復雜度為。因此，生成檢測器集合D的時間復雜度如下。

因此，GB-RNSA中檢測器生成過程的時間復雜度為O {[|D| /（1 -P′）]（Ns+|D|2）}。證畢。

SNSA、RNSA和V-Detector是主要的檢測器生成算法，且被廣泛應用于基于人工免疫的模式識別、異常檢測、免疫優化等。表2.7顯示了這些否定選擇算法與GB-RNSA的對比。從表2.7中可以看出，傳統算法的時間復雜度與自體集大小Ns呈指數關系。當自體元素增多時，時間復雜度將迅速增高。GBRNSA消除了指數影響，并降低了自體規模的增長對時間復雜度的影響。因此，GB-RNSA降低了原始算法的時間復雜度并改進了檢測器生成的效率。