基于包含索引的频繁闭序列模式挖掘的新算法

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (10): 2485-2488.

基于包含索引的频繁闭序列模式挖掘的新算法

李晋宏^1,2, 杨炳儒¹, 宋威², 侯伟¹

1. 北京科技大学信息工程学院, 北京, 100083;
2. 北方工业大学信息工程学院, 北京, 100144

收稿日期:2008-05-26 修回日期:2008-10-20 出版日期:2009-10-20 发布日期:2010-01-03
作者简介:李晋宏(1965- ),男,教授,博士,主要研究方向为数据挖掘,模糊专家系统.E-mail:ljh@ncut.edu.cn
基金资助:
国家自然科学基金(60675030);北京市属市管高等学校人才强教计划资助课题

New mining algorithm for frequent closed sequential pattern based on subsume index

LI Jin-hong^1,2, YANG Bing-ru¹, SONG Wei², HOU Wei¹

1. School of Information Engineering, Univ. of Science and Technology Beijing, Beijing 100083, China;
2. Coll. of Information Engineering, North China Univ. of Technology, Beijing 100144, China

Received:2008-05-26 Revised:2008-10-20 Online:2009-10-20 Published:2010-01-03

摘要/Abstract

摘要： 频繁闭序列模式惟一确定全体频繁序列模式,且规模小得多.传统的闭序列模式挖掘算法对每个频繁项目都进行扩展,往往会产生大量的非闭合序列.为解决这一问题,提出了一种新的基于包含索引的频繁闭序列模式挖掘算法,其主要思想是只对闭项集进行扩展,大大减少了非闭合序列的产生.首先,论证了闭序列模式只能由闭项集组成;其次,说明了如何利用包含索引来快速发现闭项集;最后,给出了一种深度优先的挖掘频繁闭序列模式的新算法.实验结果表明,该算法具有较高的效率.

Abstract: The set of frequent closed sequential pattern determines exactly the complete set of all frequent sequential patterns and is usually much smaller than the latter.Traditional closed sequential pattern mining algorithms extend a frequent sequence with every frequent single item,which leads to the generation of a lot of non-closed sequence.To solve these problems,a new mining algorithm for frequent closed sequential pattern based on subsume index is proposed.The main idea of the proposed algorithm is to extend a frequent sequence with closed itemsets only.Thus,the generation of non-closed sequences is avoided greatly.Firstly,it is proved that a closed sequential pattern is only composed of closed itemsets.Then,it is explained that the closed itemsets can be discovered efficiently by using a subsume index.Finally,a depth-first algorithm for mining frequent closed sequential pattern is presented.The experimental results show that the proposed algorithm is efficient.

中图分类号:

TP18

李晋宏, 杨炳儒, 宋威, 侯伟. 基于包含索引的频繁闭序列模式挖掘的新算法[J]. Journal of Systems Engineering and Electronics, 2009, 31(10): 2485-2488.

LI Jin-hong, YANG Bing-ru, SONG Wei, HOU Wei. New mining algorithm for frequent closed sequential pattern based on subsume index[J]. Journal of Systems Engineering and Electronics, 2009, 31(10): 2485-2488.

参考文献

[1] Dong G,Pei J.Sequence data mining[M].New York:Springer,2007.
[2] Han J,Cheng H,Xin D,et al.Frequent pattern mining:current status and future directions[J].Data Mining and Knowledge Discovery,2007,15(1):55-86.
[3] Agrawal R,Srikant R.Mining sequential patterns[C]//Proc.of the 11th International Conference on Data Engineering,1995:3-14.
[4] Pei J,Han J,Mortazavi-Asl B,et al.Mining sequential patterns by pattern-growth:the PrefixSpan approach[J].IEEE Trans.on Knowledge and Data Engineering,2004,16(11):1424-1440.
[5] Zaki M J.SPADE:an efficient algorithm for mining frequent se-quences[J].Machine Learning,2001,42(1/2):31-60.
[6] Yan X,Han J,Afshar R.CloSpan:mining closed sequential patterns in large databases[C]//Proc.of the 3rd SIAM International Conference on Data Mining,2003:166-177.
[7] Wang J,Han J,Li C.Frequent closed sequence mining without candidate maintenance[J].IEEE Trans.on Knowledge and Data Engineering,2007,19(8):1042-1056.
[8] 叶飞跃.基于自适应哈希链的分布式频繁模式挖掘算法[J].系统工程与电子技术,2005,27(3):560-564.(Ye Feiyue.Distributed algorithm for mining frequent pattern based on adaptive Hash chain structure[J].Systems Engineering and Electronics,2005,27(3):560-564.)
[9] 陈慧萍,王建东,叶飞跃,等.基于FP-tree和支持度数组的最大频繁项集挖掘算法[J].系统工程与电子技术,2005,27(9):1631-1635.(Chen Huiping,Wang Jiandong,Ye Feiyue,et al.Efficient mining maximal frequent itemsets by using FP-tree and support arruy[J].Systmes Engineering and Electronics,2005,27(9):1631-1635.)
[10] Yang G.Computational aspects of mining maximal frequent patterns[J].Theoretical Computer Science,2006,362(1-3):63-85.
[11] Arimura H.Efficient algorithms for mining frequent and closed patterns from semi-structured data[C]//Proc.of the 12th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining,2008:2-13.
[12] Song W,Yang B R,Xu Z Y.Index-MaxMiner:a new maximal frequent itemset mining algorithm[J].International Journal on Artificial Intelligence Tools,2008,17(2):303-320.
[13] 宋威,杨炳儒,徐章艳,等.一种改进的频繁闭项集挖掘算法[J].计算机研究与发展,2008,45(2):278-286.
[14] Jonassen I,Collins J F,Higgins D G.Finding flexible patterns in unaligned protein sequences[J].Protein Science,1995,4(8):1587-1595.

