基于矩陣的模糊關聯規則挖掘算法及其應用研究

2010-05-13 09:17:24李林,易云飛,黃潛,覃俊

現代電子技術 2009年20期

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

摘要:針對布爾型關聯規則不能表達挖掘對象中模糊信息的關聯性,給出了一系列有關模糊關聯規則的定義,并提出了一種基于矩陣結構的模糊關聯規則數據挖掘算法(FARMBM)。該算法通過構造矩陣結構來壓縮存儲模糊模式候選集和頻繁集,有效節約了存儲模糊模式候選集和模糊模式頻繁集內存花銷,只需掃描數據庫兩遍,且可以有效減少系統的I/O開銷。這里把FARMBM運用到入侵檢測的仿真實驗中,實驗結果表明,該算法是有效的。

關鍵詞:Apriori;矩陣;模糊關聯規則;隸屬函數;入侵檢測

中圖分類號: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 引言

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

1 關聯規則的概念與算法

1.1 關聯規則的概念

關聯規則是當前數據挖掘研究的主要模式之一,它用于確定數據集中不同領域或屬性之間的聯系,找出可信的、有價值的多個域之間的依賴關系。關聯規則的挖掘目標是從數據庫中找出形如“由于某些事件的發生而引起另外一些事件的發生”的規則[4-10]。

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

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

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

大多數關聯規則挖掘算法通常采用的一種策略是:將關聯規則挖掘任務分解為如下兩個子任務:

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

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

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

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

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

1.2 基于矩陣結構的關聯規則數據挖掘算法

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

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

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

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

針對這些缺點,采用矩陣結構改進Apriori算法,算法思想如下:

(1) 首先把所要挖掘的數據轉化為矩陣結構:事務集T作為行的標記,項I作為列的標記,矩陣中每個元素對應某一事務對應某個屬性的支持計數,這樣每一列的和除以事務的總和,就是所有事務對這一列所對應屬性的支持度。

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

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

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

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

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

2 基于矩陣結構的模糊關聯規則數據挖掘算法

2.1 模糊關聯規則

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

(1) 關聯規則直接依賴于審計記錄,與審計記錄具有一一對應的關系,缺少靈活性。

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

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

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

則支持度描述為:

support()=∑∈D(∧xj∈

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

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

置信度[6]描述為:

confidence()=support

A∪B>/support

由關聯規則挖掘所產生的規則集,其模式是準確的,而在入侵檢測系統中,對于規則集的建立,往往更偏重于語義的,而不是非常準確的區間描述,比如采用數據包傳輸的大與小,由TCP協議傳輸的數據包所占比例的高與低來描述網絡傳輸數據的性質,要比用精確的區間如用[100,110)來描述更符合實際處理的需要。因此,將模糊關聯規則應用于入侵檢測系統中,更符合入侵檢測的數據處理模式,使得規則集的建立更趨于準確降低了規則集建立的疏漏和誤判。為此,把模糊集合理論與關聯規則挖掘結合起來,提出基于矩陣結構的模糊關聯規則數據挖掘算法(Fuzzy Association Rule Mining Base on Matrix,FARMBM)。

2.2 算法的描述

FARMBM算法與基于矩陣結構的關聯規則數據挖掘算法基本相似,只有一點不同就是首先需要將挖掘的數據通過隸屬函數轉化為模糊數據集后再進行挖掘。具體算法如下:

算法:FARMBM

輸入:模糊數據集D、最小支持度minsup;

輸出:模糊關聯規則集。

方法:

初始化矩陣行和列數:countrow和countcol;

初始化矩陣:

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

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

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

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