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)

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

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

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

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

1 相關(guān)研究

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

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

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

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

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

2.1 Douglas-Peucker法概述

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

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

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

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

2.2 基于DP的時間序列冗余點壓縮

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

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

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

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

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

基于Douglas-Peucker法的時間序列的冗余點壓縮算法的偽代碼可歸納如下:

functionDPFilter(seriesList［］，D)

{//找出最大距離的點及所在位置

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);//計算改進的垂線距離//找出垂線距離最大的數(shù)據(jù)點

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

}

if(Dmax＞=D)

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

//分成前后兩部分

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

//直到去除完所有的冗余點為止

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 時間序列的逐段線性化趨勢提取

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4.2 算法描述

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

輸出:不匹配度λ，異常序列標志flag

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

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

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

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

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

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

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

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

3 算法實驗分析

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

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

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

圖5D-閾值下的運行時間對比

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

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

3.2 精確度(正確率)對比

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

圖73 種算法的精確度對比

3.3 計算時間效率

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

圖83 種算法的時間消耗對比

4 總結(jié)與展望

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

［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］劉良旭，樂嘉錦，喬少杰，等.基于軌跡點局部異常度的異常點檢測算法［J］.計算機學報，2011，34(10):1966-1975.

［3］劉瑞琴，劉學軍.WSN中基于加速動態(tài)時間彎曲的異常數(shù)據(jù)流檢測［J］.傳感技術(shù)學報，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模型的多遠時間序列相關(guān)性研究及預測［J］.系統(tǒng)仿真學報，2008，20(7):1669-1673.

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

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

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

［13］曼蘇爾，于晉龍，馬書惠.一種基于數(shù)據(jù)流跟蹤的無線傳感網(wǎng)能量模型及網(wǎng)絡(luò)優(yōu)化［J］.傳感技術(shù)學報，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)，女，江蘇省蘇州市，碩士生，主要研究方向為數(shù)據(jù)挖掘，異常檢測，傳感器網(wǎng)絡(luò)，liuruiqin_r@163.com;

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

基于冗余點壓縮的趨勢異常序列檢測*

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

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

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

TP393

A

1004－1699(2014)03－0401－08

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

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

10.3969/j.issn.1004－1699.2014.03.024