LI Bin，LIU Ruiqin，LIU Xuejun

(College of Electronic and Information Engineering，Nanjing University of Technology，Nanjing 210009，China)

Abnormal Series Detection Based on Trend Analysis with Point Compression*

LI Bin，LIU Ruiqin*，LIU Xuejun

(College of Electronic and Information Engineering，Nanjing University of Technology，Nanjing 210009，China)

As a special mode of time series，abnormal sequence plays a very important role.But most time series use the distance-based method in similarity measure，ignore the morphological feature of time series itself.Therefore，this paper proposes an abnormal series detection algorithm based on trend contrast，makes use of the bottom-up linear approximation method with combination of important point and the piecewise linearization.And to extract trend features with higher accuracy，the paper fuses the adjacent subsection on the premise of minimizing the two new optimal object function.Moreover，for the purpose of reducing the complexity of the algorithm，time series were collected after deleting redundant point by Douglas-Peucker algorithm，which keeps the whole trend feature of the sequence and to some extent reduces the amount of calculations.The results of simulation demonstrate that the detection algorithm is feasible，and it not only improves the detection accuracy，but also enhances the sequence visualization of the change in trend.

sensor network;time series;outlier data;trend feature;piecewise linear approximation;subsection integration EEACC:7230

時(shí)間序列最早被應(yīng)用于經(jīng)濟(jì)預(yù)測，是指將某種現(xiàn)象某一個(gè)統(tǒng)計(jì)指標(biāo)在不同時(shí)間上的各個(gè)數(shù)值按時(shí)間先后的順序排列而形成的序列，這些值可以是具體的實(shí)數(shù)值，也可以是特定模式的數(shù)值或者是觀察事件發(fā)生的數(shù)目。隨著科學(xué)技術(shù)的迅速發(fā)展，對于信息的獲取和分析等處理基本轉(zhuǎn)換成對數(shù)據(jù)的處理，而大多的數(shù)據(jù)都是以時(shí)間序列的形式提供，尤其是在動(dòng)態(tài)數(shù)據(jù)的監(jiān)測環(huán)境中(比對單個(gè)數(shù)據(jù)的檢測更有意義)，如傳感器網(wǎng)絡(luò)，全球定位系統(tǒng)，衛(wèi)星導(dǎo)航等。因此，時(shí)間序列作為各領(lǐng)域研究的熱點(diǎn)，對于動(dòng)態(tài)系統(tǒng)中的知識(shí)獲?。?］、控制決策等具有重要意義，并在科學(xué)、商業(yè)和工業(yè)等領(lǐng)域有著廣泛的應(yīng)用前景。通常情況下，異常時(shí)間序列數(shù)據(jù)在序列的挖掘過程中有著不可或缺的地位，因?yàn)檫@些數(shù)據(jù)往往代表著某種異常事件的發(fā)生，例如通過對股市、證券交易等異常序列數(shù)據(jù)的分析來預(yù)知未來的走勢，或是在某些監(jiān)測系統(tǒng)的傳感器中，通過感知的異常序列能夠?qū)馂?zāi)、颶風(fēng)［2］或入侵有較好的監(jiān)測和提前預(yù)警作用。而趨勢作為時(shí)間序列模式挖掘領(lǐng)域里的一個(gè)重要特征，更能反映出時(shí)間序列變化的重要信息，因此在時(shí)間序列數(shù)據(jù)庫里利用趨勢的變化來描述序列是發(fā)現(xiàn)相似序列、相關(guān)聯(lián)模式或離群序列最直觀的方法。

時(shí)間序列趨勢的挖掘，可以看作是對序列移動(dòng)方向一種高層模式的挖掘。由于趨勢可以較直觀地用穩(wěn)定上升、穩(wěn)定下降或者周期波動(dòng)等日常用語表示，因此這種直觀的長期趨勢是現(xiàn)象運(yùn)動(dòng)和發(fā)展變化的基本態(tài)勢，這種態(tài)勢不僅存在于過去，而且還可能延伸到未來。對時(shí)間序列長期趨勢的研究，可以幫助人們對現(xiàn)象的前景和將來的狀況進(jìn)行預(yù)測，并且通過這些從時(shí)間序列分離出來的趨勢還有助于更好地觀察各種序列季節(jié)性變動(dòng)、循環(huán)變動(dòng)和不規(guī)則變動(dòng)，尤其是在股票市場預(yù)測分析、環(huán)境趨勢分析或金融證券分析等應(yīng)用中。所以，本文提出了一種時(shí)間序列趨勢的挖掘算法，通過序列的趨勢變化情況來挖掘出異常時(shí)間序列，并且利用冗余點(diǎn)壓縮算法較好地解決了時(shí)間序列數(shù)據(jù)量帶來的計(jì)算復(fù)雜度問題。

本文后續(xù)內(nèi)容安排如下:第2節(jié)介紹了當(dāng)前相關(guān)的研究工作;第3節(jié)提出了一種基于冗余點(diǎn)壓縮的趨勢異常時(shí)間序列挖掘算法;第4節(jié)通過仿真實(shí)驗(yàn)分析了該算法的性能，進(jìn)一步驗(yàn)證了該方法的有效性;第5節(jié)在總結(jié)全文的同時(shí)提出了更深層次的研究工作。

