摘 ?要： 時間序列數(shù)據(jù)具有數(shù)據(jù)量大、維度高等特點，對時間序列數(shù)據(jù)進行挖掘之前通常先進行分段預處理。傳統(tǒng)的基于特殊點分段算法往往只關注該特殊點相鄰點或相鄰特殊點的變化情況，不能有效表示該特殊點左右兩側的中長期變化趨勢，本文提出一種基于趨勢轉折點邊界面積的時間序列分段算法。該方法首先找出趨勢轉折點，之后尋找該點左右兩側維持趨勢的邊界點，在尋找邊界時允許輕微波動，最后計算這三點構成的面積，以此代表該點的重要性。該算法在真實工業(yè)生產數(shù)據(jù)上實驗效果良好，并通過不同領域公共數(shù)據(jù)集與其他算法進行比較，證明算法有效。

關鍵詞： 時間序列;趨勢轉折點;邊界面積;波動閾值;擬合誤差

中圖分類號： 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 ?引言

時間序列數(shù)據(jù)挖掘在近年來成為熱點研究領域，由特定的字母、數(shù)字、符號等實值元素組成的連續(xù)序列通常稱為時間序列[1]。隨著大數(shù)據(jù)和云計算的發(fā)展，數(shù)據(jù)存儲和處理能力不斷增強，許多數(shù)據(jù)被以時間序列形式存儲，例如股票價格、銷售數(shù)據(jù)、天氣數(shù)據(jù)、心電圖、工業(yè)生產數(shù)據(jù)等。時間序列數(shù)據(jù)挖掘通常包括預測、分類、聚類、相似性搜索、異常檢測、關聯(lián)規(guī)則挖掘等[2]。時間序列由于其數(shù)據(jù)量大和維度高的特點，在進行挖掘之前通常會經過預處理，常見的方法有基于頻域的方法，例如傅里葉變換[3]（DFT）、離散小波變換[4]（DWT）、離散余弦變換[5]（DCT），基于符號的表示方法[6]（SAX），基于奇異值分解的方法[3]（SVD），以及分段線性表示方法[7]（PLR）。

文獻[7]提出分段線性表示方法（Piecewise Linear Representation）一類是通過控制擬合誤差不超過設定閾值的方法，包括滑動窗口（Sliding Windows）、自頂向下（Top-Down）、自底向上（Bottom-Up）三種方法，另一類是將時間序列數(shù)據(jù)通過相鄰的多個線段來表示，包括線性插值（Linear Interpolation）和線性回歸（Linear Regression）方法，其中線性插值方法是指在時間序列中選取有限數(shù)個點，相鄰點之間的直線線段用來表示該兩點之間的數(shù)據(jù)，而線性回歸的擬合結果則可能會導致線段之間不連接。文獻[8]提出的分段近似聚合（PLR_PAA）算法是一種常用的時間序列線性表示方法，該方法首先將時間序列按照相同時間跨度進行劃分，之后取每個劃分后的子序列的均值來表示整個子序列。文獻[9]提出一種基于斜率變化來提取邊緣點的時間序列分段線性表示方法（PLR_SEEP），當某一點與左右兩側相鄰點之間的斜率變化大于設定閾值時即認為是邊緣點。文獻[10][11]均通過定義并查找趨勢轉折點，計算該趨勢轉折點的重要程度，從而對時間序列進行分段線性表示。文獻[12]分析了不同距離函數(shù)選擇對關鍵點選取的影響，并提出了基于序列重要點的時間序列分割算法（PLR_SIP），該算法需要輸入分段的區(qū)域誤差值，通過遞歸一直對序列左側進行分割，直到擬合誤差小于指定的值。文獻[13]提出一種基于重要點的時間序列分段算法（PLR_TSIP），通過分析擬合誤差的大小和序列長度，對優(yōu)先級較高的子序列進行預分段處理，該算法分段后擬合誤差較低，但是算法復雜度較高，執(zhí)行時間較長。文獻[14]提出一種基于相鄰均值差（AMD）的時間序列動態(tài)分割方法，計算某一點與左右鄰域的差值來定義峰值點和谷值點，并用符號表示序列變化，以此為依據(jù)進行劃分。

