【图文】算法分析第四章_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
算法分析第四章
上传于|0|0|暂无简介
大小：809.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢&&&&2014, Vol. 25 Issue (3): 560-575
李正欣, 张凤鸣, 李克武, 张晓丰. 一种支持DTW距离的多元时间序列索引结构[J].软件学报,): 560-575.http://www./10.html &&
LI Zheng-Xin, ZHANG Feng-Ming, LI Ke-Wu, ZHANG Xiao-Feng. Index Structure for Multivariate Time Series under DTW Distance Metric[J]. Ruan Jian Xue Bao/ Journal of Software, ): 560-575.http://www./10.html &&
一种支持DTW距离的多元时间序列索引结构
李正欣, 张凤鸣, 李克武, 张晓丰&&&&
空军工程大学 装备管理与安全工程学院, 陕西 西安 710051
作者简介：张凤鸣(1963－),男,教授,博士生导师,主
要研究领域为信息系统工程与智能决策.
E-mail: zhangfm_李克武(1968－),男,副教授,主要研究领域
为智能信息处理与决策.
E-mail: 张晓丰(1978－),男,博士,副教授,主要研
究领域为智能信息处理与决策.
E-mail: .cn
通讯作者：李正欣(1982－),男,河南信阳人,博士,讲
师,主要研究领域为信息系统工程与智能
决策,数据挖掘.
E-mail: lizhengxin_
摘要：现有的索引结构难以有效地支持DTW距离度量下的多元时间序列相似性搜索.首先给出一种将不等长多元时间序列转换为等长一元时间序列的方法，并证明这种转换满足下界距离引理；以此为基础，提出一种多元时间序列的DTW下界距离，并对其性质进行分析；然后，针对给出的下界距离，提出一种支持DTW距离度量的多元时间序列索引结构，对多元时间序列数据库进行有效组织；再给出多元时间序列相似模式搜索算法及流程，并证明该搜索方法具有非漏报性；最后，通过实验对所提方法的有效性进行验证.
多元时间序列&&&&
动态时间弯曲&&&&
下界距离&&&&
索引结构&&&&
相似性搜索&&&&
Index Structure for Multivariate Time Series under DTW Distance Metric
LI Zheng-Xin, ZHANG Feng-Ming, LI Ke-Wu, ZHANG Xiao-Feng&&&&
Equipment Management and Safety Engineering College, Air Force Engineering University, Xi'an 710051, China
Corresponding author:LI Zheng-Xin, E-mail: lizhengxin_
Abstract: Existing index structures for multivariate time series can't support similarity search under DTW distance efficiently. Firstly, a transformation method, which converts unequal-length multivariate time series into equal-length univariate time series, is proposed and a mathematical proof that the transformation satisfies lower bounding distance lemma is provided. Secondly, DTW lower bounding distance is proposed, and its character is analyzed. Thirdly, based on DTW lower bounding distance proposed above, an index structure for multivariate time series is proposed, allowing database of multivariate time series be organized. Further, similarity search algorithm and process for multivariate time series are discussed, and related mathematical proofs that false dismissals can be avoided are given. Finally, validity of proposed method is verified by experiments.
Key words:
multivariate time series&&&&
dynamic time warping&&&&
lower bounding distance&&&&
index structure&&&&
similarity search&&&&
现实世界中存在大量多元时间序列(multivariate time series,简称MTS)类型的数据[],如航天飞船等重要仪器的运行状态数据、互联网中关键服务器的通信流量数据、应用于多种行业的人体运动捕捉数据、患者的脑电波等.一些多媒体数据经过转换后也可以形成多元时间序列.时间序列相似模式挖掘就是从时间序列数据库中查找和发现用户感兴趣的模式,旨在研究隐含在时间序列之中的更深层次的知识,从中获取蕴含的系统演化规律[].相似模式挖掘不仅是时间序列数据挖掘的主要研究内容之一,还是实现其他挖掘任务的基础[].
模式匹配与相似性搜索是时间序列相似模式挖掘的两个核心问题.模式匹配是度量时间序列相似程度的方法,在时间序列分析处理中具有基础性地位[].目前,最常见的MTS模式匹配方法是Minkowski距离、动态时间弯曲(dynamic time warping,简称DTW)距离.Minkowski距离计算简单、容易理解,但它要求两条时间序列的长度必须相等,且对时间轴伸缩和弯曲问题无能为力.DTW距离定义了序列之间的最佳对齐匹配关系,支持不同长度时间序列的相似性度量,支持时间轴的伸缩和弯曲[].由于DTW距离比Minkowski距离有更好的鲁棒性,因此被广泛用于时间序列的相似性度量[].在时间序列相似性搜索中,如果用查询序列逐一与数据库中其他序列进行相似性比较,搜索效率很低,在实际应用中往往是不可行的.因此,研究高效的搜索方法是非常必要的.目前,针对Minkowski距离度量的索引方法较为成熟[],而针对DTW距离度量的索引方法并不多见.主要原因是DTW距离不满足距离三角不等式,且计算复杂度较高[].
已有的支持DTW距离度量的索引结构基本都遵循如下思路:寻找一种计算更简单的距离度量来粗略地估计DTW距离,称为DTW下界距离,通过它过滤掉大部分不满足相似性要求的序列,从而提高查询效率.为了保证查询的准确和高效,DTW下界距离应满足3个条件[]:
· 正确性:经下界距离过滤得到的候选集中必须包含所有满足条件的序列,即不允许出现漏报;
· 有效性:下界距离的计算复杂度应尽量低;
· 紧致性:下界距离的度量结果应尽量逼近DTW距离,这样才能使得候选集不至过大,从而减少后处理的计算量.
Yi[],Kim[],Keogh[]和Zhu[]分别提出了支持DTW距离度量的一元时间列搜索方法,他们分别给出了各自的DTW下界距离,然后提出了支持相应下界距离的索引构建方法,并且证明搜索方法的非漏报性.Yi计算两条一元时间序列的DTW下界距离时,选择一条序列作为基准序列,以另一条序列中大于基准序列最大值的点集以及小于基准序列最小值的点集作为特征,以此为基础构造DTW下界距离,记为LB_Yi.Kim提取一元时间序列的起始点、结束点、最大值点和最小值点这4个特征,以此为基础构造DTW下界距离,记为LB_Kim.Keogh提取查询序列的上、下边界序列作为查询特征,进而构造出一种DTW下界距离,记为LB_Keogh;使用PAA方法把数据库中的一元时间序列转换为空间向量点,用R-Tree对向量点进行组织;利用下界距离LB_Keogh在空间索引结构上执行查询,索引查询的结果构成候选集;最后,使用DTW距离计算查询序列与候选集中每个一元时间序列的DTW距离,去除不符合相似性条件的序列,得到结果集,并通过大量实验验证了LB_Keogh的紧致性优于LB_Yi和LB_Kim.Zhu在文献[]中对下界距离方法进行了数学证明,并提出了一种DTW下界距离,记为LB_Zhu,这可以视为LB_Keogh方法的改进,进一步提高了下界距离在索引查询中的紧致性.此外,文献[]对时间序列进行分段累积近似,用网格最小边界矩形近似表示查询序列,进而提出一种DTW下界距离,记为LB_GMBR.
文献[,,,,]提出的搜索方法不会遗漏正确结果,下界距离LB_Keogh及其改进形式LB_Zhu的紧致性较高,相应搜索方法的整体性能较优.但以上几种方法存在一定的局限性:它们仅针对一元时间序列,而不适用于多元时间序列;Keogh和Zhu提出的方法还要求查询序列和搜索序列的长度必须相等.
本文的目标是找到一种支持DTW距离度量的多元时间序列索引结构,从而实现多元时间序列的高效搜索.首先给出一种多元时间序列的DTW下界距离;在下界距离的基础上,提出一种支持DTW距离度量的多元时间序列索引结构,进而给出相应的相似性搜索算法;最后,通过实验对所提方法进行有效性分析.
1 预备知识
1.1DTW距离及性质分析
定义1(时间序列). 一系列记录值xt(j)称为时间序列(time series,简称TS),其中,t(t=1,2,…,n)表示第t个时间点,j(j=1,2,…,m)表示第j个变量,xt(j)表示第j个变量在第t个时间点上的记录值.当m&1时,xt(j)为多元时间序列;当m=1时,xt(j)为一元时间序列(univariate time series,简称UTS).时间序列可以用mxn矩阵表示,m表示变量数,n表示时间点数量,矩阵行代表变量维,列代表时间维.
定义2(DTW距离)[]. 设时间序列X=áx1,x2,…,xn&,Y=áy1,y2,…,ym&,则X,Y的DTW距离Ddtw(X,Y)定义见公式(1),其中,Dbase(xi,yj)表示向量点xi和yj之间的基距离,可以根据情况选择不同的距离度量.不失一般性,本文使用Minkowski距离作为基距离.
DTW距离允许序列点自我复制后再进行对齐匹配,能够很好地支持时间轴弯曲,并且它可以对非等长时间序列进行度量,也支持时间轴伸缩,但其计算复杂度较高、且不满足距离三角不等式.DTW距离实际上就是确定序列X与Y上每个点之间的对齐匹配关系,如图 1(c)所示,这种匹配关系可能有很多种,每一种匹配关系可以用一条弯曲路径表示,如图 1(b)所示.也就是说,序列间的匹配关系与弯曲路径是一一对应的关系.
图1Fig. 1Fig. 1 Warping path and resulting alignment图 1 弯曲路径与点对匹配结果
弯曲路径必须满足3个基本条件:
(1) 边界条件:路径起始于点(x1,y1)、终止于点(xn,ym),它表示两个序列的起始点和结束点对应匹配;
(2) 连续性:路径上的任意两个相邻点和满足条件0≤|i1-i2|≤1,0≤|j1-j2|≤1;
(3) 单调性:若和为路径上前后两个点,则须满足i2-i1≥0,j2-j1≥0.
满足上述条件的弯曲路径有很多,每一条弯曲路径都代表一种点对匹配关系.设弯曲路径为W=(w1,w2,…, wk,…,wK),wk=(i,j)k是弯曲路径上第k个元素,它表示xi与yj建立的匹配关系,路径长度满足max(n,m)≤K≤n+m-1.
点对匹配关系中,点对基距离之和的最小值即为DTW距离,对应的弯曲路径为最佳路径.DTW距离表示为
求解最佳路径需要构造一个m行n列的累积距离矩阵Mmxn,矩阵中的每个元素gi,j定义为
gi,j=Dbase(xi,yj)+min{gi,j-1,gi-1,j,gi-1,j-1} (3)
gi,j为序列X[1:j]与序列Y[1:i]的DTW距离,因此,Ddtw(X,Y)=gm,n,gm,n可以用动态规划法求解[].
1.2 查询策略与查询完备性
顺序扫描是用查询序列逐一与MTS数据库中的序列进行模式匹配,找出满足相似条件的序列.然而,数据库包含的序列数量很多,且DTW距离的计算复杂度较高,因此,顺序扫描方法效率很低.目前常用的查询策略一般遵循两步查询步骤(如图 2所示):
图2Fig. 2Fig. 2 Process of two-step search图 2 两步搜索流程
(1) 先使用下界距离进行索引查询:将时间序列映射到低维特征空间,转换为低维空间中的几何对象,采用空间索引结构组织这些低维空间对象;然后,使用查询序列的特征在索引结构上进行查询,通过索引的过滤和剪枝策略提高查询效率,索引查询结果即为候选集;
(2) 再使用DTW距离对候选集进行后处理:依次计算查询序列与候选集中每个序列的DTW距离,去除不符合相似性条件的序列,得到结果集.
查询完备性是衡量查询策略优劣的一个重要标准,它包括两层含义:完全性和准确性.设S是数据库TB中满足相似性匹配要求的序列集合,R是实际查询到的序列集合.若R是S的子集,则查询不是完全的,S-R表示遗漏的正确结果,称发生漏报(false dismissal);相反地,若S是R的子集,则查找是不准确的,R-S表示引入的错误结果,称发生误报(false alarm).
通常,查询准确性较容易得到保证,只需结果集中的序列都满足相似模式匹配要求;而查询完全性却并不是所有的查询策略都能达到的,有时会为了查询的效率而损失一定的查询完全性.Faloutsos等人在文献[]中证明了一个重要引理,能够保证时间序列在变换到特征空间后的相似模式搜索不发生漏报.
定理1(下界距离引理). 设时间序列Q和C通过特征提取函数F映射到特征空间,为了保证特征空间的搜索不产生漏报,必须满足Dfeature(F(Q),F(C))≤Dtrue(Q,C),其中,Dfeature和Dtrue分别表示特征空间和原始空间的距离度量函数.
1.3R-Tree索引结构
R-Tree最初由Guttman于1984年提出,随后人们在此基础上针对不同的空间操作需求提出了各种改进方案,如R+-Tree,R-Tree等,经过20多年的发展,逐渐形成了一个枝繁叶茂的空间索引R-Tree家族[].R-Tree是一种处理多维数据的空间索引结构,是许多空间索引方法的基础,在空间索引领域中占有重要地位[].它的结点分为两类:内部结点和叶结点.内部结点包括若干个形如(ptr,R)的项,其中,ptr是指向树中下一层结点的指针,R是包括ptr所指向结点中的所有最小界限矩形(minimum bounding rectangle,简称MBR)的最小矩形.叶结点包括若干个形如(oid,R)的项,其中,oid是指向目标对象的标识符,R是目标对象的MBR.
2 多元时间序列的DTW下界距离
本节首先给出一种将不等长MTS转换为等长UTS的方法,并证明这种转换满足下界距离引理.以此为基础,提出一种多元时间序列的DTW下界距离,并对其性质进行分析.
2.1 弯曲路径的全局约束条件
除了定义的3个条件之外,弯曲路径还需满足全局约束条件,即限定一个序列中的点只能同另一序列中位置相近的某些点进行匹配,累积距离矩阵中允许弯曲路径访问的元素集合被称为弯曲窗口.设时间序列Q,C的弯曲路径上的元素为wk=(i,j)k,弯曲路径的全局约束条件可以理解为对元素wk=(i,j)k下标的限制,即j-r≤i≤j+r,其中,r表示序列上某个点的弯曲限制.Sakoe-Chiba约束中,r为常数,弯曲窗口为沿对角线方向的带形,如图 3(a)所示;Itakura-Parallelogram约束中,r为i的函数,弯曲窗口为沿对角线方向的平行四边形,如图 3(b)所示.文中主要针对Sakoe-Chiba约束条件进行讨论.
图3Fig. 3Fig. 3 Two kinds of warping windows图 3 两种弯曲窗口
性质1. 设时间序列Q=áq1,q2,…,qm&,C=ác1,c2,…,cn&,弯曲路径在全局约束条件下的弯曲限制为r,为了保证DTW距离计算的有效性,Q,C的长度差不大于r.
证明:使用反证法.
设时间序列Q,C的长度分别为m,n,它们的长度差大于r,即m-n&r或m-n&-r.
DTW距离计算的有效性可以理解为:累积距离矩阵中,弯曲路径除了要满足自身定义的3个条件之外,还必须满足全局约束条件.
根据第1个约束条件,弯曲路径的起始点由q1,c1形成,终止点由qm,cn形成;如果点qi,cj是弯曲路径上的匹配点对,其中,1≤i≤m,1≤j≤n,则全局约束条件要求j-r≤i≤j+r.
由于qm,cn形成弯曲路径的终止点,因此满足n-r≤m≤n+r,显然与假设矛盾.
性质1表明:计算序列Q,C的DTW距离时,当增加弯曲路径的全局约束条件后,仍然支持不等长序列的匹配,但序列的长度差有一定限制.本文余下部分都是在性质1的条件下进行讨论.
2.2 不等长MTS转换为等长UTS
MTS在时间维和变量维上都具有较高的维度数,直接用索引结构对其进行组织较为困难,为了便于用索引结构对MTS进行有效组织,文中将不等长MTS转换为等长UTS.下面提出几个性质,并对其进行简单证明,作为这种变换的理论基础.
性质2. 设时间序列Q=áq1,q2,…,qm&,C=ác1,c2,…,cn&,在累积距离矩阵M中,如果存在一条弯曲路径,该路径上的点对基距离之和为a,则DTW(Q,C)≤a.
证明:在累积距离矩阵中,能够找到多条弯曲路径,其中存在一条最佳路径W=(w1,w2,…,wk,…,wK),元素
wk=(i,j)k表示qi与cj建立的匹配关系,使得路径W确定的点对基距离之和最小,记
Dbase(wk)=Dbase(qi,cj).
现存在一条弯曲路径,使得.
由DTW距离的定义,因此DTW(Q,C)≤a.
性质3. 设时间序列,如果Q&与Q、C&与C的长度分别相同,且Q&,C&上任意点对的基距离均不大于Q,C上对应点对的基距离,即 其中,1≤i≤m,1≤j≤n,则DTW(Q&,C&)≤DTW(Q,C).
证明:首先求解DTW(Q,C),该过程可理解为两个步骤:确定Q与C上的点对的最佳匹配关系,形成最佳路径W=(w1,w2,…,wk,…,wK),元素wk=(i,j)k表示qi与cj建立的匹配关系;计算所有匹配点对的基距离之和,即
然后求解DTW(Q&,C&),由于序列Q&与Q、C&与C的长度分别相同,求解DTW(Q&,C&)时,可以沿用弯曲路径W形成的点对匹配关系,并计算这种匹配关系下的点对基距离之和a.
因为,所以,即a≤DTW(Q,C).
因为在Q&,C&形成的累积距离矩阵中存在一条弯曲路径,该路径上的点对基距离之和为a,由性质2可知,
DTW(Q&,C&)≤a.
因此,DTW(Q&,C&)≤DTW(Q,C).
性质4. 变量维数为m(m&1)的时间序列Q,C,把任意对应的k(1≤k≤m)个变量相加,分别得到两组一元时间序列Q&,C&,则DTW(Q&,C&)≤DTW(Q,C).
证明:不失一般性,假设Q&,C&分别是由Q,C的前k(1≤k≤m)个变量相加得到的一元时间序列.显然,Q&与Q、C&与C的长度分别相同.
设Q,C任意时刻的记录值分别为qi=(qi1,qi2,…,qim)T,cj=(cj1,cj2,…,cjm)T,其中,1≤i≤Len(Q),1≤j≤Len(C);
Q&,C&在对应时刻的值分别为.
Q,C上任意点对的基距离为;
Q&,C&上对应点对的基距离为
因此,.根据性质3可知,DTW(Q&,C&)≤DTW(Q,C).
根据性质4,可以把MTS转换为UTS,文中把这种转换称为变量加和,并且这种转换满足下界距离引理.下面提出一种序列扩展方法,把不等长UTS转换为等长UTS.
设UTS数据库中序列的最大长度为Lmax,其中,任意两条一元时间序列记为 ,长度分别为m,n.
序列扩展可以表示为映射:F(Q&)&Q&+,F把任意长度序列映射为长度为Lmax+1的序列.
序列扩展方法可描述为:在长度为L的原始序列后面增加Lmax+1-L个常数e(取e=0).
例如,Q&+=áQ&,Q&*&,C&+=áC&,C&*&,其中,Q&*=á0,0,…,0&Lmax+1-m,C&*=á0,0,…,0&Lmax+1-n.
下面简单说明DTW(Q&+,C&+)≤DTW(Q&,C&)成立.
Q&,C&的最佳路径W如图 4(a)所示,最佳路径确定的匹配点对基距离之和即为DTW(Q&,C&).
图4Fig. 4Fig. 4 DTW distance computation of extended time series图 4 扩展时间序列的DTW距离计算
Q&+由Q&,Q&*组成,C&+由C&,C&*组成,因此,寻找Q&+,C&+之间的一种点对匹配关系可分为两个步骤:先确定Q&,C&上的点对匹配关系;再确定Q&*,C&*上的点对匹配关系.Q&,C&仍可沿用路径W,Q&*,C&*任意确定一种匹配关系,如图 4(b)所示.由于Q&*,C&*上的值都为0,所以在构造的点对匹配关系下,Q&+,C&+间匹配点对的基距离之和为DTW(Q&,C&).即在Q&+、C&+形成的累积距离矩阵中存在一条弯曲路径,该路径上的点对基距离之和为DTW(Q&,C&),由性质2可知,DTW(Q&+,C&+)≤DTW(Q&,C&).
2.3DTW下界距离
上文提出了把不等长MTS转换为等长UTS的方法,下面给出等长UTS的DTW下界距离.
设一元查询序列Q=áq1,q2,…,qn&,弯曲路径在全局约束条件下的弯曲限制为r,定义两条新序列U=áu1,u2,…, un&,L=ál1,l2,…,ln&:
ui=max(qi-r,qi+r) (4)
li=min(qi-r,qi+r) (5)
U,L分别称为Q的上、下边界序列.图 5反映了Q与上、下边界序列的位置关系,Q被包围在上、下边界序列形成的区域中,该区域称为封袋.显然,有公式(6)成立.
&i,ui≥qi≥li (6)
图5Fig. 5Fig. 5 Query series and its upper and lower bounding series图 5 查询序列与其上、下边界序列
等长一元时间序列Q,C的DTW下界距离定义为:
LB_DTW(U,L,C)可理解为:C没有落入封袋的点同封袋边界的距离之和,如图 6所示.
图6Fig. 6Fig. 6 An illustration of the lower bounding function LB_DTW图 6 下界距离LB_DTW的示意图
下面证明LB_DTW(U,L,C)≤LB_DTW(Q,C),即LB_DTW(U,L,C)满足下界距离引理.
证明:设Q,C的最佳路径W=(w1,w2,…,wk,…,wK),由DTW距离的定义得,其中,
n≤K&2n-1,则原命题可转换为
弯曲路径上的元素wk=(i,j)k,每一个i(1≤i≤n)对应一个或多个j,选出其中j值最小的元素,把相应的k标记为k&Imatch.公式(8)变为
公式(9)中,不等式左侧分为3种情况:
· 当ci&ui时,不等式左侧的第i项为|ci&ui|,不等式右侧中的对应元素为Dbase(wk)=|ci-qj|.
因为ui=max(qi-r:qi+r),i-r≤j≤i+r,所以qj≤max(qi-r:qi+r),即qj≤ui;变形后有ci-ui≤ci-qj,即|ci-ui|≤|ci-qj|,因此,|ci-ui|≤Dbase(wk);
· 当ci&li时,同理可证|ci-li|≤Dbase(wk);
· 当li≤ci≤ui时,显然有0≤|ci-qj|.
弯曲路径上基距离非负,有,因此公式(9)成立.
下面分别从正确性、有效性和紧致性这3个方面对LB_DTW进行分析:
(1) 设变量维数为m(m&1)的不等长多元时间序列Q,C,把任意对应的k(1≤k≤m)个变量相加,得到不等长一元时间序列Q&,C&,由性质4可知,DTW(Q&,C&)≤DTW(Q,C);再使用序列扩展方法,把不等长一元时间序列Q&,C&扩展为等长一元时间序列Q&+,C&+,且有DTW(Q&+,C&+)≤DTW(Q&,C&);对于等长一元时间序列Q&+,C&+,设Q&+的上、下边界序列分别为U&+,L&+,则有LB_DTW(U&+,L&+,C&+)≤DTW(Q&+,C&+),因此有LB_DTW(U&+,L&+,C&+)≤DTW(Q,C),再根据下界距离引理得知,LB_DTW(U&+,L&+,C&+)是DTW(Q,C)的下界距离,用其作为距离度量时,查询结果不会产生漏报;
(2) 从公式(7)可以看出,LB_DTW下界距离是针对等长UTS的模式匹配方法,点对匹配关系明确,在形式和计算方法上都非常类似于Minkowski距离,因此同DTW距离相比,计算复杂度明显降低;
(3) LB_DTW下界距离的紧致性不易定性分析,下文将通过实验对其进行验证.
LB_Keogh及其改进方法只适用于等长UTS,具有较大的局限性;而LB_DTW以性质1~性质4为理论支撑,实现了从一元向多元、从等长向不等长的拓展,把研究对象从等长UTS推广到不等长MTS,可视为LB_Keogh方法的拓展.
3 支持DTW距离的索引结构
针对上文给出的下界距离,本节提出一种支持DTW距离的多元时间序列索引结构,对MTS数据库进行有效组织,并给出MTS相似性搜索算法.
3.1 时间序列的分段累积近似
为了把长度从n降到N,UTS在时间维度上被分割为等长度的N段,用每一段记录值的平均值作为该段序列的基本特征,这种表示方法被称为时间序列的分段累积近似(piecewise aggregate approximation,简称PAA).
令N表示时间序列的分段数目,则序列C可用N维空间中的点表示为,其中,的第i个元素可以用公式(11)表示:
设一元时间序列Q=áq1,q2,…,qn&,C=ác1,c2,…,cn&,通过公式(11)把其转化为,定义序列的距离为
并且有公式(13)成立,证明过程见文献[]:
3.2 索引结构的建立
对于长度为n的一元时间序列,如果直接用索引进行组织,由于维度过高,会使索引的性能严重退化[, ].为此,可以使用PAA方法把序列从n维约减至N维(N&&n),再用索引对N维向量进行组织.LB_DTW的输入是n维原始序列,下面再提出一种下界距离LB_PAA,其输入为N维向量(原始序列的PAA形式),这样便能够在N维索引结构上实现相似性搜索.
对一元查询序列Q的上、下边界序列U和L,分别使用PAA方法表示为:
下界距离LB_PAA定义为
由公式(13)可知:
使用R-Tree对N维向量进行组织,设V为索引上的叶子结点,R=(L,H)表示与叶子结点V相关的MBR,其中, H=(h1,h2,…,hN),L=(l1,l2,…,lN)分别表示最小边界矩形R的上、下边界,R中包含着满足上、下边界条件的N维向量.Q与R的距离定义为
表示查询序列Q与R中所有N维向量的最小LB_PAA距离,证明过程见文献[].因此,如果大于阈值e,则Q与R中所有N维向量的LB_PAA距离都大于e,从而实现剪枝过滤功能.
LB_DTW,LB_PAA和MinDist均是针对等长一元时间序列的DTW下界距离,但应用场合不同,它们的输入对象分别为一元时间序列、N维向量(序列的PAA形式)和R-Tree索引上的MBR.三者之中,LB_DTW是基础, LB_PAA和MinDist是对LB_DTW的延伸.
3.3 相似性搜索算法
下面给出e范围搜索算法RangeSearch(Q,e,rootNode),算法以一元查询序列Q、距离阈值e和R-Tree的根结点rootNode作为输入,采用结点递归的方式进行搜索,如图 7所示.
图7Fig. 7Fig. 7 Algorithm of e range search图 7 e范围搜索算法
4MTS相似性搜索流程
上文在各个步骤上详细阐述了不等长MTS相似性搜索的实现方法,本节将从整体流程上对该方法进行描述.支持DTW距离的不等长MTS相似性搜索主要包括3方面的内容:
(1) 用索引结构组织MTS数据库,如图 8所示;
图8Fig. 8Fig. 8 Process of index construction图 8 索引构建流程
(2) 提取查询序列的上、下边界特征,如图 9所示;
图9Fig. 9Fig. 9 Feature extraction process of query upper and lower bounding series图 9 查询序列上、下边界的特征提取流程
(3) 用查询序列的上、下边界特征在索引结构上进行相似性搜索,如图 10所示.
图10Fig. 10Fig. 10 Process of similarity search图 10 相似性搜索流程
使用变量加和方法,把数据库中的MTS转换为UTS.但由于UTS的时间维数较高,直接用索引进行组织较为困难,因此在把UTS扩展为等长序列的基础上,通过PAA方法把等长UTS转换为N维向量,其中,N为索引结构能够处理的维度数.最后,使用R-Tree索引结构对所有的N维向量进行组织.
从MTS数据库中任意抽取一个序列作为查询序列,通过变量加和、序列扩展的方法,将其转换为定长一元时间序列,使得查询序列与MTS数据库中其他序列具有相同的长度;然后,提取定长一元时间序列的上、下边界序列;最后,通过PAA方法把上、下边界序列分别转换为N维向量,作为查询序列在索引查询中的特征.
在前两个流程的基础上,根据公式(16)、公式(18),使用查询序列上、下边界序列的N维向量形式,在索引结构上执行搜索,搜索结果构成候选集.
由于使用DTW下界距离在索引结构上执行搜索,候选集中不会产生漏报但会引入误报序列,因此必须对候选集进行后处理,即把候选集中的UTS映射为原始MTS后,依次计算每个原始MTS与多元查询序列的DTW距离,去除误报序列.由于候选集中的序列数量远小于数据库中的序列数量,因此能够提高搜索效率.
5 实验分析与讨论
5.1 实验环境与实验数据
实验环境为Matlab 7.0,Windows XP Professional SP3,300G硬盘,1.98G内存,Intel(R) Core(TM)2 Duo CPU.选取两组多元时间序列数据集作为研究对象:Australian Sign Language[]和FlightData.
Australian Sign Language(记为ASL)是一组手语信号数据集,包含22个连续型变量,左、右手的动作特征各用11个变量刻画:6个变量(分别对应6个自由度)表示手所处的位置,5个变量表示各手指的弯曲程度.手语信号数据集包含95种语意(95个类),每种语意都有27组序列.不失一般性,选取前8种语意对应的序列作为实验数据集(记为ASL),一共216个实验样本.8种语意分别为alive,all,answer,boy,building,buy,change-mind,cold,216组多元时间序列的时间跨度在47~95之间,每组序列都体现一个完整的手语动作过程.
FlightData是一组飞行数据集,它记录了某型飞机在训练过程中的飞行品质.为了便于实验分析,邀请飞参领域专家,通过专业软件截取飞行过程中表征特定飞行动作的数据段作为研究对象.5组飞行动作分别为:加力盘旋、减速盘旋、水平横滚、180°盘旋和360°盘旋,每组动作包含200个样本序列.飞行速度、飞行高度、俯仰角、横滚角和航向角这5个变量基本能够对这些飞行动作进行完整刻画.1 000组多元飞行数据的时间跨度在240~319之间,每组序列都体现一个完整的飞行动作过程.
使用文献[]中的共同主成分方法分别对两组数据集进行降维,方差贡献率参数s=80%,两组MTS数据集降维后的变量数均为2,分别记为ASL_DR,FlightData_DR,后续的实验针对降维后的数据进行讨论.
5.2 实验结果与分析
设多元时间序列Q,C,使用变量加和方法转换为不等长一元时间序列Q&,C&,序列扩展后形成等长一元时间序列Q&+,C&+,U&+,L&+是Q&+的上、下边界序列,和分别是U&+,L&+和C&+的PAA形式.
实验1. MTS转化为UTS时,变量加和方案的选择.
由性质4知,对于变量数为m(m&1)的多元时间序列Q,C,把任意对应的k(1≤k≤m)个变量相加,能够得到两组一元时间序列Q&,C&,每一个k值都对应着种加和方案,因此,变量加和的方案一共有种.下面研究把MTS转化为UTS时,如何选择最佳的变量加和方案.距离保持率s定义为
它表示变量加和方法对DTW距离的保持程度,并用其评价各种方案的优劣.s越大,说明转换效果越好.
设MTS数据集DsMts中含有n个序列,使用一种变量加和方案,把其转化为UTS数据集DsUts.从DsUts中任意选择一个序列作为查询序列Q&,它在DsMts中对应的序列为Q;DsUts中的其他序列为(1≤i≤n-1),它在DsMts中对应的序列记为Ci.si表示Q&与其他n-1个序列的平均距离保持率,见公式(20):
使用留一交叉验证法重复以上实验,可以得到n个平均距离保持率.则平均距离保持率的数学期望s*可由公式(21)确定,并用其作为变量加和方案的比较依据:
下面针对降维数据集FlightData_DR,ASL_DR计算各种变量加和方案的s*.两种数据集中的变量数均为2,不妨记为x1,x2,则一共存在3种加和方案,结果见表 1.
表 1(Table 1)
Table 1 Comparison of different variable addition schemes 表 1 变量加和方案的比较
变量加和方案
S* (FlightData_DR)
S* (ASL_DR)
Table 1 Comparison of different variable addition schemes 表 1 变量加和方案的比较
从实验结果可以看出,对于FlightData_DR,ASL_DR,最优加和方式均为方案3.使用最优加和方案得到的UTS数据集分别记为FlightData_DR_UTS,ASL_DR_UTS.为了形象地验证性质4,在ASL_DR_UTS中选择第1个序列作为查询序列Q&,分别计算Q&与其他序列(2≤i≤216)的距离;再求出ASL_DR中对应序列的距离DTW(Q,Ci),结果如图 11所示.为了便于观察,图中仅截取了曲线的前50个点.可以看出,DTW(Q,Ci)的值都在之上,从而验证了性质4的正确性.
图11Fig. 11Fig. 11 Validation of variable addition method图 11 变量加和方法的有效性验证
实验2. 不等长UTS列扩展为等长UTS.
使用序列扩展方法,把实验1中变量加和后的UTS数据集FlightData_DR_UTS,ASL_DR_UTS分别转化为等长UTS数据集,记为FlightData_DR_UTS_ELen(其中的序列长度均为320),ASL_DR_UTS_ELen(其中的序列长度均为96).
下面验证序列扩展方法的有效性.
在ASL_DR_UTS_ELen中,选择第1个序列作为查询序列Q&+,分别计算Q&+与数据集中其他序列(2≤i≤216)的距离;再求出ASL_DR_UTS中对应序列的距离,结果如图 12所示.为了便于观察,图中仅截取了曲线的前50个点.
可以看出,的值都在之上,从而验证了
图12Fig. 12Fig. 12 Validation of time series extended method图 12 序列扩展方法的有效性验证
实验3. 下界距离LB_DTW的紧致性分析.
紧致性越好,说明下界距离越接近实际距离,使用下界距离进行查询时,得到的误报序列就越少.实验用紧缩率和修剪率两个指标度量下界距离LB_DTW的紧致性.下界距离LB_DTW的紧缩率TDTW定义为
修剪率P定义为
其中,N表示使用顺序扫描方法与查询序列进行DTW距离计算的序列数,即为数据集中的序列数量;N0表示在下界距离LB_DTW的过滤作用下,不需要与查询序列进行DTW距离计算的序列数.
紧缩率、修剪率越高,表明紧致性越好,下界距离的过滤作用越明显,从而减少后处理的计算量,提高查询效率.下面以等长UTS数据集FlightData_DR_UTS_Elen,ASL_DR_UTS_ELen为实验对象,使用留一交叉验证法计算两组数据集中紧缩率TDTW的平均值以及不同距离阈值e下的修剪率,结果分别见表 2并如图 13所示.
表 2(Table 2)
Table 2 Tightness ratio of LB_DTW 表 2 下界距离LB_DTW的紧缩率
实验数据集
紧缩率的平均值(%)
FlightData_DR_UTS_ELen
ASL_DR_UTS_ELen
Table 2 Tightness ratio of LB_DTW 表 2 下界距离LB_DTW的紧缩率
图13Fig. 13Fig. 13 Pruning efficiency of the lower bounding function LB_DTW图 13 下界距离LB_DTW的修剪率
实验结果表明:针对两组数据集时,下界距离LB_DTW的紧缩率均大于50%;距离阈值较小时,修剪率都能达到70%以上.这说明下界距离LB_DTW的紧致性较好,在查询中的过滤作用较为明显.距离阈值越小,修剪率越高;随着阈值的不断增加,修剪率逐渐降低.这是因为下界距离LB_DTW的修剪率依赖于距离阈值,当距离阈值大于实际DTW距离时,下界距离将失去过滤作用.
实验4. PAA方法中分段数N的确定.
下面讨论把UTS表示为PAA形式时,分段数N的确定方法.下界距离LB_PAA的紧缩率TPAA定义为
分段数N决定着对U&+,L&+,C&+的近似程度,N越大,近似程度越高.以等长UTS数据集FlightData_DR_UTS_Elen,ASL_DR_UTS_ELen为实验对象,当N取不同值时,使用留一交叉验证法计算紧缩率TPAA的平均值,结果如图 14所示.
图14Fig. 14Fig. 14 Relation between N in PAA method and tightness ratio图 14 PAA方法中分段数N与紧缩率之间的关系
从实验结果可以看出,分段数N越大,紧缩率越高.这是由于随着N的增加,PAA方法对序列的近似程度逐步提高,下界距离LB_PAA就越接近实际DTW距离.
针对FlightData_DR_UTS_Elen,ASL_DR_UTS_ELen,N分别取320,96时,下界距离LB_PAA的紧缩率与LB_DTW相同.这是因为当分段数N与时间序列的长度相同时,序列的PAA形式就是序列自身,LB_DTW, LB_PAA具有相同的表达式.
文献[, ]表明,对于高维空间索引结构,当维度数大于16时,索引的性能会严重下降.因此,一般取N≤16.从图 14可看出,当N=16时,紧缩率已经与最大值比较接近.
实验5. 下界距离LB_DTW与DTW距离计算复杂度的比较.
通过理论分析可知,下界距离LB_DTW的计算复杂度低于DTW距离,下面用实验进行验证.
以FlightData_DR_UTS_Elen,ASL_DR_UTS_ELen为实验对象,用平均查询时间表示计算复杂度.为了消除实验环境引起的偏差,以两种方法计算时间的比值作为比较依据,结果见表 3.
表 3(Table 3)
Table 3 Comparison of computation time between LB_DTW and DTW distance
表 3 LB_DTW,DTW距离计算时间的比较
实验数据集
tLB_DTW/tDTW
FlightData_DR_UTS_ELen
ASL_DR_UTS_ELen
Table 3 Comparison of computation time between LB_DTW and DTW distance
表 3 LB_DTW,DTW距离计算时间的比较
从实验结果可以看出,针对两组数据集,下界距离LB_DTW的计算时间不足DTW距离的1%.这是由于LB_DTW在形式和计算方法上都非常类似于Minkowski距离,序列间的点对匹配关系明确,计算过程中不需要考虑动态时间弯曲的影响.
本文给出了一种MTS的DTW下界距离LB_DTW;然后以其为基础,提出了一种支持DTW距离度量的MTS索引结构,进而给出相应的相似性搜索算法.LB_DTW以相关性质为理论支撑,实现了从一元向多元、从等长向不等长的拓展,把研究对象从等长一元时间序列推广到不等长多元时间序列,可视为对LB_Keogh方法的拓展.实验结果表明,本文提出的MTS索引方法能够有效地支持DTW距离的相似性搜索,且具有非漏报性,与顺序扫描方法相比,能够有效地提高搜索效率.
致谢 感谢Mohammed Waleed Kadous提供的实验数据集Australian Sign Language.
Zhou DZ, Wu XL, Yan HC. An efficient similarity search for multivariate time series. Computer Applications, ):
(in Chinese with English abstract).
Zhu Q, Wang XY, Keogh E, Lee SH. An efficient and effective similarity measure to enable data mining of petroglyphs..
Li ZX, Zhang FM, Li KW. Research on pattern matching method for multivariate time series. Control and Decision, ): 565-570 (in Chinese with English abstract).
Zhou DZ, Jiang WB, Li MQ. Efficient clustering algorithm for multivariate time series. Computer Engineering and Applications, ):137-139 (in Chinese with English abstract).
Fu AWC, Keogh E, Lau LYH, Ratanamahatana CA, Wong RCW. Scaling and time warping in time series querying..
Bankó Z, Abonyi J. Correlation based dynamic time warping of multivariate time series..
Bhaduri K, Zhu Q, Oza NC, Srivastava AN. Fast and flexible multivariate time series subsequence search. .
Vlachos M, Hadjieleftheriou M, Gunopulos D, Keogh E. Indexing multidimensional time series..
Wong TSF, Wong MH. Efficient subsequence matching for sequences databases under time warping. .
Yi BK, Jagadish HV, Faloutsos C. Efficient retrieval of similar time sequences under time warping. .
Kim SW, Sanghyun P, Chu WW. An index-based approach for similarity search supporting time warping in large sequence databases. .
Keogh E, Ratanamahatana CA. Exact indexing of dynamic time warping..
Zhu YY, Shasha D. Warping indexes with envelope transforms for query by humming. I.
Mu B, Yan JL. Efficient time series lower bounding technique. Computer Engineering and Applications, ):168-171 (in Chinese with English abstract).
Berndt DJ, Clifford J. Using dynamic time warping to find patterns in time series. In: Proc. of the Workshop on Knowledge Discovery in Databases. 8.
Zhou M, Wong MH. Efficient online subsequence searching in data streams under dynamic time warping distance. .
Faloutsos C, Ranganathan M, Manolopoulos Y. Fast subsequence matching in time-series databases. .
Zhang MB, Lu F, Shen PW, Cheng CX. The evolvement and progress of R-tree family. Chinese Journal of Computers, ): 289-300 (in Chinese with English abstract).
Guttman A. R-trees: A dynamic index structure for spatial searching. .
Yi BK, Faloutsos C. Fast time sequence indexing for arbitrary Lp norms. In: Proc. of the 26th Int’l Conf. on Very Large Databases. 4.
Park S, Chu WW, Yoon J, Won J. Similarity search of time-warped subsequences via a suffix tree..
Seidl T, Kriegel H. Optimal multi-step k-nearest neighbor search. In: Proc. of the ACM SIGMOD Int’l Conf. on Management of Data. 5.
Kadous MW. High-Quality recordings of Australian sign language signs. 2002. .
Yoon H, Yang K, Shahabi C. Feature subset selection and feature ranking for multivariate time series. IEEE Trans..
周大镯,吴晓丽,闫红灿.一种高效的多变量时间序列相似查询算法.计算机应用,):.
李正欣,张凤鸣,李克武.多元时间序列模式匹配方法研究.控制与决策,):565-570.
周大镯,姜文波,李敏强.一个高效的多变量时间序列聚类算法.计算机工程与应用,):137-139.
穆斌,闫金来.高效的时间序列下界技术.计算机工程与应用,):168-171.
张明波,陆锋,申排伟,程昌秀.R树家族的演变和发展.计算机学报,):289-300.}