基于反饋的人工負(fù)選擇分類算法

沈彤　關(guān)毅　董喜雙

摘要：人工免疫系統(tǒng)是受人體免疫系統(tǒng)啟發(fā)的一種智能算法，負(fù)選擇算法作為人工免疫系統(tǒng)的核心算法之一，在各領(lǐng)域被廣泛研究和應(yīng)用。從兩方面對負(fù)選擇算法進(jìn)行了改進(jìn)，首先對記憶細(xì)胞數(shù)量對識別準(zhǔn)確率的影響進(jìn)行了研究，提出一種反饋學(xué)習(xí)的思想來進(jìn)行記憶細(xì)胞數(shù)量的優(yōu)化，實現(xiàn)提高分類過程中的識別準(zhǔn)確率。然后為了解決傳統(tǒng)負(fù)選擇算法存在檢測器覆蓋空間存在交集、整體覆蓋空間較低的問題，提出通過記憶細(xì)胞識別半徑的自動調(diào)整，減少檢測器數(shù)量，提高整體覆蓋空間的方法，這種方法避免了“交叉識別（overlap）”和“識別洞（hole）”現(xiàn)象的出現(xiàn)。最后，實驗結(jié)果表明算法在解決文本分類問題是有效可行的，其在路透社文本分類數(shù)據(jù)集上分類準(zhǔn)確率達(dá)到了93.89%。

關(guān)鍵詞：負(fù)選擇算法； 人工負(fù)選擇分類； 反饋學(xué)習(xí)

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-2163（2013）05-0061-05

0引言

“負(fù)選擇（Negative selection，NS）”是免疫系統(tǒng)中自體/非自體區(qū)分機制的基礎(chǔ)。負(fù)選擇過程是指在T細(xì)胞發(fā)育過程中，在其表面通過隨機遺傳重排產(chǎn)生了對于特定抗原決定基高度特異的抗原識別受體來識別抗原的過程。T細(xì)胞在胸腺成熟的過程中，生物免疫系統(tǒng)將與自體蛋白質(zhì)相結(jié)合的T細(xì)胞消除，保留未結(jié)合的T細(xì)胞，從而確保T細(xì)胞在體內(nèi)循環(huán)時不會識別自體細(xì)胞[1]。負(fù)選擇算法（Negative Selection Algorithm，NSA）模擬了免疫系統(tǒng)識別自體和非自體細(xì)胞的負(fù)選擇過程，首先隨機產(chǎn)生候選檢測器，然后與自體樣本數(shù)據(jù)集進(jìn)行識別判斷，生成非自體檢測器，最后使用非自體檢測器對非自體數(shù)據(jù)進(jìn)行識別[2]，完成自體與非自體數(shù)據(jù)的分類。負(fù)選擇算法作為人工免疫系統(tǒng)的核心算法之一，其研究成果涉及諸多領(lǐng)域，例如入侵檢測[3]、數(shù)據(jù)分類[4]聚類[5]和異常檢測[6，7]等，但仍存在以下兩個問題：一方面，負(fù)選擇算法中記憶細(xì)胞數(shù)量選擇的不當(dāng)會對識別精度產(chǎn)生一定的影響；另一方面，由于負(fù)選擇算法在匹配過程中通常使用K連續(xù)位匹配規(guī)則，該規(guī)則的特殊性使得負(fù)選擇算法帶來的檢測器在其覆蓋空間出現(xiàn)交集，因而檢測器集合整體覆蓋空間較低的問題。

在負(fù)選擇算法中，記憶細(xì)胞數(shù)量的不同會對算法的識別精度產(chǎn)生影響。由于在傳統(tǒng)的負(fù)選擇算法中，記憶細(xì)胞數(shù)量是固定值，無法比較判斷當(dāng)前記憶細(xì)胞數(shù)量是否為最佳值。為了解決記憶細(xì)胞數(shù)量選擇不當(dāng)對識別精度的影響，本文通過開展記憶細(xì)胞數(shù)量對識別準(zhǔn)確率的影響的研究，提出一種通過反饋學(xué)習(xí)思想進(jìn)行記憶細(xì)胞數(shù)量的優(yōu)化，從而達(dá)到最佳分類效果的方法。

