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

張繼周+李婷

【摘 要】此文介紹了關(guān)聯(lián)規(guī)則的主要內(nèi)容，結(jié)合了網(wǎng)絡(luò)審計(jì)系統(tǒng)中事務(wù)數(shù)據(jù)庫(kù)的特征，從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è)在局域網(wǎng)絡(luò)出口上，采用串聯(lián)監(jiān)控或旁路監(jiān)控兩種形式，對(duì)所有流通的封包進(jìn)行審計(jì)挖掘。通過(guò)匹配規(guī)則庫(kù)中的特征值來(lái)完成報(bào)警、攔截、日志等一系列審計(jì)工作。當(dāng)前的網(wǎng)絡(luò)審計(jì)的最大速度瓶頸就是面對(duì)海量的審計(jì)記錄無(wú)法快速挖掘出異常行為，而且出現(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ī)則挖掘來(lái)進(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ī)律性。關(guān)聯(lián)規(guī)則挖掘的目的是找出數(shù)據(jù)庫(kù)中的隱藏的關(guān)聯(lián)關(guān)系。從海量的數(shù)據(jù)中找出我們需要的知識(shí)和規(guī)律，這些知識(shí)和規(guī)律是隱含在數(shù)據(jù)倉(cāng)庫(kù)中具有決策價(jià)值的。由于關(guān)聯(lián)規(guī)則挖掘技術(shù)在數(shù)據(jù)特征值分析方面有著先天的優(yōu)勢(shì)，所以采用關(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ī)則，而且通過(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è)重要研究?jī)?nèi)容。

設(shè)I={i1，i2……im}是一個(gè)項(xiàng)目合集，相關(guān)事務(wù)數(shù)據(jù)庫(kù)M={t1，t2 ……tn}，其中每個(gè)事務(wù)tj表示M的第j個(gè)事務(wù)，是由I中的若干項(xiàng)目構(gòu)成的集合，即tj？哿I。事務(wù)tj包含X，是指對(duì)于I的子集X，有X？哿tj。關(guān)聯(lián)規(guī)則的主要表現(xiàn)形式為“X→Y”，其中X？哿I，Y？哿I，并且X∩Y=？覫。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）

1.3 關(guān)聯(lián)規(guī)則挖掘步驟

關(guān)聯(lián)規(guī)則的挖掘有兩個(gè)步驟。

1.3.1 發(fā)現(xiàn)頻繁項(xiàng)集

通過(guò)給定的最小支持度（Smin），找到所有滿足“支持度≥Smin”的項(xiàng)目集，滿足條件的項(xiàng)集稱為頻繁項(xiàng)集。

1.3.2 生成關(guān)聯(lián)規(guī)則

通過(guò)給定的最?。–min），如果對(duì)每個(gè)頻繁項(xiàng)集進(jìn)行置信度的計(jì)算，然后對(duì)比Cmin，計(jì)算量將耗費(fèi)大量的時(shí)間，所有利用定理，頻繁項(xiàng)集的子集也一定是頻繁項(xiàng)集，就可以對(duì)每個(gè)最大頻繁項(xiàng)集進(jìn)行置信度的計(jì)算，大大減少了計(jì)算量。

對(duì)于第二個(gè)問(wèn)題實(shí)現(xiàn)相對(duì)容易，所以，所有優(yōu)化算法都是集中在第一個(gè)問(wèn)題的研究上，它是關(guān)聯(lián)規(guī)則算法的核心問(wèn)題。

2 Apriori算法的應(yīng)用與改進(jìn)

2.1 Apriori算法

Apriori算法是一種尋找頻繁項(xiàng)集的關(guān)聯(lián)規(guī)則挖掘算法，通過(guò)多次掃面數(shù)據(jù)庫(kù)來(lái)發(fā)現(xiàn)頻繁項(xiàng)集。算法第一步采用逐層迭代的方法找出所有頻繁項(xiàng)目集，要求頻繁項(xiàng)集的支持度大于等于設(shè)定的最小支持度；第二步從頻繁項(xiàng)集中構(gòu)造置信度不小于設(shè)定的最低閾值。

2.2 算法步驟

步驟如下：

（1）設(shè)定最小支持度s和最小置信度c。

（2）Apriori算法使用候選項(xiàng)集。首先產(chǎn)生出候選的項(xiàng)的集合。即候選項(xiàng)集。若候選項(xiàng)集的支持度大于或等于最小支持度，則該候選項(xiàng)集為頻繁項(xiàng)集。

（3）在Apriori算法的過(guò)程中，首先從數(shù)據(jù)庫(kù)讀入所有的事務(wù)，每個(gè)項(xiàng)都被看作候選1_項(xiàng)集，得出各項(xiàng)的支持度，再使用頻繁1_項(xiàng)集合集來(lái)產(chǎn)生候選2_項(xiàng)集集合，因?yàn)橄闰?yàn)原理保證所有非頻繁的1_項(xiàng)集的超集都是非頻繁的。

