通信網(wǎng)banner.jpg)
0 引 言
從Apriori算法執(zhí)行過程可以了解到Apriori算法的缺點(diǎn)：一方面，在每一次產(chǎn)生候選項(xiàng)集時(shí)循環(huán)產(chǎn)生的組合過多，沒有具體考慮不符合閾值的組合；另一方面，對(duì)每個(gè)項(xiàng)集計(jì)算支持度時(shí)要對(duì)整個(gè)數(shù)據(jù)庫(kù)掃描一遍，對(duì)于分析網(wǎng)絡(luò)數(shù)據(jù)包這樣大型的數(shù)據(jù)庫(kù)會(huì)增加I／O開銷。這種開銷是隨著數(shù)據(jù)庫(kù)的記錄的增加呈幾何級(jí)數(shù)的增長(zhǎng)�，F(xiàn)階段人們開始探索一種能減少系統(tǒng)I／O開銷的更為快捷的算法，相繼提出了許多改進(jìn)的算法。主要有Park等人提出的基于哈希技術(shù)的DHP算法，Savasere等人提出的基于劃分技術(shù)的Partition算法，Toivonen提出的抽樣算法，Sampling、Zaki等人提出的基于等價(jià)類和圖論的MaxCique系列算法，S．Agarwal等人提出的采用有序樹數(shù)據(jù)結(jié)構(gòu)的TreeP-rojection算法以及Orlando等人提出的Apriori增強(qiáng)版的DCP算法等。而對(duì)于挖掘數(shù)據(jù)包是網(wǎng)絡(luò)數(shù)據(jù)包時(shí)，數(shù)據(jù)源的特征屬性較多而且數(shù)據(jù)包的記錄數(shù)較大，這就需要必須選擇合理的算法才能發(fā)現(xiàn)能描述用戶特征的規(guī)則。
1 引用作用度的Apriori_lift算法
1．1 作用度
作用度是采用相關(guān)分析描述規(guī)則內(nèi)在價(jià)值的度量，它描述的是項(xiàng)集X對(duì)Y的影響力的大小。作用度越高表示X的出現(xiàn)對(duì)Y出現(xiàn)的可能性影響越大，作用度度量的是X與Y之間蘊(yùn)涵的實(shí)際強(qiáng)度。
作用度表示為：
1．2 Aprior=>lift算法的描述
第一步：大項(xiàng)集的生成；
第二步：采用作用度找出強(qiáng)關(guān)聯(lián)規(guī)則。
使用第一步找到的所有頻繁項(xiàng)集產(chǎn)生期望的規(guī)則。為了獲取強(qiáng)有效關(guān)聯(lián)規(guī)則，在使用信任度的基礎(chǔ)上增加作用度計(jì)算來(lái)度量規(guī)則的有效性。具體描述過程如下：
(1)對(duì)于每個(gè)頻繁K(K≥2)項(xiàng)集L，產(chǎn)生L的所有非空子集S；
(2)對(duì)于項(xiàng)集L的每個(gè)非空子集S，規(guī)則：
如果lift[S=>(L-S)]>1，則規(guī)則“S=>(L-S)”是強(qiáng)有效關(guān)聯(lián)規(guī)則，輸出。
2 算法性能比較
在局域網(wǎng)環(huán)境中(如圖1所示)捕獲網(wǎng)絡(luò)數(shù)據(jù)包2 000個(gè)，分別采用Apriori，Apriori_lift算法挖掘，其挖掘過程及結(jié)果如下：
表3是實(shí)驗(yàn)采用的兩個(gè)數(shù)據(jù)集Tcppro，Udppro。
表4是二種算法在不同支持度(Supp)信任度(Conf)下的挖掘結(jié)果統(tǒng)計(jì)。
由表4可知，在相同的作用度與支持度的情況下，Apriori，Apriori_lift算法挖掘得到的規(guī)則逐漸遞減；在不同的作用度與支持度情況下，參數(shù)值越低挖掘出的規(guī)則越多，這主要體現(xiàn)在Apriori算法的挖掘上，而對(duì)于Apriori_lift算法當(dāng)參數(shù)值達(dá)到一定閾值時(shí)，改變參數(shù)值對(duì)其挖掘結(jié)果影響不大，改善了挖掘規(guī)則遺漏的情況。
作者：關(guān)德君 林麗 來(lái)源：現(xiàn)代電子技術(shù)
