基于大數(shù)據(jù)的時間序列異常點檢測研究

程艷云，張守超，楊 楊

(南京郵電大學(xué) 自動化學(xué)院，江蘇 南京 210023)

基于大數(shù)據(jù)的時間序列異常點檢測研究

程艷云，張守超，楊 楊

(南京郵電大學(xué) 自動化學(xué)院，江蘇 南京 210023)

針對傳統(tǒng)時間序列異常點檢測方法在處理大量數(shù)據(jù)時檢測精度與效率低下的缺陷，文中提出一種基于大數(shù)據(jù)技術(shù)的全新時間序列異常點檢測方法。首先介紹了傳統(tǒng)時間序列異常點檢測方法并分析了其缺陷。其次介紹了基于大數(shù)據(jù)方法的理論推導(dǎo)，包括特征提取、奇異點檢測及異常點判別，具體為采用大數(shù)據(jù)方法將海量序列分解為周期分量、趨勢分量、隨機誤差分量及突發(fā)分量四個不同分量，對不同分量進(jìn)行特征提取并根據(jù)特征提取結(jié)果進(jìn)行奇異點檢測，并在此基礎(chǔ)上利用序列特點判別奇異點是否為異常點。最后通過實驗分析對比驗證大數(shù)據(jù)方法的可行性與效率。實驗結(jié)果表明，基于大數(shù)據(jù)方法的時間序列異常點檢測相比于傳統(tǒng)的方法具有更高的檢測精度與更快的檢測速率。

異常點檢測;時間序列;大數(shù)據(jù);特征提取

0 引 言

所謂異常點，即數(shù)據(jù)集中與數(shù)據(jù)的一般行為或?qū)ο蟛灰恢碌臄?shù)據(jù)對象，異常點一般也稱作離群點[1]。數(shù)據(jù)的不確定性是產(chǎn)生異常點的主要原因，數(shù)據(jù)的不確定性可分為存在的不確定性和值的不確定性兩類[2]。簡而言之，就是數(shù)據(jù)測量和收集誤差、自然變異、數(shù)據(jù)不確定性等原因?qū)е庐惓｜c的出現(xiàn)。異常數(shù)據(jù)往往包含著很重要的信息，對實驗結(jié)果與分析起到了重要作用，一方面不應(yīng)該將異常數(shù)據(jù)簡單地作為錯誤數(shù)據(jù)來處理，另一方面應(yīng)當(dāng)尋找有效的方法去檢測并挖掘這些異常點所隱含的意義。

時間序列是由記錄值和記錄時間組成的元素的有序集合[3]。時間序列的分析主要包括趨勢分量、季節(jié)性分量、突發(fā)分量以及隨機誤差分量，而趨勢分量與隨機誤差分量是時間序列中異常點檢測的重要研究方向。文中將在分析時間序列特性的基礎(chǔ)上，比較傳統(tǒng)時間序列異常點檢測方法的各自優(yōu)缺點，結(jié)合大數(shù)據(jù)算法，研究如何采用大數(shù)據(jù)方法來對時間序列進(jìn)行異常點的檢測與分析，從而提高檢測的效率與精度，為下一步的數(shù)據(jù)處理提供幫助。

1 傳統(tǒng)時間序列異常點檢測

為了減少異常點對實驗結(jié)果的干擾，需要對異常點進(jìn)行檢測并處理。異常數(shù)據(jù)的挖掘主要使用偏差檢測，包括聚類法、序列異常法、最近鄰居法、多位數(shù)據(jù)分析法等[4-5]。通過偏差檢測可以在一定程度上發(fā)現(xiàn)異常點，但是也存在部分缺陷，比如導(dǎo)致兩種不良的后果：(1)掩蓋現(xiàn)象，即未能識別出某些真正的離群點；(2)淹沒現(xiàn)象，即將正常點誤判為離群點[6]。

時間序列的一個最重要特征就是具有時間屬性，序列值之間必須按照時間先后順序進(jìn)行嚴(yán)格的排序。針對這一特性，產(chǎn)生了很多種時間序列異常點檢測方法，主要分為以下幾大類：

(1)統(tǒng)計學(xué)方法[7-9]。

主要包括基于統(tǒng)計的異常點檢測算法、基于密度的方法、基于距離的異常點的檢測算法等等，然而這類方法需要在多維空間中尋找異常點，并不適用于一維的時間序列，并且在使用統(tǒng)計學(xué)方法前必須得知道數(shù)據(jù)的分布模型，這就涉及到模型參數(shù)的問題，但是這些信息一般事先是不知道的。

