一種基于重要點的時間序列分段算法

孫志偉，董亮亮，馬永軍

天津科技大學(xué) 計算機科學(xué)與信息工程學(xué)院，天津 300222

1 引言

時間序列是指按照時間先后順序排列的各個觀測記錄的有序集合，廣泛存在于商業(yè)、經(jīng)濟、科學(xué)工程和社會科學(xué)等領(lǐng)域。隨著時間的推移，時間序列通常包含大量的數(shù)據(jù)。如何對這些時間序列數(shù)據(jù)進行統(tǒng)計和分析，從中發(fā)現(xiàn)一些有價值的信息和知識，一直是用戶感興趣的問題。近年來，時間序列數(shù)據(jù)上的數(shù)據(jù)挖掘研究受到普遍關(guān)注，包括關(guān)聯(lián)規(guī)則挖掘、相似性查詢、模式發(fā)現(xiàn)、異常檢測等。由于時間序列數(shù)據(jù)的海量和復(fù)雜的特點，直接在時間序列上進行數(shù)據(jù)挖掘，不但在儲存和計算上要花費高昂代價，而且可能會影響算法的準確性和可靠性。為了提高數(shù)據(jù)挖掘算法的準確度和有效性，需要首先對時間序列做預(yù)處理，以一種精簡的近似表示來代替原始的時間序列數(shù)據(jù)。

人們對時間序列數(shù)據(jù)的近似研究做了大量的研究工作，國內(nèi)外提出了很多時間序列模式表示的方法[1-2]：基于頻域方法[3]，基于奇異值分解、符號化[4]表示方法以及分段線性表示[5-6]方法。分段線性表示（Piecewise Linear Representation）方法是通過提取原時間序列上反映序列趨勢走向的主要特征點，用連續(xù)的、首尾相連的直線段來近似表示原序列，具有簡單直觀，數(shù)據(jù)壓縮率高等特點，是一種數(shù)據(jù)壓縮和消除噪聲的有效方法，因此對時間序列線性表示的研究具有重要意義。

按照分段方法的不同，基于分段的表示法可分為以下幾種：

第一種稱為PAA（分段近似聚合），通過對時間序列進行等間隔劃分，用每一段的平均值來近似描述整個序列[7-8]，即將給定時間序列轉(zhuǎn)換為只包括K個直線段的近似序列，但是不能控制每一子段和全段的誤差。PAA方法在不考慮實際序列形狀的情況下，僅僅采用等分的方法，不能很好地保留原始序列的變化趨勢。

第二種稱為PLR（分段線性表示），將時間序列數(shù)據(jù)表示為相鄰的線段簇，用若干條首尾相鄰的直線段來近似代替原有時間序列，間隔并不一定相等。對于每個分段內(nèi)部，一般采用線性插值或者線性回歸的方法擬合數(shù)據(jù)。分段線性表示方法一種是采用擬合誤差的方法進行分段，代表人是Keogh[3]。在Keogh的分段表示方法中，分段近似的目標是使原時間序列與其線性近似表示之間的殘差平方和最小。這種方法又可以細分為兩種：其一使用局部閾值來控制單個分段，讓當前子段的誤差不超過該局部閾值，其二是使用全局閾值，讓所有分段的誤差和不超過該閾值。文獻[9]介紹了三種該類型的具有代表意義線性分段算法：即滑動窗口（SW）、自頂向下（TD）、自底向上（BU）。其中，SW支持時間序列的在線分段，但分段效果一般[10]，而且不支持保留分段歷史信息以及二次擬合[11]。相比之下，TD和BU算法盡管分段效果較好，但不支持對時間序列進行在線分段[12]，而且算法空間復(fù)雜度較高。此外，文獻[13]提出了一種基于時態(tài)邊緣算子的時間序列分段算法，文獻[14]提出一種基于斜率提取邊緣點的時間序列分段算法，基于斜率提取邊緣點的時間序列分段線性表示方法中提出了基于某點與左右兩側(cè)相鄰點之間連線的斜率差來進行判斷的方法，斜率差大于某個閥值時，即將其加入邊緣點的集合。基于時間序列趨勢轉(zhuǎn)折點的分段線性表示法將極值點和變化幅度大于某一閥值的點列為轉(zhuǎn)折點[15]。上述度量方法的共同缺陷是需要事先指定一些不容易確定的參數(shù)，如斜率的閥值、變化幅度的閥值，并且只考慮了局部的情況，對整體考慮不足。

