李 林,易云飛,黃 潛,覃 俊

摘 要:針對布爾型關(guān)聯(lián)規(guī)則不能表達挖掘?qū)ο笾心：畔⒌年P(guān)聯(lián)性,給出了一系列有關(guān)模糊關(guān)聯(lián)規(guī)則的定義,并提出了一種基于矩陣結(jié)構(gòu)的模糊關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法(FARMBM)。該算法通過構(gòu)造矩陣結(jié)構(gòu)來壓縮存儲模糊模式候選集和頻繁集,有效節(jié)約了存儲模糊模式候選集和模糊模式頻繁集內(nèi)存花銷,只需掃描數(shù)據(jù)庫兩遍,且可以有效減少系統(tǒng)的I/O開銷。這里把FARMBM運用到入侵檢測的仿真實驗中,實驗結(jié)果表明,該算法是有效的。

關(guān)鍵詞:Apriori;矩陣;模糊關(guān)聯(lián)規(guī)則;隸屬函數(shù);入侵檢測

中圖分類號:TP39308文獻標識碼:A

文章編號:1004-373X(2009)20-069-04

Study and Application of Fuzzy Association Rule Mining Based on Matrix

LI Lin1,YI Yunfei1,2,HUANG Qian1,QIN Jun1

(1.College of Computer Science,South-central University for Nationalities,Wuhan,430074,China;

2.Hechi University,Yizhou,546300,China)

Abstract:In allusion to the Boolean association rules can′t express the association of fuzzy data,a series of definitions of fuzzy association rules and mining algorithm based on matrix for fuzzy association rules are proposed.The algorithm can store fuzzy pattern candidate sets and frequent sets compressible by constructing matrix structure,which effectively saves the memory cost for storing fuzzy pattern candidate sets and frequent sets,it only scans database twice,besides it can effectively reduce the I/O spending.FARMBM is applied to the simulation results of intrusion detection,and efficiency of the algorithm is verified by the experiment.

Keywords:Apriori;matrix;fuzzy association rule;membership function;intrusion detection

0 引 言

入侵檢測技術(shù)[1-3]是網(wǎng)絡(luò)安全的核心技術(shù)之一,是網(wǎng)絡(luò)信息系統(tǒng)的一種重要的動態(tài)防護手段。入侵檢測技術(shù)的研究是進一步研究網(wǎng)絡(luò)安全問題的基礎(chǔ),是解決網(wǎng)絡(luò)安全問題的前提和保證。當然,網(wǎng)絡(luò)入侵技術(shù)也在不斷的發(fā)展,隨著網(wǎng)絡(luò)數(shù)據(jù)的增大,入侵的行為表現(xiàn)為不確定性、復(fù)雜性等特點。那么入侵檢測怎么樣才能做到既減小數(shù)據(jù)量,又能有效地檢測到入侵。在入侵檢測技術(shù)中引入數(shù)據(jù)挖掘就能有效的解決這一問題。數(shù)據(jù)挖掘技術(shù)在從大量數(shù)據(jù)中提取特征和規(guī)則方面具有很大的優(yōu)勢,將數(shù)據(jù)挖掘技術(shù)應(yīng)用于入侵檢測中,能夠克服目前入侵檢測技術(shù)存在的缺陷,建立一個準確性高的、易于擴展的、適應(yīng)性好、伸縮性好、智能的入侵檢測系統(tǒng)。在對關(guān)聯(lián)規(guī)則深入分析的基礎(chǔ)上,把模糊集合理論與數(shù)據(jù)挖掘技術(shù)中關(guān)聯(lián)規(guī)則挖掘結(jié)合起來,提出了一種基于矩陣結(jié)構(gòu)的模糊關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法(FARMBM),并把FARMBM運用到了入侵檢測技術(shù)當中。

1 關(guān)聯(lián)規(guī)則的概念與算法

1.1 關(guān)聯(lián)規(guī)則的概念

關(guān)聯(lián)規(guī)則是當前數(shù)據(jù)挖掘研究的主要模式之一,它用于確定數(shù)據(jù)集中不同領(lǐng)域或?qū)傩灾g的聯(lián)系,找出可信的、有價值的多個域之間的依賴關(guān)系。關(guān)聯(lián)規(guī)則的挖掘目標是從數(shù)據(jù)庫中找出形如“由于某些事件的發(fā)生而引起另外一些事件的發(fā)生”的規(guī)則[4-10]。

