核轉(zhuǎn)折點(diǎn)裁剪表示的時間序列異常檢測算法

展 鵬，陳 琳 ，曹魯慧，許浩然，李學(xué)慶

1.山東大學(xué) 軟件學(xué)院，濟(jì)南 250100

2.山東大學(xué) 信息化工作辦公室，濟(jì)南 250100

1 引言

時間序列是日常生產(chǎn)過程中無處不在的一種數(shù)據(jù)類型，其廣泛存在于醫(yī)療診斷[1-2]、網(wǎng)絡(luò)監(jiān)測[3]、金融經(jīng)濟(jì)[4]、水文分析[5]、能源電力[6]等各種行業(yè)中。隨著信息化、物聯(lián)網(wǎng)等先進(jìn)技術(shù)的飛速發(fā)展，時間序列數(shù)據(jù)正以驚人的速度不斷積累，如何從海量的時間序列中挖掘潛在有價值的信息已經(jīng)成為學(xué)術(shù)界和工業(yè)界的研究熱點(diǎn)。正如楊強(qiáng)教授在文獻(xiàn)[7]中指出，時間序列數(shù)據(jù)挖掘已經(jīng)成為21世紀(jì)十大最富有挑戰(zhàn)性數(shù)據(jù)挖掘領(lǐng)域的研究方向之一。

在時間序列數(shù)據(jù)挖掘相關(guān)研究內(nèi)容中，時間序列異常檢測一直備受國內(nèi)外研究人員關(guān)注。不失一般性的，時間序列異常檢測是指發(fā)現(xiàn)時間序列中與其他對象最不相似的數(shù)據(jù)序列或數(shù)據(jù)點(diǎn)的集合[8]。通常，時間序列異常檢測通?？梢苑譃閿?shù)據(jù)點(diǎn)異常檢測和數(shù)據(jù)序列異常檢測[9]，本文主要研究序列異常檢測。由于時間序列具有數(shù)據(jù)維度高、數(shù)據(jù)量大且持續(xù)積累等天然特性，直接利用傳統(tǒng)的數(shù)據(jù)挖掘方法進(jìn)行異常檢測往往難以獲得令人滿意的檢測效率，且原始時間序列數(shù)據(jù)在采集過程中難免夾雜大量噪聲數(shù)據(jù)，對異常檢測結(jié)果的準(zhǔn)確性與可靠性亦會產(chǎn)生影響。如Keogh等[8]提出的基于距離的時間序列暴力異常檢測算法（Brute Force Discord Discovery，BFDD）因時間復(fù)雜度為O(m2)，實際應(yīng)用開銷過大，難以應(yīng)用于高維度、大數(shù)據(jù)量的時間序列。因此，對時間序列進(jìn)行異常檢測之前，通常需要對時間序列進(jìn)行降維表示，即將高維的原始序列轉(zhuǎn)化成低維的特征表示形式。

多年來，國內(nèi)外研究人員對時間序列降維表示展開了深入研究，提出了多種降維表示方法，整體上可以劃分為四類[10]：數(shù)據(jù)自適應(yīng)方法、數(shù)據(jù)非自適應(yīng)方法、基于模型的方法以及數(shù)據(jù)驅(qū)動的方法。常用的時間序列降維表示方法主要有分段線性表示（PLR）[11-12]、分段聚合近似表示（PAA）[13]、符號化表示（SAX）[10，14]、域變換表示（DFT、DWT）[15-16]、裁剪表示（Clipped）[17-19]等。針對基于時間序列降維表示的異常檢測，國內(nèi)外研究人員做了大量研究并提出了一系列有效的方法。Keogh 等將時間序列轉(zhuǎn)換為符號化表示形式，利用基于啟發(fā)式的異常發(fā)現(xiàn)算法，優(yōu)化內(nèi)外循環(huán)檢測過程，提出了HOTSAX[8]異常檢測算法。Khanh等將可索引的符號化表示iSAX與WAT 算法相結(jié)合，提出了WATiSAX[20]異常檢測算法。周大鐲等提出了一種基于重要點(diǎn)分割的K近鄰時間序列局部異常檢測算法[21]，該算法通過計算待檢測時間序列的局部異常因子LOF[22]進(jìn)而發(fā)現(xiàn)異常序列。相關(guān)研究成果表明，基于降維表示的時間序列異常檢測不僅有效提升了異常檢測效率，同時能夠確保檢測結(jié)果的有效性和穩(wěn)定性。

