基于改進主動學習的異常檢測算法

蔡 穎，陳偉榮

(中國電子科技集團第二十八研究所 第一研究部，江蘇 南京 210001)

0 引 言

異常檢測作為入侵檢測技術中的一個重要分支，基本思想是先建立正常的行為模式，再通過計算待檢測行為與正常行為模式之間的偏離程度，來判斷待檢測行為是否異常。其優點是能夠有效地檢測出新的異常類型，缺點是較難建立精確描述正常行為的模型。目前，異常檢測算法主要分為基于統計[1-3]的異常檢測算法、基于特征選擇[4-6]的異常檢測算法、基于神經網絡[7-9]的異常檢測算法和基于數據挖掘技術[10-12]的異常檢測算法4類。這些傳統的異常檢測算法往往需要大量的訓練數據集，且訓練數據集的質量對算法的效率也具有很大的影響[13]。

支持向量機(support vector machine，SVM)是研究小樣本情況下，結構風險最小化的一類新型機器學習方法。傳統的SVM作為有監督的學習方法通常用于解決分類和預測問題，但在實際應用中，對數據進行標簽化需要耗費大量的時間和經濟成本，此外，龐大的訓練數據集也會導致算法消耗更多時間來建立模型。而主動學習則能有效減少所需的已標記樣本的數量[14,15]。傳統的主動學習在選擇策略上，采用了與分類邊界距離最小原則。通常而言，與分類邊界距離越小的樣本，越能影響分類邊界的位置，因此包含的信息量越大。但僅考慮樣本與分類邊界間的距離，而忽視樣本間的冗余，以及候選樣本的代表性，會降低算法運行效率，從而增加不必要的時間和經濟開銷。

基于上述問題，在異常檢測的應用背景下，本文考慮將主動學習加入到傳統SVM算法中，同時對算法的選擇策略進行優化，進而提出了一種基于改進主動學習的異常檢測算法。該算法在采樣過程中，綜合考慮了樣本與分類邊界的距離，以及樣本間的冗余情況，從而使得選取出來的樣本更加合理。同時，通過調整樣本選擇數量，有效地減少了算法的迭代次數，進一步提高了算法效率。

1 主動學習

傳統的SVM算法通過已標記樣本，計算出能夠將不同樣本集合分隔的最優超平面，從而獲得分類模型?；趥鹘ySVM的異常檢測算法，其效果和效率在很大程度上依賴于已標記樣本的質量和數量。雖然在機器學習中，往往默認更多的數據將會帶來更高精度的模型，但事實上，從數據質量的角度出發，可以認為所有數據并不都是平等的，即樣本所包含的信息量并非都是相等的，因此并不是所有的樣本都是對訓練有價值的。與此同時，通過一定的人工驗證和干預過程，則可以使得算法兼顧機器學習的速度，和人工分類的準確度。而主動學習就是這樣一種思想下的機器學習框架。主動學習是指通過一定的選擇策略，從候選樣本集中選擇信息量較大的未標記樣本，經由專家標記后，作為訓練樣本來訓練分類模型的過程。主動學習使得模型訓練成為一個交互的過程，從而有效提高了已標記樣本的質量。

主動學習的模型可以表示為：A=(C,Q,S,L,U)， 其中C為分類器，Q為選擇策略，S為專家，L為已標記樣本集，U為未標記樣本集。在主動學習流程中，首先按照選擇策略Q， 從未標記樣本集U中選擇樣本，經由專家S標記后，加入到已標記樣本集L中，然后重新訓練分類器C， 并迭代上述過程直到分類器C的準確度達到閾值。主動學習流程如圖1所示。

圖1 主動學習流程

由上可知，主動學習和被動學習的最大區別在于選擇策略Q的加入，它允許從未標注的候選樣本集U中選擇下一個應標注的樣本。基于傳統主動學習的異常檢測算法，充分利用了SVM的分類超平面僅與支持向量有關，而與其它向量無關的特質。因此，雖然在機器學習中，用于訓練模型的數量規模越大，得到的模型精度越高，但引入主動學習后，則可以使用更少的數據即達到與隨機抽樣相同的精度。而在分類器一致的情況下，采用何種選擇策略是主動學習效果的關鍵，即如何選擇新的訓練樣本，將直接影響到算法整體的性能。

