王 玲 周 南 申 鵬

（北京科技大學(xué)自動(dòng)化學(xué)院 北京 100083）

（工業(yè)過程知識(shí)自動(dòng)化教育部重點(diǎn)實(shí)驗(yàn)室（北京科技大學(xué)） 北京 100083）（lingwang@ustb.edu.cn）

目前，時(shí)間序列的異常檢測(cè)作為一項(xiàng)重要的數(shù)據(jù)挖掘任務(wù)，已被廣泛應(yīng)用到氣象信息[1]、水文監(jiān)測(cè)[2]、醫(yī)療保健[3]、工業(yè)應(yīng)用[4]等眾多領(lǐng)域中.根據(jù)異常的表現(xiàn)形式不同，時(shí)間序列的異?？梢苑譃楫惓｜c(diǎn)、異常序列及異常子序列[5].異常點(diǎn)是與大部分?jǐn)?shù)據(jù)點(diǎn)有顯著差異的數(shù)據(jù)點(diǎn)[6-7]；異常序列指的是與大部分時(shí)間序列有顯著偏差的整條時(shí)間序列[8-9]；異常子序列是與大部分子序列有顯著不同的子序列[10-11].考慮到異常子序列可能與一段時(shí)間內(nèi)的特殊事件有關(guān)，往往會(huì)比正常子序列包含更多有用的信息，更有研究?jī)r(jià)值，本文主要對(duì)異常子序列進(jìn)行研究.

異常子序列并非只有一種，不同的機(jī)制[12]會(huì)導(dǎo)致多類異常子序列的產(chǎn)生.例如，心電圖的異常子序列即心率失常，可以分為竇性心動(dòng)過速、早搏、房顫、竇性心動(dòng)過緩、房室傳導(dǎo)阻滯等多種類型；水文時(shí)間序列中的異常子序列也可以分為洪水、干旱等多種異常類型.為了識(shí)別不同類型的異常，可以先檢測(cè)異常子序列，然后再利用聚類算法區(qū)分異常子序列的類型，令一個(gè)異常模式代表一類異常子序列，進(jìn)而實(shí)現(xiàn)異常模式的識(shí)別.下面分別對(duì)異常子序列檢測(cè)和異常子序列聚類這2部分的相關(guān)工作進(jìn)行說明.

目前, 常見的異常子序列檢測(cè)算法包括基于距離的異常子序列檢測(cè)方法[13-15]、基于聚類的異常子序列檢測(cè)方法[5,16]、基于密度的異常子序列檢測(cè)方法等[17-18].基于距離的異常子序列檢測(cè)方法利用子序列之間的距離計(jì)算子序列的異常分?jǐn)?shù)(異常因子), 通過比較異常分?jǐn)?shù)與設(shè)定閾值的大小來(lái)檢測(cè)異常子序列.文獻(xiàn)[13]提出一種基于距離的異常子序列檢測(cè)算法DBAD，通過計(jì)算兩兩子序列的歐氏距離，并比較其與分布中心的偏差程度實(shí)現(xiàn)異常子序列檢測(cè).文獻(xiàn)[15]將子序列與其最近的k個(gè)子序列距離的平均值作為異常分?jǐn)?shù)，并利用假設(shè)檢驗(yàn)確定子序列是否異常.基于聚類的異常子序列檢測(cè)方法是將子序列劃分到不同的類簇中，使得簇中的子序列具有較高相似度，簇間的子序列具有較低相似度.通過分析子序列和類簇中心之間的關(guān)系，來(lái)尋找異常子序列.文獻(xiàn)[16]使用模糊c均值聚類[19]來(lái)揭示子序列的結(jié)構(gòu)，然后利用從簇中心和劃分矩陣得到的重構(gòu)準(zhǔn)則[20]重建原始子序列，對(duì)于每個(gè)子序列，根據(jù)原始子序列與重建子序列的差值分配其異常分?jǐn)?shù).該聚類算法需要人為設(shè)置聚類個(gè)數(shù)，但在實(shí)際應(yīng)用中，我們通常缺少對(duì)數(shù)據(jù)集的先驗(yàn)知識(shí)，這會(huì)嚴(yán)重影響聚類的效果.而基于密度的異常子序列檢測(cè)方法是根據(jù)子序列的密度與其周圍子序列的密度之間的比值來(lái)定義異常分?jǐn)?shù)，從而檢測(cè)出異常子序列.文獻(xiàn)[18]提出了一種動(dòng)態(tài)局部密度估計(jì)(dynamic local density estimation, DLDE)異常子序列檢測(cè)算法，利用時(shí)間分割樹 (time split tree, TSTree)動(dòng)態(tài)分割時(shí)間序列，并通過子序列中每個(gè)數(shù)據(jù)點(diǎn)的動(dòng)態(tài)局部密度來(lái)評(píng)估子序列的異常程度；但該算法需要利用集成學(xué)習(xí)獲取參數(shù)，算法復(fù)雜度較大.

