[發明專利]用于數據庫入侵檢測領域的壓縮中間候選頻繁項集的方法

有效

• 申請號: 201410851266.7
• 申請日: 2014-12-31
• 公開（公告）號: CN104516978B
• 公開（公告）日: 2018-11-27
• 發明（設計）人: 李淼;呂迅;朱宏軍;崔維力;武新
• 申請（專利權）人: 天津南大通用數據技術股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 天津濱海科緯知識產權代理有限公司 12211
• 代理人: 楊慧玲

本發明提供一種用于數據庫入侵檢測領域的壓縮中間候選頻繁項集的方法，包括如下步驟：1)依據目標事務數目值，從事務數據庫中篩選出項目數不小于目標事務數目值的事務作為新事務數據庫；2)使用Apriori算法的連接步驟和剪枝步驟，掃描新事務數據庫，計算產生頻繁1?項集L(1)；3)找出頻繁1?項集L(1)中的項目排在前面的與目標事務數目值相同數值的幾項候選項集；4)掃描候選項集，得到目標事務數目值的頻繁項集。本發明具有的優點和積極效果是：能免去按照自然數順序，從1開始，逐個生成中間候選頻繁項集和中間頻繁項集的操作，大幅提高了數據挖掘搜索效率；達到減少數據庫掃描工作量，從而大幅提高了計算頻繁項集的速度。

技術領域

本發明屬于Apriori算法技術領域，尤其是涉及一種用于數據庫入侵檢測領域的壓縮中間候選頻繁項集的方法。

背景技術

關聯規則(Associate rule)挖掘在數據挖掘中占有極其重要的地位，是數據挖掘的主要任務之一。關聯規則的經典算法是Apriori算法。Apriori算法使用一種稱為逐層迭代方法，k-項集用于(k+1)-項集的搜索，Apriori算法性質：頻繁項集的所有非空子集都必須也是頻繁項集。

Apriori算法：根據定義，如果項集I不滿足最小支持度(min_sup)，則項集I不是頻繁的，即P(I)<(min_sup)。如果項A添加到項集I，則結果項集I即(I∪A)不可能比項集I更頻繁出現。因此，P(I∪A)也不是頻繁的，即P(I∪A)<(min_sup)。

Apriori算法主要包括兩個操作：

(1)連接步

C1＝I，I為事務數據庫所包含的項目，掃描數據庫，得到頻繁1-項目集L1，執行連接產生C2，掃描數據庫，得到L2，執行連接產生C3。如此下去，在第k遍掃描中，則是首先利用L(k－1)來生成若Ck＝Φ，則算法結束，否則掃描數據庫得到Lk。

(2)剪枝步

利用Apriori算法性質，進行對事務的刪除，提高掃描的效率。在第k遍掃描中，第一步，利用第(k－1)次掃描得到的L(k－1)來產生Ck，首先將L(k－1)中前k-1項相同的項集進行連接產生Ck，接著將連接得到的項集，若其子集L(k－1)不是頻繁項集，那么任何(k－1)-項集都不可能是頻繁項集，則刪除，即修剪；第二步，對每個事務，若Ck中某項集包含在該事務中，則該項集的支持度加1，掃描結束后，將Ck中支持度大于最小支持度的所有項集加入Lk(Ck稱為候選頻繁k項集的集合,Lk稱為k項頻繁項集；即以Ck表示k-itemsets備選項集,以Lk表示k-itemsets頻繁項集)。

上述Apriori算法對候選集的大小進行了壓縮，但是在生成Ck的過程中仍需k次掃描整個事務數據庫。因而，對于海量的數據庫，經典Apriori算法的效率會下降，并且系統的I/O開銷也很大。

后來發明了改進的Apriori算法，如下：

根據項集有序性和事務的壓縮，在候選頻繁項目集Ck的產生過程中，采用兩次剪枝，刪除其中不必要的掃描的事務；產生一個新的事務數據庫D(K+1)，在下一輪的迭代中使用。D(K+1)比DK包含了較少的事務，從而提高掃描的效率，節省系統的開銷。

(1)連接步不變

(2)事務剪枝步

事務t包含一個k-項集，則k-頻繁項集的所有子k-1項集都是k-1頻繁項集。根據定義1，在第k步掃描前，對事務Dk的每個事務t進行剪枝，得到新的事務D’。