閆欣鳴，孟凡榮，閆秋艷

(中國礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

(*通信作者電子郵箱yanxm@cumt.edu.cn)

基于趨勢特征表示的shapelet分類方法

閆欣鳴*，孟凡榮，閆秋艷

(中國礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

(*通信作者電子郵箱yanxm@cumt.edu.cn)

Shapelet是一種具有辨識性的時(shí)間序列子序列，通過識別局部特征達(dá)到對時(shí)間序列準(zhǔn)確分類的目的。原始shapelet發(fā)現(xiàn)算法效率較低，大量工作關(guān)注于提高shapelet發(fā)現(xiàn)的效率。然而，對于帶有趨勢變化的時(shí)間序列，采用典型的時(shí)間序列表示方法進(jìn)行shapelet發(fā)現(xiàn)，容易造成序列中趨勢信息的丟失。為了解決時(shí)間序列趨勢信息丟失的問題，提出一種基于趨勢特征的多樣化top-kshapelet分類方法：首先采用趨勢特征符號化方法對時(shí)間序列的趨勢信息進(jìn)行表示；然后針對序列的趨勢特征符號獲取shapelet候選集合；最后通過引入多樣化top-k查詢算法從候選集中選取k個(gè)最具代表性的shapelets。在時(shí)間序列的分類實(shí)驗(yàn)中，與傳統(tǒng)分類算法相比，所提方法在11個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率均有提升；與FastShapelet算法相比，提升了運(yùn)行效率，縮短了算法的運(yùn)行時(shí)間，并在趨勢信息明顯的數(shù)據(jù)上效果顯著。結(jié)果表明，所提方法能有效提高時(shí)間序列的分類準(zhǔn)確率，提升算法運(yùn)行效率。

shapelet；趨勢特征；符號化；多樣化top-k查詢; 時(shí)間序列分類

0 引言

近些年來，人們對于時(shí)間序列數(shù)據(jù)挖掘的興趣越來越濃厚。其中大多數(shù)的研究是基于不同距離度量方法的最近鄰算法，如歐氏距離、動態(tài)時(shí)間歸整(Dynamic Time Warping，DTW)等。2009年，Keogh等提出了shapelet的概念[1]，引起了廣泛的關(guān)注，并在時(shí)間序列的分類[2]和聚類[3]等領(lǐng)域有了廣泛的應(yīng)用。通俗來講，shapelet是時(shí)間序列的子序列，是時(shí)間序列中具有辨識度的局部特征，它在某種意義上能夠最大限度地代表一個(gè)類，并據(jù)此很好地區(qū)分兩類間的不同[4]。原始的shapelet分類方法是利用shapelet構(gòu)造決策樹，這種分類方法相比最近鄰算法(Nearest Neighbor Algorithm， 1NN)有較大提高，然而它并不能勝任多分類問題。2012年，Lines等在文獻(xiàn)[5]中利用shapelet對原始數(shù)據(jù)集進(jìn)行轉(zhuǎn)換，使用這種方法，能夠?qū)υ嫉臅r(shí)間序列降維，并將shapelet發(fā)現(xiàn)與構(gòu)造分類器分離開來，而后利用轉(zhuǎn)換后的數(shù)據(jù)與其他分類器結(jié)合使用，從而克服了原始shapelet方法在多分類問題上的不足。2014年，原繼東等在文獻(xiàn)[6]中提出了基于shapelet的剪枝和覆蓋算法，對降低shapelet集合的冗余性作出了改進(jìn)。

由于時(shí)間序列通常是連續(xù)的高維數(shù)據(jù)，許多研究者采用時(shí)間序列符號化方法對時(shí)間序列進(jìn)行離散化、降維[7]。2007年，Lin等在文獻(xiàn)[8]中提出了符號聚集近似(Symbolic Aggregate approXimation，SAX)算法，SAX因其簡易高效的特性而廣受歡迎。2013年，Keogh等在文獻(xiàn)[9]中提出了快速shapelet算法，通過將時(shí)間序列進(jìn)行SAX符號化表示，利用生物信息學(xué)中的隨機(jī)規(guī)劃[10]算法評判shapelet的分值，大大提高了shapelet發(fā)現(xiàn)的效率。

然而，現(xiàn)實(shí)生活中帶有趨勢變化的時(shí)間序列挖掘?qū)ξ覀兲岢隽诵碌奶魬?zhàn)，例如：股票數(shù)據(jù)、天氣數(shù)據(jù)、居民用電量等，此類數(shù)據(jù)中的趨勢信息對于發(fā)現(xiàn)特殊事件的發(fā)展規(guī)律和對異常事件預(yù)測預(yù)警，具有重要意義。典型的時(shí)間序列符號化表示方法，如分段聚集近似(Piecewise Aggregate Approximation， PAA)，SAX等，均使用平均值對序列的分段特征進(jìn)行表示，對于時(shí)間序列的趨勢特征，如上升(下降)、角度、幅度等信息，則無能為力。

