動(dòng)態(tài)時(shí)間彎曲算法在K線相似度計(jì)算中的應(yīng)用

動(dòng)態(tài)時(shí)間彎曲算法在K線相似度計(jì)算中的應(yīng)用序言在證券交易數(shù)據(jù)中，股票K線圖無(wú)疑是一種非常重要的數(shù)據(jù)．它反映了股票在過(guò)去歷史中基于開(kāi)盤價(jià)與收盤價(jià)的交易價(jià)格的變動(dòng)．古有言，以史為鑒，歷史往往存在相似性，對(duì)一支股過(guò)去歷史波動(dòng)的研究，往往可以對(duì)其自身，以及其他股票的未來(lái)價(jià)格變動(dòng)作出一些合理預(yù)測(cè)．而股票價(jià)格究其根本是一種時(shí)間序列．對(duì)于時(shí)間序列，是一種以時(shí)間為軸，在一些特別規(guī)定的時(shí)間點(diǎn)上通過(guò)采樣得到的一系列按照時(shí)間順序排列的，從被觀測(cè)對(duì)象獲取到的觀測(cè)值．通過(guò)對(duì)時(shí)間序列的研究，找到兩條時(shí)間序列相似程度的的度量方法就被稱為時(shí)間序列相似性度量，這是時(shí)間序列聚類分析中一個(gè)不可缺少的步驟，同時(shí)也是分類、聚類、規(guī)律發(fā)現(xiàn)、模式識(shí)別等工作的子進(jìn)程．對(duì)于研究股票k線圖相似性，是為了對(duì)未來(lái)進(jìn)行合理預(yù)測(cè)，因此度量方法應(yīng)該考慮其性能對(duì)于后期時(shí)間序列數(shù)據(jù)挖掘的效果的的直接影響程度．時(shí)間序列的相似程度是由度量距離的大小所決定的．而相似性度量方式的特性又決定了相似性度量的效果．在時(shí)間序列相似性度量中，我們最常用的方法就是動(dòng)態(tài)時(shí)間彎曲(DynamicTimeWarping,DTW)?這是由Berndt于1994年提出將其應(yīng)用在時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域中，以此來(lái)發(fā)現(xiàn)時(shí)間序列中的模式.而這剛好適用于股票k線圖的相似程度的研究.這是由于動(dòng)態(tài)時(shí)間彎曲不僅可以消除歐式距離“點(diǎn)對(duì)點(diǎn)”的匹配缺陷，通過(guò)彎曲時(shí)間來(lái)達(dá)到時(shí)間序列數(shù)據(jù)點(diǎn)“一對(duì)多”的匹配，從而實(shí)現(xiàn)不等長(zhǎng)時(shí)間序列的度量，還對(duì)時(shí)間序列的偏移，振幅變化等情況具有較強(qiáng)的魯棒性(魯棒是Robust的音譯，也就是健壯和強(qiáng)壯的意思.魯棒性指的是遭遇外來(lái)干擾，性質(zhì)保持不變的能力?)?這對(duì)于不同股票的k線圖在不同的時(shí)間跨度而可能形成相同價(jià)格形態(tài)有著重要意義.一、DTW算法原理動(dòng)態(tài)時(shí)間彎曲是一種在語(yǔ)音識(shí)別領(lǐng)域得到首次應(yīng)用的，準(zhǔn)確性高并且魯棒性強(qiáng)的時(shí)間序列相似性度量方法.它區(qū)別于傳統(tǒng)的歐幾里的距離，其不同在于動(dòng)態(tài)時(shí)間彎曲可以通過(guò)彎曲時(shí)間序列的時(shí)間區(qū)域從而對(duì)時(shí)間序列的數(shù)據(jù)點(diǎn)進(jìn)行匹配，這樣我們不單單能夠得到更好的形態(tài)度量的效果，更重要的是我們能夠度量?jī)蓷l不等長(zhǎng)的時(shí)間序列.對(duì)于股票K線圖的相似性，我們尋求的是價(jià)格形態(tài)的相似性.例如威廉?歐奈爾提到的一種最普遍的價(jià)格形態(tài)“帶柄茶杯形態(tài)”,當(dāng)我們找到與此形態(tài)相似的股票時(shí)就要做出準(zhǔn)備，這可能是一支帶動(dòng)市場(chǎng)發(fā)展的“超級(jí)牛股”一如當(dāng)年的微軟與蘋果.要想實(shí)現(xiàn)股票K線圖的這種相似度匹配，依靠歐式距離在度量中講時(shí)間序列進(jìn)行“一對(duì)一“的數(shù)據(jù)匹配是不夠的，盡管它具有高效性，但是它并未能準(zhǔn)確的使波峰、波谷匹配起來(lái)?而動(dòng)態(tài)時(shí)間彎曲則能夠通過(guò)彎曲時(shí)間軸來(lái)實(shí)現(xiàn)“一對(duì)多”的數(shù)據(jù)匹配?通過(guò)這樣，動(dòng)態(tài)時(shí)間彎曲就能成功將兩條不同的股票 K線圖的波峰和波谷匹配起來(lái)，從而有助于我們度量?jī)r(jià)格形態(tài)的相似程度，體現(xiàn)了動(dòng)態(tài)時(shí)間彎曲在形態(tài)度量上的優(yōu)勢(shì).1.1動(dòng)態(tài)時(shí)間彎曲距離【1】