覆蓋空間出現(xiàn)交集在將負(fù)選擇算法應(yīng)用于分類的過程中體現(xiàn)為“交叉識別”現(xiàn)象。“交叉識別”現(xiàn)象指樣本數(shù)據(jù)未被分配到任何類別。與此對應(yīng)的“識別洞”現(xiàn)象，是指樣本被標(biāo)記為多個類別，其時則無法判斷應(yīng)屬哪一類別。為了解決傳統(tǒng)負(fù)選擇算法存在檢測器覆蓋空間出現(xiàn)交集、整體覆蓋空間較低的問題，本文提出一種通過記憶細(xì)胞識別半徑的自動化調(diào)整，減少檢測器覆蓋空間交集，提高整體覆蓋空間的方法，避免了“交叉識別”和“識別洞”現(xiàn)象的出現(xiàn)。其中，解決“交叉識別”現(xiàn)象的方法是縮小識別半徑，避免被多種記憶細(xì)胞識別。解決“識別洞”現(xiàn)象的方法是增大識別半徑，擴大記憶細(xì)胞覆蓋空間。

全文共分為五部分，其內(nèi)容具體安排為：第一部分引言，主要介紹了生物免疫系統(tǒng)的負(fù)選擇原理，以及課題的研究背景和研究意義，又給出了本文主要研究內(nèi)容和文章結(jié)構(gòu)。第二部分相關(guān)工作，首先分析了負(fù)選擇算法的國內(nèi)外研究現(xiàn)狀，然后介紹了常用的文本分類算法和基于人工免疫系統(tǒng)的分類算法。第三部分人工負(fù)選擇分類，首先對負(fù)選擇算法的原理進(jìn)行了系統(tǒng)描述，提出負(fù)選擇算法待解決的問題，其次介紹人工負(fù)選擇分類算法的具體流程，然后對其中每一部分進(jìn)行具體論述，并針對負(fù)選擇算法中出現(xiàn)的問題提供了詳細(xì)解決方案。第四部分實驗結(jié)果與分析，針對提出的新算法在兩個方面的改進(jìn)分別進(jìn)行了試驗，證明算法改進(jìn)后的正確性和優(yōu)越性。全文第五部分則是論文的結(jié)論及對下一步研究工作的展望。

1相關(guān)工作

負(fù)選擇算法已廣泛應(yīng)用到數(shù)據(jù)分類聚類、異常檢測、網(wǎng)絡(luò)入侵檢測等諸多領(lǐng)域。劉錦偉等人[8]通過分析已有實值負(fù)選擇算法檢測率不高的原因，提出一種通過鑒別邊界自體樣本以提高對“識別洞”的覆蓋率的改進(jìn)負(fù)選擇算法，并采用人工合成數(shù)據(jù)集2DSyntheticData和實際Biomedical數(shù)據(jù)集對算法進(jìn)行驗證，結(jié)果表明，該算法針對夜晚視頻進(jìn)行目標(biāo)檢測是準(zhǔn)確有效的，對于實現(xiàn)智能交通系統(tǒng)的全天候監(jiān)控有現(xiàn)實意義；汪慧敏等人[9]為解決基于負(fù)選擇的異常檢測算法中檢測器數(shù)目和檢測器對非我空間的覆蓋二者之間的矛盾問題，采用粒子群優(yōu)化算法（PSO）來優(yōu)化負(fù)選擇算法中隨機產(chǎn)生的檢測器的位置，從而實現(xiàn)利用較少的檢測器就能達(dá)到對非我空間的更大覆蓋；仲巍[10]在分析了影響負(fù)選擇算法性能的因素后，提出了一種基于切割的負(fù)選擇算法，算法中使用新型的元素定義標(biāo)準(zhǔn)和匹配規(guī)則，結(jié)合一種多級檢測器生成思想，有效解決了負(fù)選擇算法中檢測效率及檢測率低下等問題。同時設(shè)計了基于層次型的檢測器組織策略和基于優(yōu)先級的檢測器管理策略，并提出了一套快速檢測器更新機制，可動態(tài)修改檢測器信息，而且減少了環(huán)境變動時所造成的系統(tǒng)開銷；曹霞[11]提出了一種應(yīng)用于入侵檢測系統(tǒng)的實值負(fù)選擇改進(jìn)算法，該算法通過估算“非自體”空間大小和優(yōu)化抗體分布來產(chǎn)生最優(yōu)化抗體集合，從而提高系統(tǒng)的檢測率和降低誤報率。國外很多研究學(xué)者對負(fù)選擇算法也展開了研究。Bereta等人[12]將負(fù)選擇算法與免疫K-means算法相結(jié)合應(yīng)用于數(shù)據(jù)分析和聚類，研究首先對原始數(shù)據(jù)進(jìn)行負(fù)選擇，使用進(jìn)化的負(fù)選擇檢測器生成一組人工樣本。然后將原始數(shù)據(jù)與人工樣本相結(jié)合來構(gòu)建訓(xùn)練數(shù)據(jù)，并使用免疫K-means算法訓(xùn)練得到記憶細(xì)胞以用于數(shù)據(jù)聚類，取得了較好的聚類效果；Fernando Esponda等人[13]提出一種通用框架用來分析正負(fù)選擇在近似匹配背景下的不同，該框架可以應(yīng)用于異常入侵檢測，例如，檢測在局域網(wǎng)中異常TCP連接或者檢測執(zhí)行程序的系統(tǒng)調(diào)用中的異常模式；Laurentys等人[14]提出了一種基于人工免疫系統(tǒng)的負(fù)選擇算法原理的故障檢測系統(tǒng)的設(shè)計方法——多操作算法。

