孫冬璞，曲 麗

哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

當(dāng)今社會(huì)是一個(gè)數(shù)據(jù)信息爆炸的時(shí)代，時(shí)間序列作為其中一種普遍的數(shù)據(jù)類型，在日常生活中無處不在。如今已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域[1]研究的主要方向，廣泛應(yīng)用于金融、氣象、醫(yī)學(xué)[2]、電子科技、教育、工業(yè)等多個(gè)領(lǐng)域。人們可以通過時(shí)間序列的歷史數(shù)據(jù)挖掘出其中的潛在價(jià)值信息并預(yù)測未來趨勢。簡言之，時(shí)間序列是一組根據(jù)時(shí)間先后順序不斷變化的數(shù)列，如果直接對(duì)原時(shí)間序列進(jìn)行處理，無法避免產(chǎn)生耗時(shí)長，時(shí)間復(fù)雜度高，成本高的問題。因此，選擇一種簡單的轉(zhuǎn)換方式，將數(shù)據(jù)量大、動(dòng)態(tài)性強(qiáng)、易受噪聲干擾的高維密集型時(shí)間序列轉(zhuǎn)換為低維離散型時(shí)間序列，發(fā)現(xiàn)不同時(shí)間序列之間的關(guān)系，探索其中的規(guī)律，達(dá)到降低研究成本的目的，就變得尤為重要。

特征表示是一種將數(shù)量冗長的高維時(shí)間序列映射到低維數(shù)據(jù)空間的常用方法，在提取局部特征信息仍然能夠反映整體時(shí)間序列信息的前提下，過濾掉低頻信息，既保證了時(shí)間序列的基本信息和形態(tài)特征，又有效地實(shí)現(xiàn)了數(shù)據(jù)降維去噪。這種方法為提高數(shù)據(jù)挖掘效率奠定了良好基礎(chǔ)。

相似性度量作為數(shù)據(jù)挖掘領(lǐng)域另一個(gè)重要的過程，應(yīng)用于大部分時(shí)間序列的預(yù)處理階段。一般情況下，在對(duì)時(shí)間序列進(jìn)行分類、聚類、回歸分析之前，如果通過相似性度量發(fā)現(xiàn)序列之間的內(nèi)在規(guī)律，篩選出重要的時(shí)間序列，對(duì)于提高數(shù)據(jù)挖掘的效率非常有利。針對(duì)不同類型的時(shí)間序列，采取合適的相似性度量方法能夠更加客觀地反映時(shí)間序列之間的關(guān)系。除了基于形狀的相似性度量、基于模型的相似性度量方法和基于數(shù)據(jù)壓縮的相似性度量方法外，常用的相似性度量方法還有興趣模式發(fā)現(xiàn)、異常模式處理、序列可視化[3-5]等。

本文主要從時(shí)間序列的特征表示和相似性度量方面對(duì)目前時(shí)間序列的研究現(xiàn)狀進(jìn)行總結(jié)。

首先，針對(duì)時(shí)間序列特征表示方法，本文從非數(shù)據(jù)適應(yīng)性方法、數(shù)據(jù)自適應(yīng)性方法、基于模型的方法三方面進(jìn)行闡述說明，比較了多種常用方法的優(yōu)缺點(diǎn)、時(shí)間復(fù)雜度、不同特征表示方法之間的區(qū)別以及適用條件。

其次，針對(duì)時(shí)間序列相似性度量，本文從基于形狀的相似性度量、基于模型的相似性度量、基于數(shù)據(jù)壓縮的相似性度量三方面進(jìn)行系統(tǒng)描述。對(duì)各種方法是否支持去噪、是否滿足三角不等式等方面進(jìn)行了說明，并且對(duì)常用的經(jīng)典模型如歐氏距離（Euclidean distance，ED）、隱馬爾科夫模型（hidden Markov model，HMM）、最長公共子序列（longest common subsequence，LCSS）、自回歸滑動(dòng)平均模型（autoregressive moving average model，ARMA）等進(jìn)行了系統(tǒng)的介紹。

最后，本文對(duì)時(shí)間序列未來研究發(fā)展方向進(jìn)行了展望，提出了引入聚類算法、分類算法、預(yù)測算法、權(quán)值、斜率、魯棒性技術(shù)等研究方法。這些方法能夠一定程度地降低時(shí)間序列噪聲，提高挖掘精度。

1 時(shí)間序列特征表示方法研究現(xiàn)狀