在眾多降維表示方法中，基于數(shù)據(jù)驅(qū)動的時間序列裁剪表示[17]是一種簡單、直觀的降維表示方法，它依據(jù)時間序列中數(shù)據(jù)點(diǎn)與序列均值的關(guān)系將原始時間序列轉(zhuǎn)換成一組由0 和1 組成的序列。通過這種策略，有效地實現(xiàn)了對原始時間序列的壓縮，減少了存儲成本。此外，基于裁剪表示的下界距離計算方法使得其支持與原始時間序列比較相似性，因而能夠獲得更緊密的下界距離，進(jìn)而確?；诓眉舯硎镜臅r間序列檢索、聚類、異常檢測等過程的高效性和無漏報（no false dismissals）。然而，傳統(tǒng)的裁剪表示方法忽略了時間序列中數(shù)據(jù)點(diǎn)對序列趨勢變化的影響，并且存在著無法自定義降維表示壓縮率的缺陷。

綜上所述，本文提出了一種可自定義壓縮率的、基于核轉(zhuǎn)折點(diǎn)的時間序列裁剪表示方法（Kernel Turning Points Clipped Representation，KTPC）。在此基礎(chǔ)上，提出了基于KTPC 表示的時間序列異常檢測算法（KTPC-based Anomaly Detection，KTPC-AD）。本文詳細(xì)分析了算法的執(zhí)行過程與特點(diǎn)，對算法時間復(fù)雜度做了細(xì)致解析，通過實驗對比分析，驗證了該方法在時間序列異常檢測方面的有效性與高效性。

2 相關(guān)定義

2.1 時間序列

時間序列中的每一個數(shù)據(jù)觀測值通?？杀硎緸橐粋€元組(ci,ti)，代表在時刻ti所記錄的數(shù)據(jù)值為ci[1，12，23]，由此，本節(jié)給出了時間序列的定義。

定義1（時間序列）時間序列是一種按照時間順序遞增而不斷累積的數(shù)據(jù)觀測值的有序集合，可將其形式化表示為：

其中，n為時間序列的長度。由于時刻t是嚴(yán)格遞增的，因此，本文將時間序列簡記為：

就時間序列異常檢測領(lǐng)域而言，人們更關(guān)注某段時間區(qū)間內(nèi)的異常情況，即局部的異常，稱之為時間序列子序列[1]。

定義2（時間序列子序列）對于一個給定的時間序列C，子序列X是C中的一個連續(xù)片段，即X是長度為m(m≤n)且從時刻j(1 ≤j≤n-m+1)開始連續(xù)采樣m次所得，可形式化表示為：

為了檢測時間序列中的異常子序列，通常采用滑動窗口（Sliding Window）[1，11]技術(shù)將時間序列劃分成一系列的子序列，以形成子序列集合，見定義3。

定義3（子序列集合）對于一個給定的時間序列C，利用滑動窗口技術(shù)將時間序列C劃分成一系列的子序列，可形式化表示為：

XS即為子序列集合，其中N為子序列的數(shù)量。若滑動窗口大小為w，滑動步長為e，則子序列集合XS中每個元素可形式化表示為：

其中，Xi為子序列集合XS中第i個子序列。該子序列首位數(shù)據(jù)值的時刻j可根據(jù)滑動步長e計算所得，即j=(i-1)×e+1；末位數(shù)據(jù)值的時刻根據(jù)首位時刻與滑動窗口大小w計算得出，即j+w-1。

2.2 時間序列裁剪表示

基于數(shù)據(jù)驅(qū)動的裁剪表示方法是一種直觀、高效的降維表示方法，該方法由Ratanamahatana 等人最先提出[17]。裁剪表示方法根據(jù)時間序列中每個數(shù)據(jù)點(diǎn)與當(dāng)前序列均值的大小關(guān)系，將原始時間序列轉(zhuǎn)換成一組由0 和1 組成的序列。定義4 給出了時間序列裁剪表示[17]的表示過程。

定義4（裁剪表示）對于一個給定的長度為n的時間序列C，令其裁剪表示形式記為?，則?中每個元素由公式（6）計算所得：

其中，μ為時間序列C的均值。如公式（6）所示，當(dāng)時間序列C中元素ci大于均值μ時，其對應(yīng)的裁剪表示形式c?i設(shè)定為1，否則設(shè)置為0。為形式化展示裁剪表示的處理過程，圖1 所示為一段時間序列數(shù)據(jù)經(jīng)過裁剪表示后的結(jié)果，原始時間序列即表示為000000001100111111111100。

圖1 時間序列裁剪表示

從圖1可以看出，位于均值線μ以上的數(shù)據(jù)點(diǎn)映射為1，μ以下的點(diǎn)映射為0。裁剪表示方法的降維表示效率非常高，適用于表示高維度、大數(shù)據(jù)量的時間序列數(shù)據(jù)。然而，傳統(tǒng)的裁剪表示方法忽視了時間序列中數(shù)據(jù)點(diǎn)對序列趨勢變化的影響程度是不同的這一事實，即均等對待每個數(shù)據(jù)點(diǎn)。同時，降維表示的壓縮率完全由數(shù)據(jù)自身決定，而無法自定義壓縮率。