為了解決現(xiàn)有shapelet分類方法無法有效表示時(shí)間序列趨勢特征的問題，本文提出了一種基于趨勢特征的多樣化top-kshapelet分類方法，該方法首先采用趨勢特征符號化方法對時(shí)間序列的趨勢信息進(jìn)行表示；然后針對序列的趨勢特征符號獲取shapelet候選集合；最后通過引入多樣化top-k查詢算法[11]從候選集中選取k個(gè)最具代表性的shapelets[12]。實(shí)驗(yàn)部分分別選取公測數(shù)據(jù)和實(shí)際數(shù)據(jù)，將本文方法與對比算法進(jìn)行比較，結(jié)果表明本文算法針對具有趨勢特征的時(shí)間序列數(shù)據(jù)具有更好的分類效果。

1 相關(guān)定義

表1總結(jié)了本文涉及的相關(guān)符號，并于下文對其進(jìn)行了詳細(xì)釋義。

表1 符號表Tab.1 Symbol table

定義1 時(shí)間序列。時(shí)間序列T=t1,t2,…,tm是一段時(shí)間等間隔的實(shí)值序列，m是時(shí)間序列的長度。

定義2 子序列。一條時(shí)間序列的子序列S=tp,tp+1,…,tp+l-1是T上一段連續(xù)的序列，p是開始位置，l代表長度。

定義3 時(shí)間序列間的距離。對于兩條時(shí)間序列T和Q，定義T和Q之間的距離為：

定義5 分裂點(diǎn)[1]。分裂點(diǎn)〈S,d〉是一個(gè)二元組，其中S為時(shí)間序列子序列，d為距離閾值。分裂點(diǎn)表示存在某一距離閾值d使得數(shù)據(jù)集D被其分為兩個(gè)數(shù)據(jù)集DL和DR，并且對于所有的TL和TR都有SubseqDist(S,TL)

定義6 信息增益。一個(gè)分裂點(diǎn)〈S,d〉的信息增益為：

其中E(D)表示數(shù)據(jù)集D的熵，計(jì)算公式如下：

E(D)=-∑p(Ci) lb (p(Ci))

定義7 shapelet[1]。是一個(gè)最優(yōu)分裂點(diǎn)，采用信息增益作為量度，能夠?qū)?shù)據(jù)集D一分為二，并且使得最終的信息增益最大，即滿足IG(〈shapelet,dosp〉)≥IG(〈S,d〉),其中IG為該分裂點(diǎn)的信息增益。

定義8 shapelet相似[6]。對于任意兩個(gè)shapelet 〈S1,d1〉和〈S2,d2〉，若SubseqDist(S1,S2)

定義9 多樣化top-k查詢[11]。給定一個(gè)查找集合I={v1,v2,…}和一個(gè)正整數(shù)k，其中對于任意vi∈I，vi的分?jǐn)?shù)可以表示為score(vi),并且1≤k≤|I|。定義多樣化top-k查詢結(jié)果D(I)滿足以下條件：

1)D(I)?I并且|D(I)|≤k;

2)對于任意兩個(gè)結(jié)果vi∈I和vj∈I，并且vi≠vj，如果vi與vj相似，那么vi和vj不同屬于D(I);

定義10 多樣化圖[11]。給定一個(gè)查找集合I={v1,v2,…}，其多樣化圖表示為無向圖G(I)=(V,E)，其中V是I中所有變量組成的頂點(diǎn)集合，若vi與vj相似，則兩點(diǎn)間有一條邊，記為E。為了不失一般性，假定G(I)中的點(diǎn)都是以其分?jǐn)?shù)非遞增排列的，即1≤i

定義11 多樣化top-kshapelets[12]。在候選shapelets集合I={S1,S2,…,Sn}中，滿足下列條件的k個(gè)shapelets，將其表示為DivTopk(I)：

1)DivTopk(I)?I,|DivTopk(I)|≤k;

2)對于任意兩個(gè)shapelets，Si,Sj∈I,Si≠Sj，如果Si和Sj相似，則Si和Sj不同屬于DivTopk(I);

2 趨勢特征表示的shapelet分類方法

本文給出一種基于趨勢特征的多樣化top-kshapelet分類方法(Trend-based Diversified top-kShapelet， TDTS)，算法主要分為三個(gè)部分：1)對序列進(jìn)行趨勢特征符號化，并進(jìn)行shapelets發(fā)現(xiàn)；2)對產(chǎn)生的shapelets候選集進(jìn)行多樣化top-k查詢，選出k個(gè)最具代表性的shapelets；3)使用shapelet轉(zhuǎn)換技術(shù)對原始數(shù)據(jù)集進(jìn)行轉(zhuǎn)換，并利用轉(zhuǎn)換后的數(shù)據(jù)集進(jìn)行分類。算法偽代碼見算法1。

