江藝羨，張岐山（福州大學(xué) 經(jīng)濟(jì)與管理學(xué)院，福州 350108）

基于重要點(diǎn)與灰色GM（1,1）模型的時(shí)間序列分段算法

江藝羨，張岐山
（福州大學(xué) 經(jīng)濟(jì)與管理學(xué)院，福州 350108）

重要點(diǎn)分段法主要利用局部極值點(diǎn)進(jìn)行劃分，可以將時(shí)間序列分割成若干個(gè)相對(duì)較短但不重疊的子序列。該方法在進(jìn)行序列劃分時(shí)，能夠既保留全局特征，又保持局部性質(zhì)，是時(shí)間序列分段常用的方法之一。文章采用重要點(diǎn)分割法將序列分割成子序列，之后采用灰色GM（1,1）模型對(duì)各個(gè)子序列進(jìn)行擬合。實(shí)驗(yàn)證明，基于灰色GM（1,1）模型與重要點(diǎn)的時(shí)間序列分段算法能夠以更少的擬合誤差，實(shí)現(xiàn)序列的壓縮。

GM（1,1）模型；重要點(diǎn)；時(shí)間序列；分段表示

0 引言

時(shí)間序列作為數(shù)據(jù)庫(kù)中的一種數(shù)據(jù)形式，在商業(yè)、氣象、工程等領(lǐng)域普遍存在。時(shí)間序列數(shù)據(jù)均有“高維”、“海量”等特點(diǎn)，對(duì)其直接分析或處理的難度較大。因此，需要對(duì)時(shí)間序列進(jìn)行降維，目前分段算法主要有限制分段數(shù)、限制分段誤差以及提取特殊點(diǎn)三種類型。提取特殊點(diǎn)的分段算法主要有界標(biāo)模型法、邊緣點(diǎn)分段法、重要點(diǎn)分段法[1]。采用特殊點(diǎn)的提取方法，能夠盡可能較好地保留序列的全局特征的同時(shí)保持序列局部性質(zhì)。目前較多文獻(xiàn)使用線段表示各子序列。線性的表示方式比較簡(jiǎn)單直觀，但在現(xiàn)實(shí)生活中，采用線性的表示方式會(huì)造成較大的數(shù)據(jù)誤差，因此采用曲線的表示方式更具有現(xiàn)實(shí)意義。目前有采用二次回歸以及多項(xiàng)式的表達(dá)式，但這些方法需要較大的計(jì)算量，有時(shí)表示方法不合適時(shí)，會(huì)降低擬合效果?；疑獹M（1,1）模型建模方法簡(jiǎn)單，且具有單調(diào)性，易于后續(xù)子序列的處理；模型又具有曲線的性質(zhì)，相對(duì)線性擬合方法，能有更好的擬合精度。本文首先采用重要點(diǎn)分段法確定時(shí)間序列的分段數(shù)，之后利用灰色GM（1,1）模型對(duì)各子序列進(jìn)行擬合，提出基于重要點(diǎn)與灰色GM（1,1）模型的時(shí)間序列分段算法。

1 重要點(diǎn)定義

通過(guò)序列重要點(diǎn)可以將時(shí)間序列分割成若干個(gè)相對(duì)較短但不重疊的子序列，從而達(dá)到降低時(shí)間復(fù)雜度的目的。重要點(diǎn)分段法主要利用局部極值點(diǎn)進(jìn)行描述，因此重要點(diǎn)的選擇尤為重要。本文借鑒文獻(xiàn)[2]的分割算法。該算法在固定分段點(diǎn)的情況下采用重要點(diǎn)探測(cè)技術(shù)對(duì)時(shí)間序列進(jìn)行分段，能較好地描述時(shí)間序列的整體特征。相關(guān)定義如下：

定義1（時(shí)間序列）：時(shí)間序列是一系列的觀測(cè)值和觀測(cè)時(shí)間組成的有序集合，記為Q=(X1，X2，…，Xn)，其中點(diǎn)Xi的記錄值為x(ti)。

定義2（重要點(diǎn)）：任意時(shí)間序列Q=(X1，X2，…，Xn)，對(duì)于?Xi，i∈[1，n]，若Xi與相鄰兩重要點(diǎn)Xp與Xq連線的垂直距離di→Lpq（公式如下）最大，則Xi為序列重要點(diǎn)。

