基于趨勢(shì)的時(shí)間序列相似性度量方法

基于趨勢(shì)的時(shí)間序列相似性度量方法

0基于時(shí)間序列趨勢(shì)的相似性度量時(shí)間序列是時(shí)間序列之后的幾名實(shí)物的序列，反映了時(shí)間序列中實(shí)體屬性的函數(shù)。時(shí)間序列匹配在位置定位(locationbasedservice,LBS)系統(tǒng)、環(huán)境監(jiān)測(cè)、物聯(lián)網(wǎng)等領(lǐng)域中有廣泛的應(yīng)用。由于時(shí)間序列(確定時(shí)間序列和不確定時(shí)間序列)的長(zhǎng)度很大,并且不確定時(shí)間序列在每個(gè)觀察點(diǎn)的觀察值具有不確定性,導(dǎo)致了維度災(zāi)難和龐大的可能世界,使得時(shí)間序列相似性度量和聚類挖掘的時(shí)間代價(jià)過(guò)高。本文提出了基于時(shí)間序列變化趨勢(shì)的相似性度量方法和聚類方法,其中基于趨勢(shì)的相似性度量方法首先對(duì)時(shí)間序列進(jìn)行區(qū)間劃分和區(qū)間內(nèi)的趨勢(shì)判斷,生成短的趨勢(shì)符號(hào)序列,然后計(jì)算各趨勢(shì)符號(hào)的一階連接性指數(shù),最后通過(guò)計(jì)算兩序列中各趨勢(shì)符號(hào)一階連接性指數(shù)的塔尼莫特系數(shù)完成相似性度量?；谮厔?shì)的聚類方法通過(guò)定義趨勢(shì)高度,迭代判斷趨勢(shì)符號(hào)序列的趨勢(shì)變化,并構(gòu)建趨勢(shì)樹(shù)完成聚類。1相關(guān)工作1.1基于時(shí)間序列聚類分析的精度改進(jìn)時(shí)間序列相似性問(wèn)題最早是由Agrawal等人提出的,將該問(wèn)題定義為:在大規(guī)模的時(shí)間序列數(shù)據(jù)庫(kù)里,通過(guò)一定的相似性匹配方式,查詢出和已知序列相匹配的時(shí)間序列集合,相似是基于距離函數(shù)來(lái)衡量的。Agrawal率先使用等長(zhǎng)時(shí)間序列的歐氏距離度量時(shí)間序列間的相似度,歐氏(Euclid)距離是最基本的,而明考夫斯基(Mikowski)距離則是對(duì)歐氏距離的推廣。Berndt等人在文獻(xiàn)中引入了在語(yǔ)音識(shí)別中被廣泛使用的DTW(dynamictimewarping)距離作為時(shí)間序列的相似性度量距離。文獻(xiàn)[3,4]闡述了這種基于非線性規(guī)整技術(shù)的算法可以獲得很高的識(shí)別和匹配精度,尤其對(duì)時(shí)間序列在時(shí)間軸上的形狀扭曲有非常優(yōu)秀的辨識(shí)能力。但是DTW的計(jì)算復(fù)雜度較高,并且DTW不滿足距離的三角不等式。Keogh在文獻(xiàn)中分析了DTW距離的特性,針對(duì)時(shí)間序列索引和查詢提出了基于時(shí)間序列邊界的DLB_Keogh距離。這是目前最好的時(shí)間序列度量距離,但是DLB_Keogh距離不是一種對(duì)稱的時(shí)間序列距離度量,所以并不適合直接應(yīng)用于時(shí)間序列的聚類。編輯距離(editdistance)是計(jì)算兩字符串符號(hào)序列距離的一種度量,它的定義是將一字符串轉(zhuǎn)換為另一字符串所需的最小編輯(插入、刪除、改變)步數(shù)。該方法充分利用了字符串匹配等成熟計(jì)算方法,但是需要將時(shí)間序列轉(zhuǎn)換成相應(yīng)的字符串,精度不高。文獻(xiàn)[6,7]使用了ARMA模型表示時(shí)間序列數(shù)據(jù),并通過(guò)定義基于兩個(gè)模型的距離公式進(jìn)行相似性度量。Wang等人將HMM模型應(yīng)用到時(shí)間序列數(shù)據(jù)聚類研究中,并在公共數(shù)據(jù)集上進(jìn)行了測(cè)試,獲得了良好的效果。其他相似性度量方式,如Swale模型、SpADe距離等在時(shí)間序列相似性度量領(lǐng)域也得到了廣泛的應(yīng)用。1.2時(shí)間序列差異度公式MacQue在1967年提出的K-means算法,是一種被廣泛應(yīng)用于科學(xué)研究和工業(yè)應(yīng)用中的經(jīng)典聚類算法。K-means算法的核心思想是把一個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類,使每個(gè)聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小。Huang等人在文獻(xiàn)[11,12]中為克服K-means算法僅適合于數(shù)值屬性數(shù)據(jù)聚類的局限性,提出了一種適合于分類屬性數(shù)據(jù)聚類的K-modes算法,并證明了經(jīng)過(guò)有限次迭代,K-modes算法收斂于局部最小值。文獻(xiàn)為了刻畫時(shí)間序列趨勢(shì)的內(nèi)在規(guī)律特征,在K-means算法的基礎(chǔ)上提出了基于劃分的K_SC算法,并給出了新的時(shí)間序列差異度公式,保證任意兩個(gè)時(shí)間序列的相似性只與它們的趨勢(shì)走向有關(guān),而與它們的峰值數(shù)值以及在何時(shí)達(dá)到峰值無(wú)關(guān)。時(shí)間序列聚類是一種完全根據(jù)數(shù)據(jù)自身所提供的信息進(jìn)行分類的一種方法,根據(jù)相似性度量方式不同,時(shí)間序列的聚類主要分為基于距離的時(shí)間序列聚類、基于特征的時(shí)間序列聚類和基于模型的時(shí)間序列聚類三種。1990年,Kosmelj等人提出了relocation聚類算法,該算法采用歐氏距離進(jìn)行距離度量,可以對(duì)多變量等長(zhǎng)時(shí)序數(shù)據(jù)進(jìn)行聚類分析。Golay等人將模糊C-均值方法應(yīng)用到磁共振數(shù)據(jù)(單變量等長(zhǎng)數(shù)據(jù))中,對(duì)人腦行為進(jìn)行分析,采用歐氏距離作為距離度量方法。文獻(xiàn)對(duì)模糊C-均值聚類方法進(jìn)行了改進(jìn),該方法使用STS距離度量,被應(yīng)用于DNA序列檢測(cè)。Fu等人在文獻(xiàn)中沿時(shí)間軸使用一個(gè)連續(xù)的滑動(dòng)窗口,通過(guò)自組織映射方法提取序列中關(guān)鍵的時(shí)間點(diǎn)。最終,用多個(gè)關(guān)鍵點(diǎn)來(lái)代替整個(gè)時(shí)間序列,使用改進(jìn)的SOM聚類算法進(jìn)行聚類。Owsley等人提出了序列集群細(xì)化算法(SCRA),通過(guò)模式匹配發(fā)現(xiàn)大批量數(shù)據(jù)信號(hào)的代表性數(shù)據(jù),最終形成一個(gè)高分辨率的有代表性的部分?jǐn)?shù)據(jù)集合。文獻(xiàn)通過(guò)尋找時(shí)間序列的關(guān)鍵點(diǎn),利用改進(jìn)的FCM算法完成時(shí)間序列的動(dòng)態(tài)聚類。2各時(shí)間序列的描述確定時(shí)間序列表示為每個(gè)時(shí)間點(diǎn)上有一個(gè)確定采樣值的有序序列;不確定時(shí)間序列的不確定性表示為每個(gè)時(shí)間點(diǎn)的樣本觀測(cè)值的集合,每一個(gè)時(shí)間點(diǎn)的取值用一個(gè)隨機(jī)變量來(lái)表示,不確定時(shí)間序列是具有時(shí)間特性的隨機(jī)變量的有序序列。定義1時(shí)間序列。長(zhǎng)度為n的時(shí)間序列由一條包含n個(gè)元素的序列組成,時(shí)間序列記為TS={(t1,X1,P1),(t2,X2,P2),…,(tn,Xn,Pn)}。其中,ti代表第i個(gè)時(shí)間點(diǎn),每條元組中的屬性用變量Xt和Pt表示,Xt代表第t時(shí)刻觀察值的集合,記為Xt={xt,1,xt,2,…,xt,s};Pt代表第t時(shí)刻觀察值取值概率的集合,記為Pt={pt,1,pt,2,…,pt,s},s為集合Xt的基數(shù)即樣本觀察值的個(gè)數(shù)。當(dāng)s=1時(shí),TS表示確定時(shí)間序列,且Pt={1.0}。確定時(shí)間序列數(shù)據(jù)集如表1所示。當(dāng)s≠1時(shí),TS表示不確定時(shí)間序列。不確定時(shí)間序列的數(shù)據(jù)集如表2所示。3基于序列趨勢(shì)的相似性測(cè)量3.1tdd結(jié)果與區(qū)間趨勢(shì)定義2序列區(qū)間。給定長(zhǎng)度為n的時(shí)間序列T和分割的區(qū)間長(zhǎng)度L(L≥3),將時(shí)間序列T分割為k=n/L個(gè)等長(zhǎng)且連續(xù)的區(qū)間,稱為k個(gè)序列區(qū)間,分別記為i1,i2,…,ik。如果n≠k×L,則舍棄k×L+1到n的序列部分。區(qū)間ij(1≤j≤k)的區(qū)間范圍為[(j-1)×L,j×L],區(qū)間ij(1≤j≤k)的下邊界記為low(ij),上邊界記為high(ij),則L=high(ij)-low(ij),并且對(duì)于區(qū)間ij(1≤j<k),high(ij)=low(ij+1)。定義3區(qū)間趨勢(shì)。給定長(zhǎng)度為n的時(shí)間序列T和分割后的k個(gè)序列區(qū)間i1,i2,…,ik,時(shí)間序列在區(qū)間ij(1≤j≤k)內(nèi)的變化趨勢(shì)為區(qū)間趨勢(shì),記為tdj,tdj∈{tdup,tddw,tdst,tdpk,tdth}。其中:tdup為時(shí)間序列在分割區(qū)間內(nèi)呈現(xiàn)上升趨勢(shì);tddw為時(shí)間序列在分割區(qū)間內(nèi)呈現(xiàn)下降趨勢(shì);tdst為時(shí)間序列在分割區(qū)間內(nèi)呈現(xiàn)平緩趨勢(shì);tdpk為時(shí)間序列在分割區(qū)間內(nèi)取得峰值;tdth為時(shí)間序列在分割區(qū)間內(nèi)取得谷值。五種區(qū)間趨勢(shì)tdup,tddw,tdst,tdpk,tdth如表3所示,并且區(qū)間趨勢(shì)與趨勢(shì)符號(hào)一一對(duì)應(yīng),與此對(duì)應(yīng)的趨勢(shì)符號(hào)為tsup,tsdw,tsst,tspk,tsth。對(duì)長(zhǎng)度為n的時(shí)間序列T進(jìn)行序列區(qū)間分割和各區(qū)間趨勢(shì)判斷,具體步驟如下:a)計(jì)算序列T的期望序列Texp。如果T為確定時(shí)間序列,則Texp=T;如果T為不確定時(shí)間序列,則Texp={(t1,X1P1),(t2,X2P2),…,(tn,XnPn)},其中XiPi=xi,1×pi,1+xi,2×pi,2+…+xi,s×pi,s(1≤i≤n)。b)根據(jù)分割的區(qū)間長(zhǎng)度L,將期望序列Texp分割為k個(gè)序列區(qū)間,分別記為i1,i2,…,ik。記錄Texp在區(qū)間ij(1≤j≤k)內(nèi)的區(qū)間開(kāi)始點(diǎn)、區(qū)間中間點(diǎn)和區(qū)間結(jié)束點(diǎn)的取值V1、V2、V3,以及在該區(qū)間內(nèi)的最大取值Vmax和最小取值Vmin。根據(jù)表4(α為趨勢(shì)系數(shù))所示的判斷條件判斷區(qū)間ij內(nèi)的時(shí)間序列趨勢(shì),即序列區(qū)間ij的區(qū)間趨勢(shì)。定義4趨勢(shì)符號(hào)序列。給定長(zhǎng)度為n的時(shí)間序列T,在分割為k個(gè)序列區(qū)間并判斷每個(gè)序列區(qū)間內(nèi)的區(qū)間趨勢(shì)后,每個(gè)序列區(qū)間與一個(gè)區(qū)間趨勢(shì)對(duì)應(yīng),同樣每個(gè)序列區(qū)間與一個(gè)趨勢(shì)符號(hào)對(duì)應(yīng),將趨勢(shì)符號(hào)從左向右依次連接后形成的序列稱為時(shí)間序列T的趨勢(shì)符號(hào)序列,記為SL(T)={(i1,ts1),(i2,ts2),…,(ik,tsk)},其中tsj∈{tsup,tsdw,tsst,tspk,tsth}(1≤j≤k)。3.2時(shí)間序列的相似度通過(guò)引入在化學(xué)分子結(jié)構(gòu)研究和基因序列相似性研究中普遍使用的一階連接性指數(shù),以及塔尼莫特系數(shù)完成時(shí)間序列的相似性度量。定義5趨勢(shì)位置信息。給定長(zhǎng)度為k的趨勢(shì)符號(hào)序列SL(T),比較趨勢(shì)符號(hào)ts(ts∈{tsup,tsdw,tsst,tspk,tsth})和SL(T)中的每一個(gè)趨勢(shì)符號(hào)tsj(1≤j≤k且tsj∈{tsup,tsdw,tsst,tspk,tsth}),如果ts=tsj,則ts在位置j的信息為j/k;通過(guò)遍歷SL(T)得到趨勢(shì)符號(hào)ts在SL(T)的全部信息,并將其按照從左向右的順序組織為序列,稱該序列為ts在T中的趨勢(shì)位置信息,記為L(zhǎng)T(ts)=(LT,1(ts),LT,2(ts),…,LT,l(ts))。其中l(wèi)是在SL(T)中滿足ts=tsj的tsj個(gè)數(shù)。給定趨勢(shì)符號(hào)ts在趨勢(shì)符號(hào)序列SL(T)中的趨勢(shì)位置信息LT(ts),則ts在T中的一階連接性指數(shù)為IdT(ts)=(LT,1(ts)×LT,2(ts))-0.5+(LT,2(ts)×LT,3(ts))-0.5+…+(LT,l-1(ts)×LT,l(ts))-0.5,其中ts∈{tsup,tsdw,tsst,tspk,tsth}。例1給定SL(T1)={(i1,tspk),(i2,tsst),(i3,tsup),(i4,tsdw),(i5,tsh),(i6,tsst),(i7,tsup),(i8,tsdw),(i9,tsh),(i10,tspk),(i11,tsst),(i12,tsup),(i13,tsdw),(i14,tsth),(i15,tsst)}。tsdw在T1中的趨勢(shì)位置信息LT1(tsdw)=(4/15,8/15,13/15),tsdw在時(shí)間序列T1中的一階連接性指數(shù)IdT1(tsdw)=(4/15×8/15)-0.5+(8/15×13/15)-0.5=4.12。時(shí)間序列T1中五種趨勢(shì)符號(hào)的一階連接性指數(shù)對(duì)應(yīng)為IdT1(tsup),IdT1(tsdw),IdT1(tsst),IdT1(tspk),IdT1(tsth);時(shí)間序列T2中五種趨勢(shì)符號(hào)的一階連接性指數(shù)對(duì)應(yīng)為IdT2(tsup),IdT2(tsdw),IdT2(tsst),IdT2(tspk),IdT2(tsth),則時(shí)間序列T1和T2的相似度通過(guò)塔尼莫特系數(shù)ST1,T2(ST1,T2∈[0,1])來(lái)衡量。如果ST1,T2>ε,則時(shí)間序列T1和T2相似,否則兩序列不相似。其中ε為相似性閾值,ST1,T2如式(1)所示。3.3基于趨勢(shì)的時(shí)間復(fù)雜度分析基于趨勢(shì)的時(shí)間序列相似性匹配算法輸入:時(shí)間序列Q,時(shí)間序列集合D={T1,T2,…,Tm},其中m是序列集合的尺寸,Ti={(t1,X1,P1),(t2,X2,P2),…,(tn,Xn,Pn)}(1≤i≤m);序列區(qū)間分割子程序Div_Sl;區(qū)間趨勢(shì)判斷和趨勢(shì)符號(hào)序列生成子程序Td_Sl;趨勢(shì)位置信息及一階連接性指數(shù)計(jì)算子程序CN_ID;塔尼莫特系數(shù)計(jì)算子程序CA_MT;相似性閾值ε。輸出:匹配的時(shí)間序列集合S。基于趨勢(shì)的時(shí)間序列相似性匹配算法的時(shí)間復(fù)雜度分析如下(首先討論不確定時(shí)間序列的情況):a)步驟1的時(shí)間復(fù)雜度為O(1)。b)步驟2~4計(jì)算時(shí)間序列Q中五種趨勢(shì)符號(hào)的一階連接性指數(shù)。首先步驟2計(jì)算Q的期望序列,該步驟需要遍歷時(shí)間序列的每個(gè)觀察值,該步驟的時(shí)間復(fù)雜度為O(ns),s為時(shí)間序列觀察點(diǎn)的觀察值個(gè)數(shù);然后步驟3對(duì)期望序列進(jìn)行序列區(qū)間劃分和區(qū)間趨勢(shì)判斷,并生成趨勢(shì)符號(hào)序列,該步驟需要遍歷期望序列的每個(gè)觀察點(diǎn),該步驟的時(shí)間復(fù)雜度為O(n);步驟4計(jì)算趨勢(shì)符號(hào)序列中五種趨勢(shì)符號(hào)的一階連接性指數(shù),該步驟的時(shí)間復(fù)雜度為O(5k),其中k為趨勢(shì)符號(hào)序列的長(zhǎng)度。由于k<n,步驟2~4的時(shí)間復(fù)雜度為O(ns)。c)同理,步驟6~8的時(shí)間復(fù)雜度為O(ns)。d)步驟9計(jì)算兩時(shí)間序列五種趨勢(shì)符號(hào)的塔尼莫特系數(shù),該步驟的時(shí)間復(fù)雜度為O(1);步驟5~11需要遍歷數(shù)據(jù)庫(kù)中的m條時(shí)間序列,并進(jìn)行相似性度量,則步驟5~11的時(shí)間復(fù)雜度為O(mns)。綜上所述,對(duì)不確定時(shí)間序列進(jìn)行基于趨勢(shì)的相似性匹配,時(shí)間復(fù)雜度為O(mns);同理可得對(duì)確定時(shí)間序列進(jìn)行基于趨勢(shì)的相似性度量,時(shí)間復(fù)雜度為O(mn)。4基于序列趨勢(shì)的集群4.1生成趨勢(shì)符號(hào)序列定義6趨勢(shì)高度。給定趨勢(shì)符號(hào)ts(ts∈{tsup,tsdw,tsst,tspk,tsth}),ts對(duì)應(yīng)唯一的數(shù)值,稱ts對(duì)應(yīng)的唯一數(shù)值為趨勢(shì)高度,記為th。ts與th(th∈[0,1])的對(duì)應(yīng)關(guān)系記為(ts,th),則五種趨勢(shì)符號(hào)和其趨勢(shì)高度的對(duì)應(yīng)關(guān)系表示為{(tsup,0.25),(tsdw,0.75),(tsst,0.5),(tspk,0),(tsth,1.0)},該對(duì)應(yīng)關(guān)系保證趨勢(shì)類型越相近,趨勢(shì)之間趨勢(shì)高度差越小。根據(jù)定義6,每個(gè)趨勢(shì)符號(hào)與唯一的數(shù)值對(duì)應(yīng),則趨勢(shì)符號(hào)序列SL1(T)可轉(zhuǎn)換為每個(gè)時(shí)間點(diǎn)有一個(gè)確定觀察值的時(shí)間序列,記為TL1(T),其中SL1(T)=SL(T)。將TL1(T)中每三個(gè)觀察點(diǎn)劃分為一個(gè)區(qū)間,并根據(jù)觀察值進(jìn)行趨勢(shì)判斷,生成新的趨勢(shì)符號(hào)序列SL2(T)。對(duì)SL1(T)進(jìn)行i次上述過(guò)程的迭代處理后,生成的趨勢(shì)符號(hào)序列記為SLi+1(T),其中i≤log3k,并且SLi+1(T)對(duì)應(yīng)的確定時(shí)間序列記為TLi+1(T),進(jìn)行m=log3k次迭代后,生成的趨勢(shì)符號(hào)序列SLm+1(T)=ts,其中ts∈{tsup,tsdw,tsst,tspk,tsth}。由TLi(T)(1≤i≤m)確定SLi+1(T)的步驟如下:a)SLi+1(T)的第j(1≤j≤k/3i)個(gè)趨勢(shì)符號(hào)由TLi(T)中的觀察點(diǎn)3j-2到觀察點(diǎn)3j的觀察值確定,三個(gè)觀察值分別記為th1,th2,th3。b)根據(jù)表5所示的判定條件判定SLi+1(T)的第j個(gè)趨勢(shì)符號(hào)。定義7趨勢(shì)樹(shù)。給定趨勢(shì)符號(hào)序列SL(T),如果滿足以下條件則根據(jù)SL(T)構(gòu)建的樹(shù)為趨勢(shì)樹(shù)tree(T),其中SL(T)長(zhǎng)度為k,tree(T)的高度為h,k=3h-1。a)tree(T)的第1層的k個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)SL(T)的k個(gè)趨勢(shì)符號(hào)。b)tree(T)的第i(1<i<h)層的中間節(jié)點(diǎn)對(duì)應(yīng)SLi(T)(SLi(T)的長(zhǎng)度為k/3i-1)中的k/3i-1個(gè)趨勢(shì)符號(hào)。c)tree(T)的第h層只有一個(gè)節(jié)點(diǎn),即根節(jié)點(diǎn),并且根節(jié)點(diǎn)為趨勢(shì)符號(hào)ts=SLh(T)。例2設(shè)SL(T2)={(i1,tspk),(i2,tsst),(i3,tsup),(i4,tsdw),(i5,tsth),(i6,tsst),(i7,tsup),(i8,tsdw),(i9,tsth),(i10,tspk),(i11,tsst),(i12,tsup),(i13,tsdw),(i14,tsth),(i15,tsst),(i16,tsup),(i17,tsdw),(i18,tsth),(i19,tsst),(i20,tspk),(i21,tsdw),(i22,tsup),(i23,tsst),(i24,tsth),(i25,tsst),(i26,tsdw),(i27,tspk)},構(gòu)建趨勢(shì)樹(shù)如圖1所示,其中k=27,h=4,根節(jié)點(diǎn)為tsup。定義8聚類類別。給定tree(T),根據(jù)tree(T)根節(jié)點(diǎn)表示的不同趨勢(shì)類型,共五種聚類類別,分別記為Cup,Cdw,Cst,Cpk,Cth。聚類類別Ci∈{Cup,Cdw,Cst,Cpk,Cth}與SLh(T)表示的趨勢(shì)類型對(duì)應(yīng),即Cup,Cdw,Cst,Cpk,Cth分別對(duì)應(yīng)tsup,tsdw,tsst,tspk,tsth。Ci為聚集到該類的時(shí)間序列集合,該集合內(nèi)的時(shí)間序列趨勢(shì)樹(shù)根節(jié)點(diǎn)表示的趨勢(shì)類型相同,不同聚類類別內(nèi)的時(shí)間序列其趨勢(shì)樹(shù)根節(jié)點(diǎn)表示的趨勢(shì)類型不同,其中Ci∈{Cup,Cdw,Cst,Cpk,Cth}(1≤i≤5)。4.2基于趨勢(shì)的時(shí)間序列聚類算法基于趨勢(shì)的時(shí)間序列聚類算法輸入:時(shí)間序列集合D={T1,T2,…,Tm},其中m是序列集合的尺寸,Ti={(t1,X1,P1),(t2,X2,P2),…,(tn,Xn,Pn)}(1≤i≤m);序列區(qū)間分割子程序Div_Sl;區(qū)間趨勢(shì)判斷和趨勢(shì)符號(hào)序列生成子程序Td_Sl;趨勢(shì)樹(shù)生成子程序tree_Td。輸出:聚類類別集合{Cup,Cdw,Cst,Cpk,Cth}。基于趨勢(shì)的時(shí)間序列聚類算法的時(shí)間復(fù)雜度分析如下(首先討論不確定時(shí)間序列的情況):a)步驟2計(jì)算時(shí)間序列的期望序列,需要遍歷時(shí)間序列的所有觀察值,步驟2的時(shí)間復(fù)雜度為O(ns),s為時(shí)間序列觀察點(diǎn)的觀察值個(gè)數(shù)。b)步驟3對(duì)期望序列進(jìn)行序列區(qū)間劃分和區(qū)間趨勢(shì)判斷,并生成趨勢(shì)符號(hào)序列,該步驟需要遍歷期望序列的每個(gè)觀察點(diǎn),步驟3的時(shí)間復(fù)雜度為O(n)。c)步驟4對(duì)趨勢(shì)符號(hào)序列進(jìn)行迭代趨勢(shì)判斷,并生成趨勢(shì)樹(shù),步驟4的時(shí)間復(fù)雜度為O(3+32+…+3h-1)=O(0.5×3h),其中h為趨勢(shì)樹(shù)的高度。d)步驟5~8根據(jù)趨勢(shì)樹(shù)根節(jié)點(diǎn)表示的趨勢(shì)類型進(jìn)行聚類。該步驟的時(shí)間復(fù)雜度為O(1)。e)步驟1需要遍歷數(shù)據(jù)庫(kù)中的m條時(shí)間序列并進(jìn)行步驟2~8的計(jì)算。由于k<0.5×3h<n,其中k為趨勢(shì)符號(hào)序列SL(T)的長(zhǎng)度,n為時(shí)間序列T的長(zhǎng)度,則步驟2~8的時(shí)間復(fù)雜度為O(ns),該算法的時(shí)間復(fù)雜度為O(nms);同理對(duì)確定的時(shí)間序列集合D={T1,T2,…,Tm}進(jìn)行基于趨勢(shì)聚類的時(shí)間復(fù)雜度為O(nm),其中m為D的尺寸。5實(shí)驗(yàn)5.1實(shí)驗(yàn)環(huán)境本次實(shí)驗(yàn)的環(huán)境為:Windows732位操作系統(tǒng);英特爾酷睿i3-370處理器;NVIDIAGeforceGT330M顯卡。5.2不確定時(shí)間序列1)不確定時(shí)間序列數(shù)據(jù)實(shí)驗(yàn)數(shù)據(jù)是來(lái)自鋼廠軋鋼過(guò)程中一卷鋼板的凸度值變化情況。在實(shí)際鋼廠軋鋼過(guò)程中,將每一卷鋼板作為一個(gè)周期,每一卷的檢測(cè)數(shù)據(jù)是按時(shí)間順序變化的,每一時(shí)隙的變化是不確定的,形成一個(gè)不確定的時(shí)間序列。假定檢測(cè)過(guò)來(lái)的原始數(shù)據(jù)與數(shù)據(jù)庫(kù)中時(shí)間范圍是相同周期的,每一卷檢測(cè)值是一個(gè)時(shí)間序列,每一條元組都是一個(gè)2-tuple〈ti,vi〉,循環(huán)讀取這組檢測(cè)數(shù)據(jù)中的每一個(gè)二元組,與數(shù)據(jù)庫(kù)中對(duì)應(yīng)時(shí)刻的值進(jìn)行比較,更新數(shù)據(jù)庫(kù)中的值,統(tǒng)計(jì)出每一時(shí)刻所出現(xiàn)的觀察值的頻率。本文主要通過(guò)統(tǒng)計(jì)每一組值來(lái)找到這樣的經(jīng)驗(yàn)值。具體做法是:將原始檢測(cè)數(shù)據(jù)通過(guò)統(tǒng)計(jì)計(jì)算,得到每個(gè)時(shí)刻的樣本可能出現(xiàn)值和可能值的概率,實(shí)際每個(gè)周期大概是150個(gè)時(shí)間點(diǎn),這樣形成了一條不確定的時(shí)間序列數(shù)據(jù)。最后得到1000條不確定時(shí)間序列,每條時(shí)間序列的時(shí)間點(diǎn)都是150。2)確定時(shí)間序列數(shù)據(jù)通過(guò)統(tǒng)計(jì)鋼板凹凸值變化得到不確定時(shí)間序列后,將該序列的期望序列作為實(shí)驗(yàn)中的確定時(shí)間序列數(shù)據(jù),則最后得到1000條確定時(shí)間序列,每條時(shí)間序列的時(shí)間點(diǎn)都是150。5.3測(cè)定一階連接性指數(shù)法對(duì)2000條時(shí)間序列(1000條確定時(shí)間序列和1000條不確定時(shí)間序列)分別計(jì)算五種趨勢(shì)符號(hào)的一階連接性指數(shù),然后對(duì)每一條時(shí)間序列分別計(jì)算與其余序列趨勢(shì)符號(hào)的塔尼莫特系數(shù)。實(shí)驗(yàn)結(jié)果表明在2000條時(shí)間序列集合中,沒(méi)有兩序列的塔尼莫特系數(shù)等于1,即2000條時(shí)間序列中,沒(méi)有兩條時(shí)間序列的趨勢(shì)符號(hào)的一階連接性指數(shù)完全相等,所以可以使用五種趨勢(shì)符號(hào)的一階連接性指數(shù)唯一地表示一條時(shí)間序列。5.4查詢結(jié)果的相關(guān)性分析本文通過(guò)查全率和查準(zhǔn)率兩種參數(shù)來(lái)進(jìn)行相似性度量的結(jié)果分析。查全率(召回率)是衡量從不確定性時(shí)間序列數(shù)據(jù)庫(kù)中查詢出與給定的查詢序列相似成功度的一項(xiàng)指標(biāo),即查詢出的相關(guān)序列與數(shù)據(jù)庫(kù)中全部不確定時(shí)間序列的百分比。查準(zhǔn)率(精度)是衡量查詢出的相似性序列的準(zhǔn)確度的一項(xiàng)指標(biāo),即查詢出的相關(guān)序列中真正滿足相似的序列與全部查詢出的相關(guān)序列的百分比。5.4.1對(duì)于相似性匹配結(jié)果任意給定一個(gè)查詢序列Q,對(duì)1000條確定的期望時(shí)間序列分別基于歐氏距離(ED)、DTW、序列趨勢(shì)(TD)三種度量方式進(jìn)行相似性匹配。相似性匹配結(jié)果如表6所示。使用基于序列趨勢(shì)的度量方式,查全率最高,但是查準(zhǔn)率與基于歐氏距離的相似性度量方式接近,并低于基于DTW的相似性度量方式。三種度量方式的匹配效率如圖2所示,基于序列趨勢(shì)的度量方式匹配效率介于其余兩者之間,并且基于DTW的度量方式匹配效率最低。以上數(shù)據(jù)表明,對(duì)于確定時(shí)間序列,基于趨勢(shì)的相似性度量方式是有效的。5.4.