·44 智能系统学报 第2卷 图中查询时间随范例序列长度n增长最快的是na Maryland,1989 ive方法，随着查询序列长度的增长，改进方法性能 [10]BOHM C,BERCHTOLD S,KEIM D.Searching in 优势越来越明显.试验结果验证了我们前文的分析， high-dimensional spaces-index structures for improving 改进方法在时间复杂度上的表现非常好 the performance of multimedia databases[J ]ACM Com- puting Surveys,2001,33(3):322-373. 5结束语 [11 GA EDE V,GUNTHER O.Multidimensional access method[J ]ACM Computing Surveys,1998,30(2):221 文中讨论了如何为CBR增加处理时间序列数 .290. 据的能力，参考时间序列数据领域的研究成果，基于 [12]BRACEWELL R.The fourier transform and its appli- CBR的使用需要，我们设计了一种新的时间序列数 cations[M].Mc Graw-Hill,2000. 据检索算法应用于CBR.整个算法基于己有时间序 [13]史忠植.高级人工智能：第二版[M].北京：科学出版 列数据相似度匹配算法的核心思想，用卷积的方法 一社.2006. 批处理计算相似度，并用FFT简化卷积的计算过 [14]HA YKIN S,叶世伟，史忠植.神经网络原理[Ml.北 程，不仅保持了较低的时间复杂度，也增加了查询时 京：机械工业出版社，2004 的灵活性，方便了CBR的应用.我们的下一步工作 [15]吴镇扬.数字信号处理[M].北京：高等教育出版社， 2004. 是结合CBR在时间序列数据方面的具体应用，研究 [16 ]MONTANI S,PORTINALEL.Case based representa- 时间序列数据，对CBR的其他模块提出的新的要 tion and retrieval with time dependent features[A ]IC- 求，比如范例库维护等 CBR 2005[C].Chicago,IL,USA,2005. 参考文献： [17]SANCHEZ MM,CORTES U.An approach for tem- poral case-based reasoning:episode-based reasoning[A]. [1]AAMODT A,PLAZA E.Case based reasoning:founda- ICCBR 2005[C].Chicago,IL,USA,2005. tional issues,methodological variations,and system ap- 作者简介： proaches[J ]AI Communications,1994(7):56-72. 史忠植，男，1941年生，中国科学院 [2]MA J,KNIGHT B.A Framework for Historical Case- 计算所主任研究员，博士生导师.EEE Based Reasoning [A ]ICCBR 2003 [C].Trondheim, 高级会员.主要研究领域为智能科学、分 Norway,2003. 布智能、机器学习、知识工程等.1979 [3JAERE M D,AAMODT A,SKALL E P.Representing 年、1998年2001年均获中国科学院科 temporal knowledge for case-based prediction [A ]EC- 技进步二等奖，1994年获中国科学院科 CBR 2002[C].Aberdeen,Scotland,UK,2002. 技进步特等奖，2002年获国家科技进步 [4 ]ALL EN J F.Maintaining knowledge about temporal in- 二等奖 tervals[J].Communications of the ACM 1983,26(11): Email shizz @ics.ict.ac.cn. 832.843. (5]AGRAWAL R,FALOU TSOS C,SWAMI A.Efficient 尹超，男，1979年生，硕士研究生， similarity search in sequence database [A ]FODO Con- 主要研究方向为智能信息处理，基于范 ference[C].Evanston,Ilinois,1993. 例的推理技术。 [6]FALOUTSOS C,RANGANATHAN M,MANOLO- Email yinchao04 @mails.gucas.ac. POULOS Y.Fast subsequence matching in time-series database[A].Proc of the ACM SIGMOD[C].Minneap- olis,Minnesota,1994. [7]GUTTMAN A.R-trees:a dynamic index structure for spatial searching[A].Proceedings of the ACM SIGMOD 叶世伟男，1968年生，博士，副教 [C].Boston,MA,1984. 授.中国科学院研究生院信息科学与工 [8]BERCHTOLD S.,BOHM C,KRIEGEL H.The pyra 程学院；主要研方向为智能信息处理、神 mid-technique:towards breaking the curse of dimension 经计算与优化计算、认知科学等方面，在 ality[A].Proceedings of SIGMOD'98 [C].Seattle, 国内外重要刊物上发表论文20余篇」 Washington,USA,1998. [9]FALOU TSOS C,ROSEMAN S.Fractals for secondary key retrieval[R].Technical Report UMIACS-TR-89-47, CS-TR-2242,University of Maryland,College Park, 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net图中查询时间随范例序列长度 n 增长最快的是 na2 ive 方法 ,随着查询序列长度的增长 ,改进方法性能 优势越来越明显. 试验结果验证了我们前文的分析 , 改进方法在时间复杂度上的表现非常好. 5 结束语 文中讨论了如何为 CBR 增加处理时间序列数 据的能力 ,参考时间序列数据领域的研究成果 ,基于 CBR 的使用需要 ,我们设计了一种新的时间序列数 据检索算法应用于 CBR. 整个算法基于已有时间序 列数据相似度匹配算法的核心思想 ,用卷积的方法 批处理计算相似度 ,并用 FF T 简化卷积的计算过 程 ,不仅保持了较低的时间复杂度 ,也增加了查询时 的灵活性 ,方便了 CBR 的应用. 我们的下一步工作 是结合 CBR 在时间序列数据方面的具体应用 ,研究 时间序列数据 ,对 CBR 的其他模块提出的新的要 求 ,比如范例库维护等. 参考文献 : [1 ]AAMODT A ,PLAZA E. Case2based reasoning : founda2 tional issues , methodological variations , and system ap2 proaches[J ]. AI Communications , 1994 (7) :56 - 72. [2 ]MA J , KNIGH T B. A Framework for Historical Case - Based Reasoning [ A ]. ICCBR 2003 [ C ]. Trondheim , Norway , 2003. [3 ]J AERE M D , AAMODT A , SKALL E P. Representing temporal knowledge for case2based prediction [ A ]. EC2 CBR 2002[C]. Aberdeen , Scotland , U K , 2002. [4 ]ALL EN J F. Maintaining knowledge about temporal in2 tervals[J ]. Communications of the ACM 1983 , 26 (11) : 832 - 843. [5 ] A GRAWAL R , FALOU TSOS C , SWAMI A. Efficient similarity search in sequence database [ A ]. FODO Con2 ference[C]. Evanston , Illinois , 1993. [6 ] FALOU TSOS C , RAN GANA THAN M , MANOLO2 POULOS Y. Fast subsequence matching in time2series database[ A ]. Proc of the ACM SIGMOD[C]. Minneap2 olis , Minnesota , 1994. [7 ] GU TTMAN A. R2trees: a dynamic index structure for spatial searching[ A ]. Proceedings of the ACM SIGMOD [C]. Boston , MA , 1984. [8 ]BERCH TOLD S. , BO HM C , KRIEGEL H. The pyra2 mid2technique : towards breaking the curse of dimension2 ality [ A ]. Proceedings of SIGMOD’98 [ C ]. Seattle , Washington , USA , 1998. [9 ] FALOU TSOS C ,ROSEMAN S. Fractals for secondary key retrieval[ R]. Technical Report UMIACS2TR289247 , CS2TR22242 , University of Maryland , College Park , Maryland , 1989. [10 ] BO HM C , BERCH TOLD S , KEIM D. Searching in high - dimensional spaces2index structures for improving the performance of multimedia databases[J ]. ACM Com2 puting Surveys ,2001 , 33 (3) : 322 - 373. [ 11 ] GA EDE V , GUN THER O. Multidimensional access method[J ]. ACM Computing Surveys , 1998 , 30 (2) :221 - 290. [12 ]BRACEWELL R. The fourier transform and its appli2 cations[ M]. Mc Graw2Hill , 2000. [13 ]史忠植. 高级人工智能 :第二版[ M ]. 北京 :科学出版 社 , 2006. [14 ] HA YKIN S , 叶世伟 , 史忠植. 神经网络原理[ M ]. 北 京 :机械工业出版社 , 2004 [15 ]吴镇扬. 数字信号处理 [ M ]. 北京 :高等教育出版社 , 2004. [16 ]MON TANI S ,PORTINAL E L. Case based representa2 tion and retrieval with time dependent features[ A ]. IC2 CBR 2005[C]. Chicago , IL , USA , 2005. [17 ] SANCHEZ M M , CORTES U. An approach for tem2 poral case2based reasoning : episode2based reasoning[A ]. ICCBR 2005[C]. Chicago , IL , USA , 2005. 作者简介 : 史忠植 , 男 ,1941 年生 ,中国科学院 计算所主任研究员 ,博士生导师. IEEE 高级会员. 主要研究领域为智能科学、分 布智能、机器学习、知识工程等. 1979 年、1998 年、2001 年均获中国科学院科 技进步二等奖 ,1994 年获中国科学院科 技进步特等奖 ,2002 年获国家科技进步 二等奖. Email :shizz @ics. ict. ac. cn. 尹 超 ,男 ,1979 年生 ,硕士研究生 , 主要研究方向为智能信息处理 ,基于范 例的推理技术. E2mail :yinchao04 @mails. gucas. ac. cn. 叶世伟 男 , 1968 年生 ,博士 ,副教 授. 中国科学院研究生院信息科学与工 程学院 ;主要研方向为智能信息处理、神 经计算与优化计算、认知科学等方面 ,在 国内外重要刊物上发表论文 20 余篇. · 44 · 智 能 系 统 学 报 第 2 卷