基于雙曲正切函數(shù)約束的時間序列建模表示

曹洋洋，林 意，王智博，畢小紅

江南大學 數(shù)字媒體學院，江蘇 無錫 214122

1 引言

時間序列的數(shù)據(jù)挖掘是從大量時間序列數(shù)據(jù)中發(fā)現(xiàn)有價值的規(guī)律性的算法和實現(xiàn)的技術，廣泛應用于經(jīng)濟、科學、工業(yè)等諸多領域[1-2]。但由于時間序列數(shù)據(jù)具有海量性，短期波動，噪聲大等特點，直接在原始時間序列上進行相似性查詢[3-4]、聚類[5-6]、模式挖掘[7-8]等不僅存儲和計算效率低而且影響算法的準確性和可靠性，難以取得滿意的效果。因此，數(shù)據(jù)的高級表示[9]是有效并高效的解決問題的關鍵。常見的時間序列降維方法包括傅里葉變換[10]、奇異值分解（SVD）[11]、符號映射[12]等，與此同時，許多研究人員忽略時間序列的細節(jié)變化，提出了線性表示來描述時間序列的主要特征，本文主要研究最常用的時間序列表示方法PLR。

PLR[13]方法是指將長度為n的時間序列用k個直線段近似表示。PLR中的分段數(shù)決定了原始時間序列的大致粒度，由于擬合誤差與壓縮率呈現(xiàn)反相關的關系，如何在考慮序列的時間特性確定合理分段數(shù)的基礎上選擇適當?shù)姆侄吸c以保證擬合誤差在合理的范圍下壓縮率盡可能低是分段問題的重點。目前已有的PLR算法大體上分為：（1）自定義分段數(shù)算法，如文獻[14]提出了多尺度時間序列固定分段數(shù)線性表示方法（PLR_BTBU）。（2）自定義擬合誤差算法，如滑動窗口（SW）、自底向上（BU）和自頂向下（TD）[15]。（3）選擇有代表性的分段點的算法，如趨勢轉折點[16]、重要點[17]以及導數(shù)突變點[18]等來近似表示時間序列的算法。由于分段后k通常比n小得多，降維后的序列使得數(shù)據(jù)的存儲、傳輸和計算效率有明顯的提高。但應用于不同領域的時間序列數(shù)據(jù)往往具有明顯的數(shù)據(jù)特征的差異，同一時間序列在不同的時間段所呈現(xiàn)的數(shù)據(jù)特征也不相同，傳統(tǒng)的分段方法忽略了時間序列的時間特性和不斷增長的性質，得到的分段結果不夠精確，影響時間序列相似性度量和之后的預測工作。

文獻[19]和[20]分別獨立地提出了時間序列分段聚合近似算法。由于該算法簡單直觀，支持任意長度的時間序列的相似性查詢、所有的Minkowski度量以及加權歐氏距離，而且能夠用于索引提高查詢效率，因此該算法具有通用性和普遍性，Keogh等人的實驗結果表明將PAA方法用于時間序列的索引時，查詢效率比DFT表示方法提高了1～2個數(shù)量級[19]，而且能夠用于加權歐幾里德距離的計算。雖然Keogh和Yi等人提出的PAA方法能夠有效地劃分時間序列，對時間序列進行降維，但是在時間序列數(shù)據(jù)不斷增長的過程中，不同區(qū)段的時間序列數(shù)據(jù)對當前時間區(qū)段數(shù)據(jù)的影響是不同的，在當前時間序列區(qū)段的左端，越靠右的區(qū)段對當前時間序列段的影響越大，對時間序列的預測的參考價值越大。而靠左的區(qū)段施加的影響較小，對時間序列預測的參考價值也越小，所以在對時間序列進行分段時引入不同區(qū)段的時間影響因素是有必要的，但PAA對時間序列進行分段時，用均值來表示不同區(qū)段的數(shù)據(jù)，在計算不同區(qū)段數(shù)據(jù)的距離時同等對待，沒有考慮時間序列特有的時間性質。王元珍[21]等考慮了時間序列的時間特性，提出一種PAA的改進方法RPAA，該方法將時間影響因子應用到時間序列的分段中，但RPAA方法將滑動窗口首先作用在時間序列的尾端，然后沿著時間軸逆方向以步長為w的大小移動，計算各區(qū)段的均值以及相應的影響因子，這使得RPAA不能滿足動態(tài)增長的時間序列分段的需求，不能實時在線劃分時間序列，對于時間序列數(shù)據(jù)實際情況是不利的。