另外分段線性表示還包括采用尋找重要點的方法，主要是存儲對序列走勢有重要影響的點[16-18]。而基于重要點的方法很符合人們的視覺印象，可以保留整個序列中重要的趨勢情況，但需要準確對重要點進行定義。周大鐲等證明了正交距離和垂直距離的等效性，并提出了基于序列重要點分割算法PLR_SIP[19]。該方法采用遞歸調(diào)用的方法，一直對最左側(cè)序列進行分解，直到擬合誤差小于用戶指定的某個值，不能根據(jù)用戶的需要找出最重要的指定個數(shù)的點，即用戶參數(shù)不易設(shè)定，無法根據(jù)用戶的需要選擇壓縮的程度。陳然[20]提出的基于重要點的時間序列固定分段數(shù)分段算法，采用每一段的擬合誤差作為優(yōu)先級的標準，同時設(shè)置了誤差閾值作為輸入?yún)?shù)，但是誤差閾值的參數(shù)值不太好估計。

本文提出的方法通過分析原始曲線與擬合曲線，首先考慮到了擬合誤差的大小和序列長度，接著針對優(yōu)先級較高的分段進行預(yù)分段處理以期找到最優(yōu)的分段，并在分段時考慮分段中多個重要點（最大值點和最小值點）的同異向關(guān)系，可以一次劃分成多段，從而在壓縮率一定的情況下，保證了反應(yīng)時間序列曲線總體特征的同時，大大提高了固定點分段的效率；而且方法參數(shù)容易確定，除數(shù)據(jù)集外只需要輸入壓縮率或者分段數(shù)量，用戶非常容易確定。

2 時間序列的概念和問題描述

2.1 相關(guān)概念

2.1.1 時間序列

時間序列數(shù)據(jù)中間的每個觀察結(jié)果可形式化定義為元組(v,t)。v為待觀察變量的值，可以是股票的價格、某地的溫度、網(wǎng)絡(luò)事件的評價等；t為觀察時刻的時間戳，一個時間序列包含若干個這樣的元組{(v1,t1),(v2,t2),…,(vn,tn)}，其中t1,t2,…,tn，按照時間先后順序有序排列。一般情況下，時間序列的采樣間隔時間Δt=ti-ti-1相等，可以看出t1=0,Δt=1，此時將時間序列X={x1=(v1,t1),x2=(v2,t2),…,xn=(vn,tn)}簡記為X={x1,x2,…,xn}。

2.1.2 時間序列的分段線性表示

設(shè)有時間序列X=

其中，wi表示時間區(qū)間[wi-1,wi]的兩個端點的坐標，fi(t,wi)表示連接模式wi兩端點的線性函數(shù)，ek(t)是一段時間內(nèi)時間序列與它的模式表示之間的誤差。

2.1.3擬合誤差

設(shè)時間序列，通過線性分段算法得到時間序列的PLR表示為：

其中L(?,?)表示連接兩點的直線段。將L(X)經(jīng)過線性插值后得到的時間序列記為，那么該PLR表示與原始時間序列之間的擬合誤差定義為：

2.1.4 時間序列分段線性表示的壓縮率

設(shè)時間序列X=

2.1.5 時間序列分段擬合差值的最大值和最小值

分段擬合差值定義為原始曲線與擬合曲線對應(yīng)的點做差，表示為（參照垂直距離計算），擬合誤差的最大值定義為一段時間序列中，擬合差值的最大值，表示為，分段擬合誤差的最小值，定義為一段時間序列中，擬合差值的最小值，表示為

2.2 時間序列重要點探測技術(shù)

重要點探測技術(shù)最早由Chung[21]等提出，在時間序列分段算法中可用該方法生成一連串重要點序列作為時間序列的分段點，從而達到線性擬合的目的，重要點即是時間序列中dis最大的點，dis見公式（2），如圖1所示，對于整段序列來說，點B是距離序列首尾連線垂直距離最大的點（文獻[19]中，周大鐲等已經(jīng)證明使用垂直距離相對于使用正交距離的優(yōu)越性），所以點B是序列重要點。垂直距離：從B向AC引垂直線段，與AC交于D,BD的長度，即：

圖1 重要點分析

2.3 問題分析

本文從不同角度提出了自己的三點看法：

（1）在圖2中，A段表示時間序列中X軸為0～3表示的分段，B段表示時間序列中X軸5～6表示的分段，按照擬合誤差的公式（1）計算，A段的擬合誤差比B段的擬合誤差稍大，如果按照陳然[20]提出的分段優(yōu)先級按照擬合誤差的大小進行排序，應(yīng)該先對A段進行分段，但是，顯然B段的波動比A段更大，而且B段只需要一次分段即可更好地擬合，因此B段應(yīng)該優(yōu)先分段，所以只考慮擬合誤差的排序是不合理的。不僅要考慮分段總誤差對時間序列的影響，還要考慮分段所包含的時序長度對時間序列分段優(yōu)先級的影響。對以往的時間序列重要點按照分段擬合誤差比較的分段算法進行了改進，先將分段按照擬合誤差大小進行排序，然后選取指定數(shù)的分段按照分段包含的點數(shù)由小到大進行排序。

