張群慧

(湖南信息科學(xué)職業(yè)學(xué)院 湖南 410151)

0 引言

要從海量的數(shù)據(jù)中挖掘出有用的信息知識，關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的主要工具之一。它主要是能夠從大量的數(shù)據(jù)中尋找出數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系。作為傳統(tǒng)網(wǎng)絡(luò)安全技術(shù)的補充，入侵檢測受到更多的重視?；谀Ｊ狡ヅ?、統(tǒng)計分析和完整性分析的傳統(tǒng)入侵檢測方法，逐漸不能適應(yīng)快速發(fā)展的網(wǎng)絡(luò)安全技術(shù)。將關(guān)聯(lián)規(guī)則引入到入侵檢測中，可以適應(yīng)快速發(fā)展的網(wǎng)絡(luò)技術(shù)并提高入侵檢測的檢測效率。

1 傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法

Apriori 是一種最有影響的挖掘頻繁項集的算法。早在1994年Agrawal等人在項目集格空間理論的基礎(chǔ)上提出了用于發(fā)現(xiàn)頻繁項目集的Apriori算法。這種經(jīng)典的Apriori算法是采用一種叫做“逐層搜索”的迭代方法。要使用k-項集來生成(k+1)-項集，首先必須對數(shù)據(jù)庫進行掃描以計算出頻繁l-項集的集合,將該集合記為：L1，然后再執(zhí)行迭代過程來計算頻繁k-項集，一直到生成頻繁了k-項集的集合（記為：Lk）為空，其過程為：

（1）連接：用Lk-1進行自連接運算,來生成候選k-項集的集合（記為：Ck）。通過運算后，Ck集合將包含所有的頻繁k-項集。

（2）剪枝：連接生成的Ck就是Lk的超集，通過掃描DataBase來計算Ck中每個候選項集的支持度。用戶首先給定最小支持度，對于支持度大于給定的最小支持度的候選k-項目集就是頻繁k-項目集。

Apriori算法存在以下缺點：

（1）可能產(chǎn)生大量的候選項集，特別是候選2-項集。如果有1000個頻繁1-項集，那么該算法將會產(chǎn)生105數(shù)量級的候選2-項集。

（2）可能需要重復(fù)地掃描數(shù)據(jù)庫。

（3）計數(shù)工作量可能非常大。

2 改進的Apriori 算法及其算法實驗

采用自適應(yīng)步長躍進。因為每個頻繁項集對數(shù)據(jù)庫需要掃描一次。為了減少對數(shù)據(jù)庫的掃描次數(shù)，本算法是在己產(chǎn)生的Lk基礎(chǔ)上以hi為步長，通過連接、剪枝一次性產(chǎn)生新的以hi為步長的(k+j)-itemset (j= 1，2…， hi)的候選頻繁集，然后再掃描數(shù)據(jù)庫，確定其中真正的頻繁項集，從而可以大大減少數(shù)據(jù)庫挖掘過程中的掃描時間，以提高效率。

3 動態(tài)修剪候選項集。頻繁項集的特征

特征1: 若k維數(shù)據(jù)項目集I={i1，i2，…，ik}中，存在至少有一個im使得Nk-1(im)

特征2：對于不包含Ck-1的事務(wù)產(chǎn)生的任何項集，則刪除該事務(wù)對Lj(j≥k)的計算沒有影響。

本文主要是在一次生成候選項集的時候按照上述性質(zhì)，通過縮減和刪除數(shù)據(jù)集的規(guī)模，減少候選項集的個數(shù)，從而使得搜索空間比原來小，使Apriori算法在搜索空間上得到改進。

在原來的Apriori算法基礎(chǔ)上，改進算法U-Apriori的實現(xiàn)的主要步驟如下：

輸入：經(jīng)過布爾化的數(shù)據(jù)庫D，最小化支持閾值min_sup

輸出：Li，D中的頻繁項集。

（1）L1=find_freguent_1_itemset(D)；

（2）for(k=2;Lk≠ф;k++)

（3）Ck=apriori_gen(Lk-1,min_sup)；

（4）for each c∈Ck);

（5）for each p∈Lk-1&&q∈Lk-1；

（6）if(p⊕q==c)

