淺析入侵模式挖掘系統(tǒng)結(jié)構(gòu)算法

[摘 要]網(wǎng)絡(luò)日志數(shù)據(jù)量日益增大。如何從巨大的網(wǎng)絡(luò)數(shù)據(jù)中提取有效信息是數(shù)據(jù)研究人員一直關(guān)心的問題。入侵模式挖掘系統(tǒng)（Intrusion Digger）結(jié)合了數(shù)據(jù)挖掘技術(shù)與入侵檢測技術(shù)，旨在通過發(fā)現(xiàn)關(guān)聯(lián)規(guī)則而對網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行判別。最小支持度小于所有支持度的項(xiàng)集稱為頻繁項(xiàng)集，簡稱頻集?；趧澐指倪M(jìn)的Apriori算法明顯優(yōu)越于原來的算法?；趧澐指倪M(jìn)的Apriori算法為入侵模式挖掘系統(tǒng)的設(shè)計提供了重要的理論支持。

[關(guān)鍵詞]入侵模式挖掘系統(tǒng) 基于劃分改進(jìn)的Apriori算法 數(shù)據(jù)挖掘

[中圖分類號] G642 [文獻(xiàn)標(biāo)識碼] A [文章編號] 2095-3437（2013）15-0036-02

一、系統(tǒng)的實(shí)現(xiàn)原理

眾所周知，網(wǎng)絡(luò)日志數(shù)據(jù)量日益增大，從巨大的網(wǎng)絡(luò)數(shù)據(jù)中提取有用信息是入侵模式挖掘系統(tǒng)所要完成的工作。在這里我們使用數(shù)據(jù)挖掘的關(guān)聯(lián)分析方法，即產(chǎn)生頻繁項(xiàng)集與關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則就是我們得到的有用信息。在得到關(guān)聯(lián)規(guī)則后，我們便可以使用關(guān)聯(lián)規(guī)則對測試數(shù)據(jù)進(jìn)行分析，判斷測試數(shù)據(jù)是正常數(shù)據(jù)還是非正常數(shù)據(jù)。對于判斷的結(jié)果，我們用一個評價體系來評測判斷結(jié)果的好壞。入侵模式挖掘系統(tǒng)結(jié)合了數(shù)據(jù)挖掘技術(shù)與入侵檢測技術(shù)，旨在通過發(fā)現(xiàn)關(guān)聯(lián)規(guī)則而對網(wǎng)絡(luò)數(shù)據(jù)來進(jìn)行判別。因此，根據(jù)以上分析，入侵模式挖掘系統(tǒng)的總體大致設(shè)計圖如圖1.1所示。

■

圖1.1 入侵模式挖掘系統(tǒng)總體設(shè)計圖

圖1.1中方框內(nèi)為數(shù)據(jù)或文件如原始網(wǎng)絡(luò)日志數(shù)據(jù)、測試結(jié)果文件等，初步設(shè)計有三個大的子系統(tǒng)，分別是模式挖掘系統(tǒng)、測試系統(tǒng)、評價系統(tǒng)。箭頭代表數(shù)據(jù)的流向或者結(jié)果的輸出，橢圓框內(nèi)為入侵模式挖掘系統(tǒng)的初步設(shè)計的子系統(tǒng)。

二、系統(tǒng)的設(shè)計算法分析

（一）Apriori算法

本系統(tǒng)采用關(guān)聯(lián)分析方法中的Apriori算法作為核心算法。目前，該算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集算法中最有影響力的一種，基于兩階段頻集思想的遞推算法是其核心。在此，最小支持度小于所有支持度的項(xiàng)集稱為頻繁項(xiàng)集，簡稱頻集。[1]在分類上該關(guān)聯(lián)規(guī)則屬于單層、單維和布爾關(guān)聯(lián)規(guī)則，該關(guān)聯(lián)規(guī)則為了生成所有頻集，采用了遞推的方法。

算法思路：第一步，找出所有出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣的頻集。第二步，由頻集產(chǎn)生必須滿足最小可信度和最小支持度的強(qiáng)關(guān)聯(lián)規(guī)則。第三步，使用第一步找到的頻集產(chǎn)生只包含集合項(xiàng)的所有規(guī)則，其中每一條定義為中規(guī)則的右部只有一項(xiàng)的規(guī)則。第四步，大于用戶給定的最小可信度的規(guī)則被留下來生成我們需要的規(guī)則。

程序算法如下：

（1）L1 = find_frequent_1_itemset（D）；

（2）for（k = 2； Lk-1≠φ； k++）{

（3） Ck = apriori_gen（Lk-1）；

（4） for each t ∈ D{

（5） Ck = subset（Ck，t）；

（6） For each c ∈ Ct c.count++； }

（7）Lk = {c∈Ck| c.count > min_sup} }

（8）retrurn L = ∪Lk

該算法中首先產(chǎn)生頻繁1項(xiàng)集L1，其次產(chǎn)生頻繁2項(xiàng)集L2，然后直到有一個頻繁r值使得對應(yīng)項(xiàng)集Lr為空，此時算法終止。Ck中的項(xiàng)集是用來產(chǎn)生頻集的候選項(xiàng)集，最終的頻集Lk一定是集合Ck的一個子集。在第k次循環(huán)中，算法先產(chǎn)生候選項(xiàng)k項(xiàng)集的集合Ck，Ck中的每一個項(xiàng)集屬于項(xiàng)集Lk-1的頻集來產(chǎn)生的下一個連接集合。Ck中的每個元素都需要在數(shù)據(jù)庫中進(jìn)行驗(yàn)證，然后才能決定該項(xiàng)是否能夠加入頻集Lk中。