（2）從之前先按照擬合誤差排序，后按照分段包含的點數(shù)排列的優(yōu)先級隊列中，選取前兩個分段，進行預(yù)處理，即模擬進行各自按照重要點分段之后，將分段之后的擬合誤差與之前分段的擬合誤差作比較，分段之后擬合誤差減小的多的分段優(yōu)先進行分段，表示采用該段進行分段之后，擬合誤差會減小得更快，此方法考慮了分段的連續(xù)性，從而讓擬合誤差減小的多的分段優(yōu)先分段。

（3）在進行模擬分段預(yù)處理和實際分段時，陳然[20]直接采用垂直距離最大的點將某一分段一分為二，然后逐一進行分段，分段的效率并不高，實際的重要點的分布經(jīng)常是連續(xù)的，與具體的時間序列有關(guān)。如圖3所示，時間序列片段x=1的點為最大值點，時間序列片段x=3的點為最小值點，分別為重要點，需要進行分段，使用固定點分段算法需要分段兩次，才能同時找到x=1和x=3對應(yīng)的點，如果能夠一次同時獲取兩個分段點，將提高分段的效率。通過大量的數(shù)據(jù)觀察測試發(fā)現(xiàn)，經(jīng)常在某一段的最大值點或最小值分段之后，接下來就在該段的最小值點或最大值點進行分段，當某一分段中如果滿足分段的原始曲線與擬合曲線的最大值與最小值符號相反并且或滿足時，可以同時將最大值點與最小值點同時進行分段，從而一分為三，而不是一分為二，有效提升分段的效率。

圖2 分段與時序長度的關(guān)系

圖3 分段與擬合最大值和最小值的關(guān)系

3 PLR_TSIP算法

PLR_TSIP算法執(zhí)行流程如圖4所示，具體描述如下：算法輸入為時間序列X=(x1,x2,…,xi,…,xn)和固定分段數(shù)N或壓縮率，算法輸出為重要點集合IPs。

圖4 PLR_TSIP算法執(zhí)行流程

步驟1對時間序列數(shù)據(jù)X進行歸一化處理，初始化分段點的集合IPs，將時間序列X的起點和終點加入到集合IPs中，將X的起點和終點構(gòu)成的分段加入到優(yōu)先級隊列Q中。

步驟2計算優(yōu)先級隊列Q中新加入的分段擬合誤差，優(yōu)先級隊列Q按照擬合誤差的大小進行排序。

步驟3取出優(yōu)先級隊列Q中按照擬合誤差排列的前k段（默認值為5），對前k段按照時間序列的分段長度進行從小到大排序。

步驟4選出步驟3中分段長度小的前兩段，進行預(yù)處理，即模擬進行各自按照重要點分段之后，將分段之后的擬合誤差與之前分段的擬合誤差作比較，分段之后擬合誤差減小較多的分段優(yōu)先進行分段，將擬合誤差減小的多的分段優(yōu)先進行處理。

步驟5計算通過步驟4獲取的分段的原始曲線與擬合曲線的最大值與最小值，如果滿足符號相 反并且或時，可以同時將最大值點與最小值點作為分段點同時進行分段，從而一分為三，然后將分段起點，最大值點，最小值點，分段終點構(gòu)成的三條時序分段，放到優(yōu)先級隊列Q中，同時固定分段點數(shù)N減2；否則按照重要點進行分段，將由分段的起點，重要點和分段終點構(gòu)成的兩條時序分段按照擬合誤差由大到小的順序加入到優(yōu)先級隊列中，同時分段點的個數(shù)N減1。如果分段點N的個數(shù)大于零，返回執(zhí)行步驟2，當分段點的個數(shù)N為零時，就停止執(zhí)行，輸出重要點集合IPs。

4 實驗與分析

4.1 數(shù)據(jù)集描述

基于重要點的時間序列固定點分段算法輸入?yún)?shù)為時序數(shù)據(jù)集和壓縮率，實驗環(huán)境為：內(nèi)存為8 GB的Intel電腦，開發(fā)語言采用Python。實驗數(shù)據(jù)集采用IBM common stock closing prices：daily，29th June 1959 to 30th June 1960原始時間序列，時序長度為255和Keogh[3]等人提供的來自不同領(lǐng)域的公開數(shù)據(jù)集（簡稱KData數(shù)據(jù)集），KData數(shù)據(jù)集具有良好的廣泛性和代表性，為方便對比，從KData數(shù)據(jù)集選取了其他論文中常用的11個作為實驗數(shù)據(jù)，數(shù)據(jù)如表1所示。由于數(shù)據(jù)集中各個時間序列來自不同領(lǐng)域，序列值相差很大，所以為了便于計算和對比，在采用固定點分段算法之前首先需要對時間序列做[0，1]區(qū)間規(guī)范化處理，規(guī)范化公式如下：

