目錄

• 動(dòng)態(tài)時(shí)間規(guī)整算法: 從DTW到FastDTW
• • 總結(jié)：
  • 簡(jiǎn)介[^1]
  • DTW[^1]
  • FastDTW：使用多級(jí)粗化的方法[^1]
  • 結(jié)果

動(dòng)態(tài)時(shí)間規(guī)整算法: 從DTW到FastDTW

總結(jié)：

FastDTW作者對(duì)DTW的改進(jìn)點(diǎn)很巧妙！先通過舉例說明在一些情況下目前現(xiàn)有的方法對(duì)DTW改進(jìn)的缺陷，然后闡述自己的算法如何避免這些缺陷，最后還在三個(gè)數(shù)據(jù)集上證明在較長(zhǎng)時(shí)間序列數(shù)據(jù)中取得線性復(fù)雜度。 說明在做算法時(shí)，在無法找到更低復(fù)雜度的方法的時(shí)候，可以考慮在犧牲一些可接受的準(zhǔn)確度的情況下實(shí)現(xiàn)更低的復(fù)雜度算法！！！同時(shí)，必須通過實(shí)驗(yàn)證明準(zhǔn)確度降低的程度，文中就使用正常復(fù)雜度算法和近似復(fù)雜度算法進(jìn)行對(duì)比，從而計(jì)算出降低的準(zhǔn)確率！！最后，可以吸取現(xiàn)有的一些改進(jìn)的基礎(chǔ)上，再進(jìn)一步改進(jìn)，就比在原始的DWT算法上改進(jìn)的效果更好！！！！

簡(jiǎn)介¹

Dynamic time warping：動(dòng)態(tài)時(shí)間扭曲 (DTW) 是一種在兩個(gè)時(shí)間序列之間找到最佳對(duì)齊的技術(shù)，其中一個(gè)時(shí)間序列可以通過拉伸或收縮其時(shí)間軸來非線性地“扭曲”。 這種比對(duì)可用于找到對(duì)應(yīng)的區(qū)域或確定兩個(gè)時(shí)間序列之間的相似性。 DTW 經(jīng)常用于語音識(shí)別，以確定兩個(gè)波形是否代表相同的口語短語。 在語音波形中，每個(gè)語音的持續(xù)時(shí)間和聲音之間的間隔是允許變化的，但整體語音波形必須相似。 DTW 還用于許多其他學(xué)科 ，包括數(shù)據(jù)挖掘、手勢(shì)識(shí)別、機(jī)器人技術(shù)、制造和醫(yī)學(xué)。 一個(gè)時(shí)間序列“扭曲”到一個(gè)示例如圖 所示:

FastDTW：動(dòng)態(tài)時(shí)間規(guī)整 (DTW) 具有平方時(shí)間和空間復(fù)雜度，這限制了它在大時(shí)間序列中的使用。 后面有很多優(yōu)化，本文主要解釋 FastDTW，它是 DTW 的近似，具有線性時(shí)間和空間復(fù)雜度。 FastDTW 使用多級(jí)方法，從較粗的分辨率遞歸地投影計(jì)算并細(xì)化投影。 從理論上和經(jīng)驗(yàn)上證明了 FastDTW 的線性時(shí)間和空間復(fù)雜度。FastDTW 與其他兩種現(xiàn)有的近似 DTW 算法進(jìn)行比較來分析 FastDTW 的準(zhǔn)確性：約束（例如 Sakoe-Chiba Bands）和抽象。 與現(xiàn)有方法相比，準(zhǔn)確性有了很大提高。使用的方法太過巧妙，如下所示：

1) 粗化——將時(shí)間序列縮小為更小的時(shí)間序列，以更少的數(shù)據(jù)點(diǎn)盡可能準(zhǔn)確地表示相同的曲線。

2) 投影——在較低分辨率下找到最小距離扭曲路徑，并將其用作更高分辨率最小距離扭曲路徑的初始猜測(cè)。

