基于時間序列波動性的分段線性表示方法①

李 穎,于 東,胡 毅,劉勁松,張麗鵬

1(中國科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽 110168)

2(中國科學(xué)院大學(xué),北京 100049)

3(沈陽中科數(shù)控技術(shù)股份有限公司,沈陽 110168)

1 引言

在這個信息化時代中,隨著計(jì)算機(jī)技術(shù)的高速發(fā)展,信息的產(chǎn)生、收集和存儲能力不斷增強(qiáng),產(chǎn)生了越來越多的數(shù)據(jù).數(shù)據(jù)類型不斷增多:圖像、文本、音頻等.時間序列型數(shù)據(jù)不僅只在時間上具有前后關(guān)系,任何邏輯上具有先后關(guān)系且不可改變的數(shù)據(jù)都是時間序列型數(shù)據(jù).所以,時序數(shù)據(jù)廣泛存在于各個數(shù)據(jù)類型中.因此,時間序列型數(shù)據(jù)得以在醫(yī)療診斷、工業(yè)生產(chǎn)與控制、運(yùn)動檢測、生物識別、考古研究等生活的各個領(lǐng)域中應(yīng)用廣泛.但是,通常采集到的時序型數(shù)據(jù)在一個維度上會不斷增加,所以時間序列型數(shù)據(jù)具有數(shù)據(jù)維度高、數(shù)據(jù)量大[1]的特點(diǎn).若直接使用傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)對時間序列數(shù)據(jù)進(jìn)行分析不僅需要耗費(fèi)大量的時間和存儲成本[2],還很可能難以分析,得不到結(jié)果.

為了在保留時間序列有效特征的前提下,減少數(shù)據(jù)量,對數(shù)據(jù)進(jìn)行壓縮,Keogh、Chu和Hart 提出了PLR[3]表示方法.PLR 方法是時間序列的分段線性表示方法.該方法的主要思想是從原始時間序列中提取重要特征點(diǎn),用這些特征點(diǎn)連接起來的直線段代表原時間序列.這種方法用尋找到的關(guān)鍵點(diǎn)更直觀地展示了原始時間序列的特征.Ehmke 等[4]提出了自頂向下的TD 方法尋找關(guān)鍵點(diǎn).與文獻(xiàn)[4]不同,Theodosios等[5]以自底向上的BU 方法尋找關(guān)鍵點(diǎn).兩個方法都是時間序列分段線性表示的經(jīng)典算法,但都存在時間復(fù)雜度較高的問題.為了提高查找效率,Chakrabarti 等[6]引入了滑動窗口,降低了查找的時間復(fù)雜度.林意等[7]從時間序列的形態(tài)出發(fā),將其與幾何圖形結(jié)合,提出了PLR_WFTP 方法.詹艷艷等[8]則將斜率變化(PLR_SEEP)作為關(guān)鍵點(diǎn)的判斷指標(biāo).湯晶晶等[9]通過點(diǎn)邊界面積(PLR_AP)作為判斷點(diǎn)的重要性,以此來作為該點(diǎn)是否能成為關(guān)鍵點(diǎn)的依據(jù).肖輝等[10]提出了基于時態(tài)邊緣算子的TEO 方法.

本文研究了時間序列的狀態(tài),發(fā)現(xiàn)了時間序列的波動特性,在結(jié)合前人研究的基礎(chǔ)上,提出了基于時間序列波動性的分段線性表示方法.該算法將時間序列的趨勢分為上、下兩層,在此基礎(chǔ)上提取關(guān)鍵點(diǎn),將原來3 點(diǎn)之間的比較擴(kuò)大為9 個點(diǎn),很好地保留了時間序列的全局特征.同時,該算法在關(guān)鍵點(diǎn)的提取過程中,忽略了對趨勢變化沒有貢獻(xiàn)的點(diǎn).在提取連續(xù)型趨勢段中的關(guān)鍵點(diǎn)時得到的點(diǎn)數(shù)更少,結(jié)果更精確,有更小的擬合誤差.