1 相關(guān)研究

隨著時(shí)代的進(jìn)步和各領(lǐng)域的需求，時(shí)間序列被廣泛擴(kuò)展到軍事科學(xué)、空間科學(xué)、氣象預(yù)報(bào)和工業(yè)自動(dòng)化等部門。而異常序列的檢索以大規(guī)模時(shí)間序列數(shù)據(jù)庫相似查詢(搜索)為基礎(chǔ)，成為近年來數(shù)據(jù)挖掘的熱點(diǎn)內(nèi)容之一。異常(離群)序列，采用Hawkin的定義［3］可理解為在傳感器采集到的序列中那些偏離大部分正常時(shí)間序列的序列，使人懷疑其是由不同的機(jī)制產(chǎn)生的而非隨機(jī)偏差造成。在之前的研究中，絕大多數(shù)研究集中在時(shí)間序列中存在的異常點(diǎn)或序列數(shù)據(jù)的相似性模式，且這些算法普遍采用基于密度或距離的度量方式，需要各點(diǎn)數(shù)據(jù)的一一對應(yīng)或等同。而在實(shí)際生活中，會(huì)有以下兩種情況: (1)每個(gè)數(shù)據(jù)點(diǎn)并不是十分的重合，或者說整體數(shù)據(jù)在被采集時(shí)會(huì)因?yàn)橹車h(huán)境的影響使整個(gè)數(shù)據(jù)的具體值偏高或偏低，但是時(shí)間序列的整體變化趨勢卻是較為正常;(2)被檢測序列與正常序列出現(xiàn)交叉現(xiàn)象或距離很近，但是變化趨勢卻截然不同，若是通過基于距離［3-4，14］的方式進(jìn)行序列間的相似性度量，則即使距離累計(jì)和閾值定義得很小，異常序列也會(huì)被誤判為正常的。這些都忽視了時(shí)間序列在研究過程中的形態(tài)特征，導(dǎo)致整體形態(tài)在進(jìn)行比對時(shí)造成偏差。一個(gè)具體例子如圖1所示。

圖1 距離表示時(shí)間序列特征存在的問題

由圖1(a)和1(b)可知，若利用距離累積和計(jì)算，由于監(jiān)測到的值相差過大或過小，會(huì)導(dǎo)致最后的距離(不管是點(diǎn)對點(diǎn)距離還是動(dòng)態(tài)時(shí)間彎曲距離)累計(jì)和偏大或偏小，使得最終的結(jié)果判斷錯(cuò)誤。但是從序列本身的長期趨勢分析來看，不難發(fā)現(xiàn)圖1(a)的時(shí)間序列模式的變化信息是正常的，而圖1(b)則是相反的結(jié)果。因此，Wijsen J［5］提出了趨勢依賴的概念，并被廣泛運(yùn)用到氣候的季節(jié)性變化、股票市場等多領(lǐng)域。雖然利用趨勢特征能對時(shí)間序列的形態(tài)有一個(gè)很好的描述，能較準(zhǔn)確的進(jìn)行序列間相似性度量，但對于該特征的提取需要較大的計(jì)算量，這也是該算法的局限性所在。為了解決這個(gè)問題，在一定程度上對數(shù)據(jù)進(jìn)行壓縮，Camerra A［6］等提出了一種基于PAA(Piecewise Aggregate Approximation)的數(shù)據(jù)壓縮降維方法，該方法利用各分段的均值來表示序列在各段的特征，雖然達(dá)到了高壓縮率的效果，但對原序列的整體形態(tài)趨勢變化沒有進(jìn)行很好的描述。Keogh E［7］等提出了一種子序列匹配算法，該算法首先將監(jiān)測到的時(shí)間序列符號(hào)化，通過符號(hào)檢索出時(shí)間序列中最不尋常(異常)的子序列。Dang-Hoan Tran［8］等人利用DFT方法將時(shí)間序列轉(zhuǎn)變成頻域序列進(jìn)行離群數(shù)據(jù)檢測，但DFT方法平滑了原序列中局部極大值和極小值，導(dǎo)致許多重要信息的丟失，且該種方法對非平穩(wěn)序列也不適用。韓敏等［9］提出了一種改進(jìn)的正交奇異值分解方法EOF-SVD，通過對原始數(shù)據(jù)進(jìn)行自然正交分解及奇異值分解，根據(jù)得到的變量相關(guān)關(guān)系對時(shí)間序列預(yù)測，但其計(jì)算量相當(dāng)大，而且數(shù)據(jù)動(dòng)態(tài)變化后需要重新計(jì)算，這對在線實(shí)時(shí)數(shù)據(jù)很不適用。李曉光等［10］提出了一種基于增量PLA的窗口數(shù)據(jù)近似表示方法，通過動(dòng)態(tài)生成大尺度窗口來適應(yīng)可變長的趨勢變化檢測。張力生等［11］則提出了一種基于時(shí)間序列重要點(diǎn)分割的異常子序列檢測算法，從一定程度上彌補(bǔ)了點(diǎn)異常檢測的局限性。

