基于系數(shù)矩陣弧微分的時(shí)間序列相似度量

王智博,林 意,曹洋洋

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

0 概述

將某一個(gè)統(tǒng)計(jì)指標(biāo)的各個(gè)數(shù)值按時(shí)間先后順序排列便構(gòu)成了時(shí)間序列。從金融領(lǐng)域到科學(xué)工程,從天文氣象到社會(huì)學(xué)[1-2],時(shí)間序列無(wú)處不在。由于實(shí)際應(yīng)用中的時(shí)間序列往往具有高維、規(guī)模巨大、易受噪聲干擾等特點(diǎn)[3-4],直接在原始時(shí)間序列上進(jìn)行數(shù)據(jù)分析、處理和挖掘變得非常困難,因此在對(duì)時(shí)間序列挖掘之前進(jìn)行有效的預(yù)處理成為解決上述問(wèn)題的關(guān)鍵。這其中時(shí)間序列特征表示和相似度量是預(yù)處理的關(guān)鍵[5-6]。

相似度量是時(shí)間序列挖掘中一項(xiàng)重要的基礎(chǔ)任務(wù),主流的度量算法通常自定義一個(gè)距離函數(shù),選取的自變量為離散序列點(diǎn)坐標(biāo)及其變形,序列之間的距離越小則序列越相似。常見(jiàn)的算法有:歐氏距離[7](Euclidean Distance,ED),設(shè)定單一距離閾值,容易理解且算法簡(jiǎn)單;動(dòng)態(tài)時(shí)間規(guī)整[8](Dynamic Time Warping,DTW),借鑒語(yǔ)音數(shù)據(jù)處理的思路并運(yùn)用動(dòng)態(tài)規(guī)劃思想,通過(guò)彎曲時(shí)間軸來(lái)實(shí)現(xiàn)相似性度量;符號(hào)化距離[9],將時(shí)間序列預(yù)處理為字符串,利用查詢等概率劃分的正態(tài)分布完成相似度量;基于條件復(fù)雜性距離[10],嵌入信息論和計(jì)算理論,關(guān)注算法運(yùn)行過(guò)程中的連接和壓縮操作,借助壓縮率來(lái)反映數(shù)據(jù)之間的相似性。

本文引入數(shù)理統(tǒng)計(jì)和回歸分析中的最小二乘思想,通過(guò)若干離散序列點(diǎn)并利用偏微分構(gòu)建系數(shù)矩陣方程,從而求得擬合多項(xiàng)式的不定參數(shù)。該參數(shù)以向量形式存在且刻畫(huà)曲線的基本形態(tài),被稱為向量基。由于實(shí)現(xiàn)了離散序列點(diǎn)的連續(xù)化,因此可利用幾何連續(xù)的性質(zhì)來(lái)繼續(xù)研究問(wèn)題。本文給出最小相似點(diǎn)和微分三角形的概念,分析對(duì)比連續(xù)曲線的弧微分與曲率半徑微分的關(guān)系,發(fā)現(xiàn)當(dāng)以最小相似點(diǎn)為端點(diǎn)構(gòu)成的微分三角形相似時(shí),可以使得微分三角形對(duì)應(yīng)的弧微分與曲率微分成等比關(guān)系,從而得出弧微分相似判定等式,最后根據(jù)分治、遞歸思想,判斷若在某一連續(xù)區(qū)間內(nèi)2條曲線所有最小相似點(diǎn)都在判定等式的合理閾值范圍內(nèi),可以得出這2個(gè)序列相似的情況。當(dāng)候選的2條序列時(shí)間粒度不相同時(shí),本文算法具有無(wú)需人工干預(yù)也能完成序列的相似度量的優(yōu)點(diǎn);當(dāng)候選的2條序列長(zhǎng)度不相同時(shí),該算法也能彌補(bǔ)傳統(tǒng)算法不能實(shí)現(xiàn)形態(tài)相似度量的不足。

1 時(shí)間序列相關(guān)定義與問(wèn)題描述

1.1 時(shí)間序列相關(guān)定義

