基于相關性的多維時序數據異常溯源方法

王沐賢，丁小歐，王宏志，李建中

哈爾濱工業大學 計算機科學與技術學院，哈爾濱150000

近年來我國制造業持續快速發展。工業互聯網的智能工廠已經積累并正在產生大量的工業時序數據。通過對基于采集時間點的多維時間序列數據的分析和挖掘，能夠對系統的運行狀態進行控制、分析、決策和規劃[1]，形成了有效的工業知識產生、提取、應用的積極循環，進而實現了對工業大數據的智能分析[2]。

通過分析傳感器組傳回數據可以檢測出工業系統及設備中存在的顯性或隱性異常，例如產品質量缺陷、精度缺失、設備故障、加工失效、性能下降、環境突變等[1]。這些故障給企業帶來了大量消耗損失。為了降低危害，工業系統和設備會加入一套故障處理方案，由系統運維人員或自動運維程序對數據中顯示的異常狀態進行判斷并介入故障排查[3]。但通過調研發現，在很長一段時間中，工業生產的故障診斷存在著以下一些問題：

（1）工業時序數據具有數據量大、時效性強、模式多樣的特點。傳統的單維靜態數據處理方法存在一定局限性。

（2）利用工業時序數據判別異常類型為系統故障抑或是錯誤數據存在困難。

（3）工業時序數據可能存在模式相關，這是工業系統的物理屬性決定的。但數據可能僅是數學上表現出相關性，可能在整體上并不能表現出相關關系。

為了能夠減少工業生產中將數據異常錯誤歸類造成損失，本研究提出了一種基于時序相關環模型的異常來源檢測算法。本文的創新點包括：

（1）給出區別于傳統單維數據的基于圖論的多維時序相關性模型，將相關性分析放在圖中進行解釋，在不失去嚴謹性的同時更加直觀。

（2）設計了一種在時序相關圖中提取最大時序相關環的方法，對異常成因進行溯源。利用序列間的相關關系得到相關序列集合，通過在相關序列中定量分析序列相關性對異常來源進行分類。

（3）在實際的多維工業數據中，通過與基準算法進行比較，本文方法在準確率、召回率以及穩定性上高于基準算法。

1 相關工作

靜態數據的異常檢測（anomaly detection）研究相對起步較早。現在靜態異常檢測已經被應用到網絡入侵檢測、工業探傷、星云探測等多學科多領域，文獻[4]識別網絡中流量的特定異常分布模式，以確認監控的計算機是否將敏感數據發送給未經授權的其他計算機。文獻[5]利用心電圖中的正常模式進行匹配，若失配則認為對應患者的心臟存在病變。這是利用已知數據中的特征或固有統計模型挖掘數據中不符合該特征或模型的點或片段檢測異常。

利用機器學習的模型進行異常檢測已有很多研究，其中基于分類和基于聚類的方法得到了廣泛應用。基于多類別分類的異常檢測技術假定訓練數據包含屬于多個正常類別的標記實例[6]。這種異常檢測技術可以學習得到一個多維分類器，以區分每個正常分類與其余分類。如果一個測試實例沒有被任何分類器歸類為正常，則該測試實例被認為是異常的。基于二分類的異常檢測技術假定所有訓練實例都只有一個類標簽。這類方法有使用二分類SVM（support vector machine）判別一個正常模式的邊界[7]，也有利用Fisher 核做判別式指導分類器劃分的方法[8]。基于聚類的異常檢測技術有：正常數據實例屬于數據中的一個聚類，而異常實例不屬于任何聚類。基于上述假設的技術將已知的基于聚類的算法應用于數據集，并將不屬于任何聚類的任何數據實例聲明為異常[9]。正常數據實例位于其最接近的聚簇質心附近，而異常則離其最接近的聚簇質心很遠。基于上述假設的技術包括兩個步驟。在第一步中，使用聚類算法對數據進行聚類。在第二步中，對于每個數據實例，將其到其最接近的群集質心的距離計算為其異常分數[10]。注意，如果數據形式中的異常本身是聚簇的，則上述技術將無法檢測到此類異常。

