基于改進(jìn)離群算法的多元時間序列異常檢測

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

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

0 引 言

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

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

為此，文章提出一種基于改進(jìn)離群算法的多元時間序列異常檢測方法?？紤]多元時間序列的多個維度特征之間的相似性，基于最小距離度量改進(jìn)傳統(tǒng)的離群點(diǎn)檢測方法，利用改進(jìn)后離群算法對多元時間序列異常進(jìn)行數(shù)值化表達(dá)，從而實(shí)現(xiàn)多元時間序列的異常檢測。運(yùn)用該算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，結(jié)果表明該算法檢測性能良好。

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

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

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

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

(1)

根據(jù)特征值的大小，選擇前h個特征向量構(gòu)成特征空間，進(jìn)而得到相應(yīng)的主成分。對應(yīng)的時間序列的特征為主成分，其計算式如式(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，最小距離度量方法與傳統(tǒng)Eros距離度量方法的思想一致，即找到一組匹配具有最小距離的最優(yōu)解，并取得最小距離度量。該問題可歸納為一個線性規(guī)劃問題，目標(biāo)函數(shù)如式(4)所示。

(4)

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

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

1.2 基于最小距離優(yōu)化的局部離群因子算法

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

1)o點(diǎn)的k距離

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

(5)

2)o點(diǎn)的k距離鄰域

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

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

(6)

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

3)可達(dá)距離

如圖1所示，對于樣本點(diǎn)o，關(guān)于樣本點(diǎn)p的可達(dá)距離定義如式(7)所示。

圖1 可達(dá)距離示意圖

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

(7)

4)局部可達(dá)密度

樣本點(diǎn)o的局部可達(dá)密度定義為樣本點(diǎn)o到o點(diǎn)的k距離鄰域內(nèi)所有點(diǎn)的平均可達(dá)距離的倒數(shù)，如式(8)所示。

(8)

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

(9)

以樣本點(diǎn)o的局部可達(dá)密度為基準(zhǔn)，對o點(diǎn)的k距離領(lǐng)域內(nèi)所有樣本點(diǎn)的局部可達(dá)密度進(jìn)行求和，通過取平均值來度量樣本點(diǎn)o的密度與周圍樣本點(diǎn)的密度差異，從而對樣本點(diǎn)o的離群程度進(jìn)行量化?；谧钚【嚯x優(yōu)化離群算法的多元時間序列異常檢測流程如圖2所示。

2 實(shí)驗(yàn)及結(jié)果分析

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

表1 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計

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

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

式中：m為原始數(shù)據(jù)集中的真實(shí)異常點(diǎn)數(shù)；n為算法檢測到的真實(shí)異常點(diǎn)數(shù)。

由表2可知，當(dāng)k=25時，MRN_measles數(shù)據(jù)集異常檢測的準(zhǔn)確度最高；當(dāng)k=15時，F(xiàn)ace(all)數(shù)據(jù)集異常檢測的準(zhǔn)確度最高；當(dāng)k=20時，Trace數(shù)據(jù)集異常檢測的準(zhǔn)確度最高。圖3為鄰域k值與計算時間的關(guān)系圖，由圖可知，在3組數(shù)據(jù)集上算法的計算時間均隨著鄰域k值的增大而增加。

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

圖3 計算時間與k值的關(guān)系

2.2 算法準(zhǔn)確性與可用性

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

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

運(yùn)用傳統(tǒng)離群算法和改進(jìn)后離群算法分別對3種數(shù)據(jù)集進(jìn)行多元時間序列異常檢測，結(jié)果如圖4～6所示。

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

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

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

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

2.3 算法的計算時間

本組實(shí)驗(yàn)采用隨機(jī)數(shù)發(fā)生器產(chǎn)生1 000～10 000大小不等、服從正態(tài)分布且具有不同密度的聚類數(shù)據(jù)集，通過比較傳統(tǒng)離群算法與改進(jìn)后離群算法的計算時間來進(jìn)行對比實(shí)驗(yàn)[14-20]。

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

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

3 結(jié) 語

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