(2)機器學(xué)習(xí)方法[10-12]。

機器學(xué)習(xí)方法主要可以劃分為兩大類：一是人工神經(jīng)網(wǎng)絡(luò)，二是支持向量機。兩類方法也是各有優(yōu)缺點：人工神經(jīng)網(wǎng)絡(luò)在處理小規(guī)模問題上具有很好的應(yīng)用效果，但是對于大規(guī)模的問題，人工神經(jīng)網(wǎng)絡(luò)的構(gòu)造將會非常復(fù)雜，因此不能很好地往大規(guī)模問題上擴展；相對于人工神經(jīng)網(wǎng)絡(luò)，支持向量機不僅具有相同的處理能力，而且在計算效率上也有很大的提高，但是支持向量機在理論方面或者在建立模型方面都相對比較復(fù)雜，因此在實際應(yīng)用中存在一定的難度。

(3)其他方法[13-16]。

除了上述提及的兩大類方法，還包括基于空間的方法、基于小波的方法、基于AR模型的方法等等。基于小波的方法雖然在查詢性能上有所改進(jìn)，但是對短期的異常模式無法檢測；而基于AR模型的方法需要知道時間序列模型。

雖然時間序列異常點檢測研究領(lǐng)域出現(xiàn)了很多算法，但是這些算法還不夠成熟，尤其面對日益增加的數(shù)據(jù)量，傳統(tǒng)的時間序列異常點檢測方法在效率與精度上都達(dá)不到預(yù)期要求，所以必須采用新的方法來進(jìn)行處理。

2 基于大數(shù)據(jù)的異常點檢測算法

由于時間序列具有結(jié)構(gòu)簡單的特點，傳統(tǒng)時間序列異常點檢測方法面臨的主要問題在于時間序列特征難以提取，而且面對海量數(shù)據(jù)時，傳統(tǒng)方法在處理能力上已顯得力不從心。為了解決這兩大問題，文中在時間序列基本特點的基礎(chǔ)上，結(jié)合全新的大數(shù)據(jù)處理算法，提出一種新的時間序列異常點檢測方法。通過分析隱藏在海量數(shù)據(jù)背后的特征，提取新的時間序列特征進(jìn)行分析，從而提高預(yù)測效率與精度，改進(jìn)預(yù)測速率，克服傳統(tǒng)方法的缺陷。

時間序列由周期分量、趨勢分量、突發(fā)分量及隨機誤差分量四個分量組成[17]，每個分量均具有不同的特征。文中將先對四個分量進(jìn)行特征提取并根據(jù)特征提取結(jié)果進(jìn)行奇異點檢測，然后結(jié)合四個分量共同特點進(jìn)行異常點檢測，提高檢測精度與速率。圖1為基于大數(shù)據(jù)方法的異常點檢測方法流程圖。

圖1 基于大數(shù)據(jù)的時間序列異常點檢測流程圖

1)周期分量特征提取。

時間序列中周期分量的特征提取主要為時間序列周期的確定，一般的周期確定方法有傅里葉變換、小波變換、差分計算等[18]。文中將根據(jù)時間序列周期特點，結(jié)合大數(shù)據(jù)處理方法，采用一種全新的方法來確定周期L。首先根據(jù)式(1)對時間序列X{x1,x2,…,xM}(xi范圍為V1-V2)進(jìn)行差分計算得到矩陣A(其中m>30*48,n>50)，如下所示：

(1)

對矩陣A的每一行進(jìn)行線性擬合，參數(shù)分別記為(a1,a2,…,am-1),(b1,b2,…,bm-1)，將A的每一行下標(biāo)分別代入對應(yīng)的Y=aN+b中得到對應(yīng)的A'，如式(2)所示。

采用最小二乘法(見式(3))計算A與A'每行最小誤差，其中首次出現(xiàn)最小誤差的行數(shù)即為周期L。

(2)

(3)

2)趨勢分量特征提取。

周期分量特征的正確提取是進(jìn)行趨勢分量特征提取的前提條件。通過周期分量特征提取得到周期L，將時間序列X以周期L進(jìn)行劃分得到矩陣B，其中xM為時間序列X最后一個數(shù)據(jù)，xM之后數(shù)據(jù)均為空值NA。

(4)

