網(wǎng)絡(luò)審計(jì)系統(tǒng)中Apriori算法的應(yīng)用與研究

1、網(wǎng)絡(luò)審計(jì)系統(tǒng)中Apriori算法的應(yīng)用與研究機(jī)械制造論文網(wǎng)絡(luò)審計(jì)系統(tǒng)中Apriori算法的應(yīng)用與研究網(wǎng)絡(luò)審計(jì)系統(tǒng)中Apriori算法的應(yīng)用與研究張繼周1李婷2(1.西安財(cái)經(jīng)學(xué)院網(wǎng)絡(luò)與教育技術(shù)中心，陜西西安710061 ; 2.西安財(cái)經(jīng)學(xué) 院統(tǒng)計(jì)學(xué)院，陜西西安710061 )摘要此文介紹了關(guān)聯(lián)規(guī)則的主要內(nèi)容，結(jié)合了網(wǎng)絡(luò)審計(jì)系統(tǒng)中事務(wù)數(shù)據(jù)庫的 特征,從Apriori算法的基本概念出發(fā)，根據(jù)網(wǎng)絡(luò)審計(jì)的特點(diǎn)，介紹了一種基于 分片的改進(jìn)的Apriori算法的，并給出證明。最后在改進(jìn)的策略選擇上給出結(jié)論。關(guān)鍵詞網(wǎng)絡(luò)審計(jì)；關(guān)聯(lián)規(guī)則；Apriori算法網(wǎng)絡(luò)安全審計(jì)是網(wǎng)絡(luò)安全中重要的一環(huán)。審計(jì)系統(tǒng)一般架設(shè)在局域

2、網(wǎng)絡(luò)出口 上，采用串聯(lián)監(jiān)控或旁路監(jiān)控兩種形式,對所有流通的封包進(jìn)行審計(jì)挖掘。通過 匹配規(guī)則庫中的特征值來完成報(bào)警、攔截、日志等一系列審計(jì)工作。當(dāng)前的網(wǎng)絡(luò) 審計(jì)的最大速度瓶頸就是面對海量的審計(jì)記錄無；去塊速挖掘出異常行為，而且出 現(xiàn)大量誤報(bào)，影響管理者的判斷，嚴(yán)重影響了網(wǎng)絡(luò)審計(jì)系統(tǒng)的性能。網(wǎng)絡(luò)審計(jì)中的行為主要表現(xiàn)形式為大量的含有不同特征值的數(shù)據(jù)，這些數(shù)據(jù)都 有同樣的格式，即TCP報(bào)文或UDP報(bào)文，因此使用數(shù)據(jù)挖掘技術(shù)中的關(guān)聯(lián)規(guī)則 挖掘來進(jìn)行發(fā)現(xiàn)特征數(shù)據(jù)就是很有效的方法。關(guān)聯(lián)規(guī)則挖掘(Data Mining )首 先由Rakesh Apwal等人提出。關(guān)聯(lián)是指兩個(gè)或兩個(gè)以上項(xiàng)集的值之間的某中 規(guī)律

3、性。關(guān)聯(lián)規(guī)則挖掘的目的是找出數(shù)據(jù)庫中的隱藏的關(guān)聯(lián)關(guān)系。從海量的數(shù)據(jù) 中找出我們需要的知識和規(guī)律，這些知識和規(guī)律是隱含在數(shù)據(jù)倉庫中具有決策價(jià) 值的。由于關(guān)聯(lián)規(guī)則挖掘技術(shù)在數(shù)據(jù)特征值分析方面有看先天的優(yōu)勢，所以采用 關(guān)聯(lián)規(guī)則挖掘技術(shù)進(jìn)行網(wǎng)絡(luò)審計(jì)的數(shù)據(jù)挖掘是目前最好的選擇。運(yùn)用關(guān)聯(lián)規(guī)則挖 掘用戶的行為模式不但能發(fā)現(xiàn)相關(guān)屬性值之間的關(guān)聯(lián)規(guī)則，而且通過合并和泛 化，可以形成新的有價(jià)值的特征。1關(guān)聯(lián)規(guī)則1.1 關(guān)聯(lián)規(guī)則定義關(guān)聯(lián)規(guī)則是Agrawl等人于1993年提出的，關(guān)聯(lián)規(guī)則發(fā)展至今已經(jīng)成為數(shù)據(jù) 挖掘中的一個(gè)重要研究內(nèi)容。設(shè)I=il , i2.im )是一個(gè)項(xiàng)目合集，相關(guān)事務(wù)數(shù)據(jù)庫M=tl,t2tn ),

