基金項(xiàng)目：2014年廣西壯族自治區(qū)級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃立項(xiàng)項(xiàng)目（201411548098）。

作者簡(jiǎn)介：通訊作者，范雅靜，女，廣西南寧人，漢族，廣西財(cái)經(jīng)學(xué)院信息與統(tǒng)計(jì)學(xué)院教師。

摘 要：時(shí)間序列在經(jīng)濟(jì)社會(huì)等多個(gè)領(lǐng)域發(fā)揮著重要的作用。然而，時(shí)間序列通常含有較多不規(guī)則波動(dòng)，這些不規(guī)則波動(dòng)易對(duì)時(shí)間序列數(shù)據(jù)挖掘造成影響。因此，對(duì)時(shí)間序列進(jìn)行降噪處理則是一個(gè)亟待解決的問(wèn)題。本文介紹了一種基于光滑曲線去噪算法在分段線性時(shí)間序列中的應(yīng)用方法。通過(guò)對(duì)時(shí)間序列進(jìn)行光滑去噪處理，從而得到去噪后的光滑曲線數(shù)據(jù)，再通過(guò)時(shí)間序列分段線性的方法找出該序列數(shù)據(jù)的關(guān)鍵點(diǎn)，進(jìn)行時(shí)間序列的線性分段擬合。實(shí)驗(yàn)表明：與直接分段擬合相比，先通過(guò)光滑去噪后再進(jìn)行分段線性擬合得到的結(jié)果更好。

關(guān)鍵字：時(shí)間序列；光滑去噪；線性擬合；分段表示；

中圖分類(lèi)號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）12（c）-0000-00

Research of Denoising Algorithm Smooth Curve in the Application of Piecewise Linear Fitting Time Series

HUANG Qiuping CHEN Jucan FAN Yajing LI Jinqing

（School of Information and Statistics， Guangxi University of Finance and Economics， Nanning 530003， Guangxi， China）

Abstract： Time series plays an important role in the economic， society， and other fields. However， time series usually contains many irregular fluctuations which are easy to cause an negative effect on time series data mining. Therefore， noise reduction processing is a problem to be solved. This paper introduced a denoising algorithm based on smooth curve in the application of piecewise linear time series. Smooth curve data is created after removing the time series noise. Then by using the method of time series piecewise linear， data points are found out to fit the original time series. The experiments show that： compared with direct subsection fitting methods， the experiments results are much better by doing smooth denoising firstly and then piecewise linear fitting.

key words： Time series； Smooth denoising； Piecewise linear fitting； Segmentation presentation

引 言：

時(shí)間序列的數(shù)據(jù)挖掘研究是從海量的數(shù)據(jù)中發(fā)掘出有價(jià)值的具有規(guī)律性信息的算法和實(shí)現(xiàn)技術(shù)，廣泛應(yīng)用于工業(yè)、科學(xué)、經(jīng)濟(jì)等領(lǐng)域[1-2]。由于數(shù)據(jù)序列數(shù)據(jù)量大、噪聲干擾嚴(yán)重、短期波動(dòng)頻繁，直接在原始時(shí)間序列上進(jìn)行線性擬合、模式識(shí)別、相似性查詢(xún)等操作，存在工作量大、效率低、耗時(shí)長(zhǎng)等弊端。許多研究者提出相關(guān)的時(shí)間序列的分段線性方法，進(jìn)行時(shí)間序列線性擬合。過(guò)去，國(guó)內(nèi)外眾多學(xué)者對(duì)時(shí)間序列分段先行方法進(jìn)行了研究，并提出極值點(diǎn)擬合法、特征點(diǎn)擬合法、基于關(guān)鍵點(diǎn)擬合法和精確的時(shí)間序列擬合法等多種方法，這些方法都能夠較好地將原時(shí)間序列分段并擬合。而本文試圖在此基礎(chǔ)上，先對(duì)原時(shí)間序列進(jìn)行光滑處理，再分別利用不同的方法提取原時(shí)間序列分段點(diǎn)，并評(píng)價(jià)該點(diǎn)用于原時(shí)間序列擬合時(shí)的效果。