矩陣B具有兩個方向的特征坐標(biāo)，同一行內(nèi)所有點代表處于同一周期的所有時間點的集合，同一列內(nèi)的所有點代表處于不同周期同一位置的點的集合。將矩陣B的每一列依次取出，得到共計L個時間序列{x1,xL+1,…,xN*L+1},{x2,xL+2,…,xN*L+2},…,{xi,xL+i,…,xM},{xi+1,xL+i+1,…,NA},…,{xL,x2L,…,NA}，分別記做L1～LL。其中，每個Li序列均有N個數(shù)據(jù)(xM所在列之后序列最后一位數(shù)值均為NA)。

圖2展示了時間序列X及經(jīng)過趨勢分量提取之后的序列X'。圖(a)中，X坐標(biāo)表示時間點，Y坐標(biāo)表示序列值大小;圖(b)中，X坐標(biāo)表示不同周期，Y坐標(biāo)表示單周期長度，Z坐標(biāo)表示序列值大小。

對所有序列Li分別進(jìn)行如下操作：

(1)如果序列中存在NA，則將NA剔除，序列長度變?yōu)镹-1；

(2)對處理后的Li進(jìn)行聚類分析[19]，離群點劃入奇異點E。

對于序列Li內(nèi)的所有點，其本質(zhì)為序列X內(nèi)所有周期內(nèi)相同位置的點的集合，排除突發(fā)分量和隨機誤差影響，理論上具有相同的分布特性。若序列Li趨勢分量為固定值，則Li內(nèi)所有點處于同一條水平直線上，該直線之外的所有點則均認(rèn)為是奇異點；若序列Li趨勢分量按照一定的規(guī)律分布，則不按照該規(guī)律分布的點視為奇異點；若序列Li趨勢分量為隨機分布，則需要先找出隨機分布范圍[min,max]，在該范圍之外的點均為奇異點。

(a)周期特征提取前時間序列X

(b)趨勢分量提取后序列X

3)隨機誤差分量Rt特征提取。

傳統(tǒng)方法一般認(rèn)為時間序列隨機誤差分布函數(shù)服從正態(tài)分布，其均值為0，方差則根據(jù)實際情況確定。而在文中方法中，將根據(jù)時間序列的實際情況來確定隨機誤差分量的分布函數(shù)，具體方法如下所示：

(5)

根據(jù)所有的Rt(i)，可以得到序列X的隨機誤差分布模型，記為Xe～Fe(r)。

(6)

根據(jù)隨機誤差分布模型，即可得到序列X的隨機誤差分布范圍，為下一步的判別奇異點是否為異常點做好準(zhǔn)備工作。

4)突發(fā)分量Bt特征提取。

突發(fā)分量特征提取是判別奇異點是否為異常點的前提，分別對N1～NN-1行做如下操作：

(7)

(8)

(3)如果Sum(i)>Sum(i)'，則序列Ni內(nèi)數(shù)據(jù)均為突發(fā)點，否則序列Ni內(nèi)數(shù)據(jù)不為突發(fā)點。

突發(fā)分量特征Bt提取之后，判別奇異點E是否屬于Bt或者Rt范圍內(nèi)，若是，則該奇異點不是異常點，若否，則該奇異點為異常點。方法總體步驟如下所示：

fori=1:m

計算A得到周期L

end

then

計算得到B(N*L)

fori=1:L

對B的每列進(jìn)行趨勢分量提?。?/p>

分析得到奇異點E:{e1,e2,…,en};

end

提取突發(fā)分量特征Bt;

then

提取隨機誤差分量特征Rt;

forE

if(ei屬于Bt或者在Rt范圍內(nèi))

ei為非異常點

else

ei為異常點

end

3 實驗與結(jié)果

在通信網(wǎng)絡(luò)中，各項核心性能指標(biāo)(KPI)均以時間序列形式表示。以單一小區(qū)為例，單一KPI一年數(shù)據(jù)量長度為48*365。文中將以通訊網(wǎng)絡(luò)中時間序列為例，分析并比較傳統(tǒng)時間序列異常點檢測方法與基于大數(shù)據(jù)的時間序列異常點檢測方法各自的優(yōu)缺點。

任取某一小區(qū)某一KPI(RRC設(shè)置成功率)半年數(shù)據(jù)為例，取m=400，n=100進(jìn)行差分處理得到矩陣A(400*100)，并對矩陣A的每一行進(jìn)行線性擬合并采用最小二乘法計算誤差得到Error矩陣，取矩陣Error首次出現(xiàn)最小值行數(shù)記為周期L，得到最優(yōu)參數(shù)L=48，按照L=48得到矩陣B。對矩陣B以周期為單位畫作圖(按行)和以相同時間點作圖(按列)，見圖3。

(a)L-V維度矩陣B

(b)N-V維度矩陣B