為了解決如上問題，Son等人提出了一種基于感知重要點(diǎn)（Perceptually Important Points，PIP）[24]的裁剪表示方法IPIP[18]。IPIP方法首先將時間序列劃分成若干分段的形式，然后提取每個分段中的PIP，最后利用公式（6）將分段中的PIP轉(zhuǎn)換成0和1的形式。IPIP方法利用對時間序列具有重要表示特征的PIP進(jìn)行裁剪表示，同時通過自定義PIP 提取數(shù)量來控制數(shù)據(jù)的壓縮率。然而，PIP的提取過程時間復(fù)雜度相對較高，一定程度上影響了IPIP 方法在相似性檢索、異常檢測等領(lǐng)域的應(yīng)用。隨后，Son等人采用分段中間點(diǎn)作為特征點(diǎn)進(jìn)行裁剪表示，從而簡化了特征點(diǎn)提取方法，稱為MP_C 方法[19]。MP_C方法不僅保留著裁剪表示方法的高效優(yōu)勢，同時可通過自定義中間點(diǎn)提取數(shù)量來控制數(shù)據(jù)壓縮率，而且，中間點(diǎn)提取過程較PIP提取更加高效。但是，MP_C方法采用分段中間點(diǎn)作為裁剪表示特征點(diǎn)同樣忽視了時間序列中數(shù)據(jù)點(diǎn)對序列趨勢變化的影響程度不一的事實。

在前期工作中發(fā)現(xiàn)[11-12，25-26]，時間序列中對序列趨勢變化有重要貢獻(xiàn)的數(shù)據(jù)點(diǎn)往往更能夠表現(xiàn)原始時間序列的形態(tài)特征，將基于特征數(shù)據(jù)點(diǎn)的降維表示方法應(yīng)用于時間序列檢索、分類、異常檢測等研究領(lǐng)域中，能夠有效提升數(shù)據(jù)分析的精度。結(jié)合當(dāng)前裁剪表示方法存在的問題，本文提出了一種基于核轉(zhuǎn)折點(diǎn)的時間序列裁剪表示方法KTPC，該方法不僅支持可自定義的數(shù)據(jù)壓縮率，而且簡化了核轉(zhuǎn)折點(diǎn)的提取過程，有效提升了KTPC的降維表示效率。

2.3 時間序列異常檢測

時間序列C經(jīng)滑動窗口劃分成子序列集合XS后，本文所提異常檢測算法即是從XS中找到那些不正常的子序列集合。不失一般性的，異常得分是時間序列異常檢測方法中一種重要的反饋異常的方式，基于異常得分的異常檢測方法需要根據(jù)設(shè)定的閾值來判斷待檢測對象是否為異常[27]。由此，本文給出了異常得分及異常子序列的相關(guān)定義。

定義5（異常得分）對于一個給定的時間序列子序列集合XS，其中子序列Xi∈XS，令?i表示子序列Xi的異常得分，即表示子序列Xi相較于XS中其他子序列的差異程度。

定義6（異常得分集合）對于一個給定的時間序列子序列集合XS，其中每條子序列的異常得分組成了XS的異常得分集合AOS，可形式化表示為：

令表示異常得分集合AOS的均值，則子序列Xi的異常平均指數(shù)ζi由公式（8）計算得出：

定義7（異常子序列）對于一個給定的時間序列子序列集合XS，γ記為子序列異常閾值。若子序列Xi的異常平均指數(shù)ζi滿足不等式ζi ＞γ，則Xi可定義為異常子序列。

3 核轉(zhuǎn)折點(diǎn)裁剪表示方法KTPC

時間序列隨著數(shù)據(jù)值的變化，其波動趨勢會呈現(xiàn)不同的形態(tài)，如股票價格走勢、網(wǎng)絡(luò)流量變化等等。轉(zhuǎn)折點(diǎn)（Turning Point，TP）[11，14]是引起時間序列趨勢變化的特征點(diǎn)，可依此作為裁剪表示的重要特征點(diǎn)。

圖2 KTPC裁剪表示過程

定義8（轉(zhuǎn)折點(diǎn)）對于一個給定的時間序列子序列X，若數(shù)據(jù)點(diǎn)ci∈X使以下任意一項不等式成立，則數(shù)據(jù)點(diǎn)ci為轉(zhuǎn)折點(diǎn)（TP）。