其中，點(diǎn) Xp與點(diǎn) Xq已經(jīng)確定為序列重要點(diǎn)，且p＜q。如圖1所示，若di→Lpq＞dj→Lpq，則 Xi為重要點(diǎn)，則構(gòu)成(Xp，Xi)與(Xi，Xq)兩個(gè)子序列。

圖1序列重要點(diǎn)圖示

重要點(diǎn)確定后，可根據(jù)需要對(duì)各子序列進(jìn)行擬合。之后計(jì)算擬合誤差以及壓縮率。序列分割后的擬合誤差以及壓縮率的定義可參考文獻(xiàn)[3]。

時(shí)間序列通過(guò)上述重要點(diǎn)確定分段數(shù)后，采用灰色GM（1,1）模型對(duì)各分段進(jìn)行擬合。該模型建模方法簡(jiǎn)單，且具有單調(diào)性，易于后續(xù)對(duì)子序列的處理；模型又具有曲線的性質(zhì)，相比線性擬合方法，能有更好的擬合精度。

2 灰色GM（1,1）模型

灰色GM（1,1）模型是解決特殊的實(shí)際問(wèn)題而產(chǎn)生的，只要系統(tǒng)符合灰建模的條件，其建模過(guò)程的相關(guān)研究在理論和應(yīng)用中都是有意義的[4]。因此對(duì)于本文采用灰色GM（1,1）模型對(duì)子序列進(jìn)行擬合。相關(guān)定義如下：

定義3：設(shè) X（0）=(x(0)(1)，x(0)(2)，…，x(0)(n))為非負(fù)序列，稱 X(1)=(x(1)(1)，x(1)(2)，…，x(1)(n))為 X（0）的一階累加生成算子（1-AGO）序列，其中，…，n)；Z(1)=(z(1)(2)，z(1)(3)，…，z(1)(n))為 X(1)的緊鄰均值生成序列，其中，

定義4：設(shè)X（0），X(1)，Z(1)如定義3所述，若?=[a，b]T為參數(shù)列且滿足式（5）則稱GM（1,1）模型x(0)(k)+az(1)(k) =b的最小二乘估計(jì)參數(shù)列滿足?=(BTB)-1BTY。

定理1：設(shè)Y，B，a?如上所述，u?=(BTB)-1BTY，則有：

（2）灰色微分方程 x(0)(k)+az(1)(k)=b的時(shí)間響應(yīng)式為：

其中k=1，2，…，n。

（3）還原值為：

其中k∈[2，n]。

因此本文采用指數(shù)序列灰色GM（1,1）模型對(duì)時(shí)間序列的各子序列進(jìn)行擬合，在重要點(diǎn)分段前提下，實(shí)現(xiàn)對(duì)時(shí)間序列的數(shù)據(jù)壓縮，并盡可能保留原始序列的數(shù)據(jù)特征。

3 算法描述

根據(jù)以上定義，提出基于重要點(diǎn)與灰色GM（1,1）模型時(shí)間序列分段算法，簡(jiǎn)記為GMPR-IP。算法步驟如下：

算法輸入：時(shí)間序列Q=(x (t1)，x(t2)，…，x(tn))，分段數(shù)num

算法輸出：GMPR-IP

算法步驟如下：

（1）以第一個(gè)點(diǎn)X1與最后一個(gè)點(diǎn)Xn為重要點(diǎn)IPs和IPe。時(shí)間序列端點(diǎn)序列為queue=[1，n，ε1，ip，comp，a，b]。其中，1表示子序列的起點(diǎn)，n表示子序列的終點(diǎn)，ε1表示該子序列進(jìn)行擬合后的平均擬合誤差，ip判斷該子段是否為目標(biāo)子序列，取值為0或1，comp判斷該子段是否已經(jīng)處理過(guò)，取值為0或1，a，b為模型擬合參數(shù)。

（2）判斷queue中，各子段是否已經(jīng)都處理過(guò)，如果有未處理子段，即某子段對(duì)應(yīng)的comp=0，進(jìn)入步驟（3）；如果已經(jīng)都處理完，即queue各子段對(duì)應(yīng)的comp均為1，則進(jìn)入步驟（4）。