由于不同結(jié)構(gòu)的異常子序列預(yù)示著不同的異常事件，因此需要對(duì)異常子序列進(jìn)行聚類以區(qū)分不同類型的異常子序列，識(shí)別所有異常模式.這里介紹一些可用于聚類異常子序列的時(shí)間序列聚類算法.文獻(xiàn)[21]提出了一種基于軌跡形狀的時(shí)間序列聚類算法kmlShape，該算法是k均值聚類算法[22]的一個(gè)變體，利用弗雷歇距離計(jì)算出時(shí)間序列之間的距離，并提出弗雷歇平均值確定每個(gè)類別的均值以實(shí)現(xiàn)時(shí)間序列的聚類；文獻(xiàn)[23]提出一種基于統(tǒng)計(jì)預(yù)處理的距離密度聚類DDC，將平滑和特征選擇作為預(yù)處理步驟，在每個(gè)特性集群中進(jìn)行距離密度聚類以完成時(shí)間序列聚類；文獻(xiàn)[24]提出了一個(gè)新穎的時(shí)間序列聚類算法，該算法可以生成同質(zhì)且較好分離的聚類，其采用標(biāo)準(zhǔn)的互相關(guān)距離度量方法并基于此提出了一個(gè)計(jì)算簇心的算法，在每一次迭代中都用其來(lái)更新時(shí)間序列的聚類分配.然而，這些聚類算法對(duì)輸入?yún)?shù)較為敏感，影響最終聚類結(jié)果的正確性，這在一定程度上限制了這些聚類算法的應(yīng)用.

文獻(xiàn)[21?24]中提出的算法在設(shè)置參數(shù)方面較為薄弱，且忽略了異常子序列的類別區(qū)分問題，因此，本文重新定義了異常模式這一概念，提出一種基于自適應(yīng)k近鄰的異常模式識(shí)別算法(anomaly pattern recognition algorithm based on adaptiveknearest neighbor, APAKN).該算法首先根據(jù)各子序列的自適應(yīng)k近鄰計(jì)算其自適應(yīng)距離比和相對(duì)密度，這里相對(duì)密度與傳統(tǒng)基于密度的異常檢測(cè)算法[25]的局部密度有所區(qū)別，無(wú)需計(jì)算待測(cè)對(duì)象密度與其鄰域?qū)ο竺芏戎龋蝗缓筇岢鲆环N基于最小方差的自適應(yīng)閾值方法確定異常閾值；最后采用基于自適應(yīng)k近鄰的聚類算法自動(dòng)發(fā)現(xiàn)聚類中心并聚類異常子序列.整個(gè)算法過程在無(wú)需設(shè)置任何參數(shù)的情況下，不僅解決了密度不平衡問題，還精簡(jiǎn)了傳統(tǒng)基于密度異常子序列檢測(cè)算法的步驟，實(shí)現(xiàn)良好的異常模式識(shí)別效果.

1 相關(guān)定義

定義1.子序列.給定一子序列集合D={s1,s2,…,, 其中為子序列的個(gè)數(shù)其中表示子序列所包含的數(shù)據(jù)點(diǎn)個(gè)數(shù).

定義2.異常子序列和正常子序列.異常子序列是子序列集合中異常分?jǐn)?shù)大于異常閾值的子序列，異常子序列集合表示為其中n為異常子序列的個(gè)數(shù), 則正常子序列的個(gè)數(shù)為N?n，正常子序列集合表示為

定義3.異常模式.異常模式是由相似異常子序列構(gòu)成的類簇的中心, 異常模式集合表示為P={p1,p2,…,pi,…,pc}，其中c為聚類后的類簇個(gè)數(shù).

定義4.子序列距離.對(duì)于子序列集D中任意2個(gè)子序列si,sj, 采用動(dòng)態(tài)時(shí)間彎曲（dynamic time warping，DTW）距離[26]度量計(jì)算si與sj之間的距離

其中，si[1:li?1]為si去除尾元素后剩余的子序列，即去除尾元素后剩余的子序列，即表示數(shù)據(jù)點(diǎn)與數(shù)據(jù)點(diǎn)之間的歐氏距離，計(jì)算方法為 √

定義5.第k近 鄰 和 第k近 鄰 距 離.假 設(shè)si和sj為 子序列集D中 的子序列，對(duì)于任意正整數(shù)k,si的第k近鄰為sj，si的 第k近 鄰 距 離 為si與sj之 間 的 距 離，記為kdk(si),sj需要滿足2個(gè)條件：

1)D中 至 少 存 在k個(gè) 子 序 列sj′, 使kdk(si)成立；

2)D中 最多存在k?1個(gè)子序列sj′，使kdk(si)成立.

定義6.k近鄰域.子序列集合D中 ，除si外所有與si的距離小于等于si的第k近鄰距離kdk(si)的子序列構(gòu)成子序列si的k近鄰域KNNk(si)，即

將KNNk(si)中子序列的個(gè)數(shù)定義為si的k近鄰個(gè)數(shù)，記為 |KNNk(si)|.

定義7.反向k近鄰域.對(duì)于任意子序列，如 果si屬 于sj的k近 鄰 域 ， 則sj屬 于si的 反 向k近 鄰 域RNNk(si)，即