2 基本定義

定義1.時間序列.X(t)={x(t1),x(t2),x(t3),…,x(tm)}是一個長度為m的有序數(shù)據(jù)集合.其中x(ti)=＜xi,ti＞,(i=1,2,3,…,m;m∈N+)表示X在ti時刻采集到的數(shù)據(jù)值為xi,xi可以是單個數(shù)據(jù)值,也可以是一個數(shù)據(jù)集合.通常,t1=0,Δt=1,(Δt=ti?ti?1).因此,時間序列X可簡單地記為X={x1,x2,xi,…,xm},(m≥1,m∈N+).當(dāng)數(shù)據(jù)空間的維度為N時,該時間序列的每個數(shù)據(jù)項(xiàng)都有n個分量,則X的第i個數(shù)據(jù)項(xiàng)可表示為:

其中,xij表示xi在第j個維度的分量坐標(biāo)值.本文只考慮數(shù)據(jù)空間為一維的情況,即j=n=1.由于時間序列的廣義化,采集到的數(shù)據(jù)值xi可以是多種類型的,如:符號、文本、圖像、聲音等.本文只考慮xi是實(shí)值型數(shù)據(jù)的情況.

定義2.擬合誤差.設(shè)原時間序列X={x1,x2,x3,…,xn},分段操作得到的分段點(diǎn)集合為X′={x1′,x2′,x3′,…,xk′},其中x1=x1′,xn=xk′,k＜n.線性插值后得到的新時間序列為XC={xc1,xc2,xc3,…,xcn}.定義新時間序列與原時間序列之間的歐式距離為擬合誤差.其公式如下:

定義3.壓縮率.原時間序列X={x1,x2,x3,…,xn},經(jīng)過PLR 算法得到的新時間序列X′={x1′,x2′,x3′,…,xk′}.定義該算法的壓縮率如下:

3 基于時間序列波動性的分段線性表示方法

3.1 趨勢轉(zhuǎn)折點(diǎn)

研究中,觀察到時間序列中的點(diǎn)總是波動的,在整體上呈現(xiàn)出某種趨勢和趨勢變化.研究發(fā)現(xiàn),時間序列的變化可細(xì)分為“上升”、“下降”、“保持”這3 種基本趨勢.基于這3 種基本趨勢,3 個相鄰的時間序列點(diǎn)可呈現(xiàn)出9 種趨勢變化[11].其中有6 種發(fā)生趨勢轉(zhuǎn)折,其余3 種保持趨勢不變.基本趨勢模式如圖1所示.

圖1 基本趨勢模式

時間序列3 點(diǎn)間的趨勢變化模式如圖2、圖3所示.

圖2 6 種趨勢轉(zhuǎn)折

圖3 4 種趨勢保持

3.2 上、下層備選點(diǎn)

研究發(fā)現(xiàn),對時間序列3 點(diǎn)間趨勢變化模式的描述可以擴(kuò)展到整個時間序列.由于序列總是波動的,在某一時間段內(nèi)才穩(wěn)定呈現(xiàn)出上升、下降、保持其中一種趨勢.將這些時間段中的趨勢連接起來,就得到了時間序列整體趨勢變化模式.在對時間序列進(jìn)行分段時,無論是基于斜率[8]的方法還是引入幾何中三角形[9,11–13]的方法,都關(guān)注于極值點(diǎn)和拐點(diǎn).從極值點(diǎn)和拐點(diǎn)中提取重要特征點(diǎn).因此,現(xiàn)有的時間序列分段方法很容易陷入局部最優(yōu)的狀態(tài),從而忽略了時間序列的全局特征.針對現(xiàn)有分段方法忽略了時間序列整體特征這一問題,本文研究了時間序列的發(fā)展趨勢,發(fā)現(xiàn)時間序列的趨勢總是由波動點(diǎn)構(gòu)成的:時間序列中的點(diǎn)總是波動的,不是向上波動就是向下波動.因此可以認(rèn)為,波動點(diǎn)描述了時間序列的變化趨勢.基于此發(fā)現(xiàn),本文提出了時間序列分層的概念,為關(guān)鍵點(diǎn)的選取打下基礎(chǔ).其定義如下:

設(shè)有時間序列X(t)={x(t1),x(t2),x(t3),…,x(tn)}.其中x(ti),i=1,2,3,…,n表示該序列在時刻ti的數(shù)據(jù)值為x(ti),簡寫為xi.

定義4.(上層備選點(diǎn)).對于時間序列中的任意一點(diǎn)xi,若滿足xi＞xi?1或xi＞xi+1,則稱xi屬于上層備選點(diǎn).

定義5.(下層備選點(diǎn)).對于時間序列中的任意一點(diǎn)xi,若同時xi＜xi?1或xi＜xi+1,則稱xi屬于下層備選點(diǎn).

性質(zhì).時間序列的上下兩層備選點(diǎn),分別保留了時間序列上層和下層的重要特征.

3.3 關(guān)鍵點(diǎn)

時間序列分段線性表示方法的主要內(nèi)容是找到時間序列中的關(guān)鍵點(diǎn),即時間序列中左右兩邊趨勢發(fā)生變化的點(diǎn).由時間序列3 點(diǎn)間的趨勢變化模式可知,只有在趨勢轉(zhuǎn)折點(diǎn)處的趨勢才發(fā)生變化.同時,若一個點(diǎn)不是趨勢轉(zhuǎn)折點(diǎn),則它一定是趨勢保持點(diǎn).所以,時序中的點(diǎn)除趨勢保持點(diǎn)以外都是趨勢轉(zhuǎn)折點(diǎn),即關(guān)鍵點(diǎn).基于此發(fā)現(xiàn),本文分別遍歷上、下層備選點(diǎn),判斷其與相鄰備選點(diǎn)之間的大小,若滿足保持趨勢關(guān)系,則剔除掉.遍歷完成之后得到的剩余點(diǎn)就是關(guān)鍵點(diǎn).

3.4 算法描述

算法流程圖,如圖4所示.

圖4 算法流程

輸入:時間序列X={x1,x2,x3,…,x1}

步驟1.提取備選點(diǎn)

比較xi與其相鄰點(diǎn)的大小,若xi＞xi?1則認(rèn)為該點(diǎn)是上層備選點(diǎn).將該點(diǎn)的值保存到up_v 數(shù)組中,該點(diǎn)的位置信息保存到up_k 數(shù)組中;若xi＜xi+1或xi＜xi?1,則認(rèn)為該點(diǎn)是下層備選點(diǎn).將該點(diǎn)的值保存到low_v數(shù)組中,該點(diǎn)的位置信息保存到low_k 數(shù)組中.

步驟2.提取關(guān)鍵點(diǎn)

遍歷up_v和up_k 數(shù)組,若當(dāng)前點(diǎn)up_v[i]不滿足up_v[i+1]＞up_v[i]＞up_v[i?1],同時不滿足up_v[i+1]＜up_v[i]＜up_v[i?1],即當(dāng)前上層備選點(diǎn)不是趨勢保持點(diǎn),那么當(dāng)前點(diǎn)是關(guān)鍵點(diǎn).將該點(diǎn)的數(shù)值信息及位置信息保存到up 集合中,以該點(diǎn)的位置信息作為集合的key 值,該點(diǎn)的數(shù)值信息作為集合的value 值;遍歷low_v和low_k 數(shù)組,若當(dāng)前點(diǎn)low_v[i]不滿足low_v[i+1]＞low_v[i]＞low_v[i?1],同時不滿足low_v[i+1]＜low_v[i]＜low_v[i?1],即當(dāng)前下層備選點(diǎn)不是趨勢保持點(diǎn),則當(dāng)前點(diǎn)是關(guān)鍵點(diǎn).將該點(diǎn)的數(shù)值信息及位置信息保存到low 集合中.同樣,以該點(diǎn)的位置信息作為low集合的key 值,該點(diǎn)的數(shù)值信息作為low 集合的value 值.