2 基于改進主動學習的異常檢測

2.1 樣本冗余度

基于傳統主動學習的異常檢測算法，其選擇策略采用了與分類邊界距離最小原則，即每次選擇與分類邊界距離最近的樣本交由專家標記。這是因為樣本距離分類邊界越近，其類別不確定性越大，在機器學習的前提下，越容易被算法分錯類別。而一旦分錯，則可能會導致模型過擬合或算法收斂變慢。由此可見，與分類邊界距離越近的樣本，其包含的信息量越大，越可能改變分類邊界的位置。因此，采用與分類邊界距離最小原則作為選擇策略，可以使得每次選取出來的樣本，都是候選樣本集U中對SVM的分類超平面影響最大的樣本。但基于傳統主動學習的異常檢測算法，僅以樣本與分類邊界的距離作為選擇策略，在計算簡單的同時，也存在著樣本信息冗余和收斂緩慢的問題。

主動學習在每一輪的迭代中，均選擇了與分類邊界距離最近的樣本，作為待標記樣本交由專家標記，因此存在相鄰兩次迭代過程中，選擇的樣本均為同一類別，并且彼此間距離極其相近的情況。在這種情況下，這兩個樣本雖然均為當前迭代輪次中，蘊含信息量最大的樣本，但實際上，兩者間卻極為相似，后者則對分類邊界的確定影響較小，這會導致專家待標記樣本數量和算法迭代次數增多，造成人力和算力的浪費。

因此，為解決相鄰兩次樣本選擇過程中，相似樣本所帶來的冗余問題，本文引入了冗余度p的概念。對于未標記樣本集U中的每一個樣本xi， 定義其在算法的第k次迭代過程中，樣本的冗余度pk(xi) 為

(1)

(2)

式中：Xi，Yi分別表示n維樣本a，b第i維的值。

通過理論分析可得，未標記樣本xi與分類器C分類邊界的距離越小，xi包含的信息量越大，越應該被選取。同時，未標記樣本xi在與已標記訓練樣本集L所含樣本間余弦相似度的平均值越小，xi與L所含樣本的冗余就越小，越應該被選取。而由式(1)可知，樣本的冗余度和待選樣本與分類邊界的距離，以及待選樣本與已標記樣本間的相似度成正比，符合理論分析結果。綜上可得，樣本的冗余度越小，樣本的價值越大，越應該被選取。

此外，傳統主動學習中，每次僅選擇一個樣本進行標記和訓練，導致了迭代收斂速度較慢。同時，如果當前迭代中僅選擇的一個樣本存在異常，并不具備當前數據集的代表性，則會使得分類邊界偏離預期，丟失了候選樣本的總體特征。此外，在實際應用過程中，要求專家逐次對按照選擇策略Q，從未標記樣本集U中選擇出的僅單個樣本進行標記，也是難以實現的。從算法時間開銷和經濟開銷的角度考慮，應該盡可能減少標記輪數和迭代次數。因此，本文所提算法將按照樣本的冗余度從低到高，在合適的范圍內，適當增加每輪迭代過程中樣本的選擇數量。

2.2 算法描述

本文對基于傳統主動學習的異常檢測算法進行了選擇策略上的優化。傳統算法的選擇策略采用了與分類邊界距離最小原則，而如果相鄰兩輪迭代所選擇的樣本屬于同一類別，并且特征相似，將會導致分類邊界變化較小，徒增迭代次數。因此，本文引入了冗余度的概念，以冗余度最小原則作為選擇策略，在計算樣本與分類邊界距離的前提下，通過選擇與已訓練樣本間相似度更低的樣本，作為待標記樣本，并且適當增加樣本選擇數量，以達到減少算法迭代次數，提高算法運行效率的目的?；诟倪M主動學習的異常檢測算法描述如算法1所示。

算法1：基于改進主動學習的異常檢測算法

輸入：未標記樣本集U， 測試樣本集T， 分類準確率P， 分類準確率閾值ω

輸出：滿足P≥ω的分類器C

