張繼周+李婷

【摘 要】此文介紹了關(guān)聯(lián)規(guī)則的主要內(nèi)容，結(jié)合了網(wǎng)絡(luò)審計系統(tǒng)中事務(wù)數(shù)據(jù)庫的特征，從Apriori算法的基本概念出發(fā)，根據(jù)網(wǎng)絡(luò)審計的特點，介紹了一種基于分片的改進(jìn)的Apriori算法的，并給出證明。最后在改進(jìn)的策略選擇上給出結(jié)論。

【關(guān)鍵詞】網(wǎng)絡(luò)審計；關(guān)聯(lián)規(guī)則；Apriori算法

網(wǎng)絡(luò)安全審計是網(wǎng)絡(luò)安全中重要的一環(huán)。審計系統(tǒng)一般架設(shè)在局域網(wǎng)絡(luò)出口上，采用串聯(lián)監(jiān)控或旁路監(jiān)控兩種形式，對所有流通的封包進(jìn)行審計挖掘。通過匹配規(guī)則庫中的特征值來完成報警、攔截、日志等一系列審計工作。當(dāng)前的網(wǎng)絡(luò)審計的最大速度瓶頸就是面對海量的審計記錄無法快速挖掘出異常行為，而且出現(xiàn)大量誤報，影響管理者的判斷，嚴(yán)重影響了網(wǎng)絡(luò)審計系統(tǒng)的性能。

網(wǎng)絡(luò)審計中的行為主要表現(xiàn)形式為大量的含有不同特征值的數(shù)據(jù)，這些數(shù)據(jù)都有同樣的格式，即TCP報文或UDP報文，因此使用數(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)是指兩個或兩個以上項集的值之間的某中規(guī)律性。關(guān)聯(lián)規(guī)則挖掘的目的是找出數(shù)據(jù)庫中的隱藏的關(guān)聯(lián)關(guān)系。從海量的數(shù)據(jù)中找出我們需要的知識和規(guī)律，這些知識和規(guī)律是隱含在數(shù)據(jù)倉庫中具有決策價值的。由于關(guān)聯(lián)規(guī)則挖掘技術(shù)在數(shù)據(jù)特征值分析方面有著先天的優(yōu)勢，所以采用關(guān)聯(lián)規(guī)則挖掘技術(shù)進(jìn)行網(wǎng)絡(luò)審計的數(shù)據(jù)挖掘是目前最好的選擇。運用關(guān)聯(lián)規(guī)則挖掘用戶的行為模式不但能發(fā)現(xiàn)相關(guān)屬性值之間的關(guān)聯(lián)規(guī)則，而且通過合并和泛化，可以形成新的有價值的特征。

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ù)挖掘中的一個重要研究內(nèi)容。

設(shè)I={i1，i2……im}是一個項目合集，相關(guān)事務(wù)數(shù)據(jù)庫M={t1，t2 ……tn}，其中每個事務(wù)tj表示M的第j個事務(wù)，是由I中的若干項目構(gòu)成的集合，即tj？哿I。事務(wù)tj包含X，是指對于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ī)則的前項，Y稱為關(guān)聯(lián)規(guī)則的后項。

1.2 描述關(guān)聯(lián)規(guī)則屬性的兩個參數(shù)

1.2.1 支持度（Support）

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

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

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

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

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

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

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

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

2.1 Apriori算法

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

2.2 算法步驟

步驟如下：

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

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

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

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

（5）重復(fù)掃描數(shù)據(jù)庫，與最小支持度比較，產(chǎn)生更高層次的頻繁項集，再從該集合里產(chǎn)生下一級候選項集，直到不再產(chǎn)生新的候選項集為止。

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

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

證明：反證法。假設(shè)頻集在D的任何一個分片都不頻繁。令F為任意一個頻集，D為事務(wù)數(shù)據(jù)庫集合，C為D中的事務(wù)總數(shù)，A為D中包含F(xiàn)的事務(wù)總數(shù)，min_sup為最小支持度。因為F是一個頻集，所以A=CXmin_sup。將D分成n個不重疊的分片：d1，d2，d3，…，dn，令C1，C2，C3，…，Cn為分片d1，d2，d3，…，dn各自對應(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。因為前面已經(jīng)假設(shè)F在D中任意一個分片d1，d2，d3，…，dn中都不頻繁，則a1

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

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

3 結(jié)束語

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

【參考文獻(xiàn)】

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

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

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

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