與以上的研究不同，本文提出了一種在冗余點(diǎn)壓縮后基于趨勢對比的異常序列檢測算法。該算法先將采集到的時(shí)間序列進(jìn)行基于Douglas-Peucker算法的逐點(diǎn)壓縮，去除冗余點(diǎn)的同時(shí)保持了時(shí)間序列原有的形態(tài)，從而達(dá)到一定的檢測提速效果。然后，將壓縮后的序列進(jìn)行重要點(diǎn)和分段相結(jié)合的自底向上的趨勢特征提取，利用數(shù)據(jù)的分段線性逼近擬合得到各準(zhǔn)確分段的斜率，繼而轉(zhuǎn)化成趨勢。最后將分析的趨勢結(jié)果與正常序列趨勢進(jìn)行比對，從而搜索出異常序列。該種方法不僅提高了檢測精度，還從一定程度上減少了計(jì)算復(fù)雜度。

2 相關(guān)定義與算法描述

2.1 Douglas-Peucker法概述

Douglas-Peucker算法一般用在GIS、計(jì)算機(jī)制圖和計(jì)算機(jī)圖形學(xué)等領(lǐng)域，主要是為了實(shí)現(xiàn)矢量數(shù)據(jù)的壓縮，它是在經(jīng)典的垂距法的基礎(chǔ)上做了一些改進(jìn)。如圖2所示，其中圖2(a)是起伏較大的時(shí)間序列經(jīng)過兩種算法處理后的結(jié)果示意圖，圖2(b)表示彎曲度較小的序列經(jīng)過處理后的結(jié)果對比。由圖可知，DP不管在何種情況下都能夠很好的描述出整條序列的形態(tài)，這是因?yàn)榈栏窭?普克算法可準(zhǔn)確的刪除小彎曲上的定點(diǎn)，能從整體上有效地保持線要素的彎曲形態(tài)特征，而垂距法卻只考慮了線的局部，每次處理時(shí)，當(dāng)時(shí)間序列各相鄰點(diǎn)起伏變化不大時(shí)，在處理過程中可能刪除掉所有的中間點(diǎn)，造成形態(tài)的嚴(yán)重失真。

圖2 兩算法處理結(jié)果對比

為了能更好地理解本文采用的數(shù)據(jù)壓縮方法，簡單介紹Douglas-Peucker法的基本思想。即對分段后的每條時(shí)間序列的首尾兩點(diǎn)虛連一條直線，求出序列上所有的點(diǎn)到該條虛連直線的距離，同時(shí)找出這些垂線距離值中的最大值Dmax，定義一個(gè)垂線段的最大距離閾值D，用Dmax與D進(jìn)行比較:(1)若Dmax＜D，則將序列上這兩點(diǎn)間全部的中間點(diǎn)刪去; (2)若Dmax≥D，則保留Dmax對應(yīng)的坐標(biāo)點(diǎn)，并以該點(diǎn)為界，把曲線分成兩部分，以此類推重復(fù)使用該方法，直到處理完全部的序列為止。該算法的示意圖如下圖3所示。

圖3 具體DP處理過程示意圖

2.2 基于DP的時(shí)間序列冗余點(diǎn)壓縮

時(shí)間序列的相似性搜索是時(shí)間序列數(shù)據(jù)挖掘的基礎(chǔ)問題，而相似性度量的定義和搜索算法的時(shí)間復(fù)雜度一直以來是它的瓶頸。在實(shí)際應(yīng)用中，對于采集到的數(shù)據(jù)流時(shí)間序列，若不作任何處理直接對這些數(shù)據(jù)進(jìn)行序列檢測，其算法的計(jì)算復(fù)雜度是難以想象的，并且很不利于數(shù)據(jù)的傳輸。因此，本文采用DP(Douglas-Peucker，道格拉斯-普克)算法對時(shí)間序列先進(jìn)行數(shù)據(jù)的壓縮，減少兩序列間的點(diǎn)比對數(shù)目，從一定程度上提高檢測的速度。

定義1(時(shí)間序列)假設(shè)采集的時(shí)間序列可看作是一系列的觀測值和觀測時(shí)間組成的有序集合，則可表示為:

定義2(垂線段的距離)假設(shè)序列上數(shù)據(jù)點(diǎn)A(tA，xA)、B(tB，xB)、C(tC，xC)，其中點(diǎn)A和點(diǎn)B是DP算法中的首尾兩點(diǎn)，點(diǎn)C是中間點(diǎn)，則數(shù)據(jù)點(diǎn)C到AB連線上數(shù)據(jù)點(diǎn)的距離為:

定理1(垂線段距離簡化定理)在連續(xù)變化的時(shí)間序列中，序列上的點(diǎn)如定義2中所描述，則在算法的執(zhí)行過程中，距離可簡化為d'⊥=|atC+bxC+c |，無需再計(jì)算d⊥中分母的值。