算法1 TDTS。

輸入 數(shù)據(jù)集D；

輸出 分類結(jié)果R。

1)

allShapelets=?

2)

allShapelets=ShapeletCandidates(D,min,max)

3)

kShapelets=DivTopkSearch(allShapelets,k)

4)

R=ShapeletConvert(kshapelets,D)

5)

returnR

2.1 帶有趨勢特征的快速shapelet發(fā)現(xiàn)算法

本文進(jìn)行shapelet發(fā)現(xiàn)主要利用趨勢特征符號化的方法對時(shí)間序列進(jìn)行降維處理,并保留序列的趨勢信息，再對序列進(jìn)行快速shapelet發(fā)現(xiàn)，以保證shapelet發(fā)現(xiàn)的運(yùn)行效率，具體流程如圖1，其中TFSA序列表示趨勢特征符號化后的符號化序列，即后文中算法2的返回結(jié)果。

圖1 趨勢shapelet快速發(fā)現(xiàn)過程Fig. 1 Process of trendy shapelet quick discovery

2.1.1 時(shí)間序列的趨勢特征符號化

由于時(shí)間序列大多帶有趨勢信息，所以在對時(shí)間序列進(jìn)行符號化時(shí)需要考慮這些趨勢特征。文獻(xiàn)[9]中使用SAX對時(shí)間序列進(jìn)行符號化處理，這種方法較為簡潔，實(shí)現(xiàn)了高維到低維、實(shí)值到離散的轉(zhuǎn)化。但是使用SAX方法對序列符號化并不能有效地保留時(shí)間序列的趨勢信息，因此本文引入文獻(xiàn)[13]中基于趨勢特征的時(shí)間序列的符號化方法，對原始時(shí)間序列進(jìn)行趨勢特征符號化。

在趨勢特征符號化的過程中，首先對要符號化的序列進(jìn)行分段，所有分段點(diǎn)用u表示。分段過后，將每一段分割后的序列對應(yīng)成一個(gè)二元組〈K,u〉，其中：K是該段序列的斜率，其符號代表了該段序列的趨勢，正表示上升趨勢，負(fù)表示下降趨勢，0保持平穩(wěn)；u是該段序列的終點(diǎn)值，即分段過程產(chǎn)生的分段點(diǎn)，最后一段序列的終點(diǎn)值即為整條序列的終點(diǎn)值。對每一段分割后的序列計(jì)算出其對應(yīng)的二元組值，即完成符號化。斜率K的計(jì)算如下:

(1)

其中：x表示該段序列的長度，vj表示時(shí)間戳tj在序列中對應(yīng)的值。

圖2給出了趨勢特征符號化的一個(gè)示例。符號化方法使用滑動窗口機(jī)制計(jì)算窗口內(nèi)序列的斜率，當(dāng)斜率的變化(即角度angle)超過一定閾值時(shí)，產(chǎn)生一個(gè)分段點(diǎn)ui，并繼續(xù)滑動窗口，以此類推。找出所有分段點(diǎn)后，對每一段序列進(jìn)行符號化。在對每一段待符號化序列符號化的過程中，本文首先參考了文獻(xiàn)[13]中的離散方法，將斜率值K離散地對應(yīng)到集合{x|x=-9,-8, …，8,9}中，表示斜率值K在該離散值對應(yīng)的區(qū)間內(nèi)，例如當(dāng)離散化后的斜率值K=5時(shí)，表示該段序列與x軸的夾角在(40°,50°)區(qū)間范圍內(nèi)；當(dāng)K=-5時(shí)，表示序列與x軸夾角在(-50°,-40°)區(qū)間范圍內(nèi)；當(dāng)K=0時(shí)，與x軸夾角為0°。而后參考了文獻(xiàn)[8]中的符號化方法，將終點(diǎn)值u映射到集合{x|x=a,b,c,d}中，從而完成整個(gè)符號化過程。即將每一段序列對應(yīng)成一個(gè)二元組〈K,u〉，記為q，qi表示分段后第i段序列的趨勢特征符號化結(jié)果，即qi=〈Ki，ui〉，詳細(xì)過程見算法2。

圖2 趨勢特征符號化示意圖Fig. 2 Symbolization of trend feature

算法2 CreateTFSAList。

輸入 數(shù)據(jù)集D，分段點(diǎn)個(gè)數(shù)num，閾值τ。

輸出 TFSA序列集。

1) Forid=1 ton

2)U=?

3)l=m/num

4)S1=subseq(Tid,1,l)

5)K1=slope(S1)

