時(shí)間序列數(shù)據(jù)挖掘中的特征表示與相似性度量方法研究分析

王培屹

（鄭州幼兒師范高等?？茖W(xué)校，河南 鄭州 450000）

1 引言

時(shí)間序列數(shù)據(jù)能夠隨著時(shí)間而變化，它的產(chǎn)生過(guò)程極易受環(huán)境的影響，而且會(huì)伴隨一定的噪聲。由于數(shù)據(jù)極為繁雜，研究的難度很大，然而其中蘊(yùn)含著有非常價(jià)值的信息，這類信息對(duì)于社會(huì)實(shí)踐具有重要的意義。時(shí)間序列數(shù)據(jù)相較于普通數(shù)據(jù)而言，它是高維的，在實(shí)踐過(guò)程中，針對(duì)時(shí)間序列數(shù)據(jù)，通常都必須對(duì)其進(jìn)行降維，具體方法有兩種：其一是進(jìn)行全局特征分解；其二是局部特征提取。時(shí)間序列相似性度量的作用是挖掘時(shí)間序列數(shù)據(jù)中存在的有價(jià)值的信息，使其更好地應(yīng)用于社會(huì)生產(chǎn)實(shí)踐。

2 特征表示方法

時(shí)間序列特征表示的含義：針對(duì)原時(shí)間序列數(shù)據(jù)，使之轉(zhuǎn)變成另外一個(gè)不同論域中的數(shù)據(jù)，并實(shí)現(xiàn)其降維，在進(jìn)行降維之后，對(duì)于低維空間的數(shù)據(jù)，也能最大限度地反映出原時(shí)間序列的信息。就目前而言，已經(jīng)出現(xiàn)很多特征表示方法，下面就簡(jiǎn)單介紹幾種：

2.1 分段線性表示方法

分段線性表示方法與其他表示方法相比，更加直觀和簡(jiǎn)單，它在時(shí)間序列數(shù)據(jù)挖掘中的應(yīng)用最為普遍，通常和時(shí)間序列相似性度量方法相互配合來(lái)使用。利用這種方法來(lái)分割時(shí)間序列，需要建立線性模型。根據(jù)分割方法的不同，采用的分割策略也不同。據(jù)分析研究可知，對(duì)于滑動(dòng)窗口方法和自底向上的方法而言，其時(shí)間復(fù)雜度和序列長(zhǎng)度的關(guān)系是前者為后者的平方階；而對(duì)于自頂向下的方法而言，其時(shí)間復(fù)雜度為線性階?；瑒?dòng)窗口的方法，在某些情形下，對(duì)時(shí)間序列的擬合程度不夠好，對(duì)于原時(shí)間序列中蘊(yùn)含的變化信息，不能夠全面地反映出來(lái)。對(duì)于自頂向下方法而言，其時(shí)間復(fù)雜度雖然相對(duì)來(lái)說(shuō)更高一些，然而，在圖像處理以及機(jī)器學(xué)習(xí)方面，它的應(yīng)用極為廣泛。通過(guò)對(duì)時(shí)間序列進(jìn)行識(shí)別和掃描，尋找其中的關(guān)鍵性片段，如：波谷和波峰，然后再自頂向下切割。遺憾的是，對(duì)于噪聲數(shù)據(jù)，它一樣比較敏感。通過(guò)對(duì)比可知，自底向上方法具有其他方法不具備的兩大優(yōu)點(diǎn)：第一，這種方法的時(shí)間復(fù)雜度對(duì)數(shù)據(jù)集擁有線性擴(kuò)展性；第二，在分割大部分時(shí)間序列數(shù)據(jù)集時(shí)，它的效果更好。通過(guò)對(duì)比以上三種分割方法，各有優(yōu)點(diǎn)和不足，經(jīng)過(guò)研究提出了一種更好的分割方法，這種方法集中了自底向上以及滑動(dòng)窗口各自的優(yōu)勢(shì)，不僅使在線分割得以實(shí)現(xiàn)，而且，對(duì)時(shí)間序列數(shù)據(jù)的擬合效果也非常好。

2.2 分段聚合近似表示方法