起伏波動是時間序列的常見現(xiàn)象，雖然TP 能夠反映時間序列的數(shù)值變化，然而每個TP 對序列局部走勢的影響程度各有差異。文獻(xiàn)[11]中將TP 到時間序列均值的垂直距離（Vertical Distance，VD）作為其對時間序列局部影響程度的指標(biāo)，其中，VD是時間序列降維表示過程中常用的一種權(quán)重度量方法[11，14，28]。該方法存在一定的局限性，即是位于均值附近的TP易被忽略。因此，為了定量描述TP 對時間序列局部走勢的影響程度，同時有效發(fā)現(xiàn)處于均值附近的TP，本文給出了轉(zhuǎn)折點(diǎn)重要指數(shù)的定義，如定義9。

定義9（轉(zhuǎn)折點(diǎn)重要指數(shù)）對于一個給定的時間序列子序列X，其中包含的轉(zhuǎn)折點(diǎn)為{TP1,TP2,…,TPi,…} ，記μ、maxX、minX分別為子序列X的均值、最大值與最小值，則轉(zhuǎn)折點(diǎn)重要指數(shù)TII可由公式（10）計算所得：

分析公式（10）可知，TII 是指數(shù)據(jù)點(diǎn)距離子序列均值和上（下）邊界VD 的最大值。當(dāng)數(shù)據(jù)點(diǎn)大于均值μ時，將數(shù)據(jù)點(diǎn)到均值μ和最大值maxX的VD中最大值作為其轉(zhuǎn)折點(diǎn)重要指數(shù)，反之，則將數(shù)據(jù)點(diǎn)到均值μ和最小值minX的VD 中最大值作為其轉(zhuǎn)折點(diǎn)重要指數(shù)。轉(zhuǎn)折點(diǎn)的TII值越大，表明該轉(zhuǎn)折點(diǎn)的權(quán)重越高，可優(yōu)先選取其作為降維表示的特征數(shù)據(jù)點(diǎn)。為此，結(jié)合TII 的定義，本文給出了核轉(zhuǎn)折點(diǎn)的定義。

定義10（核轉(zhuǎn)折點(diǎn)）對于一個給定的時間序列子序列X，其中包含的轉(zhuǎn)折點(diǎn)為{TP1,TP2,…,TPi,…} ，轉(zhuǎn)折點(diǎn)對應(yīng)的TII表示為{TII1,TII2,…,TIIi,…} 。按照TII從大到小排列，則TII處于前l(fā)位的轉(zhuǎn)折點(diǎn)，即定義為核轉(zhuǎn)折點(diǎn)（KernelTP，KTP）。

完成以上相關(guān)定義后，基于核轉(zhuǎn)折點(diǎn)的時間序列裁剪表示方法KTPC 的降維表示過程可大致分為以下三個步驟，如圖2所示。

步驟1對于一個給定的時間序列C，利用滑動窗口技術(shù)將C劃分為時間序列子序列集合XS，其中每條子序列Xi的長度均為滑動窗口大小w。接下來，即是對子序列集合XS中的每條子序列進(jìn)行KTPC 表示處理。

步驟2取出子序列集合XS中的任意子序列Xi進(jìn)行KTPC 表示。為詳細(xì)描述KTPC 表示過程，以圖3為例進(jìn)行說明。如圖3 所示，X1為XS中的第一條子序列，其長度為200。將X1等分成K(K=4) 個分段（Segments），分別為{Segment1，Segment2，Segment3，Segment4}，分段的長度均為50。利用定義8 對轉(zhuǎn)折點(diǎn)的定義即可發(fā)現(xiàn)子序列中全部的TP，如圖3中圓形點(diǎn)與方形點(diǎn)所示，可以看出，每個TP對子序列的局部波動影響程度是不同的。由此，根據(jù)定義9 計算每個TP 的轉(zhuǎn)折點(diǎn)重要指數(shù)TII。如圖3 中Segment1 所示，點(diǎn)虛線即為TP 距離子序列均值μ和上（下）邊界VD 的最大值。隨后，將每個分段中的TP按照TII降序排列，取TII值處于前(l=4)位的TP作為KTP，如圖3中方形點(diǎn)所示。

圖3 子序列的KTPC表示過程示意圖

本文對TII的計算進(jìn)行了優(yōu)化，即取TP偏離均值或上（下）邊界的最大值作為其重要性指數(shù)，確保位于序列均值附近的轉(zhuǎn)折點(diǎn)可被選取作為特征表示數(shù)據(jù)點(diǎn)。得到子序列各分段中的KTP后，利用公式（6）將KTP轉(zhuǎn)換為0和1的表示形式。最后，將子序列Xi的每個分段的裁剪表示結(jié)果進(jìn)行合并，形成Xi的KTPC表示結(jié)果X?i。

