基于SAT和BDD的频繁序列挖掘技术

Frequent Sequence Mining Techniques based on SAT and BDD

关键词:  布尔可满足性  有序二叉决策图  频繁序列挖掘

Key words:  boolean satisfiability  ordered binary decision diagram  frequent sequence pattern mining

摘要:

[目的] 研究模式挖掘领域中的频繁序列挖掘技术,由于序列模式挖掘存在指数级的搜索空间,且传统的SAT求解算法无法高效求解大规模数据集的缺点,因此研究符号表示和操作技术,用来避免冗余计算。[方法] 提出基于SAT的频繁序列挖掘的符号OBDD算法,基于深度优先算法的思想,首先将频繁序列挖掘问题构建为SAT模型,其次对变量进行排序并将约束子句分类后分别描述为OBDD,利用OBDD的"与"操作得到满足SAT的所有频繁序列模式。[结果] 实例结果表明,该方法准确可行。[结论] 该方法能有效缩减搜索空间,提高求解效率。

Abstract:

[Objective] To research the frequent sequence mining techniques in the field of pattern mining. The sequential pattern mining problem has an exponential search space. However, the traditional SAT solver algorithm cannot efficiently solve large-scale data sets. For this shortcoming, the symbolic representation and operation techniques are studied to avoid redundant computing. [Methods] Based on the depth-first algorithm, the symbolic OBDD algorithm based on SAT for mining frequent sequence was proposed. Firstly, the frequent sequence mining problem was constructed as a SAT model. Second, the variables were sorted and the constraint clauses were classified and described as OBDD respectively. Then the "AND" operation of OBDD was used to find all the frequent patterns that satisfied the SAT. [Results] The example results showed that this method was accurate and feasible. [Conclusion] This approach could reduce the search space effectively and improve the efficiency.