證明:在時(shí)間序列中，由于tA＜tC＜tB，可推知b2=(tB-tA)2＞0，所以d⊥中的分母。在利用DP法計(jì)算過程中，只是為了找出首尾兩點(diǎn)間d⊥的最大值Dmax，從而能夠與限差閾值D進(jìn)行比較。對于首尾AB兩點(diǎn)間所有中間點(diǎn)的d⊥來說，分母的值都是相等的，所以在進(jìn)行點(diǎn)壓縮過程中，可以忽略計(jì)算垂線段距離的分母值。

基于Douglas-Peucker法的時(shí)間序列的冗余點(diǎn)壓縮算法的偽代碼可歸納如下:

functionDPFilter(seriesList［］，D)

{//找出最大距離的點(diǎn)及所在位置

Dmax←0，index←0;

//初始化序列的大值和最大值所在的位置

for(i=2;i＜=seriesList.length-1;i++)

{

a←seriesList［end］.y-seriesList［1］.y;

b←seriesList［1］.x-seriesList［end］.x;

c←seriesList［1］.y*seriesList［end］.x

seriesList［end］.y*seriesList［1］.x;

d←abs(a*seriesList［i］.x+b*

seriesList［i］.y+c);//計(jì)算改進(jìn)的垂線距離//找出垂線距離最大的數(shù)據(jù)點(diǎn)

if(d＞Dmax){index←i;Dmax←d;}

}

if(Dmax＞=D)

{//Dmax超過閾值，則以Dmax所在位置為界，將

//分成前后兩部分

//將序列分成的兩部分繼續(xù)回調(diào)DPFilter函數(shù)，

//直到去除完所有的冗余點(diǎn)為止

frontPart［］←DPFilter(seriesList［1…index］，D);

backPart［］←DPFilter(seriesList［index…end］，D);

resultList［］←{frontPart［1…end-1］

backPart［1…end］};

}

else

resultList［］←{seriesList［1］，seriesList［end］};

return resultList［］;

}

2.3 時(shí)間序列的逐段線性化趨勢提取

2.3.1 時(shí)間序列數(shù)據(jù)的分段線性表示

雖然在2.2節(jié)中利用道氏算法對時(shí)間序列進(jìn)行了數(shù)據(jù)的壓縮并保留了序列的整體形態(tài)，但是對于動(dòng)態(tài)變化的時(shí)間序列來說，是無法單純地用直線擬合出來的。所以對基本趨勢的提取，必須依次逐段比較斜率，將復(fù)雜的曲線簡化為有限個(gè)直線段來提取線性結(jié)構(gòu)特征。換言之，即將數(shù)據(jù)壓縮后的時(shí)間序列先進(jìn)行一定的分段，再對每個(gè)分段內(nèi)的數(shù)據(jù)進(jìn)行最小二乘線性擬合，從而提取出各段的趨勢值，這樣就可以對每個(gè)直線段的形態(tài)有一個(gè)自然描述，即將連續(xù)的斜率值用有限的自然語言概念(上升，下降，平穩(wěn))［5］來表示。

趨勢變化信息是時(shí)間序列的重要特征，在數(shù)學(xué)領(lǐng)域中，曲線上極值點(diǎn)的兩側(cè)基本趨勢是完全不同的。本文將這一思想運(yùn)用到時(shí)間序列的自然轉(zhuǎn)折點(diǎn)上，將其作為時(shí)間序列分段的自然分割點(diǎn)，并提出重要點(diǎn)的概念。

定義3(序列重要點(diǎn))對于數(shù)據(jù)壓縮后的時(shí)間序列X={(ti，xi)}Ni=1，對于?xi(i=1，2，…N)，若對任意滿足式(3)的xj，都有xi≥xj(xi≤xj)，則稱xi為序列的重要點(diǎn)。

其中，p為給定的一個(gè)常數(shù)。

重要點(diǎn)分段法是時(shí)間序列的一個(gè)重要算法，本文將時(shí)間序列X={(ti，xi)}={Xj}劃分為r段，各分段間互不相交且不含重要點(diǎn)。假設(shè)序列的第j分段的起點(diǎn)和終點(diǎn)位置分別為sj、ej，則用線性模型來擬合時(shí)間序列在區(qū)間［tsj，tej］上的關(guān)系為φj(ti)=ajti+bj+E0，其中φj(ti)是響應(yīng)變量，ti是回歸變量，E0為誤差項(xiàng)。則利用最小化誤差平方和作為目標(biāo)函數(shù):

目標(biāo)函數(shù)E0表示了原時(shí)間序列與分段線性近似之間的擬合程度，由式(4)可知，E0越小，分段線性近似表示對原時(shí)間序列的擬合越好。因此最小化目標(biāo)函數(shù)，可得到較精確的擬合參數(shù)，從而可提取較準(zhǔn)確的趨勢值。

為了便于直觀地觀測各個(gè)分段的趨勢變化，對各個(gè)分段上的趨勢定義如下:

定義4(基本趨勢)在第j段時(shí)間序列Xj上，對于sj≤i≤ej中點(diǎn)的分段線性近似φj(ti)≈ajti+bj上的基本趨勢記為:

其中，趨勢值aj＞0表示上升趨勢，aj=0表示平穩(wěn)趨勢，aj＜0表示下降趨勢。

