第2卷第1期 智能系统学报 Vol.2 Ng 1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 一种支持时间序列数据的CBR检索算法 史忠植，尹超2叶世伟 (1.中国科学院计算技术研究所智能信息处理重点实验室，北京100080：2.中国科学院研究生院信息科学与工程学院，北京 100039) 摘要：探讨了如何为CBR(基于范例的推理)增加对一种特殊的范例类型时间序列数据的支持.分析了基于谱 分析的时间序列相似度比较算法不适用于CBR检索的缺点，并在此基础上设计了一种综合性能很好的CBR检索算 法.思路是把时间序列相似度比较转化成一个卷积问题，并用DT来简化这个卷积的计算.通过对这种CBR检索算 法进行了深入的理论分析和认真的实验，结果证明，提出的算法是一个高效的算法.在这个检索算法的基础上，CBR 就能够应用到时序数据的分析推理中，具有广阔的应用前景. 关键词：基于范例的推理；时间序列数据；相似度比较 中图分类号：TP399文献标识码：A文章编号：1673-4785(2007)01-004005 A CBRalgorithm supporting time series data SHI Zhong-zhi',YIN Chao'2,YE Shi-wei? (1.Key Laboratory of Intelligent Information Processing,Institute of Computing Technology,Chinese Academy of Sciences, Beijing 100080,China:2.School of Information Science and Engineering Graduate University of Chinese Academy of Sciences, Beijing 100039,China) Abstract:This paper focuses on the retrieval algorithms of a special kind of CBR system in which cases are composed of time-series data.We introduced the classical algorithm used for processing similarity queries on time series data.This algorithm is based on the fact that DFT preserves the Euclidean distance in the time or frequency domain,and only the first few elements of the frequency sequence are significant,so the retrieval process can only use these significant elements to compute similarity degree.However,this algo- rithm has several disadvantages limiting its usage in CBR retrieval,so a new algorithm is presented for u sing batch method to compute the similarity degree.It is based on the observation that the original problem can be transformed to a convolution problem,and the circular convolution can be computed more efficiently using FFT.Theoretical analysis and experiment result prove that this algorithm is efficient and robust. The algorithm presented in this paper furnishes the CBR with the ability to process cases consist of time- series data. Key words :case-based reasoning;time series data;similarity comparison 基于范例的推理(case-based reasoning,CBR) 间信息的重要性，很多情况下，感兴趣的不仅仅是独 是实现人工智能的一种重要方法，它是对人类思维 立的快照(snapshot),而是一段连续的片段(epie 过程的模仿.CBR在如下情形下效果比较好：1)知 sode),甚至是对将来的预测.举个例子，在诊断病人 识的主要来源是经验，而不是理论；2)解决方案是可 的时候，医生不仅要了解患者目前的症状，也要了解 重用的：3)目标是求出可行解而非最优解.在过去的 其病史.医生对同样的症状最终可能会制订不同的 几年年里，CBR的研究者们已经逐渐开始注意到时 诊疗方案.最近这方面有代表性的研究包括文献[2 收稿日期：20060710. -3,16-17]等. 基金项目：国家自然科学基金资助项目(60435010,90604017， 文献[2-3]的研究都是建立在Aen在文献 60675010):国家“973”资助项目(2003CB317004). 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 一种支持时间序列数据的 CBR 检索算法 史忠植1 ,尹 超1 ,2 ,叶世伟2 (1. 中国科学院计算技术研究所 智能信息处理重点实验室 ,北京 100080 ;2. 中国科学院研究生院 信息科学与工程学院 ,北京 100039) 摘 要 :探讨了如何为 CBR(基于范例的推理)增加对一种特殊的范例类型 ———时间序列数据的支持. 分析了基于谱 分析的时间序列相似度比较算法不适用于 CBR 检索的缺点 ,并在此基础上设计了一种综合性能很好的 CBR 检索算 法. 思路是把时间序列相似度比较转化成一个卷积问题 ,并用 DFT 来简化这个卷积的计算. 通过对这种 CBR 检索算 法进行了深入的理论分析和认真的实验 ,结果证明 ,提出的算法是一个高效的算法. 在这个检索算法的基础上 ,CBR 就能够应用到时序数据的分析推理中 ,具有广阔的应用前景. 关键词 :基于范例的推理 ;时间序列数据 ;相似度比较 中图分类号 : TP399 文献标识码 :A 文章编号 :167324785 (2007) 0120040205 A CBR algorithm supporting time series data SHI Zhong2zhi 1 , YIN Chao 1 ,2 , YE Shi2wei 2 (1. Key Laboratory of Intelligent Information Processing , Institute of Computing Technology , Chinese Academy of Sciences , Beijing 100080 , China ;2. School of Information Science and Engineering Graduate University of Chinese Academy of Sciences , Beijing 100039 , China) Abstract :This paper focuses on the retrieval algorit hms of a special kind of CBR system in which cases are composed of time2series data. We introduced t he classical algorit hm used for processing similarity queries on time series data. This algorit hm is based on t he fact t hat DF T preserves t he Euclidean distance in t he time or frequency domain , and only the first few elements of t he frequency sequence are significant , so t he retrieval process can only use t hese significant elements to comp ute similarity degree. However , this algo2 rit hm has several disadvantages limiting its usage in CBR retrieval , so a new algorithm is presented for u2 sing batch met hod to comp ute t he similarity degree. It is based on the observation that t he original problem can be transformed to a convolution problem , and the circular convolution can be comp uted more efficiently using FF T. Theoretical analysis and experiment result prove t hat t his algorit hm is efficient and robust. The algorit hm presented in t his paper f urnishes the CBR with the ability to process cases consist of time2 series data. Keywords :case2based reasoning ; time series data ; similarity comparison 收稿日期 :2006207210. 基金项 目 : 国 家 自 然 科 学 基 金 资 助 项 目 ( 60435010 , 90604017 , 60675010) ;国家“973”资助项目(2003CB317004) . 基于范例的推理 (case2based reasoning ,CBR) 是实现人工智能的一种重要方法 ,它是对人类思维 过程的模仿. CBR 在如下情形下效果比较好 :1) 知 识的主要来源是经验 ,而不是理论 ;2) 解决方案是可 重用的 ;3) 目标是求出可行解而非最优解. 在过去的 几年年里 ,CBR 的研究者们已经逐渐开始注意到时 间信息的重要性 ,很多情况下 ,感兴趣的不仅仅是独 立的快照 (snap shot) ,而是一段连续的片段 ( epi2 sode) ,甚至是对将来的预测. 举个例子 ,在诊断病人 的时候 ,医生不仅要了解患者目前的症状 ,也要了解 其病史. 医生对同样的症状最终可能会制订不同的 诊疗方案. 最近这方面有代表性的研究包括文献[ 2 - 3 ,16 - 17 ]等. 文献[ 2 - 3 ]的研究都是建立在 Allen 在文献