（7）for(i=1;i

（8）m[i]=p[i]*q[i];

（9）if(m[i]==1)m.count++

（10）if(m.count＞=min_sup)

（11）Insert_into_Lk(m)

（12）return l=UkLk

特征3：改進Apriori 算法的實驗。在一臺計算機CPU Intel P4 2.0G， 內(nèi)存為512M 上對Apriori 算法與其改進算法進行實驗測試對比（時間單位：小時） 。試驗仿真數(shù)據(jù)來源：chess數(shù)據(jù)集（http：//fimi.cs. helsinki. fi/）。所得實驗結(jié)果如圖1所示。

從圖1中可以看出， 在挖掘速度上，改進Apriori算法較改進前有比較明顯的優(yōu)勢，在數(shù)據(jù)集大小為5萬條以下不明顯，但數(shù)據(jù)集超過10萬時開始有較大區(qū)別，改進算法的優(yōu)勢已經(jīng)很明顯。這是應(yīng)為改進算法因為減少了對數(shù)據(jù)庫的掃描次數(shù)，并顯著減小了候選集的大小，所以較大程度地提高了算法效率。

4 改進的算法在入侵檢測中的應(yīng)用

數(shù)據(jù)挖掘在入侵檢測中的應(yīng)用，主要是利用數(shù)據(jù)挖掘中的數(shù)據(jù)分類、關(guān)聯(lián)分析和序列模式挖掘，對來自不同數(shù)據(jù)源的安全審計數(shù)據(jù)進行智能化的分析處理，通過提取數(shù)據(jù)本身存在的規(guī)律性，幫助系統(tǒng)生成入侵檢測規(guī)則和建立異常檢測模型，最大限度的降低在處理安全審計數(shù)據(jù)時對先驗知識的要求。關(guān)聯(lián)分析算法可用于挖掘描述入侵行為模式的關(guān)聯(lián)規(guī)則，通過這些規(guī)則進行入侵檢測。

圖1 Aprior算法改進前和改進后算法性能比較

（1）數(shù)據(jù)獲取：在網(wǎng)絡(luò)上截取用于檢測的數(shù)據(jù)。

（2）數(shù)據(jù)預(yù)處理：對網(wǎng)絡(luò)上捕獲到的原始網(wǎng)絡(luò)數(shù)據(jù)，需要先進行預(yù)處理，將它們轉(zhuǎn)換成ASCII碼格式的網(wǎng)絡(luò)分組信息，再將網(wǎng)絡(luò)分組信息處理成網(wǎng)絡(luò)連接記錄，并將其放入審計記錄庫，為數(shù)據(jù)挖掘做準(zhǔn)備。

（3）審計記錄庫：審計記錄庫存放從網(wǎng)絡(luò)上得到的各種數(shù)據(jù)。

（4）數(shù)據(jù)訓(xùn)練集：在系統(tǒng)初期，需要收集數(shù)據(jù)進行訓(xùn)練，把已知系統(tǒng)缺陷和其他已知攻擊模式裝入知識庫中。

（5）數(shù)據(jù)挖掘算法庫：在挖掘算法庫的指導(dǎo)下, 數(shù)據(jù)挖掘引擎對審計數(shù)據(jù)進行挖掘得出新的入侵規(guī)則，然后與知識庫中的規(guī)則對比。

（6）知識庫：此處存放數(shù)據(jù)挖掘所需要的領(lǐng)域知識，這些知識將用于指導(dǎo)數(shù)據(jù)挖掘的搜索過程或者用于幫助對挖掘結(jié)果的評估。

（7）數(shù)據(jù)挖掘引擎：這是數(shù)據(jù)挖掘系統(tǒng)的最基本部件，它通常包含一組挖掘功能模塊，以便完成定性歸納、關(guān)聯(lián)分析、分類歸納、進化計算和偏差分析等挖掘功能。

（8）決策模塊：負(fù)責(zé)對非正常模式或未知模式進行人工判斷。如果判斷結(jié)果是正常模式，則將其添加到知識庫中與其相近的正常模式。如果判斷結(jié)果為異常模式，則把它添加到知識庫中與其相近的異常模式，并立即執(zhí)行必要的防范措施。

5 結(jié)束語

本文在傳統(tǒng)的Apriori算法基礎(chǔ)上，提出了引入自適應(yīng)步長躍進、動態(tài)修剪候選項集的算法，大大減少了對數(shù)據(jù)庫的掃描次數(shù)，并顯著減少了候選集的數(shù)量，提高了算法的效率，具有重要的價值和廣泛的意義。

[1]郭山清，謝立，曾英佩.入侵檢測在線規(guī)則生成模型[J].計算機學(xué)報，2006(29),1523-1532.

[2]胡亮,金剛,于漫等.基于異常檢測的入侵檢測技術(shù)[J].吉林大學(xué)學(xué)報( 理學(xué)版)，2009(47),1264-1270.