基于改进MOEN算法的时序数据主旨模式挖掘
来源:用户上传
作者:
摘要：主旨模式挖掘常用于发现时间序列中具有代表性的相似子序列，其中MOEN算法（Efficient Enumeration of Motifs，MOEN）基于枚举的思想来发现指定长度范围内的主旨模式（motifs），采用候选相似子序列的方法降低了计算所需资源。本研究对距离矩阵的生成策略加以改进，进一步降低计算成本，并通过实验验证其有效性。
关键词：时间序列;motifs;MOEN算法;枚举
中图分类号：TP311 文献标识码：A 文章编号：1007-9416（2020）02-0096-02
0 引言
主旨模式挖掘作常用于发现时间序列中具有代表性的相似子序列。Patel等首次提出主旨模式（motifs）[1]，并提出了K-motif算法，該算法无法发现长度不等的motif。Tang等人在K-motif的基础上提出一种通过综合发现的motif来生成原型模式的方法[2]，来发现长度不等的motif。Muenn等先提出了精确主旨模式挖掘算法[3]，后又提出了MOEN算法[4]（Efficient Enumeration of Motifs，MOEN），算法采用候选相似子序列的方法解决了传统枚举法计算量大的问题，本文针对此算法的不足加以改进，并验证其有效性。
1 相关定义
1.1 定义1：时间序列与子序列
时间序列T是一条长度为n的实数序列，可表示为T=t1，t2，t3，…，tn。子序可表示为Si，m=ti，ti+1，…，ti+m-1，其中m<n，1≤i≤n-m+1。
1.2 定义2：平凡匹配
给定序列T与实数R，已知Sp，m与Sq，m，其中m<n，若满足p=q或当p<r<q或p>r>q时，不存在Sr，m，使得D（Sp，m，Sr，m）>R，则称Sp，m为Sq，m的平凡匹配序列。
2 改进MOEN算法
2.1 MOEN算法
MOEN算法通过边界策略来减少枚举次数，降低运算复杂度。算法第一步计算长度为m的子序列间的距离dmi，j=D（Si，m，Sj，m），i≠j与距离矩阵list;第二步统计非平凡匹配数，找出长度m下的1-motif;第三步将距离矩阵由小到大排序，候选距离矩阵listm为其前n项;第四步计算长度为m+1时的距离上界LB，公式为LB2=（+z2）-1d2，式中z为长度为m的子序列标准化后的最大值，d 为候选矩阵中距离最大值;第5步，基于listm计算新的距离，若小于LB则重复步骤2～6，若大于LB则返回步骤1。
2.2 改进MOEN算法
MOEN算法存在如下问题，首先该算法只挖掘出了1-motif，而实际应用中需要K-motifs;其次距离矩阵比较冗余。针对第一个问题，将原算法中的第2步更改为挖掘K-motifs即可。针对第二个问题，改进算法通过避免产生“无用项”来减小距离矩阵。已知， D（Si，m+1，Sj，m+1）≥D（Si，m，Sj，m），若Sj，m+1与Si，m+1的不匹配，则D（Si，m+1，Sj，m+1）>R，D（Si，m，Sj，m）>R，R为阈值。由此推得Sj，m一定不是Si，m的匹配序列，故其为无用项。因此，只要在生成listm时设置合适的距离阈值M即可筛除无用项，降低计算复杂度。为了适应不同长度下子序列间距离的变化M=2λm，λ为正数。
3 实验结果与分析
表1和表2为部分实验结果，当子序列长度为5时，改进算法的距离矩阵大小仅为原始算法产生的距离矩阵的3.1%;当子序列长度为11时，这个值为2.7%。
图1与图2 分别为原始算法与改进算法产生的候选序列，图中每条折线代表一个序列，可以看出改进MOEN算法在降低距离矩阵大小的同时，提升了算法的精度，具有实际的意义与价值。
参考文献
[1] Patel P，Keogh E J，Lin J，et al.Mining Motifs in Massive Time Series Databases[J].Proc.of IEEE Intl Conf.on Data Mining Maebashi Japan，2002：370-377.
[2] Tang H，Liao S S.Discovering original motifs with different lengths from time series[J].Knowledge-Based Systems，2008，21（7）：666-671.
[3] Mueen A，Keogh E J，Zhu Q，et al.Exact Discovery of Time Series Motifs[C]//SDM.2009：473-484.
[4] Mueen A.Enumeration of Time Series Motifs of All Lengths[C]//2013 IEEE 13th International Conference on Data Mining.IEEE Computer Society，2013.
Find Time Series Motifs Based on Improved MOEN Algorithm
WANG Dan-dan
（Chongqing JiaoTong University， Chongqing 400000）
Abstract：Motifs mining is often used to find representative similar subsequences in time series. MOEN algorithm （efficiency enumeration of motifs， Moen） is based on the idea of enumeration to find the motifs within the specified length range. The method of candidate similar subsequences reduces the computing resources. In this study， the generation strategy of distance matrix is improved to further reduce the calculation cost， and its effectiveness is verified by experiments.
Key words：time series; motifs; MOEN algorithm; enumeration
转载注明来源:https://www.xzbu.com/8/view-15192586.htm
