基于參考度的有效關聯規則挖掘*

柳景超,宋勝鋒

(海軍工程大學電子工程學院,武漢 430033)

基于參考度的有效關聯規則挖掘*

柳景超,宋勝鋒

(海軍工程大學電子工程學院,武漢 430033)

針對當前關聯規則挖掘采用的支持度-置信度框架在具體應用中存在的問題,引入新的指標——參考度對模型中關聯規則挖掘算法評價體系進行改進。實驗表明,通過引入參考度,能夠提高挖掘有效規則的效率。

數據挖掘,關聯規則,入侵檢測,參考度

引 言

入侵檢測系統作為一種積極主動的安全防護措施,能夠檢測出各種形式的入侵行為,是安全防護體系的重要組成部分。以數據為中心的入侵檢測實際上是一個數據分析的過程。隨著網絡信息的不斷豐富和帶寬的提高,收集的審計數據和網絡數據包的數量將是非常巨大,要想從海量的審計數據和網絡數據包中發現有意義的信息將變得非常困難。

數據挖掘是從大量數據中抽取出潛在的、有價值的知識的過程。因此,將數據挖掘應用于入侵檢測成為一個很有前途的研究方向[1]。關聯規則挖掘是數據挖掘中一個重要手段,在入侵檢測中發揮了重要作用。本文針對當前關聯規則挖掘采用的支持度-置信度框架在具體應用中存在的問題,引入新的評價指標——參考度對模型中關聯規則挖掘算法評價體系進行改進。實驗表明,通過引入參考度,能夠提高挖掘有效規則的效率。

1 關聯規則

關聯規則挖掘是數據挖掘研究的一個重要分支,其目的就是從海量數據中挖掘出有價值的描述數據項之間相互聯系的有關知識[2]。關聯規則挖掘問題可以分解為以下兩個子問題:

(1)找出所有頻繁項集,即找出的所有項集的支持度滿足用戶所規定的最小支持度;

(2)由頻繁項集構造置信度不低于用戶規定的最小置信度閾值的強關聯規則。

目前通常采用的挖掘算法為 Apriori算法[3]。Ap riori算法對關聯規則的評價指標為支持度和置信度,基于支持度-置信度框架的挖掘算法能夠挖掘出一些有效關聯規則,但在實際應用中可能會產生大量冗余的、起誤導作用的規則。例如:通過對某服務器系統安全日志數據庫D隨機抽取2 000條事務,并對以下 4個數據項集:

I1= {連接服務器 21端口}、I2={拒絕服務攻擊}、I3={提供 www服務}和 I4={開放 80端口 }進行統計、分析:結果如表 1所示。

表1 項目支持數列表

如果假定min sup=20%,min cof=30%,可以挖掘出如下兩個關聯規則:

規則(1)I1?I2(support=40%,con f=80%);

規則 (2)I3? I4(support=60%,con f=100%)。

通過對產生的規則進行分析,可知規則(1)的含義為凡是連接服務器 21端口的行為都是拒絕服務攻擊;規則(2)的含義是提供 www服務的服務器會開放80端口。對于規則(1)來說,顯然是一個錯誤的規則,如果規則庫加入這一規則將會增大系統的誤報率影響整個入侵檢測系統的準確性;而規則(2)盡管是一個正確的規則,但這是一個眾所周知的事實,對于檢測入侵行為而言沒有實際意義,這樣的規則加入到規則庫,將會增加入侵檢測系統搜索規則庫的時間,降低檢測效率。

2 引入新的指標改進關聯規則評價體系

為了避免生成大量冗余甚至是具有誤導作用的關聯規則,一些文章曾引入諸多閾值以加強對關聯規則的評判[4-6]。在對該問題進行深入研究的基礎上,引入參考度來提高關聯規則的有效性。

定義1:參考度。對于關聯規則X?Y,其參考度為:

其中,P(X)表示X出現的概率,P(Y)表示Y出現的概率,P(XY)表示X、Y同時出現的概率,P()表示X不出現的概率,PY)表示、Y同時出現的概率。

當某一項集支持度為 1時,通常認為它與其他任何項集之間不具有相關性,則不需要考慮該項集與其它項集之間的參考度。任何一個項集X出現的概率為 0＜P(X)＜1。 由于 0＜P(Y/X),P(Y/)≤1,所以參考度的取值范圍 [-1,1]。

為了進一步說明參考度的有效性,有必要給出相關度[7]的概念。從概率的角度定義相關度:

則由式(1)～式(3)可以得到:

分析式(4)可知,參考度的定義不僅包含了相關度的因素,而且還考慮了P(Y)的因素。因此,引入參考度可以充分體現規則X?Y的有效性。

當 corr=corr1時,corr=corr1=1,即如果 X、Y不相關 ,則也不相關;當 corr＞ 1時,corr1＜ 1,即如果X、Y具有正相關性,Y具有負相關性;當corr＜1時,corr1＞ 1,也即是如果X、Y是負相關,說明X的發生對Y的發生起抑制作用。此時,X?Y為無意義的規則應丟棄;同時考慮其反面規則。

與支持度、置信度類似,參考度也有閾值,稱之為最小參考度,記為m in consult。可以通過確定最小參考度來重新定義強關聯規則。

定義 2:強關聯規則。事務庫D上的關聯規則X?Y,如果滿足最小支持度、最小置信度和最小參考度的閾值,則認為是用戶感興趣的規則,即強關聯規則。