定義1(時(shí)間序列) 時(shí)間序列是由記錄時(shí)間和記錄值組成的有序集合。對(duì)于給定的有限時(shí)間集T、非空狀態(tài)屬性集A=〈A1,A2,…,Am〉及其對(duì)應(yīng)值域DAj,時(shí)間序列X表示如下:

X=〈X1,X2,…,Xn〉

(1)

定義2(時(shí)間序列的模式表示)[12]時(shí)間序列模式指時(shí)間序列的某種變化特征,通過(guò)提取時(shí)間序列的模式將其變換到模式空間,即得到時(shí)間序列的模式表示。設(shè)有時(shí)間序列X=〈x1,x2,…,xn〉,其模式表示為:

X(t)=f(w)+e(t)

(2)

其中,f(w)是時(shí)間序列的模式表示,e(t)是時(shí)間序列與其模式表示之間的誤差。

定義3(時(shí)間序列的分段線性表示) 設(shè)有時(shí)間序列X=〈x1,x2,…,xn〉,則其分段線性表示為:

(3)

其中,fi(t,wi)表示連接時(shí)間序列分段點(diǎn)的線性函數(shù),ei(t)是時(shí)間段內(nèi)時(shí)間序列與其分段線性表示之間的誤差。

定義4(閔氏度量) 設(shè)有2條長(zhǎng)度為n的時(shí)間序列Q=〈Q1,Q2,…,Qn〉和C=〈C1,C2,…,Cn〉,則它們之間的閔氏度量為:

(4)

其中,p為可變參數(shù)。當(dāng)p=2時(shí),閔氏度量即為使用最為廣泛的歐式距離[7]。

1.2 問(wèn)題描述

傳統(tǒng)基于點(diǎn)距離的時(shí)間序列相似度量,如歐式距離[7]是利用式(4),通過(guò)計(jì)算2條序列一一對(duì)應(yīng)點(diǎn)之間的距離得到最終度量。該算法的實(shí)現(xiàn)依賴2個(gè)充分條件:1)候選的2條序列等長(zhǎng);2)2條序列一一對(duì)應(yīng)的點(diǎn)坐標(biāo)在時(shí)間軸上的投影重合。

如圖1所示,有3條時(shí)間序列A、B、C,根據(jù)歐式距離公式,代入對(duì)應(yīng)的序列點(diǎn)坐標(biāo)值得出D2(A,C)

圖1 時(shí)間序列示意圖

圖2所示為2條時(shí)間跨度不相等的時(shí)間序列。根據(jù)歐式距離的充分條件,當(dāng)候選序列時(shí)間跨度不相同時(shí),歐式距離算法失效。解決辦法是應(yīng)用動(dòng)態(tài)時(shí)間軸彎曲距離算法(DTW)[8]。其中的2個(gè)核心步驟是:1)動(dòng)態(tài)時(shí)軸彎曲或動(dòng)態(tài)時(shí)間規(guī)整;2)距離測(cè)度計(jì)算。DTW算法的本質(zhì)是尋找一個(gè)合適的函數(shù)j=w(i),將序列A的時(shí)間軸非線性地映射到序列B的時(shí)間軸上,使得A的第i個(gè)序列點(diǎn)與B的第j個(gè)序列點(diǎn)對(duì)齊,并且使每組對(duì)齊點(diǎn)達(dá)到距離最小,如圖3所示。但該算法時(shí)間效率較低,不利于大量較長(zhǎng)時(shí)間序列的相似度量。圖3為DTW算法示意圖。

圖2 時(shí)間跨度不相同的情況

圖3 DTW算法示意圖

設(shè)A、B時(shí)間序列是某一超市同類(lèi)的2種商品1天內(nèi)銷(xiāo)售額的序列。它們跨度相同,都為12個(gè)月。但序列A統(tǒng)計(jì)的是月銷(xiāo)售額,序列B統(tǒng)計(jì)的是季度銷(xiāo)售額。2條序列時(shí)間跨度相同描述間單位不同,即刻畫(huà)序列單位的粒度不同。為能應(yīng)用經(jīng)典的基于點(diǎn)對(duì)點(diǎn)距離的算法,需要人工干預(yù),使用時(shí)刻對(duì)等使得待比較的2條序列具有相同的粒度,即算法對(duì)時(shí)間粒度的敏感性不強(qiáng),如圖4所示。

