基于趋势转折点边界面积的时间序列分段算法

摘  要： 时间序列数据具有数据量大、维度高等特点，对时间序列数据进行挖掘之前通常先进行分段预处理。传统的基于特殊点分段算法往往只关注该特殊点相邻点或相邻特殊点的变化情况，不能有效表示该特殊点左右两侧的中长期变化趋势，本文提出一种基于趋势转折点边界面积的时间序列分段算法。该方法首先找出趋势转折点，之后寻找该点左右两侧维持趋势的边界点，在寻找边界时允许轻微波动，最后计算这三点构成的面积，以此代表该点的重要性。该算法在真实工业生产数据上实验效果良好，并通过不同领域公共数据集与其他算法进行比较，证明算法有效。

关键词： 时间序列;趋势转折点;边界面积;波动阈值;拟合误差

中图分类号： TP391    文獻标识码： A    DOI：10.3969/j.issn.1003-6970.2019.12.043

本文著录格式：汤晶晶，李晋宏. 基于趋势转折点边界面积的时间序列分段算法[J]. 软件，2019，40（12）：195200

Time Series Segmentation Algorithm Based on Trend Transition Point Boundary Area

TANG Jing-jing， LI Jin-hong

（College of Information Science， North China University of Technology， Beijing Key Laboratory on

Integration and Analysis of Large-Scale Stream Data， Beijing 100144， China）

【Abstract】： Time series data has the characteristics of large data quantity and high dimension. The time series data is usually pre-processed before being mined. The traditional segmentation algorithm based on the special point usually only focuses on the changes of the adjacent points or the adjacent special points， and cannot effectively represent the mid-to-long-term change trend of the left and right sides of the special point. Therefore， a time series segmentation algorithm based on the area of trend transition point with the boundary points is proposed. This method first finds trend transition points， then looks for the boundary points to maintain the trend on the left and right sides， and allows slight fluctuations when looking for the boundary. Finally， the area formed by these three points is calculated to represent the importance of the point. This algorithm has good experimental result on real industrial production data， and is proved to be effective by comparing the public data sets in different fields with other algorithms.

【Key words】： Time series; Trend transition point; Boundary area; Fluctuation threshold; Fitting error

0  引言

时间序列数据挖掘在近年来成为热点研究领域，由特定的字母、数字、符号等实值元素组成的连续序列通常称为时间序列[1]。随着大数据和云计算的发展，数据存储和处理能力不断增强，许多数据被以时间序列形式存储，例如股票价格、销售数据、天气数据、心电图、工业生产数据等。时间序列数据挖掘通常包括预测、分类、聚类、相似性搜索、异常检测、关联规则挖掘等[2]。时间序列由于其数据量大和维度高的特点，在进行挖掘之前通常会经过预处理，常见的方法有基于频域的方法，例如傅里叶变换[3]（DFT）、离散小波变换[4]（DWT）、离散余弦变换[5]（DCT），基于符号的表示方法[6]（SAX），基于奇异值分解的方法[3]（SVD），以及分段线性表示方法[7]（PLR）。

文献[7]提出分段线性表示方法（Piecewise Linear Representation）一类是通过控制拟合误差不超过设定阈值的方法，包括滑动窗口（Sliding Windows）、自顶向下（Top-Down）、自底向上（Bottom-Up）三种方法，另一类是将时间序列数据通过相邻的多个线段来表示，包括线性插值（Linear Interpolation）和线性回归（Linear Regression）方法，其中线性插值方法是指在时间序列中选取有限数个点，相邻点之间的直线线段用来表示该两点之间的数据，而线性回归的拟合结果则可能会导致线段之间不连接。文献[8]提出的分段近似聚合（PLR_PAA）算法是一种常用的时间序列线性表示方法，该方法首先将时间序列按照相同时间跨度进行划分，之后取每个划分后的子序列的均值来表示整个子序列。文献[9]提出一种基于斜率变化来提取边缘点的时间序列分段线性表示方法（PLR_SEEP），当某一点与左右两侧相邻点之间的斜率变化大于设定阈值时即认为是边缘点。文献[10][11]均通过定义并查找趋势转折点，计算该趋势转折点的重要程度，从而对时间序列进行分段线性表示。文献[12]分析了不同距离函数选择对关键点选取的影响，并提出了基于序列重要点的时间序列分割算法（PLR_SIP），该算法需要输入分段的区域误差值，通过递归一直对序列左侧进行分割，直到拟合误差小于指定的值。文献[13]提出一种基于重要点的时间序列分段算法（PLR_TSIP），通过分析拟合误差的大小和序列长度，对优先级较高的子序列进行预分段处理，该算法分段后拟合误差较低，但是算法复杂度较高，执行时间较长。文献[14]提出一种基于相邻均值差（AMD）的时间序列动态分割方法，计算某一点与左右邻域的差值来定义峰值点和谷值点，并用符号表示序列变化，以此为依据进行划分。