6) Fori=1 tom-l

7)S2=subseq(Tid,i+1,l)

8)K2=slope(S2)

9) If |K1-K2|>τ

10)U←l+i-1

11)i=update(i)

12) >S1=subseq(Tid,i,l)

13)K1=slope(S1)

14) Else

15)K1=(K1+K2)/2

16) End For

17)TFSAList← Symbolization(U)

18) End For

19) ReturnTFSAList

算法中n表示數(shù)據(jù)集D中的時(shí)間序列個(gè)數(shù)，m表示每條時(shí)間序列的長度，Tid表示D中第id條時(shí)間序列。第一步，設(shè)置滑動窗口大小(第3)行)；第二步，計(jì)算第一個(gè)窗口內(nèi)序列的K1(第4)～5)行)；第三步，滑動窗口，計(jì)算斜率K2，并計(jì)算兩斜率的差，如果差值大于一定閾值，則認(rèn)為序列趨勢有變化，記一分段點(diǎn)ui，反之將兩段序列合為一段，記K1=(K1+K2)/2，并反復(fù)執(zhí)行此步驟，直至窗口滑動到序列結(jié)束，得出所有分段點(diǎn)(第6)～16)行)；第四步，依據(jù)分段點(diǎn)，將每個(gè)子序列進(jìn)行符號化，符號化后的信息包括序列斜率和終點(diǎn)值的符號化表示形式(第17)行)。最后返回已經(jīng)趨勢特征符號化的TFSA序列集。

2.1.2 保持趨勢特征的shapelet發(fā)現(xiàn)算法

在對原始數(shù)據(jù)進(jìn)行趨勢特征符號化后，將其與原始FastShapelet算法[9]結(jié)合，在原數(shù)據(jù)的趨勢符號化表示的基礎(chǔ)上對其進(jìn)行shapelet發(fā)現(xiàn)，具體內(nèi)容見算法3。圖3給出了一個(gè)基于趨勢特征表示的快速shapelet發(fā)現(xiàn)的示例。該算法隨機(jī)覆蓋序列的子序列，然后對未覆蓋的子序列進(jìn)行Hash碰撞檢測，碰撞后得出圖3右側(cè)的碰撞頻次，最后通過對碰撞頻次的分析(具體分析方法見文獻(xiàn)[9])，選出候選的shapelet。由于該方法選出的shapelet在自身所在類中碰撞頻次較高且在其他類中碰撞頻次較低，因此該shapelet更具有代表性。

圖3 趨勢快速shapelet發(fā)現(xiàn)示意圖Fig. 3 Illustration of trendy shapelet fast discovery

算法3 ShapeletCandidates。

輸入 數(shù)據(jù)集D，最小長度min，最大長度max，投影次數(shù)r;

輸出 Shapelet候選集allShapelets。

1)allShapelets=?

2) forlen=mintomax

3)TFSAList=CreateTFSAList(D,len)

4)Score={}

5) Forj=1 tor

6)Count=RandProjection(TFSAList,D)

7)Score=UpdateScore(Score,Count)

8) End For

9)KTFSACand=FindTopKTFSA(ScoreList,Score，M)

10)KShapeletCand=Remap(KTFSACand,D)

11) Fori=1 to |KShapeletCand|

12) CalInfoGain(Shapelet[i],D)

13) End For

14) All Shapelet.add(KShapeletCand)

15) End For

16) ReturnallShapelets

算法3中，首先對原始時(shí)間序列數(shù)據(jù)進(jìn)行趨勢特征符號化，產(chǎn)生指定長度的TFSA序列(具體過程見算法1)，將其放入列表中(第3)行)；之后，在產(chǎn)生的TFSA序列集上進(jìn)行隨機(jī)覆蓋，對每一個(gè)TFSA序列產(chǎn)生一個(gè)碰撞頻次，根據(jù)碰撞頻次計(jì)算出該序列的分值(第5)～8)行)；接著根據(jù)分值選取最好的M個(gè)TFSA序列，作為候選TFSA序列，并將其重新映射到原數(shù)據(jù)集上，產(chǎn)生候選shapelets，然后對所有候選shapelets計(jì)算信息增益，并將其加入到shapelets集合中(第9)～14)行)；最后返回所有候選的shapelets。其中r是投影次數(shù)，表示算法進(jìn)行了r次隨機(jī)映射，本文中設(shè)r=10，M=10。

2.2 多樣化top-k shapelets查詢