近些年數據的時序屬性不斷受到重視，基于時序數據的異常檢測方法也得到了很大發展。在時序異常檢測研究中，對于異常的檢測對象而言，時序數據異常主要有毛刺異常（glitch）、點異常（abnormality）和區間異常（interval abnormality）三種[11]；在時序異常檢測方法上以機器學習方法為主，包括基于聚類和基于分類器的算法。基于聚類的方法將正常或異常數據點聚集并盡可能將二者的距離增加[12]。基于分類器的方法利用確定特征方程的系數得到正常和異常數據的分界。文獻[13]利用EM（expectation-maximum）算法做正常數據與異常預測數據的多分類器。文獻[14]利用隱馬爾科夫方法發現偏序序列中各個正常點或正常子序列所具有的特征，從而將異常點或異常子序列檢測并標記處理。文獻[15]利用速度約束的概念，配合最大似然估計得到正常情形下的數據值，以此檢測異常數據并進行修復。在已有的異常檢測方法中，基于機器學習的方法往往開銷較大；基于統計模型的方法要求待測數據的分布模式已知，應用存在局限；而約束方法在挖掘較長區間的異常模式時受到計算方法的限制不能很好地使用。

2 研究內容介紹

在一個工業系統中，異常（anomaly）一般被定義為數據中不滿足常態、約束、規則、給定模型的不尋常數據值或模式[16]。工業時序數據異常的溯源可能有兩種：一種是指工業系統喪失其規定性能的狀態，稱之為故障；一種是指傳感器失靈造成正確數據出現偏差，稱之為錯誤數據。二者都可以引發數據異常，但造成的后果完全不同。

2.1 基本定義

本文的問題定義基于已有研究文獻[17]。下面給出一些便于理解本文算法的關鍵基本定義：

定義1（時間序列）時間序列是由傳感器采樣的一系列連續的數據點。一條長度為N的時間序列表示為，其中每個序列點表示為一個二元組，xi是一個實數值，ti是時間記錄點。對于任意的整數i、j，若i

定義2（多維時間序列）S是一個包含K條具有相同時間點集合T的時間序列集合，記為S={S1,S2,…,SK}。S稱為K維時間序列。

定義3（相關系數矩陣）在K維時間序列S的（默認長度為n，下同）時間序列組中，第k個時間序列表示為Sk={sk(1),sk(2),…,sk(n)}。在這個時間序列時間段中，在式（1）中定義相關系數矩陣，用于測量傳感器組S上第l時間段內K條序列的相關性，表示為SCM。

定義4（時序相關圖）設有圖G=(V,E)，V={v|v∈SK}，E={e|e∈(Rij=1)}，則圖G被稱為時序相關圖。

2.2 方法概述

由研究背景所述，現有時序異常檢測算法僅能輸出發生了異常和異常的表征，無法對異常的來源是故障還是錯誤數據進行判斷。由此，首先對待檢測時間序列組的線性相關關系進行挖掘，進而在圖論的思想下設計異常檢測算法，達到對異常數據的來源進行識別的目的。

本文的時間序列異常來源檢測的步驟如圖1 所示，主要包含異常相關模型訓練階段（簡稱為訓練階段）和異常來源判別檢測階段（簡稱為檢測階段）。

Fig.1 Step of time series anomaly source detection圖1 時間序列異常來源檢測步驟

訓練階段：該階段包含兩部分，數據預處理和相關性計算。在數據預處理階段需要對各序列數據的單位和量綱進行標準化。這里規定，訓練階段程序接收并分析的多維時序數據的標簽標注都為正確，經調研表明工業生產的絕大多數時間產生的序列數據都是正常運轉狀態的，正確的工業多維時序數據獲取難度不大。

在得到預處理的數據后，將在序列組內計算序列間的相關性關系，得到相關系數矩陣。之后將時序相關關系矩陣表達為一個時序相關圖，在圖中發掘出所有時序相關環并輸出對應的相關序列集，完成對該多維時序數據的訓練。

檢測階段：該階段將對輸入的帶有異常標簽的相同類型序列組通過之前得到的相關序列集分析每個存在異常的序列的異常來源，輸出異常的來源類型，以指導工廠對異常情況進行進一步處理。

3 多維時序相關性計算方法

