·42 智能系统学报 第2卷 为频谱(spectrum),|Xr2定义为功率谱(power 基于上述理论，文献[5-6]中采取的方法是事先计 spectrum).X比较特殊，一个序列中每个元素加上 算出所有模式序列（对应于文中CBR中的范例）的 相同的值，则只影响X,而XF,0<F<保持不 谱变换系数，以若变换序列中若干低频项作为索引 变.自然界大多数信号经DFT变换后所得频谱都是 构建高维索引结构来进行相似度匹配 非均匀的，低频对应的频谱比较大，其频谱（以股票 3 价格为例，去除Xo)表现如图1所示 时间序列CBR检索算法 3.1已有算法的分析 34.5 这种方法效率很高，但是如果照搬到CBR系统 33.5 中，会造成一些问题】 32.5 31.5 第一，缺乏灵活性.结合CBR的具体应用，显然 30.5 应当允许查询序列的长度可变，但是文献[5·6]中 25 49 事先计算谱变换序列的方法，在变换之前要求固定 (a) 序列的长度，这就限制了查询序列的长度，也就极大 25 的限制了CBR的应用范围。 第二，文献[5-6]在谱变换系数中取k个主分 量（即2k个实数作为索引），建立维度为2k的高维 5%Nw 索引结构，可是经过研究，所有的高维索引结构，包 0 9 172533 414957 括R-tree及其变种，pyramid-tree,空间填充曲线 MHz (b) 等，在高维情况下性能均退化到低于线性索引.而且 图1时间序列数据及其频谱 为了减少索引结构的规模，在建立高维索引过程中 Fig 1 Time-series data and its frequency spectrum 采取了很多近似手段，影响了查询精度，不适用于某 些精度要求非常高的应用】 DFT有如下Parseval定理 1 上述算法的核心思想是寻找时域运算在频域的 w2=,I 3 等价计算方式，从中寻找优化的可能，在此思想指导 同时DFT是一种线性变换，即有 下，提出了另一种利用FFT简化基于欧氏距离的相 [x:+]→[XF-YF1, 4) 似度计算的改进方法 [ax:1→faXF] (5) 3.2改进方法 式中：[]表示由式中：元素构成的向量，→表示傅里 对每一条范例序列C,用长度为n的滑动窗口 叶变换，由式(3)和式(4)，可以推得 截取C可得到m·n+1个子序列，应用式(1)分别 Ix-]→[Xr-Yr: 6 计算出m~n+1个相似度，这个过程可表示成如下 代入式(3)推得 的形式.为了推导的方便，用表示Q的元素，表示在 E(2.S)=E([Xr1.[YE))ll XY ll Q与S比较过程中计算的第t个E(Q,Sy 1/2 (7) E0=0f++0,1=0.…mn 即时域数据的欧氏距离可以用傅里叶变换后所得频 (9) 谱来求解 因式分解得 由于频谱分布的不均匀性，可以只取频谱的k o.1 个主分量来计算欧氏距离.虽然很大，但由于它 E(2=】 0时+c+f.2,1c+1. 与序列的波形变化无关，应予以忽略.计算DFT时 1=0,m-n (10) 可以略去公式，式2)中系数十以优化计算，并不影 n 式中 ∑]C(1+)是一个卷积，卷积的连续形 响相似度的比较.这样相似度定义为 +四 式一 般形如h(w=(x)g(u-xdx,而卷积的 E(Q.S)E([Xr].[YF1)= + E(x.. 12 ,0<k<n 8 离散形式一般是h(W=∑xu·. 1994-2008 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net为频谱 ( spectrum) , | X F | 2 定义为功率谱 (power spectrum) . X0 比较特殊 ,一个序列中每个元素加上 相同的值 ,则只影响 X0 ,而 X F , (0 < F < n) 保持不 变. 自然界大多数信号经 DF T 变换后所得频谱都是 非均匀的 ,低频对应的频谱比较大 ,其频谱 (以股票 价格为例 ,去除 X0 ) 表现如图 1 所示. 图 1 时间序列数据及其频谱 Fig11 Time2series data and its frequency spectrum DF T 有如下 Parseval 定理 : ∑ n- 1 t = 0 ( xt) 2 = ∑ n- 1 F= 0 | X F | 2 . (3) 同时 DF T 是一种线性变换 ,即有 [ xt + yt ] ] [ X F - Y F ] , (4) [ ax t ] ] [ aX F ]. (5) 式中 :[ ]表示由式中 :元素构成的向量 , ] 表示傅里 叶变换 ,由式(3) 和式(4) ,可以推得 [ xt - yt ] ] [ X F - Y F ]. (6) 代入式(3) 推得 E( Q , S) = E([ X F ] ,[ Y F ]) = ‖XY‖2 = ∑ n- 1 F=0 | X F - Y F | 2 1/ 2 . (7) 即时域数据的欧氏距离可以用傅里叶变换后所得频 谱来求解. 由于频谱分布的不均匀性 ,可以只取频谱的 k 个主分量来计算欧氏距离. X0 虽然很大 ,但由于它 与序列的波形变化无关 ,应予以忽略. 计算 DFT 时 可以略去公式 ,式(2) 中系数 1 n 以优化计算 ,并不影 响相似度的比较. 这样相似度定义为 E( Q , S) = E([ X F ] ,[ Y F ]) = ∑ k- 1 F=0 ( X F - Y F) 2 1/ 2 ,0 < k < n. (8) 基于上述理论 ,文献[ 5 - 6 ]中采取的方法是事先计 算出所有模式序列 (对应于文中 CBR 中的范例) 的 谱变换系数 ,以若变换序列中若干低频项作为索引 构建高维索引结构来进行相似度匹配. 3 时间序列 CBR 检索算法 311 已有算法的分析 这种方法效率很高 ,但是如果照搬到 CBR 系统 中 ,会造成一些问题. 第一 ,缺乏灵活性. 结合 CBR 的具体应用 ,显然 应当允许查询序列的长度可变 ,但是文献[ 5 - 6 ]中 事先计算谱变换序列的方法 ,在变换之前要求固定 序列的长度 ,这就限制了查询序列的长度 ,也就极大 的限制了 CBR 的应用范围. 第二 ,文献[5 - 6 ]在谱变换系数中取 k 个主分 量(即 2 k 个实数作为索引) ,建立维度为 2 k 的高维 索引结构 ,可是经过研究 ,所有的高维索引结构 ,包 括 R2tree 及其变种 , pyramid2tree ,空间填充曲线 等 ,在高维情况下性能均退化到低于线性索引. 而且 为了减少索引结构的规模 ,在建立高维索引过程中 采取了很多近似手段 ,影响了查询精度 ,不适用于某 些精度要求非常高的应用. 上述算法的核心思想是寻找时域运算在频域的 等价计算方式 ,从中寻找优化的可能 ,在此思想指导 下 ,提出了另一种利用 FFT 简化基于欧氏距离的相 似度计算的改进方法. 312 改进方法 对每一条范例序列 C,用长度为 n 的滑动窗口 截取 C 可得到 m - n + 1 个子序列 ,应用式 (1) 分别 计算出 m - n + 1 个相似度 ,这个过程可表示成如下 的形式. 为了推导的方便 ,用表示 Q 的元素 ,表示在 Q 与 S 比较过程中计算的第 t 个 E ( Q , S) . E(t) 2 = ∑ n- 1 t =0 (Q[i] 2 + ∑ n- 1 i =0 - C[t + i]) 2 ,t = 0 , …,m - n. (9) 因式分解得 : E(t) 2 = ∑ n- 1 i =0 (Q[i] 2 + ∑ n- 1 i =0 C[t + i] 2 - 2 ∑ n- 1 i =0 Q[i]C[t + i], t = 0 , …, m - n. (10) 式中 : ∑ n- 1 i =0 Q[ i]C( t + i) 是一个卷积 ,卷积的连续形 式一般形如 h( u) = ∫ + ∞ - ∞ f ( x) g ( u - x) d x ,而卷积的 离散形式一般是 h( u) = ∑ + ∞ i = - ∞ x [ i] y[ u - i]. · 24 · 智 能 系 统 学 报 第 2 卷