基于卷積的時(shí)態(tài)ＣＢＲ快速檢索算法及應(yīng)用

摘要:探討了如何增強(qiáng)CBR對(duì)一種常見的時(shí)態(tài)信息，即時(shí)間序列數(shù)據(jù)的檢索能力;分析了已有的基于傅里葉頻譜分析的時(shí)間序列檢索算法應(yīng)用于CBR時(shí)遇到的問題，并根據(jù)時(shí)態(tài)CBR檢索的需要，提出了一種新的基于循環(huán)卷積和傅里葉變換時(shí)間序列檢索算法。理論分析和數(shù)值實(shí)驗(yàn)結(jié)果都證明，提出的算法在檢索效率上有一定的優(yōu)勢(shì)。將采取這種檢索方法的時(shí)態(tài)CBR應(yīng)用于時(shí)間序列的預(yù)測(cè)問題中，取得了較好的預(yù)測(cè)效果且具有較高的預(yù)測(cè)效率。

關(guān)鍵詞:基于范例的推理; 時(shí)間序列數(shù)據(jù); 相似度比較

中圖分類號(hào):TP399文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001－3695(2008)02－0395－03

0引言

CBR是實(shí)現(xiàn)人工智能的一種重要方法，它是對(duì)人類思維過程的模仿。CBR在如下情形中效果比較好:知識(shí)的主要來源是經(jīng)驗(yàn)，而不是理論;解決方案是可重用的;目標(biāo)是求出可行解而非最優(yōu)解。

在過去的幾年里，CBR的研究者們已經(jīng)逐漸開始注意到時(shí)間信息的重要性。很多情況下，感興趣的不僅僅是獨(dú)立的快照(snapshot)，而是一段連續(xù)的片段(episode)，甚至是對(duì)將來的預(yù)測(cè)。例如在診斷病人時(shí)，醫(yī)生不僅要了解患者目前的癥狀，也要了解其病史，醫(yī)生對(duì)同樣的癥狀最終可能會(huì)制訂不同的診療方案。目前，這方面有代表性的研究包括文獻(xiàn)[1~4]。其中文獻(xiàn)[1，2]中的研究都是建立在Allen[5]提出的時(shí)態(tài)模型(temporal model)的基礎(chǔ)上。文獻(xiàn)[1]中提出了一種形式化邏輯方法來描述時(shí)序信息，從時(shí)序模型的觀點(diǎn)來看，這個(gè)工作特別有意義。因?yàn)槠浣⒌哪Ｐ椭腥诤狭嘶跁r(shí)間點(diǎn)和基于時(shí)間間隔的元素;然而作者卻沒有給出檢索算法，只是聲稱可以采用圖相似性算法來進(jìn)行相似度檢索。文獻(xiàn)[2]則是在一個(gè)具體的應(yīng)用項(xiàng)目的背景下，討論了如何在CBR中應(yīng)用Allen的模型。然而由于該應(yīng)用的一些特殊約束，解決方法并沒有普遍適用性。Allen的時(shí)態(tài)模型是基于間隔的，由于組合爆炸的緣故，這種模型只能處理一些簡(jiǎn)單的時(shí)序關(guān)系，而且相似性檢索的計(jì)算量很大，效果也并不十分好。文獻(xiàn)[3，4]引入的時(shí)態(tài)模型是基于時(shí)間序列數(shù)據(jù)的。時(shí)間序列的相似度比較是比較成熟的領(lǐng)域，有大量方法可以利用，如時(shí)間規(guī)整(DTW)#65380;符號(hào)化#65380;分段線性化#65380;特征抽取降維技術(shù)等。也正是因?yàn)檫@個(gè)原因，文獻(xiàn)[3，4]中沒有過多地涉及具體的檢索算法，而是側(cè)重于設(shè)計(jì)時(shí)間序列CBR的框架和范例的存儲(chǔ)結(jié)構(gòu)。經(jīng)過筆者的分析，CBR中的時(shí)間序列相似度具有很多特殊性，需要設(shè)計(jì)有針對(duì)性的檢索算法。