圖4 時(shí)刻對(duì)等示意圖

綜上可以發(fā)現(xiàn),造成這些問(wèn)題的原因是所選的序列之間距離度量函數(shù)的自變量為單一離散點(diǎn)在坐標(biāo)軸中絕對(duì)位置坐標(biāo),沒(méi)有很好捕捉到因各種原因造成的坐標(biāo)偏移,使算法只能局限于序列微觀上的相似度量(距離相近)缺少了對(duì)于序列宏觀的相似度量的魯棒性(形態(tài)相近);并且距離函數(shù)自變量的選取忽視了對(duì)序列的形態(tài)識(shí)別能力,造成度量結(jié)果的不合理;與此同時(shí),離散的思維使得不能應(yīng)用更成熟的連續(xù)幾何性質(zhì)去做繼續(xù)的研究,不能挖掘到每一條時(shí)間序列的本質(zhì)權(quán)值,造成不能對(duì)規(guī)模巨大的待比較序列根據(jù)權(quán)值做分類(lèi)處理,不利于數(shù)據(jù)挖掘的后續(xù)工作,例如時(shí)間序列的相似性搜索[13]。

2 基于系數(shù)矩陣弧微分的相似度量理論分析

2.1 系數(shù)矩陣

為了能夠應(yīng)用連續(xù)幾何的性質(zhì),首先需要解決的問(wèn)題就是離散點(diǎn)的連續(xù)化。本文給出方法是利用統(tǒng)計(jì)學(xué)[14-15]中回歸模型——最小二乘法,其一般形式為y=f[x|θ]+ε,其由參數(shù)θ決定的回歸函數(shù),ε是不可觀測(cè)的隨機(jī)誤差。目標(biāo)是使得觀測(cè)點(diǎn)和估計(jì)點(diǎn)的距離平方達(dá)到最小,從而誤差達(dá)到最小。

設(shè)待擬合曲線的函數(shù)為:

y=a0+a1x+a2x2+…+akxk

(5)

假設(shè)時(shí)間序列的已知觀測(cè)點(diǎn)個(gè)數(shù)為n,根據(jù)最小二乘理論可知各點(diǎn)到這條曲線的距離和為:

(6)

求使得Q(θ)最小的a0,a1,…,ak值,對(duì)每一個(gè)a求偏導(dǎo):

令上式的偏導(dǎo)都為0,化簡(jiǎn)得:

將這組等式表示成矩陣形式:

即XA=Y,解此矩陣方程求出A,即可得到最佳的擬合曲線。其中X即為系數(shù)矩陣,由已知的觀測(cè)點(diǎn)和曲線方程的最高階數(shù)所決定,構(gòu)造系數(shù)矩陣的目的就是把研究的關(guān)注點(diǎn)從離散轉(zhuǎn)換成連續(xù)。

2.2 向量基

在矩陣方程XA=Y中,求得的A向量是擬合曲線未知數(shù)的系數(shù),顯然,這些系數(shù)刻畫(huà)著曲線的形態(tài)。形態(tài)不隨著曲線在坐標(biāo)系中絕對(duì)位置的改變而改變;每一條曲線都有自己的固有形態(tài),又因?yàn)樾螒B(tài)由A向量所決定,所以,本文將A向量稱之為向量基。

2.3 微分三角形

設(shè)左邊曲線的方程為Y=Y(X),X∈D;相應(yīng)地,右邊曲線的方程為y=y(x),x∈d,其中D、d為各自的定義域。設(shè)他們至少存在三階導(dǎo)數(shù),且二階導(dǎo)數(shù)處處不等于0。OA、OB分別是曲線Y=Y(X)上A、B點(diǎn)的曲率中心,曲率圓半徑分別為RA、RB;相應(yīng)地,rD、rE分別是曲線y=y(x)上點(diǎn)D、E對(duì)應(yīng)的曲率圓半徑。過(guò)點(diǎn)A做割線AB的垂線,并截取AC=RA-RB;過(guò)點(diǎn)D做割線DE的垂線,并截取DE=RD-RE。于是,由點(diǎn)A、B、C和對(duì)應(yīng)的點(diǎn)D、E,F組成一組對(duì)應(yīng)的直角三角形。由已知得,2條曲線光滑且連續(xù)。

