基于相關(guān)性的多維時(shí)序數(shù)據(jù)異常溯源方法

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

哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150000

近年來(lái)我國(guó)制造業(yè)持續(xù)快速發(fā)展。工業(yè)互聯(lián)網(wǎng)的智能工廠(chǎng)已經(jīng)積累并正在產(chǎn)生大量的工業(yè)時(shí)序數(shù)據(jù)。通過(guò)對(duì)基于采集時(shí)間點(diǎn)的多維時(shí)間序列數(shù)據(jù)的分析和挖掘，能夠?qū)ο到y(tǒng)的運(yùn)行狀態(tài)進(jìn)行控制、分析、決策和規(guī)劃[1]，形成了有效的工業(yè)知識(shí)產(chǎn)生、提取、應(yīng)用的積極循環(huán)，進(jìn)而實(shí)現(xiàn)了對(duì)工業(yè)大數(shù)據(jù)的智能分析[2]。

通過(guò)分析傳感器組傳回?cái)?shù)據(jù)可以檢測(cè)出工業(yè)系統(tǒng)及設(shè)備中存在的顯性或隱性異常，例如產(chǎn)品質(zhì)量缺陷、精度缺失、設(shè)備故障、加工失效、性能下降、環(huán)境突變等[1]。這些故障給企業(yè)帶來(lái)了大量消耗損失。為了降低危害，工業(yè)系統(tǒng)和設(shè)備會(huì)加入一套故障處理方案，由系統(tǒng)運(yùn)維人員或自動(dòng)運(yùn)維程序?qū)?shù)據(jù)中顯示的異常狀態(tài)進(jìn)行判斷并介入故障排查[3]。但通過(guò)調(diào)研發(fā)現(xiàn)，在很長(zhǎng)一段時(shí)間中，工業(yè)生產(chǎn)的故障診斷存在著以下一些問(wèn)題：

（1）工業(yè)時(shí)序數(shù)據(jù)具有數(shù)據(jù)量大、時(shí)效性強(qiáng)、模式多樣的特點(diǎn)。傳統(tǒng)的單維靜態(tài)數(shù)據(jù)處理方法存在一定局限性。

（2）利用工業(yè)時(shí)序數(shù)據(jù)判別異常類(lèi)型為系統(tǒng)故障抑或是錯(cuò)誤數(shù)據(jù)存在困難。

（3）工業(yè)時(shí)序數(shù)據(jù)可能存在模式相關(guān)，這是工業(yè)系統(tǒng)的物理屬性決定的。但數(shù)據(jù)可能僅是數(shù)學(xué)上表現(xiàn)出相關(guān)性，可能在整體上并不能表現(xiàn)出相關(guān)關(guān)系。

為了能夠減少工業(yè)生產(chǎn)中將數(shù)據(jù)異常錯(cuò)誤歸類(lèi)造成損失，本研究提出了一種基于時(shí)序相關(guān)環(huán)模型的異常來(lái)源檢測(cè)算法。本文的創(chuàng)新點(diǎn)包括：

（1）給出區(qū)別于傳統(tǒng)單維數(shù)據(jù)的基于圖論的多維時(shí)序相關(guān)性模型，將相關(guān)性分析放在圖中進(jìn)行解釋?zhuān)诓皇?yán)謹(jǐn)性的同時(shí)更加直觀(guān)。

（2）設(shè)計(jì)了一種在時(shí)序相關(guān)圖中提取最大時(shí)序相關(guān)環(huán)的方法，對(duì)異常成因進(jìn)行溯源。利用序列間的相關(guān)關(guān)系得到相關(guān)序列集合，通過(guò)在相關(guān)序列中定量分析序列相關(guān)性對(duì)異常來(lái)源進(jìn)行分類(lèi)。

（3）在實(shí)際的多維工業(yè)數(shù)據(jù)中，通過(guò)與基準(zhǔn)算法進(jìn)行比較，本文方法在準(zhǔn)確率、召回率以及穩(wěn)定性上高于基準(zhǔn)算法。

1 相關(guān)工作

