基于卷積的時態ＣＢＲ快速檢索算法及應用

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

關鍵詞:基于范例的推理; 時間序列數據; 相似度比較

中圖分類號:TP399文獻標志碼:A

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

0引言

CBR是實現人工智能的一種重要方法，它是對人類思維過程的模仿。CBR在如下情形中效果比較好:知識的主要來源是經驗，而不是理論;解決方案是可重用的;目標是求出可行解而非最優解。

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

本文選擇采用的時序模型是時間序列數據，其著眼點不在于CBR的框架和范例的存儲結構，而在于針對CBR中時間序列數據的特點，利用計算機在數值計算上的強大能力設計高效的CBR檢索算法。本文的研究不僅參考了CBR等人工智能領域的研究成果，也在很大程度上參考了時間序列數據領域的一些成果。

1支持時間序列的CBR模型

在推廣CBR時遇到的一個最大阻礙就是難以構造有效的范例庫。CBR的應用首先要求從客戶的歷史數據中抽取有代表性的數據構造范例庫。這個過程不可能完全由機器完成，必須有人工參與進來。所以要向CBR增加時間序列支持，首先考慮的就是方便范例庫的構造。實際應用中，用戶往往只能確定某一段時間內的時間序列數據有特殊的含義，但并不能確定代表這種特殊含義的精確模式。在這種情況下，最妥當的方法就是把這一段連續時間序列整個作為一個范例存入范例庫中。

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

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

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

出于減少計算量和誤警等考慮，本文使用了基于歐氏距離(式(1))的相似度模型，即把時間序列看成向量。定義相似度與歐氏距離成反比，即歐氏距離越小，則相似度越大。這也是時間序列數據處理中應用最廣泛的相似度模型，但它與人類的認知模型有一定的差異。因為一些相似度很低(即歐氏距離很大)的序列對人類的感覺而言卻是相似的。

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

2已有算法的分析

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

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

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

上述算法的核心思想是尋找時域運算在頻域的等價計算方式，從中尋找優化的可能。在此思想指導下，本文提出了另一種利用FFT簡化基于歐氏距離的相似度計算的改進方法。

3基于卷積的時態CBR快速檢索算法

5數值實驗

本文取紐約證交所100個股票序列，每個序列大小在104數量級，構造范例庫。實驗程序在Linux(內核版本2.6)上用C實現，編譯器是GCC 4.0，傅里葉變換用的是FFTW3數學庫。

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

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

6結束語

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

參考文獻:

[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]吳鎮揚.數字信號處理[M].北京:高等教育出版社，2004.

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

[10]葉世偉，鄭宏偉，王文杰，等.非線性梯度下降算法理論及其對Hopfield網絡穩定性的分析[J].計算機研究與發展，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]史忠植.高級人工智能[M].2版.北京:科學出版社，2006.

[18]HAYKIN S.神經網絡原理[M].葉世偉，史忠植，譯.北京:機械工業出版社，2004.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”