矫春兰,刘建宾

(1.北京信息科技大学 计算机学院，北京 100101；2北京信息科技大学 软件工程研究中心，北京 100101)

0 引言

序列模式挖掘是数据挖掘的一个重要领域，它在生物基因学、氨基酸序列分析、Web日志分析、代码知识挖掘、客户购买行为分析预测等领域应用广泛。现有的序列模式挖掘算法主要分为两类，一类是以Apriori、GSP算法为代表的候选生成与测试方法；另一类是以PrefixSpan为代表的模式增长方法。前者需要不断重复扫描数据库生成候选序列并进行测试检查，并且会生成大量无用的候选序列模式影响挖掘的效率；后者经扫描一次数据库后产生频繁项，并根据频繁项生成对应的投影数据库，通过递归的方式把搜索空间划分为更小的投影数据库，这样挖掘过程中不产生候选序列，但是构造投影数据库会造成较大的开销。传统的序列挖掘算法挖掘较大数据库中的序列模式往往生成大量冗余序列。为减少挖掘结果集又不失完整性，有研究者提出了挖掘闭合序列模式与最大序列模式。常规的闭合顺序模式挖掘算法在产生大量低效和冗余模式时面临巨大挑战，尤其是在使用低支持阈值或模式丰富的数据库时。现有的闭合序列挖掘算法包括CloSpan[1]、BIDE[2]等，是基于顺序的算法，并不涉及连续性约束，所挖掘的结果存在跳跃与间隔的序列。然而并不是所有的频繁顺序序列模式都是用户感兴趣的。在生物基因学中常常需要分析连续的基因片段，在代码知识挖掘中也需要探索连续出现的代码片段。……