3) 細(xì)化——通過局部調(diào)整扭曲路徑來優(yōu)化從較低分辨率投影的扭曲路徑。

DTW¹

動(dòng)態(tài)時(shí)間扭曲 (DTW) 是一種在兩個(gè)時(shí)間序列之間找到最佳對(duì)齊的技術(shù)，其中一個(gè)時(shí)間序列可以通過拉伸或收縮其時(shí)間軸來非線性地“扭曲”。最初的實(shí)現(xiàn)是使用動(dòng)態(tài)規(guī)劃，使用數(shù)學(xué)表達(dá)如下：

$$\begin{gathered} D(i,j)=Dist(i,j)+min[D(i?1,j),D(i,j?1),D(i?1,j?1)], \\ 其中：i=1,2,?,x\_len+1;j=1,2,?,y\_len+1 \end{gathered}$$
代碼實(shí)現(xiàn)如下²：

#參考：https://github.com/slaypni/fastdtw import numbers import numpy as np from collections import defaultdict from scipy.spatial.distance import euclideandef dtw(x, y, window=None, dist):"""@param x 序列1，可以是向量，矩陣，不局限于一個(gè)數(shù)列，但是dist要匹配@param y 序列2，可以是向量，矩陣，不局限于一個(gè)數(shù)列，但是dist要匹配@param window 序列設(shè)置要走的范圍，當(dāng)使用Sakoe-Chiba Bands就需要自定義縮小的范圍，這里默認(rèn)None會(huì)矩陣全走一遍@param dist 自定義距離計(jì)算方法，可以是歐氏距離，漢明距離等等"""len_x, len_y = len(x), len(y)if window is None:window = [(i, j) for i in range(len_x) for j in range(len_y)]# 相當(dāng)于矩陣的索引 i=1,2,...len_x+1 j=1,2,...len_y+1 window = ((i + 1, j + 1) for i, j in window)# 初始化矩陣中的其他元素inf和D[0, 0]=0；D使用元組記錄矩陣的值和path的i,jD = defaultdict(lambda: (float('inf'),))D[0, 0] = (0, 0, 0)# 按照公式進(jìn)行規(guī)劃計(jì)算for i, j in window:dt = dist(x[i-1], y[j-1])D[i, j] = min((D[i-1, j][0]+dt, i-1, j), (D[i, j-1][0]+dt, i, j-1),(D[i-1, j-1][0]+dt, i-1, j-1), key=lambda a: a[0])# 求解路徑path = []i, j = len_x, len_ywhile not (i == j == 0):path.append((i-1, j-1))i, j = D[i, j][1], D[i, j][2]path.reverse()return (D[len_x, len_y][0], path)if __name__ == '__main__':x = np.array([1, 2, 3, 4, 5], dtype='float')y = np.array([2, 3, 4], dtype='float')distance, path = dtw(x, y, dist=euclidean)

FastDTW之前，后來主要有兩種近似計(jì)算DWT的算法，損失一定準(zhǔn)確率的前提下減少時(shí)間和空間復(fù)雜度：

1、約束 – 限制在成本矩陣中評(píng)估的單元數(shù)

典型有兩種：constraints: Sakoe-Chiba Band (left) and Itakura Parallelogram (right)；很明顯，缺點(diǎn)是當(dāng)全局最優(yōu)解不在band內(nèi)時(shí)，就有誤差。圖中的陰影區(qū)域是成本矩陣的單元格，它們被填充由每個(gè)約束的 DTW 算法。每個(gè)陰影區(qū)域或窗口的寬度由參數(shù)指定。當(dāng)使用約束時(shí)，DTW 會(huì)通過約束窗口找到最優(yōu)的扭曲路徑。但是，如果全局最優(yōu)扭曲路徑不完全在窗口內(nèi)，則將無法找到它。使用約束以一個(gè)常數(shù)因子加速 DTW，但如果窗口大小是時(shí)間序列長(zhǎng)度的函數(shù)，則 DTW 仍然是 $O(N^2)$。約束在時(shí)間序列的時(shí)間對(duì)齊只有很小差異的領(lǐng)域中效果很好，并且最佳扭曲路徑預(yù)計(jì)接近線性扭曲并以相對(duì)直線對(duì)角線穿過成本矩陣。但是，如果時(shí)間序列是在完全不同的時(shí)間開始和停止的事件，則約束效果不佳。在這種情況下，warp 路徑可能會(huì)偏離線性 warp 很遠(yuǎn)，并且必須評(píng)估幾乎整個(gè)成本矩陣以找到最佳 warp 路徑。