(7)

滿足上式的點(diǎn)A、D稱之為最小相似點(diǎn),并稱2條曲線在A、D處最小相似,以點(diǎn)A和點(diǎn)D為直角端點(diǎn)構(gòu)成的2個(gè)直角三角形稱之為微分三角形。

圖5 微分三角形

2.4 最小相似點(diǎn)判定方程

在連續(xù)幾何圖形中可知,曲率描述著曲線和的彎曲程度,由曲線弧的長(zhǎng)度和切線夾角所決定,如圖6所示。

圖6 曲率定義示意圖

(8)

同理,有:

(9)

將式(8)和式(9)代入到最小相似點(diǎn)等式,得到最小相似點(diǎn)判定方程:

(10)

2.5 曲線相似的判定

首先引入2個(gè)幾何圖形相似的判定公理:如圖形D上點(diǎn)與圖形D′上兩對(duì)應(yīng)點(diǎn)的線段之比,是恒定的非零常量,就認(rèn)為圖形D與D′相似。

然后給出曲線完全相似的判定定理[16]:2條曲線在所考慮的區(qū)間內(nèi)同向,對(duì)應(yīng)的函數(shù)都存在至少三階導(dǎo)數(shù)且二階導(dǎo)數(shù)處處不為0。若滿足關(guān)系式(11),則2條曲線在給定的區(qū)間內(nèi)完全相似。在式(11)中,C為非零常量。

(11)

最后,給出完全相似的證明過(guò)程。

圖7 曲線微小分量相似示意圖

當(dāng)曲線上相鄰兩點(diǎn)Ak、Ak+1與對(duì)應(yīng)的Bk、Bk+1表示兩點(diǎn)間距離最大者,且Ak→Ak+1、Bk→Bk+1時(shí),得出曲線弧AiAi+1Ai+2…An～曲線弧BiBi+1Bi+2…Bn。再以An,Bn為新的對(duì)應(yīng)頂點(diǎn)(An、Bn是最小相似點(diǎn)),重復(fù)以上步驟,又得新的相似弧段,且相似比仍為C。把各個(gè)相似弧段順序連接起來(lái),得到2個(gè)邊長(zhǎng)為微小量的相似多邊形。

綜上,將待比較的2條曲線分治為多個(gè)以最小相似點(diǎn)為頂點(diǎn)構(gòu)成的多邊形,遞歸地論證個(gè)多邊形的相似比仍為C。根據(jù)公理,任意兩組相似點(diǎn)的之比即對(duì)應(yīng)的對(duì)角線之比為常數(shù),因此,2條曲線完全相似,證畢。

3 基于系數(shù)矩陣弧微分的相似度量算法

分析第2節(jié)各概念的推導(dǎo)過(guò)程可以發(fā)現(xiàn):1)離散的原始序列點(diǎn)是通過(guò)最小二乘法構(gòu)建的矩陣完成連續(xù)化的;2)微分三角形和最小相似點(diǎn)的定義借助了弧微分及其所建立的比例形式;3)最小相似點(diǎn)的判定方程是依靠弧微分導(dǎo)出的變量——曲率來(lái)完成的;4)曲線相似的定理及其證明過(guò)程也用到了弧微分的概念,不難發(fā)現(xiàn),弧微分在本文理論中的核心地位,因此,將本文算法命名為基于系數(shù)矩陣弧微分的時(shí)間序列相似度量算法(CMAD)。