時(shí)間序列特征表示是一種能夠?qū)⒃几呔S時(shí)間序列轉(zhuǎn)化為另一個(gè)低維領(lǐng)域的近似表示數(shù)據(jù)，進(jìn)而對(duì)數(shù)據(jù)降維的常用方法。例如小波變換，通過對(duì)時(shí)間軸函數(shù)的伸縮平移區(qū)分高頻和低頻信號(hào)，然后投射到低維數(shù)據(jù)空間上，使投射后的時(shí)間序列盡可能地反映原始時(shí)間序列信息。有效的特征表示方法往往能以簡潔的方式表達(dá)該時(shí)間序列的特征信息，起到對(duì)時(shí)間序列降維去噪，減少計(jì)算量的效果，為進(jìn)一步提高數(shù)據(jù)挖掘效率奠定了良好基礎(chǔ)。目前已經(jīng)研究出多種關(guān)于時(shí)間序列特征表示的方法。根據(jù)時(shí)間序列數(shù)據(jù)的不同轉(zhuǎn)換方式，大體將特征表示方法分為非數(shù)據(jù)適應(yīng)性方法、數(shù)據(jù)自適應(yīng)性方法、基于模型的方法三類。不同方法之間存在著一定的區(qū)別和聯(lián)系，歸類分析如圖1 所示。

1.1 非數(shù)據(jù)適應(yīng)性方法

非數(shù)據(jù)適應(yīng)性方法能夠?qū)⒏呔S度時(shí)間序列數(shù)據(jù)轉(zhuǎn)換到其他的低維度數(shù)據(jù)空間，且數(shù)據(jù)本身相對(duì)獨(dú)立，和轉(zhuǎn)換過程、特征系數(shù)選擇無關(guān)。該方法適用于表示大?。ǖ乳L）不變并且每條時(shí)間序列的轉(zhuǎn)換參數(shù)一致的分段時(shí)間序列?；诓煌菙?shù)據(jù)適應(yīng)性方法特性的比較如表1 所示。

Fig.1 Classification of time series feature representation methods圖1 時(shí)間序列特征表示方法分類

Table 1 Comparison of non-data adaptive methods表1 非數(shù)據(jù)適應(yīng)性方法的比較

1993 年，Agrawal 等人[6]提出了一種使用傅里葉變換（discrete Fourier transform，DFT）將時(shí)間序列的特征域變換到頻域的表示方法。其時(shí)間復(fù)雜度為O(nlb(n))。該方法通過將信號(hào)分解，形成頻率幅度大小不同的頻率譜，然后通過R*-tree 將其運(yùn)用到索引和相似度查詢中。該方法有效解決了時(shí)間序列數(shù)據(jù)挖掘中“特征抽取完備性”和“維度災(zāi)難”的問題。它的優(yōu)點(diǎn)是沒有錯(cuò)誤的丟失值，數(shù)值相對(duì)精準(zhǔn)。缺點(diǎn)是不支持時(shí)間扭曲查詢，主要考慮低頻率分量，忽略了高頻率分量和時(shí)間局部化的重要特征。該方法經(jīng)常被應(yīng)用于例如聲學(xué)、光學(xué)、海洋學(xué)、信號(hào)處理等領(lǐng)域。Keogh 等人[7]提出了分段聚合近似表示方法（piecewise aggregate approximation，PAA），該方法在滿足下界定理的前提下，時(shí)間復(fù)雜度最快能達(dá)到O(n)，適用于處理短期平穩(wěn)變化的時(shí)間序列。該方法通過在索引速度和靈活性等方面與傳統(tǒng)的奇異值分解（singular value decomposition，SVD）和離散小波變換（discrete wavelet transform，DWT）進(jìn)行比較，證明其在時(shí)間序列相似性度量和索引上更具有優(yōu)勢。Keogh 等人[8]還提出了一種基于逐段線性分割的方法（partial least squares regression，PLS），該方法不僅能夠較為準(zhǔn)確地確定時(shí)間序列的形狀，而且能夠快速地對(duì)時(shí)間序列進(jìn)行聚類和分類分析。除此之外，頻譜分析也是非數(shù)據(jù)適應(yīng)性的一種常見方法。Chan 等人[9]提出的離散小波變換（discrete wavelet transform，DWT）經(jīng)常被應(yīng)用于處理平穩(wěn)信號(hào)的時(shí)間序列信息，其時(shí)間復(fù)雜度為O(n)。該方法有效結(jié)合了泛函數(shù)、調(diào)和分析、數(shù)值分析等數(shù)學(xué)分析方法。優(yōu)點(diǎn)是既能夠表示時(shí)間序列中的時(shí)域信息，又能夠表示頻域信息。此特性被廣泛應(yīng)用于語音合成、圖像處理等領(lǐng)域。相比較而言，DFT 只能表示頻域信息并且要求信號(hào)數(shù)量為2 的指數(shù)倍，信號(hào)結(jié)果不夠穩(wěn)定，具有一定的局限性。繼而，Popivanov 等人[10]對(duì)比了不同小波變換對(duì)時(shí)間序列相似性搜索的效率并得出結(jié)論，多貝西小波（Daubechies wavelet，DbN）比哈爾小波（Haar wavelet，Harr）的高效性、光滑性和擬合性都更好一些，并且使用小波變換后的時(shí)間序列更加接近初始的時(shí)間序列。但是，Haar 小波在時(shí)間序列結(jié)果的精度上優(yōu)于Daubechies和Coiflet小波，并且計(jì)算成本低。除了一維時(shí)間序列外，通過Haar 變換得到的序列精度接近最優(yōu)，其性能明顯優(yōu)于DFT。此外，PIP（perceptually important points）方法[11]通常用于非等長時(shí)間序列之間的比較，被廣泛應(yīng)用于金融領(lǐng)域當(dāng)中。

