第三章時間序列挖掘相似性

1、時間序列挖掘相似性山西財經(jīng)大學(xué)信息管理學(xué)院常新功山西財經(jīng)大學(xué)信息管理學(xué)院常新功第三章目 錄 時間序列相似性定義 時間序列相似性應(yīng)用場景 時間序列常見距離定義 時間序列相似性分類時間序列相似性定義 反映兩條時間序列相似程度的值刻劃了這兩條時間序反映兩條時間序列相似程度的值刻劃了這兩條時間序列的相似性，其概念和方法是時間序列挖掘的基礎(chǔ)。列的相似性，其概念和方法是時間序列挖掘的基礎(chǔ)。 給定某個時間序列，要求從大型時間序列數(shù)據(jù)集合中給定某個時間序列，要求從大型時間序列數(shù)據(jù)集合中找出與之相似的序列找出與之相似的序列-靜態(tài)時間序列的相似性。靜態(tài)時間序列的相似性。 實際生活中有大量以動態(tài)序列形式存在的時間序

2、列實際生活中有大量以動態(tài)序列形式存在的時間序列(時間序列流時間序列流)。 隨著研究的深入，動態(tài)時間序列的相似性問題也日益隨著研究的深入，動態(tài)時間序列的相似性問題也日益成為新時期時間序列相似性問題研究的重要組成部分。成為新時期時間序列相似性問題研究的重要組成部分。 與傳統(tǒng)靜態(tài)數(shù)據(jù)的精確相似不同，時間序列的相似性與傳統(tǒng)靜態(tài)數(shù)據(jù)的精確相似不同，時間序列的相似性會呈現(xiàn)多種變形，如振幅平移和伸縮、線性漂移、不會呈現(xiàn)多種變形，如振幅平移和伸縮、線性漂移、不連續(xù)、噪聲、時間軸伸縮等等。針對這些相似性變形，連續(xù)、噪聲、時間軸伸縮等等。針對這些相似性變形，研究者們提出了很多種相似性度量方法。研究者們提出了很多種

3、相似性度量方法。時間序列相似性應(yīng)用場景 1區(qū)別多個公司發(fā)展的相似性模型；區(qū)別多個公司發(fā)展的相似性模型； 2在股票價格上尋找價格波動的相似運動；在股票價格上尋找價格波動的相似運動； 3在樂譜版權(quán)問題上確認(rèn)兩份樂譜是否存在相似在樂譜版權(quán)問題上確認(rèn)兩份樂譜是否存在相似性；性； 4對具有相似銷售模式的商品進(jìn)行聚類；對具有相似銷售模式的商品進(jìn)行聚類； 5查找具有相似病情的心電圖；查找具有相似病情的心電圖； 6對網(wǎng)絡(luò)的異常流量預(yù)警；對網(wǎng)絡(luò)的異常流量預(yù)警； 7對天氣預(yù)報中災(zāi)害天氣的模式提取等。對天氣預(yù)報中災(zāi)害天氣的模式提取等。時間序列常見距離定義 距離函數(shù)一般要滿足如下幾個條件：距離函數(shù)一般要滿足如下幾個條

4、件： 非負(fù)性，即非負(fù)性，即d(A,B)d(A,B) 0 0 同一性：即同一性：即 d(A,A)=d(A,A)= 0 0 對稱性：對稱性： d(A,B)= d(B,A)d(A,B)= d(B,A) 滿足三角不等式：滿足三角不等式：d(A, B)d(A, B) d(A,C)+d(C,B) d(A,C)+d(C,B)，即兩點，即兩點間直線最短。這是一個高要求。間直線最短。這是一個高要求。 實際應(yīng)用中，距離函數(shù)很難滿足以上所有條件，實際應(yīng)用中，距離函數(shù)很難滿足以上所有條件，這取決于數(shù)據(jù)的表示和距離的計算方法。但是，這取決于數(shù)據(jù)的表示和距離的計算方法。但是，當(dāng)一些約束適當(dāng)放松的時候，相似性度量仍然可當(dāng)一

5、些約束適當(dāng)放松的時候，相似性度量仍然可以有效地進(jìn)行。以有效地進(jìn)行。 時間序列間的距離可用來衡量時間序列之間的差時間序列間的距離可用來衡量時間序列之間的差異性，以確定序列是否相似。異性，以確定序列是否相似。時間序列常見距離定義 時間序列間的距離可用來衡量時間序列之間的差時間序列間的距離可用來衡量時間序列之間的差異性，以確定序列是否相似。異性，以確定序列是否相似。(1)Minkowski 距離距離(Minkowski Distance) Minkowski 距離實際是一系列距離的集合，對于距離實際是一系列距離的集合，對于兩時間序列兩時間序列 和和 其計算方法其計算方法為為其中其中p=1時為曼哈頓距

