第1期 史忠植，等：一种支持时间序列数据的CBR检索算法 ·43 为了把式(10)中第3项化成卷积的标准形式， 项可以事先计算并保存在范例库中，检索过程中无 构造了序列P,使得PIi1=Q(n·1·),则式9 需重复计算，第3项即式(13)中H(W,u=n-1, 可以表示为 m-1的是主要的计算.通过利用FFT,计算 -1 H(W序列的时间复杂度从O(mn)降低到 EItP =(Pli]-clu-ip. O(m+n-1))lg(m+n-)).这是一般情况下 =n-1,…,m-1. 11) 的性能，如果结合CBR的具体应用，还有进一步优 因式分解得： 化的可能：如果所有范例序列的长度m都一样，则 Eto-ictu. 对P补m~1个零得到的P是唯一的，每次查询过 程只需对P作一次FFT计算，否则N次：如果限定 - 2 P[i]Clu-i],u=n-1,m-1.(12) 查询序列长度n为固定大小，则C的每个补了n-1 个零的子序列S也可事先确定，则每个S的FFT 式(12)与式10)中的项是一一对应的，第3项单独 也可以事先计算并保存.但是无论如何优化，每次查 列出如下： 询都要计算N次频域的componentwise积和N次 R-I H(w=∑P[iCw-iu=n-1,…m-1. 反变换，而计算第3项H(,u=n-1,…m-1的 时间复杂度不会变，仍是O(m+n-1)lg(m+n- 13) 1)) 可见H(W确实是一个离散卷积（亦称线性卷积）. 直接计算H(的时间复杂度为O(m) 4 数值试验 文献151中证明了一些有用的结论，第一，有限 从Yahoo财经网站上取得l00支股票，每支截 长序列的线性卷积等于循环卷积，而不产生混淆的 取10000个数据点，构造范例库.试验程序在linux 必要条件是延拓周期L≥N+M-1,式中N、M为2 (内核版本2.6)上用C实现，编译器是GCC4.0,傅 个有限长序列的长度.第2，傅里叶变换的循环卷积 立叶变换用的是FFTW3数学库 定理时域的循环卷积对应于频域的乘积.第3， 根据数据的实际意义，有时需要先作一些预处 长度为n的离散序列的FFT可以在O(dgm内完 理，比如对于股票价格序列，要调整数据以去除配股 成 和分红对价格序列的影响，使得各个不同时期的数 傅里叶变换的循环卷积定理的公式表达如下： 据具有可比性.这点不予以详述 A B =iDFT(DFT(A)*DFT(B)).(14) 一般希望图1中的频谱分布更加集中在少数几 式中：⊙为循环卷积运算21，文献12]第11章 个主分量上，这就需要对原始数据进行滤波，滤除高 有详细的说明和定义；*（点乘，componentwise 频分量，在这里采用金融技术分析中常用的滑动平 product)是这样一种运算 均法(Moving Averages)): 一个长度为n的序列和一个长度为m的序列 卷积后的序列长度为m+n-1,即式(14)中A⊙B 的长度为m+n-1,所以A、B的长度也必须为m+ 200 n-1.所以在对P和C作FFT之前，要先将2个序 150 列末端补零转化为长度为m+n-1的P和C,然 100 后进行如下的计算过程： P''=iDFT(DFT(P)*DFT(O)). 50 15) 由式(13)得到的H(W序列的长度为m-n+1,而 9 11 用式15)求得的p'⊙C长度为m+n-1,仔细分析 查询长度的对数log2(n P和C循环卷积的过程可知，p'⊙C的头n-1项 图2数值试验结果 和尾n-1项不是需要的欧氏距离，应予以舍弃」 Fig 2 experiment result 整个算法的分析如下：式12中，对于一次查询 试验结果如图所示.纵坐标表示10次不同的查 而言，第1项在整个检索过程中只要计算一次，第2 询所用时间，横坐标为查询序列长度（取对数坐标） 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net为了把式(10) 中第 3 项化成卷积的标准形式 , 构造了序列 P ,使得 P[ i] = Q( n - 1 - i) ,则式(9) 可以表示为 E[ t] 2 = ∑ n- 1 i =0 ( P[ i] - C[ u - i] 2 , u = n - 1 , …, m - 1. (11) 因式分解得 : E( t) 2 = ∑ n- 1 i =0 P[ i] 2 + ∑ n- 1 i = 0 C[ u - i] 2 - 2 ∑ n- 1 i =0 P[ i]C[ u - i] , u = n - 1 , …, m - 1. (12) 式(12) 与式(10) 中的项是一一对应的 ,第 3 项单独 列出如下 : H ( u) = ∑ n- 1 i = 0 P[ i]C[ u - i] , u = n - 1 , …, m - 1. (13) 可见 H ( u) 确实是一个离散卷积 (亦称线性卷积) . 直接计算 H ( u) 的时间复杂度为 O( m n) . 文献[15 ]中证明了一些有用的结论 ,第一 ,有限 长序列的线性卷积等于循环卷积 ,而不产生混淆的 必要条件是延拓周期 L ≥N + M - 1 ,式中 N 、M 为 2 个有限长序列的长度. 第 2 ,傅里叶变换的循环卷积 定理 ———时域的循环卷积对应于频域的乘积. 第 3 , 长度为 n 的离散序列的 FFT 可以在 O ( nlg n) 内完 成. 傅里叶变换的循环卷积定理的公式表达如下 : A á B = iDF T(DF T( A) 3 DF T( B) ) . (14) 式中 : á 为循环卷积运算[12 ] ,文献[12 ]第 11 章 有详细的说明和定义; 3 ( 点乘 , componentwise product) 是这样一种运算 : a b 3 c d = ac bd . 一个长度为 n 的序列和一个长度为 m 的序列 卷积后的序列长度为 m + n - 1 ,即式 (14) 中 A á B 的长度为 m + n - 1 ,所以 A 、B 的长度也必须为 m + n - 1. 所以在对 P 和 C 作 FF T 之前 ,要先将 2 个序 列末端补零转化为长度为 m + n - 1 的 P′和 C′. 然 后进行如下的计算过程 : P′á Q′= iDF T(DF T( P′) 3 DF T( Q′) ) . (15) 由式(13) 得到的 H ( u) 序列的长度为 m - n + 1 ,而 用式(15) 求得的 P′á C′长度为 m + n - 1 ,仔细分析 P′和 C′循环卷积的过程可知 , P′á C′的头 n - 1 项 和尾 n - 1 项不是需要的欧氏距离 ,应予以舍弃. 整个算法的分析如下 :式(12) 中 ,对于一次查询 而言 ,第 1 项在整个检索过程中只要计算一次 ,第 2 项可以事先计算并保存在范例库中 ,检索过程中无 需重复计算 ,第 3 项即式 (13) 中 H ( u) , u = n - 1 , …, m - 1 的是主要的计算. 通过利用 FF T , 计算 H ( u) 序 列 的 时 间 复 杂 度 从 O ( m n ) 降 低 到 O( ( m + n - 1) ) ·lg ( m + n - 1) ) . 这是一般情况下 的性能 ,如果结合 CBR 的具体应用 ,还有进一步优 化的可能 :如果所有范例序列的长度 m 都一样 ,则 对 P 补 m - 1 个零得到的 P′是唯一的 ,每次查询过 程只需对 P′作一次 FF T 计算 ,否则 N 次;如果限定 查询序列长度 n 为固定大小 ,则 C′的每个补了 n - 1 个零的子序列 S′也可事先确定 ,则每个 S′的 FF T 也可以事先计算并保存. 但是无论如何优化 ,每次查 询都要计算 N 次频域的 componentwise 积和 N 次 反变换 ,而计算第 3 项 H ( u) , u = n - 1 , …, m - 1 的 时间复杂度不会变 ,仍是 O( m + n - 1) ·lg ( m + n - 1) ) . 4 数值试验 从 Yahoo 财经网站上取得 100 支股票 ,每支截 取10 000个数据点 ,构造范例库. 试验程序在 linux (内核版本 216) 上用 C 实现 ,编译器是 GCC410 ,傅 立叶变换用的是 FFTW3 数学库. 根据数据的实际意义 ,有时需要先作一些预处 理 ,比如对于股票价格序列 ,要调整数据以去除配股 和分红对价格序列的影响 ,使得各个不同时期的数 据具有可比性. 这点不予以详述. 一般希望图 1 中的频谱分布更加集中在少数几 个主分量上 ,这就需要对原始数据进行滤波 ,滤除高 频分量 ,在这里采用金融技术分析中常用的滑动平 均法(Moving Averages) : ^x t = 1 w ∑ w- 1 i = 0 xt- i . 图 2 数值试验结果 Fig12 experiment result 试验结果如图所示. 纵坐标表示 10 次不同的查 询所用时间 ,横坐标为查询序列长度(取对数坐标) . 第 1 期 史忠植 ,等 :一种支持时间序列数据的 CBR 检索算法 · 34 ·