针对在时间序列分段算法中只考虑数值变化而忽略了时间跨度，本文提出一种基于趋势转折点与边界点面积的时间序列分割算法（PLR_AP），首先找出序列中所有的趋势转折点，接着对趋势转折点分别向两侧延伸寻找边界点，边界点满足的条件是该点与趋势转折点间的数据保持某一趋势，同时允许在阈值范围内与趋势不一致的波动，例如某一趋势转折点与其右侧的边界点的数据总体保持下降趋势，虽然中间有某一点为上升趋势，只要上升范围在阈值内即可。确定边界点后，计算特殊转折点及其两侧边界点组成的三角形面积，作为该点重要程度的指标。该算法同时考虑了趋势转折点的波动情况以及左右两侧的延伸范围，运算速度快，拟合误差也较小，波动阈值易确定。

1  相关概念和定义

1.1  基本概念

定义1（时间序列）时间序列数据是一组有序元素组成的集合，每个元素包含时间和数值，时间序列表示为，元素表示时间序列在时刻的数值为，其中时间是逐渐递增状态，通常情况下时间间隔是固定不变的，若，，则时间序列可简记为。

定义2（时间序列分段线性表示）设有时间序列，分段点集合为，其中，，，分段后的时间序列表示为，其中表示在区间[]内的线段拟合函数，其两端端点分别为。

定义3（拟合误差） 设有原时间序列与分段后的时间序列，对中每个区间[]进行线性插值，得到插值后的序列，那么拟合序列与原序列的拟合误差定义为：

定义4（压缩率） 设有原时间序列 与线性表示后的分段点集合 ，则压缩率表示为。

1.2  相关定义

1.2.1  趋势转折点

在已出现的PLR时间序列分割算法中，多数算法依据关键点或趋势转折点来对时间序列进行分割，文献[10]中作者提出了九种时间序列三点之间的模式变化，其中三种是趋势保持点，六种是趋势转折点，在本文算法中将这六种趋势转折点分为两类，一类是上升趋势转折点，一类是下降趋势转折点。对于上升趋势转折点，该点左侧应保持下降或稳定趋势，右侧应保持上升或稳定趋势，下降趋势转折点则相反，其定义如下。

定义5（趋势转折点）设有时间序列 ，若点满足或，则点为上升趋势转折点，同理若点满足且，则点为下降趋势转折点。

图1  上升、下降趋势转折点

Fig.1  Up-trend and down-trend transition points

1.2.2  边界点

定义6（边界点） 本文算法关注趋势转折点左右两侧中长期变化趋势，试图找到该点左右两侧边界点。以上升趋势转折点为例，该趋势转折点与左侧边界点之间应保持下降趋势，与右侧边界点之间应保持上升趋势，在寻找边界点过程中，左侧允许出现上升情况的点，右侧允许出现下降情况的点，单侧边出现的所有反向趋势的波动范围之和在阈值范围内即可。当波动之和超过阈值，则停止延伸搜索，在已搜索到的点中，与趋势转折点差值最大的点即为边界点。