在工業場景下的多維時間序列數據中，處于同一個系統或具有物理關系的序列間往往呈現出較強的相似性，這里定義序列相關性來定量計算序列之間的相似程度。基于多維序列相關性的異常來源檢測方法的整個過程如圖1 所示。

3.1 建立時序相關圖

得到時序相關關系矩陣后，如果將傳感器組的K維序列數據（也就是矩陣中的維度）作為節點，將序列間滿足相關關系閾值的關系作為邊，可以得到一個時序相關圖G。進而利用時序相關圖做進一步的分析，把相關關系利用圖模型聯系起來。

3.2 構建時序相關環

在以每條序列為頂點，每兩條相關序列間形成一條邊的圖G中，構成的連通圖可能有一個或多個，這些連通圖被稱為圖G中的連通分量。即在一個工業系統中，時間序列的相關關系可能存在著很多個。由時序相關圖的概念，本文提出在時序相關圖G的各連通分量中尋找最大時序相關環C。某個時序相關圖的其中一個連通分量的樣例如圖2 所示（圖中點標號為對應序列號）。最大時序相關環的定義如下：

定義5（最大時序相關環）在時序相關圖G的連通分量（connected component）CC=(V,E)，其中在|V|>2 中，若存在一條路徑C=(V′,E′)，使|V′|≤|V|(|V′|>2)，E′={e′|e′∈E且e′首尾相接}，且V-V′的點中找不到首尾相接的路徑或使已有路徑的邊增加，則路徑C被稱為最大時序相關環（maximum time series correlation cycle）。

Fig.2 Connected component of time series correlation graph圖2 時序相關圖某連通分量

定理1每個時序相關圖G的連通分量CC中至多存在一個最大時序相關環。

證明假設CC中存在兩個最大時序相關環C1、C2。如果C1、C2 存在重復路徑，則C1、C2 可以合并為一個更大的環C，C的頂點集合V=V1 ?V2-(V1 ?V2)，C的邊集合E=E1 ?E2-(E1 ?E2) ；如果C1、C2 沒有相交路徑，由題設，則C1、C2 分屬兩個不同的連通分量，與前提在同一連通分量CC中不符合。即CC中不可能存在兩個以上的最大時序相關環，得證。

可以看出在一個時序相關圖G中可以找到若干個連通分量，在每個連通分量CC中至多存在一個最大時序相關環C，它們包含的頂點總數的大小關系是|V(G)|≥|V({CC})|≥|V({C})|。每個最大時序相關環C表示一組時間序列相關關系。

下面介紹最大時序相關環的搜索算法。由定理1 可知，目標為找到一條在任意連通分量中經過每個點的路徑[18]。據此本文提出在每個連通分量CC中搜索一條支撐樹T的算法，將連通分量中的邊集合CCEdge劃分為：所有已知樹邊加入支撐樹邊集合TreeEdge以及所有已知非樹邊加入成環邊集合FcEdge，有CCEdge=TreeEdge?FcEdge。在生成支撐樹的過程中借鑒了最小生成樹中的prim 算法，最后得到的T表示成一個支撐樹邊的集合。圖3 即為圖2 中時序相關圖的連通分量生成的一棵支撐樹，這棵支撐樹只是其中的一種解，但同一連通分量生成的不同支撐樹最后計算出的最大相關環是唯一的。這時引出定理2，描述如何從一個支撐樹找到一個環結構。

Fig.3 Support tree of connected component in Fig.2圖3 由圖2 連通分量生成的支撐樹

定理2一條屬于FcEdge的邊必與對應無向圖連通分量的支撐樹形成一個環。

證明設fcedge∈FcEdge，則fcedge的兩個頂點都在連通分量中，由連通圖支撐樹的定義可知，fcedge的這兩個頂點一定在支撐樹的頂點集合中出現。又因為支撐樹任意兩點間必然存在一條路徑，則一定存在一個環，以fcedge的一個頂點為起始點，沿支撐樹中的一條路徑到達fcedge的另一個頂點，再沿fcedge回到起始點形成一個環。得證。

下一步需要在支撐樹中找到一條路徑，該路徑通過支撐樹的任意兩個葉節點和根節點。尋找該路徑的步驟見算法1。

