之前已經(jīng)介紹過了DTW算法，現(xiàn)在根據(jù)文章 toward accurate dynamic time warping in linear time and space,以及別人實(shí)現(xiàn)的fastdtw代碼分析fast-DTW算法。參考博客：http://www.cnblogs.com/kemaswill/archive/2013/04/18/3029078.html
簡單講講fast-DTW，該算法最主要有兩個(gè)部分，第一個(gè)是約束

將搜索空間約束在陰影位置，減少了搜索的次數(shù)。
第二個(gè)是抽象（abstraction）,將圖像的像素合并，1/1–>1/2–>1/4–>1/8…知道可以確定路徑。如下圖，當(dāng)像素合并為1/8時(shí)，已經(jīng)可以確定路徑，即從左下角到右上角。接著再像素粒度細(xì)化，從1/8回到1/4確定該像素下的路徑，接著1/2，最后1/1。

接下來我們看看python實(shí)現(xiàn)的fastdtw算法。

def fastdtw(x, y, radius=1, dist=lambda a, b: abs(a - b)):min_time_size = radius + 2if 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)distance, path = fastdtw(x_shrinked, y_shrinked, radius=radius, dist=dist)window = __expand_window(path, len(x), len(y), radius)return dtw(x, y, window, dist=dist)

從代碼可以看出來這個(gè)過程實(shí)現(xiàn)是遞歸的，并且調(diào)用了三個(gè)函數(shù)，__expand_window，dtw，__reduce_by_half。我們先去弄懂這三個(gè)函數(shù)，再回頭來把整個(gè)fastdtw算法理順。
首先我們來看這個(gè)dtw算法。仔細(xì)理一理思路，就能很清晰的分析這個(gè)代碼了，window就是限制了的搜索范圍，只要在這個(gè)范圍內(nèi)按照這個(gè)條件搜索就行。
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])
這其中用到了python的collections的defaultdict模塊，只要你傳入一個(gè)默認(rèn)的工廠方法，那么請(qǐng)求一個(gè)不存在的key時(shí)， 便會(huì)調(diào)用這個(gè)工廠方法使用其結(jié)果來作為這個(gè)key的默認(rèn)值。尋找路徑的時(shí)候是從終點(diǎn)尋到起點(diǎn)即可。

def dtw(x, y, window=None, dist=lambda a, b: abs(a - b)):len_x, len_y = len(x), len(y)if window is None:window = [(i, j) for i in xrange(len_x) for j in xrange(len_y)]window = ((i + 1, j + 1) for i, j in window)D = defaultdict(lambda: (float('inf'),))D[0, 0] = (0, 0, 0)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)

接著，看看constraint是怎么實(shí)現(xiàn)的，即dtw中的window。這一部分沒太弄明白，我運(yùn)行了一下這個(gè)程序，當(dāng)2x2–> 4x4擴(kuò)大的時(shí)候，path是整個(gè)大小，而4x4–>8x8擴(kuò)大的時(shí)候path大小為56。我表示很驚訝，要是我寫這個(gè)代碼，寫出來的path大小不會(huì)這么多。

paper里面寫時(shí)間復(fù)雜度的時(shí)候提到

假設(shè)我們是在8*8的的大小下尋找搜索空間，按照paper的公式來說應(yīng)該是56個(gè)，而按照?qǐng)D示和描述應(yīng)該是44個(gè)，不信自己可以去數(shù)一數(shù)。當(dāng)然我也知道當(dāng)N趨于無窮時(shí)，搜索空間的差異就顯得很小了。

def __expand_window(path, len_x, len_y, radius):path_ = set(path)for i, j in path:for a, b in ((i + a, j + b)for a in xrange(-radius, radius+1)for b in xrange(-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 xrange(0, len_x):new_start_j = Nonefor j in xrange(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 window

最后返回去看整個(gè)代碼，fastdtw就是一直遞推調(diào)用自己，同時(shí)將兩個(gè)序列二分壓縮，直到達(dá)到可以直接計(jì)算出path的大小時(shí)，返回每一次調(diào)用。然后將粒度細(xì)化，就是圖二的整個(gè)過程。

總結(jié)

以上是生活随笔為你收集整理的fast-DTW算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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