靜態(tài)數(shù)據(jù)的異常檢測(cè)（anomaly detection）研究相對(duì)起步較早。現(xiàn)在靜態(tài)異常檢測(cè)已經(jīng)被應(yīng)用到網(wǎng)絡(luò)入侵檢測(cè)、工業(yè)探傷、星云探測(cè)等多學(xué)科多領(lǐng)域，文獻(xiàn)[4]識(shí)別網(wǎng)絡(luò)中流量的特定異常分布模式，以確認(rèn)監(jiān)控的計(jì)算機(jī)是否將敏感數(shù)據(jù)發(fā)送給未經(jīng)授權(quán)的其他計(jì)算機(jī)。文獻(xiàn)[5]利用心電圖中的正常模式進(jìn)行匹配，若失配則認(rèn)為對(duì)應(yīng)患者的心臟存在病變。這是利用已知數(shù)據(jù)中的特征或固有統(tǒng)計(jì)模型挖掘數(shù)據(jù)中不符合該特征或模型的點(diǎn)或片段檢測(cè)異常。

利用機(jī)器學(xué)習(xí)的模型進(jìn)行異常檢測(cè)已有很多研究，其中基于分類(lèi)和基于聚類(lèi)的方法得到了廣泛應(yīng)用?；诙囝?lèi)別分類(lèi)的異常檢測(cè)技術(shù)假定訓(xùn)練數(shù)據(jù)包含屬于多個(gè)正常類(lèi)別的標(biāo)記實(shí)例[6]。這種異常檢測(cè)技術(shù)可以學(xué)習(xí)得到一個(gè)多維分類(lèi)器，以區(qū)分每個(gè)正常分類(lèi)與其余分類(lèi)。如果一個(gè)測(cè)試實(shí)例沒(méi)有被任何分類(lèi)器歸類(lèi)為正常，則該測(cè)試實(shí)例被認(rèn)為是異常的?；诙诸?lèi)的異常檢測(cè)技術(shù)假定所有訓(xùn)練實(shí)例都只有一個(gè)類(lèi)標(biāo)簽。這類(lèi)方法有使用二分類(lèi)SVM（support vector machine）判別一個(gè)正常模式的邊界[7]，也有利用Fisher 核做判別式指導(dǎo)分類(lèi)器劃分的方法[8]?；诰垲?lèi)的異常檢測(cè)技術(shù)有：正常數(shù)據(jù)實(shí)例屬于數(shù)據(jù)中的一個(gè)聚類(lèi)，而異常實(shí)例不屬于任何聚類(lèi)。基于上述假設(shè)的技術(shù)將已知的基于聚類(lèi)的算法應(yīng)用于數(shù)據(jù)集，并將不屬于任何聚類(lèi)的任何數(shù)據(jù)實(shí)例聲明為異常[9]。正常數(shù)據(jù)實(shí)例位于其最接近的聚簇質(zhì)心附近，而異常則離其最接近的聚簇質(zhì)心很遠(yuǎn)?；谏鲜黾僭O(shè)的技術(shù)包括兩個(gè)步驟。在第一步中，使用聚類(lèi)算法對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)。在第二步中，對(duì)于每個(gè)數(shù)據(jù)實(shí)例，將其到其最接近的群集質(zhì)心的距離計(jì)算為其異常分?jǐn)?shù)[10]。注意，如果數(shù)據(jù)形式中的異常本身是聚簇的，則上述技術(shù)將無(wú)法檢測(cè)到此類(lèi)異常。