定義1 設(shè)I={i1,i2,…,im}是由m個不同的數(shù)據(jù)項目組成的集合,其中的元素稱為項(item),項的集合成為項集,包含k個項的項集成為k項集,給定一個事務(wù)(交易)D,即交易數(shù)據(jù)庫,其中的每一個事務(wù)(交易)T是數(shù)據(jù)項I的一個子集,即T罥,T有一個惟一的標識符TID;當且僅當X罷時,稱交易T包含項集X;那么關(guān)聯(lián)規(guī)則就形如X軾的蘊含式;其中,X罥,Y罥,X∩Y=h,即表示滿足X中條件的記錄也一定滿足Y。關(guān)聯(lián)規(guī)則X軾在數(shù)據(jù)庫中成立,就有支持度s和具有置信度c。這也就是交易數(shù)據(jù)集D中具有支持度s,即D中至少有s%的事務(wù)包含X∪Y,描述為:support(X軾)=P(X∪Y)。

同時交易數(shù)據(jù)集D中具有置信度c,即D中包含X的事務(wù)至少有c%同時也包含Y,描述為:

confidence(X軾)=P(Y|X)

大多數(shù)關(guān)聯(lián)規(guī)則挖掘算法通常采用的一種策略是:將關(guān)聯(lián)規(guī)則挖掘任務(wù)分解為如下兩個子任務(wù):

(1) 頻繁項集產(chǎn)生:其目標是發(fā)現(xiàn)滿足最小支持度閾值的所有項集,這些項集稱作頻繁項集(Frequent Itemset)。

(2) 規(guī)則的產(chǎn)生:其目標是從上一步發(fā)現(xiàn)的頻繁項集中提取所有高置信度的規(guī)則,這些規(guī)則稱強規(guī)則(Strong Rule)。

Apriori算法是挖掘產(chǎn)生關(guān)聯(lián)規(guī)則所需頻繁項集的基本算法;它也是一個很有影響的關(guān)聯(lián)規(guī)則挖掘算法。Apriori 算法就是根據(jù)有關(guān)頻繁項集特性的先驗知識(Prior Knowledge)而命名的。該算法利用了一個層次順序搜索的循環(huán)方法來完成頻繁項集的挖掘工作。

Apriori算法[2]的基本思想是先找出所有頻繁1-項集,這些項集組成L1,然后由L1產(chǎn)生頻繁2-項集,直到有某個r值使得Lr為空,此時算法結(jié)束。從Lk-1到Lk的實現(xiàn),是把Lk-1與自身連接生成候選k-項集合,記為Ck,Ck中的每一個項集是對兩個只有一個項不同屬于Lk-1的頻集做一個(k-2)連接來產(chǎn)生的。Ck中的項集是用來產(chǎn)生頻集的候選集,最后的頻集Lk必須是Ck的一個子集。

由于Ck中的每個元素需在交易數(shù)據(jù)庫中進行驗證來決定其是否加入Lk,那么這個方法就要求多次掃描可能很大的交易數(shù)據(jù)庫,即如果頻集最多包含10個項,那么就需要掃描交易數(shù)據(jù)庫10遍,這需要很大的I/O負載。

1.2 基于矩陣結(jié)構(gòu)的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法

從Apriori算法的步驟可以看出,該算法有三個缺點:

(1) 在每一步產(chǎn)生的候選項集過多,沒有排除不應(yīng)參與組合的元素;

(2) 每次計算子項集的支持度時,都要進行一遍數(shù)據(jù)庫掃描比較,大大增加系統(tǒng)的I/O開銷,并且數(shù)據(jù)庫有些可以刪除的項或事務(wù)被多次掃描;

(3) 連接程序中相同的項重復(fù)比較太多。

針對這些缺點,采用矩陣結(jié)構(gòu)改進Apriori算法,算法思想如下:

(1) 首先把所要挖掘的數(shù)據(jù)轉(zhuǎn)化為矩陣結(jié)構(gòu):事務(wù)集T作為行的標記,項I作為列的標記,矩陣中每個元素對應(yīng)某一事務(wù)對應(yīng)某個屬性的支持計數(shù),這樣每一列的和除以事務(wù)的總和,就是所有事務(wù)對這一列所對應(yīng)屬性的支持度。