特別地，若時間序列的波動特征不明顯，即子序列中TP較少，在子序列劃分成若干分段后，分段中的TP點(diǎn)個數(shù)tpc

步驟 3將步驟 2 中子序列的 KTPC 表示結(jié)果X?i存入表示結(jié)果集合，隨后，將子序列集合XS中下一條子序列Xi+1移入KTPC表示方法，按照步驟2中過程進(jìn)行表示處理，并將相應(yīng)表示結(jié)果存入表示結(jié)果集合。直至XS中全部子序列均已完成KTPC表示。

為了確保利用KTPC 表示結(jié)果進(jìn)行時間序列異常檢測不會出現(xiàn)漏報，需要定義基于KTPC表示的下界距離計算方法。假設(shè)給定兩條長度為n時間序列X和Y，形式化表示為：X={x1,x2,…,xn} 和Y={y1,y2,…,yn} 。時間序列Y經(jīng)過KTPC表示后的結(jié)果為Y?。在計算X與Y?的下界距離前，需將X轉(zhuǎn)換到與Y?相同的特征空間中，需要說明的是，在將X轉(zhuǎn)換的過程中，只需標(biāo)記特征點(diǎn)的索引位置，無需將數(shù)據(jù)值轉(zhuǎn)換成0 和1 的模式。綜上，基于KTPC表示的下界距離可由公式（11）計算所得：

公式（11）由兩部分組成，分別是兩條序列各分段均值的距離和?中核轉(zhuǎn)折點(diǎn)與序列X對應(yīng)索引位置數(shù)據(jù)點(diǎn)的距離。其中，K為子序列的分段數(shù)量，h為每個分段的長度，和分別表示子序列X和Y中第i分段的均值，l為KTP數(shù)量，表示?中核轉(zhuǎn)折點(diǎn)與序列X對應(yīng)索引位置數(shù)據(jù)點(diǎn)的距離。DKTPC(?)的具體計算過程與IPIP和MP_C方法類似，計算方法和下界證明可參考文獻(xiàn)[18-19]，本文不再贅述。

4 KTPC-AD時間序列異常檢測算法

KTPC 方法實現(xiàn)了對原始時間序列的降維與特征表示，配合符合下界要求的距離計算方法DKTPC，可確保異常檢測過程中不會出現(xiàn)漏報。因此，本文基于KTPC表示，提出了一種高效的時間序列異常檢測算法KTPC-AD。

為了衡量時間序列中子序列之間的差異程度，本文定義了基于KTPC 的差異性評估矩陣（KTPC-based Difference Evaluation Matrix，KDEM），見定義11。

定義11（基于KTPC的差異性評估矩陣）對于一個給定的時間序列C，其子序列集合為XS={X1,X2,…,Xi,…,XN} ，共N條子序列。任意兩條子序列間的DKTPC距離構(gòu)成了KDEM，如公式（12）：

計算得出KDEM之后，根據(jù)定義5對子序列異常得分?的定義，公式（13）給出了?的計算方法：

定義5至定義7給出了基于KTPC的異常子序列的定義，結(jié)合以上公式可以看出，異常得分?即是子序列X較子序列集合XS的異常得分平均水平的偏離程度，?值越大，說明子序列的異常程度越高，配合定義6與定義7，即可得出異常子序列。

綜上所述，KTPC-AD方法的偽代碼如算法1所示。

算法1KTPC-AD

輸入：時間序列C，滑動窗口w，移動步長e，分段個數(shù)K，核轉(zhuǎn)折點(diǎn)提取個數(shù)l，異常閾值γ。

輸出：異常子序列集合ASList。

1.XSList=ConvertTS(C,w,e)；//將時間序列轉(zhuǎn)換成子序列集合

2.L=sizeof（XSList）；//獲取子序列個數(shù)

3.KTPCList=KTPCRepresentation（XSList，K，l）；//將子序列轉(zhuǎn)換為KTPC表示

4.Initializes KDEM filled with 0;

5.foriin 1：Ldo

6.forjin 1：Ldo

7.KDEM（i，j）=DKTPC(Xi,X?j)；//計算子序列間的下界距離

8.end for

9.end for

10.AOS=calculateAnomalyScores（KDEM）；//計算子序列的異常得分

11.AIS=calculateAnomalyIndex（AOS）；//計算子序列的異常平均指數(shù)

12.foriin 1：Ldo

13.ζi=AIS[i]；

14.ifζi ＞γthen

15.InsertXiintoASList；

16.end if

17.end for

18.returnASList；

5 算法分析

5.1 KTPC時間復(fù)雜度分析

