區間映射規則下的時間序列相似形態搜索算法

董肖凱

摘要：時間序列數據是一種隨機過程，歷史的波動趨勢在不同的時期看來往往似曾相似。本文使用用可解釋性的符號來刻畫時間序列變化形態，改進了基于符號聚合相似的搜索模型，在原始搜索模型中引入改進的參數優化準則HIC，并提供了將字符轉義為數值的變換方法，用于度量兩個形態間的相似程度。結果表明，改進的模型實現了字符、數值的相互轉化，且滿足距離下界原理；參數的優化準則穩健的提高了模型的搜索精，有效的降低了算法復雜度。

Abstract： Time series data is a kind of stochastic process. The trend of historical volatility seems to be similar in different periods. In this paper， we use interpretive symbols to depict the time series variation， improve the similar search model based on symbolic aggregation， introduce the improved parameter optimization criterion HIC into the original search model， and provide the transformation method of translating characters into numerical values， to measure the similarity between the two forms. The results show that the improved model realizes the mutual transformation of characters and values and satisfies the lower bound principle of distance. The optimization criterion of parameters steadily improves the searching precision of the model and reduces the complexity of the algorithm effectively.

關鍵詞：時間序列；SAX算法；參數優化準則；形態相似度；穩健性

Key words： time series；SAX algorithm； parameter optimization criteria；morphological similarity；robustness

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1006-4311（2018）03-0205-04

0 引言及綜述

時間序列數據本身是一種隨機過程，從數據變動所反映的形態來看，歷史的波動狀態在不同的時期看來往往似曾相識，而在細節上又有所差別。若能從這些變化著的數據中識別特定的變化趨勢，則便可利用這些蘊含共同趨勢形態的序列片段，對數據進行分類比較以及預測。

對時間序列形態搜索的研究可追述至上世紀90年代。1993年Rakesh Agrawal等人[1]首次提出了一種使用離散傅里葉變換（DFT）處理時間序列的相似性索引方法，通過離散傅里葉變換（DFT）將時間序列映射到到較低維空間。隨后，C.Faloutsos等人[2]于1994年提出在時間序列數據上使用滑動窗口并提取其特征，將每個數據序列片段映射到特征空間中，通過對這些特征的比對，迅速找到與給定（查詢）模式相匹配的子序列。這兩篇文章開啟了時間序列相似性搜索的研究熱潮。Eamonn Keogh[3]提出了一種基于均勻縮放條件下特征符號化表示的新方法，以實現快速相似序列搜索。Lin等人[5]提出的時間序列符號化聚合近似（SAX），是一種基于分段聚合近似的符號表示方法。Wei和Xi等人[6]提出利用符號聚合近似（SAX）的方法將一些關于物體形狀數據轉化為時間序列，通過符號化的表示，進行異常序列模式的發現與識別。

1 相似形態搜索模型構建

分段符號聚合表示的方法是一種連續變量離散化的形態匹配算法，該算法將原始數據標準化后按正態分布的分位區間進行壓縮編碼，壓縮后的代碼，縮短了移動窗口的長度，易于識別，同時降低了噪聲的影響，且保持了變化趨勢。然而該模型的缺點也顯而易見，主要包括模型對參數的過度依賴，相似形態距離定義的不明確等等。本文基于SAX模型的針對上述問題提出了改進方法，主要內容涉及兩個方面：一是設定時間序列片段編碼的評估準則，用以優化參數；二是改進不同編碼形態之間的相似性度量方式。

1.1 時間序列片段分段聚合符號化模型

該部分是本研究的基礎模型，以SAX算法為基礎，對時間序列進行編碼。算法的主要步驟見下文：

①第一步：窗口內時間序列片段線性表示。

設置等長的時間序列片段窗口，用等寬度窗口分割時間序列，且步長為1。每個窗口內序列壓縮為更小的區間，并用區間平均值來表示，它的輸入參數為窗口長度N，子區間長度為n；

