基于參考度的有效關(guān)聯(lián)規(guī)則挖掘*

柳景超,宋勝鋒

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

基于參考度的有效關(guān)聯(lián)規(guī)則挖掘*

柳景超,宋勝鋒

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

針對(duì)當(dāng)前關(guān)聯(lián)規(guī)則挖掘采用的支持度-置信度框架在具體應(yīng)用中存在的問題,引入新的指標(biāo)——參考度對(duì)模型中關(guān)聯(lián)規(guī)則挖掘算法評(píng)價(jià)體系進(jìn)行改進(jìn)。實(shí)驗(yàn)表明,通過引入?yún)⒖级?能夠提高挖掘有效規(guī)則的效率。

數(shù)據(jù)挖掘,關(guān)聯(lián)規(guī)則,入侵檢測(cè),參考度

引 言

入侵檢測(cè)系統(tǒng)作為一種積極主動(dòng)的安全防護(hù)措施,能夠檢測(cè)出各種形式的入侵行為,是安全防護(hù)體系的重要組成部分。以數(shù)據(jù)為中心的入侵檢測(cè)實(shí)際上是一個(gè)數(shù)據(jù)分析的過程。隨著網(wǎng)絡(luò)信息的不斷豐富和帶寬的提高,收集的審計(jì)數(shù)據(jù)和網(wǎng)絡(luò)數(shù)據(jù)包的數(shù)量將是非常巨大,要想從海量的審計(jì)數(shù)據(jù)和網(wǎng)絡(luò)數(shù)據(jù)包中發(fā)現(xiàn)有意義的信息將變得非常困難。

數(shù)據(jù)挖掘是從大量數(shù)據(jù)中抽取出潛在的、有價(jià)值的知識(shí)的過程。因此,將數(shù)據(jù)挖掘應(yīng)用于入侵檢測(cè)成為一個(gè)很有前途的研究方向[1]。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中一個(gè)重要手段,在入侵檢測(cè)中發(fā)揮了重要作用。本文針對(duì)當(dāng)前關(guān)聯(lián)規(guī)則挖掘采用的支持度-置信度框架在具體應(yīng)用中存在的問題,引入新的評(píng)價(jià)指標(biāo)——參考度對(duì)模型中關(guān)聯(lián)規(guī)則挖掘算法評(píng)價(jià)體系進(jìn)行改進(jìn)。實(shí)驗(yàn)表明,通過引入?yún)⒖级?能夠提高挖掘有效規(guī)則的效率。

1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的一個(gè)重要分支,其目的就是從海量數(shù)據(jù)中挖掘出有價(jià)值的描述數(shù)據(jù)項(xiàng)之間相互聯(lián)系的有關(guān)知識(shí)[2]。關(guān)聯(lián)規(guī)則挖掘問題可以分解為以下兩個(gè)子問題:

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

(2)由頻繁項(xiàng)集構(gòu)造置信度不低于用戶規(guī)定的最小置信度閾值的強(qiáng)關(guān)聯(lián)規(guī)則。

目前通常采用的挖掘算法為 Apriori算法[3]。Ap riori算法對(duì)關(guān)聯(lián)規(guī)則的評(píng)價(jià)指標(biāo)為支持度和置信度,基于支持度-置信度框架的挖掘算法能夠挖掘出一些有效關(guān)聯(lián)規(guī)則,但在實(shí)際應(yīng)用中可能會(huì)產(chǎn)生大量冗余的、起誤導(dǎo)作用的規(guī)則。例如:通過對(duì)某服務(wù)器系統(tǒng)安全日志數(shù)據(jù)庫D隨機(jī)抽取2 000條事務(wù),并對(duì)以下 4個(gè)數(shù)據(jù)項(xiàng)集:

I1= {連接服務(wù)器 21端口}、I2={拒絕服務(wù)攻擊}、I3={提供 www服務(wù)}和 I4={開放 80端口 }進(jìn)行統(tǒng)計(jì)、分析:結(jié)果如表 1所示。

表1 項(xiàng)目支持?jǐn)?shù)列表

如果假定min sup=20%,min cof=30%,可以挖掘出如下兩個(gè)關(guān)聯(lián)規(guī)則:

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

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