top-k查詢通常是在列表中直接按分值查詢最優(yōu)的k個(gè)結(jié)果，但這種方法并沒有考慮到結(jié)果之間的相似性。在前文中提到的shapelets發(fā)現(xiàn)算法中，得到shapelets候選集，而這些shapelets間存在許多相似shapelets，由于shapelet是能夠最大程度代表一個(gè)類的時(shí)間序列子序列，如果直接選取k個(gè)最優(yōu)的shapelets，那么使用相似的shapelets進(jìn)行分類可能使其失去了代表性。因此參考文獻(xiàn)[11]中的多樣化top-k查詢，得出本文使用的多樣化top-kshapelets查詢[12,14]，算法流程見圖4，詳細(xì)過程見算法4。

圖4 多樣化top-kshapelets查詢過程

Fig. 4 Process of diversified top-kshapelets query

算法4 DivTopkSearch。

輸入 shapelets候選集allShapelets，k值。

輸出k個(gè)shapelets。

1)Graph=?

2) sort(allShapelets)

3) Fori=1 to |allShapelets|

4)Graph.add(allShapelets[i])

5) End For

6) Forj=1 to |allShapelets|

7) Fork=1 to |allShapelets|

8) If(allShapelets[j]≈allShapelets[k])

9)Graph[j].add(Graph[k])

10)Graph[k].add(Graph[j])

11) End For

12) End For

13)kShapelets=?,n=|V(Graph)|

14)kShapelets.add(v1)

15) while(|kShapelets|

16) Fori=2 ton

17) If(vi.adj(Graph)∩kShapelets=?)

18)kShapelets.add(vi)

19) End If

20) End For

21) returnkShapelets

算法由兩部分構(gòu)成。第一部分，構(gòu)造多樣化shapelets圖(第1)～12)行)。首先對算法1中得到的所有shapelets根據(jù)其信息增益進(jìn)行排序，并將其作為點(diǎn)加入圖中(第1)～5)行)；接著依次遍歷所有shapelets，判斷與其他shapelets是否相似，如若相似，在兩點(diǎn)間構(gòu)造一條邊(第6)～12)行)。這樣便完成了多樣化shapelets圖的構(gòu)造。第二部分，查詢多元化top-kshapelets(第13)～21)行)。首先將信息增益最大的shapelet(v1)放到kShapelets集合中(第14)行)。如果k=1，此時(shí)算法將會結(jié)束，并返回該shapelet；否則，對于多元化圖中的其他節(jié)點(diǎn)，如果該節(jié)點(diǎn)的鄰接節(jié)點(diǎn)都不在kShapelets中，就可以將該節(jié)點(diǎn)加入到kShapelets中(第15)～20)行)。最后返回k個(gè)多元化shapelets(第21)行)。

2.3 shapelet轉(zhuǎn)換分類方法

在得到所有shapelets候選集后，采用shapelet轉(zhuǎn)換技術(shù)對原始數(shù)據(jù)集進(jìn)行轉(zhuǎn)換[5]。轉(zhuǎn)換過程中計(jì)算時(shí)間序列與所有shapelets的距離，記為新的一條時(shí)間序列。將傳統(tǒng)的分類方法應(yīng)用于轉(zhuǎn)換后的數(shù)據(jù)集進(jìn)行分類，得出分類結(jié)果。

2.4 算法時(shí)間復(fù)雜度分析

算法首先進(jìn)行時(shí)間序列的趨勢特征符號化，其時(shí)間復(fù)雜度為O(nm)，其中n表示時(shí)間序列的個(gè)數(shù)，m表示時(shí)間序列的長度；而后使用快速shapelet發(fā)現(xiàn)算法進(jìn)行shapelet發(fā)現(xiàn)，其時(shí)間復(fù)雜度為O(nm2)；而多樣化Top-kshapelets查詢的時(shí)間復(fù)雜度為O(p2)，p為候選shapelets個(gè)數(shù)。因此，算法總體時(shí)間復(fù)雜度為O(nm2)+O(p2)。

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

3.1 實(shí)驗(yàn)說明

通過對算法的設(shè)計(jì)與實(shí)現(xiàn)，現(xiàn)利用算法對合適的數(shù)據(jù)集進(jìn)行分類以驗(yàn)證其效果，數(shù)據(jù)集的選取將在3.2節(jié)詳細(xì)介紹。算法首先通過與原始時(shí)間序列分類方法對比，以驗(yàn)證shapelet分類的有效性；而后對比本文算法與FastShapelet算法的效果，以驗(yàn)證趨勢特征符號化在提高分類準(zhǔn)確度上的有效性。由于算法需要選取k個(gè)shapelets參與最后的分類，實(shí)驗(yàn)過程中需要對k值進(jìn)行設(shè)定，k值的選取見3.3節(jié)。在3.4節(jié)給出了本文算法與對比算法的分類準(zhǔn)確率對比，以驗(yàn)證本文算法的效果。在3.5節(jié)對則本文算法與FastShapelet算法的運(yùn)行時(shí)間進(jìn)行了對比。

3.2 數(shù)據(jù)集的選取