(2) 如果某一事務(wù)中只包含一個屬性,那么它不可能再包含任一個鏈接后的2-項集或者k-項集(k≥2),這一事務(wù)在以后統(tǒng)計更高階的頻繁集時不再用到,為了提高掃描速度,可以把這一事務(wù)刪除,對應(yīng)矩陣就是把這一行給刪除。

(3) 接下來把每一列所對應(yīng)屬性的支持度與最小支持度minsup進行比較,如果小于minsup則把這一列刪除,保留下來的就是頻繁1-項集。

(4) 然后矩陣與自身進行一次連接,這樣就產(chǎn)生了2-項集。

(5)接著重復(fù)做步驟(2)~(4),直到矩陣為空或只剩一列,這時候已經(jīng)找到所有支持度大于最小支持度的項集,即頻集,算法結(jié)束。

可以看出,此算法可以有效地減小事務(wù)集以及屬性集,這就避免了數(shù)據(jù)庫有些可以刪除的項或事務(wù)被多次掃描。同時解決了連接程序中相同的項重復(fù)比較太多的問題。

2 基于矩陣結(jié)構(gòu)的模糊關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法

2.1 模糊關(guān)聯(lián)規(guī)則

用于入侵檢測技術(shù)[2,3]的關(guān)聯(lián)規(guī)則挖掘,需要考慮網(wǎng)絡(luò)數(shù)據(jù)特有的特點,否則會產(chǎn)生很多無用的規(guī)則。由于關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘通常只能對離散值進行處理,在數(shù)據(jù)預(yù)處理中要將連續(xù)屬性域劃分為若干離散區(qū)間,這就導(dǎo)致了所謂的“尖銳邊界”(Sharp Boundary)問題。這就引出了關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘存在兩個缺陷:

(1) 關(guān)聯(lián)規(guī)則直接依賴于審計記錄,與審計記錄具有一一對應(yīng)的關(guān)系,缺少靈活性。

(2) 屬性值的微小變化將會引起分類上的突變。比如:設(shè)定TCP包在區(qū)間[0.5,0.9]是挖掘出某一屬性的正常模式,那么如果TCP包是0.900 001,就會判斷為異常,也就是說某個行為如果與表示正常模式的區(qū)間稍有偏差,會被判為異常。那么,入侵行為如稍有一些變化而落入?yún)^(qū)間內(nèi),就不會被檢測出來。

這里采用屬性論域上的模糊集來軟化邊界。這是因為模糊集可以在集合元素和非集合元素之間提供平滑的過渡[4,5]。

定義2 數(shù)據(jù)集D={t1,t2,…,tk,…,tn},I={i1,i2,…,im}為m個不同的數(shù)據(jù)項目組成的集合,要發(fā)現(xiàn)的模糊關(guān)聯(lián)規(guī)則是形如的蘊涵式。其中,X={x1,x2,…,xn},Y={y1,y2,…,yn}且X∩Y=h,A={fx1,fx2,…,fxp},B={fy1,fy2,…,fyq}分別是與X,Y中屬性相應(yīng)的模糊集集合。

則支持度描述為:

support()=∑∈D(∧xj∈

X{αaj(di[xj])}/|D|

其中,αaj(di[xj])為di的隸屬度。

置信度[6]描述為:

confidence()=support

A∪B>/support

由關(guān)聯(lián)規(guī)則挖掘所產(chǎn)生的規(guī)則集,其模式是準確的,而在入侵檢測系統(tǒng)中,對于規(guī)則集的建立,往往更偏重于語義的,而不是非常準確的區(qū)間描述,比如采用數(shù)據(jù)包傳輸?shù)拇笈c小,由TCP協(xié)議傳輸?shù)臄?shù)據(jù)包所占比例的高與低來描述網(wǎng)絡(luò)傳輸數(shù)據(jù)的性質(zhì),要比用精確的區(qū)間如用[100,110)來描述更符合實際處理的需要。因此,將模糊關(guān)聯(lián)規(guī)則應(yīng)用于入侵檢測系統(tǒng)中,更符合入侵檢測的數(shù)據(jù)處理模式,使得規(guī)則集的建立更趨于準確降低了規(guī)則集建立的疏漏和誤判。為此,把模糊集合理論與關(guān)聯(lián)規(guī)則挖掘結(jié)合起來,提出基于矩陣結(jié)構(gòu)的模糊關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法(Fuzzy Association Rule Mining Base on Matrix,FARMBM)。