(1)從未標記樣本集U中選擇一定量的樣本，并正確標記，構造初始的已標記樣本集L， 且L中正負樣本至少各含一個

(2)利用L訓練SVM分類器C

(3)基于C對測試樣本集T進行分類，得到分類準確率P， 若P≥ω， 則跳轉到(6)，否則跳轉到(4)

(4)計算U中樣本的冗余度p， 并按p升序選取topN樣本{α1,α2,…,αN}

(5) 正確標注 {α1,α2,…,αN} 后加入L， 跳轉到(2)

(6) 返回C

3 實驗數據處理

3.1 數據源

本文實驗部分采用的數據集為KDD 99，它是1999年美國國防部高級規劃署(defense advanced research projects age-ncy，DARPA)為知識發現與挖掘(knowledge discovery in database，KDD)競賽提供的一個異常檢測的標準數據集。美國林肯實驗室模擬了一個典型的美國空軍網絡環境，期間通過仿真各種用戶類型，以及各類網絡流量和攻擊手段，收集了9周時間的TCPdump網絡連接和系統審計數據，從而創建了該數據集。這些采集的原始數據被分為7周時間的訓練數據以及2周時間的測試數據兩個部分，其中前者包含約500萬條網絡連接記錄，即TCP數據包序列，而后者包含約300萬條測試數據[16，17]。

KDD 99數據集中的每一條網絡連接記錄由41個特征組成，這41項特征可以分成4大類。其中TCP連接基本特征9種，包含了一些連接的基本屬性，如連接持續時間、協議類型、連接狀態和傳送的字節數等；TCP連接的內容特征13種，包含例如登錄失敗次數、root用戶訪問次數和訪問文件次數等，此類特征包含了網絡攻擊的內容特征；基于時間的網絡流量統計特征9種，包含了當前連接記錄與之前一段時間內的連接記錄之間存在的關系，潛在反映出網絡攻擊在時間上的關聯性；基于主機的網絡流量統計特征10種，作為基于時間無法統計出的網絡流量特征的補充。數據集的每條網絡連接記錄具有一個類別標簽，表明該條數據是正常(normal)數據或攻擊(attack)數據[18]。

為彌補傳統算法的不足，基于改進主動學習的異常檢測算法綜合了樣本與分類邊界的距離以及樣本間的相似度，從而引入了冗余度的概念，對傳統算法的選擇策略進行了優化。而為了計算樣本冗余度，首先需要對實驗數據進行數值化和向量化等預處理，此外，將基于卡方檢驗的思想，對數據集中的數據進行特征選取，以進一步提高算法效率。

3.2 數據預處理

3.2.1 數值化處理

由于KDD 99數據集中存在著非數值型數據，因此需要對非數值型數據進行數值化處理。本文的做法是先確定非數值型數據的取值空間，然后將取值空間中的每一個取值用互不相同的數值表示，最后將非數值型數據用對應的數值進行替換。例如：特征protocol_type表示的是連接的協議類型，它的取值空間為 {TCP，UDP，ICMP} 共3種，則將TCP賦值1、UDP賦值2、ICMP賦值3，最后在原始數據中進行替換。

3.2.2 標準化處理

經過數值化處理之后的數據，往往還不能直接用來進行實驗操作。由于數據不同特征之間的數量級別不同，還需要對不同量綱的數據進行標準化和歸一化處理。標準化處理是改變一個變量取值的表示方法，使得變量的變化范圍變換到一個指定的量程內。標準化處理使得不同量綱的特征對數據的影響因素對等，消除了大數量級特征掩蓋小數量級特征作用的隱患。

若AVG表示各特征值的平均值，STAD表示各特征值的平均絕對誤差，xi表示當前特征值，n表示KDD 99數據集數據量，則數據標準化處理步驟如下：

(1)計算特征值的平均值

(3)

(2)計算特征值的平均絕對誤差

(4)

(3)計算標準化后的特征值

(5)

3.2.3 歸一化處理

此處歸一化的目的是讓數據壓縮在 [0,1] 范圍內。數據歸一化處理步驟如下：