針對在時間序列分段算法中只考慮數(shù)值變化而忽略了時間跨度，本文提出一種基于趨勢轉折點與邊界點面積的時間序列分割算法（PLR_AP），首先找出序列中所有的趨勢轉折點，接著對趨勢轉折點分別向兩側延伸尋找邊界點，邊界點滿足的條件是該點與趨勢轉折點間的數(shù)據(jù)保持某一趨勢，同時允許在閾值范圍內與趨勢不一致的波動，例如某一趨勢轉折點與其右側的邊界點的數(shù)據(jù)總體保持下降趨勢，雖然中間有某一點為上升趨勢，只要上升范圍在閾值內即可。確定邊界點后，計算特殊轉折點及其兩側邊界點組成的三角形面積，作為該點重要程度的指標。該算法同時考慮了趨勢轉折點的波動情況以及左右兩側的延伸范圍，運算速度快，擬合誤差也較小，波動閾值易確定。

1 ?相關概念和定義

1.1 ?基本概念

定義1（時間序列）時間序列數(shù)據(jù)是一組有序元素組成的集合，每個元素包含時間和數(shù)值，時間序列表示為，元素表示時間序列在時刻的數(shù)值為，其中時間是逐漸遞增狀態(tài)，通常情況下時間間隔是固定不變的，若，，則時間序列可簡記為。

定義2（時間序列分段線性表示）設有時間序列，分段點集合為，其中，，，分段后的時間序列表示為，其中表示在區(qū)間[]內的線段擬合函數(shù)，其兩端端點分別為。

定義3（擬合誤差） 設有原時間序列與分段后的時間序列，對中每個區(qū)間[]進行線性插值，得到插值后的序列，那么擬合序列與原序列的擬合誤差定義為：

定義4（壓縮率） 設有原時間序列 與線性表示后的分段點集合 ，則壓縮率表示為。

1.2 ?相關定義

1.2.1 ?趨勢轉折點

在已出現(xiàn)的PLR時間序列分割算法中，多數(shù)算法依據(jù)關鍵點或趨勢轉折點來對時間序列進行分割，文獻[10]中作者提出了九種時間序列三點之間的模式變化，其中三種是趨勢保持點，六種是趨勢轉折點，在本文算法中將這六種趨勢轉折點分為兩類，一類是上升趨勢轉折點，一類是下降趨勢轉折點。對于上升趨勢轉折點，該點左側應保持下降或穩(wěn)定趨勢，右側應保持上升或穩(wěn)定趨勢，下降趨勢轉折點則相反，其定義如下。

定義5（趨勢轉折點）設有時間序列 ，若點滿足或，則點為上升趨勢轉折點，同理若點滿足且，則點為下降趨勢轉折點。

圖1 ?上升、下降趨勢轉折點

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

1.2.2 ?邊界點

定義6（邊界點） 本文算法關注趨勢轉折點左右兩側中長期變化趨勢，試圖找到該點左右兩側邊界點。以上升趨勢轉折點為例，該趨勢轉折點與左側邊界點之間應保持下降趨勢，與右側邊界點之間應保持上升趨勢，在尋找邊界點過程中，左側允許出現(xiàn)上升情況的點，右側允許出現(xiàn)下降情況的點，單側邊出現(xiàn)的所有反向趨勢的波動范圍之和在閾值范圍內即可。當波動之和超過閾值，則停止延伸搜索，在已搜索到的點中，與趨勢轉折點差值最大的點即為邊界點。

如圖2所示，點是上升趨勢轉折點，假設其左側允許上升的范圍閾值為，線段、、均為上升趨勢，線段與的上升波動之和小于，加上線段后波動之和大于，則點向左側搜索到點停止，在、、、四個點中與點差值最大的點為，那么點的左側邊界點即為。同理，假設其右側允許下降的范圍閾值為，向右搜索到點停止，同時點也是點的右側邊界點。

圖2 ?趨勢轉折點與邊界點

Fig.2 ?Trend transition points and boundary points

