区间映射规则下的时间序列相似形态搜索算法

董肖凯

摘要：时间序列数据是一种随机过程，历史的波动趋势在不同的时期看来往往似曾相似。本文使用用可解释性的符号来刻画时间序列变化形态，改进了基于符号聚合相似的搜索模型，在原始搜索模型中引入改进的参数优化准则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