本文選擇采用的時(shí)序模型是時(shí)間序列數(shù)據(jù)，其著眼點(diǎn)不在于CBR的框架和范例的存儲(chǔ)結(jié)構(gòu)，而在于針對(duì)CBR中時(shí)間序列數(shù)據(jù)的特點(diǎn)，利用計(jì)算機(jī)在數(shù)值計(jì)算上的強(qiáng)大能力設(shè)計(jì)高效的CBR檢索算法。本文的研究不僅參考了CBR等人工智能領(lǐng)域的研究成果，也在很大程度上參考了時(shí)間序列數(shù)據(jù)領(lǐng)域的一些成果。

1支持時(shí)間序列的CBR模型

在推廣CBR時(shí)遇到的一個(gè)最大阻礙就是難以構(gòu)造有效的范例庫(kù)。CBR的應(yīng)用首先要求從客戶的歷史數(shù)據(jù)中抽取有代表性的數(shù)據(jù)構(gòu)造范例庫(kù)。這個(gè)過程不可能完全由機(jī)器完成，必須有人工參與進(jìn)來。所以要向CBR增加時(shí)間序列支持，首先考慮的就是方便范例庫(kù)的構(gòu)造。實(shí)際應(yīng)用中，用戶往往只能確定某一段時(shí)間內(nèi)的時(shí)間序列數(shù)據(jù)有特殊的含義，但并不能確定代表這種特殊含義的精確模式。在這種情況下，最妥當(dāng)?shù)姆椒ň褪前堰@一段連續(xù)時(shí)間序列整個(gè)作為一個(gè)范例存入范例庫(kù)中。

本文使用的表示符號(hào)如下:范例序列為C，其長(zhǎng)度均大于某個(gè)下限，元素表示為C[i];查詢序列為Q，其長(zhǎng)度均小于某個(gè)上限，元素可表示為Q[i](下文為了簡(jiǎn)潔起見有時(shí)表示為xt)。設(shè)len(C)=m，len(Q)=n，m≥n。每個(gè)范例序列C有m-n+1個(gè)長(zhǎng)度為n的子序列S，稱為時(shí)序范例。設(shè)范例庫(kù)中有N個(gè)范例序列，它們的長(zhǎng)度不一定相等。

基于CBR的應(yīng)用需要，范例庫(kù)中任意范例序列C的長(zhǎng)度m均大于查詢序列Q的長(zhǎng)度n。查詢過程中，需要用大小為n的滑動(dòng)窗口在C上截取出子序列S，計(jì)算S與查詢序列Q的相似度sim(Q，S)。相似度最大的幾個(gè)S作為查詢結(jié)果返回。這實(shí)際上是一個(gè)子序列匹配問題。

時(shí)間序列相似度模型對(duì)CBR的推理效果起著重要作用，常用的有基于歐氏距離#65380;基于時(shí)間歸整(dynamic time warping)#65380;基于界標(biāo)(landmark)#65380;基于最長(zhǎng)公共子序列(longest common subsequence)#65380;基于分段線性化表示和基于概率方法等。

出于減少計(jì)算量和誤警等考慮，本文使用了基于歐氏距離(式(1))的相似度模型，即把時(shí)間序列看成向量。定義相似度與歐氏距離成反比，即歐氏距離越小，則相似度越大。這也是時(shí)間序列數(shù)據(jù)處理中應(yīng)用最廣泛的相似度模型，但它與人類的認(rèn)知模型有一定的差異。因?yàn)橐恍┫嗨贫群艿?即歐氏距離很大)的序列對(duì)人類的感覺而言卻是相似的。

計(jì)算相似度的時(shí)間復(fù)雜度為Q(n)，對(duì)每個(gè)范例序列需要計(jì)算m-n+1次相似度。如果直接計(jì)算的話，對(duì)于大小為N的范例庫(kù)，一次查詢需要進(jìn)行N次時(shí)間復(fù)雜度為O(n(m-n+1))的比較。本文把這種直接計(jì)算的方法稱做naive方法，并作為比較各種算法效率的基準(zhǔn)。

2已有算法的分析