常用的文本分類算法包括貝葉斯分類、神經(jīng)網(wǎng)絡(luò)分類、支持向量機、TFIDF算法、粗糙集方法和模糊集（Fuzzy Set）方法等[15]。其中，基于人工免疫系統(tǒng)的分類算法的研究已獲得了豐碩成果，例如，Alves等人提出的基于規(guī)則的模糊規(guī)則歸納算法（Induction of Fuzzy Rules with an Artificial Immune System，IFRAIS）[16]；邱小寧對IFRAIS 算法進(jìn)行了改進(jìn)，在IFRAIS 算法的規(guī)則進(jìn)化研究中對抗體的克隆選擇過程增加了抗體抗原間的交叉，以提高分類準(zhǔn)確率，提出了抗體抗原交叉的規(guī)則歸納算法（Induction of Rule with Antibody-Cross-Antigen of Artificial Immune System， IRAA），并通過實驗對改進(jìn)算法進(jìn)行了驗證[17]；Watkins在克隆選擇和有限資源人工免疫系統(tǒng)等基礎(chǔ)上提出了人工免疫識別系統(tǒng)（Artificial Immune Recognition System，AIRS）分類器模型[18，19]；彭凌西等人對AIRS進(jìn)行了改進(jìn)，提出了一種基于免疫的監(jiān)督式分類算法，有效減少了記憶細(xì)胞數(shù)量，提高了分類準(zhǔn)確率[20]；劉芳等人提出了一種基于免疫克隆算法的搜索機制以及Michigan方法模型的規(guī)則提取和分類方法——免疫克隆分類算法（Immune Clonal Algorithm for Classification，ICAC）[21]；K.lgawa等人對負(fù)選擇算法進(jìn)行了改進(jìn)，將負(fù)選擇算法應(yīng)用于多類別分類問題，并提出一種“裁剪”的思想來減弱噪聲對分類結(jié)果的影響[22]。

2人工負(fù)選擇分類器

首先對基于人工免疫系統(tǒng)的負(fù)選擇算法進(jìn)行介紹，負(fù)選擇算法借鑒了生物免疫系統(tǒng)中胸腺T細(xì)胞生成時的“負(fù)選擇”過程，其主要算法流程如圖1所示。