提取矩陣B的每一列得到不同的時間子序列Li，對于所有的序列Li，判別其趨勢分量特征。若趨勢分量為固定值，采用聚類或線性擬合進(jìn)行奇異點確定[20]；若趨勢分量為規(guī)律分布，根據(jù)規(guī)律進(jìn)行奇異點確定；若趨勢分量為隨機分布，根據(jù)分布函數(shù)進(jìn)行奇異點確定。

圖4分別展示了矩陣B的三種不同趨勢分量分布奇異點確定方法。

(a)趨勢分量為零

(b)趨勢分量隨機分布

(c)趨勢分量規(guī)律分布

如圖(a)中所示，對于序列Ni內(nèi)所有點理論均為固定值，即所有點的集合為一條直線，直線之外歸為奇異點；圖(b)中所有點為隨機分布，找出分布的上下區(qū)間，取上區(qū)間的前5%和下區(qū)間的后5%的點記為奇異點；圖(c)中，表示趨勢分量呈一定的周期分布，在此周期之外的點為奇異點。

奇異點E提取過后，進(jìn)行隨機誤差分量特征提取，按照大數(shù)據(jù)算法公式，可以得到整體分布函數(shù)為：

統(tǒng)計每個周期的分布函數(shù)，通過計算可以得到隨機誤差分布函數(shù)為：

Xe～Fe(x)=

突發(fā)分量特征提取結(jié)束之后，進(jìn)行最后一步計算，判別奇異點是否為突發(fā)分量或者在隨機誤差范圍內(nèi)。

圖5為基于大數(shù)據(jù)方法的異常點檢測算法、基于距離的異常點的檢測算法[21]、基于人工神經(jīng)網(wǎng)絡(luò)的異常點檢測方法[22]、基于AR模型方法的異常點檢測方法[23]結(jié)果對比圖，其中虛線線條對應(yīng)點即為異常點。

表1為上述四種方法對于不同數(shù)據(jù)量(短期：30*48個數(shù)據(jù)量；長期：12*30*48個數(shù)據(jù)量)的檢測精度、檢測效率、檢測速率對比結(jié)果。

(a)基于大數(shù)據(jù)

(b)基于距離

(c)基于人工神經(jīng)網(wǎng)絡(luò)

(d)基于AR模型

檢測精度=正確的檢測結(jié)果數(shù)/異常點總數(shù)值* 100%

檢測效率=正確的檢測結(jié)果數(shù)/檢測結(jié)果數(shù)* 100%

檢測速率=完成一次檢測所需時間(s)

表1 短/長期檢測精度、效率、速率結(jié)果對比

通過實驗結(jié)果可以看出，基于大數(shù)據(jù)的時間序列異常點檢測方法在短期異常點檢測中與傳統(tǒng)方法相比在檢測精度、檢測效率上有一定的改進(jìn)，但在檢測速率上稍微遜色一點；但是在面對大量的長期數(shù)據(jù)時，基于大數(shù)據(jù)的時間序列異常點檢測方法在檢測精度與檢測效率上均比其他方法有很大的提高，在檢測速率上相比于其他方法，基于大數(shù)據(jù)的方法具有更快的速率。

4 結(jié)束語

面對日益增長的數(shù)據(jù)量，文中采用大數(shù)據(jù)方法，基于時間序列特征提出了一種全新的時間序列異常點檢測方法，并通過實驗分析該方法的可行性與效率，達(dá)到了預(yù)期要求。同時作為剛剛興起的大數(shù)據(jù)方法，還有許多需改進(jìn)的地方，將來的工作需要對算法做進(jìn)一步的改進(jìn)，提高短期預(yù)測速率、長期預(yù)測精度與效率等。

[1] 曹忠虔.時間序列異常檢測的研究[D].成都:電子科技大學(xué),2012.

[2] 郭 春.基于數(shù)據(jù)挖掘的網(wǎng)絡(luò)入侵檢測關(guān)鍵技術(shù)研究[D].北京:北京郵電大學(xué),2014.

[3]BoxGEP.時間序列分析——預(yù)測與控制[M].上海:機械工業(yè)出版社,2011.

[4] 楊金偉.基于距離和信息熵的不確定異常點檢測研究[D].昆明:云南大學(xué),2011.

[5] 劉良旭,樂嘉錦,喬少杰,等.基于軌跡點局部異常度的異常點檢 測算法[J].計算機學(xué)報,2011,34(10):1966-1975.

[6] 劉丹丹,陳啟軍,森一之.線性回歸模型的多離群點檢測方法及節(jié)能應(yīng)用[J].信息與控制,2013,42(6):765-771.