實(shí)驗(yàn)選取了多種數(shù)據(jù)集進(jìn)行測量。第一種采用UCR數(shù)據(jù)集[15]，選取其中7個(gè)數(shù)據(jù)集做了進(jìn)一步的實(shí)驗(yàn)；第二種使用千秋礦上電磁輻射的強(qiáng)度和脈沖數(shù)據(jù)，以其狀態(tài)異?；蛘＿M(jìn)行分類；第三種選用加州大學(xué)歐文(爾灣)分校機(jī)器學(xué)習(xí)庫中的占用檢測(Occupancy Detection)數(shù)據(jù)集[16]，實(shí)驗(yàn)數(shù)據(jù)采集溫度、濕度、燈光和二氧化碳濃度等，對辦公室占用或者不占用進(jìn)行二分類。

在這些數(shù)據(jù)集當(dāng)中，有一部分時(shí)間序列有著明顯的趨勢特征，例如UCR數(shù)據(jù)集中的CBF數(shù)據(jù)集，示例如圖5所示；而另一部分則不明顯具有趨勢特征，例如UCR數(shù)據(jù)集中的MedicalImages數(shù)據(jù)集，由于該數(shù)據(jù)集類別過多，此處僅列舉3類示意，示例如圖6所示?？梢钥闯霰疚乃惴ㄔ诎忻黠@趨勢特征的數(shù)據(jù)集上有著良好的效果。

圖5 CBF數(shù)據(jù)集部分序列示例Fig. 5 Illustration of part series in CBF dataset

圖6 MedicalImages數(shù)據(jù)集部分序列示例Fig. 6 Illustration of part series in MedicalImages dataset

3.3k值選取說明

算法中k取值的不同會對算法的結(jié)果造成影響，因此k值的選取相當(dāng)關(guān)鍵。針對不同k值對本文算法進(jìn)行測試的結(jié)果如圖7所示，可以看出，隨著k取值的增加，算法的結(jié)果趨于穩(wěn)定，當(dāng)k大于13以后，算法的結(jié)果穩(wěn)定在某一數(shù)值，因此在以后的對比實(shí)驗(yàn)中，均取k=13時(shí)的算法分類準(zhǔn)確度作為對比實(shí)驗(yàn)的比對數(shù)據(jù)。

3.4 分類準(zhǔn)確率對比

為了說明本文所提出的TDTS算法能夠提高包含有趨勢特征的時(shí)間序列的分類準(zhǔn)確率，將其與其他算法在多個(gè)數(shù)據(jù)集上的分類準(zhǔn)確度進(jìn)行對比。算法將原始數(shù)據(jù)集進(jìn)行shapelet轉(zhuǎn)換，并將轉(zhuǎn)換后的結(jié)果運(yùn)用于多個(gè)原始分類器上以評估算法的效果。表2展現(xiàn)了TDTS算法與傳統(tǒng)分類算法的準(zhǔn)確率對比,對比算法包括C4.5、1NN、樸素貝葉斯(Naive Bayes, NB)、貝葉斯網(wǎng)絡(luò)(Bayesian Network, BN)、隨機(jī)森林(Random Forest, RanF)、旋轉(zhuǎn)森林(Rotation Forest, RoF)、支持向量機(jī)(Support Vector Machine, SVM)。表2中：第1列為測試數(shù)據(jù)集，第2列為單獨(dú)C4.5算法對各數(shù)據(jù)集分類的準(zhǔn)確率(以“單獨(dú)”表示)，第3列為C4.5算法應(yīng)用于本文算法后得出的分類準(zhǔn)確率(以“結(jié)合”表示)，以此類推，最后一行表示TDTS算法對比傳統(tǒng)分類算法分類準(zhǔn)確率有所提升的數(shù)據(jù)集個(gè)數(shù)。對比結(jié)果表明，在11個(gè)數(shù)據(jù)集上，TDTS算法對大部分?jǐn)?shù)據(jù)集在準(zhǔn)確率上均有所提升。

由于FastShapelet算法采用SAX符號化方法對原始時(shí)間序列符號化，本文算法思路與其相似，為了體現(xiàn)TDTS更能保留時(shí)間序列的趨勢特征，選取FastShapelet算法作為本文的對比算法。表2展示了FastShapelet算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率，圖8對TDTS算法與FastShapelet算法在分類準(zhǔn)確率上進(jìn)行了對比。對比顯示，本文算法在11個(gè)數(shù)據(jù)集上有7個(gè)數(shù)據(jù)集要好于FastShapelet，表明本文算法能夠較好地提高分類準(zhǔn)確率。

圖7 不同數(shù)據(jù)集分類準(zhǔn)確率隨k變化過程Fig. 7 Classification accuracy of different datasets changing with k

