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

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

1(中國科學院 沈陽計算技術研究所,沈陽 110168)

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

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

1 引言

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

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

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

2 基本定義

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

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

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

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

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

3.1 趨勢轉折點

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

圖1 基本趨勢模式

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

圖2 6 種趨勢轉折

圖3 4 種趨勢保持

3.2 上、下層備選點

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

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

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

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

性質.時間序列的上下兩層備選點,分別保留了時間序列上層和下層的重要特征.

3.3 關鍵點

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

3.4 算法描述

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

圖4 算法流程

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

步驟1.提取備選點

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

步驟2.提取關鍵點

遍歷up_v和up_k 數組,若當前點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],即當前上層備選點不是趨勢保持點,那么當前點是關鍵點.將該點的數值信息及位置信息保存到up 集合中,以該點的位置信息作為集合的key 值,該點的數值信息作為集合的value 值;遍歷low_v和low_k 數組,若當前點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],即當前下層備選點不是趨勢保持點,則當前點是關鍵點.將該點的數值信息及位置信息保存到low 集合中.同樣,以該點的位置信息作為low集合的key 值,該點的數值信息作為low 集合的value 值.

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

步驟3.將up 集合和low 集合合并,并按照key值排序.將排好序的數據放入關鍵集合.

步驟4.采用線性插值方法對關鍵點區間進行擬合.

輸出:新的序列.

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

4 實驗分析

4.1 實驗數據

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

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

表1 實驗數據集

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

4.2 實驗方法

本文實驗環境為:Windows10 操作系統、Inter-i5處理器、8 GB 內存.開發環境為Python3.8.

在對實驗數據進行實驗之前,為了保證一致性,本文對數據進行了歸一化處理,即對所有數據進行以下操作:

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

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

4.3 實驗結果及分析

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

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

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

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

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

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

4.4 算法對比

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

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

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

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

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

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

5 總結與展望

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