基于改進離群算法的多元時間序列異常檢測

苑津莎，甘斌斌，李 中，萬 利，李 燦

(1.華北電力大學 電氣與電子工程學院，河北 保定 071003; 2.國網四川省電力有限公司樂山供電公司，四川 樂山 614000;3.國網湖北省電力有限公司武漢供電公司，武漢 430000)

0 引 言

異常檢測旨在檢測出與主體數據存在顯著差異的異常數據[1]，并挖掘出其中的信息價值。目前，異常檢測已被廣泛應用于金融、航天、醫療等諸多領域。這些領域中的數據集大多為具有時間性的多元時間序列數據，而多元時間序列具有海量、維數高、結構復雜且隨時間不斷變化等特點。因此，為了快速準確地檢測出異常數據，防止數據源的異常工作狀態造成惡劣影響，對多元時間序列進行異常檢測尤為重要。

國內外學者針對不同類型的數據集，提出了一些多元時間序列異常檢測的方法。LI J[2]提出了一種基于隱馬爾可夫模型框架的多元時間序列異常檢測方法；李海林[3]基于頻繁模式發現的時間序列異常檢測方法，克服了傳統異常檢測方法在增量式時間序列異常檢測中準確率低的問題；戴仙波[4]提出了一種基于改進高斯核函數的邊界網關協議異常檢測方法，提高了模型分類的準確率；WANG X[5]提出了一種自學習在線異常檢測算法，克服了時間序列的異常檢測中異常無法定位的問題；余立蘋[6]提出了一種基于高維數據流的異常檢測算法，解決了傳統算法精確度無法保證和計算時間過長的問題，實現了高維數據流的異常檢測；BREUNIG M M等[7]提出了基于密度完成異常檢測的方法，解決了子集密度不同所導致的混合錯誤問題；王欣[8]提出了兩階段的多元時間序列異常檢測方法，先利用K-means對數據聚類，再通過循環嵌套算法和剪枝規則快速地完成異常檢測。現有的多元時間序列異常檢測方法雖提高了算法效率，但準確率卻沒有得到很好地提高。

為此，文章提出一種基于改進離群算法的多元時間序列異常檢測方法。考慮多元時間序列的多個維度特征之間的相似性，基于最小距離度量改進傳統的離群點檢測方法，利用改進后離群算法對多元時間序列異常進行數值化表達，從而實現多元時間序列的異常檢測。運用該算法進行實驗驗證，結果表明該算法檢測性能良好。

1 基于最小距離的離群算法

1.1 主成分分析與最小距離度量

主成分分析(Principal Component Analysis,PCA)[9]作為一種常用的線性降維方法，其功能是將高維空間中的數據樣本映射到低維空間中。對于一個多元時間序列X=[x1,x2, …,xn]，可以表示成一個n×m的矩陣，即X=(xij)n×m。xij表示第i個時間節點的第j個維度觀測值，n和m分別表示多元時間序列的時間長度和觀測維度。

主成分分析首先需要計算多元時間序列多個觀測維度變量之間的協方差，得到協方差矩陣Sn×m，利用奇異值分解對協方差矩陣進行特征值和特征向量分解，得到按特征值大小排列的對角矩陣Vm×m=diag(λ1,λ2, ...,λm)和對應的特征矩陣Um×m=[u1,u2, ... ,um],如式(1)所示。

(1)

根據特征值的大小，選擇前h個特征向量構成特征空間，進而得到相應的主成分。對應的時間序列的特征為主成分，其計算式如式(2)所示。

Yn×h=Xn×mUm×h

(2)

式中：Yn×h為降維后的時間序列特征值。

dij=1- |cosθij|

(3)

式中：cosθij為第個i基向量和第j個基向量的夾角。

對于兩個多元時間序列，基于式(3)可計算前h個特征向量中任意兩個向量之間的夾角距離矩陣Dh×h=(dij)h×h。

基于最小距離矩陣Dh×h，最小距離度量方法與傳統Eros距離度量方法的思想一致，即找到一組匹配具有最小距離的最優解，并取得最小距離度量。該問題可歸納為一個線性規劃問題，目標函數如式(4)所示。

(4)

式中：(cij)h×h是決策變量矩陣，且當cij=1時，表示夾角距離矩陣元素dij參與最小距離度量。

該線性規劃問題為一個線性任務分配問題，選擇匈牙利算法[10]對其進行求解，目的是求得一個使總距離代價最小的決策變量矩陣，從而得到最終的最小距離度量dMEros=MEros(An1×m,Bn2×m,h)。

1.2 基于最小距離優化的局部離群因子算法

多元時間序列經過PCA進行特征表示后，樣本被映射為高維空間中的點群。由于數據源的穩定性，大部分的點都相對集中。基于該特點，局部離群因子(Local Outlier Factor，LOF)算法[11]通過定義LOF來描述每一個樣本的離群程度。不同于閾值的硬性劃分，對于給定含有n個樣本的集合以及預期離群樣本數k,LOF算法的任務是從集合中通過LOF挖掘出所有樣本中離群程度最顯著的k個樣本，實現異常點的檢測。基于最小距離優化的局部離群因子通過o點的k距離、o點的k距離鄰域、可達距離、局部可達密度四個概念來定義。

1)o點的k距離

定義數據集中樣本點o到任意點p的最小距離為dMEros(o,p)，樣本o點到以o為中心的第k個最鄰近樣本的距離為o點的k距離，記為dk(o)，其計算式如式(5)所示。

(5)

2)o點的k距離鄰域

對于數據集中的任意點o，數據集中所有到點o的距離不大于dk(o)的點的組成的集合，稱之為o點的k距離鄰域，記為Nk(o)，其計算式如式(6)所示。

