基于影响度的统计显著序列模式挖掘算法

Statistically significant sequential patterns mining algorithm under influence degree

针对传统序列模式挖掘算法中支持度不能如实体现序列模式兴趣度以及未对报告的序列模式进行质量评估的问题,提出一个基于影响度的统计显著序列模式挖掘算法ISSPM。首先,递归地挖掘出所有满足兴趣度约束的序列模式;然后,使用项集置换方法构建这些序列模式的置换检验零分布;最后,通过该零分布计算出被评估的序列模式的统计度量值,并从上述序列模式中找到所有统计显著序列模式。真实序列记录集合上的实验结果表明,ISSPM算法相较于PSPM、SPDL和PSDSP算法挖掘到的序列模式数量更少但兴趣度更强;仿真序列记录集合上的实验结果表明,ISSPM算法报告的结果中假阳性序列模式数量平均占比为3.39%,且该算法的嵌入模式的发现率均不低于66.7%,明显优于上述3个对比算法。可见,ISSPM算法报告的统计显著序列模式能够体现序列记录集合中更有价值的信息,同时根据这些信息做出的进一步分析和决策也更加可靠。

Aiming at the problems that the degree of support is not a good indicator for the interestingness of sequential patterns and the quality of reported sequential patterns is not evaluated in traditional sequential patterns mining algorithms,a statistically significant sequential patterns mining algorithm under influence degree,calling ISSPM(Influence-based Significant Sequential Patterns Mining),was proposed. Firstly,all sequential patterns meeting the interestingness constraint were mined recursively. Then,the itemset permuting method was introduced to construct permutation test null distribution for these sequential patterns. Finally,the statistical measures of the evaluated sequential patterns were calculated from this distribution,and all statistically significant sequential patterns were found from the above sequential patterns. In the experiments with the PSPM(Prefix-projected Sequential Patterns Mining),SPDL(Sequential Patterns Discovering under Leverage)and PSDSP(Permutation Strategies for Discovering Sequential Patterns)algorithms on the real-world sequential record datasets,ISSPM algorithm reports fewer but more interesting sequential patterns. Experimental results on the synthetic sequential record datasets show that the average proportion of the false positive sequential patterns reported by the ISSPM algorithm is 3. 39%,and the discovery rate of embedded patterns of this algorithm is not less than 66. 7%,which are significantly better than those of the above three algorithms to compare. It can be seen that the statistically significant sequential patterns reported by ISSPM algorithm can reflect more valuable information in sequential record datasets,and the decisions made based on the information are more reliable.