區(qū)間映射規(guī)則下的時(shí)間序列相似形態(tài)搜索算法

董肖凱

摘要：時(shí)間序列數(shù)據(jù)是一種隨機(jī)過(guò)程，歷史的波動(dòng)趨勢(shì)在不同的時(shí)期看來(lái)往往似曾相似。本文使用用可解釋性的符號(hào)來(lái)刻畫時(shí)間序列變化形態(tài)，改進(jìn)了基于符號(hào)聚合相似的搜索模型，在原始搜索模型中引入改進(jìn)的參數(shù)優(yōu)化準(zhǔn)則HIC，并提供了將字符轉(zhuǎn)義為數(shù)值的變換方法，用于度量?jī)蓚€(gè)形態(tài)間的相似程度。結(jié)果表明，改進(jìn)的模型實(shí)現(xiàn)了字符、數(shù)值的相互轉(zhuǎn)化，且滿足距離下界原理；參數(shù)的優(yōu)化準(zhǔn)則穩(wěn)健的提高了模型的搜索精，有效的降低了算法復(fù)雜度。

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.

關(guān)鍵詞：時(shí)間序列；SAX算法；參數(shù)優(yōu)化準(zhǔn)則；形態(tài)相似度；穩(wěn)健性

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2018）03-0205-04

0 引言及綜述

時(shí)間序列數(shù)據(jù)本身是一種隨機(jī)過(guò)程，從數(shù)據(jù)變動(dòng)所反映的形態(tài)來(lái)看，歷史的波動(dòng)狀態(tài)在不同的時(shí)期看來(lái)往往似曾相識(shí)，而在細(xì)節(jié)上又有所差別。若能從這些變化著的數(shù)據(jù)中識(shí)別特定的變化趨勢(shì)，則便可利用這些蘊(yùn)含共同趨勢(shì)形態(tài)的序列片段，對(duì)數(shù)據(jù)進(jìn)行分類比較以及預(yù)測(cè)。

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

1 相似形態(tài)搜索模型構(gòu)建

分段符號(hào)聚合表示的方法是一種連續(xù)變量離散化的形態(tài)匹配算法，該算法將原始數(shù)據(jù)標(biāo)準(zhǔn)化后按正態(tài)分布的分位區(qū)間進(jìn)行壓縮編碼，壓縮后的代碼，縮短了移動(dòng)窗口的長(zhǎng)度，易于識(shí)別，同時(shí)降低了噪聲的影響，且保持了變化趨勢(shì)。然而該模型的缺點(diǎn)也顯而易見(jiàn)，主要包括模型對(duì)參數(shù)的過(guò)度依賴，相似形態(tài)距離定義的不明確等等。本文基于SAX模型的針對(duì)上述問(wèn)題提出了改進(jìn)方法，主要內(nèi)容涉及兩個(gè)方面：一是設(shè)定時(shí)間序列片段編碼的評(píng)估準(zhǔn)則，用以優(yōu)化參數(shù)；二是改進(jìn)不同編碼形態(tài)之間的相似性度量方式。

1.1 時(shí)間序列片段分段聚合符號(hào)化模型

該部分是本研究的基礎(chǔ)模型，以SAX算法為基礎(chǔ)，對(duì)時(shí)間序列進(jìn)行編碼。算法的主要步驟見(jiàn)下文：

①第一步：窗口內(nèi)時(shí)間序列片段線性表示。

設(shè)置等長(zhǎng)的時(shí)間序列片段窗口，用等寬度窗口分割時(shí)間序列，且步長(zhǎng)為1。每個(gè)窗口內(nèi)序列壓縮為更小的區(qū)間，并用區(qū)間平均值來(lái)表示，它的輸入?yún)?shù)為窗口長(zhǎng)度N，子區(qū)間長(zhǎng)度為n；

將標(biāo)準(zhǔn)正態(tài)分布取m個(gè)等分為點(diǎn)，則每?jī)蓚€(gè)分位點(diǎn)的區(qū)間對(duì)應(yīng)的概率相等，按分位點(diǎn)的大小，小到大對(duì)區(qū)間進(jìn)行命名，區(qū)間號(hào)即為編碼符號(hào)。

