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

蔡 穎，陳偉榮

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

0 引 言

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

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

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

1 主動學習

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

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

圖1 主動學習流程

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

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

2.1 樣本冗余度

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

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

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

(1)

(2)

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

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

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

2.2 算法描述

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

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

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

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

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

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

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

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

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

(6) 返回C

3 實驗數(shù)據(jù)處理

3.1 數(shù)據(jù)源

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

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

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

3.2 數(shù)據(jù)預處理

3.2.1 數(shù)值化處理

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

3.2.2 標準化處理

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

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

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

(3)

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

(4)

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

(5)

3.2.3 歸一化處理

此處歸一化的目的是讓數(shù)據(jù)壓縮在 [0,1] 范圍內(nèi)。數(shù)據(jù)歸一化處理步驟如下：

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

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

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

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

(6)

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

(7)

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

3.2.4 特征選取

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

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

4 實驗結(jié)果及分析

4.1 實驗設計

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

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

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

4.2 實驗結(jié)果分析

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

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

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

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

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

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

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

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

圖3 冗余度隨樣本選擇數(shù)量的變化

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

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

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

5 結(jié)束語

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