基于動態填充和權重調整的改進DTW算法

關鍵詞：動態規整算法；缺失值；權重調整；相似性；動態填充

中圖分類號：TP311.13;U491 文獻標識碼：A

文章編號：1009-3044（2024）36-0067-03"開放科學（資源服務） 標識碼（OSID） ：

0 引言

動態時間規整（Dynamic Time Warping， DTW） [1]算法自1994年由Berndt等人[2]提出以來，作為一種經典且廣泛應用的相似性度量方法，展現出獨特的優勢。DTW允許時間序列間的局部彈性變換（如移位、收縮及拉伸） ，在保留單調性和邊界約束的條件下，尋求全局最優對齊路徑，顯著增強了時間序列匹配的靈活性與精度。然而，傳統DTW算法在處理復雜多變的時間序列數據時，其局限性逐漸顯現[3]。核心問題在于，傳統DTW算法僅聚焦于點對點之間的距離信息，而忽視了序列的整體動態特性與局部結構特征[4]。

此外，現有的一些改進嘗試雖在一定程度上優化了DTW對齊效果與分類精度，但往往未能全面兼顧序列的整體趨勢、分段特性及細節波動間的復雜關系，從而限制了其普適性和性能表現。在實際應用場景中，時間序列數據紛繁復雜，不同領域乃至同一序列在不同分析目標下所側重的關鍵信息各不相同。例如，心電信號分析強調細節波動與局部特征的精確捕捉[5]，而水文數據則更需把握整體變化趨勢[6]。單一信息維度的考量易導致算法在特定領域應用中的性能下滑。此外，噪聲干擾與數據缺失作為時間序列分析中常見的挑戰，進一步加劇了相似性度量的難度。傳統濾波方法雖能減輕噪聲影響，卻可能伴隨高頻細節信息的損失[6]；而DTW算法在直接處理含缺失值數據時，常因數據完整性的破壞而難以準確評估序列間的相似性。

鑒于上述挑戰，本文創新性地提出了MDIWDTW算法。該算法巧妙融合動態缺失值填充與權重調整機制，通過智能填充策略，有效彌補缺失數據造成的信息斷層；同時，通過精細的權重分配，平衡不同特征在相似性評估中的重要性，從而實現對復雜時間序列數據更為全面、準確的相似性度量。

2 動態規整算法

2.1 DTW 算法原理

DTW算法優化了特征參數錯位所產的影響，基本原理是尋找兩個時間序列之間的最優彎曲路徑，序列中的數據點根據坐標值去匹配另一條序列中最具有相同特點的點，數據點的距離和即為最優彎曲距離的累加和[7]。

2.2 DTW 算法的局限性

DTW算法的基本原理是尋找兩個時間序列之間的最優彎曲路徑，其中數據點的距離和即為最優彎曲距離的累加和。盡管DTW算法在處理非同步時間序列時表現出色，但其對缺失值表現出高度敏感性，傳統的DTW算法在存在缺失值時往往無法直接應用。

當時間序列中存在缺失值時，如果直接應用DTW 算法，可能會因為缺失值而引入額外的距離或偏差，同時也可能導致序列在比對過程中出現不連續或跳躍現象，使得DTW算法難以找到最佳的對齊路徑。

3 MDIW-DTW 算法框架

為了提高交通流時間序列的利用率，并更好地聚類相關的時間序列，本文提出一種基于改進DTW算法的聚類方法。該方法將著重于優化DTW算法以更好地處理時間序列中的特性，如季節性、趨勢、周期性以及潛在的缺失值，同時確保聚類過程能夠準確地識別出具有相似行為模式的時間序列。

3.1 算法流程

MDIW-DTW算法的實現流程如下：

第一步：預處理時間序列，隨機挖空30%數據。

第二步：根據時間序列的特點，采用均值填充數據，并標記。

第三步：構建距離矩陣和權重矩陣，并初始化相關參數。

第四步：根據距離矩陣和權重矩陣計算出相似矩陣。

式中：式（7） 中的γ和δ是調整相鄰點差異對權重影響的參數。這個公式的基本思想是，如果某個點與其前一個點的差異很小，那么該點在匹配過程中可能更重要。

3.2 算法復雜度分析

MDIW-DTW算法的時間復雜度主要取決于路徑搜索和權重調整兩個步驟。其中，路徑搜索的時間復雜度為O（n^2），n為時間序列的長度；權重調整的時間復雜度取決于權重更新的頻率和方式，但通常不會超過O（n）。因此，MDIW-DTW算法的整體時間復雜度仍保持在可接受的范圍內。

4 實驗驗證與結果分析

4.1 實驗數據集

實驗采用加利福尼亞高速公路網絡PEMS交通流數據集和云南省交通2019年1月1日至8月26日的環路檢測器采集的31天交通流數據，數據聚合周期分別為5分鐘、30分鐘、60分鐘。數據集如表1所示。

4.2 實驗設置

本實驗將MDIW-DTW算法與傳統DTW算法以及其他幾種處理缺失值的DTW改進算法進行對比，評價指標包括相似度計算的準確性。

4.3 實驗結果與分析

考慮到數據集缺失率的差異，算法相似性的度量性能也隨之變化。對于不同的數據集，算法均存在其最優參數配置。本實驗旨在驗證MDIW-DTW算法在參數固定情況下對不同數據類型的普適性，故將參數統一設置為γ=2和δ=1。需要說明的是，本次實驗設置的參數并非對所有數據集都是最優配置，在實際應用中通過選取最優參數可獲得更好的相似分類結果。

本文采用K-means聚類方法，通過輪廓系數來衡量距離矩陣的聚類效果。輪廓系數取值范圍為[0，1]，數值越大表明聚類效果越好。各數據集的聚類效果輪廓系數如表2所示。

根據表中數據可以看出不同的K值的選擇對距離矩陣聚類效果有影響，時間間隔為5分鐘的數據集相似距離聚類效果略差，當K值為4時，效果要好，時間間隔越長，每天數據量越少，距離矩陣聚類效果越好，輪廓系數越大。

本文根據DTW結合K-means對不同缺失率的時間序列進行聚類，輪廓系數表如表3所示。

由表中數據可知，MDIW-DTW算法在交通流數據集上計算相似性的表現優于傳統DTW算法，不同數據集呈現出不同的聚類效果，其中在CYNSTD2數據集上效果最為顯著。此外，在不同缺失率條件下，MDIW-DTW算法的距離值聚類效果始終保持優勢。

圖2和圖3展示了缺失率為30%時的結果可視化，其中深色表示樣本，淺色表示相似樣本。

實驗結果表明，MDIW-DTW算法在處理含缺失值的時間序列時表現出色。與傳統DTW 算法相比，MDIW-DTW算法在缺失率為30%時能夠更準確地計算時間序列間的相似度，并且具有更好的魯棒性。然而，當缺失率超過30%時，算法難以有效識別相似樣本。

5 結論與展望

本文提出了一種基于缺失值的動態規整算法改進方法（MDIW-DTW） ，通過動態填充缺失值并引入權重調整機制，提高了DTW算法在缺失值環境下的性能。實驗結果表明，MDIW-DTW算法在處理含缺失值的時間序列時具有更高的準確性和魯棒性。未來研究可進一步探索更高效的缺失值處理方法和權重調整策略，以提升MDIW-DTW算法的性能。同時，也可將MDIW-DTW算法推廣至更廣泛的應用領域。