下圖描述了約束 DTW 不能很好地工作的情況的簡(jiǎn)化示例，必須評(píng)估整個(gè)成本矩陣以獲得良好的結(jié)果。這可能發(fā)生在時(shí)間序列是受監(jiān)控設(shè)備的應(yīng)用程序中，這些設(shè)備以可預(yù)測(cè)的順序發(fā)出命令（例如開/關(guān)），但命令之間的時(shí)間量（穩(wěn)態(tài)條件）未指定。此類數(shù)據(jù)的示例包括航天飛機(jī)閥門特征。

2、抽象——對(duì)數(shù)據(jù)的簡(jiǎn)化表示執(zhí)行 DTW

這種方法作者在FastDTW中也用上，如圖所示，就是在低分辨率的矩陣中求解，也會(huì)有誤差，因?yàn)槁窂讲粔蚣?xì)化。抽象通過對(duì)數(shù)據(jù)的簡(jiǎn)化表示進(jìn)行操作來加速 DTW 算法。這些算法包括 IDDTW 、PDTW 和 COW 。時(shí)間序列的大小被縮小以使成本矩陣更易于計(jì)算。為較低分辨率的時(shí)間序列找到了一個(gè)扭曲路徑并被映射回到全分辨率。

由此產(chǎn)生的加速取決于使用了多少抽象。顯然，計(jì)算出的翹曲路徑隨著抽象級(jí)別的增加，它變得越來越不準(zhǔn)確。投影低分辨率扭曲全分辨率的路徑通常會(huì)創(chuàng)建一個(gè)遠(yuǎn)非最佳的扭曲路徑。這是因?yàn)榧词谷绻顑?yōu)扭曲路徑通過低分辨率單元，則將扭曲路徑投影到更高的分辨率忽略了扭曲路徑中可能非常重要的局部變化。因此不適用于局部變化劇烈的序列。

FastDTW：使用多級(jí)粗化的方法¹

FastDTW使用下面三種方法進(jìn)行改進(jìn)：

1) 粗化——將時(shí)間序列縮小為更小的時(shí)間序列，以更少的數(shù)據(jù)點(diǎn)盡可能準(zhǔn)確地表示相同的曲線。

2. 投影——在較低分辨率下找到最小距離扭曲路徑，并將其用作更高分辨率最小距離扭曲路徑的初始猜測(cè)。

3. 細(xì)化——通過局部調(diào)整扭曲路徑來優(yōu)化從較低分辨率投影的扭曲路徑。

總結(jié)：

1、FastDTW中的分級(jí)使用更高分辨率計(jì)算，彌補(bǔ)了之前的Abstract的方法，原來只使用一次降低分辨率；

2、FastDTW中的細(xì)化使用半徑參數(shù)控制，彌補(bǔ)原來的Band的方法那種不靈活性，因?yàn)锽and的方法需要依靠先驗(yàn)知識(shí)判斷最優(yōu)路徑大概在那些位置；而半徑參數(shù)只是作為分級(jí)粗化投影的一個(gè)補(bǔ)充。確實(shí)很巧妙！！！