圖8 TDTS與FastShapelet分類準(zhǔn)確率對比Fig. 8 Classification accuracy comparison between TDTS and FastShapelet algorithms

3.5 shapelet發(fā)現(xiàn)時(shí)間對比

由于算法在shapelet發(fā)現(xiàn)階段耗時(shí)最長，本文僅對比算法在shapelet發(fā)現(xiàn)階段所用時(shí)間，結(jié)果如表4所示，其中加速倍數(shù)=FastShapelet算法運(yùn)行時(shí)間/TDTS算法運(yùn)行時(shí)間。由于本文算法在進(jìn)行shapelet發(fā)現(xiàn)前先對時(shí)間序列整體進(jìn)行符號化，而原始FastShapelet算法則是在shapelet發(fā)現(xiàn)過程中對子序列進(jìn)行符號化進(jìn)而計(jì)算shapelet，因此本文算法在運(yùn)行時(shí)間上要少于原始FastShapelet算法。由表4可以看出，與FastShapelet算法相比，TDTS算法一定程度上提升了時(shí)間效率。本文算法采用先符號化后進(jìn)行shapelet發(fā)現(xiàn)的過程，與FastShapelet算法相比，本文算法主要節(jié)省了符號化的時(shí)間，但由于本文符號化的結(jié)果是一個(gè)個(gè)二元組，在處理符號化后序列的過程中會比FastShapelet算法慢。MoteStrain等數(shù)據(jù)集原始序列長度較短，造成本文算法運(yùn)行時(shí)間比FastShapelet算法長，先處理符號化后進(jìn)行shapelet發(fā)現(xiàn)的優(yōu)勢無法體現(xiàn)，因此無法加速；而FaceFour等數(shù)據(jù)集原始序列長度較長，更能體現(xiàn)本文算法優(yōu)勢。由于時(shí)間序列大多較長，因此可以認(rèn)為本文算法在提升效率上具有一定優(yōu)勢。

表2 TDTS算法與傳統(tǒng)分類算法準(zhǔn)確率對比Tab.2 Accuracy comparison between TDTS and traditional classification algorithms

表3 FastShapelet算法在不同數(shù)據(jù)集下的分類準(zhǔn)確率 %Tab.3 Classification accuracy of FastShapelet algorithm in different datasets %

表4 算法運(yùn)行時(shí)間對比Tab. 4 Comparison of running time

4 結(jié)語

本文提出了一種基于趨勢特征的多樣化top-kshapelet查詢方法，解決了現(xiàn)存的shapelet分類算法不能很好地捕捉時(shí)間序列趨勢信息的問題。通過將趨勢特征符號化與FastShapelet進(jìn)行結(jié)合，選出包含有趨勢信息的shapelets，并利用多樣化查詢的方法對shapelet去除冗余，利用shapelets轉(zhuǎn)換技術(shù)對時(shí)間序列進(jìn)行分類。實(shí)驗(yàn)結(jié)果表明，算法能夠有效地提高時(shí)間序列的分類效率，提高了算法的運(yùn)行效率，縮短了算法的運(yùn)行時(shí)間，并在趨勢信息明顯的數(shù)據(jù)上效果顯著。但由于算法在進(jìn)行shapelet發(fā)現(xiàn)的過程中著重保留了時(shí)間序列的趨勢信息，應(yīng)用在部分趨勢信息較弱的時(shí)間序列時(shí)，分類效果會差于趨勢特征明顯的數(shù)據(jù)，因此在這方面還有待提高。

References)

[1] YE L, KEOGH E. Time series shapelets: a new primitive for data mining [C]// KDD ’09: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 947-956.

[2] MUEEN A, KEOGH E, YOUNG N. Logical-shapelets: an expressive primitive for time series classification [C]// KDD’11: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2011: 1154-1162.

[3] ZAKARIA J, MUEEN A, KEOGH E. Clustering time series using unsupervised-shapelets [C]// ICDM 2012: Proceedings of the IEEE 12th International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2012: 785-794.

[4] YE L, KEOGH E. Time series shapelets: a novel technique that allows accurate, interpretable and fast classification [J]. Data Mining and Knowledge Discovery, 2011, 22(1/2): 149-182.

[5] LINES J, DAVIS L M, HILLS J, et al. A shapelet transform for time series classification [C]// KDD ’12: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 289-297.

[6] 原繼東,王志海,韓萌.基于Shapelet剪枝和覆蓋的時(shí)間序列分類算法[J].軟件學(xué)報(bào),2015,26(9)：2311-2325. (YUAN J D, WANG Z H, HAN M. Shapelet pruning and shapelet coverage for time series classification [J]. Journal of Software, 2015, 26(9):2311-2325.)

