第1期 史忠植，等：一种支持时间序列数据的CBR检索算法 ·41· [4]中提出的时态模型(temporal model)的基础上 len(g=n,m≥n.每个范例序列C有m-n+1个 的.文献[2]中提出了一种形式化逻辑方法来描述时 长度为n的子序列，其元素为Si]下文为了简洁 序信息，从时序模型的观点来看，这个工作特别有意 起见有时表示为y.设范例库中有N个范例序列， 义，因为该文建立的模型中融合了基于时间点的元 它们的长度不一定相等 素和基于时间间隔的元素.然而，作者却没有给出检 基于CBR的应用需要，范例库中任意范例序列 索算法，而只是声称可以采用图相似性算法来进行 C的长度m均大于查询序列Q的长度n.查询的过 相似度检索.文献[3]则是在一个具体的应用项目的 程中，需要用大小为n的滑动窗口在C上截取出子 背景下讨论了如何在CBR中应用Allen的模型，然 序列S,计算S与查询序列Q的相似度Sim(Q,S 而由于该应用的一些特殊约束，所以该文的解决方 相似度最大的几个S作为查询结果返回，这实际上 法并没有普遍适用性.Allen的时态模型是一种基 是一个子序列匹配问题， 于间隔的(interval-based).由于组合爆炸的缘故， 时间序列相似度模型对CBR的推理效果起着 这种模型只能处理一些简单的时序关系，而且相似重要作用，常用的有基于欧氏距离的，基于时间归整 性检索的计算量很大，效果也并不十分好」 (dynamic time warping)的，基于界标(landmark) 文献[16-17]引入的时态模型是基于时间序列 的，基于最长公共子序列(longest common subse 数据的，时间序列的相似度比较是个比较成熟的领 quence)的，基于分段线性化表示的，基于概率方法 域，有大量方法可以利用，比如时间规整(DTW),符 的，等等 号化，分段线型化，特征抽取降维技术等等.也正是 出于减少计算量，减少误警(false alarm)等考 因为这个原因，这2篇文章中没有过多的涉及具体 虑，文中使用了基于欧氏距离的相似度模型，即把时 的检索算法，而是侧重于设计时间序列CBR的框架 间序列看成向量，定义相似度与欧氏距离成反比，欧 和范例的存储结构.然而经过分析，CBR中的时间 氏距离越小，则相以度越大.这也是时间序列数据处 序列相似度比较具有很多特殊性，需要设计有针对 理中应用最广泛的相似度模型，但它与人类的认知 性的检索算法 模型有一定的差异，因为一些相似度很低（即欧氏距 文中选择采用的时序模型是时间序列数据，着 离很大)的序列对人类的感觉而言却是相似的 眼点不在于CBR的框架和范例的存储结构，而在于 E(Q.S) (x2 1V2 (1 针对CBR中时间序列数据的特点，利用计算机在数 值计算上的强大能力，设计高效的CBR检索算法 Sim(O,S)=-E(o.S). 文中的研究不仅参考了CBR等人工智能领域的研 计算相似度的时间复杂度为O(d,对每个范例 究成果，也很大程度上参考了时间序列数据领域的 序列需要计算m-n+1次相似度.如果直接计算的 一些成果 话，对于大小为N的范例库，一次查询需要进行N 次时间复杂度为O(n·(m-n+1))的比较.文中把 1 支持时间序列的CBR模型 这种直接计算的方法称作naive方法，并作为比较 在推广CBR时遇到的一个最大的阻碍就是难 各种算法效率的基准 于构造有效的范例库，CBR的应用首先要求从客户 2基于谱分析的相似度检索算法 的历史数据中抽取有代表性的数据构造范例库，这 个过程不可能完全由机器完成，必须有人工参与进 基于欧氏距离计算相似度的方法中，Agrawal 来.所以要向CBR增加时间序列支持，首先考虑的 等人1提出的基于离散傅里叶变换(DFT)的方法效 就是方便范例库的构造.实际应用中，用户往往只能 果比较好.离散傅立叶变换公式如下，x,是时域数 确定某一段时间内的时间序列数据有特殊的含义， 据，XF是变换域数据 但并不能确定代表这种特殊含义的精确模式，在这 i2F XF= x,exp F=0,1,…n-1, 种情况下最妥当的方法就是把这一段连续时间序列 整个作为一个范例存入范例库中 2) 文中使用的表示符号如下：范例序列为C,其长 2 =0,1,…,n-1. 度均大于某个下限，其元素表示为C11.查询序列 为Q,其长度均小于某个上限，其元素可表示为Q] 式中如果x:是实数，则(X)(F>0)一定是复数， 下文为了简洁起见有时表示为x.设len(g=m, 且Xr和X.r(F>O)一定互相共轭.模|Xr定义 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net[4 ]中提出的时态模型 (temporal model) 的基础上 的. 文献[ 2 ]中提出了一种形式化逻辑方法来描述时 序信息 ,从时序模型的观点来看 ,这个工作特别有意 义 ,因为该文建立的模型中融合了基于时间点的元 素和基于时间间隔的元素. 然而 ,作者却没有给出检 索算法 ,而只是声称可以采用图相似性算法来进行 相似度检索. 文献[3 ]则是在一个具体的应用项目的 背景下讨论了如何在 CBR 中应用 Allen 的模型 ,然 而由于该应用的一些特殊约束 ,所以该文的解决方 法并没有普遍适用性. Allen 的时态模型是一种基 于间隔的(interval - based) . 由于组合爆炸的缘故 , 这种模型只能处理一些简单的时序关系 ,而且相似 性检索的计算量很大 ,效果也并不十分好. 文献[16 - 17 ]引入的时态模型是基于时间序列 数据的 ,时间序列的相似度比较是个比较成熟的领 域 ,有大量方法可以利用 ,比如时间规整(D TW) ,符 号化 ,分段线型化 ,特征抽取降维技术等等. 也正是 因为这个原因 ,这 2 篇文章中没有过多的涉及具体 的检索算法 ,而是侧重于设计时间序列 CBR 的框架 和范例的存储结构. 然而经过分析 ,CBR 中的时间 序列相似度比较具有很多特殊性 ,需要设计有针对 性的检索算法. 文中选择采用的时序模型是时间序列数据 ,着 眼点不在于 CBR 的框架和范例的存储结构 ,而在于 针对 CBR 中时间序列数据的特点 ,利用计算机在数 值计算上的强大能力 ,设计高效的 CBR 检索算法. 文中的研究不仅参考了 CBR 等人工智能领域的研 究成果 ,也很大程度上参考了时间序列数据领域的 一些成果. 1 支持时间序列的 CBR 模型 在推广 CBR 时遇到的一个最大的阻碍就是难 于构造有效的范例库 ,CBR 的应用首先要求从客户 的历史数据中抽取有代表性的数据构造范例库 ,这 个过程不可能完全由机器完成 ,必须有人工参与进 来. 所以要向 CBR 增加时间序列支持 ,首先考虑的 就是方便范例库的构造. 实际应用中 ,用户往往只能 确定某一段时间内的时间序列数据有特殊的含义 , 但并不能确定代表这种特殊含义的精确模式 ,在这 种情况下最妥当的方法就是把这一段连续时间序列 整个作为一个范例存入范例库中. 文中使用的表示符号如下 :范例序列为 C ,其长 度均大于某个下限 ,其元素表示为 C[ i]. 查询序列 为 Q ,其长度均小于某个上限 ,其元素可表示为Q[ i] (下文为了简洁起见有时表示为 xt) . 设len( C) = m , len( Q) = n , m ≥n. 每个范例序列 C 有 m - n + 1 个 长度为 n 的子序列 S ,其元素为 S [ i](下文为了简洁 起见有时表示为 yt) . 设范例库中有 N 个范例序列 , 它们的长度不一定相等. 基于 CBR 的应用需要 ,范例库中任意范例序列 C的长度 m 均大于查询序列 Q 的长度 n. 查询的过 程中 ,需要用大小为 n 的滑动窗口在 C 上截取出子 序列 S ,计算 S 与查询序列 Q 的相似度 Sim ( Q , S) , 相似度最大的几个 S 作为查询结果返回 ,这实际上 是一个子序列匹配问题. 时间序列相似度模型对 CBR 的推理效果起着 重要作用 ,常用的有基于欧氏距离的 ,基于时间归整 (dynamic time warping) 的 ,基于界标 (landmark) 的 ,基于最长公共子序列 (longest common subse2 quence) 的 ,基于分段线性化表示的 ,基于概率方法 的 ,等等. 出于减少计算量 ,减少误警 (false alarm) 等考 虑 ,文中使用了基于欧氏距离的相似度模型 ,即把时 间序列看成向量 ,定义相似度与欧氏距离成反比 ,欧 氏距离越小 ,则相似度越大. 这也是时间序列数据处 理中应用最广泛的相似度模型 ,但它与人类的认知 模型有一定的差异 ,因为一些相似度很低(即欧氏距 离很大) 的序列对人类的感觉而言却是相似的. E( Q , S) = ∑ n- 1 t =0 ( xt - yt) 2 1/ 2 . (1) Sim( Q , S) = - E( Q , S) . 计算相似度的时间复杂度为 O( n) ,对每个范例 序列需要计算 m - n + 1 次相似度. 如果直接计算的 话 ,对于大小为 N 的范例库 ,一次查询需要进行 N 次时间复杂度为 O ( n ·( m - n + 1) ) 的比较. 文中把 这种直接计算的方法称作 naive 方法 ,并作为比较 各种算法效率的基准. 2 基于谱分析的相似度检索算法 基于欧氏距离计算相似度的方法中 ,Agrawal 等人[5 ]提出的基于离散傅里叶变换(DF T) 的方法效 果比较好. 离散傅立叶变换公式如下 , xt 是时域数 据 , X F 是变换域数据. X F = 1 n ∑ n- 1 t =0 xtexp - j2πFt n , F = 0 ,1 , …, n - 1 , (2) xt = 1 n ∑ n- 1 F=0 X Fexp j2πFt n , t = 0 ,1 , …, n - 1. 式中 :如果 xt 是实数 ,则 ( X F) ( F > 0) 一定是复数 , 且 X F 和 X n - F ( F > 0) 一定互相共轭. 模| X F | 定义 第 1 期 史忠植 ,等 :一种支持时间序列数据的 CBR 检索算法 · 14 ·