1.相關(guān)算法介紹

1.1 時(shí)間序列分段線性算法

極值點(diǎn)擬合法是利用原時(shí)間序列數(shù)據(jù)的單調(diào)變化屬性提取其中重要的特征數(shù)據(jù)，這些數(shù)據(jù)點(diǎn)均為原時(shí)間序列的極值點(diǎn)。對(duì)于原時(shí)間序列數(shù)據(jù) ，其中0

特征點(diǎn)擬合法是對(duì)極值點(diǎn)擬合法的改進(jìn)，利用極值點(diǎn)擬合法提取極值點(diǎn) ，若選出的極值點(diǎn)與前后極值點(diǎn)之間的時(shí)間段與該序列長(zhǎng)度L的比值必須大于某個(gè)閾值C，則和原序列的起點(diǎn)和終點(diǎn)作為特征點(diǎn)保留下來(lái)。計(jì)算公式為： 。其中， 和 分別表示 和 點(diǎn)所在原序列中的位置。

基于關(guān)鍵點(diǎn)的線性擬合方法是對(duì)特征點(diǎn)擬合法的改進(jìn)，在特征點(diǎn)擬合法的基礎(chǔ)上，利用自定義的單調(diào)序列中線距離閾值提取轉(zhuǎn)折點(diǎn)。當(dāng)數(shù)據(jù)序列中的某個(gè)數(shù)據(jù)點(diǎn) 與前后數(shù)據(jù) 、 平均值距離 （e>0）時(shí)，則 為轉(zhuǎn)折點(diǎn)。

精確的時(shí)間序列線性擬合方法將特征點(diǎn)擬合法和斜率法相結(jié)合，在找出時(shí)間序列極值點(diǎn)（保持閾值C）的同時(shí)，通過(guò)斜率的方法提取出時(shí)間序列中的變化轉(zhuǎn)折點(diǎn)。以 為基準(zhǔn)做一條平行于X軸的直線，若 ， 位于 的同側(cè)，則 與前后兩個(gè)相鄰點(diǎn)所確定的線段中，只要有一條線段的斜率大于閾值，則該點(diǎn)是轉(zhuǎn)折點(diǎn)。若 ， 位于 的異側(cè)，所確定的線段的斜率的歐式距離大于閾值，則認(rèn)為是轉(zhuǎn)折點(diǎn)。

1.2 光滑去噪處理算法

光滑去噪聲算法是通過(guò)前后數(shù)據(jù)計(jì)算去除當(dāng)前點(diǎn)的噪聲，在長(zhǎng)度為m的時(shí)間序列中，第i個(gè)點(diǎn)的去噪計(jì)算公式如式（1）所示。

（1）

式（1）中，d為去噪前的時(shí)間序列數(shù)據(jù)，D為去噪后的數(shù)據(jù)，n為光滑度指數(shù)。但是，式（1）并沒(méi)有完全定義所有的D點(diǎn)，例如當(dāng)n等于2，m=100時(shí)，式（1）中的i值將大于等于3且小于等于98， ， 直接套用式（1）可得： 。而 、 的值計(jì)算不能使用式（1）， 、 計(jì)算過(guò)程如下： ， ；對(duì)序列 點(diǎn)的光滑度指數(shù)計(jì)算也存此問(wèn)題，計(jì)算方法參考 、 的算法。

2.模型的建立

