樸素貝葉斯分類在入侵檢測中的應用

論文類別:理學論文 > 統計學論文
論文作者: 鐘慰 周鐵軍
上傳時間:2008/5/1 15:49:00

摘 要 貝葉斯分類能高效地處理大型數據,本文使用核密度估計的樸素貝葉斯分類來进行入侵檢測。由於入侵檢測審計数據屬性多為連續變量,所以在貝葉斯分類算法中使用核密度估計,有助於提高分類的精度,另引入對稱不確定方法有效地刪除不相關的檢測属性,進一步提高分類效率。
  關鍵字 貝葉斯;核密度;入侵檢測;分类

1 前言

  在入侵檢测系統中,為了提高系統的性能,包括降低誤報率和漏報率,縮短反應时間等,學者們引入了許多方法,如專家系統、神經网絡、遺傳算法和數據挖掘中的聚類,分類等各種算法。例如:Cooper & Herkovits提出的一種基於貪心算法的貝葉斯信念網絡,而Provan & Singh Provan,G.M & Singh M和其他學者報告了這種方法的優點。貝叶斯網絡說明聯合條件概率分布,為機器學習提供一種因果关系的圖形,能有效的處理某些問題,如診斷:貝葉斯网絡能正確的處理不確定和有噪聲的问題,這類問題在任何檢測任務中都很重要。
  然而,在分類算法的比較研究發現,一種稱作樸素貝叶斯分類的簡單貝葉斯算法給人印象更為深刻。盡管樸素貝葉斯的分類器有個很簡單的假定,但從現實数據中的實驗反復地表明它可以與決定樹和神經網絡分類算法相媲美[1]
  在本文中,我們研究樸素貝葉斯分類算法,用來檢測入侵審計數據,旨在開發一種更有效的,檢驗更加準确的算法。

2 貝葉斯分类器

  貝葉斯分類是統計學分類方法。它們可以預測類成員關系的可能性,如給定樣本屬於一個特定類的概率。
  樸素貝葉斯分類[2]假定了一个屬性值對給定類的影響獨立於其它屬性的值,這一假定稱作類条件獨立。
  設定數據樣本用一個 n 維特征向量X={x1,x2,,xn}表示,分別描述對n 個屬性A1,A2,,An樣本的 n 個度量。假定有m個類 C1,C2,,Cm 。給定一個未知的數據樣本 X(即沒有類標號),樸素貝葉斯分類分類法將預測 X 屬於具有最高後驗概率(條件 X 下)的類,當且僅當P(Ci | X)> P(Cj | X),1≤j≤m,j≠i 这樣,最大化P(Ci | X)。其中P(Ci | X)最大类Ci 稱為最大後驗假定,其原理為貝葉斯定理:
朴素贝叶斯分类在入侵检测中的应用              公式(1)
  由於P(X) 對於所有類为常數,只需要P(X | Ci)P(Ci)最大即可。並據此對P(Ci| X)最大化。否則,最大化P(X | Ci)P(Ci)。如果給定具有許多屬性的數據集,計算P(X | Ci)P(Ci)的開銷可能非常大。為降低計算P(X| Ci )的開銷,可以做类條件獨立的樸素假定。給定樣本的類標號,假定屬性值相互條件獨立,即在屬性间,不存在依賴關系,这樣,
朴素贝叶斯分类在入侵检测中的应用      公式(2)
  概率朴素贝叶斯分类在入侵检测中的应用,可以由訓練樣本估值:
  (1) 如果Ak是分类屬性,則P(xk|Ci)=sik/si其中sik是Ak上具有值xk的類Ci的訓練樣本數,而si是Ci中的訓練樣本數。
  (2) 如果Ak是連续值屬性,則通常假定該屬性服從高斯分布。因而