Table 2 Comparison of data adaptive methods表2 數(shù)據(jù)自適應(yīng)性方法的比較

由于國內(nèi)對(duì)于時(shí)間序列特征表示方面的研究起步較晚，而且主要集中在國內(nèi)的重點(diǎn)高校和科研所當(dāng)中[12]。因此，研究成果與國外相比較還有一定的提升空間。

1.2 數(shù)據(jù)自適應(yīng)性方法

數(shù)據(jù)自適應(yīng)性是一種數(shù)據(jù)和參數(shù)隨著時(shí)間變化而變換的方法。與非數(shù)據(jù)適應(yīng)性方法不同，數(shù)據(jù)適應(yīng)性方法允許各條時(shí)間序列的轉(zhuǎn)換參數(shù)是不一致的，該方法既依賴于單條時(shí)間序列，又受整體時(shí)間序列數(shù)據(jù)集的影響，相對(duì)獨(dú)立性較差。對(duì)于數(shù)據(jù)自適應(yīng)性方法的比較如表2 所示。

Lin 等人[13]提出了一種符號(hào)聚集近似（symbolic aggregate approximation，SAX）表示方法，時(shí)間復(fù)雜度能達(dá)到O(n)的級(jí)別。該方法能夠?qū)崿F(xiàn)將高維非離散時(shí)間序列轉(zhuǎn)化為低維離散符號(hào)化時(shí)間序列，有效達(dá)到降維去噪的效果。該方法優(yōu)點(diǎn)是滿足下界定理，可以將字母存儲(chǔ)為位而不是雙精度，并且允許維度減少，大大節(jié)省了空間。研究者根據(jù)該方法可以更好地進(jìn)行字符串處理、生物信息學(xué)應(yīng)用、股票數(shù)據(jù)聚類等操作。缺點(diǎn)是該方法只適用于能等分且服從高斯分布的離散型和字母型時(shí)序數(shù)據(jù)，并且符號(hào)化過程只采取時(shí)間序列的均值作為局部特征提取，只能反映原始時(shí)間序列的總體變化趨勢，不能客觀描述各段的局部信息，容易忽略時(shí)間序列形態(tài)變化和特征點(diǎn)等信息，造成數(shù)據(jù)中其他信息的缺失，而且當(dāng)兩個(gè)時(shí)間序列各段的均值一致而各段趨勢不同時(shí)，SAX 的局限性更明顯。

Lkhagva 等人[14]在SAX 基礎(chǔ)上提出了擴(kuò)展方法（extension of symbolic aggregate approximation，ESAX），考慮加入時(shí)間序列段的均值、極大值和極小值等特征點(diǎn)元素，能夠更加準(zhǔn)確地反映時(shí)間序列的形態(tài)，在進(jìn)行相似性搜索時(shí)，該方法效率更高，但是下界性沒有得到充分證明。除此之外，可轉(zhuǎn)位符號(hào)聚合近似（indexable symbolic aggregate apprximation，iSAX）的多分辨率符號(hào)表示方法，能夠?qū)崿F(xiàn)快速精確搜索和超快速近似搜索。其中，iSAX 與SAX 的不同在于是否通過二進(jìn)制形式替代字母形式表示每個(gè)分段。iSAX方法創(chuàng)建的層次結(jié)構(gòu)索引不能包含重疊的區(qū)域，是一種支持大量數(shù)據(jù)集進(jìn)行索引的表示方法，可以索引多達(dá)億個(gè)數(shù)量級(jí)的時(shí)間序列[15]。奇異值分解（singular value decomposition，SVD）[16]表示方法也是一種數(shù)據(jù)適應(yīng)性方法，因?yàn)檫\(yùn)行時(shí)間復(fù)雜度高達(dá)O(Mn2)，代價(jià)成本較高，應(yīng)用并不廣泛，往往應(yīng)用于文本處理領(lǐng)域，用來處理數(shù)據(jù)的底層結(jié)構(gòu)。Ye 等人[17-18]提出的shapelets 子序列的概念，是一種能夠最大限度突出時(shí)間序列主要特征的子序列表示方法，具有準(zhǔn)確性高、分類速度快、可解釋性強(qiáng)的特點(diǎn)。該方法搭建起了時(shí)間序列和形狀之間相互表示的橋梁。Sun 等人[19]提出了一種基于趨勢距離的符號(hào)聚合近似表示方法（SAX trend distance，SAX-TD），通過時(shí)間序列段的起點(diǎn)和終點(diǎn)構(gòu)建趨勢距離，是一種融合了SAX 距離和趨勢距離的新距離度量表示方法。該方法的缺點(diǎn)是在構(gòu)建距離時(shí)，難免伴隨著存儲(chǔ)維度和運(yùn)行時(shí)間的增加。除此之外，分段多項(xiàng)式也是常見的數(shù)據(jù)自適應(yīng)性方法。

