王 斌 黄晓芳 袁 平

(西南科技大学计算机学院 四川绵阳 621000)

基于PrefixSpan序列模式挖掘的改进算法

王 斌 黄晓芳 袁 平

(西南科技大学计算机学院 四川绵阳 621000)

针对PrefixSpan算法在构建投影数据库时时间开销过多和随着支持度增加效率下降的问题，提出了一种基于PrefixSpan算法的改进算法AP(AprioriAll-PrefixSpan)，该算法可以减少构建投影数据库的时间开销和降低支持度增加对算法效率的影响。改进思想是在第一次划分生成投影数据库时，按投影数据库中项集的个数从小到大排序，在第二次划分的时候 ，从已挖掘序列模式中直接生成所需序列模式，从而减少数据库的构建。实验结果显示AP 算法效率高于PrefixSpan算法。

PrefixSpan 序列模式 投影数据库 生成序列 二次划分

序列模式挖掘是挖掘频繁出现的有序事件或子序列[1]。由于序列模式挖掘对先验知识的依赖较少，可以发现未知的规律，所以得到了广泛的应用。比如：网络安全中的异常行为发现[2]、生物工程[3]、DNA序列分析[4]、网络访问模式分析[5]、用户社交行为分析[6]等。

序列模式挖掘最先由Agrawal和Srikant在文献[7]中提出，论文主要介绍了3种基于Apriori算法框架的AprioriAll，AprioriSome和DynamicSome算法，随后提出了一种基于泛化GSP[8]算法。文献[9]提出了一种基于垂直数据格式的SPADE 算法。以上算法都会产生大量的候选集。而文献[10]提出的FreeSpan算法，是基于序列模式的增长，不产生候选集。文献[11]的PrefixsSpan算法是对FreeSpan算法的改进，减少了投影数据库和子序列连接次数，数据库收敛更快，算法效率比之前的算法效率都高。

PrefixSpan算法[11]是根据前缀生成对应的投影数据库，然后对投影数据库进行扫描，避免了对整个数据库进行扫描，从而减少了扫描时间。……