光滑曲線去噪算法在分段線性擬合時間序列中的應用研究

基金項目：2014年廣西壯族自治區級大學生創新創業訓練計劃立項項目（201411548098）。

作者簡介：通訊作者，范雅靜，女，廣西南寧人，漢族，廣西財經學院信息與統計學院教師。

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

關鍵字：時間序列；光滑去噪；線性擬合；分段表示；

中圖分類號：TP31 文獻標識碼：A 文章編號：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

引 言：

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

1.相關算法介紹

1.1 時間序列分段線性算法

極值點擬合法是利用原時間序列數據的單調變化屬性提取其中重要的特征數據，這些數據點均為原時間序列的極值點。對于原時間序列數據 ，其中0

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

基于關鍵點的線性擬合方法是對特征點擬合法的改進，在特征點擬合法的基礎上，利用自定義的單調序列中線距離閾值提取轉折點。當數據序列中的某個數據點 與前后數據 、 平均值距離 （e>0）時，則 為轉折點。

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

1.2 光滑去噪處理算法

光滑去噪聲算法是通過前后數據計算去除當前點的噪聲，在長度為m的時間序列中，第i個點的去噪計算公式如式（1）所示。

（1）

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

2.模型的建立

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

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

本文以原時間序列的壓縮率、擬合絕對誤差和關鍵點與絕對誤差的乘積值作為評價指標，比較分析直接分段擬合與經過光滑去噪再進行分段擬合的這2種方法的擬合結果。在相同擬合率下，直接比較擬合誤差的大小就可以判斷出哪種方法較好。在不同壓縮率下，無法通過擬合絕對誤差的大小來直接判斷哪種方法較好，則通過這2種方法分別進行擬合后各自得到的代表原序列的關鍵點個數與誤差率的乘積的比值（W值）來進行分析比較。其中，壓縮率、擬合絕對誤差和W值的計算公式分別為：

壓縮率： （2）

擬合絕對誤差： （3）

W值： （4）

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

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

3.實驗結果與分析

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

表1 OliveOil的實驗結果

方法IPSSIPSFPSSFPSKPSSKPSAPSSAPS

關鍵點（個）5727432052525252

擬合絕對誤差6.557.406.557.471.521.261.511.34

壓縮率（%）90.0595.2691.9096.5091.7091.7091.7091.70

W1.871.891.211.13

表2 股票樣本的實驗結果

方法IPSSIPSFPSSFPSKPSSKPSAPSSAPS

關鍵點（個）998318188179173173174174

擬合絕對誤差11.0427.6141.9133.3032.3027.7833.9429.07

壓縮率（%）50.1084.1090.6091.0591.3591.3591.3091.30

W1.251.321.171.17

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

4.結論

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

參考文獻

[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] 肖輝，胡運發.基于分段時間彎曲距離的時間序列挖掘[J].計算機研究與發展.2005，0l：72-78.

[5] 杜奕.時間序列挖掘相關算法研究及應用[D].合肥：中國科技技術大學，2007

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

[7] 趙建秀，王洪國，邵增珍，張岳，丁艷輝.一種基于信息熵的時間序列分段線性表示方法[J]. 計算機應用研究.2013，08：2391-2394