將RNNk(si)中子序列的個(gè)數(shù)定義為si的 反向k近鄰個(gè)數(shù)，記為 |RNNk(si)|.

為說明k近鄰域和反向k近鄰域，圖1利用7個(gè)空心圓分別表示7個(gè)子序列，顯示出各子序列之間的距離關(guān)系.表1列出近鄰值k=4時(shí)7個(gè)子序列的k近鄰域、反向k近鄰域、反向k近鄰個(gè)數(shù).

Fig.1 Schematic diagram of subsequence distribution圖1 子序列分布示意圖

Table 1 k Near Neighbors Domain and Reverse k Near Neighbors Domain of Subsequences when k = 4表1 k = 4時(shí)子序列的k近鄰域與反向k近鄰域

從表1可以看出，同一子序列的k近鄰域和反向k近鄰域并不存在對(duì)稱關(guān)系.

2 基于自適應(yīng) k近鄰的異常模式識(shí)別算法

APAKN是一個(gè)基于自適應(yīng)k近鄰的異常模式識(shí)別算法，算法整體工作流程如圖2所示，主要由異常子序列檢測(cè)和異常子序列聚類2個(gè)部分組成.本節(jié)將對(duì) APAKN 算法的基本思想及其實(shí)現(xiàn)過程進(jìn)行詳細(xì)介紹.

Fig.2 The overall workflow of the APAKN圖2 APAKN的總體工作流程

2.1 基于相對(duì)密度的異常子序列檢測(cè)

為了確定子序列是否異常，查詢各子序列的自適應(yīng)k近鄰值計(jì)算子序列的相對(duì)密度，根據(jù)相對(duì)密度計(jì)算異常分?jǐn)?shù)，將異常分?jǐn)?shù)大于異常閾值的子序列視為異常子序列.

考慮到異常子序列具有較少的鄰居，正常子序列具有較多的鄰居，各子序列的k近鄰值并不相同是自適應(yīng)k近鄰搜索算法區(qū)別于傳統(tǒng)k近鄰[27]算法的主要特征.搜索子序列si(si∈D)的自適應(yīng)k近鄰值ki的主要過程為：令搜索次數(shù)r=1，迭代地尋找每個(gè)子序列的r近鄰 域,使用Numr記 錄 第r次迭代時(shí)集合中0的個(gè)數(shù).若Numr在連續(xù)3次迭代中未發(fā)生變化，即Numr=Numr+1=Numr+2，則認(rèn)為算法達(dá)到穩(wěn)定狀態(tài)，迭代停止，否則，令r=r+1繼續(xù)迭代.將迭代停止后的迭代次數(shù)計(jì)為kf=r+2，子序列si的 自適應(yīng)k近鄰值

以圖1中的子序列為例查找各子序列的自適應(yīng)k近鄰值.圖3展示了7個(gè)子序列在r=1,r=2,r=3,r=4時(shí)的近鄰情況.

當(dāng)r=1時(shí), 圖3 (a)展示了所有子序列的 1近鄰，其 |RNN1(si)|=0的子序列為s1,s6,s7, 此時(shí)Num1=3.

當(dāng)r=2 時(shí)，圖3 (b)展示了所有子序列的2近鄰，{|RNN2(si)|}i=1={0,3,2,3,4,1,1} ，其 |RNN2(si)|=0 的子序列為s1, 此時(shí)Num2=1.

當(dāng)r=3 時(shí), 圖3 (c)展示了子序列s1,s5的3近鄰，{|RNN3(si)|}7i=1={0,4,3,5,6,2,1}，其 |RNN3(si)|=0的子序列為s1, 此時(shí)Num3=1.

當(dāng)r=4 時(shí), 圖3 (d)展示了子序列s1,s5的4近鄰，{|RNN4(si)|}7i=1={0,4,5,6,6,4,3}，其 |RNN4(si)|=0的子序列為s1, 此時(shí)Num4=1.

當(dāng)r=2 時(shí)滿足Num2=Num3=Num4, 搜索停止,kf=r+2=4, 輸出所有子序列的自適應(yīng)k值為{k1,k2,…,k7}={0,4,5,6,6,4,3}.

Fig.3 Neighbors of subsequences at different values of r圖3 子序列在不同 r值時(shí)的近鄰情況

在得到子序列si(i=1,2,…,N)的自適應(yīng)k近鄰值ki(i=1,2,…,N)的基礎(chǔ)上，計(jì)算子序列的相對(duì)密度來(lái)進(jìn)一步得到子序列的異常分?jǐn)?shù).許多復(fù)雜的數(shù)據(jù)集可能有多個(gè)密度不同的集群，如果只比較局部密度的大小可能會(huì)將一些密度較小集群中的數(shù)據(jù)對(duì)象誤檢為異常.為解決密度不平衡問題，目前基于密度的異常子序列檢測(cè)算法通常在估計(jì)出所有子序列的局部密度后，通過比較待測(cè)子序列的局部密度與其鄰域內(nèi)子序列的局部密度來(lái)檢測(cè)異常，但算法結(jié)果對(duì)鄰域參數(shù)較為敏感，人工選擇合適的鄰域參數(shù)較為困難，需要研究者的經(jīng)驗(yàn)或大量的實(shí)驗(yàn)，也使算法不具備自適應(yīng)性.為此，本文引入自適應(yīng)距離比計(jì)算相對(duì)密度，不僅解決密度不平衡問題，而且無(wú)需人為選擇近鄰參數(shù).