時(shí)間序列的分段線性近似的最大好處在于可以快速分析時(shí)間序列的趨勢，而將各趨勢進(jìn)行簡單的數(shù)字化更便于在離群檢測時(shí)的比對。

2.3.2 基于逼近原則的趨勢特征提取

趨勢值的精確提取一直是一個(gè)難題，為了最小化目標(biāo)函數(shù)E0，大多數(shù)的文章采用改變時(shí)間序列分段的數(shù)量r、改變各分段區(qū)間的長度或改變對每一分段進(jìn)行線性擬合的方法等。蔣嶸等［12］利用定長分段線性化方法對各分段區(qū)間內(nèi)的數(shù)據(jù)進(jìn)行線性擬合來較快地得到相應(yīng)的線性化模型，但是對于復(fù)雜的時(shí)間序列來說，不同區(qū)間內(nèi)的時(shí)間序列變化也不同，當(dāng)分段長度相等時(shí)，誤差比較大，基本趨勢也有可能被錯(cuò)誤提取。通常情況下，分段數(shù)越多，對序列的逼近效果越好，但會(huì)使壓縮效果變差，這樣就背離了本文對快速變化數(shù)據(jù)流時(shí)間序列處理的初衷。所以本文利用自底向上的線性化方法，通過調(diào)整各分段時(shí)間區(qū)間的長度，并在進(jìn)行分段線性擬合的同時(shí)根據(jù)分段數(shù)和誤差平方和的關(guān)系，選定具體的分段數(shù)。

雖然利用分段線性化的方法，可以獲得時(shí)間序列在不同精度的抽象表示，但是近似誤差為目標(biāo)函數(shù)會(huì)使某些顯著的趨勢在擬合過程中失去原有的特征。為了能更好地進(jìn)行分段線性近似擬合以及對趨勢的準(zhǔn)確提取，本文利用式(4)的思想，將每個(gè)點(diǎn)的趨勢值與每段的趨勢值之間的誤差作為最小優(yōu)化目標(biāo)函數(shù)，以此來提取更準(zhǔn)確的結(jié)果，相關(guān)的定義如下:

定義5設(shè)時(shí)間序列X上的任一個(gè)點(diǎn)(ti，xi)，則其在該段序列上的趨勢值為:

則在分段數(shù)r下關(guān)于趨勢的最小目標(biāo)函數(shù)為:

其中，E1表示整個(gè)時(shí)間序列的趨勢值和各分段趨勢值之間的誤差，E2則表示分段趨勢與整體趨勢的不一致程度。為了保證基本趨勢的正確提取，最小化式(7)中的目標(biāo)函數(shù)，使得分段線性近似得到最優(yōu)化。顯而易見，同時(shí)優(yōu)化E1和E2是很困難的，必須將多目標(biāo)優(yōu)化問題進(jìn)行簡化。而本文是為了較準(zhǔn)確地提取序列的趨勢，即保證趨勢基本一致，因此可以將問題轉(zhuǎn)化為在E2=0的條件下最小化E1的單目標(biāo)問題。

定理2假設(shè)在時(shí)間序列第j(1≤j≤r)分段(sj，ej)中不包含重要點(diǎn)，若要使第j分段內(nèi)點(diǎn)的趨勢值與原序列趨勢值的誤差最小，則第j分段線性近似斜率(趨勢值)的值為:

證明:在第j分段(sj，ej)內(nèi)，各點(diǎn)的趨勢值(斜率)為ai∈{asj，asj+1，…，aej-1，aej}，則由式(7)可知，趨勢值之間的誤差為:

由上述定理2的結(jié)果可知，在目標(biāo)函數(shù)E2=0時(shí)，可得出因此，不難看出在分段內(nèi)各點(diǎn)的趨勢和段內(nèi)所有點(diǎn)的整體趨勢是一致的，換而言之，即在各個(gè)小分段開區(qū)間內(nèi)不存在重要點(diǎn)(分段點(diǎn))，這樣就需要尋找重要點(diǎn)(分段)位置，以達(dá)到準(zhǔn)確的趨勢特征提取。所以本文利用逐段融合的思想，首先將時(shí)間序列分為若干個(gè)較小的初始分段，同時(shí)形成滿足相關(guān)條件的初始位置，然后逐步合并初始分段，使?jié)M足定義5中的目標(biāo)函數(shù)最優(yōu)化，從而確定新的分段位置，直到?jīng)]有可融合的分段為止。假設(shè)兩相鄰可融合的分段位置為ξ(第ξ分段和第ξ+1分段為可融合分段)，則融合后趨勢值之間的誤差以及相關(guān)融合段的趨勢值為:

2.4 基于趨勢對比的離群序列檢測算法(TOTSD)

2.4.1 檢測算法的設(shè)計(jì)模型