朴素贝叶斯分类在入侵检测中的应用           公式(3)
  其中,給定类Ci的訓練樣本屬性Ak的值,朴素贝叶斯分类在入侵检测中的应用 是屬性Ak的高斯密度函数,而 分別為平均值和標準差。
  樸素貝葉斯分類算法(以下稱為NBC)具有最小的出錯率。然而,實践中並非如此,這是由於對其應用假定(如類條件獨立性)的不確定性,以及缺乏可用的概率數据造成的。主要表現為:
  ①不同的檢測屬性之間可能存在依賴關系,如protocol_type,src_bytes和dst_bytes三種屬性之間總會存在一定的聯系;
  ②當連續值屬性分布是多态時,可能產生很明顯的問題。在这種情況下,考慮分類問題涉及更加廣泛,或者我們在做數據分析時應該考慮另一種數据分析。
後一種方法我們將在以下章節詳細討论。

3 樸素貝叶斯的改進:核密度估計

  核密度估計是一種普便的樸素貝葉斯方法,主要解決由每個連續值屬性设為高斯分布所產生的問题,正如上一節所提到的。在[3]文中,作者認為連續屬性值更多是以核密度估計而不是高斯估計。
樸素貝葉斯核密度估計分類算法(以下称K-NBC)十分类似如NBC,除了在計算連續屬性的概率 朴素贝叶斯分类在入侵检测中的应用時:NBC是使用高斯密度函數朴素贝叶斯分类在入侵检测中的应用來評估该屬性,而K-NBC正如它的名字所說得一樣,使用高斯核密度函數來評估屬性。它的標準核密度公式為
朴素贝叶斯分类在入侵检测中的应用            公式(4)
  其中h=σ 稱為核密度的帶寬,K=g(x,0,1) ,定義為非負函數。這樣公式(4)變形為公式(5)
朴素贝叶斯分类在入侵检测中的应用               公式(5)
  在K-NBC中采用高斯核密度為數據分析,這是因為高斯密度有著更理想的曲線特點。圖1說明了實際數據的概率分布更接近高斯核密度曲線。
  圖1 兩種不同的概率密度對事務中數據的評估,其中黑線代表高斯密度,虚線為核估計密度並有两個不同值的帶寬樸素貝葉斯算法在计算μc和σc時,只需要存儲觀測值xk的和以及他們的平方和,這對一個正態分布來說是已經足夠了。而核密度在訓練過程中需要存儲每一個连續屬性的值(在學習過程中,對名词性屬性只需要存儲它在樣本中的頻率值,這一點和樸素貝葉斯算法一樣)。而為事例分類時,在計算連續值屬性的概率 時,朴素貝葉斯算法只需要評估g一次,而核密度估計算法需要對每个c類中屬性X每一個觀察值進行n次評估,這就增加計算存儲空間和時間復杂度,表1中對比了兩種方法的时間復雜度和內存需求空間。

4 實驗研究與結果分析

  本节的目標是評價我們提出核密度評估分類算法對入侵审計數據分類的效果,主要從整體檢測率、檢測率和誤檢率上來分析。
表1 在給定n條訓練事務和m個檢測屬性条件下,
NBC和K-NBC的算法復雜度
樸素貝葉斯
核密度
 時間
空間
時间
空間
具有n條事务的訓練數據
O(nm)
O(m)
O(nm)
O(nm)
具有q條事務的測試數據
O(qm)
O(qnm)

4.1 實驗建立

  在實驗中,我們使用NBC与K-NBC進行比較。另观察表1兩種算法的复雜度,可得知有效的減少檢測屬性,可以提高他們的运算速度,同時刪除不相關的檢測屬性還有可以提高分類效率,本文將在下一節詳細介紹對称不確定方法[4]如何對入侵審計數據的預處理。我們也會在實驗中進行對比分析。
  我們使用WEKA來进行本次實驗。采用 KDDCUP99[5]中的數据作為入侵檢測分類器的訓練樣本集和測試樣本集,其中每個記錄由41個離散或连續的屬性(如:持續時間,協议類型等)來描述,並标有其所屬的類型(如:正常或具體的攻擊類型)。所有數據分類23類,在這裏我们把這些類網絡行為分為5大類网絡行為(Normal、DOS、U2R、R2L、Probe)。
  在實验中,由於KDDCUP99有500多萬條記錄,為了處理的方便,我們均勻從kddcup.data.gz 中按照五類網絡行為抽取了5萬條數據作为訓練樣本集,並把他們分成5組,每組數據為10000条,其中normal數據占據整組數據中的98.5%,這一點符合真實環境中正常数據遠遠大於入侵數據的比例。我們首