④第四步：子區(qū)間的均值進(jìn)行分為區(qū)間匹配。

時(shí)序窗口子區(qū)間的標(biāo)準(zhǔn)化均值的每個(gè)點(diǎn)在N（0，1）分布中對(duì)應(yīng)的區(qū)間，并將區(qū)間號(hào)設(shè)為每個(gè)子區(qū)間的編碼，即對(duì)時(shí)序窗口完成了編碼，將N長(zhǎng)的連續(xù)變量降為長(zhǎng)為n的離散字符。整個(gè)過(guò)程可表示為：winY→PAA→symbol（符號(hào)化）

第三步與第四步過(guò)程如圖1所示，序列片段按子區(qū)間平均化后，找到對(duì)應(yīng)在正態(tài)分布中的分為區(qū)間，按分為區(qū)間的位置，賦給該數(shù)值相應(yīng)的編碼。圖中相應(yīng)數(shù)據(jù)的編碼結(jié)果為“1-3-2-5-5”，整體上反映了時(shí)間序列片段波動(dòng)上升的趨勢(shì)。endprint

⑤第五步：等寬窗口移動(dòng)至包絡(luò)所有數(shù)據(jù)。

設(shè)置步長(zhǎng)，一般步長(zhǎng)設(shè)置為1，每次窗口內(nèi)數(shù)據(jù)編碼完后，窗口移動(dòng)一個(gè)時(shí)點(diǎn)，進(jìn)行下一輪數(shù)據(jù)編碼，重復(fù)步驟2至步驟4。

1.2 構(gòu)建模型參數(shù)優(yōu)化準(zhǔn)則

分段符號(hào)聚合表示的形態(tài)設(shè)定方式的參數(shù)簇為（N，n，m），其中N表示窗口長(zhǎng)度；n表示窗口子區(qū)間個(gè)數(shù)；m表示字符級(jí)別數(shù)目（分位區(qū)間數(shù)）。在給定N的情形下，n、m有多個(gè)選擇，每種選擇可能所映射的編碼空間都不一樣。為在給定窗口長(zhǎng)度N的前提下，選擇最優(yōu)的n和m，則需對(duì)編碼空間與原始序列空間的變換關(guān)系設(shè)置擬合標(biāo)準(zhǔn)以此進(jìn)行參數(shù)的選擇：

1.2.1 信息損失最小原則（經(jīng)驗(yàn)損失函數(shù)）

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

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

1.3 編碼形態(tài)相似度的衡量——定義符號(hào)化距離

對(duì)于不同的時(shí)間序列片段，每?jī)烧叨伎捎靡痪嚯x來(lái)衡量二者之間的相似程度，距離越小，序列之間越相似，反正則越不相似。

1.3.1 將原始時(shí)間序列片段投射至新的編碼空間進(jìn)行比較，可能會(huì)出現(xiàn)兩類錯(cuò)誤：

①原空間中不相似的形態(tài)，在編碼空間中會(huì)相似：即出現(xiàn)錯(cuò)誤判斷

②原空間中相似的形態(tài)，在編碼空間中不相似：即出現(xiàn)漏判

在相似搜索中，往往第二類漏判的錯(cuò)誤更為嚴(yán)重，為防止第二類錯(cuò)誤，需對(duì)不同形態(tài)之間距離的定義增加限定條件，即原始距離下界條件：

1.3.2 針對(duì)上述問(wèn)題，本文提供了一種將符號(hào)映射回連續(xù)數(shù)值的空間相似距離計(jì)算方法：

將各字符對(duì)應(yīng)到分位區(qū)間，并以分為區(qū)間的中點(diǎn)來(lái)數(shù)值化表示字符，則兩個(gè)編碼形態(tài)的距離即為相應(yīng)數(shù)值化變量的歐拉距離該過(guò)程為原始數(shù)據(jù)壓縮編碼的逆過(guò)程。

2 基于金融時(shí)間序列的實(shí)證分析

2.1 數(shù)據(jù)說(shuō)明

本研究選取證券市場(chǎng)中的滬深300指數(shù)作為數(shù)據(jù)源，從中截取2010年1月4日到2014年12月31日的日收盤價(jià)數(shù)據(jù)作為樣本。