對于一個給定的時間序列C，令滑動窗口大小為w，子序列集合XS的容量為L，KTPC表示中分段數(shù)為K，每個分段提取的核轉(zhuǎn)折點(diǎn)數(shù)為l。對于時間序列子序列集合中的一條子序列X，KTPC表示的時間復(fù)雜度可以從以下三個方面進(jìn)行分析：

（1）在長度為w的子序列X查找轉(zhuǎn)折點(diǎn)并計算轉(zhuǎn)折點(diǎn)重要指數(shù)的時間復(fù)雜度為O(w)。

（2）根據(jù)核轉(zhuǎn)折點(diǎn)的定義，當(dāng)計算獲得轉(zhuǎn)折點(diǎn)重要指數(shù)后，在每個分段中提取l個核轉(zhuǎn)折點(diǎn)的時間復(fù)雜度為O(K×l)。

（3）最后，將核轉(zhuǎn)折點(diǎn)表示成0和1的序列形式的時間復(fù)雜度為O(K×l)。

已知，不等式K×l≤w是成立的。因此，對于一條子序列，KTPC表示的時間復(fù)雜度不超過O(w)。綜上，對于一個給定的時間序列C，KTPC表示的時間復(fù)雜度不超過O(L×w)。

5.2 KTPC-AD時間復(fù)雜度分析

利用KTPC 方法對時間序列C進(jìn)行裁剪表示后，即可基于裁剪表示結(jié)果進(jìn)行異常檢測。算法1 給出了KTPC-AD 的算法執(zhí)行過程偽代碼，該算法的時間復(fù)雜度可從以下兩個方面進(jìn)行分析：

（1）根據(jù)KTPC 表示結(jié)果，首先需要構(gòu)建差異性評估矩陣。由此分析，基于KTPC的相似性距離DKTPC的時間復(fù)雜度為O(K×l)，構(gòu)建KDEM的時間復(fù)雜度則為O(L2×K×l)。

（2）KDEM 構(gòu)建完成后，計算子序列異常得分、異常平均指數(shù)以及判斷是否異常子序列的時間復(fù)雜度均為O(L)。

綜上所述，KTPC-AD 算法時間復(fù)雜度不超過O(L2×K×l)。

6 實驗結(jié)果與分析

本章通過在開源數(shù)據(jù)集[29]及網(wǎng)絡(luò)流量時序數(shù)據(jù)集上的對比實驗，從下界距離緊密性（Tightness of Lower Bound，TLB）、降維表示效率以及異常檢測精度三個方面來檢驗本文提出的KTPC 和KTPC-AD 方法的有效性。實驗軟硬件環(huán)境如表1所示。

表1 實驗環(huán)境

本章實驗數(shù)據(jù)采用了Keogh 博士團(tuán)隊整理的UCR時間序列分類數(shù)據(jù)集[29]，以及采集自山東大學(xué)核心網(wǎng)絡(luò)設(shè)備的網(wǎng)絡(luò)流量時序數(shù)據(jù)。根據(jù)數(shù)據(jù)的不同分類，實驗所使用的數(shù)據(jù)集如表2所示。

表2 實驗用時間序列數(shù)據(jù)集

結(jié)合上文介紹，KTPC主要參數(shù)為分段數(shù)K和核轉(zhuǎn)折點(diǎn)的提取個數(shù)l。由于不同類型時間序列的數(shù)據(jù)長度是不同的，本章實驗采用特征點(diǎn)提取率cr來計算每個分段的特征點(diǎn)數(shù)量l，如公式（14）：

其中，sn表示每個分段的數(shù)據(jù)點(diǎn)個數(shù)。

6.1 下界距離緊密性對比實驗

下界距離是在時間序列特征表示空間下的距離計算，下界距離的好壞通常用緊密性（TLB）來衡量，TLB可由公式（15）計算得出：

其中，DLB(X′,Y′)為時間序列在降維表示空間下的下界距離，D(X,Y)為時間序列間的實際距離。由公式（15）可以看出，TLB 取值范圍為0～1，TLB 越接近1，說明在當(dāng)前表示空間的下界距離越接近真實的距離，下界距離的表現(xiàn)越好。

圖4所示為4種降維表示方法（PAA、IPIP、MP_C和KTPC）在三種時間序列數(shù)據(jù)集上的TLB結(jié)果對比。其中，該實驗中設(shè)置分段數(shù)K=4，橫坐標(biāo)為提取率cr。分析圖4 實驗結(jié)果，PAA 方法采用分段均值降維表示原始時間序列，因此數(shù)據(jù)特征損失較嚴(yán)重，下界距離與實際距離差距較大，因此TLB較低；IPIP、MP_C與KTPC方法均采用特征點(diǎn)進(jìn)行裁剪表示，由于KTPC 方法中利用高效核轉(zhuǎn)折點(diǎn)提取方法，有效獲取了對原始時間序列局部特征有重要影響程度的點(diǎn)，因此，基于KTPC表示的下界距離與實際距離的差距較小，即擁有最大的TLB。