免費論文下載中心 http://www.hi138.com 先檢測一组數據中只有同類的入侵的情況,共4組數據(DOS中的neptune,Proble中的Satan,U2R中的buffer_ overflow,R2l中的guess_passwd),再檢測一組數據中有各种類型入侵數據的情況。待分類器得到良好的訓練後,再从KDD99數據中抽取5組數據作為測試樣本,分別代表Noraml-DOS,Normal-Probe,Normal-U2R,Normal-R2L,最後一組為混後型数據,每組數據為1萬條。

4.2 數據的預處理 

  由於樸素貝葉斯有個假定,即假定所有待測属性對給定類的影響獨立於其他属性的值,然而現實中的數據不總是如此。因此,本文引入對稱不確定理論來對數據進行預处理,刪除數據中不相關的屬性。
  對稱不確定理論是基於信息概念論,首先我們先了解一下信息理論念,屬性X的熵為:
朴素贝叶斯分类在入侵检测中的应用           公式(6)
  給定一个觀察變量Y,變量X的熵為:
朴素贝叶斯分类在入侵检测中的应用     公式(7)
  P(xi )是變量X所有值的先驗概率,P(xi|yi )是給定觀察值Y,X的後驗概率。這些隨著X熵的降低反映在條件Y下,X額外的信息,我們稱之為信息增益,
朴素贝叶斯分类在入侵检测中的应用              公式(8)
  按照這個方法,如果IG(X|Y)>IG(X|Y),那麽屬性Y比起屬性Z來,與屬性X相關性更強。
定理:對兩個隨機變量來說,它们之間的信息增益是對稱的。即
朴素贝叶斯分类在入侵检测中的应用 公式(9)
  對測量屬性之間相关性的方法來說,對称性是一種比較理想的特性。但是在計算有很多值的屬性的信息增益时,結果會出現偏差。而且為了確保他們之間可以比較,必須使這些值离散化,同樣也會引起偏差。因此我們引入對稱不確定性,
朴素贝叶斯分类在入侵检测中的应用         公式(10)
  通過以下兩个步驟來選擇好的屬性:
  ①計算出所有被測屬性與class的SU值,並把它們按降序方式排列;
  ②根據設定的閾值刪除不相关的屬性。
  最後決定一個最優閾值δ,這裏我們通過分析NBC和K-NBC計算結果來取值。

4.3 實驗結果及分析

  在試驗中,以記錄正確分類的百分比作為分類效率的評估標准,表2為兩種算法的分类效率。

表2 對應相同入侵類型數据進行檢測的結果
數據集
算法
DOS
(neptune)
Proble
(satan)
R2L
( guess_passwd)
U2R
(buffer_overflow)
檢測率
誤檢率
整體檢測率
檢測率
误檢率
整體檢測率
檢測率
誤檢率
整體檢測率
檢测率
誤检率
整體检測率
NBC
99.5
0.2
99.79
98.3
0.1
99.84
97.3
0.8
99.2
95
1.8
98.21
K-NBC
99.5
0.2
99.96
98.3
0
99.96
97.3
0.2
99.81
71
0.1
99.76
SU+NBC
99.5
0
99.96
98.3
0.1
99.85
98
0.7
99.24
9
1.1
98.84
SU+K-NBC
99.5
0
99.96
98.3
0
99.96
98.7
0.2
99.76
85
0.1
99.81

  根据表2四組不同類別的入侵檢測結果,我們從以下三個方面分析:
  (1)整體檢測率。K-NBC的整體檢測率要比NBC高,這是因為K-NBC在對normal这一類數據的檢測率要比NBC高,而normal這一類數據又占整個检測數據集數的95%以上,这也說明了在上一節提到的normal類的數據分布曲線更加接近核密度曲線。
  (2)檢測率。在對DOS和PROBLE這两組數據檢測結果,兩個算法的检測率都相同,這是因為這兩类入侵行為在實現入侵中占絕大部分,而且這一類数據更容易檢測,所以兩種算法的檢測效果比較接近;針對 R2L檢測,從表2可以看到,在沒有進行數據預處理之前,兩者的的檢測率相同,但經過數據預處理後的兩個算法的檢測率都有了提高,而K-NBC的效率比NBC更好點;而對U2R的檢測结果,K-NBC就比NBC差一點,經過數據預處理后,K-NBC的檢測率有一定的提高,但還是比NBC的效果差一些。
  (3)誤檢率。在DOS和Proble這兩種組數據的誤檢率相同,在其他兩組數據的中,K-NBC的誤檢率都比NBC的低。
  根據表3的结果分析,我們也可以看到的檢測结果與表2的分組檢測的結果比较類似,並且從綜合角度來說,K-NBC檢測效果要比NBC的好。在這裏,我們也發現,两種算法對R2L和U2L這兩類入侵的檢測效果要比DOS和Proble這兩類入侵的差。這主要是因為這两類入侵屬於入侵行為的稀有類,检測難度也相應加大。在KDD99競賽中,冠軍方法對這兩類的檢測效果也是最差的。但我們可以看到NBC對這種稀有類的入侵行为檢測更為準確一點,這應該是稀有类的分布更接近正態分布。
