[研究方法] 用C#去實作一個簡單的Dynamic Time Warping (動態時間扭曲)

在做研究的時候，常常遇到一些研究方法。

不懂的時候，有時把它寫出來會更容易一些。

在這裡簡單做個筆記，關於動態時間調整(Dynamic Time Warping)演算法。


在上演算法的時候，常常會遇到一個很常用的方法。就是動態規劃

Dynamic Programming : (演算法筆記)

 [Introduction]

這邊要做個筆記的是Dynamic Time Warping  以下簡稱 : [DTW]

一個常見的演算法用於去比對兩個不同長度(維度)的向量他們之間的距離。

我們常用於比較距離的是 "歐式距離"

但是在不同維度的距離測量下，無法使用歐式距離。就必須用到DTW

然而我們要測量兩個不同維度的向量時候，可以用DTW。

常見的用途為機器學習上的應用，同時對於不同維度測量距離也是相當方便。

只要是可以化成 序列 的兩個向量，皆可以拿來測量距離。




在此有更詳細的介紹-> 張智星老師的網站，寫得非常棒! ，但有時假日會關站。

這篇作的筆記在於wiki上的解釋以及去實作上面的Pseudocode (維基解釋DTW)


[Implement]

我們在實作上的時候，序列A 以及 序列B是可以用 一維陣列去宣告的。

但是在這邊為了練習物件導向，我使用了類別。

但也是可以用物件陣列去實作一個序列。

我們先創建一個類別。

class Series
{
    private List<int> weightArray;

    // Constructor
    public Series(int number)
    {
        weightArray = new List<int>();
        // get a random number for weight
        Random random = new Random((int)DateTime.Now.Millisecond);
        for (int i = 0; i < number; i++ )
            weightArray.Add(random.Next(0, 10));
    }
    public int Weight(int index)
    {
        return weightArray[index];
    }
}

在上述程式碼之中。宣告了List變數，並且在每一個變數值給了一個亂數值(預設0-10)

因為是動態指定空間(假設上)，所以我用List去實作一個序列。

然後下面Weight 方法回傳一個傳入index他的權重值回去。




在主程式部分

Series seriesA = new Series(3);
Thread.Sleep(20); // in order to let the random random
Series seriesB = new Series(4);
上述程式碼之中，new出了序列陣列，並且宣告其大小值。

(此處因為是動態規劃的關係 我們預設上是一個 seriesA[2個值] ，一個series B[3個值]
而需要邊界值，所以宣告[3,4])

然而即呼叫丟入DTW去算值(距離)

int dis = DTWDistance(seriesA,seriesB);
System.Console.WriteLine("DISTANCE = " + dis); 


在DTW演算法部分

 public static int DTWDistance(Series seriesA , Series seriesB)
    {
        int[,] DTW = new int[3, 4];
        int cost = 0;
        // assume the infinity is 100000
        for (int i = 1; i < 3; i++ )
        {
            DTW[i,0] = 100000;
        }

        for (int i = 1; i < 4; i++)
        {
            DTW[0, i] = 100000;
        }
        DTW[0, 0] = 0;

        for (int i = 1; i < 3;i++ )
        {
            for (int j = 1; j < 4; j++ )
            {
                cost = Math.Abs(seriesA.Weight(i) - seriesB.Weight(j));
                int min = Math.Min(DTW[i-1,j] , DTW[i , j-1]) ;
                min = Math.Min(min , DTW[i-1,j-1]);
                DTW[i, j] = cost + min;
                //System.Console.WriteLine("DTW["+ i + "," + j + "] = "  + DTW[i,j]);
            }

        }
            return DTW[2,3];
 }


演算法部分其實是完全參考維基上的去實作。(要特別注意index)

其實主要上宣告一個DTW陣列，並且假設無窮大是100000

結果如下，

在動態規劃上的流程如下(畫得很粗糙請見諒!) 紅色箭頭為推導方向依此類推。

以這樣子來說就可以去測量兩個不同維度的向量距離。

完整程式碼如下:



參考資料來源: (上面文章內有提供連結)

維基DTW

張智星老師 DTW

用C實作簡單DTW