將標準正態分布取m個等分為點，則每兩個分位點的區間對應的概率相等，按分位點的大小，小到大對區間進行命名，區間號即為編碼符號。

④第四步：子區間的均值進行分為區間匹配。

時序窗口子區間的標準化均值的每個點在N（0，1）分布中對應的區間，并將區間號設為每個子區間的編碼，即對時序窗口完成了編碼，將N長的連續變量降為長為n的離散字符。整個過程可表示為：winY→PAA→symbol（符號化）

第三步與第四步過程如圖1所示，序列片段按子區間平均化后，找到對應在正態分布中的分為區間，按分為區間的位置，賦給該數值相應的編碼。圖中相應數據的編碼結果為“1-3-2-5-5”，整體上反映了時間序列片段波動上升的趨勢。endprint

⑤第五步：等寬窗口移動至包絡所有數據。

設置步長，一般步長設置為1，每次窗口內數據編碼完后，窗口移動一個時點，進行下一輪數據編碼，重復步驟2至步驟4。

1.2 構建模型參數優化準則

分段符號聚合表示的形態設定方式的參數簇為（N，n，m），其中N表示窗口長度；n表示窗口子區間個數；m表示字符級別數目（分位區間數）。在給定N的情形下，n、m有多個選擇，每種選擇可能所映射的編碼空間都不一樣。為在給定窗口長度N的前提下，選擇最優的n和m，則需對編碼空間與原始序列空間的變換關系設置擬合標準以此進行參數的選擇：

1.2.1 信息損失最小原則（經驗損失函數）

對于模型的參數簇，在給定窗口N的前提下，序列編碼后信息損失的度量，為參數n和m的優化提供了可能。本文用均值方差（MSE）來衡量相對信息損失程度。

編碼信息損失準則HIC越小則表示模型整體效果越穩健。從該指標的表達式可以看出，一方面將編碼后模型的復雜度考慮其中，若模型參數越大，模型越復雜，則HIC的第一項H（S）的比重將增大；另一方面改準則也考慮了模型的擬合程度，若模型參數越小，則模型越欠擬合，HIC中的第二項I（S，X）將會增大。故該指標綜合反映了模型復雜度與模型信息損失的等因素。

1.3 編碼形態相似度的衡量——定義符號化距離

對于不同的時間序列片段，每兩者都可用一距離來衡量二者之間的相似程度，距離越小，序列之間越相似，反正則越不相似。

1.3.1 將原始時間序列片段投射至新的編碼空間進行比較，可能會出現兩類錯誤：

①原空間中不相似的形態，在編碼空間中會相似：即出現錯誤判斷

②原空間中相似的形態，在編碼空間中不相似：即出現漏判

在相似搜索中，往往第二類漏判的錯誤更為嚴重，為防止第二類錯誤，需對不同形態之間距離的定義增加限定條件，即原始距離下界條件：

1.3.2 針對上述問題，本文提供了一種將符號映射回連續數值的空間相似距離計算方法：

將各字符對應到分位區間，并以分為區間的中點來數值化表示字符，則兩個編碼形態的距離即為相應數值化變量的歐拉距離該過程為原始數據壓縮編碼的逆過程。

2 基于金融時間序列的實證分析

2.1 數據說明

本研究選取證券市場中的滬深300指數作為數據源，從中截取2010年1月4日到2014年12月31日的日收盤價數據作為樣本。

2.2 基于HIC準則的模型參數優化過程

①以滬深300自2010年到2015年的日收盤價作為訓練樣本，根據交易周期，每個月的交易日平均為20天，故窗口長度取20。按N=20，設置滑動窗口，取移動步長為1，對每個窗口內的時間序列片段按SAX算法進行壓縮編碼。

②每次壓縮設定（n，m），進行循環，并統計所以窗口HIC值，以所以窗口的HIC均值作為（n，m）的返回值。

③設定n的取值范圍為5-10的整數，m的取值范圍為5-15的整數，進行參數空間的遍歷。

