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

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

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

1 引言

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

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

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

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

2 PAA和RPAA分段表示方法

2.1 相關(guān)定義

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

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

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

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

2.2 PAA算法及問(wèn)題描述

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

當(dāng)N=n時(shí)向量表示即為原時(shí)間序列；N=1時(shí)向量表示原時(shí)間序列的均值。

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

2.3 RPAA算法及問(wèn)題描述

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

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

2.4 歐幾里德距離

歐幾里德距離廣泛應(yīng)用于時(shí)間序列距離計(jì)算中，給定長(zhǎng)度為n的時(shí)間序列C=c1,c2,…,cn和Q=q1,q2,…,qn，則C和Q之間的歐幾里德距離為：

為了防止遞加數(shù)過(guò)多，導(dǎo)致歐幾里德距離過(guò)大，可以計(jì)算加權(quán)的歐幾里德距離：

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

PAA支持平方后的加權(quán)歐幾里德距離的計(jì)算，將一個(gè)查詢Q降維表示為：

則此時(shí)計(jì)算PAA表示平方后的歐幾里德距離為：

3 時(shí)間序列的HTFPAA算法

3.1 時(shí)間序列的HTFPAA表示算法

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

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

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

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

函數(shù)證明如下：

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

因此，當(dāng)x→∞時(shí)，ex→∞則

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

首先對(duì)雙曲正切函數(shù)求導(dǎo)：

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

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

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

同時(shí)也可如RPAA方法首先將滑動(dòng)窗口置于時(shí)間序列末端，公式為：

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

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

輸出：時(shí)間序列S的HTFPAA表示。

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

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

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

（5）返回 S′。

3.2 距離計(jì)算

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

3.3 滿足下界定理

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

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

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

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

序列點(diǎn)的漏查問(wèn)題則決定了是否能夠?qū)π蛄羞M(jìn)行有效的相似性查找，為了能夠解決這個(gè)問(wèn)題，F(xiàn)aloutsos[23]給出維度下限下界定理，即 Dindex(C,Q)≤D(C,Q)。

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

證明由0

又

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

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)和平臺(tái)

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

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

4.2 擬合誤差的比較

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

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

表3 實(shí)驗(yàn)平臺(tái)

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

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

表4中下劃線并且加粗的數(shù)據(jù)表示該行中擬合誤差的最小值?？梢钥闯鯤TFPAA算法在7條時(shí)間序列上具有較小的擬合誤差；而在其他3條時(shí)間序列上HTFPAA算法的擬合誤差也接近最小值。而且從擬合誤差的平均值來(lái)看，HTFPAA算法擬合誤差的平均值遠(yuǎn)遠(yuǎn)小于其他3種算法，實(shí)驗(yàn)結(jié)果表明，HTFPAA算法在10條數(shù)據(jù)集上的擬合誤差都比較小，算法有良好的適應(yīng)性。

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

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

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

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

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

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

4.3 分類效果對(duì)比實(shí)驗(yàn)

4.3.1分類效果評(píng)價(jià)標(biāo)準(zhǔn)

序列分類的準(zhǔn)確率直接受分段結(jié)果準(zhǔn)確率的影響，文中使用錯(cuò)誤率作為分類效果的評(píng)價(jià)指標(biāo)，錯(cuò)誤率越小，分類效果越好，否則，分類效果越差。分類錯(cuò)誤率定義如下：

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

4.3.2 分類實(shí)驗(yàn)及耗時(shí)比較

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

表5 算法的實(shí)驗(yàn)結(jié)果

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

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

圖4 HTFPAA分段效果圖

4.4 序列聚類實(shí)驗(yàn)

4.4.1 聚類結(jié)果評(píng)價(jià)標(biāo)準(zhǔn)

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

4.4.2 聚類實(shí)驗(yàn)

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

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

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

圖5 PAA方法聚類結(jié)果

圖6 RPAA方法聚類結(jié)果

圖7 HTFPAA方法聚類結(jié)果

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

4.5 實(shí)驗(yàn)小結(jié)

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

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

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