1、基于改进基于改进 MOENMOEN 算法的时序数据主旨模算法的时序数据主旨模式挖掘式挖掘 王丹丹 摘要：主旨模式挖掘常用于发现时间序列中具有代表性的相似子序列，其中MOEN 算法（Efficient Enumeration of Motifs，MOEN）基于枚举的思想来发现指定长度范围内的主旨模式（motifs），采用候选相似子序列的方法降低了计算所需资源。本研究对距离矩阵的生成策略加以改进，进一步降低计算成本，并通过实验验证其有效性。关键词：时间序列;motifs;MOEN 算法;枚举 中图分类号：TP311 文献标识码：A 文章编号：1007-9416（2020）02-0096-02 0
2、引言 主旨模式挖掘作常用于发现时间序列中具有代表性的相似子序列。Patel 等首次提出主旨模式（motifs）1，并提出了 K-motif 算法，該算法无法发现长度不等的 motif。Tang 等人在 K-motif 的基础上提出一种通过综合发现的 motif来生成原型模式的方法2，来发现长度不等的 motif。Muenn 等先提出了精确主旨模式挖掘算法3，后又提出了 MOEN 算法4（Efficient Enumeration of Motifs，MOEN），算法采用候选相似子序列的方法解决了传统枚举法计算量大的问题，本文针对此算法的不足加以改进，并验证其有效性。1 相关定义 1.1 定义
3、1：时间序列与子序列 时间序列 T 是一条长度为 n 的实数序列，可表示为 T=t1，t2，t3，tn。子序可表示为 Si，m=ti，ti+1，ti+m-1，其中 mn，1in-m+1。1.2 定义 2：平凡匹配 给定序列 T 与实数 R，已知 Sp，m 与 Sq，m，其中 mq 时，不存在 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），ij 与距离矩阵 list
4、;第二步统计非平凡匹配数，找出长度 m 下的 1-motif;第三步将距离矩阵由小到大排序，候选距离矩阵 listm 为其前 n 项;第四步计算长度为 m+1 时的距离上界LB，公式为 LB2=（+z2）-1d2，式中 z 为长度为 m 的子序列标准化后的最大值，d 为候选矩阵中距离最大值;第 5 步，基于 listm 计算新的距离，若小于 LB 则重复步骤 26，若大于 LB 则返回步骤 1。2.2 改进 MOEN 算法 MOEN 算法存在如下问题，首先该算法只挖掘出了 1-motif，而实际应用中需要K-motifs;其次距离矩阵比较冗余。针对第一个问题，将原算法中的第 2 步更改为挖掘
5、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=2m，为正数。3 实验结果与分析 表 1 和表 2 为部分实验结果，当子序列长度为 5 时，改进算法的距离矩阵大小仅为原始算法产
6、生的距离矩阵的 3.1%;当子序列长度为 11 时，这个值为 2.7%。图 1 与图 2 分别为原始算法与改进算法产生的候选序列，图中每条折线代表一个序列，可以看出改进 MOEN 算法在降低距离矩阵大小的同时，提升了算法的精度，具有实际的意义与价值。参考文献 1 Patel P，Keogh E J，Lin J，et al.Mining Motifs in Massive Time Series DatabasesJ.Proc.of IEEE Intl Conf.on Data Mining Maebashi Japan，2002：370-377.2 Tang H，Liao S S.Discov
7、ering original motifs with different lengths from time seriesJ.Knowledge-Based Systems，2008，21（7）：666-671.3 Mueen A，Keogh E J，Zhu Q，et al.Exact Discovery of Time Series MotifsC/SDM.2009：473-484.4 Mueen A.Enumeration of Time Series Motifs of All LengthsC/2013 IEEE 13th International Conference on Dat
8、a 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，Moe
9、n）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