令km為集合 {k1,k2,…,kN}中的最大值，為子序列si的km近鄰域中的子序列，為子序列的自適應(yīng)k近鄰值，si與的距離為，的第近鄰距離為，計(jì)算si與其km近鄰域KNNkm(si)內(nèi)所有子序列的自適應(yīng)距離比.子序列si相對(duì)于子序列的自適應(yīng)距離比為

計(jì)算子序列si(si∈D)的相對(duì)密度，其為si與其所有KNNkm(si)內(nèi)子序列的平均自適應(yīng)距離比的倒數(shù)，KNNkm(si)中的子序列個(gè)數(shù)用表示.si的相對(duì)密度計(jì)算公式為

以圖4為例說明自適應(yīng)距離比如何解決密度不平衡問題.圖4中s8,s9,s10屬于高密度集群，s11為異常子序列，s12,s13,s14,s15,s16屬于低密度集群.若是單純將密度小的子序列視為異常，則低密度集群都有可能被視為異常.這里以s8,s11,s14為例證明自適應(yīng)距離比解決密度不平衡問題的有效性.在該示例中km=8，圖4中已標(biāo)注出s8,s11,s14的8近鄰域范圍，表2列出km=8時(shí)s8,s11,s14相對(duì)于其第8近鄰的自適應(yīng)距離比.

Fig.4 Density imbalance data圖4 密度不平衡數(shù)據(jù)

Table 2 Adaptive Distance Ratio of s8, s11, s14 Relative to Its 8th Nearest Neighbor表2 s8, s11, s14相對(duì)于其第8近鄰的自適應(yīng)距離比

從表2可以看出adr(s8,s9)與adr(s14,s15)相差較小，而adr(s11,s12)遠(yuǎn)大于adr(s8,s9)和adr(s14,s15)，根據(jù)相對(duì)密度的計(jì)算公式（6）可以推斷出M(s8)與M(s14)的值大致相同，而M(s11)遠(yuǎn)小于M(s8)和M(s14)的值.這可以證明本文提出的自適應(yīng)距離比和相對(duì)密度不受其所屬集群密度的影響，解決了密度不平衡問題.

子序列相對(duì)密度較低意味著其可能具有較高的異常分?jǐn)?shù).進(jìn)一步，子序列si的異常分?jǐn)?shù)為

得到異常分?jǐn)?shù)集合S={S(s1),S(s2),…,S(si),…,S(sN)}后，對(duì)其做歸一化處理，子序列si的最終異常分?jǐn)?shù)為

以圖1中s1為例計(jì)算異常分?jǐn)?shù)：由于{k1,k2,…,k7}={0,4,5,6,6,4,3}，所以該集合中的最大值km=6，為子序列s1的6近鄰域中的子序列，即(j=1,2,…,6)∈KNN6(s1)={s3,s2,s5,s4,s7,s6}，為子序列的自適應(yīng)k近鄰值，s3,s2,s5,s4,s7,s6的自適應(yīng)k近鄰值分別為5,4,6,6,3,4，s3,s2,s5,s4,s7,s6的第近鄰分別是s6,s6,s1,s1,s4,s7，因此的第近鄰距離分別為ddtw(s3,s6)，ddtw(s2,s6)，ddtw(s5,s1)，ddtw(s4,s1)，ddtw(s7,s4)，ddtw(s6,s7)；代入式(6)可以得到M(s1)=0.413,s1的原始異常分?jǐn)?shù)為S(s1)=1?M(s1)=0.586，歸一化異常分?jǐn)?shù)為S′(s1)=1，后文中若無(wú)特殊說明，異常分?jǐn)?shù)即是指歸一化后的異常分?jǐn)?shù).

為了準(zhǔn)確確定異常子序列，需要設(shè)置異常閾值T，將待檢測(cè)子序列si(i=1,2,…,N)的異常分?jǐn)?shù)S′(si)與異常閾值T相比較.若S′(si)

其中均值u和標(biāo)準(zhǔn)差 σ 是確定值，令參數(shù) β∈{0,0.1,0.2,0.3,…,2.8,2.9,3.0}.為了選擇合適的 β值確定最佳異常閾值T，以異常子序列和正常子序列的異常分?jǐn)?shù)集合的方差之和作為目標(biāo)函數(shù)，找出使得目標(biāo)函數(shù)最小的 β以確定異常閾值T.

以圖1中子序列為例確定異常閾值T：所有子序列的異常分?jǐn)?shù)的均值和標(biāo)準(zhǔn)差分別為0.280和0.315，β∈{0,0.1,0.2,0.3,…,2.8,2.9,3.0}，則 異 常 閾 值T∈{0.280,0.312,0.343,0.375,…,1.162,1.194,1.225}， 根 據(jù)這31個(gè)閾值取值分別得到31種異常子序列集合，根據(jù)式(12)計(jì)算得出目標(biāo)函數(shù)值的集合，當(dāng) β =0.3 時(shí)取得目標(biāo)函數(shù)的最小值0.015，此時(shí)確定異常閾值T=0.280+0.315×0.3=0.375，由于只有S′(s1)≥T，則檢測(cè)出圖1中子序列s1為異常子序.