過(guò)去，眾多學(xué)者已經(jīng)提出了多個(gè)時(shí)間序列分段線性擬合方法。在國(guó)外，Sanghyun Park等人提出極值點(diǎn)擬合法[3]（IPSegmentation，簡(jiǎn)稱(chēng)IPS）通過(guò)提取極值點(diǎn)來(lái)擬合時(shí)間序列，算法簡(jiǎn)單，運(yùn)算率高，較好的反應(yīng)了原始時(shí)間序列的主要變化模式。在國(guó)內(nèi)，肖輝，胡運(yùn)發(fā)提出特征點(diǎn)擬合法[4]（FPSegmentation，簡(jiǎn)稱(chēng)FPS）進(jìn)行線性擬合，在選取極值的基礎(chǔ)上，引入極值點(diǎn)保持時(shí)間閾值，較好的考慮了噪音處理；杜奕提出基于關(guān)鍵點(diǎn)的擬合方法[5]（KPSegmentation，簡(jiǎn)稱(chēng)KPS）進(jìn)行線性擬合，將已有的極值點(diǎn)和三角形中線的方法相結(jié)合，能夠發(fā)現(xiàn)時(shí)間序列中的變化轉(zhuǎn)折點(diǎn)；王郝楠提出了一種精確的時(shí)間序列線性擬合方法[6]（APSegmentation，簡(jiǎn)稱(chēng)APS），在找出極值點(diǎn)（保持時(shí)間段閾值C）的同時(shí)，通過(guò)斜率的方法將時(shí)間序列中的變化轉(zhuǎn)折點(diǎn)提取出來(lái)，從而更好地近似表示原時(shí)間序列。

本文對(duì)原序列先進(jìn)行平滑處理，去除序列數(shù)據(jù)中的噪音，得到去噪后的光滑曲線數(shù)據(jù)，再分別運(yùn)用上述極值點(diǎn)擬合法、特征點(diǎn)擬合法、基于關(guān)鍵點(diǎn)擬合法和精確的時(shí)間序列擬合法在光滑曲線上提取關(guān)鍵點(diǎn)，進(jìn)行線性擬合，近似表示原時(shí)間序列。本文將這四種方法分別稱(chēng)為SIPSegmentation（簡(jiǎn)稱(chēng)SIPS）、SFPSegmentation（簡(jiǎn)稱(chēng)SFPS）、SKPSegmentation（簡(jiǎn)稱(chēng)SKPS）和SAPSegmentation（簡(jiǎn)稱(chēng)SAPS）。

本文以原時(shí)間序列的壓縮率、擬合絕對(duì)誤差和關(guān)鍵點(diǎn)與絕對(duì)誤差的乘積值作為評(píng)價(jià)指標(biāo)，比較分析直接分段擬合與經(jīng)過(guò)光滑去噪再進(jìn)行分段擬合的這2種方法的擬合結(jié)果。在相同擬合率下，直接比較擬合誤差的大小就可以判斷出哪種方法較好。在不同壓縮率下，無(wú)法通過(guò)擬合絕對(duì)誤差的大小來(lái)直接判斷哪種方法較好，則通過(guò)這2種方法分別進(jìn)行擬合后各自得到的代表原序列的關(guān)鍵點(diǎn)個(gè)數(shù)與誤差率的乘積的比值（W值）來(lái)進(jìn)行分析比較。其中，壓縮率、擬合絕對(duì)誤差和W值的計(jì)算公式分別為：

壓縮率： （2）

擬合絕對(duì)誤差： （3）

W值： （4）

式（2）中，L是原序列長(zhǎng)度，N是找到的關(guān)鍵點(diǎn)的個(gè)數(shù)；式（3）中 是原序列數(shù)據(jù)， 是擬合序列的數(shù)據(jù)。式（4）中，D、E分別代表提取的關(guān)鍵點(diǎn)個(gè)數(shù)和擬合絕對(duì)誤差。下標(biāo)1表示直接分段擬合方法，2表示經(jīng)過(guò)光滑處去噪后再進(jìn)行分段擬合的方法。若W>1，則表明經(jīng)過(guò)光滑去噪后的擬合方法比較好；若W<1，則表明直接分段擬合的方法比較好。四種基于平滑曲線的分段線性時(shí)間序列的計(jì)算流程如圖1所示。

圖1 四種光滑處理后的擬合算法流程圖