針對上述的不足，文章結合PAA算法滿足動態(tài)增長的時間序列的分段要求的優(yōu)點，在RPAA算法的啟發(fā)下提出了基于時間約束滑動窗口的分段線性表示算法（HTFPAA），由于時間序列的時間特性較為復雜，任何模型都不能真正反應序列時間的真實性能。于是在時間的非線性特征尚不十分清楚的情況下，可采用任何計算方便且行之有效地簡化數(shù)學模型或物理模型來描述時間的非線性特征。因此HTFPAA算法構造了一種新的時間非線性模型，在考慮時間序列不斷增長并且與時間高度相關的特性的基礎上，引入的雙曲正切函數(shù)，可以有效度量隨著時間推移當前序列對后繼時間序列段的影響，并且該方法繼承了PAA支持時間序列在線劃分的優(yōu)點，函數(shù)模型形式簡單，物理意義明確，且參數(shù)少，只需記錄當前分段的位置，有利于數(shù)值及編程實現(xiàn)。大量的實驗結果表明與其他PLR算法在相同的壓縮率下進行比較，該算法能夠得到更小的擬合誤差和更好的分類聚類性能。

2 PAA和RPAA分段表示方法

2.1 相關定義

定義1（時間序列）給定一個屬性集X，時間序列是由記錄時間t和記錄值Xi組成的有序集合：對于給定的時間序列，有限時間集為T、非空狀態(tài)屬性集A=及其對應值域Daj。

定義2（時間序列長度）對于有限長的時間序列X=x1,x2,…,xn，X的長度為組成時間序列X的實數(shù)的個數(shù)，記為|X |，即，對于無限長的時間序列，X的長度定義為文章主要討論有限長時間序列的分段方法。

