時間序列聚類是挖掘物聯網等場景下頻繁模式的關鍵技術，但現有SOTA方法（如K-Shape）面臨兩大瓶頸：1）傳統數據庫因LSM-Tree存儲導致時間戳無序，難以直接支持高效聚類；2）跨時間范圍查詢需重復計算，效率低下。
清華大學團隊創新提出K-Shape數據庫內適配方案，首次實現時序聚類與存儲引擎深度協同。針對長序列性能問題，進一步提出Medoid-Shape及其數據庫優化版本，在保持精度的同時顯著提速。實驗驗證，該方案在密集寫入、多范圍查詢場景下性能優勢突出，為時序分析開辟新路徑！
我花了很長時間整理出了十幾篇【時間序列+聚類】的相關論文，希望能幫到大家。
感興趣的可以? [絲 xin]? 我~~
?
【論文標題】In-Database Time Series Clustering
【論文鏈接】https://dl.acm.org/doi/10.1145/3709696
研究背景
時間序列聚類是一種重要的數據分析技術，廣泛應用于多種領域。現有的最先進的（SOTA）時間序列聚類方法 K-Shape 能夠高效地通過形狀對時間序列進行聚類，并且其準確性顯著優于其他方法。然而，K-Shape 在物聯網（IoT）場景中面臨挑戰，因為物聯網數據具有到達無序和大量數據存儲的特點。因此，數據庫內時間序列聚類所面臨如下挑戰：
-
由于延遲到達，時間序列通常在 LSM 樹數據庫中以無序方式存儲，而現有的聚類方法要求數據按時間順序排列。按時間順序對數據進行排序會帶來額外的預處理時間開銷。
-
對于不同的任務，可能需要使用不同的時間過濾器反復執行聚類操作。每次 K-Shape 都需要從頭開始聚類，效率低下。
-
K-Shape 在處理長子序列時效率低下，因為其復雜度與子序列長度成正比。
核心貢獻
本研究致力于解決上述三個挑戰。貢獻可總結如下：
-
數據庫內K-Shape：提出了對現有聚類方法K-Shape的數據庫內適應版本，利用數據庫中預計算的頁面級元數據進行加速。
-
Medoid-Shape：提出了一種新的聚類方法Medoid-Shape，通過用近似的中心點（medoid）代替K-Shape中的形狀提取步驟，避免了耗時的特征向量分解。
-
數據庫內Medoid-Shape：將 Medoid-Shape方法適應到數據庫內場景，進一步提高了聚類效率。
-
實驗驗證：通過廣泛的實驗驗證了所提方法的高效性和有效性。
方法解析
?
數據庫內K-Shape
本文利用 LSM-Tree 的分層文件結構，通過多版本合并機制直接在數據庫內對無序數據按時間范圍排序，避免全量數據加載和外部排序開銷。
-
單頁元數據：對每頁內的完整子序列運行 K-Shape，存儲聚類中心、成員子序列的和矩陣（用于形狀提取）、平均類內距離。不完整子序列單獨存儲，留待后續拼接。
-
多頁聚合：相鄰頁：直接合并相似聚類中心，更新和矩陣（無需重新計算形狀）。 互補頁：將不完整子序列拼接為完整子序列，視為新頁后合并。 重疊頁：加載沖突數據點更新和矩陣，重新提取中心形狀。
-
最終聚類：所有頁聚合后，從全局和矩陣一次性提取最終聚類中心。
Medoid-Shape
K-Shape 基于 SBD（Shape-Based Distance）和迭代質心優化的復雜度為 （ 為序列數， 為序列長度），難以處理長序列。本文放棄傳統質心迭代優化，改用聚類內真實存在的 Medoid 作為代表，避免特征向量分解的高計算量。
-
貪心算法：迭代選擇樣本子序列，每次選擇能使目標函數提升最大的子序列加入中心集。將長序列劃分為固定長度的子窗口，對每個子窗口進行局部形狀對齊，降低全局對齊的計算復雜度。
-
近似評估：先對子序列做快速近似聚類，用聚類中心近似代表全體子序列。計算目標函數時，僅需比較中心與候選 Medoids，大幅減少計算量。
?
數據庫內Medoid-Shape
本文在 LSM-Tree 的 Compaction 階段預計算不同時間粒度的 Medoid 候選集，存儲為元數據，加速查詢時候選集篩選。基于時間范圍查詢條件，按層級索引快速定位相關數據分片，動態剔除不相關子序列的 Medoid 計算。
-
單頁元數據：每頁預計算近似聚類中心、類內平均距離、類大小。不存儲和矩陣，節省空間。
-
多頁聚合：相鄰/互補頁：按距離合并相似聚類中心，加權更新類內距離。重疊頁：直接更新沖突子序列所屬的聚類中心。
-
最終聚類：將所有頁的近似中心作為候選，運行貪心算法選出最終 Medoids。
?
實驗驗證
不同數據負載下的可擴展性
子序列數量的可擴展性。上圖展示了在不同子序列數量 N 下的時間成本。在所有數據規 模下，本文的數據庫內方法表現最佳。
子序列長度的可擴展性。上圖展示了不同子序列長度下的時間成本。隨著子序列長度的增加，K-Shape 和基于數據庫的 K-Shape 的時間成本迅速增加，這是由于形狀提取過程耗時。然而，Medoid-Shape 和基于數據庫的 Medoid-Shape 在子序列長度較大時，分別表現出高達 1 個和 2 個數量級的改進，所需的時間顯著減少。
不同配置下的效率
隨著補充頁面數量的增加，數據庫內方法的時間成本略有增加，因為需要額外處理新形成的子序列。然而，這些方法仍然優于傳統方法。
in-database K-Shape 的時間成本隨著重疊頁面數量的增加而迅速增加，因為每次處理重疊頁面都需要進行形狀提取。相比之下，in-database Medoid-Shape 的時間成本增加較少，因為它可以在線性時間內處理重疊頁面。
隨著重疊長度的增加，數據庫內方法的時間成本略有增加，因為需要更多時間來處理重疊部分。即使在極端情況下（所有頁面都重疊，且重疊長度達到10,000個數據點），數據庫內方法仍然優于傳統方法。
總結
在本文中，我們研究了數據庫內的時間序列聚類，以支持在基于 LSM 樹的時間序列數據庫中對不同時間范圍的時間序列進行反復聚類。現有的數據庫外方法在處理大量物聯網數據以及頻繁的具有不同時間過濾器的聚類查詢時，效率低下。因此，我們提出利用數據庫特性在數據庫內高效地對時間序列進行聚類。具體而言，我們設計了一種基于數據庫的 SOTA 時間序列聚類方法 K-Shape 的適應版本。為了解決 K-Shape 在處理長子序列時效率低下的問題，我們提出了 Medoid-Shape 以及相應的數據庫內 Medoid-Shape 適應版本以進一步加速。我們推導了幾個命題以確保在數據庫內提議的多頁聚合。我們還證明了 Medoid-Shape 的有保證的誤差界限，以確保其有效性。值得注意的是，我們在 Apache IoTDB（一個開源的商品化基于 LSM 樹的時間序列數據庫）中實現了并部署了所有提議。大量的實驗表明，我們的提議具有更高的效率，且有效性相當。