2.2 算法的描述

FARMBM算法與基于矩陣結(jié)構(gòu)的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法基本相似,只有一點不同就是首先需要將挖掘的數(shù)據(jù)通過隸屬函數(shù)轉(zhuǎn)化為模糊數(shù)據(jù)集后再進行挖掘。具體算法如下:

算法:FARMBM

輸入:模糊數(shù)據(jù)集D、最小支持度minsup;

輸出:模糊關(guān)聯(lián)規(guī)則集。

方法:

初始化矩陣行和列數(shù):countrow和countcol;

初始化矩陣:

double[,] arraya;//使用一個二維數(shù)組存放矩陣

double[] tempa;//使用一個一維數(shù)組存放每個屬性的支持度

String[,]strArr;//使用一個字符串數(shù)組來存放各個屬性

While(countcol>1);//矩陣至少大于一列

for(int i=0;i

{for(int k=0;k

if(arraya[i,k]!=0)

num++;

if(num<2) Delete Ti;//刪除行

for(int k=0;k

{ for(int i=0;i

tempa[k]=tempa[k]+arraya[i,k];}

//把各個屬性的隸屬度相加,得出各個屬性的支持度

if(tempa[k]

if(arraya[m,countrol-1]!= arraya[n,countrol-1])

for(w=countrol-1;w>=0;w--)

if(arraya[m,w]== arraya[n,w])

TstrArr[i]= arraya[m,w]+arraya[n,w];

for(int f=0;f

{c++;

if(c==count){e++;c=e+1;}

for(int i=0;i

arrayb[i,f]=arraya[i,e]*arraya[i,c];}

//如果第m列與第n列中除了最后一個頻繁項不同,其余的都相同,則組成一個新的頻繁項,這兩列各元素相乘;接著對arrayb做刪除行和刪除列,自身連接,直到矩陣為空或只剩一列,算法結(jié)束

3 基于FARMBM的入侵檢測技術(shù)

3.1 實驗環(huán)境

操作系統(tǒng):Microsoft Windows XP Professional,CPU;Pentium (R) 2.40 GHz;內(nèi)存:256 MB;開發(fā)平臺:Microsoft Visual Studio.Net 2003;編程語言:C#。

3.2 實驗方法

首先選擇與網(wǎng)絡(luò)流量相關(guān)的4個屬性:TCP和UDP包在全部數(shù)據(jù)包中的比例PTCP和PUDP,網(wǎng)絡(luò)中每秒的平均數(shù)據(jù)包數(shù)量Avg.Packet/s 以及每秒平均數(shù)據(jù)位Avg.Mb/s。

利用Wincap抓取網(wǎng)絡(luò)數(shù)據(jù),將它們劃分為High和Low如表1所示的兩個模糊集,PTCP,PUDP,Avg.Packet/s以及Avg.Mb/s的隸屬函數(shù)如圖1所示。

表1 模糊集

TID

PTCPPUDPAvg.PacketAvg.Mb

ABCDEFGH

T100.881000.6301

T200.920.91000.7500.92

T300.56100101

T400.920100.7300.86

T500.870.5300.89010

T60000.500.6101

T7010.56000.9301

T810100100.91

T90.730100.63010

T100.910100100.83

圖1 隸屬函數(shù)

High:

μA(X)=0, x

(x-a)/(b-a),a≤x≤b

1,x>b

Low:

μA(X)=1, x

(b-x)/(b-a),a≤x≤b

0,x>b

為了在數(shù)組中便于表示,采用如下表示方法:

A:Ptcp Low,B:Ptcp High,C:Pudp Low,D:Pudp High,E:Avg.Packet/s High,F:Avg.Packet/s Low G:Avg.Mb/s Low,H:Avg.Mb/s High。

運行FARMBM程序,對表1數(shù)據(jù)經(jīng)行挖掘:最小支持度minsup設(shè)定為0.25。首先產(chǎn)生頻繁1-項集。頻繁1-項集自身連接,經(jīng)過刪除行和列,產(chǎn)生頻繁2-項集。最后產(chǎn)生頻繁3-項集。于是,可以發(fā)現(xiàn)以下關(guān)聯(lián)規(guī)則:

R1:B:PtcpHigh,F:Avg.Packet/s Low→H:Avg.Mb/s High

支持度為:28.4%,可信度為:2.839 11/3.397 2=83.57%

R2:C:PUDP Low,F:Avg.Packet/s Low→H:Avg.Mb/s High

支持度為:42.2%,可信度:4.223 037/4.832 3=87.39%

這些規(guī)則揭示了網(wǎng)絡(luò)各數(shù)據(jù)屬性的潛在關(guān)系,比如:在高TCP,低每秒的平均數(shù)據(jù)包數(shù)量的時候,有83.57%的可能產(chǎn)生高每秒平均數(shù)據(jù)位;在低UDP,低每秒的平均數(shù)據(jù)包數(shù)量的時候,有87.39%的可能產(chǎn)生高每秒平均數(shù)據(jù)位。這些規(guī)則對網(wǎng)絡(luò)數(shù)據(jù)流量的監(jiān)控與判斷檢測異常是非常有用的。FARMBM算法與Apriori算法時間消耗的比較如圖2所示。

圖2 FARMBM算法與Apriori算法時間消耗的比較

4 結(jié) 語

數(shù)據(jù)挖掘技術(shù)是一種處理大量數(shù)據(jù)的復(fù)雜過程,它為入侵檢測提供了新的方法,為入侵檢測的發(fā)展注入了強大的動力。模糊集合理論與數(shù)據(jù)挖掘技術(shù)中關(guān)聯(lián)規(guī)則挖掘的結(jié)合為入侵檢測技術(shù)提供了更有效的方法。在此提出FARMBM算法,給出算法的描述,并以實例進行了分析與驗證。實驗表明,改進后的算法用于入侵檢測技術(shù)中是可行的,有效的。

參考文獻

[1]Li Tianrui,Pan Wuming.Intrusion Detection System Based on New Association Rule Mining Model[A].Granular Computing,2005 IEEE International Conference[C].2005,2:512-515.

[2]覃俊,易云飛,李林.改進k均值聚類算法在網(wǎng)絡(luò)入侵檢測中的應(yīng)用研究[J].中南民族大學(xué)學(xué)報:自然科學(xué)版,2008,27(9):75-78.

[3]谷保平,許孝元,郭紅艷.基于粒子群優(yōu)化的k均值算法在網(wǎng)絡(luò)入侵檢測中的應(yīng)用[J].計算機應(yīng)用,2007,27(6):1 368-1 370.

[4]Han Jiawei,Kamber M.Data Mining:Concepts and Techniques[M].China Machine Press,2007.

[5]Ji Lei,Zhang Baowen,Li Jianhua.A New Improvement on Apriori Algorithm[A].2006 International Conference on Computational Intelligence and Security[C].2006,1:840-844.

[6]Kuok C,Fu A,Wong M.Mining Fuzzy Association Rules in Databases[J].ACM SIGMOD Record,1998,27(1):41-46.

[7]Agarwal R,Aggrawal C,Prasad V V V.A Tree Projection Algorithm for Generation of Frequent Itemsets[J].Journal of Parallel and Distributed Computing,2000:427-434.

[8]Holt J D,Chung S M.Mining Association Rules in Text Databases Using Multipass with Inverted Hashing and Pruning Tools with Artificial Intelligence[A].ICTAI[C].2002:49-56.

[9]Ayouni S,Ben Yahia S.Extracting Compact and Information Lossless Set of Fuzzy Association Rules[A].Fuzzy Systems Conference[C].2007:1-6.

[10]朱天清,熊平.模糊關(guān)聯(lián)規(guī)則挖掘及其算法研究[J].武漢工業(yè)學(xué)院學(xué)報,2005,24(1):24-28.

[11]朱燁,葉高英.關(guān)聯(lián)規(guī)則挖掘Apriori算法的改進[J].現(xiàn)代電子技術(shù),2008,31(18):78-80.