近些年數(shù)據(jù)的時(shí)序?qū)傩圆粩嗍艿街匾?，基于時(shí)序數(shù)據(jù)的異常檢測(cè)方法也得到了很大發(fā)展。在時(shí)序異常檢測(cè)研究中，對(duì)于異常的檢測(cè)對(duì)象而言，時(shí)序數(shù)據(jù)異常主要有毛刺異常（glitch）、點(diǎn)異常（abnormality）和區(qū)間異常（interval abnormality）三種[11]；在時(shí)序異常檢測(cè)方法上以機(jī)器學(xué)習(xí)方法為主，包括基于聚類(lèi)和基于分類(lèi)器的算法?；诰垲?lèi)的方法將正?；虍惓?shù)據(jù)點(diǎn)聚集并盡可能將二者的距離增加[12]?；诜诸?lèi)器的方法利用確定特征方程的系數(shù)得到正常和異常數(shù)據(jù)的分界。文獻(xiàn)[13]利用EM（expectation-maximum）算法做正常數(shù)據(jù)與異常預(yù)測(cè)數(shù)據(jù)的多分類(lèi)器。文獻(xiàn)[14]利用隱馬爾科夫方法發(fā)現(xiàn)偏序序列中各個(gè)正常點(diǎn)或正常子序列所具有的特征，從而將異常點(diǎn)或異常子序列檢測(cè)并標(biāo)記處理。文獻(xiàn)[15]利用速度約束的概念，配合最大似然估計(jì)得到正常情形下的數(shù)據(jù)值，以此檢測(cè)異常數(shù)據(jù)并進(jìn)行修復(fù)。在已有的異常檢測(cè)方法中，基于機(jī)器學(xué)習(xí)的方法往往開(kāi)銷(xiāo)較大；基于統(tǒng)計(jì)模型的方法要求待測(cè)數(shù)據(jù)的分布模式已知，應(yīng)用存在局限；而約束方法在挖掘較長(zhǎng)區(qū)間的異常模式時(shí)受到計(jì)算方法的限制不能很好地使用。

2 研究?jī)?nèi)容介紹

