一種基于重要點(diǎn)的時(shí)間序列分段算法

孫志偉，董亮亮，馬永軍

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

1 引言

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

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

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

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

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

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

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

2 時(shí)間序列的概念和問(wèn)題描述

2.1 相關(guān)概念

2.1.1 時(shí)間序列

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

2.1.2 時(shí)間序列的分段線性表示

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

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

2.1.3擬合誤差

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

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

2.1.4 時(shí)間序列分段線性表示的壓縮率

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

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

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

2.2 時(shí)間序列重要點(diǎn)探測(cè)技術(shù)

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

圖1 重要點(diǎn)分析

2.3 問(wèn)題分析

本文從不同角度提出了自己的三點(diǎn)看法：

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

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

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

圖2 分段與時(shí)序長(zhǎng)度的關(guān)系

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

3 PLR_TSIP算法

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

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

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

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

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

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

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

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

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

基于重要點(diǎn)的時(shí)間序列固定點(diǎn)分段算法輸入?yún)?shù)為時(shí)序數(shù)據(jù)集和壓縮率，實(shí)驗(yàn)環(huán)境為：內(nèi)存為8 GB的Intel電腦，開(kāi)發(fā)語(yǔ)言采用Python。實(shí)驗(yàn)數(shù)據(jù)集采用IBM common stock closing prices：daily，29th June 1959 to 30th June 1960原始時(shí)間序列，時(shí)序長(zhǎng)度為255和Keogh[3]等人提供的來(lái)自不同領(lǐng)域的公開(kāi)數(shù)據(jù)集（簡(jiǎn)稱KData數(shù)據(jù)集），KData數(shù)據(jù)集具有良好的廣泛性和代表性，為方便對(duì)比，從KData數(shù)據(jù)集選取了其他論文中常用的11個(gè)作為實(shí)驗(yàn)數(shù)據(jù)，數(shù)據(jù)如表1所示。由于數(shù)據(jù)集中各個(gè)時(shí)間序列來(lái)自不同領(lǐng)域，序列值相差很大，所以為了便于計(jì)算和對(duì)比，在采用固定點(diǎn)分段算法之前首先需要對(duì)時(shí)間序列做[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原始時(shí)間序列長(zhǎng)度為255，原始時(shí)間序列如圖5所示，當(dāng)選擇的壓縮段數(shù)為50時(shí)，擬合效果如圖6所示，可以直觀地看出，壓縮后的序列很好地保留了總體的趨勢(shì)。

圖5 股票原時(shí)間序列

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

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

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

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

4.3 算法分段擬合誤差比較

算法的性能通過(guò)在同一壓縮率下，比較分段線性表示序列與原序列的擬合誤差的大小來(lái)確定。在相同壓縮率為80%的情況下，比較PAA[7]、PLR_PF[22]、PLR_FPIP[20]、PLR_TSIP這四種算法的擬合誤差，如表2所示。隨著時(shí)間序列分段數(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í)間序列分段數(shù)的增加，算法擬合誤差在減小，但在相同壓縮率的情況下，PLR_TSIP算法的擬合誤差明顯小于PAA、PLR_PF這兩種算法。

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

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

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

4.4 算法耗時(shí)分析與比較

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

5 結(jié)論

圖10 擬合時(shí)間比較

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