適用于ＩＤＳ中數(shù)據(jù)分類的數(shù)值歸約算法

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

關(guān)鍵詞：數(shù)據(jù)挖掘；入侵檢測系統(tǒng)；分類；數(shù)值歸約

中圖分類號：TP301文獻(xiàn)標(biāo)志碼：A

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

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

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

但是，在IDS的龐大數(shù)據(jù)源上進(jìn)行復(fù)雜的數(shù)據(jù)分析和挖掘的時間復(fù)雜度和空間復(fù)雜度較高。如果利用數(shù)據(jù)歸約技術(shù)將數(shù)據(jù)集歸約表示，使其變小但仍基本保持原數(shù)據(jù)集的完整性，那么在歸約后的數(shù)據(jù)集上挖掘?qū)⒏行В⒛墚a(chǎn)生相同或相似的挖掘結(jié)果。數(shù)據(jù)歸約可分為特征歸約、樣本歸約和數(shù)值歸約。其中的數(shù)值歸約是特征值離散化技術(shù)，它將連續(xù)型特征的值離散化，形成少量區(qū)間，每個區(qū)間映射到一個離散符號。

1IDS中被檢測數(shù)據(jù)的特點(diǎn)及經(jīng)典分類算法的不足

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

IDS的檢測規(guī)則中用于判斷入侵的多為數(shù)值型特征。以MIT林肯實(shí)驗(yàn)室的KDD99數(shù)據(jù)集為例，包括了網(wǎng)絡(luò)數(shù)據(jù)包所能蘊(yùn)涵的所有信息。從帶有模擬攻擊的原始網(wǎng)絡(luò)數(shù)據(jù)流中采集和處理得到的每個記錄由42個特征組成。其中有38個特征是數(shù)值型特征，3個特征是字符型特征，最后一個特征標(biāo)記該記錄屬于什么攻擊類型。數(shù)值型特征的值一般比較多，如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個特征值等。可見，這些特征的值過于孤立，用決策樹歸納分類算法對這些具體的單點(diǎn)值進(jìn)行分析，得到的決策規(guī)則(if_then)意義不大。更重要的是通過孤立的單點(diǎn)數(shù)據(jù)得到的決策規(guī)則雖然可以很好地判斷曾經(jīng)發(fā)生過的行為。但是不能預(yù)測未發(fā)生的類似行為。IDS中更多的是要通過已發(fā)生的行為數(shù)據(jù)來預(yù)測未發(fā)生的行為，傳統(tǒng)的決策樹算法不能直接應(yīng)用于IDS的數(shù)據(jù)源上。

2適用于IDS中數(shù)據(jù)分類的數(shù)值歸約算法

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

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

3．3仿真結(jié)果與分析

實(shí)驗(yàn)b)與a)測試結(jié)果的比較如表1所示；實(shí)驗(yàn)c)與a)的比較如表2所示。

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

由表2可以看出，第1.000 1~10萬號測試集的準(zhǔn)確率提高不多，因?yàn)橹涤蚧?guī)則對于該測試集來說數(shù)值還是低值域化

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

4結(jié)束語

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

參考文獻(xiàn)：

［1］邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法[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. 數(shù)據(jù)挖掘教程[M].郭崇慧，田鳳占，靳曉明，等譯. 北京: 清華大學(xué)出版社， 2003:79-88.

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