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

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

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

中圖分類號(hào):TP39308文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

從Apriori算法的步驟可以看出,該算法有三個(gè)缺點(diǎn):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這里采用屬性論域上的模糊集來(lái)軟化邊界。這是因?yàn)槟：梢栽诩显睾头羌显刂g提供平滑的過(guò)渡[4,5]。

定義2 數(shù)據(jù)集D={t1,t2,…,tk,…,tn},I={i1,i2,…,im}為m個(gè)不同的數(shù)據(jù)項(xiàng)目組成的集合,要發(fā)現(xiàn)的模糊關(guān)聯(lián)規(guī)則是形如的蘊(yùn)涵式。其中,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ī)則集,其模式是準(zhǔn)確的,而在入侵檢測(cè)系統(tǒng)中,對(duì)于規(guī)則集的建立,往往更偏重于語(yǔ)義的,而不是非常準(zhǔn)確的區(qū)間描述,比如采用數(shù)據(jù)包傳輸?shù)拇笈c小,由TCP協(xié)議傳輸?shù)臄?shù)據(jù)包所占比例的高與低來(lái)描述網(wǎng)絡(luò)傳輸數(shù)據(jù)的性質(zhì),要比用精確的區(qū)間如用[100,110)來(lái)描述更符合實(shí)際處理的需要。因此,將模糊關(guān)聯(lián)規(guī)則應(yīng)用于入侵檢測(cè)系統(tǒng)中,更符合入侵檢測(cè)的數(shù)據(jù)處理模式,使得規(guī)則集的建立更趨于準(zhǔn)確降低了規(guī)則集建立的疏漏和誤判。為此,把模糊集合理論與關(guān)聯(lián)規(guī)則挖掘結(jié)合起來(lái),提出基于矩陣結(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ù)挖掘算法基本相似,只有一點(diǎn)不同就是首先需要將挖掘的數(shù)據(jù)通過(guò)隸屬函數(shù)轉(zhuǎn)化為模糊數(shù)據(jù)集后再進(jìn)行挖掘。具體算法如下:

算法:FARMBM

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

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

方法:

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

初始化矩陣:

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

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

String[,]strArr;//使用一個(gè)字符串?dāng)?shù)組來(lái)存放各個(gè)屬性

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];}

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

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列中除了最后一個(gè)頻繁項(xiàng)不同,其余的都相同,則組成一個(gè)新的頻繁項(xiàng),這兩列各元素相乘;接著對(duì)arrayb做刪除行和刪除列,自身連接,直到矩陣為空或只剩一列,算法結(jié)束

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

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 實(shí)驗(yàn)方法

首先選擇與網(wǎng)絡(luò)流量相關(guān)的4個(gè)屬性: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所示的兩個(gè)模糊集,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。

運(yùn)行FARMBM程序,對(duì)表1數(shù)據(jù)經(jīng)行挖掘:最小支持度minsup設(shè)定為0.25。首先產(chǎn)生頻繁1-項(xiàng)集。頻繁1-項(xiàng)集自身連接,經(jīng)過(guò)刪除行和列,產(chǎn)生頻繁2-項(xiàng)集。最后產(chǎn)生頻繁3-項(xiàng)集。于是,可以發(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ù)量的時(shí)候,有83.57%的可能產(chǎn)生高每秒平均數(shù)據(jù)位;在低UDP,低每秒的平均數(shù)據(jù)包數(shù)量的時(shí)候,有87.39%的可能產(chǎn)生高每秒平均數(shù)據(jù)位。這些規(guī)則對(duì)網(wǎng)絡(luò)數(shù)據(jù)流量的監(jiān)控與判斷檢測(cè)異常是非常有用的。FARMBM算法與Apriori算法時(shí)間消耗的比較如圖2所示。

圖2 FARMBM算法與Apriori算法時(shí)間消耗的比較

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[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]覃俊,易云飛,李林.改進(jìn)k均值聚類算法在網(wǎng)絡(luò)入侵檢測(cè)中的應(yīng)用研究[J].中南民族大學(xué)學(xué)報(bào):自然科學(xué)版,2008,27(9):75-78.

[3]谷保平,許孝元,郭紅艷.基于粒子群優(yōu)化的k均值算法在網(wǎng)絡(luò)入侵檢測(cè)中的應(yīng)用[J].計(jì)算機(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é)報(bào),2005,24(1):24-28.

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