# AP5成型機 - 算法筆記 (DTW)
> [name=JayHsu][time=Fri, Sep 27, 2019 1:29 AM]

[TOC]

## 算法介紹
- DTW: Dynamic Time Warping, 动态时间规整
- DTW可以计算两个时间序列的相似度，尤其适用于不同长度、不同节奏的时间序列（比如不同的人读同一个词的音频序列）。DTW将自动warping扭曲 时间序列（即在时间轴上进行局部的缩放），使得两个序列的形态尽可能的一致，得到最大可能的相似度。 [(知乎)](https://zhuanlan.zhihu.com/p/32849741)
- 當我們要比較兩個序列的相似度時, 最直覺的算法就是先將兩組序列的數據點做一一對應, 接著計算每一個配對數據點的差異, 最後將所有的差異相加, 就能代表這兩個序列的相似度
 

- 但限制兩個序列的數據點要一一對應並不合理, 兩個序列之間的數據點, 有可能是一對多與多對一的關係.

- 找到兩個序列之間的數據點對應關係, 讓兩個序列計算出來的差異最小, 就是DTW算法要做的事情

- 因此, 我們可以拿DTW來計算兩個序列之間的相似度

- 也就是说，两个比对序列之间的特征是相似的，只是在时间上有不对齐的可能，这个算法名中的Time Warping，指的就是对时间序列进行的压缩或者延展以达到一个更好的匹对。[(算法筆記)](https://blog.csdn.net/raym0ndkwan/article/details/45614813)

## 算法流程
给定一个样本序列X和比对序列Y, DTW分為以下兩步驟:
1. DTW首先会根据序列点之间的距离(欧氏距离)，获得一个序列距离矩阵 M，其中行对应X序列，列对应Y序列，矩阵元素为对应行列中X序列和Y序列点到点的欧氏距离

2. 然后根据距离矩阵生成损失矩阵(Cost Matrix)或者叫累积距离矩阵Mc，两个序列的距离，由损失矩阵最后一列给出，在这里也就是2。
- 損失矩陣直觀的看就是去窮舉兩個序列之間所有點的可能對應, 並計算差距, 最後可由损失矩阵看出兩個序列的最相似對應關係, 並且算出兩個序列的差距

- 换句话说，就是给定了距离矩阵，如何找到一条从左上角到右下角的路径，使得路径经过的元素值之和最小。这个问题可以由动态规划（Dynamic Programming）解决（时间复杂度O(N+M)），也就是上面例子中，计算损失矩阵的过程，实际上不需要把整个矩阵都求解出来，大致将对角线上的元素求解出来即可。

## python實作流程


步驟：
1. 讀取控制器數據
2. 由於每個Case的製程參數設定不同, 所以當比較不同Case的參數相似性時, 必須先將數據做Nomalize, 將數據轉換到0~1之間, 使用sklearn裡面的MinMaxScaler
3. DTW算兩個序列的數據點對應關係, 並且計算兩個序列之間的歐幾里得距離
4. 畫圖比較兩個序列之間差異

## Source Code
> http://10.160.29.112:8888/tree/AP5/MMIA/IM_Algorithm/Algorithm-DtwAnalysis.ipynb

Source Code主要包含兩個Class, 一個(DataAgent)讀取數據, 另一個(DtwAnalysis)分析DTW

class DTWAnalysis(object):
    """This class implement DTW分析
    functinos:
        preparedata - 準備DTW分析要用的數據
        getDtwAnalysis - DTW分析
        plt - 畫圖
    """ 
    
    def preparedata(self):
        """
        準備DTW分析要用的數據, 
            Case1/Case2的控制器數據 - df_ctr1/df_ctr2
            Case1/Case2在Event區間的控制器數據 - df_evt1/df_ctr2
            Case1/Case2的Event區間數據的Normalize - df_sca1/df_ctr2
        Parameters: NA
        Returns: NA
        """     
        
    def getDtwAnalysis(self):
        """
        DTW分析, 以下為分析步驟
        1. 直接使用dtw套件得到dtw分析結果
            分析結果 - dict_dtwSummary
        Parameters: NA
        Returns: NA
        """                
        
    def plt(self):
        """
        畫出每個參數的Case參數趨勢圖, 並標註
            - 第一欄：Case 1參數趨勢圖
            - 第二欄：Case 2參數趨勢圖
            - 第三欄：DTW分析結果
        Parameters: NA
        Returns: NA
        """                
        

## Demo

c1 = MCase('case01')
c2 = MCase('case02')
dtwAnalysis = DTWAnalysis(c1=c1, c2=c2)
dtwAnalysis.plt()


## 其他
實作一個新的class MCase, 方便存取case資訊
Class:

class MCase(object):
    def __init__(self, caseid, **kwargs):
        case = json.load(open('case.json', 'r'))
        casecfg=case[caseid]
        #casecfg=case['case01']
        self.strdt = datetime.strptime(casecfg['data_strdt'], '%Y-%m-%d %H:%M:%S')
        self.enddt = datetime.strptime(casecfg['data_enddt'], '%Y-%m-%d %H:%M:%S')
        self.strts, self.endts = self.strdt.timestamp(), self.enddt.timestamp()
        self.evt_str, self.evt_end = casecfg['idx_evt'], casecfg['idx_evt2']
        self.mid = casecfg['machine']
        

Usage:

c1 = MCase('case02')
print(c1.strts, c1.endts, c1.mid)
print(c1.evt_str:c1.evt_end)

###### tags: `AP5成型機`