論文學習——一種基于DTW聚類的水文時間序列相似性挖掘方法

文章目錄

• 1 摘要
• 2 引言
• • 2.1 現有的研究
  • 2.2 本文貢獻
• 3 時間序列語義相似與聚類
• • 3.1 時間序列的語義是什麼
  • 3.2 層次聚類
  • 3.3 算法步驟
• 4 基于DTW聚類的相似性挖掘
• • 4.1 相似性挖掘準備階段
  • 4.2 相似性挖掘查詢階段
  • 4.3 資料預處理介紹
  • 4.4 特征點的選擇
  • 4.5 時間序列符号化
  • 4.6 符号序列度量
  • 4.7 小結一下
• 5 實驗對比與分析
• • 5.1 實驗步驟
  • 5.2 時間消耗對比結果
  • 5.3 準确性分析
• 6 總結

寫在前面：《一種基于DTW聚類的水文時間序列相似性挖掘方法》；期刊：《計算機科學》；主辦機關：重慶西南資訊有限公司；中文核心

作者介紹：

1 摘要

1. 先對資料進行小波去噪、特征點分段 以及 語義劃分；
2. 基于DTW距離對劃分後的子序列，做層次聚類并符号化；
3. 根據符号序列間的編輯距離，篩選候選集；
4. 最後通過序列間的DTW距離進行精确比對，擷取相似水文時間序列。

實驗資料：以滁河六合站的日水位資料進行實驗, 結果表明，所提方法能夠有效地縮小候選集, 提高查找語義相似的水文時間序列的效率。

2 引言

1. 水文時間序列的相似性分析，可以回答防汛指揮中經常會問到的 “目前水文過程相當于曆史上哪一時期的同類過程” 等問題, 同時也是研究時序關聯規則挖掘、聚類、模體挖掘以及異常發現等問題的基礎，因而在洪水預報、防洪排程等方面有着重要的意義。
2. 在水文時間序列 相似性查詢中，時間序列降維和相似性度量方式，是相似性分析研究的熱點問題。

2.1 現有的研究

1. 基于特征點的分段表示法，能在保留子序列語義的基礎上，實作有效的時間序列降維，在水文時間序列相似性挖掘中被廣泛應用。

   例如：

   《水文時間序列相似性查詢的分析與研究》

   《基于Hadoop水文時間序列相似性研究與應用》

   《水文時間序列相似性查詢優化算法》

   《基于語義相似的水文時間序列相似性挖掘》

2. 時間序列符号化的經典算法SAX，SAX采用PAA算法對時間序列進行降維，用不同的符号代表相應平均值的子序列，具有簡單易用的特點。然而,PAA算法等長劃分時往往會破壞語義，導緻符号化效果不理想，是以後期的符号化算法多是基于SAX算法，并結合資料特點進行改進。

   例如：

   《A symbolic representation of time series, with implications for streaming algorithms》

3. 闫秋燕等提出了一種基于關鍵點的SAX改進算法，該算法選取序列中滿足一定篩選條件的極值點作為關鍵點來對時間序列進行分段【就是分段+SAX結合被】，很好地保留了序列的形态特征。

   例如：

   《一種基于關鍵點的SAX改進算法》

4. 朱躍龍等通過引入語義相似的概念，基于極值點對時間序列進行劃分并賦予語義符号,實作水文時間序列的語義符号化。

   例如：

   《基于語義相似的水文時間序列相似性挖掘》

5. 李迎提出了一種基于DTW的符号化時間序列聚類算法，該算法将DTW距離用于關鍵點提取後的符号序列間的相似性度量，再利用Normal矩陣和FCM方法進行聚類分析，說明了将DTW距離用于時間序列聚類分析具有較高的準确率。

   注意：但是該算法對初始聚類中心敏感,容易産生局部最優解,且無法避免孤點造成的影響。

   《一種基于DTW的符号化時間序列聚類算法》

現有的水文時間序列的相似性度量方式主要有歐氏距離、動态模式比對、FastDTW距離

2.2 本文貢獻

在前人研究成果的基礎上（《基于語義相似的水文時間序列相似性挖掘》作者：朱躍龍等），本文在其

DTW_SS

方法的基礎上，針對

DTW_SS

方法在挖掘過程中産生的候選集過大（如果查詢的原序列比較短，或者是模式很單一的話，比如說{UD}， 那麼就有可能出現 候選集過大的問題），導緻采用DTW距離進行精确比對耗時過長的問題。

• 本文提出的方法：

  DTW_CSW

  方法

  ① 采用凝聚層次聚類方法，對語義劃分後的子序列做聚類分析并符号化；

  ② 根據符号化結果在曆史資料中擷取與查詢符号序列編輯距離最小的候選集；

  ③ 最後在候選集中進行DTW距離精确比對以擷取相似時間子序列，進而提高查詢效率。

3 時間序列語義相似與聚類

3.1 時間序列的語義是什麼

時間序列語義化是對水文時間序列進行離散化，将所得子序列看作一系列的符号，并對每個符号進行語義解釋。