Nk(o)={p∈χ│p≠o,dMEros(o,p)≤dk(o) }

(6)

式中：x為多元時間序列數據集中所有數據樣本的集合。

3)可達距離

如圖1所示，對于樣本點o，關于樣本點p的可達距離定義如式(7)所示。

圖1 可達距離示意圖

Rd(o)=max{dk(p),dMEros(o,p)}

(7)

4)局部可達密度

樣本點o的局部可達密度定義為樣本點o到o點的k距離鄰域內所有點的平均可達距離的倒數，如式(8)所示。

(8)

通過以上四個定義，可以定義出度量樣本點o離群程度的局部離群因子，如式(9)所示。

(9)

以樣本點o的局部可達密度為基準，對o點的k距離領域內所有樣本點的局部可達密度進行求和，通過取平均值來度量樣本點o的密度與周圍樣本點的密度差異，從而對樣本點o的離群程度進行量化。基于最小距離優化離群算法的多元時間序列異常檢測流程如圖2所示。

2 實驗及結果分析

為驗證算法的實際效果，選用多元時間序列標準數據集，將基于歐氏距離度量的離群算法與所提改進后的離群算法進行比較，通過對比兩種方法的檢測率(Detecton Rate，DR)、誤報率(False Positive Rate，FPR)、漏報率(False Negative Rate，FNR)以及算法的計算時間來驗證改進后離群算法的性能。實驗數據選用3組多元時間序列數據集：MRN_measles[12]、Face(all)[13]和Trace[13]。表1為3組數據集信息的描述。

表1 實驗數據統計

2.1 離群算法鄰域k值的確定

在基于離群算法進行異常檢測的實驗中，鄰域k值的大小對算法的性能有著至關重要的影響，如果鄰域k值太小，則可能無法檢測出異常簇；如果鄰域k值太大，則可能將正常點檢測為異常值。表2列舉了3組數據集在鄰域k值不同時，離群算法異常檢測的準確度。異常檢測的準確度EAcc定義如下：

式中：m為原始數據集中的真實異常點數；n為算法檢測到的真實異常點數。

由表2可知，當k=25時，MRN_measles數據集異常檢測的準確度最高；當k=15時，Face(all)數據集異常檢測的準確度最高；當k=20時，Trace數據集異常檢測的準確度最高。圖3為鄰域k值與計算時間的關系圖，由圖可知，在3組數據集上算法的計算時間均隨著鄰域k值的增大而增加。

表2 鄰域k值對算法精確度的影響

圖3 計算時間與k值的關系

2.2 算法準確性與可用性

為了更準確地驗證運用改進離群算法進行多元時間序列異常檢測的有效性，在對比實驗中，分別選取3組多元時間序列數據集準確度較高且計算時間較短時所對應的鄰域k值進行實驗。實驗通過檢測率、誤報率、漏報率來衡量算法的性能。計算式如下：

式中：X代表數據集合；Y代表X中的異常數據集合；Y′代表離群算法檢測出的異常數據集合。

運用傳統離群算法和改進后離群算法分別對3種數據集進行多元時間序列異常檢測，結果如圖4～6所示。

圖4 兩種不同算法下的檢測率對比

圖5 兩種不同算法下的誤報率對比

圖6 兩種不同算法下的漏報率對比

實驗結果顯示，在檢測率方面，所提算法與傳統離群算法相比，在MRN_measles、Trace和Face(all)數據集中檢測率分別提高了3.2%、5.1%和3.0%；在誤報率方面，所提算法與傳統離群算法相比，在MRN_measles、Trace和Face(all)數據集中檢測率分別降低了3.4%、3.0%和1.2%；在漏報率方面，所提算法與傳統離群算法相比，雖然在數據集Trace的實驗中漏報率沒有降低，但是在數據集MRN_measles和Face(all)的實驗中漏報率分別降低了2.1%和1.4%。通過這3組數據集和3項指標的評估實驗表明，相較于傳統的離群算法，文中提出的改進后的離群算法具有更好的準確性和可用性。

2.3 算法的計算時間

本組實驗采用隨機數發生器產生1 000～10 000大小不等、服從正態分布且具有不同密度的聚類數據集，通過比較傳統離群算法與改進后離群算法的計算時間來進行對比實驗[14-20]。

由圖7可知，兩種算法的計算時間隨著實驗個數的增加而增加。在實驗個數較少的情況下，傳統離群算法的計算時間低于改進后離群算法；當實驗個數趨近7 000時，改進后的離群算法與傳統離群算法的計算時間逐步接近；直至實驗個數達到9 000～10 000時，兩種算法的計算時間幾乎相等。與傳統離群算法相比，改進的離群算法在提升多元時間序列異常檢測性能的同時，計算時間隨著數據量的增加產生較小增幅，達到了較好的檢測效果。

圖7 兩種不同算法的計算時間對比

3 結 語

提出一種基于最小距離改進的多元時間序列異常檢測算法，彌補了傳統離群算法中時間軸彎曲所導致的誤檢、誤報等不足。通過MRN_measles、Face(all)和Trace 3組多元時間序列標準數據集進行實驗，將基于歐氏距離度量的離群算法與改進后的離群算法進行比較，結果表明，運用改進后的離群算法進行檢測，3種數據集的檢測率得到明顯提高，且誤報率和漏報率得到有效降低。采用隨機數發生器產生的數據集進行實驗，將兩種算法的時間代價進行對比，結果表明，兩種算法的時間代價會隨著數據量的增加逐步趨近，且改進后的離群算法在時間代價上具有較小的增幅。因此，改進后的離群算法對多元時間序列的異常檢測具有較良好的性能。