基于一次指数预测算法的动态规划分割算法

◇西南石油大学 赵春兰 罗 银 何 婷

时间序列分割在变异点检测、变化趋势检测及数据预处理等方面都具有重要作用。针对经典动态规划分段算法未考虑时间序列数据之间的相互影响，提出一种基于一次指数平滑预测算法和动态规划算法相结合的多元时间序列分割方法。利用一次指数平滑预测算法对所有多元时间序列分割片段进行预测，计算分割代价；再根据分割代价，运用动态规划算法对多元时间序列数据进行分割，得到全局最优的分割结果。对仿真多元时间序列数据进行分割，将新方法结果与已有算法结果进行比较，新方法分割度量值为0.0155，较已有算法减少了0.0293，说明该分割方法得到的分割结果有较高的准确度。

1 引言

时间序列数据是指在一定时间段内按照时间先后顺序排列的由时间和所对应的观察值所组成的有序数据集，广泛存在于农业、工业、医学、气象、金融、交通、通信等重要领域[1-4]。时间序列分割算法可以作为数据预处理的一个子程序，可以为后面的数据挖掘提供巨大便利，还可以让分析者得到更精确的分析结果[5-7]。

故本文在经典的动态规划算法上进行改进，考虑时间序列数据具有动态性、连续性的特点，在已有的多元时序数据的基础上，使用一次指数平滑预测算法来预测下一时刻的数据，并计算预测值与实际值之间的预测误差，根据分割误差计算分割代价，再使用动态规划算法根据分割代价选择分割点。

2 相关原理

2.1 时间序列分割

2.2 一次指数平滑法

2.3 时间序列分割的评价指标

3 基于一次指数平滑预测的动态规划分割算法

为了实现对多元时间序列的分割，本文首先根据一次指数平滑预测算法计算所有片段的误差；然后，对时间序列数据进行动态规划分割。该分割方法具体实现过程如图1所示。

图1 基于一次指数平滑预测的动态规划分割算法思维图

3.1 利用一次指数平滑法计算所有片段的误差

3.2 动态规划分割

3.3 回溯

在计算得到了所有分割片段的最优分割的分割代价及其分割边界后，根据施瓦茨的贝叶斯信息准则[9]，通过回溯确定该多元时间序列最优的分割阶数及分割边界。

4 实验分析

4.1 多元合成数据集实验

由模型可知，生成的5维时间序列由3个子片段构成，实际分段位置为40、100、150，其中150是最后一个时间点。生成的5维时间序列数据集及实际分段位置如图2所示。

图2 生成的5维时间序列及其实际分段位置

图3 分割结果

4.2 气象数据实验

本文以Guo等人[1]和 Sun等人[3]论文里用的多元气象时间序列，阿雷西博地区（Arecibo）2013年10月1日00:00到2013年10月2日00:00监测结果统计数据作为原始数据，以风速、风向、阵风为初始评价指标，如表1所示。

表1 阿雷西博地区（Arecibo）2013年10月1日00:00到2013年10月2日00:00监测数据

在该实验中，经过z_score标准化处理后，令分割阶数的最大值，应用该分割方法对数据集进行分割，获得时的分割情况。当分割阶数取不同值时，对应的数值变化如图4（a）所示。

图4 分割结果

在Guo等人[1]的论文中，使用基于贝叶斯信息准则的动态规划分割对该多元气象数据进行分割，其最优分割阶数为2，分割点位置在第134个时间点；在Sun等人[3]的论文中，使用基于动态因子模型的多元时间序列分割方法对相同多元气象数据进行了分割，其预设分割阶数为2时的分割点在第133个时间点处。以上两种分割方法的分割结果与本文提出分割方法的结果对比如表2所示。本文提出的分割算法与这两种分割方法得到的分割结果相似，由此可以看出，本文提出的基于一次指数平滑预测的动态规划分割算法适用于分割多元时间序列数据。对气象数据进行分段，能够对不同时段的气象数据进行比较，使数据的分析更加全面、直观，有助于深化对气象变化规律的认识，使气象服务更加精准，有效减轻由气象灾害带来的损失。

表2 三种分割方法结果对比

5 结束语

本文在已有的经典动态规划分段的基础上进行改进，提出了一次指数滑动预测算法和动态规划算法相结合的多元时间序列分割方法。首先，使用一次指数平滑预测算法对数据进行预测并计算其分割代价；然后，根据分割代价使用动态规划算法找出使得全局分割代价最小的分割结果。该方法考虑到了时间序列是一个连续的、动态的过程，下一个时刻的数据会受到前一时刻数据的影响，且常常是多维的，而一次指数滑动预测算法得到的预测值包含了时间序列中全部的历史数据信息，且可以对多维时序数据进行预测，使得预测结果具有良好的适应性。同时，基于动态规划算法的分割能够根据分割代价求得多元时间序列数据的全局最优的分割边界。