6、離；時為曼哈頓距離；p=2時為歐氏距離；時為歐氏距離；時間序列常見距離定義(2)歐氏距離歐氏距離(Euclidean Distance) Euclidean 距離是被廣泛采用的時間序列相似度量，距離是被廣泛采用的時間序列相似度量，在時間序列相似性問題研究初期大量采用，它的在時間序列相似性問題研究初期大量采用，它的計算方法是計算方法是在實際使用中，為了防止對各段采用相同的系數(shù)，在實際使用中，為了防止對各段采用相同的系數(shù)，有時采用加權(quán)的歐氏距離：有時采用加權(quán)的歐氏距離：QCD(Q,C)niiicqCQD12,Given two time series Q = q1qn and C = c1cn t

7、heir Euclidean distance is defined as:歐氏距離的優(yōu)缺點 Euclidean 距離的優(yōu)點在于：直觀距離的優(yōu)點在于：直觀而計算簡便，而計算簡便，有良好的數(shù)學(xué)背景和意義；由于序列的一些常有良好的數(shù)學(xué)背景和意義；由于序列的一些常用變換用變換(如傅立葉變換等如傅立葉變換等)的系數(shù)有歐的系數(shù)有歐氏距離保持氏距離保持不變的性質(zhì)，所以經(jīng)常用于數(shù)據(jù)庫的高效索引；不變的性質(zhì)，所以經(jīng)常用于數(shù)據(jù)庫的高效索引；無參。無參。 缺點在于：需要計算的兩序列具有相同的長度；缺點在于：需要計算的兩序列具有相同的長度；對于時間序列點的突變對于時間序列點的突變(e.g. noise)比較敏感；比

8、較敏感；Euclidean 距離對序列按照時間軸進(jìn)行點對點依距離對序列按照時間軸進(jìn)行點對點依次計算，對時間序列的錯位、移位次計算，對時間序列的錯位、移位(out of phase)等比較敏感。等比較敏感。斜率距離-歐氏距離的一個變形 設(shè)設(shè) 其中其中 X 和和Y 分別分別是原始時間序列數(shù)據(jù)轉(zhuǎn)換而成的斜率組成的時間是原始時間序列數(shù)據(jù)轉(zhuǎn)換而成的斜率組成的時間序列，即：序列，即：時間序列常見距離定義(3)編輯距離編輯距離(Edit Distance) Edit 距離是計算兩字符串序列的距離一種度量，它距離是計算兩字符串序列的距離一種度量，它的定義是將一字符串轉(zhuǎn)換為另一字符串所需的最的定義是將一字符串轉(zhuǎn)

9、換為另一字符串所需的最小編輯小編輯(插入、刪除、改變插入、刪除、改變)步數(shù)。步數(shù)。 將時間序列進(jìn)行不同的量化和編碼后形成字符串，將時間序列進(jìn)行不同的量化和編碼后形成字符串，采用編輯距離計算兩字符串的距離。采用編輯距離計算兩字符串的距離。 Edit 距離的優(yōu)點是：充分利用了字符串匹配等成距離的優(yōu)點是：充分利用了字符串匹配等成熟計算方法；容易為人所理解；熟計算方法；容易為人所理解； 允許多對無。允許多對無。 缺點是：需要將時間序列轉(zhuǎn)化為相應(yīng)的字符串，缺點是：需要將時間序列轉(zhuǎn)化為相應(yīng)的字符串，精度不高；對于不同步的時間序列效果較差。精度不高；對于不同步的時間序列效果較差。時間序列常見距離定義(4)最

10、大公共子串最大公共子串 LCS(Longest Common Subseries)方法方法 LCS是計算兩時間序列間具有的公共長度子串，并是計算兩時間序列間具有的公共長度子串，并以該子串的長度與這兩個時間序列中較長序列的以該子串的長度與這兩個時間序列中較長序列的長度比值作為序列間的相似性度量。長度比值作為序列間的相似性度量。 LCS 方法借用字符串匹配中的相似性度量，有其一方法借用字符串匹配中的相似性度量，有其一定的可取之處。其不足是：公共長度子串的長定的可取之處。其不足是：公共長度子串的長度可能偏小，兩時間序列間可能非常相似，但是度可能偏小，兩時間序列間可能非常相似，但是由于數(shù)值并不能完全一

