成果介紹：一種增強的Apriori算法分析
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：鄭曉敏
關(guān)聯(lián)規(guī)則算法作為一種廣泛應(yīng)用的數(shù)據(jù)挖掘算法，其目的是在一個數(shù)據(jù)集中找出各項之間的相關(guān)關(guān)系，是Agrawal等人在1993年首先提出的，于此同時Agrawal還給出了相應(yīng)的挖掘算法AIS，但算法性能不是很高。1994年，Agrawal和Srikant共同提出了著名的基于逐層迭代思想的Apriori算法，至今Apriori算法仍然被廣泛應(yīng)用于社會生產(chǎn)的各行各業(yè)，以后許多數(shù)據(jù)挖掘領(lǐng)域的研究人員對關(guān)聯(lián)規(guī)則的挖掘問題進行了大量的研究。Savasere等人提出了一種基于劃分思想的頻繁項集發(fā)現(xiàn)算法；Tiovonen提出了基于抽樣的思想算法，該策略實際上是以犧牲精度為代價來換取算法的執(zhí)行效率，適合以效率為重的挖掘任務(wù)；Crestana-Jensen等人提出的JSApriori算法采用逐層迭代的思想在多關(guān)系挖據(jù)中挖掘關(guān)聯(lián)規(guī)則。
在網(wǎng)絡(luò)安全領(lǐng)域Apriori算法取得了廣泛應(yīng)用，將關(guān)聯(lián)規(guī)則算法用于入侵檢測技術(shù)中也是當(dāng)前研究的熱點。網(wǎng)絡(luò)發(fā)展日新月異使得攻擊手段不斷多樣化，傳統(tǒng)的僅靠單一的基于模式匹配方法的入侵檢測技術(shù)難以適用于目前的網(wǎng)絡(luò)狀況。與其他網(wǎng)絡(luò)安全產(chǎn)品不同的是，智能化的需求在入侵檢測系統(tǒng)中格外迫切，它需要具有快速、有效分析數(shù)據(jù)的能力，并以友好的方式給出有用的結(jié)果。一個合格的入侵檢測系統(tǒng)可以最大限度地減輕網(wǎng)絡(luò)管理員的工作，大大提高系統(tǒng)檢測的準(zhǔn)確性，保證網(wǎng)絡(luò)系統(tǒng)安全可靠地運行。采用作用度的Apriori算法削弱了Apriori算法的挖掘結(jié)果規(guī)則，使網(wǎng)絡(luò)入侵檢測系統(tǒng)可以精確地發(fā)現(xiàn)用戶的行為模式，能夠高效地分析出網(wǎng)絡(luò)攻擊者，提高了基于關(guān)聯(lián)規(guī)則的入侵檢測系統(tǒng)的檢測性能。
關(guān)聯(lián)規(guī)則挖掘技術(shù)能從大量數(shù)據(jù)中挖掘出有價值、反映數(shù)據(jù)項之間潛在聯(lián)系的知識信息。隨著數(shù)據(jù)不斷的積累，存儲在數(shù)據(jù)庫中的數(shù)據(jù)規(guī)模越來越大，從這些數(shù)據(jù)中挖掘相應(yīng)的關(guān)聯(lián)知識信息顯得尤為重要，這些關(guān)聯(lián)知識信息可以為決策者做出前沿判斷提供有力支撐。
1傳統(tǒng)的Apriori算法
關(guān)聯(lián)規(guī)則挖掘是從事務(wù)集合中挖掘出滿足支持度和置信度最低閾值要求的所有關(guān)聯(lián)規(guī)則，這樣的關(guān)聯(lián)規(guī)則也稱強關(guān)聯(lián)規(guī)則。常用的關(guān)聯(lián)規(guī)則算法如表1所示。
關(guān)聯(lián)規(guī)則挖掘是從事務(wù)集合中挖掘出支持度和置信度大于最低閾值（minsup，minconf）的關(guān)聯(lián)規(guī)則，該閾值是由用戶根據(jù)公式(1)、公式(2)指定。
其中，Tcount表示所有事務(wù)的集合個數(shù)，（X,Y）count表示T中同時包含X和y的事務(wù)的個數(shù)，Xcount表示T中包含X的事務(wù)的個數(shù)。
關(guān)聯(lián)規(guī)則挖掘總體過程主要包括生成頻繁項目集和產(chǎn)生強關(guān)聯(lián)規(guī)則兩步。
1)以事先設(shè)定的最小支持度為根據(jù)，找出事務(wù)集合D中所有的頻繁項目集。最終目的是根據(jù)K-頻繁項目集生成需要的(K+1）一頻繁項目集。
2)由頻繁項目集和最小支持度產(chǎn)生強關(guān)聯(lián)規(guī)則。一種比較容易的辦法就是遍歷所有的頻繁項目集，然后從每個項目集中依次取1，2，…,K個元素作為后件，該項目集中的其他元素作為前件，通過計算該規(guī)則的置信度篩選出強關(guān)聯(lián)規(guī)則。但是這種方法的效率不是很高。
Apriori關(guān)聯(lián)規(guī)則挖掘的兩步中，步驟1）根據(jù)最小支持度找出事務(wù)集合D中所有的頻繁項目集是關(guān)聯(lián)規(guī)則挖掘的中心問題，能否迅速高效地找出集合D中所有頻繁項目集會對算法效率產(chǎn)生很大影響。步驟2）根據(jù)頻繁項目集和最小支持度產(chǎn)生強關(guān)聯(lián)規(guī)則求解相對簡單和直接，但也需要根據(jù)用戶和應(yīng)用場景的不同來沒置求解指標(biāo)（如興趣度的度量標(biāo)準(zhǔn)）。
1.1 Apriori算法計算復(fù)雜度
Apriopri算法的計算復(fù)雜度主要由支持度閾值、項數(shù)、事物數(shù)3個方面因素決定。
1.1.1支持度閾值
降低支持度閾值導(dǎo)致的后果就是頻繁項集的增多，這會大大增加算法的計算復(fù)雜度，因為支持度閾值降低產(chǎn)生的候選項集大量增加并要統(tǒng)計候選項集的個數(shù)。此外，支持度閾值的降低還將增加頻繁項集的最大長度，頻繁項集最大長度的增加帶來的后果就是算法需要更多次數(shù)的掃描數(shù)據(jù)集。所以，支持度閾值會對算法的計算復(fù)雜度產(chǎn)生很大影響。
1.1.2項數(shù)（維度）
Apriori算法項數(shù)的增加導(dǎo)致的一個直接結(jié)果就是支持度計數(shù)項的增多，為了存儲支持度計數(shù)項就需要更大的存儲空間。如果頻繁項集的數(shù)目也隨著數(shù)據(jù)維度增加而增長，那么算法產(chǎn)生的候選項集將會變得十分龐大，因此，計算量和I/O開銷將明顯增加。
1.1.3事務(wù)數(shù)
Apriori算法的一個特性就是運行時間隨著事務(wù)數(shù)增加而增加，這是因為Apriori算法需要反復(fù)掃描數(shù)據(jù)集。Apriori算法采用逐層搜索的迭代方法，其核心思想是利用后項集來探索(k+l)項集。首先，通過掃描數(shù)據(jù)庫，記錄每個項的個數(shù)，從而產(chǎn)生頻繁1-項集，同時收集滿足最小支持度的這些項，得到的集合記為L1。接下來，用L1產(chǎn)生頻繁2-項集L2，然后用L2來產(chǎn)生頻繁3-項集L3依此類推，直到?jīng)]有新的頻繁k-項集產(chǎn)生，即/k=0。每產(chǎn)生一個Lk都需要把數(shù)據(jù)庫全部掃描一遍。為提高逐層迭代產(chǎn)生頻繁項集的效率，應(yīng)用先驗原理可以減少搜索空間，提高逐層迭代產(chǎn)生頻繁項集的效率”。
1 12先驗性質(zhì)
先驗性質(zhì)( apriori property)要求頻繁項集的所有非空子集也一定是頻繁的。先驗性質(zhì)是一種用于壓縮空間的重要性質(zhì)，先驗性質(zhì)的應(yīng)用可以提高頻繁項集逐層產(chǎn)生的效率。根據(jù)定義，如果項集，不滿足最小支持度閾值minsup，則，不是頻繁的，即P(l)<min_sup。如果把項A添加到項集I中，則結(jié)果項集（即IUA）不可能比J，更頻繁出現(xiàn)，因此，/UA也不是頻繁的，即P(IUA)<min_sup。例如，如果{1，2}出現(xiàn)的次數(shù)小于最小支持度（非頻繁的），那么超集{0,1，2}的組合肯定也是非頻繁的。頻繁項集的產(chǎn)生需要合并和剪枝兩個步驟。
1.3經(jīng)典的Apriori算法
下面將給出Apriori算法產(chǎn)生頻繁項集的部分偽代碼二事務(wù)集合D和最小支持度閾值（min_sup）作為算法輸入二D中的頻繁項集L作為算法輸出。具體算法如下。
Ll= find_frequent_l-itemsets(D)；//從事務(wù)集合D中發(fā)現(xiàn)所有的頻繁1一項集，定義為Ll
Ck=apriori_gen(Lk-l，min_sup);//產(chǎn)生候選項集
for each logt D{//掃描數(shù)據(jù)庫，并計數(shù)
C1=subset(Ck，t)：//獲得t所包含的候選項集for each log t Ct//循環(huán)遍歷每個候選項集c∈C．
c．count++；1
Lk={ c∈CkI c.c,ount≥min_sup)}//提取頻繁k-項集
return L=UkLk；
apriori_gen(Lk-l:frequent(k-l) -itemsets)
∥產(chǎn)生k一項候選項集
for each itemset ll∈Lk-l{//循環(huán)遍歷每個項
for each itemset l2∈Lk_l{
if(l1[1]=l2[1])“(1.[2]=l:[2])“…”(1, [k-l]=12
[k-1])“(l1 [k-l]< 12[k-1]){
c=l1∞l2；//11和l2做笛卡爾積
if has-infrequent_subset(c,Lk-1)
delete c；／／刪除非頻繁的候選項
else add c to Ck；}
return Ck;
has_infrequent_subset(c:candidate k-itemset;Lk_,:frequent(k-l)-
itemsets)∥使用先驗知識
for each itemset (k-l)-subset s of c{
if s 不屬于Lk-1
return true,
return false;1
上述算法中的apriori-gen函數(shù)通過候選項集的產(chǎn)生和候選項集的剪枝操作產(chǎn)生候選項集。
1.4使用傳統(tǒng)Apriori算法產(chǎn)生頻繁項集
表2是一個日志審計數(shù)據(jù)庫的具體例子。在這個數(shù)據(jù)庫中有9條交易記錄，也就是IDl=9。T1,T2，…，T9表示一條日志記錄項集，以，a,b,c…表示一條日志記錄中的項。
下面的步驟用來解釋候選項集和頻繁項集的產(chǎn)生，Itemset表示項集，Sup．count表示支持度計數(shù)。表1的事務(wù)數(shù)據(jù)最小支持計數(shù)為3。
1)掃描事務(wù)集合D，統(tǒng)計每個候選項的支持度計數(shù)，如表3所示。
2)比較候選項支持度計數(shù)與最小支持度計數(shù)，刪掉不符合條件的候選，產(chǎn)生頻繁1-項集L1，如表4所示。
- 從L1，中產(chǎn)生候選2-項集G，如表5所示
- 掃描事務(wù)集合D，對每個候選項計數(shù)，如表6所示。
5)將候選項支持度計數(shù)與最小支持度比較，產(chǎn)生頻繁
2一項集l2，如表7所示。
- 從L2中產(chǎn)生候選3一項集C3，如表8所示。
- 掃描事務(wù)集合D，對每個候選項計數(shù)，如表9所示。
8)將候選項支持度計數(shù)與最小支持度比較，刪掉不符合條件的候選，產(chǎn)生頻繁3-項集L3，如表10所示。
1.5 Apriori算法的改進方法
1.5.1基于動態(tài)項集計數(shù)的改進方法
基于動態(tài)項集計數(shù)的優(yōu)化方法將數(shù)據(jù)庫劃分為標(biāo)記開點的塊，算法可以在任何開始點添加新的侯選項集。該方法動態(tài)地評估已被計數(shù)的所有項集的支持度，如果一個項集的所有子集己被確定為頻繁的，則添加它作為新的侯選項集。
1.5.2基于哈希(Hash)表技術(shù)的改進方法
利用Hash表技術(shù)可以幫助有效減少候選k-項集Ck(k≥1)所占用的空間。利用這樣Hash表技術(shù)可以有效減少需要檢查的候選項集數(shù)目。
1.5.3基于采樣的優(yōu)化方法
基于采樣的優(yōu)化方法是在一個給定數(shù)據(jù)庫D的隨機樣本S中進行挖掘，這種方法犧牲了精確性換取有效性，內(nèi)存的大小決定了樣本S的大小。樣本S中的頻繁項集不一定是數(shù)據(jù)庫D中的頻繁項集，而且，數(shù)據(jù)庫D中的頻繁項集不一定出現(xiàn)在樣本S的頻繁項集中。
2改進的Apriori算法
對于非常大的數(shù)據(jù)庫，傳統(tǒng)Apriori算法產(chǎn)生龐大的候選項集，所以它需要更大的計算代價。為了避免這個缺點，本文介紹一種改進的Apriori算法來減少候選集數(shù)量。本文提出的系統(tǒng)變量transaction_size(TS)包括個人交易項目的數(shù)量，如果transaction size小于閾值，這一交易將從數(shù)據(jù)庫中刪除。
2.1算法描述
改進的Apriori算法通過單遍掃描數(shù)據(jù)集確定每個項的支持度，進而就得到所有的頻繁1一項集的集合L1。依照此方法，使用上一次迭代發(fā)現(xiàn)的頻繁（K-1）-項集，產(chǎn)生新的候選k-項集。apriori-gen函數(shù)負(fù)責(zé)實現(xiàn)候選項的產(chǎn)生，算法需要再次掃描數(shù)據(jù)集，計算出候選項的支持度。計算候選項的支持度計數(shù)之后，算法將刪除支持度計數(shù)小于min_sup的所有候選項集。更新數(shù)據(jù)庫，通過掃描事務(wù)集合D、/k-1、Lk，將存在Lk-1中，不存在Lk中且未在頻繁1一項集中出現(xiàn)的元素從數(shù)據(jù)庫中刪除。最后再一次掃描事務(wù)集合D，計算每個事物中的元素個數(shù)，若元素個數(shù)小于k則刪除該條事物。當(dāng)沒有新的頻繁項集產(chǎn)生，即/k=0時算法結(jié)束。
下面給出了改進的Apriori算法產(chǎn)生頻繁項集的部分偽代碼。事務(wù)集合D和最小支持度閾值(min_sup)作為算法輸入，D中的頻繁項集L作為算法輸出。具體實現(xiàn)算法如下。
delete datarow;))//刪除TS計數(shù)小于所求頻繁項集數(shù)的記錄
2.2算法實例
以下步驟是使用改進的Apriori算法產(chǎn)生表1 1的頻繁項集，TS表示事務(wù)元素個數(shù)。
1)掃描表11每個1一項集的計數(shù)，生成候選l一項集，即表12，刪除候選1一項集中不滿足最小支持度的項集，生成頻繁1一項集，即表13。
表1 1原始日志審計數(shù)據(jù)庫實驗數(shù)據(jù)
2)執(zhí)行更新數(shù)據(jù)庫的操作，刪除數(shù)據(jù)庫中未在頻繁1一項集中出現(xiàn)的項，同時更新數(shù)據(jù)庫中TS的計數(shù)。檢查新數(shù)據(jù)庫中每項事務(wù)TS是否小于k，若小于k，則在數(shù)據(jù)庫中刪除該項事務(wù)（k為候選項的個數(shù)），完成數(shù)據(jù)庫更新，如表14所示。根據(jù)已產(chǎn)生的頻繁1-項集，進行連接操作，生成候選2-項集，如表15所示。掃描數(shù)據(jù)庫記錄候選2-項集支持度計數(shù)，刪除候選2-項集中不滿足最小支持度計數(shù)的項，生成頻繁2-項集，如表16所示。
3)再次執(zhí)行更新數(shù)據(jù)庫的操作，此時不再進行刪項操
作，只檢查新數(shù)據(jù)庫中每項事務(wù)TS是否小于k，若小于k，則在數(shù)據(jù)庫中刪除該項事務(wù)（k為候選項的個數(shù)），完成數(shù)據(jù)庫更新，新數(shù)據(jù)庫如表17所示。根據(jù)已產(chǎn)生的頻繁2-項集，進行連接操作，生成候選3-項集，如表18所示。掃描更新后的數(shù)據(jù)庫記錄候選3-項集支持度計數(shù)，刪除候選3-項集中不滿足最小支持度計數(shù)的項來生成頻繁3-項集，如表19所示。
3傳統(tǒng)Apriori和改進的Apriori算法性能比較
本文在不同的實例集和置信度上分別比較了兩種算法的性能，如圖1所示。
圖l中，縱軸代表時間，橫軸代表置信度。
從圖1可以看出，對于3個不同的置信度執(zhí)行改進的Apriori算法都比傳統(tǒng)的Apriori算所花的時間少。因此，改進的Apriori算法是一個高效、可擴展的完整的頻繁模式挖掘方法。
4結(jié)束語
本文通過分析Apriori算法，結(jié)合文獻中已有的經(jīng)典Apriopri算法，提出了_一種新的更高效的算法，并給出了算法實現(xiàn)思想。改進的Apriori算法通過消除數(shù)據(jù)庫中不必要記錄的傳輸有效減少了I/O所花費的時間，Apriori算法的效率得到了極大的優(yōu)化，從海量數(shù)據(jù)中挖掘關(guān)聯(lián)信息將會更陜。
評估這兩種算法的性能是基于它們產(chǎn)生關(guān)聯(lián)規(guī)則所用的時間。經(jīng)過分析可以得出，改進的Apriori算法的性能比傳統(tǒng)的Apriori算法更好。
但本文提出的改進Apriori算法除了具有Apriori普遍的缺點——產(chǎn)生大量的頻繁項集外，當(dāng)數(shù)據(jù)庫中的頻繁項集中元素個數(shù)較多時，算法執(zhí)行時并沒有太多冗余項可刪除，這就造成了無謂的掃描數(shù)據(jù)庫。因此該算法在有些情況下也會增加掃描數(shù)據(jù)庫的次數(shù)，如何避免這種情況將是進一步研究的問題。
5摘要：
在當(dāng)今這個信息極度發(fā)達的社會，網(wǎng)絡(luò)數(shù)據(jù)急劇膨脹，激增的數(shù)據(jù)背后隱藏著許多重要的信息，所以對大量數(shù)據(jù)進行分析是必要的。Ap rio ri算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項集算法，其核心思想是通過候選集生成和情節(jié)的向下封閉檢測兩個階段來挖掘頻繁項集�？赡墚a(chǎn)生大量的候選集，以及可能需要重復(fù)掃描數(shù)據(jù)庫是Ap rio ri算法的兩大缺點。文中提出了一種需要更少的掃描時間的Apriori算法，在剪枝候選項集的同時也在消除冗余的子項集的產(chǎn)生 改進的Apriori算法通過消除數(shù)據(jù)庫中不需要記錄的傳輸有效減少了I/O所花費的時間，Apriori算法的效率得到了極大的優(yōu)化。文章給出了算法實現(xiàn)思想及證明，并對傳統(tǒng)的和改進的Ap rio ri算法進行比較和分析。