通過對(duì)產(chǎn)生的規(guī)則進(jìn)行分析,可知規(guī)則(1)的含義為凡是連接服務(wù)器 21端口的行為都是拒絕服務(wù)攻擊;規(guī)則(2)的含義是提供 www服務(wù)的服務(wù)器會(huì)開放80端口。對(duì)于規(guī)則(1)來說,顯然是一個(gè)錯(cuò)誤的規(guī)則,如果規(guī)則庫加入這一規(guī)則將會(huì)增大系統(tǒng)的誤報(bào)率影響整個(gè)入侵檢測(cè)系統(tǒng)的準(zhǔn)確性;而規(guī)則(2)盡管是一個(gè)正確的規(guī)則,但這是一個(gè)眾所周知的事實(shí),對(duì)于檢測(cè)入侵行為而言沒有實(shí)際意義,這樣的規(guī)則加入到規(guī)則庫,將會(huì)增加入侵檢測(cè)系統(tǒng)搜索規(guī)則庫的時(shí)間,降低檢測(cè)效率。

2 引入新的指標(biāo)改進(jìn)關(guān)聯(lián)規(guī)則評(píng)價(jià)體系

為了避免生成大量冗余甚至是具有誤導(dǎo)作用的關(guān)聯(lián)規(guī)則,一些文章曾引入諸多閾值以加強(qiáng)對(duì)關(guān)聯(lián)規(guī)則的評(píng)判[4-6]。在對(duì)該問題進(jìn)行深入研究的基礎(chǔ)上,引入?yún)⒖级葋硖岣哧P(guān)聯(lián)規(guī)則的有效性。

定義1:參考度。對(duì)于關(guān)聯(lián)規(guī)則X?Y,其參考度為:

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

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

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

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

分析式(4)可知,參考度的定義不僅包含了相關(guān)度的因素,而且還考慮了P(Y)的因素。因此,引入?yún)⒖级瓤梢猿浞煮w現(xiàn)規(guī)則X?Y的有效性。

當(dāng) corr=corr1時(shí),corr=corr1=1,即如果 X、Y不相關(guān) ,則也不相關(guān);當(dāng) corr＞ 1時(shí),corr1＜ 1,即如果X、Y具有正相關(guān)性,Y具有負(fù)相關(guān)性;當(dāng)corr＜1時(shí),corr1＞ 1,也即是如果X、Y是負(fù)相關(guān),說明X的發(fā)生對(duì)Y的發(fā)生起抑制作用。此時(shí),X?Y為無意義的規(guī)則應(yīng)丟棄;同時(shí)考慮其反面規(guī)則。

與支持度、置信度類似,參考度也有閾值,稱之為最小參考度,記為m in consult?？梢酝ㄟ^確定最小參考度來重新定義強(qiáng)關(guān)聯(lián)規(guī)則。

定義 2:強(qiáng)關(guān)聯(lián)規(guī)則。事務(wù)庫D上的關(guān)聯(lián)規(guī)則X?Y,如果滿足最小支持度、最小置信度和最小參考度的閾值,則認(rèn)為是用戶感興趣的規(guī)則,即強(qiáng)關(guān)聯(lián)規(guī)則。

引入?yún)⒖级戎?可以將關(guān)聯(lián)規(guī)則分為以下幾種情況:

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

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

(3)負(fù)關(guān)聯(lián)規(guī)則,即滿足最小支持度、最小置信度,且 consult＜0的規(guī)則,此時(shí)其反面規(guī)則可能為感興趣規(guī)則,應(yīng)加以考慮。

在新的評(píng)價(jià)體系支持度-置信度-參考度框架下,關(guān)聯(lián)規(guī)則的挖掘工作分為以下 4個(gè)步驟:

(1)利用 Ap riori算法,找出事務(wù)數(shù)據(jù)庫D中所有頻繁項(xiàng)集L;

(2)對(duì)步驟(1)產(chǎn)生的所有頻繁項(xiàng)集 l∈ L,產(chǎn)生所有滿足置信度、參考度的關(guān)聯(lián)規(guī)則,并加入到關(guān)聯(lián)規(guī)則集合R中;

(3)對(duì)于步驟(2)中參考度小于0的所有頻繁項(xiàng)集 l∈ L,考慮其反面規(guī)則,產(chǎn)生所有滿足支持度、置信度、參考度的反面規(guī)則(?Y),并加入到關(guān)聯(lián)規(guī)則集合R中;

(4)輸出關(guān)聯(lián)規(guī)則集合 R。

