基于反饋的人工負選擇分類算法

沈彤　關毅　董喜雙

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

關鍵詞：負選擇算法； 人工負選擇分類； 反饋學習

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-2163（2013）05-0061-05

0引言

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

在負選擇算法中，記憶細胞數量的不同會對算法的識別精度產生影響。由于在傳統的負選擇算法中，記憶細胞數量是固定值，無法比較判斷當前記憶細胞數量是否為最佳值。為了解決記憶細胞數量選擇不當對識別精度的影響，本文通過開展記憶細胞數量對識別準確率的影響的研究，提出一種通過反饋學習思想進行記憶細胞數量的優化，從而達到最佳分類效果的方法。

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

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

1相關工作

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

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

2人工負選擇分類器

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

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

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

2.1學習過程

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

人工負選擇分類算法的學習過程主要由獲取最佳記憶細胞和反饋調整兩部分組成。學習過程旨在通過訓練數據集獲取記憶細胞，借鑒生物免疫系統的克隆和變異過程對記憶細胞進行優化，并通過使用記憶細胞對訓練數據進行識別的過程獲得反饋信息，同時根據反饋信息對記憶細胞數量進行調整，從而用數量適當的最佳記憶細胞來對待檢測數據進行分類預測，以達到提高識別精度的目的。具體過程如圖3所示。

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

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

2.2預測分類過程

傳統負選擇算法在分類過程中存在兩種現象——“交叉識別”現象和“識別洞”現象。“交叉識別”現象指待分類樣本數據沒有被分配到任何類別。當所有記憶細胞都能識別該樣本時，表示該樣本不屬于現有全部記憶細胞所代表的任何類別，即現有記憶細胞無法判斷該樣本真正屬于哪一個類別；“識別洞”現象是指當樣本被標記為多個類別時，無法判斷屬于哪一個類別。當一種記憶細胞無法識別該樣本時，表示該樣本屬于該類別。若多種記憶細胞無法識別該樣本，則空間中即出現一個無法識別樣本的“空洞”。

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

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