現(xiàn)在檢索時(shí)間序列數(shù)據(jù)最常用的是文獻(xiàn)[6，7]中提出的時(shí)間序列數(shù)據(jù)檢索算法，稱為Agrawal方法。這種方法的思路是采用傅里葉變換把所有截取的子序列S變換到頻域，通過從頻譜中選擇低頻分量或主分量實(shí)現(xiàn)降維，用選出的頻譜分量構(gòu)建多維索引結(jié)構(gòu)(如R樹等)。這樣由于DFT降維和多維索引的緣故，檢索時(shí)效率很高。但是如果將這種時(shí)序檢索算法照搬到CBR系統(tǒng)中，存在一些問題。

a)缺乏靈活性。結(jié)合CBR的具體應(yīng)用，顯然應(yīng)當(dāng)允許查詢序列的長(zhǎng)度可變。但是文獻(xiàn)[6，7]中事先計(jì)算譜變換序列的方法，在變換之前要求固定子序列S的長(zhǎng)度，這就限制了查詢序列Q的長(zhǎng)度，也就極大地限制了CBR的應(yīng)用范圍。

b)文獻(xiàn)[6，7]在譜變換系數(shù)中取k個(gè)主分量(即2k個(gè)實(shí)數(shù)作為索引)，建立維度為2k的高維索引結(jié)構(gòu)?？墒墙?jīng)過研究發(fā)現(xiàn)，所有的高維索引結(jié)構(gòu)，包括R－tree及其變種#65380;pyramid－tree#65380;空間填充曲線等，在高維情況下性能均退化到低于線性索引水平。而且為了減少索引結(jié)構(gòu)的規(guī)模，在建立高維索引過程中采取了很多近似手段，影響了查詢精度，不適用于某些精度要求非常高的應(yīng)用。

上述算法的核心思想是尋找時(shí)域運(yùn)算在頻域的等價(jià)計(jì)算方式，從中尋找優(yōu)化的可能。在此思想指導(dǎo)下，本文提出了另一種利用FFT簡(jiǎn)化基于歐氏距離的相似度計(jì)算的改進(jìn)方法。

3基于卷積的時(shí)態(tài)CBR快速檢索算法

5數(shù)值實(shí)驗(yàn)

本文取紐約證交所100個(gè)股票序列，每個(gè)序列大小在104數(shù)量級(jí)，構(gòu)造范例庫(kù)。實(shí)驗(yàn)程序在Linux(內(nèi)核版本2.6)上用C實(shí)現(xiàn)，編譯器是GCC 4.0，傅里葉變換用的是FFTW3數(shù)學(xué)庫(kù)。

根據(jù)數(shù)據(jù)的實(shí)際意義，有時(shí)需要先作一些預(yù)處理。比如對(duì)于股票價(jià)格序列，要調(diào)整數(shù)據(jù)以去除配股和分紅對(duì)價(jià)格序列的影響，使得各個(gè)不同時(shí)期的數(shù)據(jù)具有可比性。這點(diǎn)不予以詳述。使用第3章提出的算法對(duì)范例庫(kù)進(jìn)行檢索，實(shí)驗(yàn)結(jié)果如圖1所示。其中，縱坐標(biāo)表示10次不同的查詢所用時(shí)間，橫坐標(biāo)為查詢序列長(zhǎng)度(取對(duì)數(shù)坐標(biāo))。圖中查詢時(shí)間隨范例序列長(zhǎng)度n增長(zhǎng)最快的是naive方法;隨著查詢序列長(zhǎng)度的增長(zhǎng)，改進(jìn)方法的性能優(yōu)勢(shì)越來越明顯。實(shí)驗(yàn)結(jié)果驗(yàn)證了前文的分析，本文改進(jìn)方法在時(shí)間復(fù)雜度上的表現(xiàn)非常好。

使用第4章提出的預(yù)測(cè)算法，d1=60，d2=20的情況下，預(yù)測(cè)的平均誤差為2.43(歐氏距離)。部分預(yù)測(cè)結(jié)果如圖2所示。其中:實(shí)線為預(yù)測(cè)序列;虛線為真實(shí)的未來序列。從圖2可以看出，本文提出的基于卷積的檢索算法與這種基于CBR的預(yù)測(cè)方法相配合，取得了較好的預(yù)測(cè)效果。

6結(jié)束語

