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

關(guān)鍵詞： 時(shí)間序列;趨勢(shì)轉(zhuǎn)折點(diǎn);邊界面積;波動(dòng)閾值;擬合誤差

中圖分類(lèi)號(hào)： TP391 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.12.043

本文著錄格式：湯晶晶，李晉宏. 基于趨勢(shì)轉(zhuǎn)折點(diǎn)邊界面積的時(shí)間序列分段算法[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í)間序列數(shù)據(jù)挖掘在近年來(lái)成為熱點(diǎn)研究領(lǐng)域，由特定的字母、數(shù)字、符號(hào)等實(shí)值元素組成的連續(xù)序列通常稱為時(shí)間序列[1]。隨著大數(shù)據(jù)和云計(jì)算的發(fā)展，數(shù)據(jù)存儲(chǔ)和處理能力不斷增強(qiáng)，許多數(shù)據(jù)被以時(shí)間序列形式存儲(chǔ)，例如股票價(jià)格、銷(xiāo)售數(shù)據(jù)、天氣數(shù)據(jù)、心電圖、工業(yè)生產(chǎn)數(shù)據(jù)等。時(shí)間序列數(shù)據(jù)挖掘通常包括預(yù)測(cè)、分類(lèi)、聚類(lèi)、相似性搜索、異常檢測(cè)、關(guān)聯(lián)規(guī)則挖掘等[2]。時(shí)間序列由于其數(shù)據(jù)量大和維度高的特點(diǎn)，在進(jìn)行挖掘之前通常會(huì)經(jīng)過(guò)預(yù)處理，常見(jiàn)的方法有基于頻域的方法，例如傅里葉變換[3]（DFT）、離散小波變換[4]（DWT）、離散余弦變換[5]（DCT），基于符號(hào)的表示方法[6]（SAX），基于奇異值分解的方法[3]（SVD），以及分段線性表示方法[7]（PLR）。

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

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

1 ?相關(guān)概念和定義

1.1 ?基本概念

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

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

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

定義4（壓縮率） 設(shè)有原時(shí)間序列 與線性表示后的分段點(diǎn)集合 ，則壓縮率表示為。

1.2 ?相關(guān)定義

1.2.1 ?趨勢(shì)轉(zhuǎn)折點(diǎn)

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

定義5（趨勢(shì)轉(zhuǎn)折點(diǎn)）設(shè)有時(shí)間序列 ，若點(diǎn)滿足或，則點(diǎn)為上升趨勢(shì)轉(zhuǎn)折點(diǎn)，同理若點(diǎn)滿足且，則點(diǎn)為下降趨勢(shì)轉(zhuǎn)折點(diǎn)。

圖1 ?上升、下降趨勢(shì)轉(zhuǎn)折點(diǎn)

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

1.2.2 ?邊界點(diǎn)

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

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

圖2 ?趨勢(shì)轉(zhuǎn)折點(diǎn)與邊界點(diǎn)

Fig.2 ?Trend transition points and boundary points

1.2.3 ?趨勢(shì)轉(zhuǎn)折點(diǎn)與邊界點(diǎn)面積

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

圖3 ?面積計(jì)算

Fig.3 ?Area calculation

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

1.2.4 ?波動(dòng)閾值

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

2 ?算法描述

輸入：時(shí)間序列，壓縮率。

步驟1：對(duì)于時(shí)間序列中到，對(duì)于每個(gè)點(diǎn)計(jì)算，保存在集合中，即，。

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

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

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

步驟5：初始化。對(duì)于下降趨勢(shì)轉(zhuǎn)折點(diǎn)，左側(cè)總體應(yīng)保持上升趨勢(shì)，右側(cè)總體應(yīng)保持下降趨勢(shì)。參考步驟4，若左側(cè)搜索到下降點(diǎn)，，當(dāng)時(shí)停止搜索，并在已搜索點(diǎn)中尋找最小值為左側(cè)邊界點(diǎn)。同理，若右側(cè)搜索到上升點(diǎn)，，當(dāng)時(shí)停止搜索，并在已搜索點(diǎn)中尋找最小值為右側(cè)邊界點(diǎn)。保存加入集合。