4、 其中每個(gè)事務(wù)tj表示M的第j個(gè)事務(wù),是由I中的若干項(xiàng)目構(gòu)成的集合，即tj? 普I。事務(wù)tj包含X ,是指對于I的子集X ,有X?置tj。關(guān)聯(lián)規(guī)則的主要表現(xiàn)形 式為“X-Y”,其中X?置I, Y?置I,并且XAY二？熟X稱為關(guān)聯(lián)規(guī)則的前項(xiàng)， Y稱為關(guān)聯(lián)規(guī)則的后項(xiàng)。1.2 描述關(guān)聯(lián)規(guī)則屬性的兩個(gè)參數(shù)1.2.1 支持度(Support)設(shè)支持度表示為s，是指事務(wù)數(shù)據(jù)庫中的事務(wù)同時(shí)含有A和B的百分比,記為 S(AUB),支持度描述了 A和B這兩個(gè)項(xiàng)集的并集在所有事務(wù)中出現(xiàn)的概率。support(A?iE B)=P(AuB)1.2.2 置信度(Confidence )關(guān)聯(lián)規(guī)則的置信度是指存在看項(xiàng)集A和

5、B , B出現(xiàn)在包含A的事務(wù)中的頻率。confidence(A?：EB)= P(Af)B)XY(confidence,support)表示一個(gè)關(guān)聯(lián)規(guī)則。置信度表示規(guī)則的重要性，支持度表示規(guī)則出現(xiàn)的頻率。置信度越高說明規(guī)則重要性越強(qiáng)；支持度越高，規(guī)則出現(xiàn)的頻率越高。1.3 關(guān)聯(lián)規(guī)則挖掘步驟關(guān)聯(lián)規(guī)則的挖掘有兩個(gè)步驟。1.3.1 發(fā)現(xiàn)頻繁項(xiàng)集通過給定的最小支持度(Smin)，找到所有滿足“支持度之Smin"的項(xiàng)目集, 滿足條件的項(xiàng)集稱為頻繁項(xiàng)集。1.3.2 生成關(guān)聯(lián)規(guī)則通過給定的最小(Cmin),如果對每個(gè)頻繁項(xiàng)集進(jìn)行置信度的計(jì)算，然后對比 Cmin ,計(jì)算量將耗費(fèi)大量的時(shí)間,所有利用定理

6、，頻繁項(xiàng)集的子集也一定是頻 繁項(xiàng)集，就可以對每個(gè)最大頻繁項(xiàng)集進(jìn)行置信度的計(jì)算，大大減少了計(jì)算量。對于第二個(gè)問題實(shí)現(xiàn)相對容易，所以，所有優(yōu)化算法都是集中在第一個(gè)問題的 研究上，它是關(guān)聯(lián)規(guī)則算法的核心問題。2Apriori算法的應(yīng)用與改進(jìn)2.1 Apriori 算法Apriori算法是一種尋找頻繁項(xiàng)集的關(guān)聯(lián)規(guī)則挖掘算法，通過多次掃面數(shù)據(jù)庫 來發(fā)現(xiàn)頻繁項(xiàng)集。算法第一步采用逐層迭代的方法找出所有頻繁項(xiàng)目集，要求頻 繁項(xiàng)集的支持度大于等于設(shè)定的最小支持度；第二步從頻繁項(xiàng)集中構(gòu)造置信度不 小于設(shè)定的身氐閾值。2.2 算法步驟步驟如下：(1)設(shè)定最小支持度s和最小置信度c。(2 ) Apriori算法使用候

7、選項(xiàng)集。首先產(chǎn)生出候選的項(xiàng)的集合。即候選項(xiàng)集。若候選項(xiàng)集的支持度大于或等于最小支持度，則該候選項(xiàng)集為頻繁項(xiàng)集。(3 )在Apriori算法的過程中，首先從數(shù)據(jù)庫讀入所有的事務(wù)，每個(gè)項(xiàng)都被 看作候選1頁集，得出各項(xiàng)的支持度,再使用頻繁L項(xiàng)集合集來產(chǎn)生候選2_ 項(xiàng)集集合，因?yàn)橄闰?yàn)原理保證所有非頻繁的L項(xiàng)集的超集都是非頻繁的。(4 )再掃描數(shù)據(jù)庫，得出候選2一項(xiàng)集集合，再找出頻繁2J頁集,并利用這 些頻繁2_項(xiàng)集集合來產(chǎn)生候選3頁集。(5)重復(fù)掃描數(shù)據(jù)庫,與最小支持度比較，產(chǎn)生更高層次的頻繁項(xiàng)集，再從 該集合里產(chǎn)生下一級候選項(xiàng)集，直到不再產(chǎn)生新的候選項(xiàng)集為止。2.3 基于分片的算法改進(jìn)首先，把D中的

