王福新

摘 要：使用關(guān)聯(lián)規(guī)則算法apriori與入侵檢測相結(jié)合，并針對Apriori算法對數(shù)據(jù)庫的描次數(shù)過多、系統(tǒng)的I/O負載大和產(chǎn)生大量的無關(guān)中間項集等弊端，提出了一種改進的Apriori算法，打破了傳統(tǒng)的算法實現(xiàn)步驟減少了數(shù)據(jù)庫的掃描次數(shù)，降低了系統(tǒng)I/O負載；實驗表明，改進的Apriori算法能有效地提高運行速度和效率，同時提高入侵檢測的效率與準確性。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；apriori算法；IDS

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1671-2064（2017）19-0018-04

1 關(guān)聯(lián)規(guī)則挖掘算法

關(guān)聯(lián)規(guī)則（Association rules）挖掘是從大量數(shù)據(jù)中挖掘發(fā)現(xiàn)其項目集（itemset）之間的關(guān)聯(lián)或相關(guān)聯(lián)系.關(guān)聯(lián)規(guī)則挖掘問題是R.Agrawal等人于1993年在文獻中首先提出的.關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中一組數(shù)據(jù)項之間的某種潛在關(guān)系的規(guī)則。

經(jīng)典的apriori。在已經(jīng)提出的諸多關(guān)聯(lián)規(guī)則挖掘算法中，R.Agrawal和 R.Srikant在Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集算法中最有影響的.目前絕大多數(shù)的頻繁項集挖掘算法都是以Apriori算法為核心，或是其變體，或是其擴展。

Apriori算法的名字基于這樣的事實：算法使用頻繁項集性質(zhì)的先驗知識，Apriori算法實際上是一種逐層搜索的迭代算法，k-項集用于探索（k+1）項集該算法將關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)分為兩部分：

第一步是迭代出所有的頻繁項集；

第二步是由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。

對于Apriori算法而言，它存在著本身難以克服的缺陷。

（1）多次掃描數(shù)據(jù)庫，在Apriori算法的描述中，每生成一個候選項集，都要對數(shù)據(jù)庫進行一次搜索.如果要生成最大長度為K的頻繁項集，則要對數(shù)據(jù)庫進行K次掃描，當數(shù)據(jù)庫中存放大量的數(shù)據(jù)時，在有限的內(nèi)存容量下，系統(tǒng)I/O的負載就會相當大，每次掃描數(shù)據(jù)庫的時間就會很長，這樣效率當然非常低。

（2）它的瓶頸在于它的巨大的候選集的生成，例如，104個頻繁1-項集要生成107個候選2-項集要找尺寸為100的頻繁模式，如{X1，X2，…，X100}，你必須先產(chǎn)生2100（1030個候選集，因此，優(yōu)化Apriori算法主要在于減少其候選集的生成。

2 apriori與入侵檢測

2.1 入侵檢測

入侵檢測系統(tǒng)（Intrusion Detection System IDS）可以定義為識別針對計算機或網(wǎng)絡(luò)資源的惡意企圖和行為并對此做出響應(yīng)的系統(tǒng).它通過對計算機網(wǎng)絡(luò)或計算機系統(tǒng)中的若干關(guān)鍵點收集信息并對其進行分析，從中發(fā)現(xiàn)網(wǎng)絡(luò)或系統(tǒng)中是否有違反安全策略的行為和被攻擊的跡象。入侵檢測系統(tǒng)是將進行入侵檢測的軟件與硬件的組合，它是一種主動的防護措施，它從系統(tǒng)內(nèi)部和網(wǎng)絡(luò)中收集信息，從這些信息中分析計算機是否有安全問題，并采取相應(yīng)的措施。

2.2 基于apriori的入侵檢測模型（見圖1）

通過對網(wǎng)絡(luò)信息進行預(yù)處理通過apriori提取用戶行為特征或規(guī)則等，再對所得的規(guī)則進行歸并更新，建立起規(guī)則庫，依據(jù)規(guī)則庫的規(guī)則對當前用戶的行為進行模式匹配，判斷用戶的訪問行為是否合法并將結(jié)果輸出給用戶。

3 apriori的優(yōu)化

Apriori算法每次生成候選項目集后，又要回去掃描數(shù)據(jù)庫來判斷這些是否頻繁項目集，來判斷這些候選項目集是否頻繁項目集，造成了I/O的開銷很大，效率很低，因此，在算法的第一步對Apriori進行優(yōu)化。