1.2.3 ?趨勢轉折點與邊界點面積

文獻[12]中比較了不同距離對關鍵點度量的影響，多數(shù)算法選擇垂直距離進行度量，本文選擇趨勢轉折點及其邊界點構成的三角形面積作為度量，其計算公式由垂直距離乘以左右兩側邊界點水平距離除以2，其原因是垂直距離包含了趨勢轉折點的波動幅度，而水平距離則包含了該點的時間跨度，通過計算面積相乘的方式對該點的重要程度進行有效的評價。由于水平距離為時間間隔個數(shù)，在計算時將所有特殊點的邊界點水平間隔做縮放處理，使和為1，同理對所有特殊點的垂直距離也做縮放處理，使和為1，在同一量綱下做相乘處理。

圖3 ?面積計算

Fig.3 ?Area calculation

如圖3所示，點為趨勢轉折點，點、為點的邊界點，三角形的面積計算為線段乘以除以2，在實際計算過程中不做除以2處理。其中垂直距離的計算公式如下：

1.2.4 ?波動閾值

在定義6中給出了邊界點的定義，其中允許上升的范圍閾值為，允許下降的范圍閾值為，波動閾值的確定依據(jù)全序列的上升及下降情況，設有時間序列，其中對于點到，若點滿足，則該點為上升狀態(tài)，標記為，若點滿足，則該點為下降趨勢，標記為，閾值和閾值的計算公式如下：

2 ?算法描述

輸入：時間序列，壓縮率。

步驟1：對于時間序列中到，對于每個點計算，保存在集合中，即，。

步驟2：判斷集合中元素值的正負性，依據(jù)閾值計算公式3，計算上升波動閾值和下降波動閾值。

步驟3：初始化趨勢轉折點集合為空，依據(jù)趨勢轉折點的定義，排除序列首尾點，對，若，，且不滿足，則點為上升趨勢轉折點，標記為，轉步驟4。若，，且不滿足，則點為下降趨勢轉折點，標記為，轉步驟5。

步驟4：初始化。對于上升趨勢轉折點，左側總體應保持下降趨勢，右側總體應保持上升趨勢。向左側搜索，若左側出現(xiàn)上升點，即，為點距離點的間隔，則波動范圍，當，停止搜索，并在已搜索點中尋找最大值點為左側邊界點，記為，為左側邊界點與趨勢轉折點間隔。向右搜索，若右側出現(xiàn)下降點，即，為點距離點的間隔，則波動范圍，當，停止搜索，并在已搜索點中尋找最大值點為右側邊界點，記為，為右側邊界點與趨勢轉折點間隔。根據(jù)公式2計算垂直距離，該趨勢轉折點索引為，邊界點間隔，保存加入集合。

步驟5：初始化。對于下降趨勢轉折點，左側總體應保持上升趨勢，右側總體應保持下降趨勢。參考步驟4，若左側搜索到下降點，，當時停止搜索，并在已搜索點中尋找最小值為左側邊界點。同理，若右側搜索到上升點，，當時停止搜索，并在已搜索點中尋找最小值為右側邊界點。保存加入集合。

步驟6：對于集合中每個元素包含的和，分別作和為1的縮放處理，經過縮放后將每個元素的和相乘，并按照相乘后的結果從大到小對集合排序。

步驟7：根據(jù)壓縮率計算需提取分段點個數(shù)，若小于等于集合元素個數(shù)（2為考慮的首尾兩個點），則取中前數(shù)個點作為分段點。否則，計算剩余非趨勢轉折點與相鄰點的垂直距離，排序后，按照所缺個數(shù)選擇點作為分段點。最后加上序列首尾點。

輸出：分段點集合。

3 ?實驗與分析

3.1 ?實驗數(shù)據(jù)

本文首先對某電解鋁企業(yè)電解槽出鋁量數(shù)據(jù)進行分段線性表示，樣本為某一臺電解槽的出鋁量，每臺電解槽每日產出鋁，數(shù)據(jù)時間為2018年12月12日至2019年5月5日。