2.2 基于自適應(yīng) k 近鄰的異常子序列聚類

針對(duì)異常子序列的多樣性，為區(qū)分不同類型的異常子序列，本節(jié)對(duì)得到的異常子序列進(jìn)行聚類，將每個(gè)聚類中心定義為一個(gè)異常模式，對(duì)不同的異常模式進(jìn)行識(shí)別.本算法能夠在聚類個(gè)數(shù)未知的情況下保證聚類結(jié)果的有效性.

APAKN根據(jù)2個(gè)條件尋找聚類中心：1)聚類中心的密度高于其鄰近的子序列的密度；2)任意2個(gè)類中心的距離相對(duì)較遠(yuǎn).首先利用2.1節(jié)描述的自適應(yīng)k近鄰搜索算法確定所有異常子序列的自適應(yīng)k近鄰值(i=1,2,…,n)，將其作為各異常子序列的密度.將異常子序列中自適應(yīng)k值最大的子序列作為第1個(gè)聚類中心p1，在與p1距離最遠(yuǎn)的v個(gè)子序列中找出密度最大的異常子序列作為第2個(gè)聚類中心p2，其中即為異常子序列個(gè)數(shù)與10的比值取整加1.在距離存儲(chǔ)單元搜索剩余子序列與2個(gè)聚類中心之間的距離，確定聚類數(shù)為2時(shí)各子序列所屬聚類.同時(shí)使用輪廓系數(shù) (silhouette coefficient)[29]作為聚類有效性指標(biāo)計(jì)算當(dāng)前的輪廓系數(shù)sil2.

當(dāng)聚類數(shù)為q時(shí)，輪廓系數(shù)的計(jì)算公式為

其中N為所有子序列個(gè)數(shù)，Ci表 示第i個(gè)類簇，w為屬于類簇Ci的 子序列，sam(w,Ci)被稱為子序列w的簇內(nèi)不相似度，是子序列w到同類其他子序列的平均距離，dif(w,Ci)被稱為子序列w的簇間不相似度, 是子序列w到所有其他簇的所有子序列的平均距離中最小的那一個(gè).定義分別為：

其中nCi為 類別Ci所 包含 子序列的 個(gè)數(shù)，nCl為 類 別Cl所包含子序列的個(gè)數(shù)，ddtw(w,u)表示子序列w與u之間的DTW距離.輪廓系數(shù)的值越大，說明同類樣本相距越近，不同樣本相距越遠(yuǎn)，聚類效果越好.使得有效性指標(biāo)最大的聚類中心集合即是算法求得的所有聚類中心.

當(dāng)聚類數(shù)為i時(shí)，在與已有聚類中心{p1,p2,…,pi?1}的距離之和最大的v個(gè)子序列中找出密度最大的異常子序列作為第i個(gè)聚類中心pi，把每個(gè)剩余異常子序列分配給距離其最近的聚類中心.計(jì)算此時(shí)的輪廓系數(shù)sili，若sili

Fig.5 Schematic diagram of anomaly subsequence distribution圖5 異常子序列分布示意圖

2.3 APAKN算法步驟

算法 1.APAKN 算法.

輸入：子序列數(shù)據(jù)集D={s1,s2,…,si,…,sN}；

輸出：異常模式集合P={p1，p2,…,pi,…,pc}.

步驟1.對(duì)于數(shù)據(jù)集D={s1,s2,…,si,…,sN}，計(jì)算所有子序列之間的DTW距離并將其存放在距離存儲(chǔ)單元中以便隨時(shí)調(diào)用，利用子序列距離搜索子序列si(i=1,2,…,N)的自適應(yīng)k近鄰值.

步驟2.將k值集合 {k1,k2,…,kN}中的最大值km代入式(6)計(jì)算所有子序列的相對(duì)密度，計(jì)算異常分?jǐn)?shù)和確定異常閾值，將異常分?jǐn)?shù)大于異常閾值的子序列檢測(cè)為異常子序列

步驟3.重新搜索異常子序列s?的自適應(yīng)k值j將其作為的密度，根據(jù)所得密度和距離存儲(chǔ)單元中的子序列距離迭代地獲取聚類中心，并根據(jù)式(13)中的輪廓系數(shù)判斷迭代停止時(shí)聚類中心的個(gè)數(shù)c.

步驟4.輸出聚類中心集合，即異常模式集合P={p1,p2,…,pi,…,pc}.

2.4 時(shí)間復(fù)雜度

APAKN算法采用DTW 度量所有子序列之間的距離，該步驟的最大時(shí)間復(fù)雜度為，其中數(shù)據(jù)集中子序列數(shù)為N, 所有子序列長(zhǎng)度都為l；異常子序列檢測(cè)步驟的最大時(shí)間復(fù)雜度為其中km為所有子序列自適應(yīng)k值集合中的最大值；異常子序列聚類步驟的最大時(shí)間復(fù)雜度為，其中，n為異常子序列的個(gè)數(shù).可見，APAKN算法的時(shí)間復(fù)雜度為由于NlogN++nlogn?N2l2，算法的時(shí)間復(fù)雜度可以表示為