8、事務(wù)劃分成n個(gè)非重疊的分片,如果D中事務(wù)的最小相對支 持度閾值為min_sup ,則每個(gè)分片的最小支持度計(jì)數(shù)為min_supX該分片的事 務(wù)數(shù)。對于每個(gè)分片，掃描數(shù)據(jù)庫，找出所有的局部頻繁項(xiàng)集引。局部頻集可 能是也可能不是整個(gè)數(shù)據(jù)庫D的頻集。然而，D的彳七可頻集必須作為局部頻集 至少出現(xiàn)在一個(gè)分片中，證明如下：證明：反證法。假設(shè)頻集在D的任何一個(gè)分片都不頻繁。令F為任意一個(gè)頻 集，D為事務(wù)數(shù)據(jù)庫集合，C為D中的事務(wù)總數(shù)，A為D中包含F(xiàn)的事務(wù)總數(shù), min_sup為最小支持度。因?yàn)镕是一個(gè)頻集，所以A=CXmin_supo將D分成 n個(gè)不重疊的分片：dl, d2 , d3 , dn ,令Cl,

9、C2 , C3 , Cn為分片dl f d2 f d3 f . f dn 各自對應(yīng)的事務(wù)數(shù) f 則 C=Cl+C2+C3+.+Cno 令 al, a2 , a3 , an為分片dl , d2 , d3 , dn中包含F(xiàn)的事務(wù)數(shù)，則A=al+a2+a3+.+ano 因此 A=al+a2+a3+.+an= ( C1+C2+C3+Cn ) Xmin_supo因?yàn)榍懊嬉呀?jīng)假設(shè)F在D中任意一個(gè)分片dl, d2 , d3 , . , dn 中都不頻繁，則 alClXmin_sup; a2C2Xmin_sup; a3C3Xmin_sup; .;anCnXmin_supo 將所有不等式相加得:al+a2+a3

10、+.+an (Cl+C2+C3+.+Cn )Xmin_sup，即 ACXmin_sup，則推出 F 不是一個(gè)頻集。這和前面定義的F是一個(gè)頻集相矛盾,故假設(shè)錯(cuò)誤，所以D的任何頻集必須作 為局部頻集至少出現(xiàn)在一個(gè)分片中。因此，所有局部頻集都是D的候選項(xiàng)集，來自所有分片的局部頻集作為D的 全局候選項(xiàng)集。然后，第二次掃描數(shù)據(jù)庫D,評估每個(gè)候選的實(shí)際支持度，以確 定全局頻繁項(xiàng)集。它的優(yōu)化算法步驟為:(1)把數(shù)據(jù)庫劃分成一些模塊大小相當(dāng) 的塊，記為N塊；(2 )在每一塊內(nèi)產(chǎn)生一組自己的頻繁項(xiàng)目集；記為Li ; ( 3 ) 最后合并這些項(xiàng)目集生成一個(gè)全局候選的頻繁項(xiàng)目集；(4 )在數(shù)據(jù)庫內(nèi)，計(jì)算候 選項(xiàng)頻繁(下轉(zhuǎn)第264頁)(上接第46頁)目集的支持度，得到確定的最終頻 繁項(xiàng)目集。基于分片的Apriori算法在網(wǎng)絡(luò)審計(jì)這種類型的事務(wù)庫的挖掘中有著明顯的優(yōu) 勢，審計(jì)事務(wù)庫的特點(diǎn)就是數(shù)據(jù)具有特有的類型，每個(gè)類型有著特定的特征值, 利于分片挖掘，數(shù)據(jù)分布較為分散，數(shù)據(jù)之間的關(guān)聯(lián)性不高，采用基于分片的 Apriori算法顯著提高了挖掘效率，提高算法的可用性。3結(jié)束語在實(shí)際的應(yīng)用中，針對不同特點(diǎn)的TCP網(wǎng)絡(luò)，有看適合的改進(jìn)策略，這些策 略不用做到面面俱到，只要具有一定的針對性就可以。網(wǎng)絡(luò)擁塞的改進(jìn)是十分靈 活的，方法也很非常多，其原因正是因?yàn)椴煌W(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)特點(diǎn)不同,從而 選擇合適的改進(jìn)策略是關(guān)鍵。