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

摘要

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.%对比序列模式在识别不同类别序列样本集合的特征上有着重要的作用。已有对比序列模式挖掘算法需要用户预设间隔约束。在不具备充分先验知识情况下，用户不易准确地预设恰当的间隔约束，进而导致不能发现有用的模式。对此，文中设计了带紧凑间隔约束的最小对比序列模式挖掘算法，实现免预设间隔约束，并对候选模式自动计算最适合的间隔约束。此外，设计了3种剪枝策略来提高算法的执行效率。通过蛋白质序列、DNA 序列、行为序列数据集验证了提出的算法的有效性和高效率。