3 實(shí)驗(yàn)與結(jié)果

為了更好地驗(yàn)證所提出算法的有效性，采用了美國(guó)加州大學(xué)濱河分校 (University of California Riverside，UCR)的時(shí)間序列數(shù)據(jù)集合[30]中的10個(gè)通用數(shù)據(jù)集作為實(shí)驗(yàn)對(duì)象對(duì)本文算法進(jìn)行實(shí)驗(yàn)評(píng)估.由于APAKN算法主要是由異常子序列檢測(cè)和異常子序列聚類2個(gè)方面組成，因此實(shí)驗(yàn)部分也將從這2個(gè)方向來(lái)進(jìn)行評(píng)價(jià).實(shí)驗(yàn)環(huán)境均為 Win 10 64 b 操作系統(tǒng)，Python 3.7.6 軟件，8 GB 內(nèi)存，Intel(R) Core(TM)，i5-4200H CPU@2.80 GHz 處理器.

3.1 實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)所用數(shù)據(jù)為 10 個(gè)公開的UCR數(shù)據(jù)集，由于UCR數(shù)據(jù)集中并未標(biāo)出各類子序列是否異常，所以我們選擇子序列個(gè)數(shù)最多的一類作為正常類，隨機(jī)選擇其他幾類中的若干子序列組成異常類，使各數(shù)據(jù)集的異常率不同.表3列出了本次實(shí)驗(yàn)中各數(shù)據(jù)集的詳細(xì)信息.以50words數(shù)據(jù)集為例，原數(shù)據(jù)集包含50個(gè)類別，其中類別號(hào)為2的子序列簇包含最多的子序列且被選作正常類，類別號(hào)為4,10,43的子序列簇被選作異常類，從中隨機(jī)選擇若干子序列作為實(shí)驗(yàn)中的異常子序列.

Table 3 Experimental Data Sets表3 實(shí)驗(yàn)數(shù)據(jù)集

3.2 異常子序列檢測(cè)

3.2.1 評(píng)價(jià)指標(biāo)

本節(jié)使用準(zhǔn)確率(Accuracy)、精確率(Precision) 、召回率(Recall) 、F值作為性能評(píng)價(jià)指標(biāo)來(lái)評(píng)價(jià)本算法中異常子序列檢測(cè)部分的性能，分別定義為:

其中，TP被定義為將異常子序列檢測(cè)為異常子序列的個(gè)數(shù)；FP為把非異常子序列檢測(cè)為異常子序列的個(gè)數(shù)；FN為將異常子序列檢測(cè)為非異常子序列的個(gè)數(shù)；TN表示將非異常子序列正確檢測(cè)為非異常子序列的個(gè)數(shù).

準(zhǔn)確率代表的是所有正確預(yù)測(cè)的樣本數(shù)占總樣本數(shù)的比重；精確率衡量算法的查準(zhǔn)率，即正確預(yù)測(cè)為異常子序列占全部預(yù)測(cè)為異常子序列的比例；召回率衡量算法的查全率，即正確預(yù)測(cè)為一場(chǎng)子序列占全部實(shí)際為異常子序列的比例；F值則為精確率和召回率的調(diào)和平均數(shù)，同時(shí)兼顧算法的精確率和召回率，F(xiàn)度量值的大小反映了聚類結(jié)果的精度，它是一個(gè)介于?1和1之間的值，該值越接近1，算法的精度就越高.

3.2.2 實(shí)驗(yàn)結(jié)果

為了證明APAKN算法的優(yōu)異，圖6將算法異常子序列檢測(cè)部分在10個(gè)數(shù)據(jù)集上的部分實(shí)驗(yàn)結(jié)果可視化地表示出來(lái).圖6中共包含代表著10個(gè)數(shù)據(jù)集的10個(gè)子圖，每個(gè)子圖由2個(gè)部分組成：時(shí)間子序列和子序列異常分?jǐn)?shù).以50words數(shù)據(jù)集為例，該數(shù)據(jù)集的子序列長(zhǎng)度為270，我們從類別號(hào)為4,10,43這3個(gè)異常子序列簇中分別選擇了3個(gè)子序列，從類別號(hào)為2的正常子序列簇中選擇若干子序列，將這些子序列的異常得分在圖6 (a)中顯示出來(lái).如圖6 (a)所示，異常子序列的異常分?jǐn)?shù)遠(yuǎn)遠(yuǎn)高于正常子序列的異常分?jǐn)?shù).此外，對(duì)數(shù)據(jù)集的其他子序列都分配了一個(gè)異常分?jǐn)?shù)來(lái)度量它們的異常程度.