第2節(jié)給出的2條曲線相似的定理,是使用等式建立的,結(jié)果就是2條候選曲線完全相似或者不相似,無(wú)法對(duì)其進(jìn)行相似性的其他微小度量,算法中不可以直接應(yīng)用,因此,本節(jié)引入一個(gè)概念——互相關(guān)函數(shù)。此概念來(lái)自信號(hào)分析[17-18],描述了隨機(jī)信號(hào)x(t)、y(t)在任意2個(gè)不同時(shí)刻t1、t2之間的相關(guān)程度,它是在某一頻域內(nèi)2個(gè)信號(hào)是否相關(guān)的一個(gè)判斷指標(biāo),定義為R(u)=x(t)*y(-t),其中*表示卷積,其結(jié)果大小所表示的意義在統(tǒng)計(jì)學(xué)界通常有如表1所示的結(jié)論。

表1 相關(guān)程度

根據(jù)第3節(jié)式(9),當(dāng)有如式(12)所示關(guān)系時(shí),2條曲線完全相似。

(12)

構(gòu)建2個(gè)互相關(guān)函數(shù):

其中:

可做以下分析:當(dāng)函數(shù)A(u)的結(jié)果處于相關(guān)程度較高的區(qū)間占整個(gè)結(jié)果的比率越高,說(shuō)明a(Y)與b(y)越相關(guān),越滿足式(12)的第1個(gè)等式;同理,當(dāng)函數(shù)B(v)的結(jié)果在滿足上一個(gè)條件的同時(shí),并且在給定的區(qū)間內(nèi)結(jié)果穩(wěn)定,說(shuō)明c(Y)與d(y)越相關(guān),越滿足式(12)的第2個(gè)等式。當(dāng)2個(gè)條件都滿足時(shí),說(shuō)明2條曲線越相似,又曲線是原始時(shí)間序列根據(jù)刻畫(huà)的形態(tài)向量基連續(xù)化而來(lái),因此兩條時(shí)間序列也就越相似,達(dá)到了相似性度量的目的。本文算法描述如下:

算法基于系數(shù)矩陣弧微分的時(shí)間序列相似度量算法(CMAD)。

輸入原始時(shí)間序列X=,Y=

輸出互相關(guān)函數(shù)結(jié)果序列。

1)判斷2條原始序列的長(zhǎng)度是否為大量,如果超出一定規(guī)模,使用線性分段表示對(duì)序列進(jìn)行壓縮、降維,否則轉(zhuǎn)步驟2)。

2)對(duì)2條序列的離散點(diǎn)應(yīng)用系數(shù)矩陣進(jìn)行連續(xù)化。

3)依據(jù)式(11)求出各等式要素。

4)使用各要素構(gòu)建互相關(guān)函數(shù)。

5)在給定的區(qū)間內(nèi),對(duì)互相關(guān)函數(shù)結(jié)果進(jìn)行檢測(cè)(當(dāng)m=n時(shí),只需在原始離散點(diǎn)所在同一區(qū)間進(jìn)行檢測(cè);當(dāng)m≠n時(shí),為了說(shuō)明程序的魯棒性,需要在原始離散點(diǎn)的2個(gè)不同區(qū)間分別檢測(cè))。

6)根據(jù)檢測(cè)結(jié)果,對(duì)時(shí)間序列X、Y的相似性進(jìn)行綜合判定。

在上述算法中,步驟1)判斷原始序列可通過(guò)線性掃描,在對(duì)序列壓縮可選用線性分段表示,這兩小步的時(shí)間復(fù)雜度均為O(n)。步驟2)和步驟3)通過(guò)最小二乘思想求系數(shù)矩陣的元素,計(jì)算(n+1)個(gè)偏導(dǎo)數(shù)方程:T1(n)=O((n+1)×f(n))=O(f(n))=O(n)。步驟4)～步驟5)所構(gòu)建互相關(guān)函數(shù)的最高次冪為2,所以,T2(n)=O(f2(n))=O(n2)。綜上所述,CMAD算法時(shí)間復(fù)雜度為O(n2)。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)運(yùn)行環(huán)境為:CPU2.0 GHz、內(nèi)存8 GB、500 GB硬盤(pán),Windows7系統(tǒng)上實(shí)現(xiàn)。開(kāi)發(fā)工具為Matlab2014a。

4.2 實(shí)驗(yàn)方法