定義3（時間序列子序列段）給定長度為n的時間序列X,X的子序列段s是在X中從點xi開始，數(shù)量為w(1

定義4（滑動窗口）給定長度為n的時間序列X和一個用戶自定義的區(qū)域長度w(1≤w≤n),X的所有子序列矩陣s可以通過在X上定義一個寬度為w的窗口，將每一個區(qū)段s放入s的第s行得到，s的大小為(n-w+1)×w，w為滑動窗口的大小。

2.2 PAA算法及問題描述

Keogh和Yi等人分別獨立地提出了時間序列PAA表示算法，當使用PAA進行時間序列降維時，首先將長度為n的時間序列分成N個大小相同的幀，滑動窗口放在原始序列S的前端，然后沿著時間軸以w個步長移動，計算每個寬度為w的幀中數(shù)據(jù)點的平均值，并按照原始時間表的方向構成索引向量表示原始時間序列。 在N(1≤N≤n)維空間中將長度為n的時間序列S 表示為向量，其中第 i(1≤i≤N)元素計算為：

當N=n時向量表示即為原時間序列；N=1時向量表示原時間序列的均值。

PAA支持時間序列的在線劃分，但由于忽略了不同區(qū)段幀的時間特性對于時間序列數(shù)據(jù)后續(xù)區(qū)段的影響是不同的，靠近當前區(qū)段的時間段的對當前區(qū)段的影響較大，遠離當前區(qū)段的時間影響較小，序列劃分不夠精確，進而影響到序列的相似性度量以及預測的準確性，導致后續(xù)數(shù)據(jù)挖掘工作出現(xiàn)較大的誤差。

2.3 RPAA算法及問題描述

王元珍等人[21]考慮了時間序列的時間特征，通過在PAA線性分段方法基礎上引入影響因子ρ（其中0≤ρ≤1）提出了RPAA算法，為了避免加入影響因子后，這種按照時間軸方向的運算必須每次都計算當前區(qū)段與最后區(qū)段的位置距離(j-i)而導致ρj-i的多次重復計算，該方法首先將滑動窗口放置在時間序列X的末尾，然后沿時間軸的逆方向以w大小的步長移動并計算各個窗口（大小為w）內幀的平均值和相應的函數(shù)影響系數(shù)，公式為：

由于滑動窗口從原始時間序列的末尾逆向移動，勢必導致RPAA算法無法實現(xiàn)時間序列的在線劃分，不適用于動態(tài)增長的時間序列數(shù)據(jù)流和在線時間序列的劃分。

2.4 歐幾里德距離

歐幾里德距離廣泛應用于時間序列距離計算中，給定長度為n的時間序列C=c1,c2,…,cn和Q=q1,q2,…,qn，則C和Q之間的歐幾里德距離為：

為了防止遞加數(shù)過多，導致歐幾里德距離過大，可以計算加權的歐幾里德距離：

由于函數(shù) f(x)=x2單調，所以在實際計算中，可以計算平方后的加權歐幾里德距離：

PAA支持平方后的加權歐幾里德距離的計算，將一個查詢Q降維表示為：

則此時計算PAA表示平方后的歐幾里德距離為：

3 時間序列的HTFPAA算法

3.1 時間序列的HTFPAA表示算法

考慮到時間序列不同區(qū)段間的影響，文章引入移動增強因子的概念，定義如下。

定義5（移動增強因子）移動增強因子g(x)是取值范圍為[0，1]并且單調遞增的函數(shù)。函數(shù)的意義為兩相鄰區(qū)段中前序時間區(qū)段對后繼時間區(qū)段影響的量化值。

文中引入了雙曲正切函數(shù)g(x)=tanh(x)=(ex-e-x)/(ex+e-x)(0≤x)（如圖1）為移動增強因子。此函數(shù)關于原點（0，0）中心對稱的，在對稱的水平漸近線 y=1和y=-1處收斂，在定義域內有連續(xù)的導數(shù)，當x≥0時，g(x)∈(0,1)且g(x)在定義域的范圍內單調遞增，有較快的收斂速度又有較高的收斂精度，滿足移動增強因子的條件。并且由圖1可知，該函數(shù)的形狀符合序列的時間特性并且函數(shù)的有界性滿足時間窗的基本要求，因此可將雙曲正切函數(shù)引入到時間序列分段聚合近似中。

圖1 雙曲正切函數(shù)圖像

函數(shù)證明如下：

（1）當 x≥0時，雙曲正切函數(shù)的函數(shù)值是（0，1），證明如下：

因此，當x→∞時，ex→∞則

（2）當x≥0時，雙曲正切函數(shù)單調遞增，證明如下：

首先對雙曲正切函數(shù)求導：

由于時間序列是一維的并且隨著時間的增長具有不可逆轉性，所以只有前序數(shù)據(jù)對于后繼數(shù)據(jù)施加影響，反之并不成立。

RPAA考慮了序列的時間特性但不支持時間序列的在線劃分，PAA則恰好相反，因此文章受RPAA算法的啟發(fā)，在時間序列PAA分段中引入雙曲正切函數(shù)，不僅適用于動態(tài)增長的時間序列，而且兼顧了序列的時間特性，不會顧此失彼。

HTFPAA算法計算索引時首先將滑動窗口置于原始時間序列S的前端，然后沿著時間軸方向移動，計算各個窗口的平均值和g(x)的乘積，按照時間軸的方向組成索引向量，此時

同時也可如RPAA方法首先將滑動窗口置于時間序列末端，公式為：

HTFPAA算法支持序列的雙向劃分。算法步驟如下：

輸入：長度為n的時間序列數(shù)據(jù)S=s1,s2,…,sn，滑動窗口的大小為w(1

輸出：時間序列S的HTFPAA表示。

（1）用N=[n/w]計算時間序列總分段數(shù)，最后一段不足w，則所有數(shù)據(jù)作為一段。

（2）分段后的HTFPAA向量為S′=?。

（3）循環(huán)計算不同時間序列段的影響因子：

（5）返回 S′。

3.2 距離計算

歐幾里德距離是歐式空間中評定個體間差異大小的一種測度，其計算相似度是所有相似度計算里面最簡單、最易理解的方法。HTFPAA算法中時間序列的距離計算仍然可以使用平方后加權歐幾里德距離，不影響后續(xù)度量的準確性并且在機器學習社區(qū)中眾所周知，加入的雙曲正切函數(shù)作為權重可以大大提高分類精度，公式如下：

3.3 滿足下界定理

對原始數(shù)據(jù)進行降維處理后，在索引空間的查找可能出現(xiàn)錯查和漏查兩類問題。

錯查：在索引空間中的兩點距離小于給定的閾值ε，但在原始數(shù)據(jù)中該兩點的距離大于ε，即

對序列點出現(xiàn)錯查的情況，一般通過對索引空間中的查詢結果再次到原始數(shù)據(jù)空間中查詢，剔除其中的D(si,sj)≥ε的點來解決。由于在索引空間中查詢的結果只保留了原時間序列數(shù)據(jù)集合中一個很小的子集，所以再次在原始空間中查詢不會耗費太多CPU運行時間。

漏查：在原始數(shù)據(jù)中兩點距離小于給定的閾值ε，但在索引空間中該兩點的距離卻大于ε，即。

序列點的漏查問題則決定了是否能夠對序列進行有效的相似性查找，為了能夠解決這個問題，F(xiàn)aloutsos[23]給出維度下限下界定理，即 Dindex(C,Q)≤D(C,Q)。

證明HTFPAA算法滿足下界定理。

證明由0

又

根據(jù)上面的證明得出DHTFPAA(C,Q)針對DPAA(C,Q)滿足下界定理，又由于DPAA(C,Q)滿足歐幾里德距離的下界定理，因此得出DHTFPAA(C,Q)滿足歐幾里德距離的下界定理，得證。

4 實驗

4.1 實驗數(shù)據(jù)和平臺

實驗使用UCR數(shù)據(jù)集[24]以及Datamarket中的Time series Data Library提供的來自不同領域的數(shù)據(jù)集，與現(xiàn)有的分段算法在擬合誤差，分類聚類性能上比較，評估HTFPAA算法的有效性。數(shù)據(jù)集長短不一并且充分考慮到序列中易出現(xiàn)小幅度波動數(shù)據(jù)和突變數(shù)據(jù)的情況，具有較好的廣泛性和代表性。數(shù)據(jù)集的相關信息以及本文的實驗平臺如表1～表3所示。

表1 UCR數(shù)據(jù)集

4.2 擬合誤差的比較

對Time series中的數(shù)據(jù)分別用HTFPAA算法與基于PAA的分段線性表示算法，基于時間特性的時間序列建模表示算法（RPAA）以及基于自適應窗口的分段線性表示算法（AW）[25]進行分段，比較各算法下數(shù)據(jù)近似質量。由于任何方法都可以通過改變參數(shù)改善擬合質量，為了公平起見，控制在壓縮率相同的情況下比較各算法的擬合誤差，擬合誤差越小，算法的擬合效果越好。由于實驗選自不同領域的數(shù)據(jù)集，取值范圍相差較大，為了方便比較，首先將數(shù)據(jù)歸一化處理，歸一化公式為：

表2 Time series數(shù)據(jù)集

表3 實驗平臺

由于固定滑動窗口算法本身的特點，其壓縮率只能是(1-1/w)×100%，參數(shù)w為正整數(shù)。4種PLR分段算法在同一壓縮率下（文章取w=5即壓縮率為80%），實驗結果如表4所示。

表4 80%壓縮率時幾種PLR表示的擬合誤差

表4中下劃線并且加粗的數(shù)據(jù)表示該行中擬合誤差的最小值。可以看出HTFPAA算法在7條時間序列上具有較小的擬合誤差；而在其他3條時間序列上HTFPAA算法的擬合誤差也接近最小值。而且從擬合誤差的平均值來看，HTFPAA算法擬合誤差的平均值遠遠小于其他3種算法，實驗結果表明，HTFPAA算法在10條數(shù)據(jù)集上的擬合誤差都比較小，算法有良好的適應性。

對上述擬合誤差實驗中表現(xiàn)較好的7條序列，考慮壓縮率分別設置為75%、80%、85%、90%、95%時，HTFPAA分段算法擬合誤差的大小以及趨勢走向，結果如圖2所示。

圖2 4個數(shù)據(jù)集上擬合誤差的趨勢

從圖2可以看出，HTFPAA分段算法在各數(shù)據(jù)集上的擬合誤差都呈增加趨勢，并且上升趨勢大致相近。

表1中只有PAA算法、RPAA算法在某些數(shù)據(jù)分段上擬合質量優(yōu)于HTFPAA。因此對Time series數(shù)據(jù)中較長的4條時間序列，分別考察壓縮率為75%、80%、85%、90%、95%時PAA、RPAA與HTFPAA方法的擬合誤差。實驗結果如圖3所示。

圖3 3種分段方法不同壓縮率下的擬合誤差

由圖3對比分析可知，與RPAA方法、PAA方法相比，本文所提方法的擬合誤差在4條時間序列數(shù)據(jù)集上一直都是3種方法中擬合誤差最小的，而且隨著壓縮率的提高，擬合誤差增長比較平穩(wěn)。通過數(shù)據(jù)集橫向和縱向擬合誤差的比較，說明了該算法在不同類型的時間序列上擬合效果有著較強的可靠性和穩(wěn)定性。

4.3 分類效果對比實驗

4.3.1分類效果評價標準

序列分類的準確率直接受分段結果準確率的影響，文中使用錯誤率作為分類效果的評價指標，錯誤率越小，分類效果越好，否則，分類效果越差。分類錯誤率定義如下：

錯誤率=（錯誤分類的數(shù)量/真實類別數(shù)）×100%

4.3.2 分類實驗及耗時比較

為了進一步證明HTFPAA算法的可行性和優(yōu)越性，對HTFPAA和分段聚合近似（PAA）、基于時間特性的時間序列建模（RPAA）算法進行分類實驗，觀察比較各算法的分類結果。利用HTFPAA和經(jīng)典分段算法對測試集中的測試序列在訓練集中查找最相似即歐幾里德距離最小的序列實現(xiàn)最近鄰分類，并通過判斷測試序列與最相似序列標簽的一致性度量分類效果的好壞，評估各算法的分段效果，同時記錄各算法在對不同數(shù)據(jù)集分類時平均占用的CPU時間，實驗結果如表5所示。

表5 算法的實驗結果

表5中下劃線并且加粗的數(shù)據(jù)表示各個算法在該數(shù)據(jù)集上錯誤率最小的實驗結果。從表5中不難看出，HTFPAA算法在大部分數(shù)據(jù)集中分類錯誤率普遍較低，其中在Face（four）數(shù)據(jù)集上的錯誤率也接近最小值，錯誤率的平均值也是3個算法中最小的，說明該方法可以更準確地對時間序列進行索引，具有較好的學習效果。同時，由于PAA算法不考慮序列的時間特性只需計算各個窗口內數(shù)據(jù)的均值，因此在各個數(shù)據(jù)集上平均消耗時間最少，RPAA與HTFPAA算法占用的CPU時間則不相上下，HTFPAA算法只比PAA運行速度略低8.9%，在可以接受的范圍。

圖4是在分類效果最好的Face（all）數(shù)據(jù)集中任選的一條時間序列采用HTFPAA算法的分段效果圖，可以看出HTFPAA算法較好地反映了原始時間序列的趨勢走向。

圖4 HTFPAA分段效果圖

4.4 序列聚類實驗

4.4.1 聚類結果評價標準

給定的一組時間序列數(shù)據(jù)集聚類的真實結果為G=G1,G2,…,Gk，在某種分段方法的基礎上得到的聚類的結果為Q=Q1,Q2,…,Qk，則用式（12）作為評價指標來評估聚類效果的優(yōu)劣[26]。CPE(G,Q)越大時，說明采用某種方法得到的聚類結果越合理，反之，聚類效果越差，則說明該方法分段結果與原始時間序列相差越大。

4.4.2 聚類實驗

在時間序列數(shù)據(jù)挖掘中，序列匹配是基本也是最重要的問題，針對全序列匹配，給定查詢序列x，需要在指定的序列庫中找到和x最相似的序列或者與x距離小于某個閾值E的所有序列，實驗分別在PAA、RPAA以及文章所提到的HTFPAA算法分段的基礎上進行聚類實驗，比較三種分段算法在全序列匹配上的性能。

在表1中給出的數(shù)據(jù)集上進行聚類實驗，計算相應的CPE的值，并在其中的一個數(shù)據(jù)中（文中采用Fish數(shù)據(jù)集）任意選擇10條等長的時間序列數(shù)據(jù)，根據(jù)不同的類別標簽K，在PAA、RPAA、HTFPAA基礎上進行層次聚類，詳細觀察聚類結果。選擇的10條數(shù)據(jù)中已知1～5有相同的類別標簽6～10有相同的類別標簽，聚類結果分別如表6和圖5～圖7所示。

表6 各個數(shù)據(jù)集中聚類性能比較

圖5 PAA方法聚類結果

圖6 RPAA方法聚類結果

圖7 HTFPAA方法聚類結果

結果顯示，HTFPAA算法在7條數(shù)據(jù)集上的聚類效果明顯好于PAA以及RPAA算法，而在另外三條數(shù)據(jù)集上結果僅次于RPAA算法。圖5～圖7更加直觀地顯示算法的聚類結果，可見在進行數(shù)據(jù)挖掘時將序列的時間特性考慮在內，明顯提高了序列的聚類質量。

4.5 實驗小結

綜合以上三個實驗，可得出結論：由于HTFPAA算法不僅考慮了序列的時間性質，有擬合誤差小、算法易于實現(xiàn)的優(yōu)點，而且HTFPAA算法相比PAA算法，能夠保持原始序列的形態(tài)特征和整體特性，以極小的時間代價獲得更好的分類聚類效果。同時，HTFPAA算法時間復雜度為O(n)，具有較強的通用性、普適應和穩(wěn)定性。

5 結束語

針對傳統(tǒng)的時間序列分段算法往往忽略序列的時間特性，導致分段不夠精確的問題，提出了基于雙曲正切函數(shù)約束的時間序列建模表示算法HTFPAA。HTFPAA繼承了PAA方法支持時間序列在線劃分的優(yōu)點而且能夠滿足RPAA方法支持時間序列分段時的時間特性，更加符合實際情況。實驗結果表明HTFPAA方法能夠比較準確地表示時間序列的整體特征，參數(shù)的引用在兼顧時間特性的同時更準確地描述時間序列動態(tài)變化的過程。但時間特性對序列走勢的影響以及如何找到更加合適的函數(shù)描述時間這一特殊的變量是有待進一步研究的課題。