（1）優(yōu)化方法一：根據(jù)頻繁k-項集的支持事務(wù)來計算候選（k+1）-項集中候選項的支持度，進而找出候選集中的頻繁項目，也就是說支持（k+1）-項集的事務(wù)必然也會支持它的k階子集.換句話說，支持（k+1）-項集的所有k階子集的事務(wù)必然也支持（k+1）-項集.這里我們定義：若集合D中有K+1個元素，那么由其中任何k元素組成的非空集合稱為集合D的k階子集.如果能夠從所有k階子集的支持事務(wù)中找出其交集即公共部分，那就相當于求出了（K+1）-項集的支持事務(wù)，這樣就避免了對源數(shù)據(jù)庫進行多次掃描，從而提高了算法的效率，以最小支持事務(wù)來作為剪枝的標準，我們定義最小支持事務(wù)為最小支持度（minsup）與數(shù)據(jù)庫記錄總數(shù)的乘積。

算法描述：TID事務(wù)的唯一編號，定義TIDS（Xk）是數(shù)據(jù)庫中項集Xk支持的事務(wù)的集合，TIDS（Xk）={TID：TID是Xk支持的}，最小支持事務(wù)=minsup×|D|。

算法偽代碼如下：

Procedure weight_apriori（Lk：find_frequent_k _itemset，S： descend power subset of Ck，TIDS（Ck）： set of Ck support transactions）

{

Scan D；

Find TIDS //掃描數(shù)據(jù)庫，記錄支持每個項目的事務(wù)

C1=Generate_C1（DB）；//生成候選1-項集

L1=find_frequent_1_itemset；//頻繁1-項集

K=2；

While Lk-1≠ {

CK = apriori_gen （LK - 1 ） ；//生成新的候選集

For each candidates itemset C∈CK {

Ck.suptrans= TIDS（Ck）；

For each descend power subset S {endprint

Ck.suptrans= Ck.suptrans∩S.suptrans；}

C.count= |Ck.suptrans|；//計算支持事務(wù)集中的元素個數(shù).

K++；

}

//計算加權(quán)支持度

Lk = {c ∈Ck | C.count ≥ wminsup*|D|}；

}

Return F=Uk Lk ；

}

function Apriori_Gen（ Lk ）{

For all itemset g1 ， g2 ∈ Lk do {

if then {

add c to Ck ；

For all k-1 項集 do //剪枝

if （） then delete c from Ck ；

}}

Return Ck ；

}

算法的有效性分析：對于Apriori算法而言，在每次生成候選頻繁項目集后，要重復(fù)掃描數(shù)據(jù)庫計算項目集支持度判斷候選項目集是否頻繁項目集，造成了系統(tǒng)的布必要開銷，本算法只需要掃描一次數(shù)據(jù)庫，通過對降階子集支持的事務(wù)的交集進行計算，從而避免多次掃描數(shù)據(jù)庫即可求出所有頻繁項集，進而提高了算法的效率.關(guān)于權(quán)重的設(shè)定，對于權(quán)重的設(shè)定將直接影響關(guān)聯(lián)規(guī)則的挖掘結(jié)果，對于不同屬性的權(quán)重值的設(shè)定除了依賴于主觀的設(shè)定以外還可以根據(jù)實際情況建立模型來給出。

（2）優(yōu)化方法二：在生成候選項目集之前判斷出某些候選項目集是非頻繁項目集，則可以在再次掃描數(shù)據(jù)庫計算支持度時不予考慮，這樣計算候選項目集支持度的記錄的數(shù)目小于數(shù)據(jù)庫原來的數(shù)目，以達到提高算法的效率的目的。

算法的描述：

Procedure weight_apriori（Lk：find_frequent_k _itemset，Rm： set of rm_item）

{

C1=Generate_C1（DB）；//生成候選1-項集

L1=find_frequent_1_itemset；//頻繁1-項集

K=2；

While Lk-1≠ {

CK = apriori_gen （LK - 1 ） ；//生成新的候選集

If RmCk

Delete Rm ；

K++；}

//計算加權(quán)支持度

Lk = {c ∈Ck | C.sup ≥ wminsup}；

Return F=Uk Lk

}

4 實驗結(jié)果及分析

經(jīng)典的apriori應(yīng)用IDS結(jié)果。使用麻省理工學(xué)院的林肯實驗室的一次分布式拒絕服務(wù)攻擊的數(shù)據(jù)作為實驗室數(shù)據(jù)，該數(shù)據(jù)使用基于網(wǎng)絡(luò)的tcpdump嗅探器采集保存為XML格式的日志文檔。

程序是使用C#語言進行編程實現(xiàn)的基于關(guān)聯(lián)規(guī)則的入侵檢測系統(tǒng)，該系統(tǒng)使用XML數(shù)據(jù)作為分析數(shù)據(jù)的來源，其中部分程序如下：

public void CreateItemsetSubsets（int Level， ItemsetArrayList itemSubset， ItemsetArrayList parentItemset，Database transactionsData）

