D01:10.13374j.isml00103x.206.04.21 第28卷第4期 北京科技大学学报 Vol.28 Na 4 2006年4月 Journal of University of Science and Technology Beijing Apr.2006 基于小波和动态时间弯曲的时间序列相似匹配 曲文龙张德政杨炳儒 北京科技大学信息工程学院，北京100083 摘要提出了一种基于小波和动态时间弯曲(DTW距离的时间序列索引和相似匹配方法.该 方法采用小波变换进行数据降维，利用R一re建立多维索引结构.给出了查询序列的DTW距 离边界和其在小波空间的查询超矩形的计算方法.从而将原始空间的基于DTW距离的相似匹配 转换为小波空间基于欧氏距离的相似匹配.证明了此匹配方法不会产生漏报，给出了基于DTW 距离的范围查询算法和近邻查询算法.实验结果表明该方法具有较高匹配精度和其较低的计算代 价. 关键词时间序列：相似匹配：动态时间弯曲：小波变换 分类号TP311.13 时间序列分析与挖掘广泛应用于包括金融、 出了范围查询和近邻查询算法，最后通过对比试 商业、气象、医学、电力、水文、工业等众多领域，具 验验证了该方法的优越性. 有重要的研究价值。相似模式匹配是时间序列分 1动态时间弯曲距离 类、聚类、规则获取和预测等挖掘方法的基础，建 立索引是实现时间序列相似匹配的有效方法. 11动态时间弯曲概念 典型的相似性测度多采用欧几里德距离或其 设有两个时间序列Q=(q1,；q,9n) 改进，但欧氏距离测度存在局限性，对数据在时间 和C=(c1,,G,,cm),长度分别为n和m(如 轴上的形变缺乏辨识能力和对噪声的鲁棒性.动 图1)，为利用DTW将两个时间序列对准，首先定 态时间弯曲(Dy namic Time Warping,DTW)川可 义DTW对准矩阵M. 以获得很高的识别、匹配精度.由于DTW距离 不满足三角不等式，在低维特征空间中无法保证 (a) 检索的完整性，因此基于DTW的索引和相似性 搜索有待研究.Yi给出了一个基于FASTMAP 映射的DTW索引方法？，但只是近似索引，无法 保证检索完整性.Pak采用线性分段表示建立 DTW索引3，但无法保证无漏报且查询精度较 (c) 低.Km采用序列的四个特征建立索引，保证 图1(a)时间序列O和C:(b)DTW对准方式：(cDTW对 无漏报，但未能有效的利用多维索引结构缩减搜 准矩阵和最佳弯曲路径 索空间，误报率很高.Keogh等给出了局部DTW Fig.I (a)Time serise O and C;(b)DTW aligned:(c)DTW 的包围边界，并采用分段近似表示匀，保证无漏 aligned matrix and optimum wraping path 报并使搜索空间得到一定程度缩减.由于小波变 定义1n行m列矩阵M,矩阵中的元素 换可以有效约简特征空间、具有多尺度特性，因此 (i,j)为两时间序列数据中对准点9：和G之间的 本文采用小波方法进行时间序列的DTW距离索 引和相似匹配，给出了DTW的小波变换边界，进 距离d(q,c(d(q,G)=(q-c92),定义M为 时间序列Q和C的DTW对准矩阵. 一步缩减搜索空间，并证明了该方法无漏报且给 定义2对于两个时间序列的DTW对准异 收稿日期：2005-0221修回日期：200504-24 矩阵定义矩阵中一组连续的矩阵元素的集合W 基金项目：北京市自然科学基金资助项目(No.4022008):国家科 ={w1,wk,;wK,(wk=d(9,G),称满 技攻关项目(No.2004BA6164一11) 作者简介：曲文龙(1970一），男.博士研究生 足如以下条件的W为时间序列Q和C的弯曲路基于小波和动态时间弯曲的时间序列相似匹配 曲文龙 张德政 杨炳儒 北京科技大学信息工程学院, 北京 100083 摘 要 提出了一种基于小波和动态时间弯曲( DTW) 距离的时间序列索引和相似匹配方法.该 方法采用小波变换进行数据降维, 利用 R ＊-tree 建立多维索引结构.给出了查询序列的 DTW 距 离边界和其在小波空间的查询超矩形的计算方法, 从而将原始空间的基于 DTW 距离的相似匹配 转换为小波空间基于欧氏距离的相似匹配.证明了此匹配方法不会产生漏报, 给出了基于 DTW 距离的范围查询算法和近邻查询算法.实验结果表明该方法具有较高匹配精度和其较低的计算代 价. 关键词 时间序列;相似匹配;动态时间弯曲;小波变换 分类号 TP311.13 收稿日期:2005 02 21 修回日期:2005 04 24 基金项目:北京市自然科学基金资助项目( No .4022008) ;国家科 技攻关项目( No .2004BA616A-11) 作者简介:曲文龙( 1970—) , 男, 博士研究生 时间序列分析与挖掘广泛应用于包括金融、 商业 、气象 、医学 、电力、水文、工业等众多领域, 具 有重要的研究价值.相似模式匹配是时间序列分 类、聚类 、规则获取和预测等挖掘方法的基础, 建 立索引是实现时间序列相似匹配的有效方法 . 典型的相似性测度多采用欧几里德距离或其 改进, 但欧氏距离测度存在局限性, 对数据在时间 轴上的形变缺乏辨识能力和对噪声的鲁棒性.动 态时间弯曲( Dy namic Time Warping , DTW) [ 1] 可 以获得很高的识别 、匹配精度 .由于 DTW 距离 不满足三角不等式, 在低维特征空间中无法保证 检索的完整性, 因此基于 DTW 的索引和相似性 搜索有待研究.Yi 给出了一个基于 FASTMAP 映射的 DTW 索引方法[ 2] , 但只是近似索引, 无法 保证检索完整性.Park 采用线性分段表示建立 DTW 索引 [ 3] , 但无法保证无漏报且查询精度较 低.Kim 采用序列的四个特征建立索引[ 4] , 保证 无漏报, 但未能有效的利用多维索引结构缩减搜 索空间, 误报率很高 .Keog h 等给出了局部 DTW 的包围边界, 并采用分段近似表示 [ 5] , 保证无漏 报并使搜索空间得到一定程度缩减.由于小波变 换可以有效约简特征空间 、具有多尺度特性, 因此 本文采用小波方法进行时间序列的 DTW 距离索 引和相似匹配, 给出了 DTW 的小波变换边界, 进 一步缩减搜索空间, 并证明了该方法无漏报, 且给 出了范围查询和近邻查询算法, 最后通过对比试 验验证了该方法的优越性 . 1 动态时间弯曲距离 1.1 动态时间弯曲概念 设有两个时间序列 Q =( q1, …, qi , …, qn ) 和 C =( c1, …, cj , …, cm ), 长度分别为 n 和m(如 图 1), 为利用 DTW 将两个时间序列对准, 首先定 义 DTW 对准矩阵 M . 图1 ( a) 时间序列 Q 和C ;( b) DTW 对准方式;( c) DTW对 准矩阵和最佳弯曲路径 Fig.1 ( a) Time serise Q and C ;( b) DTW aligned;( c) DTW aligned matrix and optimum wraping path 定义 1 n 行 m 列矩阵 M, 矩阵中的元素 ( i, j) 为两时间序列数据中对准点 qi 和cj 之间的 距离d ( qi , cj)( d ( qi , cj) =( qi -cj) 2 ), 定义 M 为 时间序列Q 和C 的 DTW 对准矩阵 . 定义 2 对于两个时间序列的 DTW 对准异 矩阵, 定义矩阵中一组连续的矩阵元素的集合 W ={w 1, …, wk , …, wK}, ( wk =d ( qi , cj )), 称满 足如以下条件的 W 为时间序列Q 和C 的弯曲路 第 28 卷 第 4 期 2006 年 4 月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol .28 No.4 Apr.2006 DOI :10.13374/j .issn1001 -053x.2006.04.021