一種分段檢測器集合生成算法的研究與實(shí)現(xiàn)

張小梅

（蘭州資源環(huán)境職業(yè)技術(shù)學(xué)院 信息管理系，甘肅 蘭州 730021）

陰性選擇算法是Forrest等人研究出來的應(yīng)用于計(jì)算機(jī)安全防護(hù)的檢測算法[1]，其用于故障檢測最大的優(yōu)勢(shì)是用有限數(shù)量的檢測器檢測無限種類的故障[2-5]。但這些算法都要檢查抗原中長度超過匹配閾值的所有子串是否在檢測器中出現(xiàn)，在都未出現(xiàn)的情況下，才能夠判斷抗原合法，由此導(dǎo)致檢測效率較低。國內(nèi)的一些否定選擇算法，如參考文獻(xiàn)[6-7]的研究也主要用于這一方面，缺乏對(duì)否定選擇算法檢測效率的研究。

本文深入研究了傳統(tǒng)否定算法的缺點(diǎn)及其產(chǎn)生的原因，提出了一種新的分段選擇檢測器生成算法并加以實(shí)現(xiàn)，克服了現(xiàn)有方法的不足。

1 典型的否定選擇算法研究

設(shè)l表示自體字符串的長度，m表示字符串中使用的符號(hào)數(shù)目，則對(duì)于兩個(gè)連續(xù)r個(gè)位匹配的隨機(jī)字符串，其發(fā)生匹配的概率為：

設(shè)Ns表示自體集的數(shù)目；NR0表示候選檢測器的數(shù)目；NR表示實(shí)際使用檢測器數(shù)目；Pf表示檢測失敗的概率，則：

在 式（5）中 ，當(dāng) r≤l≤2r 時(shí)，T（l）=ml-ml-r（l-r）l-r-1；當(dāng) l>2r時(shí)，T（l）=2T（l-1）-T（l-r-1），這是一個(gè)遞歸定義。

因此，對(duì)于給定的漏檢率，為了能夠覆蓋所能檢測到的“非我”空間，需要：

2 基于否定選擇的快速檢測器生成算法

當(dāng)否定選擇算法采用r連續(xù)位匹配規(guī)則時(shí)，可以考慮對(duì)線性時(shí)間算法分段實(shí)現(xiàn)的方法進(jìn)行：先推導(dǎo)遞歸公式，然后利用有限的遞歸運(yùn)算解決那些不被S中字符串匹配的循環(huán)計(jì)數(shù)問題，以此計(jì)算出候選檢測器C的規(guī)模，最后利用遞歸求解的序號(hào)，隨機(jī)生成檢測器。于是，檢測器集合生成算法描述如下：

步驟（1）：推導(dǎo)遞歸公式，計(jì)算候選檢測器C的規(guī)模

（1）規(guī)定 Ci[s]為模板 Ti，s的右實(shí)現(xiàn)中所有與 s未匹配的字符串總數(shù)。其中，字符串s的長度為r。根據(jù)i的值分情況處理：

①i=l-r+1

此種情況下，Ti，s由 l-r個(gè)未確定的位和連續(xù)的 r個(gè)確定的位組成，其中，l-r個(gè)未確定的位在左邊，r個(gè)確定的位緊跟在l-r個(gè)未確定位的后邊，于是，模板的右實(shí)現(xiàn)就是該模板本身。由此得到Cl-r+1[s]的值為：

此種情況下，找出i+1位置開始的未被匹配的右實(shí)現(xiàn)的數(shù)量，即可求出模板的未被匹配右實(shí)現(xiàn)數(shù)量。當(dāng)Ti，s與S中的位串相匹配時(shí)，Ci[s]=0；不匹配時(shí)，則在 Ti，s的 r連續(xù)位后附加1或0，于是，求模板的未被匹配的右實(shí)現(xiàn)數(shù)量，就變成了求s←.m的右實(shí)現(xiàn)數(shù)量。于是得到如下遞歸公式：

（2）對(duì)未匹配的空間，根據(jù) r位字符串 s進(jìn)行分割，這一過程記作C1[.]。C1[s]代表每個(gè)分隔空間的大小。對(duì)從s開始的所有未被匹配的字符串，在字符串s后的相應(yīng)位上附加 1或 0，記作 C[s→.m]。 同樣地，C2[.]可看作是對(duì)未被匹配空間的進(jìn)一步分割。以此類推，從C3[.]到Cl-r+1[.]進(jìn)行更加詳細(xì)地分割。經(jīng)過Cl-r+1[.]分割后，每個(gè)分割便是一個(gè)長度為l的字符串。

（3）循環(huán)，重復(fù) l-r+1 次。

①計(jì)算2r個(gè)字符串s的右實(shí)現(xiàn)Ci[s]。

循環(huán)結(jié)束后，C1[.]的右實(shí)現(xiàn)就是一個(gè)所有位均被確定且長度為l的字符串。因此，由r位字符串s開始的未被S匹配的長度為l的字符串的總數(shù)是個(gè)C1[s]。于是得到未被匹配的字符串?dāng)?shù)目為：

