WSDM 2021 | 建構動态圖分析時間序列狀态的演化

WSDM2021論文閱讀：時序演化狀态圖

本文簡要介紹我們剛剛被WSDM2021會議錄用并即将發表的論文"Time-Series Event Prediction with Evolutionary State Graph"(

論文位址

)，在文中我們提出了一種将時序轉化為圖進行表示模組化的方法。同時我們把所實作的方法落地為阿裡雲·SLS的智能巡檢服務，可以應用于大規模的時間序列異常檢測與分析，輔助運維、營運、研發等諸多場景。

整體導讀

• 文章通過真實場景下資料分析，發現了時間序列狀态之間的動态關系對于時序事件預測很重要；
• 文章提出了演化狀态圖來捕獲時序狀态之間的關系，并提出了EvoNet模型對演化狀态圖進行模組化分析，在提高事件預測準确度的同時，也具備良好的可解釋性；
• 文章發表在資料挖掘領域頂級會議 WSDM 2021 上。

時間序列的狀态

如何對時間序列進行有效的分析在學術界有廣泛的研究，例如異常檢測[2]，語音識别[3]等。工業界也有非常多的應用場景，通常需要模型在進行判斷的同時（例如判斷異常），給出所做判斷的合了解釋，這對幫助人們進行更好的決策有很大的作用。

可解釋的時間序列分析通常需要我們提取時間序列中代表性的特征。以前的工作很大一部分從經典的特征工程和表示學習入手，這些方法具有很好的可解釋性，但主要依靠人的經驗，在複雜的場景下很難做到通用化。近年來随着深度學習的發展，許多工作開始嘗試一些複雜的模型方法來自動的挖掘特征。然而，盡管這些方法取得了良好的效果，但由于模型的複雜度高以及難以對結果很好的解釋，許多方法不能很好地滿足實際工業落地的需求。

近年來，可解釋的時序模組化多着眼于離散時序，在時間軸上将時序分段，然後從分段中抓出可以用于判斷異常的表示，常見的方法有：

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

  

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

  

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

  

這些方法可以有效的捕捉時序中的狀态，即有表征意義的特征片段。然而，這些方式都是以靜态的方式捕捉出特征，而忽略了時間序列是動态演變的。基于以上背景為出發，為了描述時間序列的動态資訊，同時讓模型學習更好的可解釋性表示，該論文嘗試捕捉時序狀态随時間的動态變化資訊，将相鄰兩時序段之間的狀态變化用圖（Graph）這種資料結構進行表示。整體時序的演變轉化為動态圖的變化，形成一種可推理可解釋的方法用于時序模組化與分析。

時序狀态的識别

這裡以時序聚類為例子，描述時序狀态的識别以及在時序上的映射。這裡時序狀态定義為

，即将離散出的時序片段聚成

個特征類，抽取類的特征值。給定時序片段

和時序狀态

，我們可以量化他們之間的距離來表示時序片段映射到時序狀态的權重，具體為：

,

其中

描述時序片段與時序狀态之間的距離。簡單的，可以采用歐式距離。該距離越小，則識别的權重就越大。通過上面的方法，每個時序片段可以分别以不同的權重映射到

個狀态上。

時序演化狀态圖

當我們将時序段識别成帶權重的狀态集後，一種簡單的方法是将時間序列視為最可能狀态的新的序列，然後對新建構序列的馬爾科夫性質進行模組化分析[6]。 但是，一個時序段不隻會屬于一個狀态，而應該将其識别為具有不同權重的多個狀态。是以，這項工作提出了一種新穎的動态圖結構來描述狀态之間的關系，并探索狀态的動态變化如何揭示時間序列的演化。

論文将演化狀态圖定義為一系列權重有向圖

。具體地，每個圖被表示為

以表示從時序段

的狀态到

的狀态的轉變。圖中的每個節點都表示一個狀态

；每個邊

表示從𝑣到

的轉移關系（或簡稱關系），對應的轉移權重為

。這裡觀察到的每個時序段的狀态權重是獨立的，那麼轉移權重可以由下式計算：

這是

被識别為狀态𝑣和

被識别為狀态

的聯合權重。相比于建構新序列的方法，演化狀态圖通過對每個時序段中多個狀态及其跨段的轉移關系進行模組化，沿時間軸保留了來自原始資料的更多資訊。

上圖展示了一個預測網絡流量異常的演化狀态圖的示例，實線表示寫入流量，虛線表示讀取流量，紅色表示當天發生異常事件。(a) 可視化了四種識别出的狀态，而 (b) 呈現在四個不同的時間間隔（在(a)中标記的I，II，III，IV）的演化狀态圖。 從圖中所示的案例可以看出，當發生異常事件時，狀态轉換（＃2→＃16）和（＃2→＃8）在時間I上更加頻繁。 同樣，狀态轉換（＃2→＃8）和（＃8→＃23）在時間II處很明顯。 這些轉變表明，寫入和讀取流量的不平衡（狀态8和狀态16）或流量下降（狀态23）将導緻網絡異常。 在時間III，在此期間未發生異常，可以看到狀态主要停留在＃2中。 然後在下一個時刻IV出現異常。 是以可以看到狀态轉換＃2→＃16的明顯增加。