對(duì)于第(3)步,要計(jì)算其反面規(guī)則的相關(guān)閾值,即對(duì)于反面規(guī)則?Y需要作以下運(yùn)算:

通過上述的推導(dǎo)過程可以得出,反面規(guī)則的相關(guān)閾值均可以利用步驟(2)中求出的結(jié)果計(jì)算得到,無需再對(duì)事務(wù)庫進(jìn)行掃描。

下面仍以表 1為例,在引入?yún)⒖级鹊那闆r下重新挖掘這兩條規(guī)則,設(shè)min consult=0.6。對(duì)于規(guī)則(1),計(jì)算其參考度為:

同樣舍棄。

通過分析,可以得到以下結(jié)果:規(guī)則(1)及反面規(guī)則均不是強(qiáng)關(guān)聯(lián)規(guī)則,即是否連接服務(wù)器 21端口不是判斷拒絕服務(wù)攻擊的一個(gè)主要標(biāo)志;而對(duì)于規(guī)則(2),盡管不會(huì)對(duì)檢測(cè)效果產(chǎn)生誤導(dǎo),但由于這條規(guī)則實(shí)際意義不大,增加該規(guī)則會(huì)降低系統(tǒng)工作效率,因此引入新的評(píng)價(jià)指標(biāo)后同樣將其舍棄。

3 實(shí)驗(yàn)分析

為了驗(yàn)證引進(jìn)的第三個(gè)指標(biāo)——參考度對(duì)結(jié)果產(chǎn)生的影響,以 KDD Cup 1999 Data[8]為數(shù)據(jù)集,進(jìn)行實(shí)驗(yàn)分析。KDD Cup 1999 Data是在軍事網(wǎng)絡(luò)環(huán)境中運(yùn)用非常廣泛的模擬入侵攻擊所得到的網(wǎng)絡(luò)數(shù)據(jù)集,是為第三屆國(guó)際知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘競(jìng)賽提供的。在實(shí)驗(yàn)過程中選取2 000條記錄作為測(cè)試數(shù)據(jù)集。實(shí)驗(yàn)所使用的硬件平臺(tái)是 Pentium4 3.00 GHz處理器,512 M內(nèi)存和 80 G硬盤的 PC機(jī),操作系統(tǒng)為Window s XP。

設(shè)定最小支持度為15%,最小置信度為80%,在不同的參考度下,統(tǒng)計(jì)產(chǎn)生的規(guī)則數(shù)目。結(jié)果如圖1所示。

圖 1表明,算法產(chǎn)生的規(guī)則數(shù)隨著參考度閾值的增加而遞減,因?yàn)殡S著參考度的增大,越來越多的規(guī)則被淘汰。由此可以看出,加入新的評(píng)價(jià)指標(biāo)——參考度來控制產(chǎn)生關(guān)聯(lián)規(guī)則的質(zhì)量是可行的,而且給系統(tǒng)帶來極大好處。

圖 1 參考度閾值-規(guī)則數(shù)關(guān)系圖

4 結(jié)束語

關(guān)聯(lián)規(guī)則挖掘作為數(shù)據(jù)挖掘中的一個(gè)重要手段在入侵檢測(cè)中發(fā)揮了重要作用。本文針對(duì)當(dāng)前關(guān)聯(lián)規(guī)則挖掘采用的支持度-置信度框架在具體應(yīng)用中存在的問題,引入新的評(píng)價(jià)指標(biāo)——參考度對(duì)模型中關(guān)聯(lián)規(guī)則挖掘算法評(píng)價(jià)體系進(jìn)行改進(jìn)。實(shí)驗(yàn)表明,通過引入?yún)⒖级?能夠提高挖掘有效規(guī)則的效率。

[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] 伊衛(wèi)國(guó),衛(wèi)金茂,王名揚(yáng).挖掘有效的關(guān)聯(lián)規(guī)則[J].計(jì)算機(jī)工程與科學(xué),2005,32(27):91-94.

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

[6] 羅 可,郗東妹.采掘有效的關(guān)聯(lián)規(guī)則 [J].小型微型計(jì)算機(jī)系統(tǒng),2005,25(26):1374-1379.

[7] 李 鵬.數(shù)據(jù)挖掘在入侵檢測(cè)中的應(yīng)用研究[D].鄭州:解放軍信息工程大學(xué),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

湖北省自然科學(xué)基金資助項(xiàng)目(2006ABA 009)

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