《区间映射规则下的时间序列相似形态搜索算法——基于改进的正则化损失函数》由会员分享，可在线阅读，更多相关《区间映射规则下的时间序列相似形态搜索算法——基于改进的正则化损失函数（8页珍藏版）》请在金锄头文库上搜索。
1、区间映射规则下的时间序列相似形态搜索算法基于改进的正则化损失函数 董肖凯 方宏舰 周波 南京财经大学 摘 要： 时间序列数据是一种随机过程, 历史的波动趋势在不同的时期看来往往似曾相似。本文使用用可解释性的符号来刻画时间序列变化形态, 改进了基于符号聚合相似的搜索模型, 在原始搜索模型中引入改进的参数优化准则 HIC, 并提供了将字符转义为数值的变换方法, 用于度量两个形态间的相似程度。结果表明, 改进的模型实现了字符、数值的相互转化, 且满足距离下界原理;参数的优化准则稳健的提高了模型的搜索精, 有效的降低了算法复杂度。关键词： 时间序列; SAX算法; 参数优化准则; 形态相似度; 稳健性
2、; 作者简介：董肖凯 (1991-) , 男, 安徽宣城人, 硕士研究生, 硕士, 研究方向为计量经济理论与应用;作者简介：周波 (通讯作者) (1993-) , 男, 安徽芜湖人, 硕士研究生, 研究方向为资源与环境经济学。Time Series Similar Morphology Search Algorithm under Interval Mapping Rules:Based on Improved Regularization Loss FunctionDONG Xiao-kai FANG Hong-jian ZHOU Bo Nanjing University of Finan
3、ce 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 impr
4、oved 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 a
5、nd 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.Keyword： time series; SAX algorithm; parameter optimization criteria; morphological si
6、milarity; robustness; 0引言及综述时间序列数据本身是一种随机过程, 从数据变动所反映的形态来看, 历史的波动状态在不同的时期看来往往似曾相识, 而在细节上又有所差别。若能从这些变化着的数据中识别特定的变化趋势, 则便可利用这些蕴含共同趋势形态的序列片段, 对数据进行分类比较以及预测。对时间序列形态搜索的研究可追述至上世纪 90年代。1993 年 Rakesh Agrawal等人1首次提出了一种使用离散傅里叶变换 (DFT) 处理时间序列的相似性索引方法, 通过离散傅里叶变换 (DFT) 将时间序列映射到到较低维空间。随后, C.Faloutsos等人2于 1994年提出在
7、时间序列数据上使用滑动窗口并提取其特征, 将每个数据序列片段映射到特征空间中, 通过对这些特征的比对, 迅速找到与给定 (查询) 模式相匹配的子序列。这两篇文章开启了时间序列相似性搜索的研究热潮。Eamonn Keogh3提出了一种基于均匀缩放条件下特征符号化表示的新方法, 以实现快速相似序列搜索。Lin 等人5提出的时间序列符号化聚合近似 (SAX) , 是一种基于分段聚合近似的符号表示方法。Wei 和 Xi等人6提出利用符号聚合近似 (SAX) 的方法将一些关于物体形状数据转化为时间序列, 通过符号化的表示, 进行异常序列模式的发现与识别。1 相似形态搜索模型构建分段符号聚合表示的方法是一
8、种连续变量离散化的形态匹配算法, 该算法将原始数据标准化后按正态分布的分位区间进行压缩编码, 压缩后的代码, 缩短了移动窗口的长度, 易于识别, 同时降低了噪声的影响, 且保持了变化趋势。然而该模型的缺点也显而易见, 主要包括模型对参数的过度依赖, 相似形态距离定义的不明确等等。本文基于 SAX模型的针对上述问题提出了改进方法, 主要内容涉及两个方面:一是设定时间序列片段编码的评估准则, 用以优化参数;二是改进不同编码形态之间的相似性度量方式。1.1 时间序列片段分段聚合符号化模型该部分是本研究的基础模型, 以 SAX算法为基础, 对时间序列进行编码。算法的主要步骤见下文:(1) 第一步:窗口
9、内时间序列片段线性表示。设置等长的时间序列片段窗口, 用等宽度窗口分割时间序列, 且步长为 1。每个窗口内序列压缩为更小的区间, 并用区间平均值来表示, 它的输入参数为窗口长度 N, 子区间长度为 n;其中:Z ti表示子区间平均数的序列;Y 表示原始时间序列样本;win Y 表示单位窗口内时间序列片段;PAA 表示时间序列片段分段平均后的新序列。(2) 第二步:时序窗口内数据标准化取均值。先将窗口内的数据先进行 z-标准化, 这样即将一个长度为 N的时序片段压缩为长度为 n的标准化的数据片段。其中:z tiN (0, 1) (3) 第三步:基于正态分布的分为点设置字符。将标准正态分布取 m个
10、等分为点, 则每两个分位点的区间对应的概率相等, 按分位点的大小, 小到大对区间进行命名, 区间号即为编码符号。(4) 第四步:子区间的均值进行分为区间匹配。时序窗口子区间的标准化均值的每个点在 N (0, 1) 分布中对应的区间, 并将区间号设为每个子区间的编码, 即对时序窗口完成了编码, 将 N长的连续变量降为长为 n的离散字符。整个过程可表示为:win YPAAsymbol (符号化) 图 1 基于正态分布的分为区间编码图 下载原图第三步与第四步过程如图 1所示, 序列片段按子区间平均化后, 找到对应在正态分布中的分为区间, 按分为区间的位置, 赋给该数值相应的编码。图中相应数据的编码结
11、果为“1-3-2-5-5”, 整体上反映了时间序列片段波动上升的趋势。(5) 第五步:等宽窗口移动至包络所有数据。设置步长, 一般步长设置为 1, 每次窗口内数据编码完后, 窗口移动一个时点, 进行下一轮数据编码, 重复步骤 2至步骤 4。1.2 构建模型参数优化准则分段符号聚合表示的形态设定方式的参数簇为 (N, n, m) , 其中 N表示窗口长度;n 表示窗口子区间个数;m 表示字符级别数目 (分位区间数) 。在给定 N的情形下, n、m 有多个选择, 每种选择可能所映射的编码空间都不一样。为在给定窗口长度 N的前提下, 选择最优的 n和 m, 则需对编码空间与原始序列空间的变换关系设置
12、拟合标准以此进行参数的选择:1.2.1 信息损失最小原则 (经验损失函数) 对于模型的参数簇, 在给定窗口 N的前提下, 序列编码后信息损失的度量, 为参数 n和 m的优化提供了可能。本文用均值方差 (MSE) 来衡量相对信息损失程度。式中 S表示形态编码, X 表示原始时间序列, s i表示序列第 i个元素所对应的数值化字符 (将编码映射为 (0-1) 空间的分为区间的中点) , x i表示原始序列第 i个元素的标准化数值。1.2.2 形态编码自信息最小原则 (正则化项) 离散化时间序列的处理一方面降低了原始序列的噪声, 另一方面降低了原始序列的信息熵, 将复杂的连续性数值用几个简单字符表示
13、, 一定程度上降低了算法的复杂度。对于给定 m与 n条件下, 形态的自信息熵为:式中, S 表示时间序列片段的编码形态, H (S) 为形态的自信息熵。1.2.3 综合信息损失与编码形态自信息熵, 构建评价符号化处理的衡量指标:编码信息损失准则 HIC编码信息损失准则 HIC越小则表示模型整体效果越稳健。从该指标的表达式可以看出, 一方面将编码后模型的复杂度考虑其中, 若模型参数越大, 模型越复杂, 则 HIC的第一项 H (S) 的比重将增大;另一方面改准则也考虑了模型的拟合程度, 若模型参数越小, 则模型越欠拟合, HIC 中的第二项 I (S, X) 将会增大。故该指标综合反映了模型复杂
14、度与模型信息损失的等因素。1.3 编码形态相似度的衡量定义符号化距离对于不同的时间序列片段, 每两者都可用一距离来衡量二者之间的相似程度, 距离越小, 序列之间越相似, 反正则越不相似。1.3.1 将原始时间序列片段投射至新的编码空间进行比较, 可能会出现两类错误:(1) 原空间中不相似的形态, 在编码空间中会相似:即出现错误判断(2) 原空间中相似的形态, 在编码空间中不相似:即出现漏判在相似搜索中, 往往第二类漏判的错误更为严重, 为防止第二类错误, 需对不同形态之间距离的定义增加限定条件, 即原始距离下界条件:1.3.2 针对上述问题, 本文提供了一种将符号映射回连续数值的空间相似距离计
15、算方法:将各字符对应到分位区间, 并以分为区间的中点来数值化表示字符, 则两个编码形态的距离即为相应数值化变量的欧拉距离该过程为原始数据压缩编码的逆过程。据此, 不同字符之间的距离即为不同分位区间的中点距离。需要注意的是, 在包含+与-的两个端点区间, 根据标准正态分布的 3 原则, 99.74%的数据都落入 (-3, 3) 内, 故将-3 赋予第一区间字符对应的数值, 而+3 赋予第 m区间字符对应的数值。2 基于金融时间序列的实证分析2.1 数据说明本研究选取证券市场中的沪深 300指数作为数据源, 从中截取 2010年 1月 4日到 2014年 12月 31日的日收盘价数据作为样本。2.
16、2 基于 HIC准则的模型参数优化过程(1) 以沪深 300自 2010年到 2015年的日收盘价作为训练样本, 根据交易周期, 每个月的交易日平均为 20天, 故窗口长度取 20。按 N=20, 设置滑动窗口, 取移动步长为 1, 对每个窗口内的时间序列片段按 SAX算法进行压缩编码。(2) 每次压缩设定 (n, m) , 进行循环, 并统计所以窗口 HIC值, 以所以窗口的 HIC均值作为 (n, m) 的返回值。(3) 设定 n的取值范围为 5-10的整数, m 的取值范围为 5-15的整数, 进行参数空间的遍历。若 n或 m选择过小, 则序列形态的设定将完全欠拟合, 对形态之间的相似性度量将失去意义。本文选择窗口子区间和字符级别的初始值为 n=5, m=5。在窗口长度 N=20的条件下, 进行 n和 m的遍历计算, 每一对 (n, m) 的组合计算出所有窗口序列的 HIC的平均值, 以 HIC的平均值来度量每对参数 (n, m) 下, 模型的优劣。图 2 不同参数组合下的训练
