基于最长公共子序列距离的主旨模式挖掘算法  

Motif Pattern Mining Algorithm Based on LCSS Distance

作　　者：冯林[1] 于孝航[1] 孙焘[1] 沈骁[1] 潘晓雯[1] 

机构地区：[1]大连理工大学大学生创新院,大连116024

出　　处：《计算机工程》2008年第14期47-48,51,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(50575031)

摘　　要：针对现有主旨模式挖掘算法易受噪声干扰的问题,提出一种基于最长公共子序列距离的挖掘算法。在搜索过程中,该算法采用基于子序列距离判别的策略进行了有效的剪枝,对于非等长的候选模式,使用最小描述长度原则求其相关权重,据此选择出现频率最高、最能体现原时间序列特征的主旨模式。实验结果表明,与朴素式搜索相比,该算法的速度至少提升60%。According to the problem that existing algorithms are apt to be interfered by noise, a motif mining algorithm based on the Longest Common Subsequence（LCSS） distance is introduced. The algorithm is pruned efficiently by using the heuristic strategy based on the distance between subsequences during the search. Minimum Description Length（MDL） principle is used to calculate the weights of the unequal-length candidate sequences based on the motif patterns selected. Experiment shows the speed of the algorithm prompts at least 60% compared with that of naive algorithm.

关 键 词：主旨模式 噪声干扰 聚类分析 最小描述长度原则 

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