（3）在queue中comp=0的各行中，提取平均擬合誤差εi最大的子序列xi。如果分段數(shù)不小于num，則該子序列對(duì)應(yīng)的，ip=1，comp=1；否則，利用重要點(diǎn)分段算法確定該子序列間的下一個(gè)重要點(diǎn)，將子序列分成兩個(gè)更小的子序列xk與xk+1，利用定理1所述灰色GM（1,1）模型進(jìn)行序列擬合計(jì)算平均擬合誤差εk+1，εk+2，將各子段信息加入對(duì)列queue中，并令xi在queue中的comp=1。

（4）取 queue中ip=1的各行構(gòu)成重要子段對(duì)列ip_queue。

（5）利用ip_queue中模型參數(shù)獲得序列的擬合值，計(jì)算序列整體擬合誤差以及壓縮率。

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

為了測(cè)試本文方法的有效性，本文在一臺(tái)硬件配置為2.0GHzCPU、2GB內(nèi)存，軟件配置為Windows XP的電腦上，采用MATLAB 7.0進(jìn)行實(shí)驗(yàn)。

算例：實(shí)驗(yàn)采用Keogh等人提供的實(shí)際數(shù)據(jù)集[5]，數(shù)據(jù)集長(zhǎng)度見(jiàn)表1。

表1 Keogh等人提供的實(shí)際數(shù)據(jù)集

文獻(xiàn)[6]介紹的分段表示算法對(duì)應(yīng)各數(shù)據(jù)集的擬合誤差見(jiàn)表2。各參考算法中，IP算法整體擬合效果最好。本文所提GMPR_IP算法在同等80%壓縮率下的數(shù)據(jù)擬合誤差最小。整體擬合效果最理想。表2中同時(shí)列出GMPR_IP算法在壓縮率為85%，90%，95%時(shí)的擬合誤差。從表中數(shù)據(jù)可知，隨著壓縮率的增加，擬合誤差逐漸變大。

表2 GMPR_IP算法在不同壓縮率下的擬合誤差

5 結(jié)束語(yǔ)

重要點(diǎn)分段算法是通過(guò)搜索的方式提取序列的特征點(diǎn)。本文將時(shí)間序列的部分重要點(diǎn)作為初始分割點(diǎn)，對(duì)分割后的序列采用灰色GM（1,1）模型進(jìn)行擬合。利用重要點(diǎn)分段算法可以保留軌跡局部特征，灰色GM（1,1）模型能夠以曲線的形式減少擬合誤差，因此本文算法同其他分段表示方法相比具有更好的壓縮效果。

[1]程敏,翁寧泉,劉慶,孫剛,陳小威.基于時(shí)間序列分段的氣象數(shù)據(jù)壓縮算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,23(8).

[2]陳然，戴齊.基于重要點(diǎn)的時(shí)間序列固定分段數(shù)分段算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（9）.

[3]詹艷艷，徐榮聰，陳曉云.基于斜率提取邊緣點(diǎn)的時(shí)間序列分段線性表示方法[J].計(jì)算機(jī)科學(xué)，2006,33（11）.

[4]劉思峰，黨耀國(guó)，方志耕，謝乃明.灰色系統(tǒng)理論及其應(yīng)用[M].北京：科學(xué)出版社，2010.

[5]Keogh E,Folias T.The UCR Time Series Data Mining Archive[EB/ OL].http://www.cs.ucr.edu/～eamonn/TSDMA/index.thml.2009.

[6]廖俊，周中良，寇英信，羅寰.一種基于重要點(diǎn)的時(shí)間序列分割方法[J].計(jì)算機(jī)工程與應(yīng)用，2011,47(24).

（責(zé)任編輯/浩 天）

N941.5

A

1002-6487（2016）24-0028-03

國(guó)家自然科學(xué)基金青年項(xiàng)目（61300104）；福建省自然科學(xué)基金資助項(xiàng)目（2013J01230）

江藝羨（1983—），女，漳州龍海人，博士研究生，研究方向：灰色系統(tǒng)、人工智能、數(shù)據(jù)挖掘。