表1 KData數(shù)據(jù)集描述

4.2 擬合結(jié)果

IBM common stock closing prices：daily，29th June 1959 to 30th June 1960原始時間序列長度為255，原始時間序列如圖5所示，當選擇的壓縮段數(shù)為50時，擬合效果如圖6所示，可以直觀地看出，壓縮后的序列很好地保留了總體的趨勢。

圖5 股票原時間序列

圖6 股票數(shù)據(jù)線性擬合（50段）

KData提供的Burst數(shù)據(jù)長度為9 382，原始時間序列如圖7所示，當選擇的壓縮率為80%時，擬合結(jié)果如圖8所示，可以直觀地看出，壓縮后的序列較好地反映了原序列的主題特征。

圖7 原始Burst曲線（9 382段）

圖8 Burst擬合曲線（1 876段）

4.3 算法分段擬合誤差比較

算法的性能通過在同一壓縮率下，比較分段線性表示序列與原序列的擬合誤差的大小來確定。在相同壓縮率為80%的情況下，比較PAA[7]、PLR_PF[22]、PLR_FPIP[20]、PLR_TSIP這四種算法的擬合誤差，如表2所示。隨著時間序列分段數(shù)的增加，PLR_TSIP方法的擬合誤差明顯小于PAA與PLR_PF，PLR_TSIP算法與PLR_FPIP算法相比，擬合誤差的降幅最小為7%，最大為22%，平均為13%。

表2 80%壓縮率下的擬合誤差

比較PLR_TSIP、PLR_PF、PAA這三種算法選用Ocean數(shù)據(jù)集在不同壓縮率情況下的擬合誤差，如圖9所示，隨著時間序列分段數(shù)的增加，算法擬合誤差在減小，但在相同壓縮率的情況下，PLR_TSIP算法的擬合誤差明顯小于PAA、PLR_PF這兩種算法。

圖9 不同壓縮率擬合誤差比較1

比較PLR_TSIP與PLR_FPIP這兩種算法選用Ocean數(shù)據(jù)集在不同壓縮率情況下的擬合誤差，如表3所示，隨著時間序列固定分段數(shù)的增高，PLR_FPIP與PLR_TSIP的擬合誤差都在減小，但PLR_TSIP的擬合誤差要小于PLR_FPIP，PLR_TSIP算法與PLR_FPIP算法相比，擬合誤差的平均降幅為15%，壓縮率較小時甚至可以提高30%以上，非常明顯。

表3 不同壓縮率擬合誤差比較2

4.4 算法耗時分析與比較

PLR_TSIP算法的時間優(yōu)化主要體現(xiàn)在步驟5，與陳然[20]的基于重要點的分段算法相比，時間優(yōu)化主要體現(xiàn)在根據(jù)最大值Vimax與最小值Vimin的符號和大小關(guān)系可以在一次分段的同時得到兩個分段點，而不需要經(jīng)過兩次分段，減少了分段的執(zhí)行次數(shù)，從而提高了分段的效率，降低了算法的時間復(fù)雜度，下文通過實驗加以證明。PLR_TSIP與PAA、PLR_PF相比，由于計算量大，因此執(zhí)行時間較多，但擬合誤差比PAA和PLR_PF降低很多。與同為重要點算法的PLR_FPIP相比，表3表明擬合效果提高很多，此處與PLR_FPIP進行時間效率比較，圖10所示，相同分段數(shù)時，PLR_TSIP要比PLR_FPIP算法效率較高，性能平均可以提高20%以上。

5 結(jié)論

圖10 擬合時間比較

本文提出了一種基于重要點的時間序列的分段方法，避免了讓用戶輸入擬合誤差等難以確定的參數(shù)值，實驗證明，這種方法在保留了原始時間序列的整體特征的基礎(chǔ)上，減小了擬合誤差，并提高了時間效率。在來自不同領(lǐng)域的公開數(shù)據(jù)集上的實驗結(jié)果表明：與傳統(tǒng)的PAA算法和其他主要的分段線性算法PLR_PF、PLR_FPIP相比，該算法具有很好的擬合效果和適應(yīng)性。接下來將進一步研究參數(shù)的合理性，如文中k值選取為固定值5，同時也在對當前的算法進行改進，從而進一步減小擬合誤差，提升算法效率。