分段聚合近似表示方法(PAA)主要是通過(guò)平均分割時(shí)間序列并根據(jù)各段序列的平均值來(lái)表示原時(shí)間序列。這種方法以m長(zhǎng)度的時(shí)間序列為對(duì)象，將其切割為w段，每段長(zhǎng)度為k，對(duì)于該長(zhǎng)度為m序列段，用k來(lái)表示，壓縮比為降維數(shù)為w，從而實(shí)現(xiàn)降維。若要確定特征序列，離不開(kāi)k和w，如果k值越大，或者w值越小，那么近似表示該時(shí)間序列的效果就越不好，同時(shí)也會(huì)丟失更多的信息，至于其降維幅度，則會(huì)越大；如果k值越小，或者w值越大，則會(huì)與上述情況完全相反。所以，實(shí)現(xiàn)了近似表示效果的最大化，就不能獲得更大的降維幅度，需要權(quán)衡利弊，找到兩者之間的平衡。在時(shí)間序列中，有極大值、極小值等重要信息，而這種方法運(yùn)用了平均值，從而造成這些重要信息丟失，而且，對(duì)于那些均值相同，但形態(tài)趨勢(shì)存在極大差異的序列，這種方法的使用會(huì)將它們表示成相同的均值信息特征。因此，相關(guān)專家學(xué)者對(duì)這種方法進(jìn)行了改進(jìn)，在表示時(shí)間序列的過(guò)程中，使用均值的同時(shí)，兼顧了分段序列的斜率。結(jié)合時(shí)間序列自身的特點(diǎn)，將其分為不等長(zhǎng)的段，仍然通過(guò)均值來(lái)反映時(shí)間序列的特征，即自適應(yīng)分段常量近似方法，為找到這種方法的分割點(diǎn)，通過(guò)采用動(dòng)態(tài)規(guī)劃的方法來(lái)實(shí)現(xiàn)對(duì)時(shí)間序列的最優(yōu)化分割，在某些情形下，可以采用貪婪算法進(jìn)行次優(yōu)分割，從而使算法的效率大大提高。

2.3 符號(hào)化表示方法

符號(hào)化表示方法的含義：實(shí)現(xiàn)時(shí)間序列向字符串序列轉(zhuǎn)換的過(guò)程。當(dāng)挖掘時(shí)間序列數(shù)據(jù)中的信息時(shí)，傳統(tǒng)挖掘方法局限于定量數(shù)據(jù)，在分析和解決問(wèn)題方面存在很大的不足。在數(shù)據(jù)結(jié)構(gòu)中，字符串具有兩大優(yōu)點(diǎn)：第一，具備特定的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)；第二，其操作算法速度快。近幾年，有很多和字符串有關(guān)的算法的應(yīng)用越來(lái)越廣泛。對(duì)于一些特殊的實(shí)際問(wèn)題，很難用具體的定量數(shù)據(jù)來(lái)反映，而通過(guò)字符型數(shù)據(jù)卻能收到令人意外的效果。在符號(hào)化表示方法之中，符號(hào)化聚合近似表示方法(SAX)屬于最具代表性的一種，它是在PAA的基礎(chǔ)上，加以改進(jìn)形成的一種表示方法。這種表示方法先將時(shí)間序列平均分為若干段，并實(shí)現(xiàn)原時(shí)間序列的Z標(biāo)準(zhǔn)化，然后再針對(duì)數(shù)據(jù)空間，將其分為概率相同的幾個(gè)部分，并以不同字符進(jìn)行表示，最后獲得的均值序列便是用各部分的字符表示的。因?yàn)镾AX是基于PAA的一種符號(hào)化表示方法，所以也擁有著PAA的某些缺陷，因此，相關(guān)學(xué)者提出了兼顧均值和方差并其轉(zhuǎn)化為符號(hào)，實(shí)現(xiàn)在二維空間下的符號(hào)化表示。

3 相似性度量研究

相似性度量方法的主要作用是：權(quán)衡不同對(duì)象之間的關(guān)系。在挖掘時(shí)間序列的過(guò)程中，相似性度量發(fā)揮著至關(guān)重要的作用。

3.1 歐氏距離

假設(shè)有時(shí)間序列 Q={q1，q2，……qm}和 C={c1，c2，……cm}，如果采用M inkowski距離度量方法，則

在距離度量方法中，上式是通用的，p值的變化會(huì)帶來(lái)距離度量方式的變化。當(dāng)p=1時(shí)，它表示曼哈頓距離；當(dāng)ρ=∞時(shí)，它轉(zhuǎn)變?yōu)?L∞范數(shù)，且滿足；當(dāng)p=2時(shí)，它表示歐氏距離，它是應(yīng)用最普遍的一種距離度量方法。通常情況下，若兩條時(shí)間序列長(zhǎng)度相同，歐氏距離可以直接進(jìn)行距離度量，然而，在大多情形下，它必須同特征表示方法相結(jié)合。比如，針對(duì)分段之后的時(shí)間序列，利用歐氏距離的方法，對(duì)擬合序列段直線斜率的相似性進(jìn)行精密的計(jì)算，將時(shí)間序列符號(hào)化之后，同樣利用歐氏距離的方法，在降維空間中，進(jìn)行相似性度量，在譜分解中進(jìn)行能量計(jì)算，從而使特征序列的相似性度量得以實(shí)現(xiàn)。但是，因?yàn)闅W氏距離對(duì)時(shí)間序列噪聲以及序列段突變有很強(qiáng)的敏感性，對(duì)于數(shù)據(jù)的預(yù)處理操作依賴性較強(qiáng)，而且，對(duì)于時(shí)間序列的位移不能進(jìn)行有效的識(shí)別。最重要的是，它只局限于度量相同長(zhǎng)度的時(shí)間序列段，針對(duì)不同長(zhǎng)度時(shí)間序列，就不適用。所以，歐氏距離一般情況下，都要充分結(jié)合時(shí)間序列的特征表示方法來(lái)度量時(shí)間序列相似性。尤其是在針對(duì)特征表示之后的空間進(jìn)行度量時(shí)，一定要滿足其下界的要求，避免有所漏報(bào)。

