Time2Graph: Revisting Time Series Modeling with Dynamic Shapelets
原文位址整體導讀
- 文章提出了帶有時間意識的Shapelet，除了可以挖掘時序中的異常狀态之外，可以自動感覺異常狀态所在時間位置上的敏感度；
- 文章嘗試捕捉不同Shapelet之間的關系，提出了通過圖結構(Graph)對這種關系進行表達的方法，在挖掘異常變化軌迹的同時也具備良好的可解釋性。文章發表在人工智能領域頂級會議 AAAI 2020 上
時序模組化中的挑戰
時間序列模組化旨在發現資料中的時空依賴關系，學術界對此有廣泛研究，例如異常檢測[2]，語音識别[3]等。這裡的關鍵問題是如何提取時間序列中代表性的特征。以前的工作很大一部分從經典的特征工程和表示學習入手，這些方法具有很好的可解釋性，但主要依靠人的經驗，在複雜的場景下很難做到通用化。近年來随着深度學習的發展，許多工作開始嘗試一些複雜的模型方法來自動的挖掘特征。然而，盡管這些方法取得了良好的效果[4,5]，但由于模型的複雜度高以及難以對結果很好的解釋，許多方法不能很好地滿足實際工業落地的需求。
基于以上背景為出發，該文嘗試通過Shapelet[6], 一種可自動挖掘具有代表特征的時序子序列的方法出發，通過分析不同Shapelet之間的關系，建構Graph進行表示，提供一種可推理可解釋且具有良好表現的時序模型。
動機：動态的Shapelet
Shapelet，代表一類可以在分類場景中提供直接的解釋性和見解的時間序列子序列[6]，并且基于Shapelet的模型在各種研究中都被證明是有前景的[7,8,9]。
上圖展現了一個Shapelet的案例。每一個Shapelet(或了解為子序列波形)會在整個時序中找到最比對的位置，以及比對程度。現有的工作主要着眼于靜态的分析Shapelet。但是，在現實世界中，Shapelet通常是動态的，這展現在兩個方面：
- 首先，出現在不同時間段的同一個Shapelet可能會産生不同的影響。例如，在檢測到竊電使用者的場景下，夏季或冬季的低電耗比春季更可疑，因為制冷或供暖裝置的使用使得用電量應該更高。
- 其次，确定Shapelet的演化方式對于全面了解時間序列至關重要。實際上，在特定時間具有較小值的Shapelet很難将竊電使用者與确實消耗少量電的普通使用者區分開。一種替代方法是識别曾經具有高電耗的Shapelet，但突然消耗很少的使用者。換句話說，這裡的一個重要線索是Shapelet如何随時間演變。
該文章将能夠反映其在不同時間片上的代表性的時序子序列稱為具有時間意識的Shapelet(Time-aware Shapelet)。此外，為了深入挖掘Shapelet的動态性和相關性，文章提出了一種新穎的方法，通過提取具有時間感覺的Shapelet并建構Shapelet演化圖來學習時間序列的表示，具體的可以參考發表在 AAAI 2020 的全文[1]。
本文開始展示的圖中顯示了一個來自真實用電記錄的具體示例，它可以更好地展現該文章建構圖的動機：圖a顯示了竊電使用者在一年中的用電情況：1月到5月是沒被抓時的用電曲線，之後是被抓後正常的用電情況。文章給每個月配置設定了最有代表性的Shapelet，并在圖b中顯示了兩個有意思的Shapelet（＃72和＃67），以及它們的時間意識因素，其中深色區域表示Shapelet相對于淺色區域更具區分性。Shapelet演變圖如圖c所示，說明了Shapelet在正常情況下如何從一個轉移到另一個：對于正常的用電量記錄，其Shapelet的過渡有一條清晰的路徑（＃90→＃67→＃ 85）。但是，對于異常資料，他們走一條不明顯的路徑（＃85→＃72→＃7），這表明Shapelet轉移路徑的連通性可以為檢測異常時間序列提供了參考标準。最後，文章将學習到的Shapelet和時間序清單示的問題轉化為圖嵌入問題，并用圖算法進行解決。
捕捉具有時間意識的Shapelet
正式地，一個Shaplet
是代表某個類别的時序片段。更确切地說，它可以通過某些特定的名額，将時序
分成兩個較小的集合，一個接近
而另一個遠離，例如對于時間序列分類任務，可以将正樣本和負樣本放入不同的組中，具體可以形式化為
這裡
表示相對于特定組
的距離，函數
接受兩個有限集作為輸入，傳回一個标量值以訓示這兩個集合有多遠，它可以是資訊增益或集合上的一些不相似性度量，即KL散度。
為了捕獲Shapelet 的動态性，文章定義了兩個因素來定量測量Shapelet在不同水準上的時序影響。具體來說，文章介紹一個局部因素
來表示特定Shapelet的第n個元素的内部重要性。之後，Shapelet
與時序片段
之間的距離可以被重新定義為
指的是DTW距離的最佳對齊。另一方面，在全局範圍内，文章旨在衡量跨段的時間效應對Shapelet的判别力的影響。直覺上Shapelet在不同的時間步長可能代表完全不同的含義，這裡可以直接通過添加段級權重來測量此類偏差。正式地，文章裡設定了一個全局因素
捕獲跨段影響，然後Shapelet
與時序
之間的距離可以寫為
然後給定一個分類任務，這裡可以建立一套監督學習方法，以選擇最重要的具有時間意識的Shapelet，并可以為每一個Shapelet學習其相應的時間因素
和
。特别地，這裡有一個從所有子序列中選擇出的作為shapelet候選者的片段池，以及一組帶标簽的時間序列
。對于每個候選者
，都有以下目标函數：
在分别從Shapelet候選者那裡學習了時序因素之後，文章選擇損失最小的前K個shapelet作為最終的具有時間意識的Shapelet。
建構Shapelet演化圖
Shapelet 演化圖是有向權重圖
，其中
由K個頂點所組成，每個頂點表示一個shapelet，每個有向邊
與其權重
，表示在相同的時間序列中，shapelet
跟着另一個shapelet
的出現機率。這裡的關鍵思想是，圖中的路徑可以自然反映出shapelet的演變及其過渡模式，然後可以将圖嵌入算法應用于學習shapelet以及時間序清單示。
文章首先配置設定每個時序片段
到距離最近的幾個Shapelets。詳細地說，這裡将shapelet的指派機率标準化為
這裡有
的預定義限制，
。然後，對于每個對
，文章從shapelet建立權重邊
到
，并通過權重
合并所有的重複邊。最後，将從每個節點獲得的邊緣權重歸一化為1，這自然會解釋每對節點之間的邊緣權重。
時序表示學習
最後，文章對如上構造的Shapelet演化圖來學習Shaplet和給定時間序列的表示。首先采用現有的圖形嵌入算法DeepWalk[10]來獲得頂點（shapelet）的表示向量，然後對于在時間序列中的每個片段，将其配置設定到不同的shapelet及其權重。最後連接配接或聚合所有這些嵌入向量以獲得原始時間序列的表示向量。然後可以将時間序列嵌入應用于各種下行任務，請參考本文的實驗部分[1]。
評價結果
文章對來自UCR-Archive [11]的三個公共基準資料集，和來自中國國家電網和中國電信的兩個真實世界資料集進行時間序列分類任務。實驗結果如下表所示：
文章還進行了廣泛的消融實驗和觀察研究，以驗證其提出的架構。在這裡，文章在不同的時間步上建構了Shapelet演化圖，以更深入地了解shapelet動态演變，如下圖所示。它顯示了兩個圖表，一個表示一月，另一個表示七月。在1月，Shapelet＃45具有較大的輸入/輸出度，并且在1月和2月（深色區域）突出顯示了其對應的時間意識分數。這表明45号Shapelet很可能在年初開始成為一種常見模式。至于7月份，Shapelet＃45不再像1月份那樣重要。同時，Shapelet＃42（在1月幾乎是一個孤立點）在7月變得非常重要。盡管在構造Shapelet演化圖時沒有明确考慮季節性資訊，但包含的時機因素意味着它們已被納入圖生成過程中。
Reference
[1] Cheng, Z; Yang, Y; Wang, W; Hu, W; Zhuang, Y and Song, G, 2020, Time2Graph: Revisiting Time Series Modeling with Dynamic Shapelets, In AAAI, 2020
[2] Chandola V, Banerjee A, Kumar V, et al. Anomaly detection: A survey[J]. ACM Computing Surveys, 2009, 41(3).
[3] Shimodaira, H.; Noma, K.-i.; Nakai, M.; and Sagayama, S. 2002. Dynamic time-alignment kernel in support vector machine. In _NIPS’02_, 921–928.
[4] Malhotra, P.; Ramakrishnan, A.; Anand, G.; Vig, L.; Agar- wal, P.; and Shroff, G. 2016. Lstm-based encoder- decoder for multi-sensor anomaly detection. _arXiv preprint arXiv:1607.00148_.
[5] Johnson, M.; Duvenaud, D. K.; Wiltschko, A.; Adams, R. P.; and Datta, S. R. 2016. Composing graphical models with neu- ral networks for structured representations and fast inference. In _NIPS’16_, 2946–2954.
[6] Ye, L., and Keogh, E. 2011. Time series shapelets: a novel technique that allows accurate, interpretable and fast classifi- cation. DMKD. 22(1):149–182.
[7] Bostrom, A., and Bagnall, A. 2017. Binary shapelet trans- form for multiclass time series classification. In TLSD- KCS’17. 24–46.
[8] Hills, J.; Lines, J.; Baranauskas, E.; Mapp, J.; and Bagnall, A. 2014. Classification of time series by shapelet transformation. DMKD. 28(4):851–881
[9] Lines, J.; Davis, L. M.; Hills, J.; and Bagnall, A. 2012. A shapelet transform for time series classification. In _KDD’12_, 289–297.
[10] Perozzi, B.; Al-Rfou, R.; and Skiena, S. 2014. Deepwalk: Online learning of social representations. In _KDD_, 701–710.
[11] Dau, H. A.; Keogh, E.; Kamgar, K.; Yeh, C.-C. M.; Zhu, Y.; Gharghabi, S.; Ratanamahatana, C. A.; Yanping; Hu, B.; Begum, N.; Bagnall, A.; Mueen, A.; and Batista, G. 2018. The ucr time series classification archive.
https://www.cs.ucr.edu/~eamonn/time_series_data_2018/.