注意到,無論是上層備選點(diǎn)還是下層備選點(diǎn)都不包括連續(xù)相鄰三點(diǎn)值相等的情況.這是因?yàn)?在波動點(diǎn)的提取過程中,忽略了不發(fā)生波動的點(diǎn).然而,這對關(guān)鍵點(diǎn)的提取并沒有影響.因?yàn)?關(guān)鍵點(diǎn)只在極值點(diǎn)和拐點(diǎn)中包括.

步驟3.將up 集合和low 集合合并,并按照key值排序.將排好序的數(shù)據(jù)放入關(guān)鍵集合.

步驟4.采用線性插值方法對關(guān)鍵點(diǎn)區(qū)間進(jìn)行擬合.

輸出:新的序列.

從以上的算法描述可以看出,該算法主要分成兩個部分:第1 部分掃描時間序列,提取備選點(diǎn);第2 部分從備選點(diǎn)序列中提取關(guān)鍵點(diǎn).經(jīng)過優(yōu)化,PLRGFKP算法只需對時間序列進(jìn)行一次掃描,其時間復(fù)雜度為O(n).

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

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

本文首先對工業(yè)時序數(shù)據(jù)進(jìn)行分段線性表示,以PCoE 數(shù)據(jù)集中的銑削數(shù)據(jù)集為例,該數(shù)據(jù)集由UC Berkeley 的the BEST lab[14]實(shí)驗(yàn)室提供,記錄了銑削刀片VB 的磨損程度.

為了驗(yàn)證本文算法的適用性.本文選取了來自不同領(lǐng)域的UCR 公開數(shù)據(jù)集[15]中的6 條實(shí)際時間序列作為實(shí)驗(yàn)數(shù)據(jù),并用來比較各算法的性能.其數(shù)據(jù)信息如表1所示.

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

數(shù)據(jù)表中顯示了6 條時間序列的名稱和長度.該數(shù)據(jù)集中包括了長度較短、長度一般、長度較長的3 種時間序列.HandOutLines (HOL)序列長度最長.其中,RefrigerationDevices (RD) 序列呈周期性變化、UWaveGestureLibraryAll (UWLA)序列變化沒有規(guī)律、Phoneme 序列斜率變化集中.

4.2 實(shí)驗(yàn)方法

本文實(shí)驗(yàn)環(huán)境為:Windows10 操作系統(tǒng)、Inter-i5處理器、8 GB 內(nèi)存.開發(fā)環(huán)境為Python3.8.

在對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)之前,為了保證一致性,本文對數(shù)據(jù)進(jìn)行了歸一化處理,即對所有數(shù)據(jù)進(jìn)行以下操作:

其中,min是該時序數(shù)據(jù)中的最小值,max是該時序數(shù)據(jù)中的最大值.該操作將時序數(shù)據(jù)中所有的值都變換到了[0,1]內(nèi).

另外,本文共選取了4 種時間序列分段線性表示算法與本文算法做比較.以原始時間序列作為輸入,新的時間序列作為輸出.分別比較了通過各算法得到的新序列與原始時間序列之間的擬合誤差.本文采用的擬合方式為線性插值法:在每個區(qū)間的兩個端點(diǎn)間插入有限個點(diǎn),依次連接相鄰兩個點(diǎn)得到區(qū)間的直線段,從而將區(qū)間連接起來得到一整條新序列.

4.3 實(shí)驗(yàn)結(jié)果及分析

如圖5所示,是銑削過程中VB 切片磨損程度的原始時間序列.該數(shù)據(jù)集中有數(shù)據(jù)缺失的現(xiàn)象,因?yàn)槿笔?shù)據(jù)對序列沒有直接影響,所以,實(shí)驗(yàn)過程中對缺失值進(jìn)行了丟棄處理.圖6是經(jīng)過分段線性表示后的新序列.由圖可知,新的序列減少了原始序列中的波動,很好地保留了其主要發(fā)展趨勢.