在產(chǎn)生檢測器階段，負(fù)選擇算法隨機產(chǎn)生候選檢測器，并判斷其是否與“自體”樣本數(shù)據(jù)集中每個數(shù)據(jù)進(jìn)行匹配，若與任一數(shù)據(jù)匹配，則將該檢測器從候選集合中刪除，反之，不與任一“自體”數(shù)據(jù)匹配的候選檢測器加入“非自體”檢測器集。在檢測階段，將待檢測數(shù)據(jù)與“非自體”檢測器集合中的“非自體”檢測器進(jìn)行匹配，若有任一“非自體”檢測器可識別該數(shù)據(jù)，則認(rèn)定該數(shù)據(jù)為“非自體”數(shù)據(jù)，即異常數(shù)據(jù)，反之，不與任一“非自體”檢測器相匹配的數(shù)據(jù)即可認(rèn)為是“自體”數(shù)據(jù)，即正常數(shù)據(jù)。本研究將傳統(tǒng)負(fù)選擇算法中的“非自體”檢測器定義為“記憶細(xì)胞”，如果被記憶細(xì)胞識別，表明樣本不屬于該類別。相反，如果無法被記憶細(xì)胞有效識別，表明樣本屬于該記憶細(xì)胞所代表的類別。

人工負(fù)選擇分類器對負(fù)選擇算法進(jìn)行了改進(jìn)，其總體流程如圖2所示。算法的主要思想是在學(xué)習(xí)過程中通過訓(xùn)練數(shù)據(jù)集獲得可用來識別非自體數(shù)據(jù)的記憶細(xì)胞，然后使用反饋學(xué)習(xí)的思想來調(diào)整記憶細(xì)胞數(shù)量，獲得可進(jìn)行預(yù)測的最終非自體記憶細(xì)胞集合。最后，在預(yù)測分類過程中對待分類數(shù)據(jù)進(jìn)行預(yù)測分類。

2.1學(xué)習(xí)過程

傳統(tǒng)的負(fù)選擇算法過程中，記憶細(xì)胞的識別半徑會影響產(chǎn)生的記憶細(xì)胞數(shù)量（即非自體檢測器數(shù)量）。其中，識別半徑指隨機生成的檢測器（即記憶細(xì)胞）能夠識別樣本的最大距離，本文采用歐氏距離計算，在系統(tǒng)初始化時設(shè)定。記憶細(xì)胞數(shù)量的不同會對算法的識別精度產(chǎn)生影響。在傳統(tǒng)的負(fù)選擇算法中，由于記憶細(xì)胞數(shù)量是固定值，無法判斷比較當(dāng)前記憶細(xì)胞數(shù)量是否為最佳值。為了解決這一問題，本文在算法的學(xué)習(xí)過程中增加了反饋機制，通過當(dāng)前記憶細(xì)胞數(shù)量對識別精度的反饋信息來調(diào)整決定記憶細(xì)胞識別半徑的參數(shù)α，從而對記憶細(xì)胞數(shù)量進(jìn)行優(yōu)化，達(dá)到最佳分類效果的方法。

人工負(fù)選擇分類算法的學(xué)習(xí)過程主要由獲取最佳記憶細(xì)胞和反饋調(diào)整兩部分組成。學(xué)習(xí)過程旨在通過訓(xùn)練數(shù)據(jù)集獲取記憶細(xì)胞，借鑒生物免疫系統(tǒng)的克隆和變異過程對記憶細(xì)胞進(jìn)行優(yōu)化，并通過使用記憶細(xì)胞對訓(xùn)練數(shù)據(jù)進(jìn)行識別的過程獲得反饋信息，同時根據(jù)反饋信息對記憶細(xì)胞數(shù)量進(jìn)行調(diào)整，從而用數(shù)量適當(dāng)?shù)淖罴延洃浖?xì)胞來對待檢測數(shù)據(jù)進(jìn)行分類預(yù)測，以達(dá)到提高識別精度的目的。具體過程如圖3所示。