算法1尋找支撐樹中的最長路徑

在找到支撐樹中可以成環的最長路徑后，對于還不屬于這個環的其他頂點unfindnode，需要對每個unfindnode進行遍歷以確定是否可以將該點加入環以形成一個更大的環，稱為環的擴張。定理3 作為最大時序相關環的生成算法中的環擴張算法的一個理論依據。

定理3在支撐樹中，若一個頂點不屬于現有的環的頂點集合，且該頂點與環的頂點集合中至少兩個頂點各自存在一條非樹邊，則該頂點加入環后可以將環的長度增加。

證明設存在一棵支撐樹T以及一個環頂點集合CycleNode，一個不屬于CycleNode的頂點v。如果在CycleNode中存在著兩個頂點c1、c2，且(v,c1)∈FcEdge，(v,c2)∈FcEdge。又因為存在(c1,c2)∈CycleNode，則v、c1、c2形成了一個三角形。由三角形兩邊之和大于第三邊可知，v加入環后環的長度增加，且環沒有斷裂，即環的結構是完整的。因此v的加入可以增加環的長度。

接下來用偽代碼給出環擴張算法的實現步驟：

算法2環擴張算法

示例說明：由上文中敘述的支撐樹可以得到支撐樹中由根節點的鄰節點作為起始點，對應葉節點生成的路徑，如例子可知其中的最長路徑為28-34-29-31-24，經過擴張算法后，CycleNode={23,24,25,26,27,28,29,30,31,32,33,34,35,36}，為所求的時間序列相關集合CS。

3.3 多維時間序列異常來源檢測

在工業多維時間序列的數據分析中，由于單列異常檢測無法很好區分故障和錯誤數據，本文提出了利用多維時間序列間相關性進行異常檢測溯源，算法3 即為基于相關性的異常檢測溯源算法。

算法3 多維時序數據異常來源檢測

3.4 算法效率分析

本節對上述算法進行效率分析，上述算法主要的時間和空間開銷產生于創建時序相關圖和尋找最大時序相關環兩個步驟。

3.4.1 創建時序相關圖

創建時序相關圖時，設計算的時間序列長度為n，序列數量為K。則時序相關圖的計算需要計算K維序列中每兩列的相關性，在計算的過程中對序列中的每個點有一次遍歷，總的時間復雜度為O(n×K2)。

3.4.2 尋找最大時序相關環

設一個K個頂點的時序相關圖G中可以劃分出N個連通分量CC，在每個連通分量中利用支撐樹搜索算法后再使用最大時序相關環搜索算法。算法的快慢與連通分量劃分相關，如果每個連通分量的頂點數都接近K/N，則支撐樹搜索算法的復雜度約為O(K2/N)；如果只有一個連通分量即G的K個頂點構成一個連通分量，則支撐樹搜索算法的復雜度約為O(K2)。在每棵支撐樹中搜索一個最大相關環的步驟中，在極限條件下即G的K個頂點構成一個連通分量，時間復雜度約為O(K3)。實際工業系統中，一個系統往往K的值較小；而K值較大的系統又往往可以劃分成多個內部相關性較強的子系統，因此時間復雜度的規模一般可以接受。

4 實驗與結果

4.1 度量標準

本文的目的是追溯并區分異常序列的異常來源，即該異常屬于系統故障還是錯誤數據。將系統故障作為正例，錯誤數據作為反例。設每個時間序列組為一個實例單位，實驗結果可以分為4 類，分別是：

（1）預測正，實際正（true positives，TP）；

（2）預測正，實際負（false positives，FP）；

（3）預測負，實際正（false negatives，FN）；

（4）預測負，實際負（true negatives，TN）。

利用以上4 個分類給出計算公式：

準確率公式：

召回率公式：

實際上計算時還會出現算法判斷不存在錯誤數據的情況，該情況是利用單維時序異常檢測算法造成的，在計算準確率和召回率時不加入計算。

4.2 數據集

