核轉折點裁剪表示的時間序列異常檢測算法

展 鵬，陳 琳 ，曹魯慧，許浩然，李學慶

1.山東大學 軟件學院，濟南 250100

2.山東大學 信息化工作辦公室，濟南 250100

1 引言

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

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

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

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

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

2 相關定義

2.1 時間序列

時間序列中的每一個數據觀測值通常可表示為一個元組(ci,ti)，代表在時刻ti所記錄的數據值為ci[1，12，23]，由此，本節給出了時間序列的定義。

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

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

就時間序列異常檢測領域而言，人們更關注某段時間區間內的異常情況，即局部的異常，稱之為時間序列子序列[1]。

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

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

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

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

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

2.2 時間序列裁剪表示

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

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

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

圖1 時間序列裁剪表示

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

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

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

2.3 時間序列異常檢測

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

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

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

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

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

3 核轉折點裁剪表示方法KTPC

時間序列隨著數據值的變化，其波動趨勢會呈現不同的形態，如股票價格走勢、網絡流量變化等等。轉折點（Turning Point，TP）[11，14]是引起時間序列趨勢變化的特征點，可依此作為裁剪表示的重要特征點。

圖2 KTPC裁剪表示過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1KTPC-AD

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

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

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

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

3.KTPCList=KTPCRepresentation（XSList，K，l）；//將子序列轉換為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）；//計算子序列的異常平均指數

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時間復雜度分析

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

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

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

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

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

5.2 KTPC-AD時間復雜度分析

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

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

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

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

6 實驗結果與分析

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

表1 實驗環境

本章實驗數據采用了Keogh 博士團隊整理的UCR時間序列分類數據集[29]，以及采集自山東大學核心網絡設備的網絡流量時序數據。根據數據的不同分類，實驗所使用的數據集如表2所示。

表2 實驗用時間序列數據集

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

其中，sn表示每個分段的數據點個數。

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

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

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

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

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

圖4 三種數據集上不同方法的TLB實驗結果

表3 不同方法的平均TLB實驗結果%

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

6.2 降維表示效率對比實驗

降維表示的執行效率是衡量一種降維表示方法是否高效的重要指標。本節將KTPC與其他5種表示方法進行對比實驗，進而分析KTPC方法的高效性。

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

圖5 不同方法降維表示的標準化平均運行時間

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

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

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

6.3 異常檢測精度對比實驗

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

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

為了公正評價各方法的異常檢測精度，本節引入異常檢出率DR[30]作為評價標準，可形式化為公式（16）：

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

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

7 結束語

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