如图2所示，点是上升趋势转折点，假设其左侧允许上升的范围阈值为，线段、、均为上升趋势，线段与的上升波动之和小于，加上线段后波动之和大于，则点向左侧搜索到点停止，在、、、四个点中与点差值最大的点为，那么点的左侧边界点即为。同理，假设其右侧允许下降的范围阈值为，向右搜索到点停止，同时点也是点的右侧边界点。

图2  趋势转折点与边界点

Fig.2  Trend transition points and boundary points

1.2.3  趋势转折点与边界点面积

文献[12]中比较了不同距离对关键点度量的影响，多数算法选择垂直距离进行度量，本文选择趋势转折点及其边界点构成的三角形面积作为度量，其计算公式由垂直距离乘以左右两侧边界点水平距离除以2，其原因是垂直距离包含了趋势转折点的波动幅度，而水平距离则包含了该点的时间跨度，通过计算面积相乘的方式对该点的重要程度进行有效的评价。由于水平距离为时间间隔个数，在计算时将所有特殊点的边界点水平间隔做缩放处理，使和为1，同理对所有特殊点的垂直距离也做缩放处理，使和为1，在同一量纲下做相乘处理。

图3  面积计算

Fig.3  Area calculation

如图3所示，点为趋势转折点，点、为点的边界点，三角形的面积计算为线段乘以除以2，在实际计算过程中不做除以2處理。其中垂直距离的计算公式如下：

1.2.4  波动阈值

在定义6中给出了边界点的定义，其中允许上升的范围阈值为，允许下降的范围阈值为，波动阈值的确定依据全序列的上升及下降情况，设有时间序列，其中对于点到，若点满足，则该点为上升状态，标记为，若点满足，则该点为下降趋势，标记为，阈值和阈值的计算公式如下：

2  算法描述

输入：时间序列，压缩率。

步骤1：对于时间序列中到，对于每个点计算，保存在集合中，即，。

步骤2：判断集合中元素值的正负性，依据阈值计算公式3，计算上升波动阈值和下降波动阈值。

步骤3：初始化趋势转折点集合为空，依据趋势转折点的定义，排除序列首尾点，对，若，，且不满足，则点为上升趋势转折点，标记为，转步骤4。若，，且不满足，则点为下降趋势转折点，标记为，转步骤5。

步骤4：初始化。对于上升趋势转折点，左侧总体应保持下降趋势，右侧总体应保持上升趋势。向左侧搜索，若左侧出现上升点，即，为点距离点的间隔，则波动范围，当，停止搜索，并在已搜索点中寻找最大值点为左侧边界点，记为，为左侧边界点与趋势转折点间隔。向右搜索，若右侧出现下降点，即，为点距离点的间隔，则波动范围，当，停止搜索，并在已搜索点中寻找最大值点为右侧边界点，记为，为右侧边界点与趋势转折点间隔。根据公式2计算垂直距离，该趋势转折点索引为，边界点间隔，保存加入集合。

步骤5：初始化。对于下降趋势转折点，左侧总体应保持上升趋势，右侧总体应保持下降趋势。参考步骤4，若左侧搜索到下降点，，当时停止搜索，并在已搜索点中寻找最小值为左侧边界点。同理，若右侧搜索到上升点，，当时停止搜索，并在已搜索点中寻找最小值为右侧边界点。保存加入集合。

步骤6：对于集合中每个元素包含的和，分别作和为1的缩放处理，经过缩放后将每个元素的和相乘，并按照相乘后的结果从大到小对集合排序。

步骤7：根据压缩率计算需提取分段点个数，若小于等于集合元素个数（2为考虑的首尾两个点），则取中前数个点作为分段点。否则，计算剩余非趋势转折点与相邻点的垂直距离，排序后，按照所缺个数选择点作为分段点。最后加上序列首尾点。

输出：分段点集合。

3  实验与分析

3.1  实验数据

本文首先对某电解铝企业电解槽出铝量数据进行分段线性表示，样本为某一台电解槽的出铝量，每台电解槽每日产出铝，数据时间为2018年12月12日至2019年5月5日。