Apriori算法的兩個嚴(yán)重不足會導(dǎo)致挖掘的效率非常低。一個方面，該算法在每進(jìn)行一次迭代的時候掃描一次數(shù)據(jù)庫，多次掃描數(shù)據(jù)庫帶來巨大I/O開銷。另一個方面，該算法在迭代過程中需要在內(nèi)存中產(chǎn)生、處理和保存數(shù)量巨大的候選頻集，這也導(dǎo)致算法在深度和廣度上的適應(yīng)性很差。

（二）基于劃分改進(jìn)的Apriori算法

為了提高Apriori算法的效率，需要對Apriori算法進(jìn)行改進(jìn)。本系統(tǒng)引入了一種基于劃分改進(jìn)的Apriori算法，該算法只需要掃描數(shù)據(jù)庫兩次。第一次掃描中，將產(chǎn)生一組潛在的頻集，這組項(xiàng)集是最后需要確定的頻集的超集，它也可能包含錯誤的選擇，但絕對不可能漏掉正確的選擇。第二次掃描中，對這些潛在的頻集進(jìn)一步計算它在整個數(shù)據(jù)庫中的實(shí)際支持度，可以最后確定所求得的真正的頻集。

算法思路：第一步，將整個數(shù)據(jù)庫盡可能劃分成N個子塊。第二步，針對每一個子塊單獨(dú)產(chǎn)生一組潛在的頻集。第三步，將上一步所有潛在的頻集合并為一個全局的候選頻集。第四步，在整個數(shù)據(jù)庫中，計算每個候選頻集的實(shí)際支持度，從而確定最后有用的頻集。

程序算法如下：

（1） P=partion_database（D）

（2）n=number of partitions

（3）for i=1 to n begin

（4）read_in_partition（PiP）

（5）LPi=gen_large_itemset（Pi）

（6）end

（7）for（i=2；LPi=φ，，J=1，2，…，n； i++）do

（8）CGi=ULPi

（9）forall candidates c∈CG do begin

（10）c.count++；

（11）Lk={c∈Ck|c.count≥min_sup}

（12）end

（13）answer=UkLk；

（14）Produce gen_large_itemset（Pi，min_sup）

（15）L1={Pi}；

（16）for（k=2；Lk-1≠？覫；k++）do begin

（17）Ck=apriori_gen（Lk-1，min_sup）；

（18）forall transactions∈tPi do begin

（19）Ct=subset（Ck，t）；

（20）forall candidations∈cCt do

（21）c.count++；

（22）end

（23）Lk={c= Ck|c.count≥min_sup*n}

（24）end

（25）return Lk

（26）Produce apriori_gen（Lk-1，min_sup）

（27）forall items l1∈Lk-1

（28）forall items l2∈Lk-1

（29）if（（l1[1]=l2[2]（∧…∧ l1[k-1]= l2[k-2]）∧（ l1[k-1] ？芻l2[k-2]））do begin

（30）c=l1？茌l2；

（31）if has_infrequent_itemset（c， Lk-1）

（32）delete c；

（33）else Ck=Ck∨{c}

（34）end；

（35）return Ck

（36）Produce has_infrequent_subset（c，Lk-1）

（37）forall （k-1）subset s of c

（38）if s？埸Lk-1 return true；

（39）else return 1

通過對基于劃分改進(jìn)的Apriori算法解析，我們發(fā)現(xiàn)該算法有三大優(yōu)點(diǎn)。

優(yōu)點(diǎn)1、兩種算法掃描次數(shù)相比，基于劃分改進(jìn)的Apriori算法掃描數(shù)據(jù)庫次數(shù)少。

優(yōu)點(diǎn)2、基于劃分改進(jìn)的Apriori算法第一次掃描數(shù)據(jù)庫產(chǎn)生的一組潛在的既有需要的也有不需要的頻集，它為第二次掃描數(shù)據(jù)庫進(jìn)行計算及確認(rèn)最后挖掘出有效頻集做了鋪墊。

優(yōu)點(diǎn)3、基于劃分改進(jìn)的Apriori算法進(jìn)行數(shù)據(jù)挖掘是將數(shù)據(jù)庫劃分成N個子塊，先對每個子塊單獨(dú)產(chǎn)生一組頻集，然后再合并所有獨(dú)立產(chǎn)生的各組頻集構(gòu)成一個全局的候選頻集。在數(shù)據(jù)量逐漸增多的情況下，這種“以大劃小，以小并行”的思想，可以使數(shù)據(jù)挖掘的效率大大提高。

綜上，通過分析比較可以看出，基于劃分改進(jìn)的Apriori算法跟Apriori算法相比，確實(shí)有了相當(dāng)不錯的改進(jìn)，數(shù)據(jù)挖掘的效率大大提高了。基于劃分改進(jìn)的Apriori算法為入侵模式挖掘系統(tǒng)的設(shè)計提供了重要的理論支持。

[ 參 考 文 獻(xiàn) ]

[1] 劉明輝，周萍.基于Web挖掘的網(wǎng)站優(yōu)化系統(tǒng)的研究[J].長春大學(xué)學(xué)報（自然科學(xué)版），2009，19（3）.

[2] aul Ammann，Duminda wijesekera and Saket kaushie. Scalable，graph-based network vulnerability analysis[A]. CCS’02[C]， Washington， DC， USA，2002.18-22.

[責(zé)任編輯：戴禎杰]