基本介紹
- 中文名：關聯規則模板
- 外文名：Association rule template
- 分類：工學
效益度的高效關聯規則挖掘算法,存在的問題及已有的相關問題,效益度與規則模板的關係及其轉換,大規模網路安全態勢分析中的報警關聯挖掘,報警關聯規則結果篩選,MFP-template算法,實驗結果與分析,
效益度的高效關聯規則挖掘算法
關聯規則挖掘算法中常用的支持度和可信度是對關聯規則在統計意義上的有效性度量，在挖掘結果的有用度上缺乏指導作用，它們不能作為有用性的指標。從數據挖掘的最終目的出發定義了基於最終用戶實際目標 的效益度指標，並對最小效益度篩選性質進行了論證，提出了一種快速有效的關聯規則挖掘算法。討論了從關聯規則的興趣模板和限制模板轉換到效益度的方法。實驗結果表明，效益度指標具有支持度與可信度不可替代的作用；該算法的最小效益度剪下技術是有效的，不僅可以較大幅度地提高算法速度，而且可以作為規則模板的統一實現算法以及提供更精確的控制。
存在的問題及已有的相關問題
已有的研究大多數是基於支持度和可信度框架的完善和改進。在實際套用中，人們發現依靠支持度和可信度框架選出的規則不理想，發現的某條關聯規則即使可信度和支持度都很高，仍沒有實際意義甚至是誤導性的，滿足最小支持度和最小可信度條件的規則並不都是人們感興趣的。注意到這2個統計指標的缺陷後，不斷有研究人員從不同的角度提出選擇感興趣的或剪除不感興趣的規則的辦法。興趣度的概念和規則模板的概念是其中最有代表性的2類改進。思路是定義稱為興趣度的度量值，把一條規則的興趣度定義為基於統計獨立性假設的真正的強度與期望的強度之比。Sri-kant等人給出了感興趣規則的定義。Klemettin-en等人提出了關聯規則的模板概念，用戶可用包含模板來確定哪些規則是令人感興趣的，而用限制模板來定義哪些規則不感興趣。對大多數的數據挖掘模型或算法的使用者來說，提高企業的盈利或效益才是真正的有用標準，投入產出比是企業決策者最終關心的。因此，應該從數據挖掘用戶的最終目標的角度，考慮解決可信度和支持度在有用度上的不足。
效益度與規則模板的關係及其轉換
關聯規則模板的概念與人們通常的認知方法相近並且直觀，是一種可以讓用戶較清楚地表達自己感興趣和不感興趣的關聯規則的一種好方法；而直接表達效益度中涉及的概念相對複雜。定性的方法從規則的外形來選擇有用的規則，通過定量的手段從用戶的使用目標來衡量規則的有用度。雖然有些差異，但從作用和目標來看兩者是相同的。
實際上，從關聯規則模板轉換到效益度的方法相當簡單。可以把結果中感興趣的屬性項的Pik設為1，不感興趣的設為0；把條件中感興趣的屬性項的Cik設為1，不感興趣的設為某一大數，而完全不感興趣的設為∞(實際中可取一個比較大的正數)。另外，可以把感興趣的程度分為不同的級別，從而可以區分感興趣的不同程度，實現對興趣模板的改進。
大規模網路安全態勢分析中的報警關聯挖掘
在對傳統的關聯規則和序列規則相關概念和算法的討論基礎之上，過渡到報警日誌挖掘的具體問題上來。在挖掘報警關聯規則過程中，由於報警日誌數目龐大，當最小置信度設定較小時，傳統的關聯規則挖掘算法效率低下，而且不可避免的生成大量無用的關聯規則。鑒於問題，引出了幾種篩選報警關聯規則結果的幾種方法，詳細討論了通過制定報警關聯規則模板的方法來減少無用規則的生成；通過引入興趣度評價標準改進支持度——置信度框架，重新評價關聯規則的價值；並結合報警關聯規則模板和興趣度，提出了MFP-template算法。實驗證明，MFP-template算法不僅可以縮短挖掘時間，降低耗費的系統資源，而且能減少大量無用的關聯規則，生成用戶更感興趣的知識。
報警關聯規則結果篩選
在完成頻繁項集的挖掘後，根據頻繁項集的每一個非空子集生成相應的關聯規則，其中無疑參雜了大量用戶不感興趣的規則，如果頻繁項集數目龐大，產生的無用的關聯規則數目將更為巨大。因此需要對挖掘結果進行篩選。在關聯規則中挑選出用戶感興趣的規則並不是一件容易的事情，刪除無用規則的同時很有可能刪掉很有價值的規則。刪減無用、冗餘的關聯規則，可以從以下幾個方面入手：
(1)用主屬性參照剪枝。將主屬性作為剪枝的條件。在報警記錄中的各種屬性存在權重關係，主屬性在描述報警數據方面起到決定性的作用，將此種屬性看作一個記錄的本質屬性，其它屬性作為非本質屬性用來描述輔助信息。報警記錄通常由時間、源主機地址、目的主機地址、源連線埠、目的連線埠、報警名稱等屬性欄位組成，這些都描述了報警的基本屬性即主屬性，一個項集必須包含主屬性的值。通過剪枝操作，可以除掉不包含主屬性的頻繁項集，從而刪除了有這種頻繁項集生成的關聯規則。
(2)使用用戶定製的規則模版。用戶感興趣的關聯規則只限於有限的幾種類型，若能夠由用戶定製相應的規則模板，將其運用到頻繁項集的挖掘過程中，不僅能夠刪除大量不符合規則模板的規則，還能提高頻繁項集的挖掘效率。
(3)改進關聯規則的評價體系。在挖掘時，僅滿足最小支持度和最小置信度的閾值產生的規則不一定都是有用的，最小支持度和最小置信度的評價體系並不能完全揭示關聯規則的價值，所以需要引入其它評價關聯規則的方法，比如興趣度等。
(4)規則合併。關聯分析提取的關聯規則很多，其中有些規則只有一些細小的差別，但其反映的本質入侵行為是一致的，這就需要將類似的模式合併，合併的原則是：多條規則的左右兩邊有部分相同，或者他們的左邊和右邊都能分別被合併。
MFP-template算法
在報警日誌的關聯規則挖掘過程中，最突出的問題就是算法的效率問題和最小支持度的選擇。如果選擇效率低下的MApriori算法，最小支持度不能設定過小，而且能夠支持的報警日誌的規模極其有限。當最小支持度設定過高時，挖掘出來的是顯而易見的規則，而報警日誌庫中新穎的，有價值的規則都是隱含在出現頻度有限的報警中，設定過高的最小支持度很容易漏掉這些規則。所以關聯規則挖掘過程中，要求最小支持度設定儘量低一些，這就對挖掘算法的性能提出了更高的要求，而且當最小支持度設定較低時，大量無用規則的泛濫嚴重影響了關聯規則挖掘的可用性；關聯規則模板可以限制關聯規則的生成類型，只生成用戶感興趣的規則，減少了無用規則的生成；在此基礎上，用興趣度來評價規則價值的高低，進一步指導用戶發現報警日誌中有用的知識。MFP-template算法就是在上述情況下提出的。MFP-template算法利用了MFP-growth算法中FP樹這種壓縮的數據存儲結構，採用以下分治策略：
(1)將提供頻繁項集的報警日誌庫壓縮到一棵頻繁模式樹FP-tree，保留項集的頻度計數和維度屬性；
(2)然後將這種壓縮後的資料庫分成一組條件資料庫，根據已找到的頻繁模式將原始大資料庫分割成若干數據子集，由局部頻繁模式組合得到更長的頻繁模式；在頻繁模式增長的過程中，利用關聯規則模板約束模式的增長，只生成模板需要的模式，並計算其支持度，這樣不僅刪去了大量無用的頻繁項集，而且加快了算法的收斂速度，實現了更高的性能。
安全事件報警日誌是一個多屬性的記錄集，至少包括以下幾個欄位：時間、報警名稱、目的 IP、目的連線埠、源 IP、源連線埠等。例如：
03/07-23:50:02·146207 ， RSERVICES rsh root ， 202·77·162·213 ， 514 ，172·16·115·20，1023，TCP。
報警關聯規則就是在這樣的報警日誌庫中進行。同基本的關聯規則挖掘一樣，報警日誌的關聯規則挖掘也由兩個步驟組成：
(1)通過用戶給定的最小支持度(min_supp)，尋找所有的頻繁項目集。
(2)在每個頻繁項目集中，尋找相應的關聯規則。第一步，採用MFP-template算法完成頻繁項集的挖掘，第二步，在每個頻繁項集中，按照關聯規則模板，尋找興趣度大於1的關聯規則，支持度和置信度作為評價關聯規則的輔助指標。
實驗結果與分析
實驗由以下幾個部分組成：
(1)首先實現MFP-template算法，設定最小支持度和最小興趣度，對實際環境中的IDS報警日誌按關聯規則模板約束完成頻繁項集挖掘，生成關聯規則，並對結果進行分析。
(2)設定一定的最小支持度，對不同規模的報警日誌庫，分別運用MApriori算法、MFP-growth算法和MFP-template算法進行頻繁項集的挖掘，比較它們的運行時間。
(3)設定一定的最小支持度，對報警日誌庫，運用MFP-growth算法和MFP-template算法進行頻繁項集的挖掘，比較它們的運行時間，占用記憶體峰值的大小和頻繁項集的數量。
(4)MFP-template算法在最小支持度最低的情況下對報警日誌規模的可擴展性實驗。
