AAAI 2020 | 時序轉化為圖用於可解釋可推理的異常檢測

時間序列表示學習旨在學習一個將原始時間序列自動轉換為向量表示的函數，是時間序列領域研究的基本問題。近年來，將時序進行分段並學習特徵表示是熱門的研究方向，比如 Shapelet (具有特徵信息的一種或幾種時序波形)。然而，時序所反饋的是不斷變化的動態信息，這種動態信息應該如何進行直觀的表示，用於有高可解釋需求的異常檢測任務中呢？時間序列異常檢測[2]在工業界是非常常見的任務，模型常常要求對所判斷出的異常給出合理的解釋，從而幫助人們做出相應的動作。近年來，可解釋的時序建模多著眼於離散時序，在時間軸上將時序分段，然後從分段中抓出可以用於判斷異常的表示，常見的方法有：

字典方法[3]，找時序分段的特徵值

形狀方法[4]，找時序分段的特殊波形

聚類方法[5]，找時序分段的分類特徵

基於以上背景為出發，為了描述時間序列的動態信息，同時提供可解釋的模型表示用於異常檢測，該論文嘗試將Shapelet映射回時序中, 探尋位置的敏感度，並隨時間累積轉移關係，構建Graph進行表示，形成一種可推理可解釋的方法用於時序建模與異常分析。其研究成果被美國人工智慧頂級會議 AAAI-20 收錄發表。

美國人工智慧協會（American Association for Artificial Intelligence）是人工智慧領域的主要學術組織之一，成立於1979年。該協會主辦的年會（AAAI, The National Conference on Artificial Intelligence）是人工智慧領域頂級學術會議之一，被列為《中國計算機學會推薦國際學術會議和期刊目錄》(CCF) 中的A類學術會議，錄用率在20%左右。AAAI在全球有超過6000名會員，匯集了全球最頂尖的人工智慧領域專家學者。

圖 |  獲得圖靈獎的深度學習三巨頭齊聚AAAI 2020

論文標題 | Time2Graph: Revisiting Time Series Modeling with Dynamic Shapelets

論文來源 | AAAI 2020

論文連結 | https://arxiv.org/abs/1911.04143

代碼連結 | https://github.com/zjunet/Time2Graph

Shapelet[4]，是時序形狀分析方法的典型代表，旨在找到特殊的特徵片段波形用於時序分類，具有良好的可解釋性。基於Shapelet的模型在各種研究中都被證明是有前景的[6,7,8]。

上圖展現的是一個Shapelet的例子。每一個Shapelet會在時序中找到最匹配的位置，以及匹配程度。現有的工作主要著眼於靜態的分析，但現實中常常可以觀察到，Shapelet通常是動態的，這體現在兩個方面：首先，出現在不同時間位置的同一個Shapelet可能會有不同的含義其次，Shapelet的動態轉變對於全面理解時間序列十分重要該論文的研究將能夠反映不同片段上的Shapelet稱為具有時間意識的Shapelet (Time-aware Shapelet)。此外，為了深入挖掘Shapelet的動態性和相關性，文章提出了一種新穎的方法，即提取Time-aware Shapelet並構建Shapelet演化圖來學習時間序列的表示，具體的可以參考發表在 AAAI 2020 的全文[1]。

上圖展示了一個關於用電時序的例子，用於展現Time2Graph方法的構圖動機：圖a展示的是竊電用戶在一年中的用電情況。該研究將時序按月進行分段，並給每個月學習分配了最有代表性的Shapelet。圖b展示了兩個特殊的Shapelet，72和67號，以及它們的時間位置注意力分數，其中深色區域表示的位置相對於淺色區域更重要。如圖c所示，Shapelet演變圖展示了時序的動態變化，即圖中的節點表示一個Shapelet而邊表示Shaplet之間的關係。演化圖展現了在時序中Shaplet是如何從一個轉移到另一個的：

這表明Shapelet轉移路徑可以為檢測時序異常提供參考信息。該論文將學習Shapelet和時間序列表示的問題轉化為圖嵌入（Graph Embedding）問題，並用圖算法進行解決。

一、Time-aware Shapelet

為了捕獲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[9]來獲得頂點（Shapelet）的表示向量，然後對於在時間序列中的每個片段，將其分配到不同的Shapelet及其權重，最後連接或聚合所有這些嵌入向量以獲得原始時間序列的表示向量。學習到的表示向量應用於各種下遊時序任務。
四、實驗結果文章對來自UCR-Archive [10]的三個公共數據集，和來自中國國家電網和中國電信的兩個真實世界數據集進行時間序列分類任務。實驗結果如下表所示：

文章還進行了廣泛的消融實驗和觀察研究，以驗證其提出的框架。
在這裡，該研究在不同的時間位置上構建了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] Jessica Lin, Rohan Khade, and Yuan Li. 「Rotation-invariant similarity in time series using bag-of-patterns representation」. In: JIIS. 39.2 (2012), pp. 287–315.[4] Ye, L., and Keogh, E. 2011. Time series shapelets: a novel technique that allows accurate, intepretable and fast classifi- cation. DMKD. 22(1):149–182.[5] D. Hallac, S. Vare, S. P. Boyd, and J. Leskovec, 「Toeplitz inverse covariance-based clustering of multivariate time series data,」 SIGKDD, pp. 215–223, 2017.[6] Bostrom, A., and Bagnall, A. 2017. Binary shapelet transform for multiclass time series classification. In TLSD- KCS』17. 24–46.[7] Hills, J.; Lines, J.; Baranauskas, E.; Mapp, J.; and Bagnall, A. 2014. Classification of time series by shapelet transformation. DMKD. 28(4):851–881[8] Lines, J.; Davis, L. M.; Hills, J.; and Bagnall, A. 2012. A shapelet transform for time series classification. In KDD』12, 289–297.[9] Perozzi, B.; Al-Rfou, R.; and Skiena, S. 2014. Deepwalk: Online learning of social representations. In KDD, 701–710.[10] 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/.
記得把TSer設為星標哦~ \(^o^)/