1.3 基于模型的方法

基于模型的方法是提前假定時(shí)間序列數(shù)據(jù)是由某個(gè)模型產(chǎn)生，然后通過對(duì)該模型設(shè)定合適的參數(shù)或者系數(shù)，實(shí)現(xiàn)對(duì)時(shí)間序列的特征表示。

Azzouzi 等人[20]提出隱馬爾科夫模型（HMM）來捕獲時(shí)間序列變量間的依賴關(guān)系和測量值中的串行相關(guān)性。該模型被廣泛應(yīng)用于語音識(shí)別、音字轉(zhuǎn)換等自然語言處理領(lǐng)域。Kalpakis 等人[21]提出了求和自回歸移動(dòng)平均模型（autoregressive integrated moving average model，ARIMA），該模型能夠更加高效直觀地表示時(shí)間序列特征信息，主要應(yīng)用于醫(yī)療領(lǐng)域?qū)α餍胁〉念A(yù)測和食品領(lǐng)域?qū)κ称钒踩灶A(yù)測方面。Nanopoulos 等人[22]提出一種基于統(tǒng)計(jì)模型（含方差、均值等）的特征提取方法，采用局部特征表示整體時(shí)間序列。李愛國等人[23]提出了一種分段多項(xiàng)式回歸模型，將時(shí)間序列分為多段表示。Fuchs等人[24-26]提出了一種基于正交多項(xiàng)式的時(shí)間序列表示方法，實(shí)現(xiàn)了正交多項(xiàng)式和最小二乘法的融合，運(yùn)用正交基向量形成特征空間，并將數(shù)值較大的坐標(biāo)系數(shù)作為特征序列。這類方法往往被用于在線分割。Sebastiani 等人[27]使用馬爾科夫鏈模型（Markov chain model，MC）表示時(shí)間序列中的動(dòng)態(tài)特征。馬爾科夫鏈模型是一種對(duì)時(shí)間、狀態(tài)離散化處理，帶有記憶情況的隨機(jī)過程模型，經(jīng)常用于對(duì)人均GDP、股票和彩票預(yù)測、全國電信業(yè)務(wù)總量的預(yù)測。另外，主成分分析法也是常用的一種基于模型的方法。基于模型的表示方法往往具有較強(qiáng)的可解釋性，若兩條時(shí)間序列可以由具有相同參數(shù)的同一數(shù)據(jù)集模型表示，那么認(rèn)為它們是相似的。此類方法的關(guān)鍵在于選擇合適的模型和提前了解時(shí)間序列數(shù)據(jù)產(chǎn)生過程的信息。只有選擇與產(chǎn)生過程相符合的模型才能獲得更好的結(jié)果?；谀Ｐ偷闹饕椒ㄌ匦员容^如表3所示。

Table 3 Characteristics comparison of model-based methods表3 基于模型方法的特性比較

主要的時(shí)間序列特征表示方法的時(shí)間復(fù)雜度如表4 所示。

Table 4 Time complexity of feature representation methods表4 特征表示方法的時(shí)間復(fù)雜度

2 時(shí)間序列相似性度量研究現(xiàn)狀

時(shí)間序列相似性度量通常采用衡量兩個(gè)不同時(shí)間序列之間距離遠(yuǎn)近程度的方式來驗(yàn)證兩個(gè)序列是否相似。目前時(shí)間序列相似性度量研究主要通過在原有研究基礎(chǔ)上提出新的時(shí)間序列相似性度量方法，評(píng)估該方法對(duì)時(shí)間序列數(shù)據(jù)挖掘精度的影響。時(shí)間序列相似性度量方法分為基于形狀的相似性度量方法、基于模型的相似性度量方法和基于數(shù)據(jù)壓縮的相似性度量方法等。不同相似性度量方法特性存在一定的差異性和聯(lián)系，如表5 所示。