(1)將數據的變化范圍限制在 [0,1] 之間，設定特征值取值上限為Vup=1， 取值下限為Vlow=0；

(2)將同類特征的特征值歸為同一組；

(3)確定同一組中特征值取值的最大值Vmax與最小值Vmin；

(4)對每一個取值進行歸一化操作

(6)

代入數據變化范圍設定，式(6)可以化簡為

(7)

其中，valuei是標準化后的特征值，value′i是經過歸一化處理之后得到的特征值。

3.2.4 特征選取

模型的構建依賴于數據集的特征，但訓練集特征維度越高，訓練模型的時間開銷也會隨之增大。此外，高維度特征可能包含的無關特征及冗余特征，也會使得分類器的性能下降。因此通過特征選取去除無關特征及冗余特征，可以有效提高分類器的訓練效率。

本文基于卡方檢驗的思想，對KDD 99數據集中的數據進行特征選取。卡方檢驗應用在數據特征選取當中，可以檢驗數據的特征與數據的類別之間的獨立性。即，首先假定某數據特征與數據類別之間是無關的，然后對樣本數據進行統計計算，得到理論值與實際值的偏差。如果偏差的值小于設定的閾值，則認定該數據特征與數據所屬類別之間是相互獨立的，那么在進行模型訓練時，則可以將該特征刪除；反之，偏差的值大于設定的閾值，則認定該數據特征與數據所屬類別之間是相關的，應予以保留。本文實驗中，通過設定偏差閾值為10，經過特征提取之后，從41個特征中篩選得到了21個相關度和差異性更高的特征，包含連接狀態(flag)、誤分段數量(wrong_fragment)、超級用戶權限設置(root_shell)、過去兩秒內目標主機相同的連接中出現SYN錯誤的百分比(serror_rate)和前100個目標主機相同的連接中出現SYN錯誤的百分比(dst_host_serror_rate)等，并且保留的21個特征也已涵蓋了KDD 99數據集的4大類特征。

4 實驗結果及分析

4.1 實驗設計

本文從KDD 99數據樣本集中選取了10 000條數據作為訓練樣本集，311 029條數據作為測試樣本集。為了更加真實地模擬網絡的實驗環境，實驗中采用了隨機選取的方法，且樣本集均經過相同的數據預處理步驟進行處理。樣本集的數據組成情況見表1。

表1 兩種候選集樣本的組成情況

為了分析算法的有效性，實驗中分別用基于傳統SVM、基于傳統主動學習以及本文提出的基于改進主動學習的異常檢測算法，在相同條件下進行實驗，觀察并比較不同算法結果。其中，基于傳統SVM的異常檢測算法稱為T-SVM，基于傳統主動學習的異常檢測算法稱為AL-SVM，基于改進主動學習的異常檢測算法稱為PAL-SVM，并且，在選擇樣本時，T-SVM采用隨機選取策略，AL-SVM采用傳統選擇策略，本文提出的PAL-SVM采用冗余度策略。實驗中，SVM使用RBF函數作為核函數，其中設定參數gamma=0.5， 參數C=1000， 初始化時使用相同的已標記訓練樣本集L， 并且L中已包含一定量的正常樣本和異常樣本。

4.2 實驗結果分析

在樣本選擇數量為1的前提下，基于傳統SVM的異常檢測算法、基于傳統主動學習的異常檢測算法、基于改進主動學習的異常檢測算法的分類準確率隨已標記樣本數量變化情況的折線如圖2所示。

圖2 分類準確率隨選擇策略的變化

由圖2中可知，在分類準確率達90%時，基于傳統SVM的異常檢測算法需要已標記樣本約3580個，基于傳統主動學習的異常檢測算法需要已標記樣本約530個，而本文所提的基于改進主動學習的異常檢測算法僅需要已標記樣本約20個即可達到相同的分類準確率。此外，在達到收斂后，本文所提的基于改進主動學習的異常檢測算法的準確率約為92.04%，基于傳統SVM的異常檢測算法的準確率約為90.88%，基于傳統主動學習的異常檢測算法的準確率約為90.89%，由此可見，本文所提算法的準確率也為三者最優。