為驗(yàn)證CMAD算法的可行性和優(yōu)越性,本文將做3個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)1的關(guān)注點(diǎn)是:待比較序列是等跨度且時(shí)間粒度不同;實(shí)驗(yàn)2關(guān)注點(diǎn)是:對(duì)原始序列進(jìn)行分段線性表示后,再對(duì)2條等跨度、粒度不同的序列進(jìn)行相似度量;實(shí)驗(yàn)3的關(guān)注點(diǎn)是:2條時(shí)間序列跨度不相同。CMVB算法針對(duì)擬合函數(shù),y=a0+a1x+a2x2+…+akxk要求連續(xù)化后的函數(shù)至少存在三階導(dǎo)數(shù)且二階導(dǎo)數(shù)處處不為零,為了算法簡(jiǎn)便,3個(gè)實(shí)驗(yàn)統(tǒng)一把函數(shù)未知數(shù)x的最高次冪定為3。

4.2.1 實(shí)驗(yàn)1

實(shí)驗(yàn)數(shù)據(jù)來(lái)自http://www.bundesbank.de/網(wǎng)站,是證券市場(chǎng)版塊下的Time series WU0053:Gross sales of domestic debt securities at nominal value。2個(gè)時(shí)間序列數(shù)據(jù)都選自1985年—1989年,時(shí)間序列A的取樣周期為每個(gè)季度一次,共20個(gè)數(shù)據(jù);時(shí)間序列B的取樣周期為每個(gè)月一次,共60個(gè)數(shù)據(jù)。2個(gè)序列如圖8所示。

圖8 不同粒度的序列

時(shí)間序列A、B是同一debt securities的不同時(shí)間粒度的2組觀測(cè)值,本質(zhì)上是同一事物,如果想要應(yīng)用傳統(tǒng)的基于離散點(diǎn)距離函數(shù)的算法,首先需要人工時(shí)刻對(duì)等;其次結(jié)果往往是不能很好判定2條序列相似的。應(yīng)用CMVB算法,互相關(guān)函數(shù)在同一區(qū)間結(jié)果如表2所示,穩(wěn)定性分析結(jié)果如圖9所示。

表2 相關(guān)程度分布 %

圖9 穩(wěn)定性分析結(jié)果

根據(jù)表2可知:1)函數(shù)A(u)的結(jié)果處于相關(guān)程度高的區(qū)間的比率達(dá)58.3%;2)函數(shù)B(v)的結(jié)果較為穩(wěn)定且在高相關(guān)的區(qū)間比率高。由上述結(jié)論可知時(shí)間序列A、B相似,符合真實(shí)數(shù)據(jù)本來(lái)結(jié)果,驗(yàn)證了CMVB算法的可行性。

如果用傳統(tǒng)的時(shí)間序列相似度量方法,需要增加以下時(shí)刻對(duì)等步驟:

1)將tA序列和tB序列進(jìn)行歸并,序列值合并并去除重復(fù)值,得到對(duì)等后的標(biāo)準(zhǔn)時(shí)刻序列:t={t1,t2,…,tw}。

2)通過(guò)遍歷循環(huán)分別找到tA序列和tB序列的值在t序列中的位置序列:loc1序列和loc2序列。

3)遍歷A和B序列,對(duì)A和B序列進(jìn)行插值補(bǔ)充,最終得到時(shí)刻對(duì)等后的序列Aplr和Bplr。

4.2.2 實(shí)驗(yàn)2

實(shí)際應(yīng)用中的時(shí)間序列數(shù)據(jù)往往是海量、高維、易受干擾的,直接對(duì)原始時(shí)間序列進(jìn)行挖掘不僅時(shí)間和空間效率低下,而且算法的可靠性和準(zhǔn)確性也容易受到影響,因此,在對(duì)時(shí)間序列挖掘之間往往需要壓縮等預(yù)處理,常見(jiàn)方法時(shí)分段線性表示方法,本文在此應(yīng)用基于斜率提取邊緣點(diǎn)的時(shí)間序列分段線性表示方法PLR_SEEP。

設(shè)有時(shí)間序列X=,提取點(diǎn)集合為〈xi1,xi2,…,xik〉,且1≤i1≤i2≤…≤ik≤n。

根據(jù)式(3),時(shí)間序列的PLR_SEEP[19]表示為:

(11)

其中,L(x,y)表示連接趨勢(shì)點(diǎn)x和y之間的線性函數(shù)。公式可以簡(jiǎn)單表示為:

XT=〈L(xi1,xi2),L(xi2,xi3),…,L(xik-1,xik)〉

本實(shí)驗(yàn)的原始數(shù)據(jù)與實(shí)驗(yàn)1相同,首先應(yīng)用SEEP算法對(duì)序列B進(jìn)行預(yù)處理,使其壓縮率為15%,保留45個(gè)數(shù)據(jù);序列A點(diǎn)較少,不進(jìn)行預(yù)處理,2條序列如圖10所示。

圖10 分段線性表示預(yù)處理

預(yù)處理后再對(duì)序列A,XT應(yīng)用CMVB算法,互相關(guān)函數(shù)的結(jié)果如表3所示。由圖11和實(shí)驗(yàn)1的分析可知,序列A、XT相似,從而序列A、B相似。

表3 分段線性表示后的相關(guān)程度分布 %

圖11 分段線性表示后的穩(wěn)定性分析結(jié)果

4.2.3 實(shí)驗(yàn)3

實(shí)驗(yàn)數(shù)據(jù)來(lái)自我國(guó)某一海港港口,記錄了每個(gè)月的集裝箱月吞吐量。序列A記錄了2013年12個(gè)月的吞吐情況;序列B記錄了2013年—2014年24個(gè)月的吞吐情況,如圖12所示。

圖12 時(shí)間跨度不相同的2條序列

顯然待比較的2條序列時(shí)間跨度不相同,傳統(tǒng)的基于離散點(diǎn)距離函數(shù)的算法失效,基于動(dòng)態(tài)時(shí)間彎曲的算法又過(guò)于復(fù)雜,在此應(yīng)用CMVB算法。因?yàn)?條序列的區(qū)間不相同,為了驗(yàn)證算法的可靠性,構(gòu)造的互相關(guān)函數(shù)需要分別在2個(gè)區(qū)間上驗(yàn)證,結(jié)果如表4、表5和圖13和圖14所示。可以看出,互相關(guān)函數(shù)的結(jié)果在2個(gè)區(qū)間都有較好反映,說(shuō)明了2個(gè)區(qū)間原始序列較為相似,符合直觀認(rèn)知。

表4 互相關(guān)函數(shù)12個(gè)月記錄相關(guān)程度分布 %

表5 互相關(guān)函數(shù)24個(gè)月記錄相關(guān)程度分布 %

圖13 CMAD算法12個(gè)月記錄穩(wěn)定性分析結(jié)果

圖14 CMAD算法24個(gè)月記錄穩(wěn)定性分析結(jié)果

綜合以上3個(gè)實(shí)驗(yàn),可以得出以下結(jié)論:CMAD算法對(duì)于跨度相同、時(shí)間粒度不同的候選序列不需要人工干預(yù)也可很好地完成相似性度量的任務(wù),并且對(duì)于數(shù)據(jù)規(guī)模較大序列應(yīng)用分段線性表示后,仍可以較好地進(jìn)行相似性度量,算法有著較強(qiáng)的穩(wěn)定性;對(duì)于時(shí)間跨度不相同的序列,可以完成2條序列宏觀意義上的相似性——形態(tài)相近,具有較強(qiáng)的魯棒性。

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

選擇一個(gè)合適的時(shí)間序列相似度量算法是時(shí)間序列數(shù)據(jù)挖掘的重要前提。本文提出的CMAD算法首先利用系數(shù)矩陣對(duì)離散序列點(diǎn)連續(xù)化,然后分析連續(xù)曲線的弧微分與曲率半徑微分的關(guān)系,找出相似性判定等式,最后通過(guò)互相關(guān)函數(shù)完成最終的時(shí)間序列相似性度量。實(shí)驗(yàn)結(jié)果表明,該算法可同時(shí)完成距離相近度量和形狀相似度量,具有良好的適用性和可行性,利于后續(xù)數(shù)據(jù)挖掘的工作進(jìn)程。下一步將在本文算法基礎(chǔ)上進(jìn)行海量數(shù)據(jù)的時(shí)間序列相似性度量。