為證明本文算法的適用性，選取Keogh[8]等人提供的來自不同領域的公開數(shù)據(jù)集，簡稱KData。同時將實驗結果與其他文獻中提出的分段算法進行比較，選取了其中常用的10個數(shù)據(jù)集，數(shù)據(jù)如表1所示。

表1 ?KData實驗數(shù)據(jù)集

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

在實驗過程中，為了方便比較觀察，在實驗之前將數(shù)據(jù)進行歸一化預處理，公式如下：

實驗環(huán)境：系統(tǒng)為window10，處理器為inter-i7，內存為16GB，開發(fā)環(huán)境為python3.6。

3.2 ?分段結果

研究工業(yè)生產序列數(shù)據(jù)時，分段預處理往往很有必要，選取某電解鋁企業(yè)5097號槽135天的出鋁量時間序列數(shù)據(jù)，壓縮率為80%。圖4和圖5分別為該電解槽出鋁量的原始序列和擬合后序列，原始序列數(shù)據(jù)特點是在短期內保持較穩(wěn)定的狀態(tài)，但在一段時間后有較大的波動，分段擬合后能夠更好體現(xiàn)數(shù)據(jù)的總體趨勢特點。

以KData數(shù)據(jù)集中speech時間序列為例，壓縮率為80%。圖6和圖7分別代表其原始序列和擬合序列，能夠看出分段擬合后可以很好地保持原數(shù)據(jù)波動特性。

圖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數(shù)據(jù)集上進行實驗比較，實驗結果如表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算法具有較小的擬合誤差，與上述幾個算法進行比較后在多個數(shù)據(jù)集上具有最小的擬合誤差，且在不是最小擬合誤差的數(shù)據(jù)集上實驗結果也保持較小水平，證明該算法在多種類型的時間序列數(shù)據(jù)上具有適用性。

3.4 ?算法速度比較

PLR_AP算法首先計算每個時間點的后一個時間點數(shù)據(jù)與該時間點數(shù)據(jù)的差值，遍歷完之后保存數(shù)據(jù)，之后根據(jù)保存的數(shù)據(jù)的正負性判斷該點是否為趨勢轉折點，若為趨勢轉折點則搜索邊界點并計算與邊界點構成的三角形面積。若根據(jù)壓縮率選取點的數(shù)量小于趨勢轉折點的數(shù)量，則可以直接從趨勢轉折點中選取，若趨勢轉折點數(shù)量不夠，則需從剩余非趨勢轉折點中選取，因此該算法運行速度主要受趨勢轉折點在序列中的比例和壓縮率之間關系的影響。本文選擇ocean數(shù)據(jù)集與PAA算法在不同的壓縮率情況下進行速度比較。

如圖8所示，當壓縮率為50%時，趨勢轉折點的數(shù)量小于所需分段點數(shù)量，因此需要計算其他非趨勢轉點與相鄰點垂直距離并選取分段點，當壓縮率為75%及以上時，趨勢轉折點數(shù)量大于所需分段點數(shù)量，直接從趨勢轉折點中選取點，運行速度明顯降低，與PAA算法耗時幾乎一致，運行速度快且保持穩(wěn)定狀態(tài)。

圖8 ?算法速度比較

Fig.8 ?Comparison of different algorithms speed

4 ?結束語

本文提出一種基于趨勢轉折點與邊界點面積的時間序列分段算法，該算法綜合考慮了趨勢轉折點的波動大小以及時間跨度的大小，通過計算面積的方式來評價該點的重要程度，同時允許趨勢轉折點小范圍的逆趨勢波動，逆趨勢波動閾值大小易確定。該算法在工業(yè)生產時間序列數(shù)據(jù)上能夠取得良好分段效果，為時間序列數(shù)據(jù)挖掘提供預處理工作。與其他時間序列分段線性表示算法相比，能夠更好地體現(xiàn)時間序列的變化趨勢和特征，同時算法速度較快，擬合誤差也較小。日后將進一步研究時間序列的最佳壓縮率，以及分段處理后的時間序列數(shù)據(jù)挖掘。

參考文獻

[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，F(xiàn)ink 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.