在介紹動(dòng)態(tài)時(shí)間彎曲算法之前，先簡(jiǎn)單的介紹一下動(dòng)態(tài)時(shí)間彎曲距離的定義.定義1給定兩條時(shí)間序列x={x，x,…，x}和y={y，y,…，y}，計(jì)算它們之間的累TOC\o"1-5"\h\z1 2 n "1"2 n積距離D(i-1,j)D(i,j)=d(x冷j)+min{D(i,j-1)1' D(i-1,j- 1)其中d(x.,y.)=IIx.-y.11 (1)ij i j CD為點(diǎn)x.到y(tǒng)j之間的距離，其中i=(12…,n),j=(1,2,…,m),當(dāng)=2時(shí)為歐式距離.得到的累積最小距離就是動(dòng)態(tài)彎曲距離，我們記為 D()在這里我們需要特別注意一點(diǎn)，動(dòng)態(tài)彎曲距離是不符合三角不等式的命題1D()不滿足三角不等式warp證明我們可以通過(guò)一個(gè)反例來(lái)證明這個(gè)論題，設(shè)x?=?0?y?=?1，2? 和？=?1,2,2?z,那我們有：Dwarp(x?,z?)=5>D(x?,y?)+D(y?,z?)warp warp=3+0=3如此命題得證.1.2動(dòng)態(tài)時(shí)間彎曲距離的計(jì)算計(jì)算它的最終累積距離其實(shí)可以認(rèn)為是在距離矩陣 D中尋找一條最優(yōu)的彎曲路徑P，從而使得累積距離達(dá)到最小，其中距離矩陣可以表示為以任意兩點(diǎn)之間的距離來(lái)確立 的距離矩陣D??(???????)???(??????)D=(?? \ 八? ??\ 75D=(???)??(????,??)???(??????),通過(guò)尋找彎曲路徑P={p1,p2,…pK}(max(n,m)<K<n+m+1)來(lái)使得S和Q的累best 丄丄 丄 計(jì)距離的值達(dá)到最小■其中p表示的是彎曲路徑元素在距離矩陣中的位置，k即p=(i,j)表示s.與h之間的匹配關(guān)系.則由此可以知道d(p)=d(i,j)k k i ] k?通過(guò)觀察距離矩陣，我們可以看出一般存在著多條彎曲路徑，有效的彎曲路k徑P必須符合三個(gè)要求：(1)邊界性：p=(1,1),p=(n,m)■即路線必須從距離矩陣的第一行第1 K—列出發(fā)到達(dá)矩陣的第n行第n列(2)單調(diào)性：給定pk=(i,j)和pk+1=(x,y)，則x>i,y>j.(3)連續(xù)性：給定pk=(i,j)和pk1=(x,y),x<i+1,y<j+1■單調(diào)

性和連續(xù)性的存在保證了彎曲路徑中某個(gè)點(diǎn)的下一個(gè)點(diǎn)在當(dāng)前點(diǎn)的上方、右上方、右方.1.3范例給定兩條時(shí)間序列x={2,5,5,4,6,7} ,y={2,4,6,5,7,7},如下圖，計(jì)算它們的動(dòng)態(tài)時(shí)間彎曲距離:77我們令d（x.訂.）=lx-yl，由此來(lái)構(gòu)造一個(gè)距離矩陣，在這里為了方便起見(jiàn)把它）的值.在股票）的值.在股票做成了一個(gè)網(wǎng)格形態(tài)，每一格中的數(shù)字代表距離矩陣相應(yīng)位置的 d（xi,y由此我們便可以根據(jù)動(dòng)態(tài)規(guī)劃（AP）找到一條最優(yōu)路徑從而得到DOwarp的相似性52231052331丿03001125112/012/0*—023033245：、基于動(dòng)態(tài)時(shí)間彎曲的股票k線圖相似性計(jì)算在股票K線圖的相似性計(jì)算中，我們通常是將股票進(jìn)行兩兩比較.在這里我們將選取其中一支具有特別價(jià)格形態(tài)的股票作為參考股票，另一支與它進(jìn)行比較的股票就叫測(cè)量股票.2.1將股票數(shù)據(jù)進(jìn)行向量化和標(biāo)準(zhǔn)化【6】為了便于后續(xù)計(jì)算，我們首先要將采集到股票數(shù)據(jù)進(jìn)行預(yù)先處理我們將參考股票具有研究意義的30天的價(jià)格變動(dòng)以向量方式記錄，記為x?（Xi，X2,…,J）同樣的我們將測(cè)量股票要測(cè)量的30天價(jià)格變動(dòng)也用向量方式記錄記為天價(jià)格變動(dòng)也用向量方式記錄，記為y?=（y^y2,…y）其中n為選取的K線圖某時(shí)刻的時(shí)序標(biāo)號(hào):n=1為起點(diǎn)時(shí)刻，在這里我們選取的是30天，所以n=30為終點(diǎn)時(shí)刻.x為第m時(shí)刻的K線圖的收盤價(jià)格.m由于股票價(jià)格差別巨大，統(tǒng)一的闕值不好判斷，所以要進(jìn)行規(guī)范處理，把所有股票的價(jià)格變動(dòng)都轉(zhuǎn)化為0?1之間，具體方法如下：xi-mm（x?）Z= imax（x?）-min?（x?）2.2通過(guò)構(gòu)建股票價(jià)格的距離矩陣尋找最優(yōu)路徑采用動(dòng)態(tài)時(shí)間彎曲算法我們首先要根據(jù)參考股票和測(cè)試股票的收盤價(jià)格來(lái)構(gòu)

建一個(gè)距離矩陣D 我們可以用如下辦法來(lái)快速構(gòu)建距離矩陣從而找到最優(yōu)路nxm徑.若把測(cè)試模板的各個(gè)時(shí)刻n=1~N在一個(gè)二維直角坐標(biāo)系中的橫軸上標(biāo)出，把參考股票的各時(shí)刻m=1~M在縱軸上標(biāo)出，通過(guò)這些表示時(shí)刻的整數(shù)坐標(biāo)畫出一些縱橫線即可形成一個(gè)網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每一個(gè)交叉點(diǎn)（n,m）表示測(cè)試股票與參考股票中某一時(shí)刻的交匯點(diǎn).用動(dòng)態(tài)規(guī)劃（DP）算法來(lái)計(jì)算并尋找一條通過(guò)此網(wǎng)絡(luò)中若干格點(diǎn)的路徑，路徑通過(guò)的格點(diǎn)即為測(cè)試和參考股票中進(jìn)行計(jì)算的時(shí)刻.具體如下圖：d(x30』1)d（x30』3。）??????d(x3,y1)嘰』1）d('y1)d(\y2)d(x1-y3)-'?…(1(x1，y3。)路徑不是隨意選擇的，首先任何一種股票的價(jià)格漲幅都有可能變化，但是其各時(shí)刻的先后次序不可能改變，因此所選的路徑必定是從左下角出發(fā)，在右上角結(jié)束為了描述這條路徑，假設(shè)路徑通過(guò)的所有格點(diǎn)依次為（「，m】）,……,（nimj）， ，（nN，mM），其中（n]，m]）=（1,1）,（nN，叫）=（N,M）■為了使路徑不至于過(guò)傾斜，可以約束斜率在0.5~2的范圍內(nèi)，如果路徑已經(jīng)通過(guò)了格點(diǎn)（n,m），那么下一個(gè)通過(guò)的格點(diǎn)（n,m）只可能是下列三種情況之

@（n,m）=（n+1,m+1）{D（n-l，m），D（n-l，m-l），D（n，m-1）}3（n,m）=（n,m+1）用r表示上述三個(gè)約束條件.求最佳路徑的問(wèn)題可以歸結(jié)為滿足約束條件r時(shí),求最佳路徑，使得沿路徑的積累距離達(dá)到最小值即D（）warp2.3搜索該路徑的方法搜索從（N,M）點(diǎn)出發(fā)，可以展開(kāi)若干條滿足r的路徑，假設(shè)可計(jì)算每條路徑達(dá)到（n,m）點(diǎn)時(shí)的總的積累距離，具有最小累積距離者即為最佳路徑?易于證明，限定范圍的任一格點(diǎn)（n,m）只可能有一條搜索路徑通過(guò)?對(duì)于（n,m），其可達(dá)到該格點(diǎn)的前一個(gè)格點(diǎn)只可能是（n-1,m）、（n-1，m-1）和（n,m-1），那么（n,m）一定選擇這3個(gè)距離之路徑延伸而通過(guò)（n,m），這時(shí)此路徑的積累距離為：D（n- 1,m）D[（n,m）]=d[x,y]+min{???D（n-1,m-1）D（n,m-1）這樣可以從（n,m）=（30,30）出發(fā)搜索（n,m），對(duì)每一個(gè)（n,m）都存儲(chǔ)相應(yīng)的距離，這個(gè)距離是當(dāng)前格點(diǎn)的匹配距離與前一個(gè)累計(jì)距離最小的格點(diǎn)（按照設(shè)定的斜率在三個(gè)格點(diǎn)中進(jìn)行比較）?搜索到（1,1）時(shí)，只保留一條最佳路徑?如果有必要的話，通過(guò)逐點(diǎn)向前尋找就可以求得整條路徑.DTW算法可以直接按上面描述來(lái)實(shí)現(xiàn)，即分配兩個(gè)NXM的矩陣，分別為積累距離矩陣D和時(shí)刻匹配距離矩陣d，其中時(shí)刻匹配距離矩陣d（i,j）的值為測(cè)試股票的第i時(shí)刻與參考股票的第j時(shí)刻間的距離.D（N,M）即為最佳匹配路徑所對(duì)應(yīng)的匹配距離.2?4范例例如我們選取兩支股票，一支是中成股份（000151）作為參考股份?x,另一支是翼凱股份（002691）作為測(cè)試股份?y，為了計(jì)算方便我們只取五天的數(shù)據(jù)第一步：提取數(shù)據(jù)X=(10.53,11.58,12.74,13.77,13.19)Y=(27.99,29.4,32.3,32.8,32.4)第二步：標(biāo)準(zhǔn)化經(jīng)過(guò)Z經(jīng)過(guò)Zi=xi-min(x?)后,max(x?)-min?(x?)0.820)0.917)X=(0,0.324,0.682,1,0.820)0.917)Y=(0,0.293,0.896,1,第三步：構(gòu)建距離矩陣并尋找最優(yōu)路徑在這里我們讓d（x,y）=|x-y|]j0.3240.8200.5270.0760.3240.8200.5270.0760.1800.097/10.7070.104痢-00.0830.6820.389T0.214/.0.3180.2350.593 打0.031 0.572 0.67600.2930.89610.917最終我們得到一個(gè)最優(yōu)累積距離Dwarp（）=0.046三、DTW在K線圖相似度計(jì)算機(jī)的實(shí)際應(yīng)用【2】在中國(guó)A股總共有3470支甚至還有中小企業(yè)板，乃至創(chuàng)業(yè)板的股票，再涉及到各自的歷史數(shù)據(jù)，這是一個(gè)非常龐大的數(shù)據(jù)庫(kù).若要在這個(gè)數(shù)據(jù)可當(dāng)中找尋于某一支股票相似的其他股票，將是一個(gè)計(jì)算量非常大的工作.顯然不可能人工手算，而是要借助計(jì)算機(jī)的索引技術(shù).但是如此龐大的數(shù)據(jù)對(duì)索引技術(shù)的準(zhǔn)確性和高效性有著非常大的挑戰(zhàn).3.1索引技術(shù)索引技術(shù)是一種快速的文件訪問(wèn)技術(shù)，舉個(gè)例子，好比我們查字典，會(huì)根據(jù)偏旁部首在索引表中找到這個(gè)字在第幾頁(yè)一樣，索引技術(shù)就是根據(jù)事先記錄好的能夠代表屬性的取值將它與物理地址關(guān)聯(lián)，進(jìn)而在數(shù)據(jù)庫(kù)中搜索.之前我們著重提到過(guò)一個(gè)命題一一D（）不符合三角不等式?這個(gè)事實(shí)對(duì)于warp我們可以用于索引的方法有著重要的意義：任何隱含或明確地符合三角不等式的索引技術(shù)都不能避免產(chǎn)生錯(cuò)誤的排除.這是一個(gè)非常嚴(yán)格的要求：所有的空間訪問(wèn)方法，以及所有使用距離、度量、有利位置樹(shù)的方法都不能避免錯(cuò)誤的排除.唯一保證不會(huì)被錯(cuò)誤排除的方法是順序掃描，，對(duì)于像股票這種大量長(zhǎng)序列集合來(lái)說(shuō)這將是計(jì)算量巨大的.為了解決這個(gè)問(wèn)題，人們提出了一種方法，用來(lái)避免一小部分的錯(cuò)誤排除的同時(shí)能夠?qū)崿F(xiàn)的索引的加速.也就是說(shuō)，人們的目標(biāo)是提供快速的索引技術(shù)，同時(shí)盡可能地避免錯(cuò)誤的排除.在這里人們引用了兩種方法.3.2基于FastMap的訪問(wèn)方法我引用的第一種技術(shù)是基于一種名為FastMap的方法【4】它的工作原理如下：給定N個(gè)對(duì)象和一個(gè)距離函數(shù)，它將對(duì)象映射到k維空間中的N個(gè)點(diǎn)，以便保持原始距離，參數(shù)k可以由用戶給出，或者人們可以在應(yīng)用中調(diào)整以獲得更好的系統(tǒng)性能?關(guān)鍵在于是假設(shè)對(duì)象確實(shí)能夠表示成n維空間中的點(diǎn)，并且能夠僅使用距離函數(shù)將這些點(diǎn)投影到相互正交k維空間中（k《n），從而實(shí)現(xiàn)降維的目的.如一個(gè)三維向量（x,y,z）可以經(jīng)過(guò)函數(shù)映射到二維空間（x,y）換用我們?nèi)缃裾谘芯康墓善眮?lái)講，就是我們要將我們包含 30天收盤價(jià)格的向量，通過(guò)一個(gè)距離函數(shù)映射到一個(gè)二維空間?從而減少數(shù)據(jù)的處理.在將對(duì)象映射到k個(gè)點(diǎn)之后，人們可以使用任何空間訪問(wèn)方法來(lái)組織它們并搜索范圍查詢.FastMap在對(duì)象的數(shù)目N（即序列）上是線性的?而且，將查詢序列映射到第k個(gè)點(diǎn)需要O（k）時(shí)間，也就是說(shuō)，相對(duì)于數(shù)據(jù)庫(kù)大小N，時(shí)間是恒定的.與其他方法一樣（參見(jiàn)命題1），如果不遵守三角不等式，F(xiàn)astMap可能會(huì)引入錯(cuò)誤的排除?我們觀察到，如果我們使用原始距離的平方根即歐幾里得距離（很明顯它符合三角不等式），我們可以避免更多的錯(cuò)誤排除?因此，我們?cè)谶x擇一個(gè)距離函數(shù)時(shí)候使用的就是歐幾里得距離.