為了驗(yàn)證提出的異常模式識(shí)別算法APAKN在異常子序列檢測(cè)部分的性能, 本文比較了APAKN與DBAD[13]，SFO[15]，DLDE[18]算法在各數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果.APAKN利用自適應(yīng)k近鄰搜索算法自動(dòng)確定各子序列的最佳近鄰值 {k1,k2,…,kN}，km為近鄰集合中的最大值；異常子序列檢測(cè)部分的對(duì)比算法DBAD遞歸計(jì)算擬合分布均值方差，需要人為設(shè)置遞歸參數(shù)t；SFO需要人為設(shè)置近鄰參數(shù)k；DLDE構(gòu)造Hash表以加快估計(jì)子序列的局部密度，需人為設(shè)置參數(shù)Hash值h.為了突出顯示本文算法的優(yōu)越性能，在10個(gè)實(shí)驗(yàn)數(shù)據(jù)集上，對(duì)3個(gè)對(duì)比算法分別進(jìn)行多次實(shí)驗(yàn)，最終選出一個(gè)使其對(duì)應(yīng)檢測(cè)結(jié)果最優(yōu)的參數(shù)值作為其最佳參數(shù)，分別記為topt，kopt，hopt.APAKN算法得到的自適應(yīng)k值中的最大值km以及對(duì)比算法相應(yīng)的topt，kopt，hopt如表4所示.

Fig.6 UCR partial time subsequences and anomaly scores圖6 UCR部分時(shí)間子序列及其異常得分

此外，APAKN提出基于最小方差的自適應(yīng)閾值方法確定異常閾值；SFO算法利用統(tǒng)計(jì)假設(shè)檢驗(yàn)方法判斷數(shù)據(jù)是否異常，其計(jì)算較為復(fù)雜；而DLDE算法只是對(duì)所有數(shù)據(jù)對(duì)象按異常分?jǐn)?shù)值降序排序，人為選擇異常分?jǐn)?shù)值最大的幾個(gè)數(shù)據(jù)對(duì)象作為異常對(duì)象，該閾值選擇方法需要實(shí)驗(yàn)者熟悉各數(shù)據(jù)集，并且對(duì)不同數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)時(shí)需要置換閾值參數(shù)，使實(shí)驗(yàn)過程更為繁瑣.DBAD利用均值和方差確定異常閾值，同樣需要人為設(shè)置閾值參數(shù).本次實(shí)驗(yàn)利用較為常見的 3 σ準(zhǔn)則作為DBAD和DLDE算法的異常閾值T=u+3σ.基于表4的最佳參數(shù)，表5和表6分別給出了4種算法在異常子序列檢測(cè)部分的精確率和召回率以及準(zhǔn)確率和F值.

表5給出了4種算法在10個(gè)數(shù)據(jù)集上異常子序列檢測(cè)的精確率和召回率對(duì)比，表6則給出了異常子序列檢測(cè)部分的準(zhǔn)確率和F值對(duì)比, 可以看出，APAKN在10個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果皆具有最佳性能.此外，DBAD算法有1個(gè)最佳精確率和1個(gè)最佳召回率；SFO有6個(gè)最佳召回率；DLDE有4個(gè)最佳精確率.由上述實(shí)驗(yàn)結(jié)果可以判斷出，相較于其他算法，本文算法不僅具有很強(qiáng)的自適應(yīng)性，而且具有很高的異常子序列檢測(cè)水平.

Table 4 km Value of APAKN and the Optimal Parameter Values of Comparison Algorithms表4 APAKN的 km 值和對(duì)比算法的最佳參數(shù)值

3.3 異常子序列聚類

3.3.1 評(píng)價(jià)指標(biāo)

本文利用調(diào)整蘭德系數(shù) (adjusted rand index, ARI)[31]和標(biāo)準(zhǔn)化互信息 (normalized mutual information, NMI)[32]兩種衡量標(biāo)準(zhǔn)對(duì)異常子序列聚類結(jié)果進(jìn)行評(píng)判.這2個(gè)衡量標(biāo)準(zhǔn)的上限均為1，該值越接近1，表示該聚類算法的準(zhǔn)確率越高，算法聚類結(jié)果越好.

Table 5 Comparison of Accuracy and Recall of Each Algorithm on 10 Data Sets表5 各算法在 10 個(gè)數(shù)據(jù)集上的精確率和召回率對(duì)比

Table 6 Comparison of Accuracy and F Value of Each Algorithm on 10 Data Sets表6 各算法在 10 個(gè)數(shù)據(jù)集上的準(zhǔn)確率和F值對(duì)比

調(diào)整蘭德系數(shù)值EARI定義為

其中na表示在算法聚類結(jié)果中為同一類、在數(shù)據(jù)集真實(shí)聚類中也為同一類的子序列對(duì)數(shù)；nb表示在算法聚類結(jié)果中為同一類、在數(shù)據(jù)集真實(shí)聚類中不為同一類的子序列對(duì)數(shù)；nc表示在算法聚類結(jié)果中不為同一類、在數(shù)據(jù)集真實(shí)聚類中為同一類的子序列對(duì)數(shù)；nd表示在算法聚類結(jié)果中不為同一類、在數(shù)據(jù)集真實(shí)聚類中也不為同一類的子序列對(duì)數(shù).

