適用于ＩＤＳ中數據分類的數值歸約算法

摘要：以提高IDS中數據分類效率為目標，分析了IDS中被檢測數據的特點，設計了一種適用于IDS中數據分類的數值歸約算法(NRAADCI)。該算法一方面用值域來減少特征值數目，另一方面將孤立的點放大為一個區域以預測類似行為。最后以決策樹分類算法為例，通過實驗驗證了該數值歸約算法的有效性。實驗結果表明，該算法在降低已有分類算法的時間復雜度的同時使分類準確率有所提升。

關鍵詞：數據挖掘；入侵檢測系統；分類；數值歸約

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2007)12-0146-03

數據挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數據中發現隱含的、規律性的、人們事先未知的，但又是潛在有用的并且最終可被理解的信息和知識的非平凡過程^[1]。數據挖掘包括關聯分析、分類與預測、聚類分析等功能。其中，分類的目的是找出描述并區分數據類或概念的模型，以便能夠使用模型預測類標記未知的對象類^[2]。

入侵檢測是對入侵行為的發現。IDS過濾網絡數據包，監視主機和應用程序的運行狀態，綜合分析來自網絡、主機、應用程序的檢測信息并及時報警或是自動響應。入侵檢測的第一步是數據的收集，但是收集到的數據是龐大、復雜的，有時候又是冗余、異常的。為了提高檢測效率，需要對數據進行挖掘處理。一個理想的入侵檢測系統應該能夠從足夠多的正常和異常數據中使用分類算法“學”到一個分類器，來標記或預測新的數據的正常或異常。數據挖掘技術在IDS中的典型應用就是用分類算法對這些數據進行挖掘以得到有價值的信息、建立檢測模型。

但是，在IDS的龐大數據源上進行復雜的數據分析和挖掘的時間復雜度和空間復雜度較高。如果利用數據歸約技術將數據集歸約表示，使其變小但仍基本保持原數據集的完整性，那么在歸約后的數據集上挖掘將更有效，并能產生相同或相似的挖掘結果。數據歸約可分為特征歸約、樣本歸約和數值歸約。其中的數值歸約是特征值離散化技術，它將連續型特征的值離散化，形成少量區間，每個區間映射到一個離散符號。

1IDS中被檢測數據的特點及經典分類算法的不足

經典的分類算法包括分類規則、貝葉斯理論、決策樹、SVM以及神經網絡等。以決策樹方法為例，它首先針對訓練集數據利用歸納算法生成可讀的規則和決策樹；然后使用決策樹對新數據進行分析。決策樹的葉節點是類名；中間節點表示在一個特征上的測試，每個分支對應于該特征的一個測試輸出^[2]。建立決策樹的過程(即樹的生長過程)是不斷地把數據進行切分的過程，每次切分對應一個問題，也對應著一個節點；對每個切分都要求分成的組之間的差異最大。常用的決策樹算法有CART、CHAID、ID3、C4.5等。各種決策樹算法之間的主要區別就是對上述組之間的差異的衡量方式的區別。其中的ID3、C4.5是比較流行的算法。ID3算法^[2，3]以自頂向下遞歸的方式構造決策樹，在樹的每個節點上使用信息增益度量選擇測試特征。選擇具有最高信息增益的特征作為當前節點的測試特征，該特征使得對結果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機性。雖然ID3算法所用的基于信息增益的測試特征選擇方法使分類所需的期望測試數目最小，并確保找到一棵簡單的樹，但是這種信息理論方法也有傾向于多值特征這個弊端。因此，ID3也傾向于選擇取值較多的特征，但取值較多的特征不一定是最佳特征；而且偏向具有較多值的特征還可能導致過擬合，在極端的情況下，對于訓練集中的每個元組都有惟一的一個值的特征將被認為是最佳特征。C4.5算法^[4]針對ID3算法存在的不足，通過考慮每個劃分中的勢，用增益比代替增益來改進ID3算法，盡管在應用于單機的決策樹算法中，C4.5算法不僅分類準確率高，而且是速度最快的，但它仍然存在對多值特征的傾向性。

IDS的檢測規則中用于判斷入侵的多為數值型特征。以MIT林肯實驗室的KDD99數據集為例，包括了網絡數據包所能蘊涵的所有信息。從帶有模擬攻擊的原始網絡數據流中采集和處理得到的每個記錄由42個特征組成。其中有38個特征是數值型特征，3個特征是字符型特征，最后一個特征標記該記錄屬于什么攻擊類型。數值型特征的值一般比較多，如duration有2 495個、src_bytes有3 300個、dst_bytes有10 725個、link_count有490個、srv_count有470個、dst_host_count有256個、dst_host_rerror_rate有101個特征值等；也有較少的，如land有2個、is_hot_login有1個、num_failed_logins有6個、num_root有20個特征值等。可見，這些特征的值過于孤立，用決策樹歸納分類算法對這些具體的單點值進行分析，得到的決策規則(if_then)意義不大。更重要的是通過孤立的單點數據得到的決策規則雖然可以很好地判斷曾經發生過的行為。但是不能預測未發生的類似行為。IDS中更多的是要通過已發生的行為數據來預測未發生的行為，傳統的決策樹算法不能直接應用于IDS的數據源上。

2適用于IDS中數據分類的數值歸約算法

為了充分利用決策樹等分類算法的優勢，同時使之能有效地用于IDS的數據分類，本文為分類挖掘算法設計了一個數據預處理算法，即適用于IDS中數據分類的數值歸約算法（NRAADCI）。該算法描述如下：

假設同類型的數值型特征的值具有值域性，即同類行為的特征值具有相似性，不同類行為的特征值具有明顯的分界線。

3．3仿真結果與分析

實驗b)與a)測試結果的比較如表1所示；實驗c)與a)的比較如表2所示。

由表1可以看出，對源數據的特征值進行數值歸約處理后，使得ID3算法的準確率有了一定的提高且生成分類規則的時間復雜度明顯下降；對于C4.5算法來說準確率變化不大，但時間節省了約27.3％。

由表2可以看出，第1.000 1~10萬號測試集的準確率提高不多，因為值域化規則對于該測試集來說數值還是低值域化

的；對于第10.000 1萬號之后的數據記錄是高值域化的，可以看出準確率有明顯的提高。由此也證明了第2章中關于同類型的數值型特征的值具有值域性的假設是正確的。

4結束語

數據挖掘技術能夠幫助決策者在海量數據信息中尋找數據間的潛在聯系、發現被忽略的要素、提取隱藏的信息，輔助決策者進行趨勢預測和行為決策。但是能適合所有領域的數據挖掘算法是不存在的。在具體的應用中，要么需要改進數據挖掘的相關算法以適應數據源的特點，要么需要對數據源進行預處理，使已有的數據挖掘算法能被有效地利用。本文的數值歸約算法對提高數據挖掘在IDS中的應用效果作了有益的研究。

參考文獻：

［1］邵峰晶，于忠清.數據挖掘原理與算法[M].北京: 中國水利水電出版社，2003：126－170.

[2]HAN Jia－wei， KAMBER M. Data mining:concepts and techniques[M].San Francisco: Morgan Kaufmann Publishers Inc， 2001：14－18，188－196.

[3]QUINLAN J R.Induction of decision trees[J].Machine Learning，1986，1(1):81－106.

[4]DUNHAM M H. 數據挖掘教程[M].郭崇慧，田鳳占，靳曉明，等譯. 北京: 清華大學出版社， 2003:79-88.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”