algorithnfrzm^s^sQarcb.W1w0i/*nasp^nse*//*filtering +/GIysa譏foreacbsecjuenGO玄LnEh七 、ifK巧〔門訕中日哥4《#).thzaddit&/?;/*pGSt^prOCa&filTL.gS-tep*/Forea^hiinR*if(PJ}>*)*TlisB ifr^tnfiiReporr/?;導(dǎo)midlj^xlthiii圖來(lái)自：【2】算法1描述了如何使用FastMap處理范圍查詢■如果將FastMap應(yīng)用于平方根距離，則搜索范圍也應(yīng)該平方根■注意F(s?)表示序列的坐標(biāo)■在過(guò)濾步驟中，根據(jù)歐幾里得距離而不是時(shí)間彎曲距離來(lái)比較兩個(gè)序列，這是由于歐幾里得計(jì)算的簡(jiǎn)單性和快捷性，這相當(dāng)于一步粗篩選?在這一步中不相關(guān)的序列被排除在外■—些不符合條件的序列可能包含在內(nèi)，但在后處理步驟中將刪除這些序列.由于兩個(gè)原因，算法1比單純的DTW方法更快■首先，它掃描較少的序列■其次，過(guò)濾步驟也更快，因?yàn)閗比序列長(zhǎng)度小得多(通常是一些固定常數(shù)，比如6)■過(guò)濾可能會(huì)刪除一些合格的序列，導(dǎo)致錯(cuò)誤排除，因?yàn)槲覀儾荒鼙ＷC在k-d空間中的歐幾里得距離越低越好.即使我們使用時(shí)間彎曲距離的平方根，情況也是如此，但在實(shí)踐中錯(cuò)誤排除的可能性非常低，我們將在后面看到.3.3下邊界技術(shù)對(duì)于兩個(gè)給定的序列?=xVX],…,x>和y?=vy],…,y>，讓max(?x)和max(y?)表示x?和y?中的最大值.min(x?)和min(y?)的定義相似，但是最小值■—對(duì)vmax(x?),min(x?)>定義了序列x?可以控制的范圍.warp不失一般性，我們假設(shè)max(x?)>max(y?)所提出的方法受以下觀察的啟發(fā):觀察1|max(x?)-max(y?)|<D(x?;?y).warp檢查其有效性相當(dāng)簡(jiǎn)單■由于max(x?)應(yīng)該至少匹配y?的一個(gè)元素，比如y.,并且我們假設(shè)max(x?)>max(y?),|max(?x)-max(y?)|< |max(x?)-y|<D(x?;?y)：i warp這個(gè)觀察的結(jié)果是最大值的絕對(duì)差值可以作為一個(gè)距離來(lái)限制時(shí)間彎曲距離■雖然這是真的，但是，它可能不是很有用，因?yàn)樗赡艿陀跁r(shí)間彎曲距離太多■因此，我們的目標(biāo)是找到一個(gè)更緊密的下界.我們考慮兩個(gè)序列的范圍的可能排列進(jìn)行比較.觀察2給定兩個(gè)范圍觀察2給定兩個(gè)范圍Rx?=vmax(?x),min(?x)>和Ry?=vmax(y?)，min(y?)>(范圍的可能排列(見(jiàn)下圖))1.overlap:Rx?1.overlap:Rx?和Ry?重疊 (min(x?)Wmax(y?);min(x?)$min(y?)).2.encloses:Rx?包含Ry? (min (?x)vmin(?y))?3.disjoint:Rx?和Ry?是不相交的(min (x?)>max(y?)【2】可以保證范圍查詢和最近相鄰D距離(維度k上Ry■RaKyRy(dIdbjoinc圖來(lái)自:我們有三種可能的排列iva1.鼻|t|——fimrlyjVi—m?B(f}|n/rJHji—■ 1|jT]— 1譏一 ■【心|ijfhFWKJ"1昭1I舟亠鮎卄7i|rij冊(cè)圖來(lái)自：【2】值得注意的是，當(dāng)通過(guò)掃描一次將序列輸入到數(shù)據(jù)庫(kù)中時(shí)，可以計(jì)算序列的最小值和最大值，并且可以將序列存儲(chǔ)以供將來(lái)使用?而且，通過(guò)簡(jiǎn)單的比較，可以在恒定的時(shí)間內(nèi)確定兩個(gè)序列的范圍的排列?最后，D的定義只需要對(duì)每個(gè)序lb列進(jìn)行一次掃描，因此我們可以計(jì)算序列長(zhǎng)度中線性時(shí)間內(nèi)兩個(gè)序列之間的D距l(xiāng)b離?這會(huì)令速效率有很大的改善，除非D太低估D?lb warp定理1對(duì)于任何兩個(gè)序列X?=VX],??，x m>和y?=<y n>,y nDib(x?,?y)WD(x?,?y)lb warp證明：見(jiàn)附錄A.作為定理1的直接結(jié)果，我們得到以下推論.>，如n推論1(沒(méi)有誤診率)對(duì)于任何兩個(gè)序列X?=<X],??,X >和>，如nTOC\o"1-5"\h\z& & y果D(x?;?y)W，貝UD(x?;?y)W?warp lb實(shí)際距離D與下邊界距離d是一種限制條件,2 lb查詢不會(huì)被錯(cuò)誤排除[8]?在過(guò)濾步驟中，快速濾除不相關(guān)序列，因?yàn)榭梢钥焖儆?jì)算lb的線性時(shí)間，通常為kW10)?一些不合格的序列可能包含在這個(gè)步驟的結(jié)果中,因?yàn)镈小于我們的動(dòng)態(tài)時(shí)間彎曲距離D?但是，這些不合格序列在后處理步驟lb warp中被刪除.具體算法如下：算法2蠱lgqrlthiq1命pe「一BquacH訥呂蔬a{}；/?riltaringstep*/Civenry,/o-re^cbsequence>inthedatabase、fif（P?i J?thenaddito{?;/*posl^precessing3t?p*/F&reicLiinR,if（jP.“就譏打IA，）■th餌removeifrom商；fl*portH;endalgorithm圖來(lái)自：【2】3.3結(jié)合兩種技術(shù)【5】假設(shè)有一個(gè)股票數(shù)據(jù)庫(kù)包含許多任意長(zhǎng)度的時(shí)間序列并且我們想要找出與某個(gè)查詢序列相似的所有序列，即時(shí)間彎曲距離單位內(nèi)的所有序列.這種類型的查詢是有效范圍查詢.處理這種查詢的直接方式是掃描所有序列并為每個(gè)掃描序列計(jì)算D （）,以選warp擇符合條件的那些序列.雖然非常簡(jiǎn)單，但速度可能很慢，因?yàn)樗x取數(shù)據(jù)庫(kù)中的每一個(gè)序列（因此速度很慢），并且它計(jì)算每個(gè)股票數(shù)據(jù)庫(kù)序列的時(shí)間彎曲距離.這個(gè)問(wèn)題的獨(dú)特之處在于，不僅I/O成本（第一種情況）很高，而且還有計(jì)算成本（第二種情況）.因此，我們所需要的技術(shù)應(yīng)該解決這兩個(gè)問(wèn)題?為了解決這些問(wèn)題，人們采用了之前提到的兩種技術(shù).1?使用FastMap構(gòu)建索引結(jié)構(gòu)以加快查詢處理速度.這種技術(shù)可能會(huì)導(dǎo)致一些錯(cuò)誤的排除.2?使用低于時(shí)間彎曲距離的下邊界距離函數(shù). 這種方法保證不會(huì)有錯(cuò)誤的排除.3?使用這兩種技術(shù)的組合.由于這兩種技術(shù)彼此獨(dú)立，因此可以采用流水線方式進(jìn)行組合.仔細(xì)考慮前面兩部分提出的兩種技術(shù)可以帶來(lái)更高效的算法.在算法1中，我們僅使用時(shí)間彎曲距離篩選過(guò)濾的序列.但是，我們可以在計(jì)算時(shí)間彎曲距離之前使用下邊界距離.如果序列確實(shí)是合格的序列，這就變成了額外的成本，但是如果不合格就可以節(jié)省大量的計(jì)算成本. 這樣我們就有了一個(gè)靈活的多階段查詢處理系統(tǒng)，如圖3所示，其中FastMap和D分別作為主要和次要過(guò)濾器.lb圖來(lái)自：【2】它由三個(gè)階段組成，它們以流水線方式連接.第一階段僅使用FastMap索引排除不相關(guān)的序列.在此階段進(jìn)行過(guò)濾可降低I/O成本和CPU成本.那些通過(guò)第一過(guò)濾階段的序列在下一階段與D()的查詢序列進(jìn)行比較.最后，后處理階段lb只選擇那些真正符合條件的序列.四、計(jì)算機(jī)程序選取一支股票，例如新鋼股份作為參考模板，將其某三十天的收盤價(jià)格以向量方式輸入.然后另選取三十支股票作為股票池S，股票池中的每一支股票S作為測(cè)試模板i與參考模板進(jìn)行配對(duì)，以期待獲得兩條如下圖般相似的股票.將所有股票數(shù)據(jù)進(jìn)行單位化xi-min?(xi-min?(x)Z.= imax(x)-min?(x)例如4用D（歐幾里得距離）【3】進(jìn)行第一次篩選2) 2J( )D=x1-y1+?+(xn-yn)A25用D進(jìn)行第二次篩選lb般票池r >11取那試股孕別輸人藝再隕空W 1 戢擁處這T邀行口“"曾址/k進(jìn)行九皓選二-一一=—丿 輸出R中所有的序列s的D (X,s)i warp i6值輔巴5i和凡卄具體程序見(jiàn)附錄B5實(shí)驗(yàn)我們?nèi)匀贿x取以中成股份(000151)為參考股票，以翼凱股份(002691)作為測(cè)試股份.第一步：讀取數(shù)據(jù)X=(7.71,7.73,7.76,7.81,7.85,7.61,7.36,7.43,7.48,7.59,7.46,7.56,7.62,7.66,7.69,7.7,7.73,7.66,7.71,7.77,7.67,7.79,7.91,8.7,9.57,10.53,11.58,12.74,13.1,12.45)Y=(23?23,23?26,23?26,23?29,23?38,23?56,23?22,23?12,23?05,23?06,23,22.95,22.96,22.93,24.12,24.45,23.3,23.27,23.2,23.28,23.14,22.87,23.89,25.4,26.46,27.99,29.4,32.3,32.8,32.4）第二步：標(biāo)準(zhǔn)化X=(0.061，0.064，0.070，0.078，0.085，0.044，0.000，0.012，0.021，0.0400.017，0.035，0.045，0.052，0.057 ，0.059，0.064，0.0520.061，0.071，0.054，0.0750.096，0.233，0.385，0.552，0.735，0.937，1.000，0.887）Y=(0.036，0.03