在一個(gè)工業(yè)系統(tǒng)中，異常（anomaly）一般被定義為數(shù)據(jù)中不滿(mǎn)足常態(tài)、約束、規(guī)則、給定模型的不尋常數(shù)據(jù)值或模式[16]。工業(yè)時(shí)序數(shù)據(jù)異常的溯源可能有兩種：一種是指工業(yè)系統(tǒng)喪失其規(guī)定性能的狀態(tài)，稱(chēng)之為故障；一種是指?jìng)鞲衅魇ъ`造成正確數(shù)據(jù)出現(xiàn)偏差，稱(chēng)之為錯(cuò)誤數(shù)據(jù)。二者都可以引發(fā)數(shù)據(jù)異常，但造成的后果完全不同。

2.1 基本定義

本文的問(wèn)題定義基于已有研究文獻(xiàn)[17]。下面給出一些便于理解本文算法的關(guān)鍵基本定義：

定義1（時(shí)間序列）時(shí)間序列是由傳感器采樣的一系列連續(xù)的數(shù)據(jù)點(diǎn)。一條長(zhǎng)度為N的時(shí)間序列表示為，其中每個(gè)序列點(diǎn)表示為一個(gè)二元組，xi是一個(gè)實(shí)數(shù)值，ti是時(shí)間記錄點(diǎn)。對(duì)于任意的整數(shù)i、j，若i

定義2（多維時(shí)間序列）S是一個(gè)包含K條具有相同時(shí)間點(diǎn)集合T的時(shí)間序列集合，記為S={S1,S2,…,SK}。S稱(chēng)為K維時(shí)間序列。

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

定義4（時(shí)序相關(guān)圖）設(shè)有圖G=(V,E)，V={v|v∈SK}，E={e|e∈(Rij=1)}，則圖G被稱(chēng)為時(shí)序相關(guān)圖。

2.2 方法概述

由研究背景所述，現(xiàn)有時(shí)序異常檢測(cè)算法僅能輸出發(fā)生了異常和異常的表征，無(wú)法對(duì)異常的來(lái)源是故障還是錯(cuò)誤數(shù)據(jù)進(jìn)行判斷。由此，首先對(duì)待檢測(cè)時(shí)間序列組的線(xiàn)性相關(guān)關(guān)系進(jìn)行挖掘，進(jìn)而在圖論的思想下設(shè)計(jì)異常檢測(cè)算法，達(dá)到對(duì)異常數(shù)據(jù)的來(lái)源進(jìn)行識(shí)別的目的。

本文的時(shí)間序列異常來(lái)源檢測(cè)的步驟如圖1 所示，主要包含異常相關(guān)模型訓(xùn)練階段（簡(jiǎn)稱(chēng)為訓(xùn)練階段）和異常來(lái)源判別檢測(cè)階段（簡(jiǎn)稱(chēng)為檢測(cè)階段）。

Fig.1 Step of time series anomaly source detection圖1 時(shí)間序列異常來(lái)源檢測(cè)步驟

訓(xùn)練階段：該階段包含兩部分，數(shù)據(jù)預(yù)處理和相關(guān)性計(jì)算。在數(shù)據(jù)預(yù)處理階段需要對(duì)各序列數(shù)據(jù)的單位和量綱進(jìn)行標(biāo)準(zhǔn)化。這里規(guī)定，訓(xùn)練階段程序接收并分析的多維時(shí)序數(shù)據(jù)的標(biāo)簽標(biāo)注都為正確，經(jīng)調(diào)研表明工業(yè)生產(chǎn)的絕大多數(shù)時(shí)間產(chǎn)生的序列數(shù)據(jù)都是正常運(yùn)轉(zhuǎn)狀態(tài)的，正確的工業(yè)多維時(shí)序數(shù)據(jù)獲取難度不大。

在得到預(yù)處理的數(shù)據(jù)后，將在序列組內(nèi)計(jì)算序列間的相關(guān)性關(guān)系，得到相關(guān)系數(shù)矩陣。之后將時(shí)序相關(guān)關(guān)系矩陣表達(dá)為一個(gè)時(shí)序相關(guān)圖，在圖中發(fā)掘出所有時(shí)序相關(guān)環(huán)并輸出對(duì)應(yīng)的相關(guān)序列集，完成對(duì)該多維時(shí)序數(shù)據(jù)的訓(xùn)練。

檢測(cè)階段：該階段將對(duì)輸入的帶有異常標(biāo)簽的相同類(lèi)型序列組通過(guò)之前得到的相關(guān)序列集分析每個(gè)存在異常的序列的異常來(lái)源，輸出異常的來(lái)源類(lèi)型，以指導(dǎo)工廠(chǎng)對(duì)異常情況進(jìn)行進(jìn)一步處理。

3 多維時(shí)序相關(guān)性計(jì)算方法

在工業(yè)場(chǎng)景下的多維時(shí)間序列數(shù)據(jù)中，處于同一個(gè)系統(tǒng)或具有物理關(guān)系的序列間往往呈現(xiàn)出較強(qiáng)的相似性，這里定義序列相關(guān)性來(lái)定量計(jì)算序列之間的相似程度?；诙嗑S序列相關(guān)性的異常來(lái)源檢測(cè)方法的整個(gè)過(guò)程如圖1 所示。

3.1 建立時(shí)序相關(guān)圖

得到時(shí)序相關(guān)關(guān)系矩陣后，如果將傳感器組的K維序列數(shù)據(jù)（也就是矩陣中的維度）作為節(jié)點(diǎn)，將序列間滿(mǎn)足相關(guān)關(guān)系閾值的關(guān)系作為邊，可以得到一個(gè)時(shí)序相關(guān)圖G。進(jìn)而利用時(shí)序相關(guān)圖做進(jìn)一步的分析，把相關(guān)關(guān)系利用圖模型聯(lián)系起來(lái)。

3.2 構(gòu)建時(shí)序相關(guān)環(huán)

在以每條序列為頂點(diǎn)，每?jī)蓷l相關(guān)序列間形成一條邊的圖G中，構(gòu)成的連通圖可能有一個(gè)或多個(gè)，這些連通圖被稱(chēng)為圖G中的連通分量。即在一個(gè)工業(yè)系統(tǒng)中，時(shí)間序列的相關(guān)關(guān)系可能存在著很多個(gè)。由時(shí)序相關(guān)圖的概念，本文提出在時(shí)序相關(guān)圖G的各連通分量中尋找最大時(shí)序相關(guān)環(huán)C。某個(gè)時(shí)序相關(guān)圖的其中一個(gè)連通分量的樣例如圖2 所示（圖中點(diǎn)標(biāo)號(hào)為對(duì)應(yīng)序列號(hào)）。最大時(shí)序相關(guān)環(huán)的定義如下：

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

Fig.2 Connected component of time series correlation graph圖2 時(shí)序相關(guān)圖某連通分量

定理1每個(gè)時(shí)序相關(guān)圖G的連通分量CC中至多存在一個(gè)最大時(shí)序相關(guān)環(huán)。

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

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

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

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

定理2一條屬于FcEdge的邊必與對(duì)應(yīng)無(wú)向圖連通分量的支撐樹(shù)形成一個(gè)環(huán)。

證明設(shè)fcedge∈FcEdge，則fcedge的兩個(gè)頂點(diǎn)都在連通分量中，由連通圖支撐樹(shù)的定義可知，fcedge的這兩個(gè)頂點(diǎn)一定在支撐樹(shù)的頂點(diǎn)集合中出現(xiàn)。又因?yàn)橹螛?shù)任意兩點(diǎn)間必然存在一條路徑，則一定存在一個(gè)環(huán)，以fcedge的一個(gè)頂點(diǎn)為起始點(diǎn)，沿支撐樹(shù)中的一條路徑到達(dá)fcedge的另一個(gè)頂點(diǎn)，再沿fcedge回到起始點(diǎn)形成一個(gè)環(huán)。得證。

下一步需要在支撐樹(shù)中找到一條路徑，該路徑通過(guò)支撐樹(shù)的任意兩個(gè)葉節(jié)點(diǎn)和根節(jié)點(diǎn)。尋找該路徑的步驟見(jiàn)算法1。

算法1尋找支撐樹(shù)中的最長(zhǎng)路徑

在找到支撐樹(shù)中可以成環(huán)的最長(zhǎng)路徑后，對(duì)于還不屬于這個(gè)環(huán)的其他頂點(diǎn)unfindnode，需要對(duì)每個(gè)unfindnode進(jìn)行遍歷以確定是否可以將該點(diǎn)加入環(huán)以形成一個(gè)更大的環(huán)，稱(chēng)為環(huán)的擴(kuò)張。定理3 作為最大時(shí)序相關(guān)環(huán)的生成算法中的環(huán)擴(kuò)張算法的一個(gè)理論依據(jù)。

定理3在支撐樹(shù)中，若一個(gè)頂點(diǎn)不屬于現(xiàn)有的環(huán)的頂點(diǎn)集合，且該頂點(diǎn)與環(huán)的頂點(diǎn)集合中至少兩個(gè)頂點(diǎn)各自存在一條非樹(shù)邊，則該頂點(diǎn)加入環(huán)后可以將環(huán)的長(zhǎng)度增加。

證明設(shè)存在一棵支撐樹(shù)T以及一個(gè)環(huán)頂點(diǎn)集合CycleNode，一個(gè)不屬于CycleNode的頂點(diǎn)v。如果在CycleNode中存在著兩個(gè)頂點(diǎn)c1、c2，且(v,c1)∈FcEdge，(v,c2)∈FcEdge。又因?yàn)榇嬖?c1,c2)∈CycleNode，則v、c1、c2形成了一個(gè)三角形。由三角形兩邊之和大于第三邊可知，v加入環(huán)后環(huán)的長(zhǎng)度增加，且環(huán)沒(méi)有斷裂，即環(huán)的結(jié)構(gòu)是完整的。因此v的加入可以增加環(huán)的長(zhǎng)度。

接下來(lái)用偽代碼給出環(huán)擴(kuò)張算法的實(shí)現(xiàn)步驟：

算法2環(huán)擴(kuò)張算法

示例說(shuō)明：由上文中敘述的支撐樹(shù)可以得到支撐樹(shù)中由根節(jié)點(diǎn)的鄰節(jié)點(diǎn)作為起始點(diǎn)，對(duì)應(yīng)葉節(jié)點(diǎn)生成的路徑，如例子可知其中的最長(zhǎng)路徑為28-34-29-31-24，經(jīng)過(guò)擴(kuò)張算法后，CycleNode={23,24,25,26,27,28,29,30,31,32,33,34,35,36}，為所求的時(shí)間序列相關(guān)集合CS。

3.3 多維時(shí)間序列異常來(lái)源檢測(cè)

在工業(yè)多維時(shí)間序列的數(shù)據(jù)分析中，由于單列異常檢測(cè)無(wú)法很好區(qū)分故障和錯(cuò)誤數(shù)據(jù)，本文提出了利用多維時(shí)間序列間相關(guān)性進(jìn)行異常檢測(cè)溯源，算法3 即為基于相關(guān)性的異常檢測(cè)溯源算法。

算法3 多維時(shí)序數(shù)據(jù)異常來(lái)源檢測(cè)

3.4 算法效率分析

本節(jié)對(duì)上述算法進(jìn)行效率分析，上述算法主要的時(shí)間和空間開(kāi)銷(xiāo)產(chǎn)生于創(chuàng)建時(shí)序相關(guān)圖和尋找最大時(shí)序相關(guān)環(huán)兩個(gè)步驟。

3.4.1 創(chuàng)建時(shí)序相關(guān)圖

創(chuàng)建時(shí)序相關(guān)圖時(shí)，設(shè)計(jì)算的時(shí)間序列長(zhǎng)度為n，序列數(shù)量為K。則時(shí)序相關(guān)圖的計(jì)算需要計(jì)算K維序列中每?jī)闪械南嚓P(guān)性，在計(jì)算的過(guò)程中對(duì)序列中的每個(gè)點(diǎn)有一次遍歷，總的時(shí)間復(fù)雜度為O(n×K2)。

3.4.2 尋找最大時(shí)序相關(guān)環(huán)

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

4 實(shí)驗(yàn)與結(jié)果

4.1 度量標(biāo)準(zhǔn)

本文的目的是追溯并區(qū)分異常序列的異常來(lái)源，即該異常屬于系統(tǒng)故障還是錯(cuò)誤數(shù)據(jù)。將系統(tǒng)故障作為正例，錯(cuò)誤數(shù)據(jù)作為反例。設(shè)每個(gè)時(shí)間序列組為一個(gè)實(shí)例單位，實(shí)驗(yàn)結(jié)果可以分為4 類(lèi)，分別是：

（1）預(yù)測(cè)正，實(shí)際正（true positives，TP）；

（2）預(yù)測(cè)正，實(shí)際負(fù)（false positives，F(xiàn)P）；

（3）預(yù)測(cè)負(fù)，實(shí)際正（false negatives，F(xiàn)N）；

（4）預(yù)測(cè)負(fù)，實(shí)際負(fù)（true negatives，TN）。

利用以上4 個(gè)分類(lèi)給出計(jì)算公式：

準(zhǔn)確率公式：

召回率公式：

實(shí)際上計(jì)算時(shí)還會(huì)出現(xiàn)算法判斷不存在錯(cuò)誤數(shù)據(jù)的情況，該情況是利用單維時(shí)序異常檢測(cè)算法造成的，在計(jì)算準(zhǔn)確率和召回率時(shí)不加入計(jì)算。

4.2 數(shù)據(jù)集

本文應(yīng)用國(guó)內(nèi)某大型火力發(fā)電廠(chǎng)的某發(fā)電機(jī)組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。本文在研究了電廠(chǎng)發(fā)電機(jī)組的某型號(hào)引風(fēng)機(jī)連續(xù)6 個(gè)月的數(shù)據(jù)后，將其中連續(xù)某三個(gè)月的歷史采樣數(shù)據(jù)作為訓(xùn)練集。該設(shè)備共有84 個(gè)傳感器，分別檢測(cè)引風(fēng)機(jī)的軸應(yīng)力、軸溫、腔內(nèi)氣體溫度、繞組線(xiàn)圈電流及溫度等。傳感器每8 s 記錄一次數(shù)據(jù)，一共記錄了84 列數(shù)據(jù)。每列時(shí)間序列數(shù)據(jù)經(jīng)預(yù)處理方法去除無(wú)效或低質(zhì)量數(shù)據(jù)后，最終采用37 列總計(jì)74 萬(wàn)個(gè)時(shí)間點(diǎn)上數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

4.3 對(duì)照算法

在實(shí)驗(yàn)中實(shí)現(xiàn)了本文算法。為突出該算法相比其他算法在異常來(lái)源檢測(cè)上的突出表現(xiàn)，本文采用兩種算法與該算法做對(duì)照：

（1）基于約束的異常檢測(cè)方法。通過(guò)檢測(cè)異常值的波動(dòng)，檢測(cè)異常并對(duì)故障或錯(cuò)誤數(shù)據(jù)進(jìn)行分類(lèi)。

（2）基于聚類(lèi)的異常檢測(cè)算法。通過(guò)提取時(shí)間序列中的特征，區(qū)分故障或錯(cuò)誤數(shù)據(jù)。即對(duì)潛在相關(guān)序列進(jìn)行聚類(lèi)，找到聚類(lèi)中心和搜索半徑并確定每條序列所在的分類(lèi)。

4.4 方法有效性分析

本文分別從測(cè)試序列組的序列維數(shù)總數(shù)、測(cè)試集規(guī)模和訓(xùn)練集規(guī)模方面對(duì)上述三種算法檢測(cè)性能進(jìn)行了測(cè)試，測(cè)試結(jié)果如下。

4.4.1 序列維數(shù)的影響

實(shí)驗(yàn)測(cè)試了序列維數(shù)從6 列提高到37 列的過(guò)程中，本文提出的最大相關(guān)環(huán)算法（cycle）和兩種對(duì)比算法（單列檢測(cè)算法fundamental 和k聚類(lèi)算法kmeans）的準(zhǔn)確率和召回率。由圖4（a）、圖4（b）可以看出，雖然相較之下k-means 算法的準(zhǔn)確率在特定條件下表現(xiàn)較好，但本文算法的準(zhǔn)確率、召回率以及不同維度下的穩(wěn)定性都略高于k-means 算法，其中準(zhǔn)確率保持在87%左右，較k-means 算法提升約0.09；召回率保持在86%左右，平均較k-means 算法提升0.11 左右。k-means算法的召回率能夠隨著維度上升有所提高是因?yàn)樾蛄芯S度升高使數(shù)據(jù)量增加，減少了kmeans 算法陷入局部最優(yōu)解的可能性。但是因?yàn)楸疚乃惴ㄝ^k-means 算法多利用了序列間相關(guān)性這一特征，使該算法較k-means 的準(zhǔn)確率和召回率都略高，也更加穩(wěn)定。這里要說(shuō)明一下，單列檢測(cè)算法幾乎無(wú)法判斷出異常的來(lái)源，因此后續(xù)的測(cè)試將不再單獨(dú)介紹該算法的效率。

4.4.2 測(cè)試集規(guī)模的影響

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

Fig.4 Effectiveness analysis in experiment圖4 實(shí)驗(yàn)有效性分析圖

Fig.5 Efficiency analysis in experiment圖5 實(shí)驗(yàn)效率分析圖

4.4.3 訓(xùn)練集規(guī)模的影響

不同訓(xùn)練集規(guī)模對(duì)算法準(zhǔn)確率和召回率的影響如圖4（e）、圖4（f）所示?？梢?jiàn)隨著訓(xùn)練集規(guī)模的提升，本文算法和k-means 算法的準(zhǔn)確率都有所上升，且本文算法的準(zhǔn)確率一直較k-means 算法高出0.03至0.05。而隨著訓(xùn)練集規(guī)模的上升，二者的召回率都有所下降。但從兩圖仍可以看出，在訓(xùn)練集的規(guī)模增加或減少時(shí)，本文算法的穩(wěn)定性都優(yōu)于k-means算法。

4.4.4 算法速率比較

圖5（a）～（c）是在上述變量的場(chǎng)景下運(yùn)行時(shí)間的比較。從中可以看出本文算法的運(yùn)行時(shí)間遠(yuǎn)小于kmeans 算法。雖然本文算法在訓(xùn)練階段需要一些時(shí)間，但利用訓(xùn)練步驟得到的環(huán)頂點(diǎn)集合可以使異常來(lái)源檢測(cè)算法在0.1 s 內(nèi)輸出結(jié)果。該算法因?yàn)椴恍枰诿看螜z測(cè)時(shí)對(duì)原數(shù)據(jù)進(jìn)行額外計(jì)算而在流數(shù)據(jù)處理上較k-means算法有更大優(yōu)勢(shì)。

5 總結(jié)

本文研究了基于統(tǒng)計(jì)相關(guān)性方法的異常檢測(cè)問(wèn)題，提出了解決異常來(lái)源檢測(cè)問(wèn)題的框架結(jié)構(gòu)，利用實(shí)際遇到的問(wèn)題進(jìn)行示例分析，分別介紹了多維時(shí)間序列相關(guān)性計(jì)算算法和多維時(shí)序相關(guān)性的最大時(shí)序相關(guān)環(huán)算法以及基于前兩種算法的多維時(shí)序異常來(lái)源檢測(cè)算法。本文在實(shí)驗(yàn)部分說(shuō)明了該方法的穩(wěn)定性、運(yùn)行速度和性能都較傳統(tǒng)的樸素基于機(jī)器學(xué)習(xí)的異常檢測(cè)算法有所提高。