。398· 北京科技大学学报 2006年第4期 9.k(x)=229(2x-k,j,k∈Z(3) 索引并进行相似匹配，需给出两时间序列Q和C 对任意平方可积函数∫(x)来说，其离散小波变 的DTW距离在小波域的低限距离定义d(O, 换为： C),并证明d"s(Q,C)为其DTW距离的低限距 十 离，从而保证相似匹配无漏报.Haar小波二进制 Wgfj,k材= =f x)9(x)dx=(f.9),f(x) 平移系为： (4) 2?2≤K(2k+1)21 其中，j,k∈Zj为尺度因子，k为平移因子.信 hj.k(t)= -2"?,(2k+)2-≤K(k+1)2 号可以用各尺度的小波系数重构： 0. K2k或⊙≥(k+1)2 fx)=∑胸，k)9(x) (5) (8) i.k 给定时间序列X={x(t)}(i=L,,n)(设 其中，j,k∈z,j为尺度因子，k为平移因子.对 n=2,不足位补0)，利用Har小波变换对X进 于离散时间序列Q=(q1,,qi,；qm人，其Haar 行J尺度分解，分解系数为山，D,;Di,;D1 的小波系数为： (2+)2广1 (J为最大分解尺度).A山为原始序列在尺度J下 Wo(j,k)= 的逼近信号，D为原始序列在尺度1≤≤J)下 =2k 的细节信号.j尺度信号的长度为2一（即k=0, (9) -1,小波分解系数的总长度为 =H2+)21 +召-%与原序列张度相等. 定义7设时间序列Q的DTW上下包围边 界序列为U和L,按如下方法构造两个序列U" 小波分解系数的排列次序为：J尺度近似信 和L": 号、按尺度j从大到小的各尺度细节信号（对于同 . 一尺度的小波系数按平移因子k从小到大排 =1+24 列).由于在时间序列相似匹配中一般首先对序 (10 列进行归一化，J尺度近似值A均为0，因此只取 各尺度细节信号即可. L(,k)= =+2k =1H2+1)2 定义6对长为n(n=2)的序列X进行J (11) 层小波分解，小波系数按尺度值从大到小排列 式中，=1，；lbg2n,k=0,；j广-1. (同一尺度的小波系数按平移因子k从小到大排 将U(j,k)按j从大到小（相同时按k从小 列)，取前m(1≤m≤n一1)个系数可得到序列 到大)排列，得到序列U"={};将L(j,k)按j X"={x}(i=l,,m),定义为X的小波变换 从大到小(j相同时按k从小到大)排列，取前m 序列. 个系数得到序列L"={}(=1,…,m).则称 利用小波变换序列近似表示原序列，构建索 U"和L"为序列Q在小波变换域的DTW上下 引结构，使索引维数得到约简，对得到的匹配候选 边界序列. 序列.可通过后处理（计算DTW距离）来滤除匹 定理3对任意两个时间序列Q和X,U和 配误报.研究中采用简单易用的Har小波，也可 L为Q的DTW上边界序列和下边界序列，U" 以采用其他正交小波，如Daubechies紧支集小波 和L"为序列Q在小波变换域的DTW上、下边 等，Har小波是正交小波，其小波函数P(x)为： 界序列，X"为X的小波变换序列.如果L≤X 1,0x≤0.5 ≤U(≤x≤)，必有L"≤x"≤U". 9(x)= -1, 0.5<x≤1 (6) 证明：设X的小波系数为Wx(,k),由于 0. x≤0或x>1 l≤x≤u,所以有 尺度函数为： (2+1)2 wX(j.)= x)= L,0x≤1 7) =2 =H21)2 0,x≤0或x心1 2.2小波变换域的动态弯曲低限距离 利用时间序列的前m个小波变换系数建立 =1+H2+1)Yφj , k ( x ) =2 -j/2 φ( 2 -j x -k ), j, k ∈ Z ( 3) 对任意平方可积函数 f ( x ) 来说, 其离散小波变 换为 : Wφf( j, k) =∫ +∞ -∞ =f( x) φj , k ( x) d x =〈f , φj , k〉, f( x) ( 4) 其中, j, k ∈ Z, j 为尺度因子, k 为平移因子 .信 号可以用各尺度的小波系数重构: f ( x ) = ∑ j, k Wφf ( j, k ) φj, k ( x ) ( 5) 给定时间序列 X ={x ( ti)}( i =1, …, n) (设 n =2 J , 不足位补 0) , 利用 Haar 小波变换对 X 进 行J 尺度分解, 分解系数为 AJ , DJ , …, Dj , …, D1 ( J 为最大分解尺度) .AJ 为原始序列在尺度J 下 的逼近信号, Dj 为原始序列在尺度j( 1 ≤j ≤J )下 的细节信号.j 尺度信号的长度为2 J-j (即 k =0, …, 2 J -j -1 ) , 小 波 分 解 系 数 的 总 长 度 为 1 + ∑ J j =1 2 J -j =2 J =n, 与原序列长度相等. 小波分解系数的排列次序为 :J 尺度近似信 号、按尺度 j 从大到小的各尺度细节信号(对于同 一尺度的小波系数按平移因子 k 从小到大排 列) .由于在时间序列相似匹配中一般首先对序 列进行归一化, J 尺度近似值 AJ 均为0, 因此只取 各尺度细节信号即可 . 定义 6 对长为 n ( n =2 J ) 的序列 X 进行J 层小波分解, 小波系数按尺度 j 值从大到小排列 (同一尺度的小波系数按平移因子 k 从小到大排 列), 取前 m ( 1 ≤m ≤n -1) 个系数可得到序列 X w ={x w i }( i =1, …, m), 定义为 X 的小波变换 序列 . 利用小波变换序列近似表示原序列, 构建索 引结构, 使索引维数得到约简, 对得到的匹配候选 序列.可通过后处理(计算 DTW 距离) 来滤除匹 配误报 .研究中采用简单易用的 Haar 小波, 也可 以采用其他正交小波, 如 Daubechies 紧支集小波 等, Haar 小波是正交小波, 其小波函数 φ( x )为: φ( x ) = 1, 0 <x ≤0.5 -1, 0.5 <x ≤1 0, x ≤0 或 x >1 ( 6) 尺度函数为: ψ( x ) = 1, 0 <x ≤1 0, x ≤0 或 x >1 ( 7) 2.2 小波变换域的动态弯曲低限距离 利用时间序列的前 m 个小波变换系数建立 索引并进行相似匹配, 需给出两时间序列 Q 和C 的 DTW 距离在小波域的低限距离定义 d w LB( Q, C), 并证明 d w LB( Q, C) 为其 DTW 距离的低限距 离, 从而保证相似匹配无漏报 .Haar 小波二进制 平移系为 : hj, k ( t) = 2 -j/ 2 , 2 j k ≤t <( 2k +1) 2 j-1 -2 -j/ 2 , ( 2k +1) 2 j -1 ≤t <( k +1)2 j 0, t <2 j k 或 t ≥( k +1)2 j ( 8) 其中, j, k ∈ z, j 为尺度因子, k 为平移因子.对 于离散时间序列 Q =( q1, …, qi , …, qn ), 其 Haar 的小波系数为 : WQ( j, k ) = ∑ ( 2 k+1) 2 j-1 i =1+2 j k q( i) 2 -j 2 - ∑ ( k+1) 2 j i =1+( 2 k+1) 2 j-1 q( i) 2 -j 2 ( 9) 定义 7 设时间序列 Q 的 DTW 上下包围边 界序列为 U 和L, 按如下方法构造两个序列 U w 和 L w : U( j , k ) = ∑ ( 2k +1) 2 j -1 i =1 +2 j k u( i) 2 - j 2 - ∑ ( k+1) 2 j i =1+( 2 k+1) 2 j-1 l( i) 2 - j 2 ( 10) L ( j , k ) = ∑ ( 2 k+1) 2 j-1 i =1+2 j k l( i) 2 - j 2 - ∑ ( k+1) 2 j i =1 +( 2k +1) 2 j-1 u( i) 2 - j 2 ( 11) 式中, j =1, …, log2 n , k =0, …, j -1 . 将 U( j, k )按 j 从大到小( j 相同时按k 从小 到大)排列, 得到序列 U w ={u w i };将 L( j, k )按 j 从大到小( j 相同时按 k 从小到大) 排列, 取前 m 个系数得到序列 L w ={l w i }( i =1, …, m ) .则称 U w 和 L w 为序列 Q 在小波变换域的 DTW 上下 边界序列 . 定理 3 对任意两个时间序列 Q 和 X , U 和 L 为 Q 的 DTW 上边界序列和下边界序列, U w 和 L w 为序列 Q 在小波变换域的 DTW 上 、下边 界序列, X w 为 X 的小波变换序列.如果 L ≤X ≤U( li ≤x i ≤ui) , 必有 L w ≤X W ≤U w . 证明 :设 X 的小波系数为 WX ( j, k ), 由于 li ≤xi ≤ui , 所以有 WX ( j, k ) = ∑ ( 2 k+1) 2 j-1 i =1+2 j k x( i) 2 -j 2 - ∑ ( k+1) 2 j i =1+( 2 k+1) 2 j-1 x( i ) 2 -j 2 ≤ ∑ ( 2 k+1) 2 j-1 i =1+2 j k u( i) 2 - j 2 - ∑ ( k +1) 2 j i =1 +( 2k +1) 2 j -1 l( i) 2 - j 2 =U( j , k) · 398 · 北 京 科 技 大 学 学 报 2006 年第 4 期