[1]	王玉佳, 方伟, 徐涛, 余应福, 邓博元. 基于遗传模糊树的海空对抗无人机智能决策模型[J]. 系统工程与电子技术, 2022, 44(12): 3756-3765.
[2]	张寒, 黄炎焱, 耿泽, 张振. 营区突发事件应急保障方案仿真推演评估方法[J]. 系统工程与电子技术, 2022, 44(11): 3433-3442.
[3]	汪瀚洋, 陈亮, 徐海, 白景波. 基于MOEA/D-ARMS的无人机在线航迹规划[J]. 系统工程与电子技术, 2022, 44(11): 3505-3514.
[4]	张俊, 张新禹, 姜卫东, 刘永祥, 黎湘. 基于广义近似消息传递的快速DOA估计方法[J]. 系统工程与电子技术, 2022, 44(10): 2995-3002.
[5]	曾斌, 张鸿强, 李厚朴. 针对无人潜航器的反潜策略研究[J]. 系统工程与电子技术, 2022, 44(10): 3174-3181.
[6]	万齐天, 卢宝刚, 赵雅心, 温求遒. 基于深度强化学习的驾驶仪参数快速整定方法[J]. 系统工程与电子技术, 2022, 44(10): 3190-3199.
[7]	刘戎翔, 吴琳, 谢智歌, 刘虹麟. 基于生成对抗网络的防空体系态势辅助分析[J]. 系统工程与电子技术, 2022, 44(8): 2522-2529.
[8]	辛立强, 张超, 赵灵芝, 刘建平. 面向复杂关联测控需求的冲突规避调度算法[J]. 系统工程与电子技术, 2022, 44(5): 1581-1588.
[9]	何立, 沈亮, 李辉, 王壮, 唐文泉. 强化学习中的策略重用: 研究进展[J]. 系统工程与电子技术, 2022, 44(3): 884-899.
[10]	王姝婷, 刘晓冰, 周军华, 白朝阳, 翟翔. 基于本体的复杂产品维修工程案例知识表示及重用方法[J]. 系统工程与电子技术, 2022, 44(2): 557-568.
[11]	马玉凤, 向南, 豆亚杰, 姜江, 杨克巍, 谭跃进. 军事系统工程中的知识图谱应用及研究[J]. 系统工程与电子技术, 2022, 44(1): 146-153.
[12]	张国令, 吴崇明, 李睿, 来杰, 向前. 基于一维堆叠池化融合卷积自编码器的HRRP目标识别方法[J]. 系统工程与电子技术, 2021, 43(12): 3533-3541.
[13]	冯建鑫, 王雅雷, 王强, 胥彪. 基于改进粒子群算法的快速反射镜自抗扰控制[J]. 系统工程与电子技术, 2021, 43(12): 3675-3682.
[14]	赵辰豪, 吴德伟, 韩昆, 朱浩男, 代传金. 基于多尺度网格细胞的路径整合模型[J]. 系统工程与电子技术, 2021, 43(10): 2961-2967.
[15]	程恺, 陈刚, 余晓晗, 刘满, 邵天浩. 知识牵引与数据驱动的兵棋AI设计及关键技术[J]. 系统工程与电子技术, 2021, 43(10): 2911-2917.