從上述各方面綜合分析,我们可以證明K-NBC作為的入侵檢测分類算法的是有其优越性的。

表3 對混合入侵類型數據进行檢測的結果
數據集
算法
整體檢測
分類檢測
Normal
Dos
Proble
R2L
U2R
檢測率
誤檢率
檢测率
誤檢率
檢測率
誤檢率
檢測率
誤檢率
檢測率
誤檢率
檢測率
誤檢率
NBC
98.14
1.8
98.2
0.8
99.8
0
99.8
0
90
0
86.7
1.8
K-NBC
99.78
0.2
99.8
2.3
99.8
0
99.8
0
96
0
73.3
0.1
SU+NBC
97.99
2.0
98
0.8
99.8
0
99.8
0
90
0
86.7
1.9
SU+K-NBC
99.79
0.2
99.8
1.9
99.8
0
99.8
0
96
0
80
0.1

5 結論

  在本文中,我們用高斯核密度函數代替樸素貝葉斯中的高斯函數,建立K-NBC分類器,對入侵行為進行檢測,另我們使用對稱不確定方法來刪除檢測數據的中與類不相關的屬性,從而進一步改进核密度樸素貝葉斯的分類效率,实驗表明,對預處理後的审計數據,再結合K-NBC來檢測,可以達到更好的分類效果,具有很好的實用性。同時我們也註意到,由於入侵檢測的數據中的入侵行為一般為稀有類,特別是對R2L和U2R這兩類數據進行檢測时,NBC有著比較理想的結果,所以在下一步工作中,我們看是否能把NBC和K-NBC这兩種分類模型和優點聯合起來,並利用對稱不确定理論來刪除檢測數據与類相關的屬性中的冗余屬性,進一步提高入侵檢測效率。

參考文獻

[1]Langley. P.,Iba,W. &Thompson,K. An analysis of Bayesian classifiers [A],in “Proceedings of the Tenth National Conference on Artificial Intelligence” [C] Menlo Park,1992. 223-228
[2]Han J.,Kamber M.. 數據挖掘概念與技術[M]. 孟小峰,等譯. 北京:機械工業出版社. 2005. 196 201
[3]John G.H.. Enhancements to the Data Mining Process [D]. Ph.D. Thesis,Computer Science Dept.,Stanford University,1997
[4]Lei Yu and Huan Liu. Feature selection for high- dimensional data:A fast correlation-based filter solution[A],in “Proceedings of the Twentieth International Conference on Machine Learning (ICML 2003)”[C] Washington,DC,2003. 856-863
[5]KDD99.KDD99 Cup Dataset [DB/OL]. http://kdd.ics.uci.edu/databases/kddcup99,1999
免費論文下載中心 http://www.hi138.com
下载论文

論文《樸素貝葉斯分類在入侵檢測中的應用》其它版本

統計學論文服務

網站聲明 | 聯系我們 | 網站地圖 | 論文下載地址 | 代寫論文 | 作者搜索 | 英文版 | 手機版 CopyRight@2008 - 2017 免費論文下載中心 京ICP备17062730号