對于采集的數(shù)據(jù)流［13］時(shí)間序列，首先進(jìn)行2.2節(jié)的數(shù)據(jù)預(yù)處理，即基于改進(jìn)的道格拉斯-普克算法的時(shí)間序列冗余點(diǎn)壓縮，這在一定程度上保持?jǐn)?shù)據(jù)序列原有形態(tài)特征的同時(shí)還較大地減少了數(shù)據(jù)量。接著在時(shí)間序列經(jīng)過壓縮后，進(jìn)行如2.3節(jié)的重要點(diǎn)和分段線性化方法相結(jié)合的趨勢特征提取，同時(shí)對相鄰分段進(jìn)行自底向上的分段融合。其設(shè)計(jì)模型如圖4所示。

圖4 算法設(shè)計(jì)模型

2.4.2 算法描述

輸入:采集到的時(shí)間序列X={(ti，xi)}ni=1，常數(shù)D，p，l，α，ε

輸出:不匹配度λ，異常序列標(biāo)志flag

Step 1對時(shí)間序列調(diào)用DPFilter(X，D)，獲得壓縮后的序列X'，并將其標(biāo)志flag置為0(默認(rèn)為正常);

Step 2根據(jù)定義3提取出X'的重要點(diǎn)位置，同時(shí)根據(jù)定義5的式(6)求出X'的各點(diǎn)的趨勢值ai，并根據(jù)定理2的結(jié)果，將相鄰兩個(gè)重要點(diǎn)之間的斜率ak作為重要點(diǎn)分段趨勢值，記錄最后的重要點(diǎn)個(gè)數(shù)q，其中k∈{1，2，3，…，q};

Step 3將序列按照重要點(diǎn)的位置分成q-1段，根據(jù)定義5中式(7)的關(guān)于趨勢值擬合誤差的定義計(jì)算出重要點(diǎn)分段的E'1;

Step 4將序列的每個(gè)重要點(diǎn)分段再劃分為初始長度為l的小分段，當(dāng)?shù)趉重要點(diǎn)分段不能被l整分時(shí):1)若第k重要點(diǎn)分段的長度Nk小于l，則將該段單獨(dú)作為一個(gè)初始小分段;2)若Nk大于或等于l，則將Nk整除l得到各小分段。同時(shí)在各重要點(diǎn)分段內(nèi)計(jì)算出初始小分段擬合誤差E1;

Step 5若E1＞αE'1，則減小l并轉(zhuǎn)到Step 4;若E1≤αE'1，將相鄰分段融合，同時(shí)根據(jù)式(9)計(jì)算融合后的E1=Eξ1，判斷:1)若Eξ1≤αE'1，記錄融合后的新分段位置，更新分段數(shù)，使迭代融合;2)反之，放棄融合。

Step 6求出融合后的總段數(shù)r;

Step 7將融合后得到的完整的趨勢特征與正常序列特征進(jìn)行對比，同時(shí)記錄出不匹配的趨勢特征段數(shù)m，利用λ=m/r計(jì)算出不匹配度，其中，m表示檢測的不匹配趨勢段數(shù);

Step 8若檢測到的當(dāng)前序列的不匹配度超過閾值，即λ＞ε，則將標(biāo)志flag設(shè)為1(表示該序列為異常序列);反之，若檢測到的λ≤ε，則不改變標(biāo)志，該序列為正常序列。

3 算法實(shí)驗(yàn)分析

本文采用MATLAB7.1實(shí)現(xiàn)上述所提出的算法，并從擬合度、精確度和計(jì)算效率等幾個(gè)方面進(jìn)行性能分析，來驗(yàn)證基于趨勢對比的離群序列檢測算法的有效性。

3.1 不同D-閾值下的性能分析

如圖5所示，描述了兩條長時(shí)間序列在不同壓縮閾值D下進(jìn)行本文所提出算法處理后的運(yùn)行時(shí)間對比，其中DataSet_s和DataSet_f分別表示趨勢變化不明顯(較平穩(wěn))和波動(dòng)相對較大的兩條數(shù)據(jù)量相同的時(shí)間序列。由圖5可知，隨著閾值的增大，算法所需的運(yùn)行時(shí)間逐漸減少，這是因?yàn)殚撝翟酱螅谶M(jìn)行DP算法處理后，對中間的冗余點(diǎn)的刪除效果就越好，即壓縮率越高。但是在較低的壓縮閾值下，由于DataSet_f起伏較大，對于很多不影響檢測結(jié)果的點(diǎn)都保存了下來，相對于序列DataSet_s，在后續(xù)進(jìn)行異常趨勢檢測時(shí)所需的運(yùn)行時(shí)間就相對較大，但是隨著閾值的增大，DataSet_f表現(xiàn)出了相對的優(yōu)勢。

圖5D-閾值下的運(yùn)行時(shí)間對比

圖6 表示兩序列的擬合度(通過壓縮后進(jìn)行趨勢比對的不匹配度λ所得)對比，從圖中可看出，壓縮率越小，對原序列的擬合效果越好。而且隨著D的增大，更利于DataSet_f的檢測。這是因?yàn)椴▌?dòng)較大的序列，其形態(tài)特征點(diǎn)較為明顯，D越大，對于中間的過渡點(diǎn)有很好的刪除作用，相對較平穩(wěn)的序列DataSet_s而言，對采集到的序列的整體形態(tài)有更好地描述，從而使得后期的趨勢特征提取的誤差率相對較小。綜合圖5和圖6中的結(jié)果分析，可得出在閾值D為3.0時(shí)，算法在精度和時(shí)間效率上都有一個(gè)較好地把握，更利于時(shí)間序列的離群檢測。

