網絡審計系統中Apriori算法的應用與研究

張繼周+李婷

【摘 要】此文介紹了關聯規則的主要內容，結合了網絡審計系統中事務數據庫的特征，從Apriori算法的基本概念出發，根據網絡審計的特點，介紹了一種基于分片的改進的Apriori算法的，并給出證明。最后在改進的策略選擇上給出結論。

【關鍵詞】網絡審計；關聯規則；Apriori算法

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

網絡審計中的行為主要表現形式為大量的含有不同特征值的數據，這些數據都有同樣的格式，即TCP報文或UDP報文，因此使用數據挖掘技術中的關聯規則挖掘來進行發現特征數據就是很有效的方法。關聯規則挖掘（Data Mining）首先由Rakesh Apwal等人提出。關聯是指兩個或兩個以上項集的值之間的某中規律性。關聯規則挖掘的目的是找出數據庫中的隱藏的關聯關系。從海量的數據中找出我們需要的知識和規律，這些知識和規律是隱含在數據倉庫中具有決策價值的。由于關聯規則挖掘技術在數據特征值分析方面有著先天的優勢，所以采用關聯規則挖掘技術進行網絡審計的數據挖掘是目前最好的選擇。運用關聯規則挖掘用戶的行為模式不但能發現相關屬性值之間的關聯規則，而且通過合并和泛化，可以形成新的有價值的特征。

1 關聯規則

1.1 關聯規則定義

關聯規則是Agrawl等人于1993年提出的，關聯規則發展至今已經成為數據挖掘中的一個重要研究內容。

設I={i1，i2……im}是一個項目合集，相關事務數據庫M={t1，t2 ……tn}，其中每個事務tj表示M的第j個事務，是由I中的若干項目構成的集合，即tj？哿I。事務tj包含X，是指對于I的子集X，有X？哿tj。關聯規則的主要表現形式為“X→Y”，其中X？哿I，Y？哿I，并且X∩Y=？覫。X稱為關聯規則的前項，Y稱為關聯規則的后項。

1.2 描述關聯規則屬性的兩個參數

1.2.1 支持度（Support）

1.3 關聯規則挖掘步驟

關聯規則的挖掘有兩個步驟。

1.3.1 發現頻繁項集

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

1.3.2 生成關聯規則

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

對于第二個問題實現相對容易，所以，所有優化算法都是集中在第一個問題的研究上，它是關聯規則算法的核心問題。

2 Apriori算法的應用與改進

2.1 Apriori算法

Apriori算法是一種尋找頻繁項集的關聯規則挖掘算法，通過多次掃面數據庫來發現頻繁項集。算法第一步采用逐層迭代的方法找出所有頻繁項目集，要求頻繁項集的支持度大于等于設定的最小支持度；第二步從頻繁項集中構造置信度不小于設定的最低閾值。

2.2 算法步驟

步驟如下：

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

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

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

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

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

2.3 基于分片的算法改進

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

證明：反證法。假設頻集在D的任何一個分片都不頻繁。令F為任意一個頻集，D為事務數據庫集合，C為D中的事務總數，A為D中包含F的事務總數，min_sup為最小支持度。因為F是一個頻集，所以A=CXmin_sup。將D分成n個不重疊的分片：d1，d2，d3，…，dn，令C1，C2，C3，…，Cn為分片d1，d2，d3，…，dn各自對應的事務數，則C=C1+C2+C3+…+Cn。令a1，a2，a3，…，an為分片d1，d2，d3，…，dn中包含F的事務數，則A=a1+a2+a3+…+an。因此A=a1+a2+a3+…+an=（C1+C2+C3+…+Cn）Xmin_sup。因為前面已經假設F在D中任意一個分片d1，d2，d3，…，dn中都不頻繁，則a1

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

基于分片的Apriori算法在網絡審計這種類型的事務庫的挖掘中有著明顯的優勢，審計事務庫的特點就是數據具有特有的類型，每個類型有著特定的特征值，利于分片挖掘，數據分布較為分散，數據之間的關聯性不高，采用基于分片的Apriori算法顯著提高了挖掘效率，提高算法的可用性。

3 結束語

在實際的應用中，針對不同特點的TCP網絡，有著適合的改進策略，這些策略不用做到面面俱到，只要具有一定的針對性就可以。網絡擁塞的改進是十分靈活的，方法也很非常多，其原因正是因為不同網絡中傳輸的數據特點不同，從而選擇合適的改進策略是關鍵。

【參考文獻】

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

[2]王麗珍，周麗華，陳紅梅，等.數據倉庫與數據挖掘原理及應用[M].北京：科學出版社，2005.

[3]王榮福，余麗娜，等.基于劃分技術對Apriori算法的改進[J].科技創新導報，2008（12）.

[責任編輯：湯靜]