3.2 層次聚類

1. 層次聚類方法将資料對象 聚內建聚類樹，通常分為凝聚和分裂兩種層次聚類方法。

2. 凝聚層次聚類 ：是一種自底向上的政策，首先将每個對象看作一個類，然後根據不同的類間距離度量準則合并初始類，直至滿足終止條件。

   分裂層次聚類 ：是一種自頂向下的政策，先是将所有對象看作一個類，然後再不斷分解，直到滿足終止條件。

• 本文采用的是凝聚層次聚類，無需事先确定聚類中心，且在結果生成後，可以剔除資料中的孤點，能達到更好的聚類效果。

3.3 算法步驟

本文采用DTW距離，作為時間子序列間的相似性度量；

通過凝聚層次聚類法，對單一語義的子序列進行聚類，距離算法步驟如下：

輸入：時間序列子序列集合（通過極值點分段後的，一段一段右符号表示出來的序列 的集合）

輸出：N類語義相同的子序列們

步驟一：初始化。

把每個子序列歸為一類，計算兩兩之間的DTW距離作為類間距離；

步驟二：合并

尋找各個類之間，距離最近的兩個類，然後合并他們。

步驟三：重新計算類間距離。

步驟四：重複步驟二和步驟三，直到滿足終止條件（終止條件應該是 找到N個類？？）

• 然後就是需要确定聚類中心

  

4 基于DTW聚類的相似性挖掘

此方法分為兩個階段：準備階段和查詢階段。

4.1 相似性挖掘準備階段

4.2 相似性挖掘查詢階段

• 這一段我笑拉了，這也太搞笑了…
• 為啥等長？等長用啥DTW，直接歐式距離上啊！
• 防止候選集太大然後DTW計算複雜度太高，你做候選集全用DTW，怎麼了、是生成候選集的時間複雜度不計算在内嗎？？

  

• 曆史序列X
• 查詢序列Q

4.3 資料預處理介紹

1. 資料填補

   用前後的均值來代替缺失值

2. 資料平滑

   時間序列的整體波動趨勢，是水文時間序列資料中最受關注的部分。

   有研究表明，小波變換能夠在很好地保持序列真題變化趨勢的情況下最大限度地去除噪聲，适用于水文時間序列平滑處理。

   《基于語義相似的水文時間序列相似性挖掘》

   《水文時間序列模式挖掘》

如下圖所示，小波變換對于時間序列的平滑效果。

4.4 特征點的選擇

特征點。特征點是指水文時間序列中，對序列整體形态和整體趨勢變化影響較大的資料點。

基于特征點的分段表示法——能夠在不破話序列語義的基礎上，實作有效的時間序列降維，提高查詢速度。

4.5 時間序列符号化

時間序列符号化，是将 時間序列 轉換為 符号序列 的過程。

符号序列的每一個符号，都表示一段子序列。（因為是用上升、平穩、下降 三個符号 UDB 來表示的嘛！）

4.6 符号序列度量

• 兩個符号序列通過插入、删除和替換符号，達到完全一緻的最小編輯次數。

4.7 小結一下

• 說白了，就是在人家朱躍龍（作者）的基礎上，在得到符号序列之後，多做了一步聚類分析。【其實真的沒必要，因為做聚類分析也是在用DTW去計算距離，通過這個方法縮小候選集，前後時間還可能對掉了…。。。。結果就是又麻煩，又沒有效率】

5 實驗對比與分析

資料：滁河六合站的日平均水位

方法：在DTW_SS的基礎上，采用基于DTW距離的凝聚層次聚類方法，對符号化後的子序列做聚類，達到縮小候選集的目的。

5.1 實驗步驟

注意：表1 說明了兩種方法的符号序列，以及門檻值的選取。

5.2 時間消耗對比結果

• 我還是那句話，沒有計算“建構候選集”的時間複雜度，這個結果毫無參考價值好嘛。。。
• 隻計算【查詢階段】的時間複雜度，而不計算【資料準備】階段的時間複雜度？？？
• （如果我哪裡是沒有了解到位，也可以指出來，不過先噴再說，如果人家的過程正确，歡迎私信或者評論，反正我先噴再說。。。）

  

5.3 準确性分析

• 我真的笑不活了，準确性是這麼判斷的嗎？你在别人的實驗基礎上，加了一點雜七雜八的東西進去，然後選三個最相似的，結果中了兩個相同的，就說自己的方法是有效的？是準确的？我2022年看這個論文真覺得看不懂了

6 總結

終于到了總結部分，這文章看的我真的是很火大。

把方法改的亂七八糟，然後結果準确率的衡量名額又十分主觀，方法“改進了”，但是在對比時間複雜度的時候也并沒有計算到【準備階段】的時間複雜度，說白了就是把人家在後面要做的比較，放在前面做完了，然後就說自己的效率比别人高？？

學術？道德？底線？

我真的火力全開在噴。。。

• 哎受不了了，下一篇下一篇！