步驟（2）：生成未被匹配的檢測器集合

（1）給每個(gè)未被匹配的字符串分配1…sum序號(hào)。

（2）根據(jù)分配的序號(hào)，查找生成相應(yīng)的字符串。生成相應(yīng)的未被S匹配的字符串的步驟如下：

以此類推，形成了一個(gè)完整的字符串s1。

該算法需要一個(gè)（l-r）×2r維的數(shù)組，用來存放兩個(gè)字符串可能r連續(xù)位匹配的所有情形。因此，它的空間復(fù)雜度為：O（2r（l-r）2），時(shí)間復(fù) 雜度為：O（2r（l-r））+O（Ns（l-r））+O（NRl）。

3 算法在實(shí)際工程中的應(yīng)用

嘗試將本文的研究內(nèi)容應(yīng)于實(shí)際的工程。利用本文算法開發(fā)出一套故障診斷在線檢測監(jiān)測系統(tǒng)。以YVP系列45 kW異步電機(jī)為實(shí)驗(yàn)對(duì)象，對(duì)正常電機(jī)和三種故障電機(jī)（電機(jī)輸出軸失衡、電機(jī)軸承噪音大、電機(jī)轉(zhuǎn)子動(dòng)偏心）進(jìn)行訓(xùn)練學(xué)習(xí)。

（1）采集各種工況下的電機(jī)振動(dòng)信號(hào)，消噪并進(jìn)行特征提取；

（2）將反映信號(hào)特征矢量數(shù)據(jù)歸一化處理，組成字符串，長度為 6；

（3）將字符串各位上的數(shù)值范圍變換到區(qū)間0～1范圍內(nèi)，并放大區(qū)間至 0～100；

（4）將區(qū)間 0～100劃分為 60個(gè)小區(qū)間，并按從小到大的順序依次編號(hào)為 0，1，2…59；

（5）將相應(yīng)的數(shù)據(jù)進(jìn)行二進(jìn)制編碼，結(jié)合自體集生成方法，對(duì)應(yīng)的子空間分別由 3 600，4 800，6 000，10 000個(gè)自體數(shù)據(jù)串組成。于是，整個(gè)自體空間的自體數(shù)據(jù)串為24 400個(gè)。

采用3個(gè)連續(xù)位匹配方法，假定檢測器未檢測到異常的概率為5%，即檢測的準(zhǔn)確率為95%，那么，由式（4）可知，只要生成73 096個(gè)抗體字符串即可達(dá)到要求。

通過對(duì)表1所列的差速器樣本的檢測，得到實(shí)驗(yàn)檢測數(shù)據(jù)。

表1 實(shí)驗(yàn)檢測結(jié)果

該算法的檢測準(zhǔn)確率高于90%，雖然未達(dá)到預(yù)先設(shè)定的95%的檢測率（這是由于“孔洞”[2]問題導(dǎo)致的），但是已經(jīng)滿足了故障在線檢測問題的需求。而且，該算法在生成檢測器集合時(shí)，所花費(fèi)的時(shí)間為2分42秒，而傳統(tǒng)否定算法則需要5分33秒，可見，改進(jìn)后的算法的時(shí)間性能提高顯著。

論文將檢測器集合的生成分段進(jìn)行，并對(duì)算法的性能進(jìn)行了驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，本文的檢測器生成算法的匹配速度更快，且能夠有效地提高檢測效率，減小漏報(bào)率與誤報(bào)率，具有實(shí)際的工程應(yīng)用價(jià)值，為進(jìn)一步研究入侵檢測系統(tǒng)提供了新的算法依據(jù)。

[1]ROEKE A J， DEMARA R F.Confidant： Collaborative ObjeetNotifieation Framework forInsiderDefense using AutonomousNetwork Transactions.AutonomousAgentsand Multi-Agent System[J].2006（1）.

[2]FORREST S， PERELSON A， A LLEN L， et al.Selfnonself discrim ination in a computer[C].In Proceedings IEEE Symposium on Research in Security and Privacy，Los A lan itos，CA，1994，IEEE Computer Society Press.

[3]FORREST S，HOFMEYR S A.Engineeringanimmune system[J].Graft，2001（4）：5-9.

[4]BALTHROP J， FORREST S， GLICKMAN M R.Revisting L ISYS：parameters and normal behavior[C].In Procceding of the 2002 Congress on Evolutionary Computation CEC 2002.

[5]FAMER J D， PACKARD N H， PERELSON A S.The immune system， adaptation， and machine learning[J].Physical D，1996.

[6]ZHANG H， WU L F， ZHANG Y S， et al.An algorithm of r-adjustable negative selection algorithm and its simulation analysis[J]. Chinese Journal of Computers， 2005， 28（10）：1614-1619（in Chinese with English abstract）

[7]SMITH R， FORREST S.Searching for diverse， cooperative populations with genetic algorithm[J].Evolutionary Computation，1993.