时间约束序列模式的有效生成候选项的方法

摘  要： 针对序列模式的几个经典的算法的缺点，提出了一种基于时间约束序列模式的快速产生候选项的方法（TFEGC）。此算法不但避免了频繁的扫描数据库，还考虑了时间限制因素，避免了无用的候选序列的产生，提高了算法运行的时间效率。
关键词： 序列模式挖掘；时间约束；候选项;快速产生
       序列模式挖掘在很多领域都具有十分重要的意义，比如它可以根据分析顾客购买行为来决定商品的摆放位置，从而制定商场的营销策划。所以，近年来出现了很多序列模式挖掘的改进算法，目前提出算法中，有两类比较典型：GSP[1]算法和采用分治策略来进行模式增长的PrefixSpan[2]算法。但是这两种算法都存在一定的缺点。参考文献[3]中提出的快速有效的产生候选项的FEGC算法，不需要多次扫描数据库，且不需要在前一次迭代的基础上来产生候选项，也不需对非频繁项进行剪枝或修剪，能够达到快速产生候选项的效果。但是，FEGC算法是针对数据库总体的序列来产生候选项的，有些并不是有效的和用户感兴趣的序列，这在实际应用中就耗费了大量的时间和空间，如分析顾客的购买行为，就不需要将其一月份购买的产品和十二月份购买的产品放在一起进行研究比较。所以本文在FEGC算法的基础上将时间限制因素加了进去，可称之为TFEGC算法，本算法继承了FEGC算法的优点，而且避免了不必要的、无用的一些候选项的产生，提高了算法的运行效率，且在序列结合的过程中，只需检查uid、fid(t)以及s(t)的值，便可知道与哪些项进行结合，无须再进行检验。
1 相关算法介绍
     GSP算法，即广义序列模式算法，使用序列模式的向下封闭性，并采用多次扫描的候选产生-测试方法，它是由Srikant和Agrawal于1996年提出的。它的主要思想是利用序列模式的种子集，即前次扫描得来的序列模式来产生潜在的频繁序列，即候选序列，每个候选序列都会比产生它的种子序列模式多包含一个项。直到