3.2 動(dòng)態(tài)時(shí)間彎曲

動(dòng)態(tài)時(shí)間彎曲的具體含義是：借助彎曲時(shí)間軸，來(lái)實(shí)現(xiàn)對(duì)時(shí)間序列的匹配映射。它最初的作用是對(duì)語(yǔ)音數(shù)據(jù)進(jìn)行處理，后來(lái)又被用作時(shí)間序列相似性的度量。動(dòng)態(tài)時(shí)間彎曲在兩條時(shí)間序列Q={q1，q2，……qm}和C={c1，c2，……cn}之間，尋找出最好的彎曲路徑，從而得到DTW(Q，C)，它是最小的距離度量值。只需要符合邊界條件的要求，P=(p1，p2……pk)可以用來(lái)表示連續(xù)性路徑，其中，qik與cjk之間的對(duì)應(yīng)關(guān)系可以pk表，qik和cjk的彎代價(jià)以d(pk)來(lái)表示，一般情況下取2，……n，在這一系列彎曲路徑中，有一條最優(yōu)路徑可以使彎曲總代價(jià)最小，即

我們可以采用動(dòng)態(tài)規(guī)劃來(lái)構(gòu)造一個(gè)代價(jià)矩陣R來(lái)求解,即：

其中，i=1,2,…m ，j=1,2,…n，R(0,0)=0，R(i,0)=R(0,j)=+∞，R(m,n)即動(dòng)態(tài)彎曲時(shí)間序列Q和C的最小距離值，即 DTW(Q,C)=R(m,n)。

通過(guò)對(duì)比動(dòng)態(tài)時(shí)間彎曲與歐氏距離，不難發(fā)現(xiàn)：（1）前者能夠度量的時(shí)間序列可以有兩種類型，即：長(zhǎng)度相同的、長(zhǎng)度不同的；后者能夠度量的時(shí)間序列只有一種，即：長(zhǎng)度相同的。（2）針對(duì)時(shí)間序列的突變點(diǎn)，前者不敏感，而且，也更加適合對(duì)其進(jìn)行度量；后者則不然，針對(duì)這類異常時(shí)間序列，敏感度較高，不適合對(duì)其進(jìn)行度量。（3）前者能夠進(jìn)行異步相似性比較，后者只局限于同步比較；（4）針對(duì)時(shí)間復(fù)雜度，前者為O(m2)，后者為O(m)；（5）前者不滿足三角不等式，后者則滿足。

3.3 符號(hào)化距離

針對(duì)時(shí)間序列的特征表示，符號(hào)化距離能夠?qū)⒅D(zhuǎn)變?yōu)樽址?，轉(zhuǎn)變成字符串之后，其度量方法也隨之發(fā)生了改變，即由定量數(shù)據(jù)轉(zhuǎn)變?yōu)槎ㄐ苑?hào)。它是在歐氏距離的基礎(chǔ)上形成的度量方法，它針對(duì)時(shí)間序列，做了標(biāo)準(zhǔn)化處理，使之能夠滿足正態(tài)分布，然后再將之轉(zhuǎn)變?yōu)樽址?。通過(guò)查詢正態(tài)分布圖，可以知曉字符間距離。據(jù)相關(guān)資料顯示，這種距離方法也符合下限要求，通過(guò)它來(lái)搜索時(shí)間序列相似性時(shí)，可以避免漏報(bào)情況的出現(xiàn)。編輯距離的含義是：實(shí)現(xiàn)兩個(gè)字符串之間的轉(zhuǎn)換所須的最少步驟，如刪除字符、插入字符等。第一步：將時(shí)間序列轉(zhuǎn)變?yōu)樽址?；第二步：針?duì)兩個(gè)字符串，借助于編輯距離，度量二者的相似性。編輯距離的主要優(yōu)點(diǎn)：能夠使挖掘算法的性能得到全面提高，更重要的是，對(duì)于其具體操作過(guò)程，更容易理解和掌握。然而，也存在一些缺點(diǎn)，比如：當(dāng)兩個(gè)時(shí)間序列不同步時(shí)，其相似性度量不能發(fā)揮出更好的效果。