時序演化狀态圖網絡

當時序轉化為動态圖·演化狀态圖之後，如何對這種動态圖結構進行模組化分析變為了主要的問題，受圖神經網絡（GNN）的啟發[7]，該文的研究者設計了兩種機制來對演化狀态圖進行模組化與分析，即局部資訊聚合和時間圖傳播。

上圖說明了所提出的演化狀态圖網絡（EvoNet）的總體結構。對于給定的時間序列以及事件

，該文首先識别每個分段

的狀态并構造演化狀态圖

。接下來，該文定義表示向量

對于圖中每個節點的資訊進行編碼，并定義表示向量

用于編碼整個圖的資訊。

基于此，如圖a，EvoNet通過消息傳遞網絡（message passing）[8]來聚合局部的結構資訊：

并使用循環神經網絡[9] 進一步傳播時間上的節點以及圖的資訊：

然後，EvoNet将學習到的特征表示

應用于下遊的時序任務。具體的推導邏輯大家可以從原文[1]中擷取，這裡不做過多闡述。

特别的，在進行時間上資訊聚合的操作中，該研究者們提出在點到點模組化的同時，還應關注點到圖的影響，即時序的演化不僅僅與狀态與狀态之間的轉變有關，狀态與整個時序片段之間的關系也有影響。是以，如圖b，作者們采用層次循環神經網絡機制，捕捉節點級别資訊與圖級别資訊随時間的影響，通過有時間注意力機制（temporal attention）量化不同時間位置上影響的權重：

實驗結果

文章對來自Kaggle的兩個公共資料集，和來自國家電網、中國電信、阿裡雲的三個真實世界資料集進行時間序列事件預測任務。實驗結果如下表所示：

工業落地實踐

該文提出的算法已落地為阿裡雲·SLS的時間序列的異常檢測服務。該方法可以提供大規模秒級别的實時異常檢測，并給出異常判斷初步解釋，輔助于運維、營運、研發等諸多場景。詳情請見

《阿裡雲SLS·機器學習服務》

。下面展現該文所列舉的一個例子：

如圖所示，圖a 展現了雲服務主機（ECS）監控下的秒級CPU使用率。紅色表示1分鐘内有異常。這個例子中設定了10個狀态以建構演化狀态圖，并可視化了每個時間位置的時間注意力分數。

1.時間注意機制的有效性：如圖b所示，熱力圖可視化了不同時間位置的注意力得分。我們可以看到注意分數成功地突出了圖a中異常的位置。

2.演化狀态圖的可解釋性：如圖c-e所示，我們可以看到，時間位置I的圖中有一個主要的轉移＃2→＃4→＃0，而在時間位置II的圖中則是＃3→＃5。請注意，II之後立即發生異常。當我們在時間軸上彙總所有演化狀态圖時（圖d）可以發現，過渡＃2→＃4→＃0是圖中的主要路徑，而＃3→＃5是次要路徑。這些觀察結果表明，間隔II中發生的轉移＃3→＃5是異常的。

如圖e所可視化的不同狀态的平均曲線，可以看到，轉移＃2→＃4→＃0表示服務程序，即CPU使用率從0.25上升到0.75，并在保持一段時間後下降。相反，轉移＃3→＃5表示CPU使用率上升到0.5，然後立即下降。這些觀察結果表明，這種異常可能是由CPU的故障引起的。

Reference

[1] Wenjie, H; Yang, Y; Ziqiang, C; Carl, Y and Xiang, R, 2021, Time-Series Event Prediction with Evolutionary State Graph, In WSDM, 2021

[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 multisensor 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 neural networks for structured representations and fast inference. In _NIPS’16_, 2946–2954.

[6]  Pierre Ailliot and Valerie Monbet. 2012. Markov-switching auto regressive models for wind time series. Environmental Modelling and Software 30 (2012), 92–101.

[7]  Peter Battaglia, Jessica BHamrick, Victor Bapst, Alvaro Sanchezgonzalez, Vinicius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. 2018. Relational inductive biases, deep learning, and graph networks. arXiv: Learning (2018).

[8]  JustinGilmer,SamuelSSchoenholz,PatrickFRiley,OriolVinyals,andGeorgeEDahl. 2017. Neural Message Passing for Quantum Chemistry. ICML (2017)

[9]  Yoshua Bengio, Patrice Y Simard, and Paolo Frasconi. 1994. Learning long-term dependencies with gradient descent is difficult. TNNLS 5, 2 (1994)

聯系我們

糾錯或者幫助文檔以及最佳實踐貢獻，請聯系：笃林

問題咨詢或方法交流請加釘釘群：