如圖所示具體如下：粗化通過平均相鄰的點(diǎn)對(duì)來減少時(shí)間序列的長(zhǎng)度（或分辨率）。生成的時(shí)間序列比原始時(shí)間序列小兩倍。粗化運(yùn)行多次以產(chǎn)生時(shí)間序列的不同分辨率。投影采用以較低分辨率計(jì)算的扭曲路徑，并以較高的分辨率確定它通過的單元格。由于分辨率增加了兩倍，因此低分辨率扭曲路徑中的單個(gè)點(diǎn)將映射到更高分辨率的至少四個(gè)點(diǎn)（如果 |X| = |Y |，則可能 > 4）。然后在細(xì)化過程中將此投影路徑用作啟發(fā)式方法，以找到更高分辨率的扭曲路徑。細(xì)化在投影路徑的鄰域中找到最佳的扭曲路徑，其中鄰域的大小由半徑參數(shù)控制。在我們的多級(jí)方法中，成本矩陣僅填充在從先前分辨率投影的路徑的附近。由于扭曲路徑的長(zhǎng)度隨著時(shí)間序列的長(zhǎng)度線性增長(zhǎng)，我們的多級(jí)方法是 O(N) 算法。 FastDTW 算法首先使用粗化來創(chuàng)建將被評(píng)估的所有分辨率。圖中顯示了一個(gè)時(shí)間序列上的例子在運(yùn)行 FastDTW 算法時(shí)創(chuàng)建的四個(gè)分辨率（使用多少個(gè)分辨率的粗化矩陣按照實(shí)際序列長(zhǎng)度確定）。

在圖 中，從 1/8 分辨率的扭曲路徑的投影顯示為 1/4 分辨率的重度陰影單元。為了細(xì)化投影路徑，使用非常具體的約束運(yùn)行受約束的 DTW 算法，即僅評(píng)估投影扭曲路徑中的單元格。這將通過從較低分辨率投影的扭曲路徑區(qū)域找到最佳扭曲路徑。然而，全局最優(yōu)扭曲路徑可能不完全包含在投影路徑中。為了增加找到全局最優(yōu)解的可能性，有一個(gè)半徑參數(shù)來控制投影路徑每一側(cè)上的額外單元數(shù)，這些單元格也將在優(yōu)化扭曲路徑時(shí)進(jìn)行評(píng)估。在圖 中，半徑參數(shù)設(shè)置為 1。由于半徑而在扭曲路徑細(xì)化過程中包含的單元格被輕微著色。一旦以 1/4 分辨率細(xì)化扭曲路徑，該扭曲路徑將投影到 1/2 分辨率，擴(kuò)大半徑 1，然后再次細(xì)化。最后，將扭曲路徑投影到圖 中的全分辨率 (1/1) 矩陣。投影被半徑擴(kuò)展并最后一次細(xì)化。這個(gè)細(xì)化的扭曲路徑是算法的輸出。 FastDTW 在所有分辨率下評(píng)估了 4 + 16 + 44 + 100 = 164 個(gè)單元，而 DTW 評(píng)估了 256 (162) 個(gè)單元。對(duì)于這個(gè)小問題，效率的提高并不是很顯著，尤其是考慮到創(chuàng)建所有四個(gè)分辨率的開銷，在長(zhǎng)序列有很大差距。然而，FastDTW 評(píng)估的單元數(shù)與時(shí)間序列的長(zhǎng)度成線性關(guān)系，而經(jīng)典的動(dòng)態(tài)時(shí)間扭曲算法總是評(píng)估$N^2$個(gè)單元（如果兩個(gè)時(shí)間序列的長(zhǎng)度均為 N）。

代碼實(shí)現(xiàn)：

FastDTW的遞歸實(shí)現(xiàn)²：