Table 5 Features comparison of similarity measurement methods表5 相似性度量方法特性比較

相似性度量在應(yīng)用于時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域時(shí)，一般與聚類算法相結(jié)合。通常此類方法首先將等長時(shí)間序列通過降維的方法處理為不等長的時(shí)間序列，然后進(jìn)行等長處理，選取兩個(gè)時(shí)間序列的公共點(diǎn)元素，構(gòu)成新的時(shí)間序列集合，利用得到的時(shí)間點(diǎn)集合再對(duì)時(shí)間序列進(jìn)行二次劃分，最后得到新的等長時(shí)間序列。此過程雖然會(huì)提高計(jì)算的復(fù)雜性，但是便于操作，基本不會(huì)對(duì)結(jié)果造成較大的偏差。

2.1 基于形狀的相似性度量

基于形狀的相似性度量方法多種多樣。表6 對(duì)主要方法的特性進(jìn)行了分析比較。

Table 6 Comparison of similarity measurement methods based on shape表6 基于形狀的相似性度量方法的比較

歐氏距離（ED）是一種基于形狀相似性的常見鎖步度量方式。當(dāng)兩個(gè)時(shí)間序列長度相等且均為數(shù)值型序列時(shí)，該方法通過公式計(jì)算兩個(gè)序列上時(shí)間點(diǎn)的距離。在模糊距離中，漢明距離和灰色關(guān)聯(lián)分析法也可以應(yīng)用在字符串形狀相似性度量中。其中漢明距離通過對(duì)等長字符串序列對(duì)應(yīng)位進(jìn)行異或運(yùn)算，統(tǒng)計(jì)結(jié)果為1 的個(gè)數(shù)。1 的個(gè)數(shù)越多，相似性越低。漢明距離有一個(gè)鮮明的特點(diǎn)就是它比較的兩個(gè)字符串必須等長，否則距離不成立。它的核心原理是如何通過字符替換（最初應(yīng)用在通訊中實(shí)際上是二進(jìn)制的0-1 替換），能將一個(gè)字符串替換成另外一個(gè)字符串?；疑P(guān)聯(lián)分析法是通過對(duì)時(shí)間序列進(jìn)行無量綱化處理，確定參數(shù)數(shù)據(jù)序列和若干比較數(shù)據(jù)序列的幾何形狀來判斷相似程度，然后根據(jù)關(guān)聯(lián)度和關(guān)聯(lián)系數(shù)衡量關(guān)聯(lián)性的強(qiáng)弱?；疑P(guān)聯(lián)分析法的特點(diǎn)在于思路清晰，可以在很大程度上減少由于信息不對(duì)稱帶來的損失，并且對(duì)數(shù)據(jù)要求較低，工作量較少。其中LP 范式為最常見的距離度量形式，時(shí)間復(fù)雜度為O(n)，并且滿足三角不等式，一般用于索引、聚類和分類上。該距離方法缺點(diǎn)是對(duì)相位漂移比較敏感，受噪音干擾較大，對(duì)于時(shí)間序列的形狀縮放和位移無法準(zhǔn)確識(shí)別，某種情況下，度量結(jié)果往往存在很大誤差。因此，該度量方式通常依賴于數(shù)據(jù)的歸一化處理。在經(jīng)過特征表示之后再進(jìn)行相似性搜索時(shí)，該空間下的距離度量需要滿足下界定理[28-31]。動(dòng)態(tài)時(shí)間彎曲（dynamic time warping，DTW）是一種通過對(duì)時(shí)間軸進(jìn)行彎曲、拉伸或收縮來計(jì)算兩個(gè)時(shí)間序列間相似性的方法。該方法既可以處理兩個(gè)等長時(shí)間序列，也可以處理兩個(gè)不等長的時(shí)間序列，而且允許時(shí)間序列的點(diǎn)自行拷貝之后再進(jìn)行等長匹配，支持平移，能夠很好地處理時(shí)間漂移問題，克服了歐氏距離對(duì)于序列變形后不能準(zhǔn)確匹配的問題，具有效率優(yōu)于歐氏距離和三角形相似性[30,32-35]的特點(diǎn)，并且允許不同時(shí)間軸上的時(shí)間序列進(jìn)行相似性匹配。但是存在不支持噪聲處理、本地時(shí)間轉(zhuǎn)換和三角不等式，且時(shí)間復(fù)雜度較高等問題，隨著時(shí)間序列維度的遞增，算法的效率并不高。針對(duì)其不足，Sakoe 等人[36]和Itakura[37]分別提出Sakoe-Chiba 條形約束和平行四邊形約束方法，通過在動(dòng)態(tài)規(guī)劃過程中引入全局約束的方法，一定程度上減少了計(jì)算量，來實(shí)現(xiàn)算法效率的提高。該方法將路徑規(guī)劃（也稱路徑彎曲）過程限制在一定區(qū)域內(nèi)，不僅避免了不必要的路徑規(guī)劃，而且有效防止過度匹配導(dǎo)致準(zhǔn)確率下降的問題。Keogh 等人將基于DTW 的精確索引應(yīng)用于時(shí)間序列挖掘中[38]。除此之外，DTW 在計(jì)算多元時(shí)間序列最佳彎曲路徑時(shí)，雖然能夠較好地反映時(shí)間序列形態(tài)變化問題，但容易出現(xiàn)不合理的匹配導(dǎo)致產(chǎn)生多條匹配路徑，從而無法選擇最精準(zhǔn)的路徑的問題。Gorecki 等人[39]考慮到局部形態(tài)特征處理問題，提出了分別用動(dòng)態(tài)時(shí)間彎曲和微分動(dòng)態(tài)時(shí)間彎曲求取多元時(shí)間序列距離后再用參數(shù)線性組合度量的方法，但僅考慮一階數(shù)值導(dǎo)數(shù)可能會(huì)失去全局形態(tài)或重要的特征。Keogh 等人[40]提出了一種擴(kuò)展方法為DDTW（derivative dynamic time warping），根據(jù)時(shí)間序列中某個(gè)點(diǎn)的相鄰信息選取適當(dāng)?shù)挠?jì)算方式構(gòu)造出新的時(shí)間序列，達(dá)到實(shí)現(xiàn)新的序列不再對(duì)異常值敏感的目的。在此基礎(chǔ)上，自適應(yīng)代價(jià)動(dòng)態(tài)時(shí)間彎曲的多元時(shí)間序列度量方法（adaptive cost multivariate dynamic time warping，ACM-DTW）[41]，通過對(duì)時(shí)間序列點(diǎn)距離矩陣賦予權(quán)重，來達(dá)到較好的匹配效果，權(quán)重由自適應(yīng)代價(jià)函數(shù)計(jì)算獲取。