{

int length = 0；

ItemsetArrayList childSubset = new ItemsetArrayList（1）；

ItemsetArrayList rulesItemset；

if（itemSubset.Count > Level）

{

foreach（ItemsetArrayList item in itemSubset）

{

ItemsetArrayList [] subsets = this.CreateItemsetSubsets（item）；

//僅有一個父項目用來生成關(guān)聯(lián)規(guī)則

if（parentItemset == null）

{ parentItemset = item； }

if （subsets ！= null）

{ length = subsets.Length； }

else{ break； }

for（int count = 0； count < length； count++）

{

//向項目表中添加項目與子集

transactionsData.AddSubset（item，subsets[count]）；

childSubset.Add（subsets[count]）；

//僅向 ItemsetArrayList 類中添加unique值

//創(chuàng)建一個含有的支持度，信任度和關(guān)聯(lián)規(guī)則的與子集相關(guān)的如

//父項-子集的規(guī)則項

rulesItemset = （parentItemset-subsets[count]）；

this.CreateItemsetRuleset（parentItemset， subsets[count]， rulesItemset，transactionsData）；

}

}

//為項目遞歸生成子集tendprint

childSubset.TrimToSize（）；

this.CreateItemsetSubsets（0， childSubset， parentItemset， transactionsData）；

}

}

由于tcpdump嗅探器保存下來的數(shù)據(jù)需要首先進行轉(zhuǎn)換預(yù)處理.既進行離散化，通過實驗得到一下結(jié)果.例如172.16.115.20， 202.77.162.213，tcp，1023，514。

通過試驗我們得到了一系列的關(guān)聯(lián)規(guī)則，如第84條規(guī)則。

202.77.162.213，tcp --> 514 63.1578947368421%

程序結(jié)果如圖2。

5 結(jié)語

基于Apriori的加權(quán)關(guān)聯(lián)規(guī)則算法是在Apriori算法基礎(chǔ)上針對Apriori算法由候選項目集生成頻繁項目集的過程進行的算法的優(yōu)化。在Apriori算法的描述中每生成一個候選項集，都要對數(shù)據(jù)庫進行一次掃描，因此需要多次對數(shù)據(jù)庫進行掃描，當數(shù)據(jù)庫中存放大量的事務(wù)數(shù)據(jù)時，在有限的內(nèi)存容量下，系統(tǒng)I/O負載就會非常大，每次掃描數(shù)據(jù)庫的時間就會很長，效率就非常低。

第一種優(yōu)化方法只需要掃描一次數(shù)據(jù)庫，然后通過統(tǒng)計后選項集Ck的K階子集支持的事務(wù)來計算支持度的方法，減少了掃描數(shù)據(jù)庫的次數(shù)，從而提高了Apriori算法的運行效率；第二種優(yōu)化方法并沒有從根本減少對數(shù)據(jù)庫的掃描次數(shù)，只是通過減少生成頻繁項目集中候選項目集中的記錄個數(shù)來達到提高Apriori算法效率的目的，這種方法在在數(shù)據(jù)庫的數(shù)據(jù)量很大時，效果并明顯，因此比較而言，第一種方法的效率應(yīng)該較高.而兩種算法都是對經(jīng)典apriori的效率改進，極大的提高了IDS的運行速度以及降低了其誤報率。實驗結(jié)果，見圖3。

參考文獻

[1]沈亮.網(wǎng)絡(luò)入侵檢測系統(tǒng)原理與應(yīng)用[M].電子工業(yè)出版社，2013，（10）.

[2]崔貫勛，李梁，王柯柯，茍光磊，鄒航.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究與改進[J]，計算機應(yīng)用，2010（11）.

[3]薛靜鋒，祝烈煌.入侵檢測技術(shù)[M].人民郵電出版社，2016，（1）.

[4]關(guān)心，王新.基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)研究[J].信息技術(shù)，2007，（10）：100-103.

[5]章小龍.基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)研究[J].沈陽工程學(xué)院學(xué)報（自然科學(xué)版），2007，（10）：364-366.

[6]宋世杰，胡華平，胡笑蕾，金士堯.數(shù)據(jù)挖掘技術(shù)在網(wǎng)絡(luò)型異常入侵檢測系統(tǒng)中的應(yīng)用[J]. 計算機應(yīng)用，2003，（12）：20-23.

[7]牛建強，曹元大.基于數(shù)據(jù)挖掘的IDS日志數(shù)據(jù)分析處理[J].計算機應(yīng)用研究，2003：82-84.

[8]張譯，劉衍珩，田大新，李川川，王媛.基于關(guān)聯(lián)規(guī)則的入侵檢測系統(tǒng)[J].吉林大學(xué)學(xué)報（信息科學(xué)版），2006，（3）：204-209.

[9]李川，張永輝譯.Ian H.Witten Eibe Frank Mark A.Hall著.數(shù)據(jù)挖掘?qū)嵱脵C器學(xué)習(xí)工具與技術(shù)[M].機械工業(yè)出版社，2014，（5）.endprint