#參考：https://github.com/slaypni/fastdtw from __future__ import absolute_import, division import numbers import numpy as np from collections import defaultdict from scipy.spatial.distance import euclideandef dtw(x, y, window=None, dist):"""@param x 序列1，可以是向量，矩陣，不局限于一個(gè)數(shù)列，但是dist要匹配@param y 序列2，可以是向量，矩陣，不局限于一個(gè)數(shù)列，但是dist要匹配@param window 序列設(shè)置要走的范圍，當(dāng)使用Sakoe-Chiba Bands就需要自定義縮小的范圍，這里默認(rèn)None會(huì)矩陣全走一遍@param dist 自定義距離計(jì)算方法，可以是歐氏距離，漢明距離等等"""len_x, len_y = len(x), len(y)if window is None:window = [(i, j) for i in range(len_x) for j in range(len_y)]# 相當(dāng)于矩陣的索引 i=1,2,...len_x+1 j=1,2,...len_y+1 window = ((i + 1, j + 1) for i, j in window)# 初始化矩陣中的其他元素inf和D[0, 0]=0；D使用元組記錄矩陣的值和path的i,jD = defaultdict(lambda: (float('inf'),))D[0, 0] = (0, 0, 0)# 按照公式進(jìn)行規(guī)劃計(jì)算for i, j in window:dt = dist(x[i-1], y[j-1])D[i, j] = min((D[i-1, j][0]+dt, i-1, j), (D[i, j-1][0]+dt, i, j-1),(D[i-1, j-1][0]+dt, i-1, j-1), key=lambda a: a[0])# 求解路徑path = []i, j = len_x, len_ywhile not (i == j == 0):path.append((i-1, j-1))i, j = D[i, j][1], D[i, j][2]path.reverse()return (D[len_x, len_y][0], path)def reduce_by_half(x):"""分辨率減半，使用平均的方法"""return [(x[i] + x[1+i]) / 2 for i in range(0, len(x) - len(x) % 2, 2)]def expand_window(path, len_x, len_y, radius):"""計(jì)算radius下的時(shí)間窗"""path_ = set(path)for i, j in path:for a, b in ((i + a, j + b)for a in range(-radius, radius+1)for b in range(-radius, radius+1)):path_.add((a, b))window_ = set()for i, j in path_:for a, b in ((i * 2, j * 2), (i * 2, j * 2 + 1),(i * 2 + 1, j * 2), (i * 2 + 1, j * 2 + 1)):window_.add((a, b))window = []start_j = 0for i in range(0, len_x):new_start_j = Nonefor j in range(start_j, len_y):if (i, j) in window_:window.append((i, j))if new_start_j is None:new_start_j = jelif new_start_j is not None:breakstart_j = new_start_jreturn windowdef fastdtw(x, y, radius, dist):min_time_size = radius + 2# 長(zhǎng)度小于min_time_size，直接使用DTW計(jì)算if len(x) < min_time_size or len(y) < min_time_size:return dtw(x, y, dist=dist)# 每次粗化一半，得到新的序列x_shrinked = reduce_by_half(x)y_shrinked = reduce_by_half(y)# 遞歸計(jì)算，直到滿足len(x) < min_time_size or len(y) < min_time_size則回溯distance, path = fastdtw(x_shrinked, y_shrinked, radius=radius, dist=dist)# 根據(jù)radius計(jì)算新的計(jì)算范圍window = expand_window(path, len(x), len(y), radius)return dtw(x, y, window, dist=dist)

結(jié)果

錯(cuò)誤率計(jì)算：

在準(zhǔn)確度上：

相比Band和Abstraction的方法，錯(cuò)誤率更低，而且隨著radius的增加，錯(cuò)誤率降低，后面已經(jīng)很接近DTW算法；

在時(shí)間上：

雖然在數(shù)列長(zhǎng)度200以內(nèi)體現(xiàn)不出區(qū)別，但是隨著時(shí)間序列長(zhǎng)度的增加，越來越接近線性時(shí)間復(fù)雜度。

參考：

---

Salvador S, Chan P. Toward accurate dynamic time warping in linear time and space[J]. Intelligent Data Analysis, 2007, 11(5): 561-580. ?? ?? ??

GitHub - slaypni/fastdtw: A Python implementation of FastDTW ?? ??

總結(jié)

以上是生活随笔為你收集整理的动态时间规整算法: 从DTW到FastDTW的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。