本文討論了如何增強(qiáng)CBR處理時(shí)間序列數(shù)據(jù)的能力。參考時(shí)間序列數(shù)據(jù)領(lǐng)域的研究成果，基于CBR的使用需要，本文設(shè)計(jì)了一種能夠很好地適應(yīng)CBR檢索需要的新的時(shí)間序列數(shù)據(jù)檢索算法。該算法用卷積的方法批處理計(jì)算相似度，并用FFT簡(jiǎn)化卷積的計(jì)算過程。理論分析和數(shù)值實(shí)驗(yàn)證明，該算法具有較低的時(shí)間復(fù)雜度。將這種快速檢索算法應(yīng)用于基于CBR的時(shí)間序列預(yù)測(cè)當(dāng)中，取得了較好的預(yù)測(cè)效果，進(jìn)一步驗(yàn)證了它的有效性。下一步工作是結(jié)合CBR在時(shí)間序列數(shù)據(jù)方面的具體應(yīng)用，研究時(shí)間序列數(shù)據(jù)對(duì)CBR其他模塊提出的新的要求，如范例庫(kù)維護(hù)等。

參考文獻(xiàn):

[1]MA Ji－xin， KNIGHT B. A framework for historical case－based reaso－ning[C]//Lecture Notes in Computer Science. Berlin: Springer， 2003:1067.

[2]JAERE M D， AAMODT A， SKALLE P. Representing temporal knowledge for case－based prediction[C]//Proc of the 6th European Conference on Advances in Case－based Reasoning.London:Springer－Verlag， 2002.

[3]MONTANI S， PORTINALE L. Case－based representation and retrie－val with time dependent features[C]//Proc of Lecture Notes in Computer Science. Berlin: Springer， 2005:253－367.

[4]SANCHEZ－MARRE M， CORTES U. An approach for temporal case－based reasoning: Episode－based reasoning[C]//Lecture Notes in Computer Science.Berlin:Springer，2005:465－476.

[5]ALLEN J F. Maintaining knowledge about temporal intervals[J]. Communications of the ACM， 1983，26(11):832－843.

[6]AGRAWAL R， FALOUTSOS C， SWAMI A. Efficient similarity search in sequence database[C]//Proc of the 4th International Conference on Foundation of Data Organization and Algorithms. London: Springer－Verlag， 1993:69－84.

[7]FALOUTSOS C， RANGANATHAN M， MANOLOPOULOS Y. Fast subsequence matching in time－series database[C]//Proc of ACM SIGMOD Int’l Conference on Management of Data. New York: ACM Press， 1994.

[8]吳鎮(zhèn)揚(yáng).數(shù)字信號(hào)處理[M].北京:高等教育出版社，2004.

[9]BRACEWELL R. The fourier transform and its applications[M].[S.l.]: McGraw－Hill，2000.

[10]葉世偉，鄭宏偉，王文杰，等.非線性梯度下降算法理論及其對(duì)Hopfield網(wǎng)絡(luò)穩(wěn)定性的分析[J].計(jì)算機(jī)研究與發(fā)展，2004，41(2):317－324.

[11]AAMODT A， PLAZA E. Case－based reasoning: foundational issues， methodological variations， and system approaches[J]. AI Communications， 1994，7(1):39－59.

[12]GUTTMAN A. R－trees: a dynamic index structure for spatial sear－ching[C]//Proc of ACM SIGMOD Int’l Conference on Management of Data. New York: ACM Press， 1984.

[13]BERCHTOLOD S， BOHM C， KRIEGEL H. The pyramid－technique: towards breaking the curse of dimensionality[J]. ACM SIGMOD Record， 1998，27(2):142－153.

[14]FALOUTSOS C， ROSEMAN S. Fractals for secondary key retrieval， UMIACS－TR－89－47， CS－TR－2242[R]. Maryland: University of Maryland， 1989.

[15]BOHM C， BERCHTOLD S， KEIM D. Searching in high－dimensional spaces－index structures for improving the performance of multimedia databases[J]. ACM Computing Surveys， 2001，33(3):322－373.

[16]GAEDE V，GUNTHER O.Multidimensional access method[J].ACM Computing Surveys， 1998，30(2):221－290.

[17]史忠植.高級(jí)人工智能[M].2版.北京:科學(xué)出版社，2006.

[18]HAYKIN S.神經(jīng)網(wǎng)絡(luò)原理[M].葉世偉，史忠植，譯.北京:機(jī)械工業(yè)出版社，2004.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”