[1] ZHAI Yuanzheng,WAHG Jinsheng,TENG Yangguo,et al.Water Demand Forecasting of Beijing Using the Time Series Forecasting Method[J].Journal of Geographical Science,2012,22(5):919-932.

[2] FCUHS E,GRUBER T,NITSCHKE J,et al.On-line Segmentation of Time Series Based on Polynomial Least-squares Approximation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(12):2232-2245.

[3] MACIEJ K,GRAZYNA S.An Approach to Dimensionality Reduction in Time Series[J].Information Science,2014,26(6):15-36.

[4] GUERRERO J L,BERLANGA A,GARCIA J,et al.Piecewise Linear Representation Segmentation as a Multiobjective Optimization Problem[M]//JANUSZ K.Advances in Intelligent and Soft Computing.Berlin,Germany:Springer,2010:267-274.

[5] MUEEN A,DING H,TRAJCEVSKI G,et al.Experimental Comparison of Representation Method and Distance Measures for Time Series Data[J].Data Mining and Knowledge Discovery,2012,26(2):275-309.

[6] EHMKE J F,MEISEL S,MATTFELD D C.Floating Car Based Travel Times for City Logistics[J].Trans-portation Research,Part C:Emerging Technologies,2012,21(1):338-352.

[7] AGRAWAL R,FALOUTSOS C,SWAMI A.Efficient Similarity Search in Sequence Databases[C]//Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms.Washington D.C.,USA:IEEE Computer Society,1993:69-84.

[8] KEOGH E,PAZZANI M.Derivative Dynamic Time Warping[C]//Proceedings of the 1st SIAM Inter-national Conference on Data Mining.Chicago,USA:SIAM,2001:1-11.

[9] LIN J,KEOGH E,LONARDI S,et al.A Symbolic Representation of Time Series,with Implications for Streaming Algorithms[C]//Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.New York,USA:ACM Press,2003:2-11.

[10] KEOGH E,LONARDI S,RATANAMAMATANA C A,et al.Compression-based Data Mining of Sequential Data[J].Data Mining and Knowledge Discovery,2007,14(1):99-129.

[11] 潘 定,沈鈞毅.時(shí)態(tài)數(shù)據(jù)挖掘的相似性發(fā)現(xiàn)技術(shù)[J].軟件學(xué)報(bào),2007,18(2):246-258.

[12] NOPIAH Z M,KHAIRIR M I,ABDULLAH S,et al.Peakvalley Segmentation Algorithm for Kurtosis Analysis and Classification of Fatigue Time Series Data[J].European Journal of Scientific Research,2009,29(1):113-125.

[13] SAKOE H,CHIBA S.Dynamic Programming Algorithm Optimization for Spoken Word Recognition[J].IEEE Transactions on Acoustics,Speech,and Signal Processing,1978,26(1):43-49.

[14] GUESTRINT C,BODIKZ P,THIBAUXT R,et al.Distributed Regression:An Efficient Framework for Modeling Sensor Network Data[C]//Proceedings of ACM International Conference on Sensor Networks.New York,USA:ACM Press,2004:1-10.

[15] DELIGIANNAKIS A,KOTIDIS Y,ROUSSOPOULOS N.Compressing Historical Information in Sensor Networks[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2004:527-538.

[16] 張智廣,趙學(xué)敏.平面曲線相似性初探[J].天津師范大學(xué)學(xué)報(bào),1998,18(2):65-72.

[17] BECKOUCHE S,MA Jianwei.Simultaneous Dictionary Learning and Denoising for Seismic Data[J].Geophysics,2014,79(3):27-31.

[18] SONG Jun,LIU Yu,WANG Xudong.Improved Denoising Algorithm for Narrow-band Signal and Its Application[J].Journal of Vibration and Shock,2013,32(16):59-62.

[19] 詹艷艷,徐榮聰,陳曉云.基于斜率提取邊緣點(diǎn)的時(shí)間序列分段線性表示方法[J].計(jì)算機(jī)科學(xué),2006,33(11):139-142.