不失一般性的，本節(jié)在同等實驗條件下，使用4 種降維表示方法對實驗數(shù)據(jù)集進(jìn)行TLB對比實驗，求對實驗結(jié)果進(jìn)行平均處理，如表3所示。

圖4 三種數(shù)據(jù)集上不同方法的TLB實驗結(jié)果

表3 不同方法的平均TLB實驗結(jié)果%

由于PAA 方法不受提取率cr影響，因此其TLB 結(jié)果在不同壓縮率情況下是相同的。隨著特征點(diǎn)提取率的提高，TLB隨之提升，這是因為獲取的特征點(diǎn)越多，越能夠表征原始時間序列的數(shù)據(jù)特征，結(jié)合公式（11）可知，相應(yīng)的下界距離也會隨之增大，進(jìn)而引起TLB的提升。綜合分析表3可知，KTPC方法具有最高的TLB，即KTPC 方法較另外3 種基準(zhǔn)方法具有更緊密的下界距離，在時間序列檢索、異常檢測等應(yīng)用中，配合相應(yīng)的索引結(jié)果，能夠更準(zhǔn)確地發(fā)現(xiàn)目標(biāo)序列。

6.2 降維表示效率對比實驗

降維表示的執(zhí)行效率是衡量一種降維表示方法是否高效的重要指標(biāo)。本節(jié)將KTPC與其他5種表示方法進(jìn)行對比實驗，進(jìn)而分析KTPC方法的高效性。

為了比較各方法在不同分段數(shù)K下，運(yùn)行時間的變化趨勢，本節(jié)首先設(shè)計實驗，將特征點(diǎn)提取率設(shè)置為cr=10%，將6 種方法在不同分段數(shù)K的條件下，應(yīng)用于實驗數(shù)據(jù)集上，最后將各數(shù)據(jù)集的表示時間進(jìn)行平均化處理。為了便于分析各個方法的平均運(yùn)行時間的變化趨勢，本節(jié)以PAA方法在K=4 情況下的平均運(yùn)行時間設(shè)置標(biāo)準(zhǔn)值1，其他方法基于該值進(jìn)行標(biāo)準(zhǔn)化處理，最終實驗結(jié)果如圖5所示。

圖5 不同方法降維表示的標(biāo)準(zhǔn)化平均運(yùn)行時間

分析圖5可知，PAA方法首先將原始時間序列劃分成K個分段，利用分段均值進(jìn)行降維表示，隨著分段數(shù)的增多，每個分段中的數(shù)據(jù)點(diǎn)相應(yīng)減少，計算分段均值的平均時間有所降低，因而會出現(xiàn)如圖5中所示PAA方法先上升后下降的趨勢形態(tài)；SAX 方法先利用PAA 的思想得到每個分段的均值，然后利用查找表將分段均值表示成字母形式，因而平均運(yùn)行時間稍高于PAA，形態(tài)特征與PAA 方法一致；Clipped 方法是原始的裁剪表示方法，不受分段數(shù)控制，因而其平均運(yùn)行時間未見明顯波動，而且其通過一次遍歷即可得到降維表示形式，效率很高；MP_C 方法先將時間序列分成K個分段，然后尋找分段的中間值作為特征值進(jìn)行裁剪表示，當(dāng)K較小時，所需的特征點(diǎn)較少，因而表示效率很高，隨著K的增加，表示所需的平均運(yùn)行時間緩慢增加，但依然具有較高的表示效率；IPIP 方法與MP_C 方法類似，不同之處在于其選取特征點(diǎn)的方式時間復(fù)雜度較高，因而其平均運(yùn)行時間也相對增加；本文提出的KTPC方法具有IPIP和MP_C方法的優(yōu)點(diǎn)，其表示的平均運(yùn)行時間低于PAA方法，KTPC利用高效的核轉(zhuǎn)折點(diǎn)提取方法有效規(guī)避了IPIP方法的不足之處，因而其表示的平均運(yùn)行時間優(yōu)于IPIP方法，而略高于MP_C和Clipped方法。

為進(jìn)一步分析分段數(shù)與提取率對KTPC 表示效率的影響，圖6 所示為KTPC 方法在不同分段數(shù)和提取率情況下，表示運(yùn)行時間的變化趨勢。整體上分析，隨著分段數(shù)K和提取率cr的增高，平均運(yùn)行時間也隨之增加。結(jié)合圖5 的實驗結(jié)果，在接下來的異常檢測實驗中，為確保檢測效率，將分段數(shù)設(shè)置為K=4，然后分析不同提取率情況下，異常檢測精度的變化情況。