基于互相關(guān)的距離度量方法（cross-correlation based distance）具有降低噪聲影響和概括時(shí)間結(jié)構(gòu)的特點(diǎn)[42]。當(dāng)兩個(gè)時(shí)間序列大體形態(tài)都很相似，此時(shí)歐氏距離和動(dòng)態(tài)時(shí)間彎曲方法都無法測量，僅僅在小范圍內(nèi)存在彎曲或斷點(diǎn)時(shí)，可以采用最長公共子序列（LCSS）距離度量方法。該方法對(duì)于噪聲的處理能力比較強(qiáng)，但是對(duì)于處理時(shí)間軸的伸縮和振幅平移問題有待于進(jìn)一步提高，而且不支持三角不等式[43-45]。LCSS 方法采用將兩個(gè)時(shí)間字符串最大的公共字符串長度與最長字符串相除的百分比作為衡量兩時(shí)間序列相似性的度量標(biāo)準(zhǔn)[46]。實(shí)序列編輯距離（edit distance on real sequence，EDR）是一種能夠有效對(duì)時(shí)間序列進(jìn)行降噪，降低序列位移和誤差敏感度的方法。該方法通過閾值模式將時(shí)間序列元素量化為0/1表示，降低了時(shí)間序列的噪聲，對(duì)于異常數(shù)據(jù)的處理具有更好的魯棒性，但是該方法并不滿足三角不等式[47-48]。實(shí)補(bǔ)償編輯函數(shù)（edit distance with real penalty，ERP）是一種允許在兩條不同長度的序列間通過添加符號(hào)達(dá)到等長效果的度量方法[49-50]。該方法對(duì)數(shù)據(jù)的噪聲、位移和縮放具有較強(qiáng)的魯棒性，通過使用一個(gè)恒定的參考點(diǎn)來達(dá)到尋找彎曲路徑中最小路徑的目的。該方法滿足三角不等式，并且能夠有效處理本地時(shí)間轉(zhuǎn)換問題[51-52]。動(dòng)態(tài)時(shí)間彎曲、最長公共子序列、實(shí)序列編輯距離、實(shí)補(bǔ)償編輯函數(shù)方法的時(shí)間復(fù)雜度均為O(n2)。

