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

Frequent Sequence Mining Techniques based on SAT and BDD

作　　者：戴瑀君 徐周波 DAI Yujun;XU Zhoubo(School of Computer and Information Security,Guilin University of Electronic Technology,Guilin,Guangxi,541004,China)

机构地区：[1]桂林电子科技大学计算机与信息安全学院,广西桂林541004

出　　处：《广西科学院学报》2018年第2期137-142,150,共7页Journal of Guangxi Academy of Sciences

基　　金：广西自然科学基金项目(2017GXNSFAA198172)资助

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]