結合實驗結果分析可得，基于改進主動學習的異常檢測算法通過引入冗余度概念，所選取的樣本相較于傳統算法，所含信息量更大，對確定分類邊界影響更為顯著，因此在與傳統算法取得相同分類準確率的前提下，需要的已標記樣本數量更少，可以更好地適用于小樣本情況下的分類問題。

為了驗證樣本選擇數量對本文所提的基于改進主動學習的異常檢測算法性能的影響，在相同樣本集上進行了進一步實驗。分類準確率隨樣本選擇數量的變化結果見表2。

表2 分類準確率隨樣本選擇數量的變化/%

以N表示樣本選擇數量，由表2可知，當模型分類準確率達90%以上時，若N∈{1,2,3}， 則需要3次迭代，而當N∈{4,5,10,20} 時，僅需要2次迭代。由此可知，每次迭代時樣本選擇數量越多，模型可以獲得的數據特征越多，對分類邊界的確定越有益。而當模型分類準確率穩定在92%以上時，N=5和N=10時算法所需的迭代次數最少，均約3次迭代，并且算法的準確率也均高于其它樣本選擇數量下的算法準確率。

進一步，在N=5和N=10時樣本冗余度隨迭代次數的變化結果如圖3所示，其中橫坐標表示迭代次數，縱坐標表示樣本的冗余度。

圖3 冗余度隨樣本選擇數量的變化

由圖3可知，在算法初期隨著迭代次數增加，選擇的待標記樣本與已標記樣本冗余度逐漸減小，表明此時選擇的待標記樣本越具有差異性，對分類邊界的確定越有價值。而當算法趨于收斂時，樣本冗余度逐漸增大，表明此時模型的分類邊界已經趨于穩定，符合理論知識。同時，當N=5時，算法從訓練至收斂的過程中，樣本冗余度隨著迭代次數增加而逐漸增加。而當N=10時，在訓練中，其選擇的待標記樣本與已標記樣本冗余度基本均高于N=5時的冗余度，表明當樣本選擇數量持續增大超過一定的范圍后，待標記樣本數量過多，并非其中的每一個樣本都具備差異性，因此導致了樣本冗余度增大。并且當N=10時，隨著迭代次數增加，其樣本冗余度存在忽大忽小的情況，表明此時選取的待標記樣本近乎隨機抽取的效果。綜上所述，綜合考慮算法的準確率和訓練開銷，當樣本選擇數量設置為5時，本文所提的基于改進主動學習的異常檢測算法性能最優。

結合實驗結果分析可得，樣本選擇數量越多，模型穩定需要的迭代次數越少，但當樣本選擇數量過多時，模型訓練的無用數據變多，分類準確率達到穩定的速度反而變慢。由此可知，在一定范圍內增加樣本選擇數量，能夠有效減少算法迭代次數，提高收斂速度。而當樣本選擇數量超過一定閾值后，冗余樣本數量增多，在迭代次數相差無幾的情況下，反而會降低每輪迭代中算法的訓練速度，降低算法運行效率。

綜上所述，本文提出基于改進主動學習的異常檢測算法，綜合考慮了樣本與分類邊界的距離，通過定義樣本間的冗余度和調整樣本選擇數量，提升了樣本選擇的有效性，減少了迭代次數，并且實驗結果表明，相較于傳統算法，本文所提算法收斂更快，在達到相同分類準確率的前提下，需要的樣本數量更少，而在算法收斂后，達到的分類準確率也更高，因此性能更佳，效果更優。

5 結束語

本文提出的基于改進主動學習的異常檢測算法，在傳統SVM的基礎上結合了主動學習的思想，針對傳統的選擇策略僅考慮樣本與分類邊界間距離，而導致運行效率較低的問題，通過綜合定義樣本間的冗余度和調整樣本選擇數量，對傳統的選擇策略進行了改進優化。實驗結果表明，本文提出的基于改進主動學習的異常檢測算法相較于傳統算法所需樣本數量更少，算法準確率更高，適當增加樣本選擇數量減少了算法迭代次數，有效地提高了算法的運行效率。而針對本文尚未對不同大小樣本集的樣本選擇數量進行定量分析的不足，將在后續研究中進一步探明。