带通配符和One-Off条件的序列模式挖掘  

Mining Sequential Patterns with Wildcards and the One-Off Condition

作　　者：吴信东[1,2] 谢飞[3] 黄咏明[1] 胡学钢[1] 高隽[1] 

机构地区：[1]合肥工业大学计算机与信息学院 [2]Department of Computer Science,University of Vermont,Burlington,VT 05405,USA [3]合肥师范学院计算机科学与技术系

出　　处：《软件学报》2013年第8期1804-1815,共12页Journal of Software

基　　金：国家自然科学基金(61229301;60828005;61273292);美国国家科学基金(CCF-0905337;CCF-0514819);国家高技术研究发展计划(863)(2012AA011005);国家重点基础研究发展计划(973)(2013CB329604)

摘　　要：很多应用领域产生大量的序列数据.如何从这些序列数据中挖掘具有重要价值的模式,已成为序列模式挖掘研究的主要任务.研究这样一个问题:给定序列S、支持度阈值和间隔约束,从序列S中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,并且要求模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束.设计了一种有效的带有通配符的模式挖掘算法One-Off Mining,模式在序列中的出现满足One-Off条件,即模式的任意两次出现都不共享序列中同一位置的字符.在生物DNA序列上的实验结果表明,One-Off Mining比相关的序列模式挖掘算法具有更好的时间性能和完备性.There is a huge wealth of sequence data available in real-world applications.The task of sequential pattern mining serves to mine important patterns from the sequence data.Given a sequence S,a certain threshold,and gap constraints,this paper aims to discover frequent patterns whose supports in S are no less than the given threshold value.There are flexible wildcards in pattern P,and the number of the wildcards between any two successive elements of P fulfills the user-specified gap constraints.The study designs an efficient mining algorithm： One-Off Mining,whose mining process satisfies the One-Off condition under which each character in the given sequence can be used at most once in all occurrences of a pattern.Experiments on DNA sequences show that this method performs better in time and completeness than the related sequential pattern mining algorithms.

关 键 词：数据挖掘 序列模式挖掘 频繁模式 通配符 One-Off条件 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]