若n或m選擇過小，則序列形態的設定將完全欠擬合，對形態之間的相似性度量將失去意義。本文選擇窗口子區間和字符級別的初始值為n=5，m=5。在窗口長度N=20的條件下，進行n和m的遍歷計算，每一對（n，m）的組合計算出所有窗口序列的HIC的平均值，以HIC的平均值來度量每對參數（n，m）下，模型的優劣。

圖為參數（n，m）空間下的HIC均值散點圖，水平面由子區間個數n（5-10的整數）和字符級別數m（5-15的整數）構成，縱軸表示每個參數簇（n，m）下所對應的HIC均值。從圖中可以看出，在n給定的情形下，隨著m的增加，IIC均值先減小后增加呈現“U”形特征，這與編碼的信息損失與編碼復雜度之間的關系是吻合的。在窗口長度為N=20的前提下，（n=6，m=10）時的HIC均值最小為3.17。故針對2010年到2015年的滬深300日收盤價進行形態設定（以20日為一周期），可能的最優的參數為（N=20，n=6，m=15）。

2.3 基于改進模型的滬深300收盤價片段的相似形態搜索

①驗證方式：以2010年到2015年的滬深300收盤價為樣本的參數訓練結果是（N=20，n=6，m=10），在該參數下，任意選擇樣本時間之外的20日收盤價為測試序列，從2010年到2015年的收盤價里搜索與測試序列最相似的前五序列片段，并輸出起始時間和形態編碼，輸出結果見圖3。

②最優參數下模型的評估結果：基于參數（N=20，n=6， m=10）優化后的形態搜索圖：目標序列為2016年11月7日到2016年12月5日共20天的滬深300指收盤價（圖中紅色序列）。搜索結果，最相近的5個序列見上圖。

由上圖可以看出，大體上模型的輸出結果保證了序列間的趨勢一致，且在部分細節上也呈現出較為一致的趨勢反轉。因為搜索結果只涉及收盤價的形態。所以文本以標準化數值的平均誤差平方和來表征模型的輸出結果的評估：

3 結論

本文以分段符號聚合近似（SAX）基礎模型，結合信息損失最小原則與形態編碼自信息熵最小原則對模型參數空間的進行局部縮小，參數選擇標準既考慮模型復雜度，又兼顧模型的擬合程度，既需防止欠擬合又要避免過度擬合，據此，本文給出了參數選擇標準HIC。結果表明，在原始搜索模型中引入參數優化準則后，模型的搜索精度顯著提升，且有效的降低了算法復雜度。在形態相似性衡量標準上，本文提供了將字符轉義為數值的方法，即將字符匹配到標準正態分布分位區間的中點，根據計算不同編碼序列對應字符的距離平方和，來度量二者之間的相似程度。結果表明，該方法實現了字符、數值的相互轉化，且該相似度衡量標準與輸出序列之間的平均誤差平方和具有一致性，即滿足距離的下界原理。

參考文獻：

[1]Rakesh Agrawal， Christos Faloutsos， Arun Swami. Efficient similarity search in sequence database. AGRAWAL R，FALOUTSOS C，SWAMI A. Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithm. 1993，（730）：69-84.

[2]Christos Faloutsos， M.Ranganathan， Yannis Manolopoulos. Fast Subsequence Matching in Time-Series Databases. Acm Sigmod Record，1994，23 （2） ：419-429.

[3]SL Lee ，SJ Chun ，DH Kim ，JH Lee ，CW Chung. Similarity Search for Multidimensional Data Sequences. International Conference on Data Engineering ， 2000 ：599-608.

[4]E Keogh. Efficiently Finding Arbitrarily Scaled Patterns in Massive Time Series Databases. European Conference on Knowledge Discovery in Discovery ， 2003 ， （2838） ：253-265.

[5]Jessica Lin， Eamonn Keogh， Li Wei， Stefano Lonardi. Experiencing SAX： a novel symbolic representation of time series. Data Mining Knowledge Discovery ，2007， （15）： 107-144.endprint