[7] 胡世杰,錢宇寧,嚴(yán)如強.基于概率密度空間劃分的符號化時間序列分析及其在異常診斷中的應(yīng)用[J].振動工程學(xué)報,2014,27(5):780-784.

[8] 蘇衛(wèi)星,朱云龍,胡琨元,等.基于模型的過程工業(yè)時間序列異常值檢測方法[J].儀器儀表學(xué)報,2012,33(9):2080-2087.

[9] 楊 越,胡漢平,熊 偉,等.一種基于超統(tǒng)計理論的非平穩(wěn)時間序列異常點檢測方法研究[J].計算機科學(xué),2011,38(6):93-95.

[10] 王佳瑋.決策支持中基于時間序列數(shù)據(jù)的異常點檢測[D].合肥:中國科學(xué)技術(shù)大學(xué),2014.

[11] 陳 敏.基于BP神經(jīng)網(wǎng)絡(luò)的混沌時間序列預(yù)測模型研究[D].長沙:中南大學(xué),2007.

[12] 崔萬照,朱長純,保文星,等.基于模糊模型支持向量機的混沌時間序列預(yù)測[J].物理學(xué)報,2005,54(7):3009-3018.

[13] 莊雪鵬.基于小波的時間序列中異常點的檢測[D].南京:南京大學(xué),2013.

[14] 張建平,李 斌,劉學(xué)軍,等.基于Hadoop的異常傳感數(shù)據(jù)時間序列檢測[J].傳感技術(shù)學(xué)報,2014,27(12):1659-1665.

[15] 王 駿,鐘富禮,王士同,等.基于移相加權(quán)球面單簇聚類的周期時間序列異常檢測[J].自動化學(xué)報,2011,37(8):984-992.

[16] 張玉飛,董永貴.一種時間序列異常檢測用參數(shù)化熵濾波器[J].機械工程學(xué)報,2011,47(22):13-18.

[17] 張 蕾.非線性時間序列的高階統(tǒng)計特征提取和趨勢分析[D].沈陽:沈陽航空航天大學(xué),2012.

[18] 龔祝平.混沌時間序列的平均周期計算方法[J].系統(tǒng)工程,2010,28(12):111-113.

[19] 韓 娜.聚類算法在時間序列中的研究與應(yīng)用[D].廣州:廣東工業(yè)大學(xué),2011.

[20] 閆秋艷,夏士雄.一種無限長時間序列的分段線性擬合算法[J].電子學(xué)報,2010,38(2):443-448.

[21]RasheedF,AlhajjR.Aframeworkforperiodicoutlierpatterndetectionintime-seriessequences[J].IEEETransactionsonCybernetics,2014,44(5):569-582.

[22]Buzzi-FerrarisG,ManentiF.Outlierdetectioninlargedatasets[J].ComputersandChemicalEngineering,2010,35:388-390.

[23]LiST,ChengYC.AstochasticHMM-basedforecastingmodelforfuzzytimeseries[J].IEEETransactionsonCybernetics,2010,40(5):1255-1266.

Research on Time Series Outlier Detection Based on Big Data

CHENG Yan-yun，ZHANG Shou-chao，YANG Yang

(College of Automation,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

According to the detection accuracy and efficiency limitation of traditional time series outlier detection methods when dealing with a large amount of data,a new time series outlier detection method is put forward,which is based on the big data technology.Firstly,the traditional time series outlier detection methods are introduced,analysis of their defects.Secondly,it introduces the theoretical derivation of big data method in this paper,which can be divided into feature extraction,abnormal detection and outlier distinguish.The massive series is decomposed into four different components,including periodic component,trend component,random error component and burst component.Then the feature is extracted to four components and abnormal detection is made according to the result of extraction.On this basis it determines whether abnormal point is outlier by series characteristic.Finally,the feasibility and efficiency of big data approach is verified by experiment analysis and comparison.The results show that the big data method has higher precision and rate compared with traditional methods.

outlier detection;time series;big data;feature extraction

2015-07-06

2015-10-14

時間：2016-05-05

江蘇省自然科學(xué)基金(BK20140877，BE2014803)

程艷云(1979-)，女，副教授，碩士生導(dǎo)師，研究方向為自動控制原理、網(wǎng)絡(luò)優(yōu)化；張守超(1991-)，男，碩士研究生，研究方向為大數(shù)據(jù)挖掘在通信網(wǎng)絡(luò)中的應(yīng)用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0817.046.html

TN915.07

A

1673-629X(2016)05-0139-06

10.3969/j.issn.1673-629X.2016.05.030