为证明本文算法的适用性，选取Keogh[8]等人提供的来自不同领域的公开数据集，简称KData。同时将实验结果与其他文献中提出的分段算法进行比较，选取了其中常用的10个数据集，数据如表1所示。

表1  KData实验数据集

Tab.1  Experimental data set

序列名称 序列长度 序列名称 序列长度

Burst 9382 Memory 6875

Chaotic 1800 Ocean 4096

Earthquake 4097 Powerplant 2400

Fluid_dynamics 10000 Speech 1021

Leleccum 4320 Tide 8746

在实验过程中，为了方便比较观察，在实验之前将数据进行归一化预处理，公式如下：

实验环境：系统为window10，处理器为inter-i7，内存为16GB，开发环境为python3.6。

3.2  分段结果

研究工业生产序列数据时，分段预处理往往很有必要，选取某电解铝企业5097号槽135天的出铝量时间序列数据，压缩率为80%。图4和图5分别为该电解槽出铝量的原始序列和拟合后序列，原始序列数据特点是在短期内保持较稳定的状态，但在一段时间后有较大的波动，分段拟合后能够更好体现数据的总体趋势特点。

以KData数据集中speech时间序列为例，压缩率为80%。图6和图7分别代表其原始序列和拟合序列，能够看出分段拟合后可以很好地保持原数据波动特性。

图4  出铝量原始序列

Fig.4  Original time series of aluminum output

图5  出铝量拟合序列

Fig.5  Fitting time series of aluminum output

图6  Speech原始序列

Fig.6  Original time series of speech time series

图7  Speech拟合序列

Fig.7  Fitting time series of speech time series

3.3  拟合误差比较

时间序列分段线性表示的一个重要评价指标是拟合后的序列与原始序列的拟合误差大小，计算方式见公式（1）。在压缩率为80%的情况下，本文算法PLR_AP分别与PAA[8]、PLR_PF[15]、PLR_FP[16]、PLR_KP[17]四种算法在KData数据集上进行实验比较，实验结果如表2。

表2  不同算法拟合误差比较

Tab.2  Comparison of fitting errors of different algorithms

序列名称 PAA PLR_

PF PLR_

FP PLR_

KP PLR_

AP

Burst 0.38 1.09 0.9 0.45 0.26

Chaotic 1.76 1.63 1.63 0.85 1.10

Earthquake 3.48 2.10 2.22 2.66 2.0

Fluid_dynamics 2.77 2.40 2.38 1.51 2.20

Leleccum 0.64 1.60 0.98 0.71 0.51

Memory 0.56 0.50 0.49 0.39 0.44

Ocean 0.31 0.42 0.31 0.30 0.28

Powerplant 1.07 2.32 1.11 1.05 0.96

Speech 2.48 1.37 3.22 1.20 1.33

Tide 3.22 2.29 2.48 3.41 1.92

由實验结果可以看出，PLR_AP算法具有较小的拟合误差，与上述几个算法进行比较后在多个数据集上具有最小的拟合误差，且在不是最小拟合误差的数据集上实验结果也保持较小水平，证明该算法在多种类型的时间序列数据上具有适用性。

3.4  算法速度比较

PLR_AP算法首先计算每个时间点的后一个时间点数据与该时间点数据的差值，遍历完之后保存数据，之后根据保存的数据的正负性判断该点是否为趋势转折点，若为趋势转折点则搜索边界点并计算与边界点构成的三角形面积。若根据压缩率选取点的数量小于趋势转折点的数量，则可以直接从趋势转折点中选取，若趋势转折点数量不够，则需从剩余非趋势转折点中选取，因此该算法运行速度主要受趋势转折点在序列中的比例和压缩率之间关系的影响。本文选择ocean数据集与PAA算法在不同的压缩率情况下进行速度比较。

如图8所示，当压缩率为50%时，趋势转折点的数量小于所需分段点数量，因此需要计算其他非趋势转点与相邻点垂直距离并选取分段点，当压缩率为75%及以上时，趋势转折点数量大于所需分段点数量，直接从趋势转折点中选取点，运行速度明显降低，与PAA算法耗时几乎一致，运行速度快且保持稳定状态。