[7] LIN J, KEOGH E, LONARDI S, et al. A symbolic representation of time series, with implications for streaming algorithms [C]// DMKD ’03: Proceedings of the 8th ACM SIDMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. New York: ACM, 2003: 2-11.

[8] LIN J, KEOGH E, WEI L, et al. Experiencing SAX: a novel symbolic representation of time series [J]. Data Mining and Knowledge Discovery, 2007, 15(2): 107-144.

[9] RAKTHANMANON T, KEOGH E. Fast shapelets: a scalable algorithm for discovering time series shapelets [C]// SDM 2013: Proceedings of the thirteenth SIAM Conference on Data Mining. Philadelphia, PA: SIAM, 2013: 668-676.

[10] BUHLER J, TOMPA M. Finding motifs using random projections [J]. Journal of Computation Biology, 2001, 9(2): 225-242.

[11] QIN L, YU J X, CHANG L. Diversifying top-kresults [J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1124-1135.

[12] 孫其法,閆秋艷,閆欣鳴.基于多樣化top-kshapelets轉(zhuǎn)換的時(shí)間序列分類方法[J].計(jì)算機(jī)應(yīng)用,2017,37(2):335-340. (SUN Q F, YAN Q Y, YAN X M. Diversified top-kshapelets transform for time series classcation [J]. Journal of Computer Applications, 2017, 37(2): 335-340.)

[13] YIN H, YANG S-Q, ZHU X-Q, et al. Symbolic representation based on trend features for knowledge discovery in long time series [J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(9): 744-758.

[14] YAN Q, SUN Q, YAN X. Adapting ELM to time series classification: a novel diversified top-kshapelets extraction method [C]// Proceedings of the 27th Australasian Database Conference on Databases Theory and Applications, LNCS 9877. Berlin: Springer-Verlag, 2016: 215-227.

[15] CHEN Y, KEOGH E, HU B, et al. The UCR time series classification archive [DB/OL]. [2015- 07- 01]. http://www.cs.ucr.edu/～eamonn/time_series_data/.

[16] CANDANEDO L M, FELDHEIM V. Accurate occupancy detection of an office room from light, temperature, humidity and CO2 measurements using statistical learning models [J]. Energy and Buildings, 2016, 112: 28-39.

This work is partially supported by the National Key Research and Development Program (2016YFC060908), the National Natural Science Foundation of China (61402482, 61572505, 51674255), the Natural Science Foundation of Jiangsu Province (BK20140192).

YANXinming, born in 1993, M. S. candidate. Her research interests include time series data mining.

MENGFanrong, born in 1962, Ph. D., professor. Her research interests include database, data mining.

YANQiuyan, born in 1978, Ph. D., associate professor. Her research interests include time series data mining, machine learning.

Shapeletclassificationmethodbasedontrendfeaturerepresentation

YAN Xinming*, MENG Fanrong, YAN Qiuyan

(SchoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,XuzhouJiangsu221116,China)

Shapelet is a kind of recognizable time series sub-sequence, by identifying the local characteristics to achieve the purpose of accurate classification of time series. The original shapelet discovery algorithm has low efficiency, and much work has focused on improving the efficiency of shapelet discovery. However, for the time series with trend change, the typical time series representation is used for shapelet discovery, which tends to cause the loss of trend information in the sequence. In order to solve this problem, a new trend-based diversified top-kshapelet classification method was proposed. Firstly, the method of trend feature symbolization was used to represent the trend information of time series. Then, the shapelet candidate set was obtained according to the trend signature of the sequence. Finally, the most representativekshapelets were selected from the candidate set by introducing the diversifying top-kquery algorithm. Experimental results of time series classification show that compared with the traditional classification algorithms, the accuracy of the proposed method was improved on 11 experimental data sets; compared with FastShapelet algorithm, the efficiency was improved, the running time of the proposed method was shortened, specially for the data with obvious trend information. The experimental results indicate that the proposed method can effectively improve the accuracy and the effciency of time series classification.

shapelet; trend feature; symbolization; diversified top-kquery; time series classification

TP311.13

A

2017- 02- 22;

2017- 05- 03。

國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFC060908)；國家自然科學(xué)基金資助項(xiàng)目(61402482,61572505,52674255)；江蘇省自然科學(xué)基金資助項(xiàng)目(BK20140192)。

閆欣鳴(1993—)，女，江蘇徐州人，碩士研究生，主要研究方向：時(shí)間序列數(shù)據(jù)挖掘； 孟凡榮(1962—)，女，遼寧沈陽人，教授，博士，主要研究方向：數(shù)據(jù)庫、數(shù)據(jù)挖掘； 閆秋艷(1978—)，女，江蘇徐州人，副教授，博士，主要研究方向：時(shí)間序列數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)。

1001- 9081(2017)08- 2343- 06

10.11772/j.issn.1001- 9081.2017.08.2343