在獲取最佳記憶細(xì)胞的過程中，首先設(shè)置識別半徑，然后設(shè)置“激活”等級，“激活”等級是指可被該檢測器識別的非自體數(shù)據(jù)的數(shù)量，激活等級的值為刺激水平值和次刺激水平值之和。刺激水平是指可被該檢測器識別，但不可被自體檢測器（即自體記憶細(xì)胞集）識別的非自體數(shù)據(jù)的數(shù)量，次刺激水平是指既可被該檢測器識別，又可被自體檢測器識別的非自體數(shù)據(jù)的數(shù)量。接著，判斷隨機生成的檢測器是否具有成為記憶細(xì)胞的條件，只有隨機生成的檢測器達(dá)到最低“激活”等級后才能成為記憶細(xì)胞。對于沒有達(dá)到最低“激活”等級的檢測器則需要進(jìn)行克隆與變異。在克隆過程中，每一個未達(dá)到最低“激活”等級的檢測器將以一定的克隆數(shù)量（初始化時設(shè)定）完成克隆后加入檢測器集合。變異過程則是借鑒遺傳算法中的單點變異，設(shè)定變異率為一個常數(shù)，在系統(tǒng)初始化時設(shè)定，若隨機產(chǎn)生的變異概率低于變異率，則該檢測器發(fā)生變異。經(jīng)過克隆和變異過程后將產(chǎn)生新的檢測器，如果這些新的檢測器達(dá)到最低“激活”等級，則作為最佳記憶細(xì)胞。

在反饋過程中，首先使用當(dāng)前非自體記憶細(xì)胞集對訓(xùn)練樣本數(shù)據(jù)進(jìn)行預(yù)測分類，然后將其分類結(jié)果與訓(xùn)練樣本數(shù)據(jù)的實際類別進(jìn)行比較獲取分類準(zhǔn)確率，并根據(jù)準(zhǔn)確率調(diào)整決定記憶細(xì)胞識別半徑的參數(shù)α，即間接調(diào)整記憶細(xì)胞數(shù)量，重新獲取最佳記憶細(xì)胞。如此迭代循環(huán)，直至調(diào)整至最佳記憶細(xì)胞數(shù)量值，則將當(dāng)前的非自體記憶細(xì)胞集作為最終非自體記憶細(xì)胞集對待分類數(shù)據(jù)集進(jìn)行預(yù)測分類。

2.2預(yù)測分類過程

傳統(tǒng)負(fù)選擇算法在分類過程中存在兩種現(xiàn)象——“交叉識別”現(xiàn)象和“識別洞”現(xiàn)象?！敖徊孀R別”現(xiàn)象指待分類樣本數(shù)據(jù)沒有被分配到任何類別。當(dāng)所有記憶細(xì)胞都能識別該樣本時，表示該樣本不屬于現(xiàn)有全部記憶細(xì)胞所代表的任何類別，即現(xiàn)有記憶細(xì)胞無法判斷該樣本真正屬于哪一個類別；“識別洞”現(xiàn)象是指當(dāng)樣本被標(biāo)記為多個類別時，無法判斷屬于哪一個類別。當(dāng)一種記憶細(xì)胞無法識別該樣本時，表示該樣本屬于該類別。若多種記憶細(xì)胞無法識別該樣本，則空間中即出現(xiàn)一個無法識別樣本的“空洞”。

預(yù)測分類過程是根據(jù)學(xué)習(xí)過程中生成的非自體記憶細(xì)胞集對待分類數(shù)據(jù)集進(jìn)行分類識別的過程。在此過程中，通過對記憶細(xì)胞識別半徑的自動化調(diào)整，減少了檢測器數(shù)量，并提高了整體覆蓋空間，同時解決了傳統(tǒng)負(fù)選擇算法帶來的檢測器覆蓋空間存在交集、整體覆蓋空間較低的問題，更進(jìn)一步地避免了“交叉識別”和“識別洞”現(xiàn)象的出現(xiàn)。其具體流程如圖4所示。

根據(jù)傳統(tǒng)負(fù)選擇算法，若樣本可被該記憶細(xì)胞（即非自體類識別器）識別，表明樣本不屬于該類別。相反，若無法被該記憶細(xì)胞識別，表明樣本屬于該記憶細(xì)胞所代表的類別。在利用獲得的記憶細(xì)胞判斷樣本類別的分類過程中，會出現(xiàn)“識別洞”和“交叉識別”現(xiàn)象，這兩種現(xiàn)象導(dǎo)致無法判斷樣本屬于哪一類別，此時，可通過調(diào)整記憶細(xì)胞的識別半徑直至有且僅有一種記憶細(xì)胞無法識別該樣本時，[JP3]即將該樣本的類別標(biāo)記為此類，由此而完成樣本分類。其具體調(diào)整算法如下：