步驟6：對(duì)于集合中每個(gè)元素包含的和，分別作和為1的縮放處理，經(jīng)過(guò)縮放后將每個(gè)元素的和相乘，并按照相乘后的結(jié)果從大到小對(duì)集合排序。

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

輸出：分段點(diǎn)集合。

3 ?實(shí)驗(yàn)與分析

3.1 ?實(shí)驗(yàn)數(shù)據(jù)

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

為證明本文算法的適用性，選取Keogh[8]等人提供的來(lái)自不同領(lǐng)域的公開(kāi)數(shù)據(jù)集，簡(jiǎn)稱KData。同時(shí)將實(shí)驗(yàn)結(jié)果與其他文獻(xiàn)中提出的分段算法進(jìn)行比較，選取了其中常用的10個(gè)數(shù)據(jù)集，數(shù)據(jù)如表1所示。

表1 ?KData實(shí)驗(yàn)數(shù)據(jù)集

Tab.1 ?Experimental data set

序列名稱 序列長(zhǎng)度 序列名稱 序列長(zhǎng)度

Burst 9382 Memory 6875

Chaotic 1800 Ocean 4096

Earthquake 4097 Powerplant 2400

Fluid_dynamics 10000 Speech 1021

Leleccum 4320 Tide 8746

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

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

3.2 ?分段結(jié)果

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

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

圖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 ?擬合誤差比較

時(shí)間序列分段線性表示的一個(gè)重要評(píng)價(jià)指標(biāo)是擬合后的序列與原始序列的擬合誤差大小，計(jì)算方式見(jiàn)公式（1）。在壓縮率為80%的情況下，本文算法PLR_AP分別與PAA[8]、PLR_PF[15]、PLR_FP[16]、PLR_KP[17]四種算法在KData數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)比較，實(shí)驗(yàn)結(jié)果如表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

由實(shí)驗(yàn)結(jié)果可以看出，PLR_AP算法具有較小的擬合誤差，與上述幾個(gè)算法進(jìn)行比較后在多個(gè)數(shù)據(jù)集上具有最小的擬合誤差，且在不是最小擬合誤差的數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果也保持較小水平，證明該算法在多種類(lèi)型的時(shí)間序列數(shù)據(jù)上具有適用性。

3.4 ?算法速度比較

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

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

圖8 ?算法速度比較

Fig.8 ?Comparison of different algorithms speed

4 ?結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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]詹艷艷， 徐榮聰， 陳曉云. 基于斜率提取邊緣點(diǎn)的時(shí)間序列分段線性表示方法[J]. 計(jì)算機(jī)科學(xué)， 2006（11）： 139-142+ 161.

[10]廖俊， 于雷， 羅寰， 穆中林. 基于趨勢(shì)轉(zhuǎn)折點(diǎn)的時(shí)間序列分段線性表示[J]. 計(jì)算機(jī)工程與應(yīng)用， 2010， 46（30）： 50- 53+81.

[11]尚福華， 孫達(dá)辰. 基于時(shí)間序列趨勢(shì)轉(zhuǎn)折點(diǎn)的分段線性表示[J]. 計(jì)算機(jī)應(yīng)用研究， 2010， 27（06）： 2075-2077+2092.

[12]周大鐲， 李敏強(qiáng). 基于序列重要點(diǎn)的時(shí)間序列分割[J]. 計(jì)算機(jī)工程， 2008， 34（23）： 14-16.

[13]孫志偉， 董亮亮， 馬永軍. 一種基于重要點(diǎn)的時(shí)間序列分段算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 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]陳帥飛， 呂鑫， 戚榮志， 王龍寶， 余霖. 一種基于關(guān)鍵點(diǎn)的時(shí)間序列線性表示方法[J]. 計(jì)算機(jī)科學(xué)， 2016， 43（05）： 234-237.