11、致，細(xì)小的偏差都會導(dǎo)致由于數(shù)值并不能完全一致，細(xì)小的偏差都會導(dǎo)致公共子串的長度偏小，從而影響到度量效果；公共子串的長度偏小，從而影響到度量效果；公共長度子串的獲取是一個問題，雖然可以采用公共長度子串的獲取是一個問題，雖然可以采用較為常見的動態(tài)規(guī)劃的方法解決，但是由于時間較為常見的動態(tài)規(guī)劃的方法解決，但是由于時間序列很可能是長度很長的序列，空間開銷較大。序列很可能是長度很長的序列，空間開銷較大。時間序列常見距離定義(5)DTW (5)DTW 距離距離(Dynamic Time Warping Distance)(Dynamic Time Warping Distance) DTW DTW 距離最

12、先在語音數(shù)字處理領(lǐng)域得到諸多成功距離最先在語音數(shù)字處理領(lǐng)域得到諸多成功的應(yīng)用，由的應(yīng)用，由 Berndt Berndt 和和 CliffordClifford于于 90 90 年代中旬年代中旬引入到時間序列挖掘中，并取得了巨大的成功。引入到時間序列挖掘中，并取得了巨大的成功。 在時間序列中，需要比較兩段長度可能并不相等在時間序列中，需要比較兩段長度可能并不相等的時間序列的相似性，在語音識別領(lǐng)域表現(xiàn)為不的時間序列的相似性，在語音識別領(lǐng)域表現(xiàn)為不同人的語速不同。而且同一個單詞內(nèi)的不同音素同人的語速不同。而且同一個單詞內(nèi)的不同音素的發(fā)音速度也不同，比如有的人會把的發(fā)音速度也不同，比如有的人會把AA這

13、個音這個音拖得很長，或者把拖得很長，或者把ii發(fā)的很短。另外，不同時發(fā)的很短。另外，不同時間序列可能僅僅存在時間軸上的位移，亦即在還間序列可能僅僅存在時間軸上的位移，亦即在還原位移的情況下，兩個時間序列是一致的。在這原位移的情況下，兩個時間序列是一致的。在這些復(fù)雜情況下，使用傳統(tǒng)的歐幾里得距離無法有些復(fù)雜情況下，使用傳統(tǒng)的歐幾里得距離無法有效地求得兩個時間序列之間的距離效地求得兩個時間序列之間的距離( (或者相似性或者相似性) )。 對于時間序列對于時間序列 和和 ，定，定義距離矩陣：義距離矩陣：DM=(aij) mn ，其中，其中aij=(xi-yj)2, 或其它或其它度量。度量。在在DM中

14、尋找一條彎中尋找一條彎曲路徑曲路徑Ww1,w2, wK, 其中其中wi=某個某個aij ，滿足以下性質(zhì)：滿足以下性質(zhì)：1、有界性：、有界性： maxm , n Km+n-1；2、邊界性：、邊界性：w1=a11,wk=amn ；3、單調(diào)性和連續(xù)性：、單調(diào)性和連續(xù)性：在彎曲路徑中，相鄰在彎曲路徑中，相鄰兩個元素兩個元素wk=aij,wk+1=ast ，則，則0 s-i 1, 0 t-j 1。單調(diào)性保證了在時間序列的每個時刻不會出現(xiàn)時間單調(diào)性保證了在時間序列的每個時刻不會出現(xiàn)時間交叉現(xiàn)象：交叉現(xiàn)象：同時使同時使 達(dá)到最小的彎曲路徑達(dá)到最小的彎曲路徑Ww1,w2, wK, 稱為最佳彎曲路徑。這個最小值

15、稱為時間序列稱為最佳彎曲路徑。這個最小值稱為時間序列 X 和和Y 動態(tài)時間彎曲距離，簡記為動態(tài)時間彎曲距離，簡記為 Ddtw(X,Y)，即有：，即有：DTW偽代碼實現(xiàn)int DTWDistance(s: array 1.n, t: array 1.m) DTW := array 0.n, 0.m for i := 1 to n DTWi, 0 := infinity for i := 1 to m DTW0, i := infinity DTW0, 0 := 0 for i := 1 to n for j := 1 to m cost:= d(si, tj) DTWi, j := cost +