图8  算法速度比较

Fig.8  Comparison of different algorithms speed

4  结束语

本文提出一种基于趋势转折点与边界点面积的时间序列分段算法，该算法综合考虑了趋势转折点的波动大小以及时间跨度的大小，通过计算面积的方式来评价该点的重要程度，同时允许趋势转折点小范围的逆趋势波动，逆趋势波动阈值大小易确定。该算法在工业生产时间序列数据上能够取得良好分段效果，为时间序列数据挖掘提供预处理工作。与其他时间序列分段线性表示算法相比，能够更好地体现时间序列的变化趋势和特征，同时算法速度较快，拟合误差也较小。日后将进一步研究时间序列的最佳压缩率，以及分段处理后的时间序列数据挖掘。

参考文献

[1]Antunes C M， Oliveira A L. Temporal data mining： An overview[C]//Kdd Workshop on Temporal Data Mining. 2001： 1-13.

[2]Saeed Aghabozorgi， Ali Seyed Shirkhorshidi， Teh Ying Wah. Time-series clustering–A decade review[J]. Information Systems. 2015， 53： 16-38.

[3]Moon Y S， Whang K Y， Loh W K. Duality-based subsequence matching in time-series databases[C]//International Conference on Data Engineering. IEEE， 2001： 263-272.

[4]Kawagoe K ， Ueda T . A Similarity Search Method of Time Series Data with Combination of Fourier and Wavelet Transforms[C]//International Symposium on Temporal Representation & Reasoning. IEEE Computer Society. 2002： 86-92.

[5]Korn F， Jagadish H V， Faloutsos C. Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences[J]. Acm Sigmod Record， 1997， 26（2）： 289-300.

[6]Keogh E J， Lonardi S， Ratanamahatana C. Towards parameter-free data mining[C]//Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， Seattle， Washington， USA， August 22-25， 2004. ACM， 2004： 206-215.

[7]Keogh E ， Chu S ， Hart D ， et al. An Online Algorithm for Segmenting Time Series[C]//Proceedings 2001 IEEE International Conference on Data Mining. IEEE， 2001： 289-296.

[8]Eamonn Keogh， Kaushik Chakrabarti， Michael Pazzani， Sharad Mehrotra. Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases[J]. Knowledge and Information Systems， 2001， 3（3）： 263-286.

[9]詹艳艳， 徐荣聪， 陈晓云. 基于斜率提取边缘点的时间序列分段线性表示方法[J]. 计算机科学， 2006（11）： 139-142+ 161.

[10]廖俊， 于雷， 罗寰， 穆中林. 基于趋势转折点的时间序列分段线性表示[J]. 计算机工程与应用， 2010， 46（30）： 50- 53+81.

[11]尚福华， 孙达辰. 基于时间序列趋势转折点的分段线性表示[J]. 计算机应用研究， 2010， 27（06）： 2075-2077+2092.

[12]周大镯， 李敏强. 基于序列重要點的时间序列分割[J]. 计算机工程， 2008， 34（23）： 14-16.

[13]孙志伟， 董亮亮， 马永军. 一种基于重要点的时间序列分段算法[J]. 计算机工程与应用， 2018， 54（18）： 250-255.

[14]C. Yang， W. Liao. Adjacent Mean Difference （AMD） method for dynamic segmentation in time series anomaly detection[C]// International Symposium on System Integration. IEEE， 2017， 241-246.

[15]Prat K B，Fink E. Search for patterns in compressed time series[J]. International Journal of Image and Graphics ， 2002， 2（1）： 89-106.

[16]Xiao H ， Feng X F ， Hu Y F . A new segmented time warping distance for data mining in time series database[C]// International Conference on Machine Learning & Cybernetics. IEEE， 2004： 1277-1281.

[17]陈帅飞， 吕鑫， 戚荣志， 王龙宝， 余霖. 一种基于关键点的时间序列线性表示方法[J]. 计算机科学， 2016， 43（05）： 234-237.