[发明专利]一种基于DTW的时间序列相似性预测方法

摘要

本发明涉及一种基于DTW的时间序列相似性预测方法，属于时间序列数据挖掘技术领域。该方法将目前已知的对DTW进行加速的方法，如LB_Kim、LB_Keogh、逆LB_Keogh和传统的DTW方法等进行级联，在不同阶段利用不同方法对查询集进行过滤。同时，为了提高查询准确性，我们引入z‑score标准化，在计算DTW距离之前对查询序列进行标准化，在读取数据的过程中，同步进行标准化，进一步提高算法效率。然后，将改进的DTW方法应用到时间序列的类比合成预测方法中，从而提高预测的速度与精度。本方法充分利用不同方法的优点，有效的提高了时间序列的查询速度，继而提高了类比合成预测方法的速度和准确性。

主权项

一种基于DTW的时间序列相似性预测方法，其特征在于：该方法包括以下步骤：S1：生成类比模式和参考模式：假设一个一维时间序列为T＝{x1,x2,…,xm,…xm+k}，先假定已有合适的模式长度k，则生成类比模式C＝{x1,x2,…,xm}和参考模式Q＝{xm+1,xm+2,…,xm+k}，其中类比模式为时间序列T中的历史数据，参考模式为时间序列最近的发展趋势；S2：构造类比模式C的封带，所述封带指的是利用全局约束条件得到序列的上下边界，其边界所包含的部分；对C进行z‑score标准化，z‑score标准化是基于原始数据的均值(mean)和标准差(standard deviation)进行数据的标准化，定义如下：x′=x-μσ---(1)]]>μ=1mΣi=1mxi---(2)]]>σ2=1mΣi=1mxi2-μ2---(3)]]>其中，x为X中的数据点，μ为X的均值，σ为X的标准差；S3：利用LB_kimFL方法对类比模式C进行过滤，所述LB_kimFL方法为LB_kim方法的改进，具体如下：LB_kim方法通过提取四元组特征向量，包括序列第一个元素、最后一个元素和序列的最大值和最小值，该下界利用提取四元组中个向量之间平方差最大值最为下界，其算法复杂度为O(N)，特征提取的计算公式如下：LB_kim(Q,C)=max|first{Q}-first{C})||last{Q}-last{C})||max{Q}-max{C}||min{Q}-min{C}|---(4)]]> 由于进行标准化后的时间序列数据的最大和最小值对于整个下界距离贡献较小，因此，去除原来LB_kim方法中提取的四个特征点中的最大和最小值，只保留起始点和终止点，称为LB_kimFL方法，其算法复杂度降为O(1)，定义如下：LB_kimFL(Q,C)=max|first{Q}-first{C}||last{Q}-last{C}|---(5);]]>S4：利用LB_keogh方法对查询集进行过滤；S5：利用LB_rkeogh方法进行过滤，当步骤S4中的方法计算得到的下界距离还未超出预定阈值时，利用LB_rkeogh方法进行进一步判断；S6：经过步骤S5得到与参考模式相似的序列候选集S，那么得到的相似序列结果为S＝{Q1，Q2,…,Qn}；接下来从S中的相似序列按照相似性大小进行排序，得到S’＝{Q1’,Q2’,…,Qn’}；根据实验，从中选取p个最相似序列，最为合成预报的参考模式，最终的得到整合的参考模式Q，＝{Q,Q1’,Q2’,…,QP’}，将其用于下一步的合成预报；S7：将得到的参考模式利用加权平均法进行合成预报。