16、 minimum(DTWi-1, j , DTWi , j-1, DTWi-1, j-1) return DTWn, mDTW的優(yōu)缺點 DTW 的優(yōu)點在于：克服了的優(yōu)點在于：克服了 Euclidean 距離距離點對必須對應(yīng)的問題，允許不同步的點對點對必須對應(yīng)的問題，允許不同步的點對應(yīng)計算；允許兩時間序列具有不同長度；應(yīng)計算；允許兩時間序列具有不同長度；對時間序列的同步問題不敏感。對時間序列的同步問題不敏感。DTW的優(yōu)缺點 缺點在于：缺點在于：DTW 的計算復(fù)雜度較高，對于長度分別為的計算復(fù)雜度較高，對于長度分別為n和和m 的時間序列，準(zhǔn)確計算的時間序列，準(zhǔn)確計算DTW 距離需要距離需要 O (

17、 nm )的的時間復(fù)雜度；時間復(fù)雜度；DTW 并不滿足距離的三角不等式并不滿足距離的三角不等式(例如，例如，DTW(111,111222)DTW(111,112)+DTW(112,111222)，在，在應(yīng)用到依據(jù)索引的時間序列相似查詢時剪枝過濾的程度應(yīng)用到依據(jù)索引的時間序列相似查詢時剪枝過濾的程度有限，在使用索引查詢時則可能會產(chǎn)生漏查。有限，在使用索引查詢時則可能會產(chǎn)生漏查。 病態(tài)彎病態(tài)彎曲問題，由于曲問題，由于 DTW允許在比較的時候兩個時間序列可進(jìn)允許在比較的時候兩個時間序列可進(jìn)行一定的非對應(yīng)時刻匹配，即求取最小距離而忽略時間行一定的非對應(yīng)時刻匹配，即求取最小距離而忽略時間上的差異，這容易

18、形成時域差異過大的情況發(fā)生。上的差異，這容易形成時域差異過大的情況發(fā)生。 解決辦法：對于，對比較的時間序列數(shù)據(jù)進(jìn)行降維處解決辦法：對于，對比較的時間序列數(shù)據(jù)進(jìn)行降維處理，進(jìn)一步探索高壓縮率和高效保真的降維方法；對于理，進(jìn)一步探索高壓縮率和高效保真的降維方法；對于，設(shè)定路徑查找的帶寬限制，即比較點不會超出參照，設(shè)定路徑查找的帶寬限制，即比較點不會超出參照點的點的ti-w,ti+w的時間范圍。這種方法同時的時間范圍。這種方法同時 還可能降低還可能降低算法的時間復(fù)雜度。算法的時間復(fù)雜度。通常將通常將w w選為時間序列長度的選為時間序列長度的10%10%。 LB_Keogh：一種考慮彎曲路徑限制的：一

19、種考慮彎曲路徑限制的DTW 計算計算方法方法 對于彎曲路徑限制為對于彎曲路徑限制為 w w 的時間序列的時間序列 DTW DTW 距離計算，距離計算，定義兩個序列定義兩個序列 U U 和和 L L，其中對于第，其中對于第 i i 個元素我們個元素我們有如下的上下界定義：有如下的上下界定義： U U 和和 L L 作為在作為在 2w 2w 時間窗內(nèi)，對于原時間序列的時間窗內(nèi)，對于原時間序列的每個元素所對應(yīng)的上下界，表現(xiàn)在圖形上實際上是每個元素所對應(yīng)的上下界，表現(xiàn)在圖形上實際上是形成了一個帶狀的域?qū)⒃紩r間序列包裹在這個域形成了一個帶狀的域?qū)⒃紩r間序列包裹在這個域中，如圖中，如圖 3-4 3-4