圖5 VB 磨損原始序列(分段表示前)

圖6 VB 磨損PLR 序列(分段表示后)

以UCR 數(shù)據(jù)集中的ECG 信號數(shù)據(jù)為例,圖7和圖8分別是ECG 信號分段線性表示前的序列和ECG信號分段表示后的序列.對比兩圖可知,該線性分段方法在減少波動的情況下,很好地保留了原始時間序列的發(fā)展趨勢.

圖7 ECG 原始序列(分段表示前)

圖8 ECG 的PLR 序列(分段表示后)

4.4 算法對比

擬合誤差是評價時間序列分段線性表示算法的一項(xiàng)重要指標(biāo)[16–19],其計(jì)算方式如式(2)所示.一般來說,擬合誤差越小,得到的新序列對原始時間序列的擬合程度越高,算法的性能越好.表2展示了在壓縮率為80%的情況下,各算法在實(shí)驗(yàn)數(shù)據(jù)上的擬合誤差.

表2 80%壓縮率下各算法擬合誤差

表2中加粗的數(shù)據(jù)表示最小擬合誤差.從表中可以看出,在6 條時間序列中,本文提出的GFKP 在其中4 條時間序列上擬合誤差最小,在另外2 條時間序列上的擬合誤差與最小擬合誤差相差不大.因此,實(shí)驗(yàn)表明本算法具有良好的適應(yīng)性.

壓縮率是評價算法的另一項(xiàng)重要指標(biāo)[20–24],其計(jì)算方式如式(3)所示.壓縮率越高,對數(shù)據(jù)的壓縮程度越高,得到的分段數(shù)目就越小.一般來說,同一個算法的壓縮率越高,擬合誤差也會隨之增加.圖9展示了4 種PLR 算法與本文算法對UWLA 序列在不同壓縮率下的擬合誤差對比.

圖9 各算法在不同壓縮率下的擬合誤差

由圖9可知,隨著壓縮率的增加,擬合誤差逐漸增大,但是,GFKP 算法的擬合誤差始終較低.因此,GFKP算法對原始序列的擬合度較好.

5 總結(jié)與展望

時間序列的線性分段表示方法的主要內(nèi)容是提取時間序列中的關(guān)鍵點(diǎn).通常認(rèn)為關(guān)鍵點(diǎn)來自于極值點(diǎn)和拐點(diǎn),因此大多數(shù)學(xué)者只關(guān)注于時間序列的局部特征,這不僅容易陷入局部最優(yōu)的狀態(tài),還忽略了時間序列整體的發(fā)展趨勢[25–28].針對這一問題,本文提出了基于時間序列波動性的分段線性表示方法.該算法首先提取出時間序列的波動點(diǎn),保留時間序列的發(fā)展趨勢.在此基礎(chǔ)上,找到關(guān)鍵點(diǎn).依次將找到的若干個關(guān)鍵點(diǎn)用線性插值的方法進(jìn)行擬合,擬合的結(jié)果就是時間序列的GFKP 表示.GFKP 表示算法計(jì)算簡單、容易實(shí)現(xiàn)、時間復(fù)雜度O(n).該算法不僅能夠在工業(yè)時序數(shù)據(jù)上取得良好的分段效果,與其他分段線性表示算法相比,能夠更好地體現(xiàn)出時間序列的發(fā)展趨勢和全局特征,且有較小的擬合誤差和較好的適應(yīng)性.接下來將研究時間序列的特征轉(zhuǎn)換.時間序列的重要特征信息主要存在于其關(guān)鍵點(diǎn)中.時間序列的特征轉(zhuǎn)換是指在提取到關(guān)鍵點(diǎn)后,轉(zhuǎn)化這些特征,使其可以結(jié)合主流的數(shù)據(jù)挖掘算法進(jìn)行研究,這是一個有價值的研究方向.