[發明專利]基于包含與演繹分析的精確序列規則挖掘方法

在審

• 申請號: 201410598480.6
• 申請日: 2014-10-30
• 公開（公告）號: CN104408290A
• 公開（公告）日: 2015-03-11
• 發明（設計）人: 杜承烈;吳其蔓;尤濤;鐘冬
• 申請（專利權）人: 西北工業大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 王鮮凱

技術領域

本發明涉及一種精確序列規則挖掘方法，特別是涉及一種基于包含與演繹分析的精確序列規則挖掘方法。

背景技術

文獻“基于最小且非重疊發生的頻繁閉情節挖掘，計算機研究與發展,2013,50(4),852-860”公開了一種基于頻繁閉情節和生成子的無冗余序列規則挖掘方法。該方法選擇頻繁閉序列與生成子作為規則基。算法采用最小且非重疊發生的支持度定義和深度優先的搜索策略來發現頻繁閉序列及其生成子，直接由頻繁閉序列及其生成子產生序列規則。該算法的規則基——閉序列及其生成子已被證明可產生具有最小前件和最大后件的包含無冗余序列規則。但是該算法忽略了規則間的冗余關系，造成挖掘的序列規則存在冗余。同時，近年來序列規則挖掘方面開展的各類算法，雖然在數據組織、處理流程等方面各有不同，但主要分為三類，如表1所示。

產生序列規則全集的典型算法為TASA、WinMiner，該類算法以頻繁序列為規則基，通過投影的方式產生序列規則全集。

產生最小前件序列規則全集的典型算法為GenMiner，其規則基為頻繁序列與生成子。算法首先采用深度優先的搜索策略來創建存儲所有序列的前綴搜索樹PSL，然后通過遍歷PSL得到包含所有序列模式生成子的超集，據此可以得到最小前件序列規則。

產生包含無冗余序列規則集的典型算法為Extractor。

表1典型序列規則挖掘算法分類比較

類別規則基產生規則1頻繁序列序列規則全集2頻繁序列與生成子最小前件序列規則全集3頻繁閉序列與生成子包含無冗余序列規則集

從上述序列規則挖掘算法的發展不難看出，規則的產生方式經歷了頻繁序列投影、頻繁序列及其生成子投影、頻繁閉序列及其生成子投影等階段；算法的效率、精確程度、精簡粒度都在逐步提高。但卻忽略了多規則間的關聯關系在挖掘過程中的作用，造成了規則冗余。

發明內容

為了克服現有挖掘方法存在規則冗余的不足，本發明提供一種基于包含與演繹分析的精確序列規則挖掘方法。該方法首先挖掘頻繁閉情節及生成子，以保證序列規則在挖掘過程是無冗余的；然后，在構成序列規則的過程中，通過檢查頻繁閉情節集和生成子集，找到其最大重疊集元素以及其投影與被投影元素，過濾其投影與被投影元素產生的序列規則，即可達到冗余性檢查的目的；最后，根據序列規則的定義，根據過濾后的頻繁閉序列集和生成子集，生成精確序列規則。該方法在保證時刻復雜度和現有序列規則挖掘算法相當的前提下，消除序列規則間的冗余，在保證序列規則代表信息完整性的前提下，保證規則數量最少。

本發明解決其技術問題所采用的技術方案是：一種基于包含與演繹分析的精確序列規則挖掘方法，其特點是采用以下步驟：