20、 所示。所示。此時，此時， LB_Keogh距離定義為：距離定義為： 定理：對于長度為 n 的任何兩個時間序列 X 和 Y，限定彎曲路徑窗口為w，即對于 xi和 yj點的比較，限定為 j-w i j+w，存在如下不等式：LB_Keogh(X,Y) DTW(X,Y)。 性質(zhì)：性質(zhì)：LB_Keogh 距離不是對稱的。即距離不是對稱的。即 LB_Keogh(X,Y) LB_Keogh(Y,X)。LB_Keogh的的Matlab實現(xiàn)實現(xiàn)LB_Keogh=sqrt(sum(Q U.* Q-U; Q n) 0 100 200 300 400 0 100 200 300 400 C Q Uniform Sc

21、aling time series query, Q, length n candidate, C, length m (mn) stretch Q to length p (npm): Qp Qpj = Qj*n/p, 1 j p scaling factor, sf = p/n max scaling factor, sfmax= m/n 0 100 200 300 400 0 100 200 300 400 C Q 0 100 200 300 400 0 100 200 300 400 Q Qp例如： a=1:10 b=1:13 如如c=b*(10/13)，則得，則得 c=0.76923

22、08 1.5384615 2.3076923 3.0769231 3.8461538 4.6153846 5.3846154 6.1538462 6.9230769 7.6923077 8.4615385 9.2307692 10.0000000 如如 c=ceiling(b*(10/13) 則則 c= 1 2 3 4 4 5 6 7 7 8 9 10 10DTW與與Uniform Scaling的不同的不同 Dynamic Time Warping (DTW) Considers only local adjustments in time, to match two time series

23、 However sometimes global adjustments are required DTW is being extensively used uniform scaling is complementary combination of both techniques offers rich, high-quality result setDTWUniform ScalingDTW與與Uniform Scaling的不同的不同 感覺Uniform Scaling不會比DTW（長度從n到m）做得更好。時間序列常見距離定義(7)Pearson 系數(shù)系數(shù) Pearson 系數(shù)也是

24、一種相似性度量，對于時間序列系數(shù)也是一種相似性度量，對于時間序列 X 和和Y ，其，其 Pearson 系數(shù)為：系數(shù)為： Pearson 系數(shù)用于線性關(guān)系時能夠取得較好的效果，系數(shù)用于線性關(guān)系時能夠取得較好的效果，但是對于非線性的測試則效果不佳，而且但是對于非線性的測試則效果不佳，而且 Pearson 系數(shù)對于數(shù)據(jù)中的突變數(shù)據(jù)點比較敏感。系數(shù)對于數(shù)據(jù)中的突變數(shù)據(jù)點比較敏感。Pearson Pearson 系數(shù)應(yīng)用示例系數(shù)應(yīng)用示例 在基于協(xié)同過濾的推薦系統(tǒng)中Pearson Pearson 系數(shù)應(yīng)用示例系數(shù)應(yīng)用示例Pearson Pearson 系數(shù)應(yīng)用示例系數(shù)應(yīng)用示例The Pearson co

25、rrelation coefficient takes values from +1 (strong positive correlation) to 1 (strong negative correlation). The similarities to the other users, User2 to User4, are 0.70, 0.00, and 0.79, respectively.Pearson Pearson 系數(shù)應(yīng)用示例系數(shù)應(yīng)用示例Pearson Pearson 系數(shù)還有另外一個杰出的性質(zhì)系數(shù)還有另外一個杰出的性質(zhì)Pearson 系數(shù)適合做增量計算 (8)基于基于PAA和

26、和SAX表示的距離表示的距離PAA distance lower-bounds the Euclidean Distance 0 20 40 60 80 100 120 -1.5 -1 -0.5 0 0.5 1 1.5 C Q 0 20 40 60 80 100 120 -1.5 -1 -0.5 0 0.5 1 1.5C Q = baabccbc C = babcacca QniiicqCQD12,Euclidean DistancewiiiwncqCQDR12),(wiiiwncqdistCQMINDIST12) ,(),(dist() can be implemented using a

27、table lookup.(9)馬氏距離(Mahalanobis distance) 度量點與集合間的相似性 The Mahalanobis distance is a measure of the distance between a point P and a distribution D, introduced by P. C. Mahalanobis in 1936 The Mahalanobis distance of an observation x=(x1,x2,xn)T from a set of observations with mean =(1,2,n)T and cov

28、ariance matrix S is defined as: Mahalanobis distance can also be defined as a dissimilarity measure between two random vectors and of the same distribution with the covariance matrix S: If the covariance matrix is the identity matrix, the Mahalanobis distance reduces to the Euclidean distance. If th

29、e covariance matrix is diagonal, then the resulting distance measure is called a normalized Euclidean distance: (si是標(biāo)準(zhǔn)差是標(biāo)準(zhǔn)差)直觀解釋 考慮估計歐氏空間中的一個測試點屬于一個集合考慮估計歐氏空間中的一個測試點屬于一個集合的概率的問題，直觀地離集合的質(zhì)心越近，這個的概率的問題，直觀地離集合的質(zhì)心越近，這個點屬于該集合的概率就越大。但是還要考慮這個點屬于該集合的概率就越大。但是還要考慮這個集合的分布形狀，即要計算集合的標(biāo)準(zhǔn)差并比較集合的分布形狀，即要計算集合的標(biāo)準(zhǔn)差并比較這個點與其相應(yīng)方向的標(biāo)準(zhǔn)差值的大小。這個點與其相應(yīng)方向的標(biāo)準(zhǔn)差值的大小。 The Mahalanobis distance is simply the The Mahalanobis distance is si