3.實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)使用E.Keogh提供的OliveOil數(shù)據(jù)（http：//www.cs.ucr.edu/～eamonn）和股票平安銀行日線數(shù)據(jù)（2001-7-6到2014-7-21）作為實(shí)驗(yàn)數(shù)據(jù)，這2種的序列數(shù)據(jù)長(zhǎng)度不同，其中，前者的序列長(zhǎng)度為570，后者為3000。實(shí)驗(yàn)結(jié)果如表1、2所示。

表1 OliveOil的實(shí)驗(yàn)結(jié)果

方法IPSSIPSFPSSFPSKPSSKPSAPSSAPS

關(guān)鍵點(diǎn)（個(gè)）5727432052525252

擬合絕對(duì)誤差6.557.406.557.471.521.261.511.34

壓縮率（%）90.0595.2691.9096.5091.7091.7091.7091.70

W1.871.891.211.13

表2 股票樣本的實(shí)驗(yàn)結(jié)果

方法IPSSIPSFPSSFPSKPSSKPSAPSSAPS

關(guān)鍵點(diǎn)（個(gè)）998318188179173173174174

擬合絕對(duì)誤差11.0427.6141.9133.3032.3027.7833.9429.07

壓縮率（%）50.1084.1090.6091.0591.3591.3591.3091.30

W1.251.321.171.17

由表可知，在相同g的壓縮率下，光滑去噪后再進(jìn)行分段線性擬合方法的結(jié)果比直接分段線性的擬合方法的結(jié)果好；在不同的壓縮率下，W（IPS）和W（FPS）都大于1，這都說(shuō)明了基于光滑曲線的分段線性時(shí)間序列合方法的擬合結(jié)果比較好。

4.結(jié)論

本文使用2種不同的數(shù)據(jù)檢驗(yàn)光滑去噪算法在分段線性擬合時(shí)間序列中的應(yīng)用效果，從實(shí)驗(yàn)結(jié)果來(lái)看，經(jīng)過(guò)去噪后再進(jìn)行IPS、FPS、KPS和APS四種時(shí)間序列分段擬合可以取得更好的擬合結(jié)果。本文方法可以提高時(shí)間序列數(shù)據(jù)的擬合效果，但需要指出的是，由于實(shí)驗(yàn)數(shù)據(jù)有限，本方法有可能會(huì)在其他時(shí)間序列數(shù)據(jù)擬合應(yīng)用中帶來(lái)擬合誤差的上升。

參考文獻(xiàn)

[1] Wiegand T，Sullivan G J，Bjontegaard G，et al.Overview of the H.264/AVC Video Coding Standard[J].IEEE Transactions on Circuits and Systems for Video Technology，2003，13（7）：560-576

[2] Joint Video Team.H.264/AVC Reference Software Version JM17.2[EB/OL].（2010-05-21）.http：//iphome.hhi.de/suehring/tml/ download/

[3] Sanghyun Park，Sang-WookKim，Wesley W.Chu.Segment-Based APProach for Subsequence searches in sequence Databases[C].Proceedings of the 16th ACM symposium on Applied Computing.NewYork：ACM Press.2001：248-252.

[4] 肖輝，胡運(yùn)發(fā).基于分段時(shí)間彎曲距離的時(shí)間序列挖掘[J].計(jì)算機(jī)研究與發(fā)展.2005，0l：72-78.

[5] 杜奕.時(shí)間序列挖掘相關(guān)算法研究及應(yīng)用[D].合肥：中國(guó)科技技術(shù)大學(xué)，2007

[6]王郝楠.時(shí)間序列的線性化表示研究[D].遼寧：遼寧師范大學(xué)，2012

[7] 趙建秀，王洪國(guó)，邵增珍，張?jiān)?，丁艷輝.一種基于信息熵的時(shí)間序列分段線性表示方法[J]. 計(jì)算機(jī)應(yīng)用研究.2013，08：2391-2394