免预设间隔约束的对比序列模式高效挖掘  

Efficient Mining of Distinguishing Sequential Patterns Without a Predefined Gap Constraint

作　　者：王慧锋[1] 段磊[1,2,3] 左劼[1] 王文韬[1] 李钟麒 唐常杰[1] 

机构地区：[1]四川大学计算机学院,成都610065 [2]四川大学华西公共卫生学院,成都610041 [3]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《计算机学报》2016年第10期1979-1991,共13页Chinese Journal of Computers

基　　金：国家自然科学基金(61103042);教育部高等学校博士学科点专项科研基金(20100181120029);软件工程国家重点实验室开放研究基金(SKLSE2012-09-32);中国博士后科学基金(2014M552371)资助

摘　　要：对比序列模式在识别不同类别序列样本集合的特征上有着重要的作用.已有对比序列模式挖掘算法需要用户预设间隔约束.在不具备充分先验知识情况下,用户不易准确地预设恰当的间隔约束,进而导致不能发现有用的模式.对此,文中设计了带紧凑间隔约束的最小对比序列模式挖掘算法,实现免预设间隔约束,并对候选模式自动计算最适合的间隔约束.此外,设计了3种剪枝策略来提高算法的执行效率.通过蛋白质序列、DNA序列、行为序列数据集验证了提出的算法的有效性和高效率.Distinguishing sequential patterns with gap constraints are very useful for identifying important features for discriminating one class of sequences from sequences of other classes. A gap constraint should be predefined by users using the proposed mining methods for distinguishing sequential patterns. It is difficult for users to set suitable gap constraints without enough priori knowledge. As a result, useful patterns may be missed. To deal with this problem, this paper presents an algorithm for mining distinguishing sequential patterns with compact gap constraints. The proposed algorithm runs well without a predefined gap constraint. Instead, it computes the most suitable gap constraint for each candidate pattern. In addition, three pruning rules are designed to improve the efficiency of the algorithm. Experiments on protein sequences, DNA sequences, and activity sequences confirmed the effectiveness and efficiency of the proposed algorithm.

关 键 词：对比序列模式 间隔约束 序列数据挖掘 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]