圖6D-閾值下的擬合度對比

3.2 精確度(正確率)對比

取閾值D=3，同時(shí)使λ＞10%時(shí)認(rèn)為序列偏離正常序列的趨勢過大，即判為離群序列。圖7顯示了3種相似性查詢算法在六組不同的時(shí)間序列數(shù)據(jù)訓(xùn)練集下的檢測精確度，其中精確度認(rèn)為是檢測到的離群序列的個(gè)數(shù)與期望得到的離群序列的總數(shù)之間的比值。由圖可知，PAA算法與DTW［14］和本文所提的TOTSD算法相比較，檢測精度是最低的，這是因?yàn)镻AA算法將采集到的序列按照等長間隔分段，并利用每個(gè)分段內(nèi)點(diǎn)的均值表示該段整體的序列數(shù)據(jù)值，對于長序列的整體形態(tài)不能有一個(gè)較好的描述，更體現(xiàn)不出時(shí)間序列的發(fā)展趨勢，這樣在進(jìn)行序列間距離計(jì)算時(shí)就會(huì)有較大的誤差，導(dǎo)致最后的離群檢測的錯(cuò)誤率較高。而經(jīng)典的DTW算法采用了在距離矩陣中遞推式的最短路徑搜索方法，彌補(bǔ)了傳統(tǒng)的一對一式的距離比較算法的缺陷，解決了序列間出現(xiàn)平移后可部分重合現(xiàn)象的問題，在準(zhǔn)確度上有了較大地提高。綜觀本文所提的TOTSD算法，采用了重要點(diǎn)和分段相結(jié)合的自底向上的分段融合的趨勢特征提取，在檢測精度的把握上與DTW基本保持一致，并在一定程度上針對距離累計(jì)計(jì)算帶來的不足(如時(shí)間序列集DataSet4，與正常序列數(shù)據(jù)值出現(xiàn)交叉和距離拉大現(xiàn)象較多)，發(fā)揮出了較大的優(yōu)勢。但是由于先經(jīng)過了基于DP算法在D閾值下的冗余點(diǎn)刪除，導(dǎo)致在某些長時(shí)間序列訓(xùn)練集的檢測準(zhǔn)確率上稍有偏差，可并不影響對序列整體發(fā)展趨勢的觀測效果。

圖73 種算法的精確度對比

3.3 計(jì)算時(shí)間效率

如圖8所示，DTW由于采取普遍的動(dòng)態(tài)規(guī)劃方法來搜索距離矩陣中起始點(diǎn)間的最優(yōu)路徑，達(dá)到所需的較高的檢測精度，但卻是以犧牲計(jì)算時(shí)間為代價(jià)的。而本文所提出的TOTSD算法由于先進(jìn)行了基于道格拉斯-普克算法的冗余點(diǎn)刪除，在整體形態(tài)趨勢保持不變的基礎(chǔ)上對采集到的原序列有較大的壓縮處理，雖然沒有同樣具備壓縮效果的PAA算法處理速度快，但是比起DTW算法有了很大的進(jìn)步，并且在某些時(shí)間序列數(shù)據(jù)訓(xùn)練集上比PAA算法的速度更快(如起伏間相隔時(shí)間較長的DataSet2，對數(shù)據(jù)有著很好的刪減效果)。比較該3種算法的整體性能，本文的TOTSD算法較好地兼顧了時(shí)間效率和檢測精度。

圖83 種算法的時(shí)間消耗對比

4 總結(jié)與展望

本文提出了一種基于趨勢特征的異常序列挖掘算法TOTSD，與已有關(guān)于趨勢特征提取算法不同的是:先利用DP算法對采集到的時(shí)間序列進(jìn)行冗余點(diǎn)的刪除，達(dá)到數(shù)據(jù)壓縮效果的同時(shí)保持了序列的整體形態(tài)，更加有助于對長序列數(shù)據(jù)的后期處理;然后在以重要點(diǎn)分段保證線性基本特征不被錯(cuò)誤提取的前提下，以小尺度分段進(jìn)行自底向上的分段融合，并通過兩個(gè)新的優(yōu)化目標(biāo)函數(shù)使融合后的線性擬合誤差最小。通過實(shí)驗(yàn)驗(yàn)證了TOTSD算法的有效性，既提高了檢測的準(zhǔn)確度，又在一定程度上減少了計(jì)算開銷。本文接下來的工作是對算法進(jìn)行改進(jìn)，進(jìn)一步提高它的檢測速度，并與實(shí)際應(yīng)用相結(jié)合，考慮海量數(shù)據(jù)的高維和在線檢測等問題，提高該算法的實(shí)際應(yīng)用價(jià)值。

［1］Keogh E，Kasetty S.On the Need for Time Series Data Mining Benchmarks:A Survey and Empirical Demonstration［C］//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Edmonton，Alberta，Canada，2002，102-111.