引入參考度之后,可以將關聯規則分為以下幾種情況:

(1)有效的關聯規則,即用戶感興趣的規則,此時該規則滿足最小支持度、最小置信度,且 consult＞0;

(2)冗余規則,即滿足最小支持度、最小置信度,且consult=0的規則;

(3)負關聯規則,即滿足最小支持度、最小置信度,且 consult＜0的規則,此時其反面規則可能為感興趣規則,應加以考慮。

在新的評價體系支持度-置信度-參考度框架下,關聯規則的挖掘工作分為以下 4個步驟:

(1)利用 Ap riori算法,找出事務數據庫D中所有頻繁項集L;

(2)對步驟(1)產生的所有頻繁項集 l∈ L,產生所有滿足置信度、參考度的關聯規則,并加入到關聯規則集合R中;

(3)對于步驟(2)中參考度小于0的所有頻繁項集 l∈ L,考慮其反面規則,產生所有滿足支持度、置信度、參考度的反面規則(?Y),并加入到關聯規則集合R中;

(4)輸出關聯規則集合 R。

對于第(3)步,要計算其反面規則的相關閾值,即對于反面規則?Y需要作以下運算:

通過上述的推導過程可以得出,反面規則的相關閾值均可以利用步驟(2)中求出的結果計算得到,無需再對事務庫進行掃描。

下面仍以表 1為例,在引入參考度的情況下重新挖掘這兩條規則,設min consult=0.6。對于規則(1),計算其參考度為:

同樣舍棄。

通過分析,可以得到以下結果:規則(1)及反面規則均不是強關聯規則,即是否連接服務器 21端口不是判斷拒絕服務攻擊的一個主要標志;而對于規則(2),盡管不會對檢測效果產生誤導,但由于這條規則實際意義不大,增加該規則會降低系統工作效率,因此引入新的評價指標后同樣將其舍棄。

3 實驗分析

為了驗證引進的第三個指標——參考度對結果產生的影響,以 KDD Cup 1999 Data[8]為數據集,進行實驗分析。KDD Cup 1999 Data是在軍事網絡環境中運用非常廣泛的模擬入侵攻擊所得到的網絡數據集,是為第三屆國際知識發現和數據挖掘競賽提供的。在實驗過程中選取2 000條記錄作為測試數據集。實驗所使用的硬件平臺是 Pentium4 3.00 GHz處理器,512 M內存和 80 G硬盤的 PC機,操作系統為Window s XP。

設定最小支持度為15%,最小置信度為80%,在不同的參考度下,統計產生的規則數目。結果如圖1所示。

圖 1表明,算法產生的規則數隨著參考度閾值的增加而遞減,因為隨著參考度的增大,越來越多的規則被淘汰。由此可以看出,加入新的評價指標——參考度來控制產生關聯規則的質量是可行的,而且給系統帶來極大好處。

圖 1 參考度閾值-規則數關系圖

4 結束語

關聯規則挖掘作為數據挖掘中的一個重要手段在入侵檢測中發揮了重要作用。本文針對當前關聯規則挖掘采用的支持度-置信度框架在具體應用中存在的問題,引入新的評價指標——參考度對模型中關聯規則挖掘算法評價體系進行改進。實驗表明,通過引入參考度,能夠提高挖掘有效規則的效率。

[1] Lee W.A Data M ining Framew ork for Construc ting Features and M odels for Intrusion Detec tion Systems[D].New York Co lumbia University,1999.

[2] Agrawal R,Im ielinske T, Swam i A. M ining Association Rules Betw een Sets o f Items in Large Databases[C]//Proc. o f the ACM SIGMOD International Con ference on the M anagement of Data.W ashington D.C,1993,5:207-216.

[3] Agrawal R,Srikant R.Fast Algorithms for M ining Association Rules[R].Reaearch Re-port RJ9893,IBM Almaden Research Center,San Jose,California,1994.

[4] 伊衛國,衛金茂,王名揚.挖掘有效的關聯規則[J].計算機工程與科學,2005,32(27):91-94.

[5] 吳良杰,劉紅祥.基于確信因子的有效關聯規則挖掘[J].計算機工程與應用,2004,40(32):187-189.

[6] 羅 可,郗東妹.采掘有效的關聯規則 [J].小型微型計算機系統,2005,25(26):1374-1379.

[7] 李 鵬.數據挖掘在入侵檢測中的應用研究[D].鄭州:解放軍信息工程大學,2004.

[8] KDD Cup 1999 Data[EB/OL].h ttp://kdd.ics.uci.edu/databases/kddcup99/kddcup99.htm l.

M ining Efficient Association Ru les Based on Consult

LIU Jing-chao,SONG Sheng-feng
(College of Electronic Engineering,N ava l University o f Engineering,Wuhan 430033,China)

Peop le find that generated association rules may be false or redundant when using the traditional evaluating indicator. The article introduces the new measure-consu lt to imp rove measure system ofmining algorithm.The experiments show that the efficiency of valid rules can be enhanced by adding the new measure.

datam ining,association rules,intrusion detection,measure-consult

TP393.08,TP311.13

A

1002-0640(2011)05-0079-03

2010-01-08

2010-04-05

湖北省自然科學基金資助項目(2006ABA 009)

柳景超(1979- ),女 ,河南周口人,碩士,講師,研究方向:數據挖掘,入侵檢測。