圖6 不同提取率情況下KTPC的表示效率對比實驗

6.3 異常檢測精度對比實驗

KTPC-AD 方法是本文提出的一種基于KTPC表示的時間序列異常檢測方法。為了對比分析KTPC-AD的異常檢測精度，本節(jié)設(shè)計實驗將KTPC-AD 與3 種異常檢測基準(zhǔn)方法（基于SAX 表示的異常檢測SAX-AD[1]、HOTSAX[8]和基于ADPAA表示的異常檢測APAA-AD[30]）進(jìn)行異常檢測精度對比。

表4 異常檢測精度對比實驗

為了公正評價各方法的異常檢測精度，本節(jié)引入異常檢出率DR[30]作為評價標(biāo)準(zhǔn)，可形式化為公式（16）：

其中，AN為異常序列的總數(shù)，DAN為異常檢測方法檢測出的異常序列數(shù)量。表4 所示為各方法在不同時間序列數(shù)據(jù)集的異常檢測檢出率實驗結(jié)果。其中，分段數(shù)設(shè)定為K=4，為分析不同提取率對KTPC-AD 方法的異常檢測精度的影響，表4 列出了4 種不同提取率（10%、30%、50%和70%）情況下的KTPC-AD 方法異常檢測精度。為了發(fā)現(xiàn)異常序列，根據(jù)定義7，本節(jié)將異常閾值γ設(shè)置為：γ=ζˉ+2×σζ。其中，ζˉ為序列異常平均指數(shù)均值，σζ為其標(biāo)準(zhǔn)差。

綜合對比分析可知，SAX-AD方法因為符號化表示損失了原始時間序列的數(shù)據(jù)特征，再利用下界距離進(jìn)行異常檢測時，會導(dǎo)致無法發(fā)現(xiàn)一些潛在的異常，導(dǎo)致檢出率較低；HOTSAX 利用了符號化表示和基于啟發(fā)式的優(yōu)化策略，配合下界距離進(jìn)行剪枝操作，有效提升了異常檢測效率，同時提高了異常檢測精度；APAA-AD方法不同于以往基于時間域的分段表示，它分割了時間序列的數(shù)值域，利用分段在數(shù)值域上的均值表示，有效提高了異常檢測精度；KTPC-AD 方法基于核轉(zhuǎn)折點(diǎn)的裁剪表示，其具有較為緊密的下界距離計算方法，配合具有局部數(shù)據(jù)特征的核轉(zhuǎn)折點(diǎn)裁剪表示形式，能夠有效計算時間序列間的相似性，從表4 可以看出，當(dāng)提取率為10%時，其異常檢出率較低，這是因為核轉(zhuǎn)折點(diǎn)數(shù)量較少，保留的原始時間序列特征難以有效區(qū)分序列間的相似度，當(dāng)提取率設(shè)定為30%或更大時，異常檢出率保持在較高水平，且相對穩(wěn)定。通過以上分析，可使用分段數(shù)K=4，提取率cr=30%的參數(shù)配置進(jìn)行時間序列異常檢測，可有效提升異常檢出率約15%。

7 結(jié)束語

本文提出了一種基于核轉(zhuǎn)折點(diǎn)裁剪表示方法KTPC的時間序列異常檢測方法KTPC-AD。方法首先將原始時間序列等分成若干分段，然后提取每個分段的核轉(zhuǎn)折點(diǎn)進(jìn)行時間序列裁剪表示，即將原始的時間序列數(shù)據(jù)轉(zhuǎn)換表示為一組由0 和1 組成的特征序列，即KTPC 表示形式。隨后，利用序列的KTPC 表示形式，結(jié)合下界距離，利用本文提出的異常得分與差異性評估矩陣，配合異常檢測過程算法，有效地執(zhí)行時間序列的異常檢測。通過在開源數(shù)據(jù)集與網(wǎng)絡(luò)流量時序數(shù)據(jù)集上的對比實驗發(fā)現(xiàn)，本文提出的KTPC表示方法具有較高的表示效率，通過能夠提供較為緊密的下界距離，為KTPC-AD異常檢測方法提供了精度保障，實驗證明，KTPC-AD方法有效提高異常檢出率約15%。在下一步工作中，將針對核轉(zhuǎn)折點(diǎn)進(jìn)行再分析，進(jìn)一步優(yōu)化轉(zhuǎn)折點(diǎn)重要指數(shù)的計算，使其能夠以盡量少的核轉(zhuǎn)折點(diǎn)表征更多的原始數(shù)據(jù)特征，進(jìn)而提高異常檢測的效率和精度。