2.2 基于HIC準(zhǔn)則的模型參數(shù)優(yōu)化過(guò)程

①以滬深300自2010年到2015年的日收盤價(jià)作為訓(xùn)練樣本，根據(jù)交易周期，每個(gè)月的交易日平均為20天，故窗口長(zhǎng)度取20。按N=20，設(shè)置滑動(dòng)窗口，取移動(dòng)步長(zhǎng)為1，對(duì)每個(gè)窗口內(nèi)的時(shí)間序列片段按SAX算法進(jìn)行壓縮編碼。

②每次壓縮設(shè)定（n，m），進(jìn)行循環(huán)，并統(tǒng)計(jì)所以窗口HIC值，以所以窗口的HIC均值作為（n，m）的返回值。

③設(shè)定n的取值范圍為5-10的整數(shù)，m的取值范圍為5-15的整數(shù)，進(jìn)行參數(shù)空間的遍歷。

若n或m選擇過(guò)小，則序列形態(tài)的設(shè)定將完全欠擬合，對(duì)形態(tài)之間的相似性度量將失去意義。本文選擇窗口子區(qū)間和字符級(jí)別的初始值為n=5，m=5。在窗口長(zhǎng)度N=20的條件下，進(jìn)行n和m的遍歷計(jì)算，每一對(duì)（n，m）的組合計(jì)算出所有窗口序列的HIC的平均值，以HIC的平均值來(lái)度量每對(duì)參數(shù)（n，m）下，模型的優(yōu)劣。

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

2.3 基于改進(jìn)模型的滬深300收盤價(jià)片段的相似形態(tài)搜索

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

②最優(yōu)參數(shù)下模型的評(píng)估結(jié)果：基于參數(shù)（N=20，n=6， m=10）優(yōu)化后的形態(tài)搜索圖：目標(biāo)序列為2016年11月7日到2016年12月5日共20天的滬深300指收盤價(jià)（圖中紅色序列）。搜索結(jié)果，最相近的5個(gè)序列見(jiàn)上圖。

由上圖可以看出，大體上模型的輸出結(jié)果保證了序列間的趨勢(shì)一致，且在部分細(xì)節(jié)上也呈現(xiàn)出較為一致的趨勢(shì)反轉(zhuǎn)。因?yàn)樗阉鹘Y(jié)果只涉及收盤價(jià)的形態(tài)。所以文本以標(biāo)準(zhǔn)化數(shù)值的平均誤差平方和來(lái)表征模型的輸出結(jié)果的評(píng)估：

3 結(jié)論

本文以分段符號(hào)聚合近似（SAX）基礎(chǔ)模型，結(jié)合信息損失最小原則與形態(tài)編碼自信息熵最小原則對(duì)模型參數(shù)空間的進(jìn)行局部縮小，參數(shù)選擇標(biāo)準(zhǔn)既考慮模型復(fù)雜度，又兼顧模型的擬合程度，既需防止欠擬合又要避免過(guò)度擬合，據(jù)此，本文給出了參數(shù)選擇標(biāo)準(zhǔn)HIC。結(jié)果表明，在原始搜索模型中引入?yún)?shù)優(yōu)化準(zhǔn)則后，模型的搜索精度顯著提升，且有效的降低了算法復(fù)雜度。在形態(tài)相似性衡量標(biāo)準(zhǔn)上，本文提供了將字符轉(zhuǎn)義為數(shù)值的方法，即將字符匹配到標(biāo)準(zhǔn)正態(tài)分布分位區(qū)間的中點(diǎn)，根據(jù)計(jì)算不同編碼序列對(duì)應(yīng)字符的距離平方和，來(lái)度量二者之間的相似程度。結(jié)果表明，該方法實(shí)現(xiàn)了字符、數(shù)值的相互轉(zhuǎn)化，且該相似度衡量標(biāo)準(zhǔn)與輸出序列之間的平均誤差平方和具有一致性，即滿足距離的下界原理。

參考文獻(xiàn)：

[1]Rakesh Agrawal， Christos Faloutsos， Arun Swami. Efficient similarity search in sequence database. AGRAWAL R，F(xiàn)ALOUTSOS 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