原文連結：http://tecdat.cn/?p=22945
最近我們被客戶要求撰寫關於動態時間規整算法的研究報告，包括一些圖形和統計輸出
動態時間扭曲算法何時、如何以及為什麼可以有力地取代常見的歐幾里得距離，以更好地對時間序列數據進行分類
時間序列分類的動態時間扭曲
使用機器學習算法對時間序列進行分類需要一定的熟悉程度。
時間序列分類（TSC）任務通常由監督算法解決，它旨在創建分類器，將輸入時間序列映射到描述時間序列本身的一個或多個特徵的離散變量（類）中。
可以在語音識別或手勢和運動識別中找到時序分類任務的有趣示例。
圖 — 移動識別示例
用於其他類型的數據（例如表格數據）的標準分類算法不能直接應用，因為它們將每個樣本與其他樣本分開處理。
對於時間序列，不能忽略數據的時間順序，因此，不能考慮時間序列的每個樣本而考慮其他樣本，但必須保留時間順序。
出於這個原因，在文獻中，有幾種類型的時間序列分類技術，將在下一段中簡要解釋。
時間序列分類方法
作為TSC不同類型方法的簡要概述。
- 基於區間的方法：從不同的區間中提取時間序列的特徵和信息，並將標準分類器應用於特徵本身。算法的一個示例是時序森林分類器。
- 基於字典 的方法：將時間序列的特徵轉換為代表類的單詞。標準分類器應用於提取單詞的分布。算法的一個例子是模式袋。
- 基於頻率的方法：在頻譜水平上提取時間序列的特徵，通過頻率分析和連續的標準分類器。算法的一個示例是隨機間隔頻譜集成。
- 基於形狀的方法：形狀是代表類的時間序列的子序列。提取時間序列中k個最具特徵的形狀，然後使用標準分類器。算法的一個示例是 Shapelet 變換分類器。
- 集成方法：對於一般問題非常有競爭力，它們結合了幾個估計器，例如HIVE-COTE算法。
基於距離的方法
在本文中，我們將重點介紹基於距離的方法。
它是一種將距離度量與分類器混合以確定類成員的非參數方法。分類器通常是 k 最近鄰 （KNN） 算法，用於了解要標記的時間序列是否與訓練數據集中的某些時間序列相似。根據鄰域，最近的類或最近類的聚合與所分析的時間序列相關聯。動態時間扭曲（DTW）是基於距離的方法的一個示例。
圖 — 基於距離的方法
距離指標
在時間序列分類中，我們需要計算兩個序列之間的距離，同時牢記每個序列內樣本之間的時間關係和依賴性。選擇正確的指標是這種方法的基礎。
歐幾里得距離
讓我們開始考慮常見的歐幾里得距離。
鑒於時間序列分類，歐幾里得距離是不合適的，因為即使它保留了時間順序，它也以逐點的方式測量距離。實際上，與兩個時間序列的歐幾里得距離的相似性是通過考慮它們的振幅來計算的，而與相移、時移和失真無關。
以圖中的示例為例。我們有樹時間序列：ts1、ts2 和 ts3。我們希望檢測兩條正弦曲線彼此相似，因為它們具有相同的形狀和上下趨勢，即使它們的相位和頻率略有不同。但是，如果我們計算歐幾里得指標，直線 ts3 的結果更接近 ts1。
圖 — 要比較的時間序列示例
之所以出現這種現象，是因為歐幾里得距離正在比較曲線的振幅，而不允許任何時間拉伸。
圖 — 歐幾里得匹配
動態時間扭曲
引入了動態時間扭曲以避免歐幾里得距離的問題。
從歷史上看，它是為語音識別而引入的。如圖所示，以不同的速度重複相同的句子，有必要將時間序列與相同的單詞相關聯，從而管理不同的速度。
圖 — DTW 的語音識別應用
DTW 允許您通過確定時間序列之間的最佳對齊方式並最大程度地減少時間失真和偏移的影響來衡量時間序列之間的相似性。
不同相的相似形狀，及時匹配彈性翹曲。
圖 — 動態時間扭曲匹配
算法
讓我們考慮兩個時間序列 X = （x₁， x₂， ...， xn） 和 Y = （y₁， y₂， ...， ym）， 在等距時間點採樣，長度相等或不同。
我們的目標是找到對齊時間序列的最小距離。
圖 — 要對齊的時間序列示例
定義局部成本矩陣，該矩陣將被最小化以找到最佳對齊方式。成本矩陣 C 定義為所有時間序列點的成對距離：
圖 — 當地成本矩陣 C
目的是通過遵循成本最低的路線，在局部成本矩陣上找到對齊時間序列的翹曲路徑。
翹曲路徑 p 是局部成本矩陣上的點序列，因此是兩個時間序列上的幾個點序列：
必須滿足一些條件：
- 邊界條件：
翹曲路徑的起點和終點必須是序列的第一個和最後一個點。
- 單調性條件：
以保留時間順序。
- 步長條件：
以限制跳躍和時間偏移，同時對齊序列。
每個翹曲路徑都有相關的成本：
- 與翹曲路徑 p 相關的成本函數
圖 — 翹曲路徑示例（非最佳）
目的是找到最佳的翹曲路徑：
DTW 通過遞歸實現解決，為此可以找到成本最低的翹曲路徑：
圖 — 最佳翹曲路徑
找到最佳翹曲路徑後，將計算出相關的最優成本，並將其用作 DTW 距離。
遞歸實現達到最優，但計算成本為 O（NM）， 其中 N 和 M 是兩個時間序列的長度。
k-最近鄰
回到對感興趣的時間序列進行分類的原始問題，距離度量可以與k-最近鄰（k-nn）算法耦合。這意味著您可以計算時間序列到訓練數據集中所有其他時間序列的 DTW 距離。然後，如果您正在考慮使用 1-nn 方法，則可以將最近鄰的類與時間序列相關聯，或者，同樣，您可以將 k 最近類中最常用的類與 k-nn 方法相關聯。
通過這種方式，您已經達到了為時間序列分配類的目標，該方法考慮了時間序列的時移。
傳統 DTW 的替代方法可加快速度
快速 DTW
提出了一種多級方法來加快FastDTW算法中的算法速度。
它需要不同的步驟：
- 粗化： 將時間序列縮小為較粗的時間序列。這通過對相鄰點對求平均值來減小時間序列的大小。
- 投影： 找到最小距離的翹曲路徑，用作更高解析度翹曲路徑的初始猜測。
- 優雅： 通過局部調整將翹曲路徑從較低解析度細化到較高解析度。此步驟在投影路徑的鄰域中查找最佳翹曲路徑，半徑 r 參數控制鄰域的大小。
圖 — 快速 DTW
FastDTW允許快速解析度，複雜度為O（Nr）， 具有良好的次優解決方案。
R語言實現
在這篇文章中，我們將學習如何找到兩個數字序列數據的排列。
創建序列數據
首先，我們生成序列數據，並在一個圖中將其可視化。
plot(a, type = "l")
lines(b, col = "blue")
點擊標題查閱往期內容
Python用KShape對時間序列進行聚類和肘方法確定最優聚類數k可視化
左右滑動查看更多
01
02
03
04
計算規整方式
dtw()函數計算出一個最佳規整方式。
align(a, b)
返回以下項目。你可以參考str()函數來了解更多信息。
現在，我們可以繪製組合。
用雙向的方法作圖
動態時間規整結果的繪圖：點比較
顯示查詢和參考時間序列以及它們的排列方式，進行可視化檢查。
Plot(align)
用密度作圖
顯示疊加了規整路徑的累積成本密度 。
該圖是基於累積成本矩陣的。它將最優路徑顯示為全局成本密度圖中的 "山脊"。
PlotDensity(align)
小結
總而言之, DTW是一種非常有用的計算序列最小距離的方法, 不論是在語音序列匹配, 股市交易曲線匹配, 還是DNA鹼基序列匹配等等場景, 都有其大展身手的地方. 它的最大特點是在匹配時允許時間上的伸縮, 因此可以更好的在一堆序列集合中找到最佳匹配的序列.
點擊文末 「閱讀原文」
獲取全文完整資料。
本文選自《R語言DTW(Dynamic Time Warping) 動態時間規整算法分析序列數據和可視化》。
點擊標題查閱往期內容
ARMA-GARCH-COPULA模型和金融時間序列案例
時間序列分析：ARIMA GARCH模型分析股票價格數據
GJR-GARCH和GARCH波動率預測普爾指數時間序列和Mincer Zarnowitz回歸、DM檢驗、JB檢驗
【視頻】時間序列分析：ARIMA-ARCH / GARCH模型分析股票價格
時間序列GARCH模型分析股市波動率
PYTHON用GARCH、離散隨機波動率模型DSV模擬估計股票收益時間序列與蒙特卡洛可視化
極值理論 EVT、POT超閾值、GARCH 模型分析股票指數VaR、條件CVaR：多元化投資組合預測風險測度分析
Garch波動率預測的區制轉移交易策略
金融時間序列模型ARIMA 和GARCH 在股票市場預測應用
時間序列分析模型：ARIMA-ARCH / GARCH模型分析股票價格
R語言風險價值：ARIMA，GARCH，Delta-normal法滾動估計VaR（Value at Risk）和回測分析股票數據
R語言GARCH建模常用軟體包比較、擬合標準普爾SP 500指數波動率時間序列和預測可視化
Python金融時間序列模型ARIMA 和GARCH 在股票市場預測應用
MATLAB用GARCH模型對股票市場收益率時間序列波動的擬合與預測R語言GARCH-DCC模型和DCC（MVT）建模估計
Python 用ARIMA、GARCH模型預測分析股票市場收益率時間序列
R語言中的時間序列分析模型：ARIMA-ARCH / GARCH模型分析股票價格
R語言ARIMA-GARCH波動率模型預測股票市場蘋果公司日收益率時間序列
Python使用GARCH，EGARCH，GJR-GARCH模型和蒙特卡洛模擬進行股價預測
R語言時間序列GARCH模型分析股市波動率
R語言ARMA-EGARCH模型、集成預測算法對SPX實際波動率進行預測
matlab實現MCMC的馬爾可夫轉換ARMA - GARCH模型估計
Python使用GARCH，EGARCH，GJR-GARCH模型和蒙特卡洛模擬進行股價預測
使用R語言對S＆P500股票指數進行ARIMA + GARCH交易策略
R語言用多元ARMA,GARCH ,EWMA, ETS,隨機波動率SV模型對金融時間序列數據建模
R語言股票市場指數：ARMA-GARCH模型和對數收益率數據探索性分析
R語言多元Copula GARCH 模型時間序列預測
R語言使用多元AR-GARCH模型衡量市場風險
R語言中的時間序列分析模型：ARIMA-ARCH / GARCH模型分析股票價格
R語言用Garch模型和回歸模型對股票價格分析
GARCH（1,1），MA以及歷史模擬法的VaR比較
matlab估計arma garch 條件均值和方差模型R語言POT超閾值模型和極值理論EVT分析