时间序列的分段线性表示

算法理论

时间序列数据的分段线性表示能使大量减少数据点,从而缩短计算时间。Keogh E[1]提出的时间序列分段线性表示方法能对时间序列有效的压缩,并在一定程度上能反应时间序列的变化趋势,并在数据挖掘的模式识别中得到了验证和广泛使用。而该方法使用的是最优化方法,所以就存在收敛性问题,因此不能保证时间序列的每一分段内只具有上升、下降或平稳的一种基本趋势,因此将导致时间序列的某些点的基本趋势被错误提取[2]。为了能保证时间序列的整体形态,同时又能反映出时间序列的局部形态特征,本文采用趋势转折点的分段线性表示法[3],具体描述如下:
(1)波动幅度达到一定程度的极值点,也就是幅度变化剧烈且相邻的极值点[2][4]。
根据文献[4]的定义1,给定常数 R 和时间序列 file,其中

$$x_{i}=\left ( \upsilon _{i},t_{i} \right ),i=1,2,...,n$$

如果 file 是一个特征点,它应该满足如下条件:
(a) 它必须是时间序列的极值点, filefile 除外;
(b) 如果 file,则 file 必须成立;否则,如果file,则 file 必须成立。
(2)短时间大波动数据点,也就是波动幅度达到一定程度的相邻点,并且这些点不是极值点。波动幅度达到一定程度可通过阈值来判定,如图1所示。

file
图1 非极值大波动数据点

$Q=\left | a-b \right |,P=\left | b-c \right |,P,Q>0$,如果 $\frac{P}{Q}>K$(P > Q),或 $\frac{P}{Q}<\frac{1}{K}$(P < Q),则认为a,b,c为大波动数据点,需要保留;而b是这种变化趋势的转折点,K为阈值。

算法流程

算法1:get_data_piece(data,t)
输入:原始数据和对应的时间序列
输出:分段线性表示数据(算法中的队列即为所求)。
step1:从data数据取一数据点;
step2:判断是否为极值点,如果是,则转step3;否则转step5;
step3:判断是否已入队列;
step4:如果该点已入队列,则转step6;否则,该点入队列,转step6;
step5:判断是否为大波动数据点,如果是,转step3;否则,转step6;
step6:判断data数据点是否取完,如果是,则结束;否则转step1。

参考文献

[1] KEOGH E. A fast and robust method for pattern matching in time series databases [C] Proc of the 9th International Conference on Tools with Artificial Intelligence. 1997:578-584.
[2] 周耹, 吴铁军. 基于重要点的时间序列趋势特征提取方法[J]. 浙江大学学报:工学版,2007,41(11):1782-1787.
[3] 尚福华, 孙达辰. 基于时间序列趋势转折点的分段线性表示[J]. 计算机应用研究,2010,27(6):2075-2077.
[4] 喻高瞻, 彭宏, 胡劲松等. 时间序列数据的分段线性表示[J]. 计算机应用与软件, 2007, 24(12):17-18.

追求梦想,做最好的自己