標(biāo)準(zhǔn)化互信息值ENMI定義為

其中cA表 示算法聚類結(jié)果的聚類類別數(shù)，cB表示數(shù)據(jù)集本質(zhì)聚類類別數(shù)，nij表 示子序列屬于真實(shí)標(biāo)簽類j但被劃分到聚類結(jié)果簇i中的個(gè)數(shù)，ni表示聚類結(jié)果類i中子序列的個(gè)數(shù)，nj表示真實(shí)標(biāo)簽類j中子序列的個(gè)數(shù).

3.3.2 實(shí)驗(yàn)結(jié)果

為了證明APAKN算法的優(yōu)異, 圖7和圖8分別將算法異常子序列聚類部分在50words和CBF數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果可視化地表示出來(lái).圖7包含代表著3類異常子序列的異常子序列示例和聚類算法下生成的簇質(zhì)心即異常模式.通過圖7中不同類別下的異常子序列的示例可以看出，同一類別下的異常子序列具有相同的趨勢(shì).從異常模式圖可以看出算法得到的質(zhì)心很好地表征了每個(gè)類別的趨勢(shì)特征.

在異常子序列聚類部分，本文選擇了kmlShape[21]，DDC[23]，KShape[24]算法進(jìn)行性能比較.APAKN的聚類部分同樣無(wú)需設(shè)置任何參數(shù)，而為了更好地顯示出算法的優(yōu)異性，對(duì)3種對(duì)比算法都進(jìn)行了參數(shù)調(diào)優(yōu).由于kmlShape算法選取的初始類簇中心不同，則聚類結(jié)果也不同，對(duì)每個(gè)數(shù)據(jù)集進(jìn)行多次重復(fù)實(shí)驗(yàn), 取其中最好的結(jié)果.kmlShape，DDC，KShape算法需要給定類簇個(gè)數(shù)，為這3種算法分別選出一個(gè)使評(píng)價(jià)指標(biāo)最優(yōu)的參數(shù)作為其聚類個(gè)數(shù).表7為APAKN的異常子序列聚類部分在10個(gè)UCR數(shù)據(jù)集上與kmlShape，DDC，KShape這3種算法的聚類結(jié)果對(duì)比.

通過表7可知，即使已經(jīng)給定了對(duì)比算法的最佳參數(shù)，kmlShape，DDC，KShape算法的聚類結(jié)果還是波動(dòng)較大, DDC聚類效果不佳.kmlShape算法在FaceAll，Trace，CBF，Synthetic_Control數(shù)據(jù)集上的性能值較優(yōu)，在其他數(shù)據(jù)集上的表現(xiàn)不佳；KShape算法在 50words，ECG5000，Lighting7，CBF 數(shù)據(jù)集上表現(xiàn)較好.但從總體上來(lái)看，APAKN在各個(gè)數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)值大部分都要優(yōu)于與之比較的算法，其余指標(biāo)均值與最佳指標(biāo)值相差不大.

Fig.7 Examples of anomaly subsequences and anomaly patterns in different categories of the 50words dataset圖7 50words數(shù)據(jù)集在不同類別下的異常子序列示例和異常模式

Fig.8 Examples of anomaly subsequences and anomaly patterns in different categories of the CBF dataset圖8 CBF數(shù)據(jù)集在不同類別下的異常子序列示例和異常模式

Table 7 Comparison of ARI and NMI of Each Algorithm on 10 Data Sets表7 各算法在 10 個(gè)數(shù)據(jù)集上的ARI和NMI對(duì)比

因此，結(jié)合異常子序列檢測(cè)與異常子序列聚類2部分的實(shí)驗(yàn)結(jié)果, 可以驗(yàn)證出算法APAKN是有效可行的.

4 結(jié) 論

本文提出了基于自適應(yīng)k近鄰的異常模式識(shí)別算法APAKN，該算法在無(wú)需任何參數(shù)輸入的情況下，不僅檢測(cè)異常子序列，還區(qū)分出異常子序列的不同類別，重新定義了異常模式.采用自適應(yīng)k近鄰搜索算法獲取子序列的自適應(yīng)k近鄰值，解決傳統(tǒng)k近鄰算法的參數(shù)設(shè)置問題；提出一種基于最小方差的自適應(yīng)閾值方法解決閾值選擇問題；APAKN通過密度與距離結(jié)合的思想尋找最優(yōu)聚類中心，并利用輪廓系數(shù)得到聚類數(shù)，從而實(shí)現(xiàn)異常子序列的快速聚類.在UCR數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明了APAKN算法的自適應(yīng)性與有效性.下一階段我們將考慮如何從距離度量方面減少算法的時(shí)間復(fù)雜度以期望提高算法的效率.

作者貢獻(xiàn)聲明：王玲提出文章的算法思路設(shè)計(jì)，對(duì)論文的邏輯性以及算法的合理性進(jìn)行指導(dǎo)；周南負(fù)責(zé)文章的定理和論證過程，以及實(shí)驗(yàn)部分的算法實(shí)現(xiàn)與實(shí)驗(yàn)結(jié)果分析；申鵬對(duì)文章整體格式進(jìn)行修改.