[發明專利]一種無冗余情節規則的抽取方法

無效

• 申請號: 201310244601.2
• 申請日: 2013-06-19
• 公開（公告）號: CN103324712A
• 公開（公告）日: 2013-09-25
• 發明（設計）人: 尤濤;杜承烈;徐偉;趙湑
• 申請（專利權）人: 西北工業大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 王鮮凱

技術領域

本發明屬于數據挖掘技術中的數據流上情節規則抽取方法，涉及一種無冗余情節規則的抽取方法，提高情節規則的生成質量和生成效率。

背景技術

歷史流數據中蘊含著大量的信息，研究歷史流數據的潛在規律并應用這些規律找出潛在的情節規則，能夠為許多現實應用提供重要的決策支持。

例如，圖書館Web服務器上記載的涉及多個讀者對多個文檔的閱讀序列，例如，＜A,A,B,D,A,C,B,B,E,A,B,A,C,E,F＞。根據這些閱讀序列，需要找出讀者們的閱讀行為，從而有助于圖書館人員發現文獻之間的關聯并向讀者提供個性化的推薦服務。對于序列＜A,A,B,D,A,C,B,B,E,A,B,A,C,E,F＞，挖掘出的頻繁情節如表1，頻繁閉情節如表2，盡管頻繁閉情節的個數遠遠少于頻繁情節的個數，但直接由頻繁閉情節集仍能產生個數繁多的情節規則，其中存在許多冗余規則。

對于這類序列，如何從序列中找出無冗余的情節是一個很重要的問題。

目前，針對如何找出潛在的無冗余的情節規則這一問題，Li等人采用了直接由頻繁閉項集及其生成子來產生無冗余關聯規則基的算法，提出的算法DPMiner采用了深度優先的搜索策略，利用倒置的FP樹來發現頻繁閉項集及其生成子；為了拓展生成子在序列模式挖掘中的應用，Lo等人引入了序列數據庫等價類和序列模式生成子的概念，并結合序列數據庫等價類的特性，提出了序列模式生成子的挖掘算法GenMiner；采用深度優先的搜索策略和最小且非重疊發生的支持度定義，提出了算法MANEPI以發現給定事件序列上的頻繁情節。此外，朱秋生等人提出了算法Extractor，利用非生成子情節的Apriori性質，避免了冗余的情節生成子判斷；直接由頻繁閉情節及其生成子產生情節規則，提高了情節規則的生成質量和生成效率。

上述情節規則抽取算法在情節規則的生成過程中，當前最優的閉情節及其生成子也會生成冗余情節規則，盡管利用了一些剪切技術來篩選冗余的情節規則，但這種后期的修剪處理增加了算法的時間代價。

發明內容

要解決的技術問題

為了避免現有技術的不足之處，本發明提出一種無冗余情節規則的抽取方法，產生無冗余情節規則。

技術方案

一種無冗余情節規則的抽取方法，其特征在于步驟如下：

步驟1：由若干事件按發生時間先后排序的序列定義數據流上的事件序列其中t_i＜t_j(1≤i≤j≤s)，掃描事件序列ES，生成事件序列的縱向表達方式，給定最小支持度min_sup和最小可信度；

步驟2：若情節α的支持度大于等于min_sup，則α是一個頻繁情節，對于事件序列ES，找出所有的頻繁情節；所述min_sup為支持度閾值；

步驟3：對于滑動窗口中的數據，若情節α是頻繁的，且α的任何一個真超情節的支持度均不等于α的支持度，則α是一個頻繁閉情節，使用閉情節挖掘算法Apriori算法進行單遍挖掘，得到支持度大于閾值的閉情節，將結果保存于一棵全局頻繁閉情節樹中；

步驟4：對于頻繁閉情節α，對于每個的界限ul_x(α)；當|α/x|是奇數的時候，ul_x(α)為α.sup的上限，表示為ux(α)，ux(α)的最小值成為α.sup的最小上限，表示為mu(α)；當|α/x|是偶數的時候，ul_x(α)為α.sup的下限，表示為lx(α)，lx(α)的最大值稱為α.sup的最大下限，表示為ml(α)。如果α.sup＝ml(α)＝mu(α)，稱α為可導集，反之，稱α為非可導集。根據給定一個情節，如果它的一個真子情節和它的支持度一致，則該情節及其為前綴的其它任何情節都是可導情節的性質，可以快速挖掘閉情節非可導生成子；