（4）再掃描數(shù)據(jù)庫(kù)，得出候選2_項(xiàng)集集合，再找出頻繁2_項(xiàng)集，并利用這些頻繁2_項(xiàng)集集合來(lái)產(chǎn)生候選3_項(xiàng)集。

（5）重復(fù)掃描數(shù)據(jù)庫(kù)，與最小支持度比較，產(chǎn)生更高層次的頻繁項(xiàng)集，再?gòu)脑摷侠锂a(chǎn)生下一級(jí)候選項(xiàng)集，直到不再產(chǎn)生新的候選項(xiàng)集為止。

2.3 基于分片的算法改進(jìn)

首先，把D中的事務(wù)劃分成n個(gè)非重疊的分片，如果D中事務(wù)的最小相對(duì)支持度閾值為min_sup，則每個(gè)分片的最小支持度計(jì)數(shù)為min_supX該分片的事務(wù)數(shù)。對(duì)于每個(gè)分片，掃描數(shù)據(jù)庫(kù)，找出所有的局部頻繁項(xiàng)集[3]。局部頻集可能是也可能不是整個(gè)數(shù)據(jù)庫(kù)D的頻集。然而，D的任何頻集必須作為局部頻集至少出現(xiàn)在一個(gè)分片中，證明如下：

證明：反證法。假設(shè)頻集在D的任何一個(gè)分片都不頻繁。令F為任意一個(gè)頻集，D為事務(wù)數(shù)據(jù)庫(kù)集合，C為D中的事務(wù)總數(shù)，A為D中包含F(xiàn)的事務(wù)總數(shù)，min_sup為最小支持度。因?yàn)镕是一個(gè)頻集，所以A=CXmin_sup。將D分成n個(gè)不重疊的分片：d1，d2，d3，…，dn，令C1，C2，C3，…，Cn為分片d1，d2，d3，…，dn各自對(duì)應(yīng)的事務(wù)數(shù)，則C=C1+C2+C3+…+Cn。令a1，a2，a3，…，an為分片d1，d2，d3，…，dn中包含F(xiàn)的事務(wù)數(shù)，則A=a1+a2+a3+…+an。因此A=a1+a2+a3+…+an=（C1+C2+C3+…+Cn）Xmin_sup。因?yàn)榍懊嬉呀?jīng)假設(shè)F在D中任意一個(gè)分片d1，d2，d3，…，dn中都不頻繁，則a1

因此，所有局部頻集都是D的候選項(xiàng)集，來(lái)自所有分片的局部頻集作為D的全局候選項(xiàng)集。然后，第二次掃描數(shù)據(jù)庫(kù)D，評(píng)估每個(gè)候選的實(shí)際支持度，以確定全局頻繁項(xiàng)集。它的優(yōu)化算法步驟為：（1）把數(shù)據(jù)庫(kù)劃分成一些模塊大小相當(dāng)?shù)膲K，記為N塊；（2）在每一塊內(nèi)產(chǎn)生一組自己的頻繁項(xiàng)目集；記為L(zhǎng)i；（3）最后合并這些項(xiàng)目集生成一個(gè)全局候選的頻繁項(xiàng)目集；（4）在數(shù)據(jù)庫(kù)內(nèi)，計(jì)算候選項(xiàng)頻繁目集的支持度，得到確定的最終頻繁項(xiàng)目集。

基于分片的Apriori算法在網(wǎng)絡(luò)審計(jì)這種類型的事務(wù)庫(kù)的挖掘中有著明顯的優(yōu)勢(shì)，審計(jì)事務(wù)庫(kù)的特點(diǎn)就是數(shù)據(jù)具有特有的類型，每個(gè)類型有著特定的特征值，利于分片挖掘，數(shù)據(jù)分布較為分散，數(shù)據(jù)之間的關(guān)聯(lián)性不高，采用基于分片的Apriori算法顯著提高了挖掘效率，提高算法的可用性。

3 結(jié)束語(yǔ)

在實(shí)際的應(yīng)用中，針對(duì)不同特點(diǎn)的TCP網(wǎng)絡(luò)，有著適合的改進(jìn)策略，這些策略不用做到面面俱到，只要具有一定的針對(duì)性就可以。網(wǎng)絡(luò)擁塞的改進(jìn)是十分靈活的，方法也很非常多，其原因正是因?yàn)椴煌W(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)特點(diǎn)不同，從而選擇合適的改進(jìn)策略是關(guān)鍵。

【參考文獻(xiàn)】

[1]Jiawei Han，Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].2版.范明，孟小鋒，譯.北京：機(jī)械工業(yè)出版社，2010.

[2]王麗珍，周麗華，陳紅梅，等.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘原理及應(yīng)用[M].北京：科學(xué)出版社，2005.

[3]王榮福，余麗娜，等.基于劃分技術(shù)對(duì)Apriori算法的改進(jìn)[J].科技創(chuàng)新導(dǎo)報(bào)，2008（12）.

[責(zé)任編輯：湯靜]