本文應用國內某大型火力發電廠的某發電機組數據進行實驗。本文在研究了電廠發電機組的某型號引風機連續6 個月的數據后，將其中連續某三個月的歷史采樣數據作為訓練集。該設備共有84 個傳感器，分別檢測引風機的軸應力、軸溫、腔內氣體溫度、繞組線圈電流及溫度等。傳感器每8 s 記錄一次數據，一共記錄了84 列數據。每列時間序列數據經預處理方法去除無效或低質量數據后，最終采用37 列總計74 萬個時間點上數據進行實驗。

4.3 對照算法

在實驗中實現了本文算法。為突出該算法相比其他算法在異常來源檢測上的突出表現，本文采用兩種算法與該算法做對照：

（1）基于約束的異常檢測方法。通過檢測異常值的波動，檢測異常并對故障或錯誤數據進行分類。

（2）基于聚類的異常檢測算法。通過提取時間序列中的特征，區分故障或錯誤數據。即對潛在相關序列進行聚類，找到聚類中心和搜索半徑并確定每條序列所在的分類。

4.4 方法有效性分析

本文分別從測試序列組的序列維數總數、測試集規模和訓練集規模方面對上述三種算法檢測性能進行了測試，測試結果如下。

4.4.1 序列維數的影響

實驗測試了序列維數從6 列提高到37 列的過程中，本文提出的最大相關環算法（cycle）和兩種對比算法（單列檢測算法fundamental 和k聚類算法kmeans）的準確率和召回率。由圖4（a）、圖4（b）可以看出，雖然相較之下k-means 算法的準確率在特定條件下表現較好，但本文算法的準確率、召回率以及不同維度下的穩定性都略高于k-means 算法，其中準確率保持在87%左右，較k-means 算法提升約0.09；召回率保持在86%左右，平均較k-means 算法提升0.11 左右。k-means算法的召回率能夠隨著維度上升有所提高是因為序列維度升高使數據量增加，減少了kmeans 算法陷入局部最優解的可能性。但是因為本文算法較k-means 算法多利用了序列間相關性這一特征，使該算法較k-means 的準確率和召回率都略高，也更加穩定。這里要說明一下，單列檢測算法幾乎無法判斷出異常的來源，因此后續的測試將不再單獨介紹該算法的效率。

4.4.2 測試集規模的影響

本小節實驗了不同測試集規模對上述算法性能的影響。測試結果如圖4（c）、圖4（d）所示。從圖中可以看出，隨著測試集規模的增加，最大相關環算法和k-means 算法的準確率都有所提升，在某些測試集條件下k-means 的準確率可以達到甚至超過本文算法，但穩定性仍存在不足。而最大相關環算法的召回率則穩定優于k-means 算法。測試集規模增大后，本文算法的基于半監督的特性使該方法的準確率仍較優于k-means算法。

Fig.4 Effectiveness analysis in experiment圖4 實驗有效性分析圖

Fig.5 Efficiency analysis in experiment圖5 實驗效率分析圖

4.4.3 訓練集規模的影響

不同訓練集規模對算法準確率和召回率的影響如圖4（e）、圖4（f）所示。可見隨著訓練集規模的提升，本文算法和k-means 算法的準確率都有所上升，且本文算法的準確率一直較k-means 算法高出0.03至0.05。而隨著訓練集規模的上升，二者的召回率都有所下降。但從兩圖仍可以看出，在訓練集的規模增加或減少時，本文算法的穩定性都優于k-means算法。

4.4.4 算法速率比較

圖5（a）～（c）是在上述變量的場景下運行時間的比較。從中可以看出本文算法的運行時間遠小于kmeans 算法。雖然本文算法在訓練階段需要一些時間，但利用訓練步驟得到的環頂點集合可以使異常來源檢測算法在0.1 s 內輸出結果。該算法因為不需要在每次檢測時對原數據進行額外計算而在流數據處理上較k-means算法有更大優勢。

5 總結

本文研究了基于統計相關性方法的異常檢測問題，提出了解決異常來源檢測問題的框架結構，利用實際遇到的問題進行示例分析，分別介紹了多維時間序列相關性計算算法和多維時序相關性的最大時序相關環算法以及基于前兩種算法的多維時序異常來源檢測算法。本文在實驗部分說明了該方法的穩定性、運行速度和性能都較傳統的樸素基于機器學習的異常檢測算法有所提高。