［2］劉良旭，樂嘉錦，喬少杰，等.基于軌跡點(diǎn)局部異常度的異常點(diǎn)檢測算法［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34(10):1966-1975.

［3］劉瑞琴，劉學(xué)軍.WSN中基于加速動(dòng)態(tài)時(shí)間彎曲的異常數(shù)據(jù)流檢測［J］.傳感技術(shù)學(xué)報(bào)，2013，26(6):887-893.

［4］Rakthanmanon T，Campana B，Mueen A，et al.Searching and Mining Trillions of Time Series Subsequences under Dynamic TimeWarping［C］//18th ACM SIGKDD Int Conf Knowledge Discovery and Data Mining，Beijing，China，2012:262-270.

［5］Wijsen J.Trends in Databases:Reasoning and Mining［J］.IEEE Transactions on Knowledge and Data Engineering，2001，13(3): 426-438.

［6］Alessandro Cammerra，Themis Palpanas，Jin Shieh，et al.iSAX 2.0: Indexing and Mining One Billion Time Series［C］//IEEE International Conference on Data Mining.Washington:IEEE，2010:1 -13.

［7］Keogh E，Lin J.Finding Unusual Medical Time-Series Subsequences: Algorithms and Applications［J］.IEEE Transactions on Information Technology in Biomedicine，2006，10(3):429-439.

［8］Dang-Hoan Tran，Jin Yang.Decentralized Change Detection in Wireless Sensor Network Using DFT-based Synopsis［C］//The 12th IEEE International Conference，2011:226-235.

［9］韓敏，李德才.基于EOF-SVD模型的多遠(yuǎn)時(shí)間序列相關(guān)性研究及預(yù)測［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20(7):1669-1673.

［10］李曉光，宋寶燕，張昕.基于滑動(dòng)多窗口的時(shí)間序列流趨勢變化檢測［J］.電子學(xué)報(bào)，2010，38(2):321-326.

［11］張力生，楊美潔，雷大江.時(shí)間序列重要點(diǎn)分割的異常子序列檢測［J］.計(jì)算機(jī)科學(xué)，2012，39(5):183-186.

［12］蔣嶸，李德毅.基于形態(tài)表示的時(shí)間序列相似性搜索［J］.計(jì)算機(jī)研究與發(fā)展，2000，37(5):601-608.

［13］曼蘇爾，于晉龍，馬書惠.一種基于數(shù)據(jù)流跟蹤的無線傳感網(wǎng)能量模型及網(wǎng)絡(luò)優(yōu)化［J］.傳感技術(shù)學(xué)報(bào)，2009，22(4):505-510.

［14］Sakurai Y，F(xiàn)aloutsos C，Yamamuro M.Stream Monitoring under the Time Warping Distance.ICDE，2007:1046-1055.

李斌(1979)，男，江蘇省南京市，碩士，講師，主要研究方向包括數(shù)據(jù)庫，傳感器網(wǎng)絡(luò)等;

劉瑞琴(1989)，女，江蘇省蘇州市，碩士生，主要研究方向?yàn)閿?shù)據(jù)挖掘，異常檢測，傳感器網(wǎng)絡(luò)，liuruiqin_r@163.com;

劉學(xué)軍(1971)，男，江蘇省南京市，副教授，博士，主要研究方向包括數(shù)據(jù)庫，數(shù)據(jù)挖掘，傳感器網(wǎng)絡(luò)等。

基于冗余點(diǎn)壓縮的趨勢異常序列檢測*

李斌，劉瑞琴*，劉學(xué)軍
(南京工業(yè)大學(xué)電子與信息工程學(xué)院，南京210009)

異常序列作為時(shí)間序列的一種特殊模式有著極其重要的作用，但大多數(shù)的時(shí)間序列利用基于距離的方法進(jìn)行序列間的相似性度量，忽略了時(shí)間序列本身的形態(tài)特征。為此，提出了一種基于趨勢對比的異常序列檢測算法，利用重要點(diǎn)和分段線性相結(jié)合的自底向上的線性逼近方法，并以最小化兩個(gè)目標(biāo)函數(shù)為目的進(jìn)行相鄰分段融合，從而使提取的趨勢特征有較高的準(zhǔn)確度。而且為了降低提取算法的復(fù)雜度問題，對采集到的時(shí)間序列先進(jìn)行道格拉斯-普克算法的冗余點(diǎn)刪除，保持序列整體形態(tài)的同時(shí)從一定程度上減少了計(jì)算量。最后通過仿真實(shí)驗(yàn)，驗(yàn)證了所提出的檢測算法的有效性，不僅提高了檢測的準(zhǔn)確率，還增強(qiáng)了序列趨勢變化觀測的直觀性。

傳感器網(wǎng)絡(luò);異常序列;離群數(shù)據(jù);趨勢特征;分段線性逼近;分段融合

TP393

A

1004－1699(2014)03－0401－08

2013-12-16修改日期:2014-02-20

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目(61073197);江蘇省科技支撐計(jì)劃項(xiàng)目(SBE201077457);國家質(zhì)檢公益性科研專項(xiàng)項(xiàng)目(201210022)

10.3969/j.issn.1004－1699.2014.03.024