2.2 基于模型的相似性度量

Ge 等人[53-54]采用隱馬爾科夫模型進(jìn)行相似性度量，加入了分段線性表示來實(shí)現(xiàn)捕獲變量之間的依賴關(guān)系，又能夠衡量時(shí)間序列測量相關(guān)性。Panuccio等人[55]采取標(biāo)準(zhǔn)化的方法對(duì)HMM 距離進(jìn)行處理，判斷時(shí)間序列的擬合性能好壞。ARMA 模型[21]是一種通過模型參數(shù)或演變參數(shù)確定原始序列相似性關(guān)系的方法。ARIMA 模型[56]全稱為自回歸積分滑動(dòng)平均模型，該模型首先判斷序列的平穩(wěn)性，若為非平穩(wěn)序列，通過差分運(yùn)算過濾掉非平穩(wěn)趨勢的點(diǎn)，然后確定時(shí)間序列的自回歸參數(shù)和滑動(dòng)平均參數(shù)?？臻g裝配距離（spatial assembling distance，SpADe）[57]也是一種基于模型的相似性度量方法?；谀Ｐ偷南嗨菩远攘颗c基于形狀的相似性度量相比，優(yōu)勢在于可以提前將數(shù)據(jù)的知識(shí)通過計(jì)算結(jié)合進(jìn)來。并且通過某個(gè)序列所建模型生成另外序列的概率值來衡量兩個(gè)序列的相似度。

2.3 基于數(shù)據(jù)壓縮的相似性度量

皮爾遜相關(guān)系數(shù)和相關(guān)距離（Perason's correlation coefficient and related distance）[58]是一種不隨數(shù)據(jù)點(diǎn)的比例和位置而變化的相似性度量方法?；诜侄握；南嗨菩远攘浚╬iecewise normalization）[59]是一種涉及不同大小的時(shí)間間隔或“窗口”的相似性度量方法?；诘诡l譜的相似性度量（cepstrum）[60]是一種頻譜測量方法，能夠短時(shí)間內(nèi)實(shí)現(xiàn)對(duì)數(shù)振幅頻譜的反傅里葉變換。

基于概率距離的相似性度量（probability-based distance）[61]能夠?qū)⒍喾N季節(jié)性模式融合匯總?；跅l件Kolmogorov 復(fù)雜性的距離度量或數(shù)據(jù)壓縮距離度量（compression-based distance measure，CDM）[62-63]通過數(shù)據(jù)壓縮比率大小反映時(shí)間序列相似性。該方法壓縮率越大，相似性越高，反之亦然。但是對(duì)算法的連接和壓縮過程要求較高，適合處理較長的離散化時(shí)間序列。Lang 等人[64]提出了基于字典壓縮的相似性度量（dictionary-based compression）方法，應(yīng)用于相似性度量的字典壓縮評(píng)分。類似的KL（Kullback-Leibler）距離相似性度量[65]、基于分段概率的相似性度量（piecewise probabilistic）[66]、基于余弦小波函數(shù)的相似性度量（cosine wavelets）[67]、基于自相關(guān)的相似性度量（autocorrelation）[68]也是比較常用的基于數(shù)據(jù)壓縮的相似性度量方法?；跀?shù)據(jù)壓縮的相似性度量來自于計(jì)算理論研究和生物信息學(xué)研究的一些結(jié)果，是一個(gè)比較新穎的想法。數(shù)據(jù)壓縮是指在不丟失有用信息的前提下，縮減數(shù)據(jù)量以減少存儲(chǔ)空間，或者按照一定的算法對(duì)數(shù)據(jù)進(jìn)行重新組織，減少數(shù)據(jù)的冗余和存儲(chǔ)空間的一種技術(shù)方法?，F(xiàn)有的相似性度量方法對(duì)短時(shí)間序列有較好的效果，但是對(duì)于較長的時(shí)間序列，它們的評(píng)估成本會(huì)迅速下降。因此應(yīng)該為數(shù)據(jù)選擇壓縮工具和壓縮參數(shù)的最佳組合。例如，CDM 取決于特定壓縮器（gzip、bzip2 等）的選擇以及壓縮參數(shù)。如今這些方法的應(yīng)用范圍也較廣泛，如醫(yī)學(xué)上的心電圖測量、生物識(shí)別中的面部識(shí)別、物理學(xué)中的粒子跟蹤等。除此之外，這些時(shí)間序列相似性度量方法對(duì)于查詢數(shù)據(jù)庫、分類和聚類十分有用。

3 未來研究方向