4 未來(lái)研究方向

隨著科學(xué)發(fā)展的日新月異，我國(guó)在時(shí)間序列方面的研究也取得了驕人的成績(jī)，被應(yīng)用于社會(huì)生活的各個(gè)層面，為社會(huì)的發(fā)展和經(jīng)濟(jì)的建設(shè)做出了重大的貢獻(xiàn)。比如：在醫(yī)療領(lǐng)域中，針對(duì)病人群體，可以用來(lái)檢測(cè)其中的異常個(gè)體；在金融領(lǐng)域中，可以用來(lái)監(jiān)視消費(fèi)支出，避免欺詐現(xiàn)象的產(chǎn)生等。但是，在研究的過(guò)程中，也逐漸暴露出了一系列的問(wèn)題，應(yīng)該給予充分的重視。

分段線性近似表示方法的應(yīng)用非常普遍，屬于最常用的方法之一，它針對(duì)時(shí)間序列的關(guān)鍵點(diǎn)和關(guān)鍵形態(tài)，進(jìn)行分析和識(shí)別，借助于直線段，實(shí)現(xiàn)原時(shí)間序列的模擬。這種方法的優(yōu)點(diǎn)是：針對(duì)時(shí)間序列的特征表示更為直觀易懂；它的缺點(diǎn)是：擬合線段數(shù)目難以確定。所以，如何有效地對(duì)時(shí)間序列進(jìn)行分段線性近似表示是一個(gè)非常有意義的研究課題，也將是未來(lái)一個(gè)重要的研究方向。

動(dòng)態(tài)時(shí)間彎曲相對(duì)來(lái)說(shuō)伸縮性更好，它可以略過(guò)時(shí)間序列的特征表示，進(jìn)行相似性比較。相比于歐氏距離，動(dòng)態(tài)時(shí)間彎曲具有兩大優(yōu)勢(shì)：第一，對(duì)異常點(diǎn)沒(méi)有敏感性；第二，可以度量不等長(zhǎng)的時(shí)間序列。但是，因?yàn)閯?dòng)態(tài)時(shí)間序列搜索最優(yōu)彎曲路徑的時(shí)間復(fù)雜度比較高，所以，對(duì)于數(shù)量多的時(shí)間序列，它不適合進(jìn)行相似性比較，應(yīng)用范圍具有很大的局限性。而且，動(dòng)態(tài)時(shí)間彎曲還有一個(gè)缺點(diǎn)就是：太過(guò)于依賴時(shí)間序列數(shù)據(jù)值，對(duì)于局部數(shù)據(jù)的特征則沒(méi)有考慮，無(wú)法對(duì)那些數(shù)據(jù)相近但形態(tài)不同的時(shí)間序列進(jìn)行相似性比較。因此，如何有效提高動(dòng)態(tài)時(shí)間彎曲方法的效率和精度是將來(lái)的一個(gè)重大課題。目前，關(guān)于這方面的研究，基本上都偏重于靜態(tài)時(shí)間序列數(shù)據(jù)，至于動(dòng)態(tài)時(shí)間序列數(shù)據(jù)，研究文獻(xiàn)則相對(duì)來(lái)說(shuō)比較少。因?yàn)閯?dòng)態(tài)時(shí)間序列數(shù)據(jù)隨時(shí)間變化而變化，這就要求特征表示方法和相似性度量方法必須具備高效、穩(wěn)定的特點(diǎn)。

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

時(shí)間序列是一種應(yīng)用極為廣泛的數(shù)據(jù)，通過(guò)數(shù)據(jù)挖掘技術(shù)能夠從中獲取有價(jià)值的信息，這類信息有助于國(guó)家的經(jīng)濟(jì)建設(shè)，具有非常重要的現(xiàn)實(shí)意義。在數(shù)據(jù)挖掘的過(guò)程中，必須做好兩項(xiàng)基礎(chǔ)性的工作，分別是：特征表示、相似性度量。這兩項(xiàng)工作能夠?yàn)閿?shù)據(jù)挖掘任務(wù)提供有效的數(shù)據(jù)處理方法和技術(shù)支持。本文客觀地闡述了相關(guān)方法的優(yōu)點(diǎn)和缺點(diǎn)，希望能夠?yàn)闀r(shí)間序列數(shù)據(jù)挖掘領(lǐng)域的研究提供幫助。