隨著科技的不斷發(fā)展，時(shí)間序列被廣泛應(yīng)用于多個(gè)領(lǐng)域，為社會(huì)的經(jīng)濟(jì)發(fā)展做出了巨大的貢獻(xiàn)。例如在醫(yī)學(xué)領(lǐng)域，時(shí)間序列用來檢測病人群體中的異常個(gè)體；金融領(lǐng)域中檢測異常收入支出，防止發(fā)生詐騙行為；工業(yè)領(lǐng)域檢測設(shè)備異常，防患于未然等。

時(shí)間序列一般用作數(shù)據(jù)挖掘的預(yù)處理步驟，降低高維數(shù)據(jù)維度，達(dá)到提高數(shù)據(jù)挖掘精度的效果。

如今時(shí)間序列相似性度量發(fā)展蓬勃，但是仍然存在一些問題值得重視。因此，針對(duì)時(shí)間序列相似性度量的未來研究方向提出了幾種規(guī)劃：

（1）一般對(duì)于時(shí)間序列相似性的研究比較理想化，多數(shù)相似性度量方法均在假設(shè)獲取的訓(xùn)練集是相對(duì)準(zhǔn)確的前提下進(jìn)行研究。但是在實(shí)際情況中，時(shí)間序列數(shù)據(jù)的采集和運(yùn)行結(jié)果往往受到周圍環(huán)境的影響，伴隨著大量噪聲的產(chǎn)生。因此，如何將相關(guān)魯棒統(tǒng)計(jì)學(xué)的技術(shù)運(yùn)用在相似性度量的學(xué)習(xí)方法中，達(dá)到更為理想的效果還有待于研究。

（2）同一數(shù)據(jù)集運(yùn)用不同的相似性度量方法時(shí)，精度的結(jié)果測量往往存在很大差異。因此，為了更好地完成數(shù)據(jù)挖掘的各類任務(wù)，在此基礎(chǔ)上，可以考慮融合數(shù)據(jù)挖掘聚類算法將時(shí)間序列數(shù)據(jù)進(jìn)行分組，每個(gè)分組內(nèi)的時(shí)間序列數(shù)據(jù)相似性越高，不同分組之間相似度越低，則聚類效果越好。因此，選擇合適的數(shù)據(jù)挖掘算法融合相似性度量方法提高結(jié)果精確度是一個(gè)值得研究的課題。

（3）考慮在時(shí)間序列的相似性度量方法上融合機(jī)器學(xué)習(xí)的分類算法。比如支持向量機(jī)、樸素貝葉斯、決策樹等，也可以達(dá)到提高相似性度量結(jié)果精確度的目的，可以作為未來研究的方向之一。

（4）如今定位技術(shù)和基于位置服務(wù)的應(yīng)用發(fā)展迅速，過程中會(huì)有文本、圖像數(shù)據(jù)等海量軌跡數(shù)據(jù)產(chǎn)生。因此，如果對(duì)不同時(shí)間點(diǎn)車輛運(yùn)行的路段信息、軌跡方向信息、運(yùn)行軌跡長度信息（包括運(yùn)行軌跡存在交叉等情況）采用合適的距離度量函數(shù)進(jìn)行計(jì)算，對(duì)軌跡相似性度量進(jìn)行深入研究，將有益于城市規(guī)劃、智慧出行的發(fā)展。

（5）目前為止，對(duì)于時(shí)間序列相似性度量研究主要為靜態(tài)低維的時(shí)間序列。對(duì)于動(dòng)態(tài)高維時(shí)間序列的研究成果較少，這就要求時(shí)間序列相似性度量方法具有高效、平穩(wěn)、低成本的特點(diǎn)，因此通過相似性度量方法改進(jìn)優(yōu)化實(shí)現(xiàn)這些特點(diǎn)，值得進(jìn)一步研究。

4 結(jié)束語

時(shí)間序列往往具有高維性、數(shù)據(jù)量大、隨著時(shí)間變化而變化的特點(diǎn)。隨著大數(shù)據(jù)時(shí)代的蓬勃發(fā)展，時(shí)間序列越來越普遍存在于人們的日常生活中。因此，根據(jù)時(shí)間序列的高維特性適當(dāng)?shù)亟档途S度，發(fā)現(xiàn)不同時(shí)間序列之間的關(guān)系，探索其中的規(guī)律，挖掘潛在價(jià)值就變得尤為重要。本文從時(shí)間序列的特征表示和相似性度量方面對(duì)目前時(shí)間序列的研究現(xiàn)狀進(jìn)行了闡述和總結(jié)，分析比較了各種方法的優(yōu)缺點(diǎn)、時(shí)間復(fù)雜度及方法之間的區(qū)別和適用條件，最后對(duì)時(shí)間序列的未來研究方向提出了幾點(diǎn)展望。