孫其法，閆秋艷,2，閆欣鳴

(1.中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221006； 2.中國(guó)礦業(yè)大學(xué) 安全工程學(xué)院，江蘇 徐州 221006)

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

基于多樣化top-kshapelets轉(zhuǎn)換的時(shí)間序列分類方法

孫其法1，閆秋艷1,2*，閆欣鳴1

(1.中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221006； 2.中國(guó)礦業(yè)大學(xué) 安全工程學(xué)院，江蘇 徐州 221006)

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

針對(duì)基于shapelets轉(zhuǎn)換的時(shí)間序列分類方法中候選shapelets存在較大相似性的問(wèn)題，提出一種基于多樣化top-kshapelets轉(zhuǎn)換的分類方法DivTopKShapelet。該方法采用多樣化top-k查詢技術(shù)，去除相似shapelets，并篩選出最具代表性的k個(gè)shapelets集合，最后以最優(yōu)shapelets集合為特征對(duì)數(shù)據(jù)集進(jìn)行轉(zhuǎn)換，達(dá)到提高分類準(zhǔn)確率及時(shí)間效率的目的。實(shí)驗(yàn)結(jié)果表明，DivTopKShapelet分類方法不僅比傳統(tǒng)分類方法具有更高的準(zhǔn)確率，而且與使用聚類篩選的方法(ClusterShapelet)和shapelets覆蓋的方法(ShapeletSelection)相比，分類準(zhǔn)確率最多提高了48.43%和32.61%；同時(shí)在所有15個(gè)數(shù)據(jù)集上均有計(jì)算效率的提升，最少加速了1.09倍，最高可達(dá)到287.8倍。

時(shí)間序列分類；shapelets；多樣化top-k

0 引言

Shapelets 是描述時(shí)間序列局部特征的子序列，是時(shí)間序列中一種微小的局部模式，具有高度的辨識(shí)性[1]?；趕hapelets的時(shí)間序列分類方法，能夠發(fā)現(xiàn)時(shí)間序列之間具有微小區(qū)別的局部特征，不僅分類精度高，對(duì)分類的結(jié)果也有很好的解釋能力，已經(jīng)成為時(shí)間序列領(lǐng)域一個(gè)重要的研究主題，受到了越來(lái)越多的關(guān)注[2-5]，并被廣泛應(yīng)用到聚類[6]、姿勢(shì)識(shí)別[7]、早期分類[8]等領(lǐng)域。

原始基于shapelets的分類方法將shapelets的求解與時(shí)間序列的分類過(guò)程通過(guò)一個(gè)決策樹算法完成，用于產(chǎn)生shapelets候選集的時(shí)間復(fù)雜度均為O(n2m4)，n為數(shù)據(jù)集中時(shí)間序列的條數(shù)，m為時(shí)間序列的長(zhǎng)度，計(jì)算出所有shapelets的集合需要耗費(fèi)的時(shí)間非常驚人。因此，提高shapelets候選集的計(jì)算效率成為一個(gè)重要的研究方向。文獻(xiàn)[1]采用提前停止距離計(jì)算和熵剪枝的加速方法；其他的加速技術(shù)依賴于計(jì)算的重用和對(duì)搜索空間的精簡(jiǎn)[3]，或者在使用符號(hào)聚集近似(SymbolicAggregateapproXimation，SAX)表示的基礎(chǔ)上對(duì)候選的shapelets進(jìn)行剪枝[4]，以及使用非頻繁shapelets[9]和一定數(shù)量的隨機(jī)shapelets[10]；此外，文獻(xiàn)[11]中采用并行化的方法提高搜索速度。

另一方面，基于shapelets轉(zhuǎn)換的時(shí)間序列分類方法[5]將shapelets的發(fā)現(xiàn)過(guò)程和分類算法分離開來(lái)，從候選集中選取最優(yōu)的k個(gè)shapelets特征，是此類方法的關(guān)鍵。為了確定需要選取的shapelets的數(shù)量，文獻(xiàn)[5]中使用的5折交叉驗(yàn)證的方法會(huì)耗費(fèi)大量時(shí)間，并且不能解決被選擇的shapelets之間存在較大相似性的問(wèn)題。為了解決這個(gè)問(wèn)題，ClusterShapelet算法[12]使用聚類的方法對(duì)候選集進(jìn)行篩選，ShapeletsSelection方法[13]提出了shapelets覆蓋的概念來(lái)確定shapelets候選集中最優(yōu)shapelets的個(gè)數(shù)。但是，運(yùn)用shapelets覆蓋所選取的shapelets，彼此之間仍會(huì)有相互重疊的部分，而且會(huì)受到評(píng)判順序的影響。這兩種方法用于產(chǎn)生shapelets候選集的時(shí)間復(fù)雜度均為O(n2m4)，時(shí)間復(fù)雜度較高。

針對(duì)目前求解最優(yōu)shapelets集合不能有效去除冗余，無(wú)法高效選取最具代表性的k個(gè)shapelets，影響了分類準(zhǔn)確率及效率的問(wèn)題，本文引入數(shù)據(jù)檢索領(lǐng)域的多樣化top-k查詢方法，對(duì)候選的shapelets進(jìn)行處理，從中選出最具有辨別能力且彼此不相似的shapelets，提高了shapelets特征選擇的準(zhǔn)確性；同時(shí)，借鑒文獻(xiàn)[4]中的方法，提高最優(yōu)shapelets候選集的計(jì)算速度，從而從整體上提高基于shapelest轉(zhuǎn)換的分類方法的效率。

1 符號(hào)與定義

圍繞本文的相關(guān)工作，以下先給出一些關(guān)于shapelets[1]及多樣化top-k查詢[14]的基本概念。

定義1 分裂點(diǎn)。一個(gè)分裂點(diǎn)由一個(gè)子序列S和一個(gè)距離閾值d組成，可表示為一個(gè)元組〈S,d〉。它可以將一個(gè)數(shù)據(jù)集分成兩個(gè)更小的數(shù)據(jù)集DL和DR，其中時(shí)間序列的個(gè)數(shù)分別為nL和nR。對(duì)于DL中的每個(gè)時(shí)間序列Ti,L，都有SubsequenceDist(S,Ti,L)

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

定義3shapelet。數(shù)據(jù)集D的shapelet是一個(gè)最優(yōu)分裂點(diǎn)，它能將數(shù)據(jù)集D分成兩部分，使最終的信息增益的值最大?？杀硎救缦?

IG(〈shapelet(D),dosp〉)≥IG(S,d)

定義4 多樣化top-k查詢。給定一個(gè)集合I={v1,v2,…,vn}，對(duì)于每一個(gè)vi∈I，v的分值為score(vi)。對(duì)于vi,vj∈I，有一個(gè)用戶定義相似度函數(shù)sim(vi,vj)和閾值τ，如果sim(vi,vj)>τ，則vi和vj相似，表示為vi≈vj。

給定一個(gè)整數(shù)k(1≤k

1)Q(I)?I,|Q(I)|≤k；

2)對(duì)于任意兩個(gè)元素vi,vj∈I，vi≠vj，如果vi≈vj，則{vi,vj}?Q(I)；

直觀上看，Q(I)就是至多k個(gè)結(jié)果的集合，其中沒有任意兩個(gè)元素是彼此相似的，同時(shí)這些元素所對(duì)應(yīng)的總分值最大。

定義5 多樣化圖。給定一個(gè)集合，I={v1,v2,…,vn}，I的多樣化圖表示為G(I)=(V,E)。其中：G是一個(gè)無(wú)向圖；V是I中所有變量組成的頂點(diǎn)集合；若vi≈vj成立，則vi與vj之間有一條邊E。不失一般性，假定G(I)中頂點(diǎn)的編號(hào)是按照頂點(diǎn)分值的非遞增順序排列，即：

score(vi)≥score(vj); 1≤i

在定義1～5的基礎(chǔ)上，本文提出相似shapelets及多樣化top-kshapelets的概念，用來(lái)求解最優(yōu)shapelets集合。

定義6 相似shapelets。對(duì)于兩個(gè)時(shí)間序列的shapeletsSi和Sj(1≤i

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

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

2)對(duì)于任意兩個(gè)shapelets，Si,Sj∈I，Si≠Sj，如果Si≈Sj，則{Si,Sj}?DivTopk(I)；

與傳統(tǒng)多樣化top-k查詢的概念相比，多樣化top-kshapelets查詢所使用的分值為shapelets的信息增益值，相似度函數(shù)滿足相似shapelets的條件。

2 本文方法

基于多樣化top-kshapelets轉(zhuǎn)換的分類方法包括三部分：1)計(jì)算shapelets候選集；2)計(jì)算多樣化top-kshapelets集；3)對(duì)數(shù)據(jù)集進(jìn)行轉(zhuǎn)換，并將轉(zhuǎn)換后的數(shù)據(jù)應(yīng)用于時(shí)間序列分類過(guò)程。

原始計(jì)算shapelets候選集的方法，時(shí)間復(fù)雜度為O(n2m4)，對(duì)大多數(shù)場(chǎng)景都是不可取的。本文借鑒文獻(xiàn)[4]中的方法，將原始的實(shí)值和高維數(shù)據(jù)進(jìn)行SAX轉(zhuǎn)換；接著使用多樣化top-k查詢方法對(duì)候選的shapelets進(jìn)行篩選。篩選方法:構(gòu)造多樣化圖，求解分類效果最優(yōu)且不相似的k個(gè)shapelets。最后，將k個(gè)最優(yōu)的shapelets作為特征屬性，對(duì)待測(cè)數(shù)據(jù)進(jìn)行轉(zhuǎn)換，將每個(gè)序列轉(zhuǎn)換為一個(gè)包含k個(gè)屬性的特征向量，使其能夠適用于任何典型的時(shí)間序列分類算法。

2.1 產(chǎn)生shapelets候選集

產(chǎn)生shapelets候選集的過(guò)程，是得到最優(yōu)shapelets的基礎(chǔ)，原始算法復(fù)雜度過(guò)高，本文參考文獻(xiàn)[4]中的方法，對(duì)原始數(shù)據(jù)進(jìn)行SAX轉(zhuǎn)換，從而大幅降低產(chǎn)生shapelets候選集所需的時(shí)間。

2.2 多樣化top-k shapelets集計(jì)算

2.2.1 構(gòu)造多樣化圖

在候選shapelets集合的基礎(chǔ)上，應(yīng)用定義5～6，構(gòu)造多樣化圖，具體過(guò)程見算法1。

算法1 conShapeletGraph(allShapelets)。

輸入shapelets候選集allShapelets；

輸出 所有shapelets構(gòu)成的多樣化圖Graph。

1)

Graph=?

2)

sort(allShapelets)

3)

fori=1to|allShapelets|

4)

Graph.add(allShapelets[i])

5)

endfor

6)

forj=1to|allShapelets|

7)

fork=1to|allShapelets|

8)

if(allShapelets[j]≈allShapelets[k])

9)

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

10)

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

11)

endfor

12)

endfor

13)

returnGraph

算法1首先初始化多樣化圖Graph(第1)行)，并對(duì)shapelets候選集中的所有shapelets按信息增益的非遞增順序排序(第2)行)。然后，將所有的shapelets均設(shè)為多樣化圖的頂點(diǎn)(第3)～5)行)。對(duì)于圖中所有的頂點(diǎn)，按照定義6相似shapelets的計(jì)算方法，判斷所有的頂點(diǎn)兩兩之間是否相似(第8)行)。如果相似，那么這兩個(gè)頂點(diǎn)之間就會(huì)存在一條邊，可以將頂點(diǎn)加入到對(duì)方的鄰接節(jié)點(diǎn)中(第9)～10)行)。

圖1給出了ChlorineConcentration數(shù)據(jù)集上候選shapelets集合構(gòu)造的多樣化圖，其中圖(a)為10個(gè)候選shapelets集合，圖(b)為該shapelets集合的多樣化圖，圖中節(jié)點(diǎn)的編號(hào)按照shapelet增益值的非遞增順序排列，即編號(hào)越小，其代表的shapelet增益值越大。運(yùn)用多樣化top-k查詢算法，最終可以得到圖1(a)中三條加粗的序列，直觀上看，這三條序列的形態(tài)各不相同，且具有一定的代表性，應(yīng)該具有最好的分類效果。

圖1 候選shapelets構(gòu)成的多樣化圖舉例

2.2.2 查詢多樣化top-kshapelets

傳統(tǒng)的top-k查詢中，返回的結(jié)果僅僅基于對(duì)象的分值，而多樣化top-k查詢能夠既考慮結(jié)果的分值，又兼顧對(duì)象之間的相關(guān)性，移除結(jié)果中的冗余項(xiàng)。這種方法恰好能夠解決求解最優(yōu)shapelets集合的問(wèn)題，具體過(guò)程見算法2。

算法2 DivTopKShapelet(Graph,k)

輸入 多樣化圖Graph，k值

輸出top-kshapelets。

1)

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

2)

kShapelets.add(v1)

3)

while(|kShapelets|

4)

fori=2ton

5)

if(Graph[i]∩kShapelets=?)

6)

kShapelets.add(vi)

7)

endif

8)

endfor

9)

returnkShapelets

該算法首先將信息增益最大的shapelet(v1)放到kShapelets集合中(第2)行)。如果k=1，此時(shí)算法將會(huì)結(jié)束，并返回該shapelet；否則，對(duì)于多樣化圖中的其他節(jié)點(diǎn)，如果該節(jié)點(diǎn)的鄰接節(jié)點(diǎn)都不在kShapelets中，就可以將該節(jié)點(diǎn)加入到kShapelets中(第3)～8)行)。最后返回k個(gè)多樣化shapelets(第9)行)。

2.3 基于多樣化shapelets的數(shù)據(jù)集轉(zhuǎn)換

進(jìn)行多樣化shapelets轉(zhuǎn)換的目的是為了將傳統(tǒng)的分類算法應(yīng)用于轉(zhuǎn)換后的時(shí)間序列數(shù)據(jù)集上。在找到k個(gè)多樣化shapelets后，利用這k個(gè)shapelets將原始的時(shí)間序列數(shù)據(jù)集進(jìn)行轉(zhuǎn)換，每條時(shí)間序列都可以表示為擁有k個(gè)屬性的實(shí)例，每個(gè)屬性的值為時(shí)間序列與shapelets之間的距離。這樣就把時(shí)間序列分類問(wèn)題看作是一般的分類問(wèn)題，其具體過(guò)程此處不再贅述。

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

本文首先通過(guò)SAX轉(zhuǎn)換，將計(jì)算shapelets候選集的時(shí)間復(fù)雜度由O(n2m4)降為O(nm2)；構(gòu)造多樣化圖所需的時(shí)間復(fù)雜度為O(p2)，p為候選shapelets的個(gè)數(shù)；計(jì)算多樣化top-kshapelets集的時(shí)間復(fù)雜度為O(k2p2)。從后面的實(shí)驗(yàn)部分得知，當(dāng)k>4時(shí)，分類的準(zhǔn)確率就會(huì)在一個(gè)很小的范圍內(nèi)波動(dòng)，k可以看作常數(shù)。因此，算法的總體復(fù)雜度為O(nm2)+O(p2)。而ClusterShapelet方法和ShapeletsSelection方法的時(shí)間復(fù)雜度分別為O(n2m4)+O(p3)和O(n2m4)+O(p2)。

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

為了評(píng)估多樣化shapelets的有效性，本文采用來(lái)自UCR[15]的時(shí)間序列數(shù)據(jù)集進(jìn)行測(cè)試，所采用的數(shù)據(jù)集均包括訓(xùn)練集和測(cè)試集。shapelets的產(chǎn)生和構(gòu)建分類器的過(guò)程都在訓(xùn)練集上進(jìn)行，測(cè)試集只用于測(cè)試分類器的分類準(zhǔn)確率。本文的算法和實(shí)驗(yàn)都在Weka框架下使用Java代碼實(shí)現(xiàn)的。

為方便對(duì)比，本文將DivTopKShapelet算法與其他分類器的結(jié)合使用，統(tǒng)一都命名為DivTopKShapelet算法。首先運(yùn)用DivTopKShapelet算法對(duì)訓(xùn)練集求取最優(yōu)shapelets集合，之后對(duì)訓(xùn)練集進(jìn)行轉(zhuǎn)換，結(jié)合其他分類算法構(gòu)建分類器。

3.1 shapelets長(zhǎng)度和k值的確定

與文獻(xiàn)[4]中shapelets的提取方法類似，算法1中有兩個(gè)參數(shù)需要設(shè)置：min和max。這兩個(gè)參數(shù)用來(lái)決定所要產(chǎn)生候選shapelets的長(zhǎng)度范圍，如果設(shè)置不合理，算法可能無(wú)法找到最具辨識(shí)力的shapelets，進(jìn)而對(duì)最終的分類結(jié)果造成影響。為了保持一致性和簡(jiǎn)潔性，本文采取與文獻(xiàn)[13]相同的做法，統(tǒng)一將最小長(zhǎng)度設(shè)置為m/11，最大長(zhǎng)度設(shè)置為m/2，m為時(shí)間序列的長(zhǎng)度。

圖2展示了隨著k的變化，15個(gè)數(shù)據(jù)集在6種分類器上平均準(zhǔn)確率的變化。隨著k值的增加，數(shù)據(jù)集的準(zhǔn)確率逐漸趨于一個(gè)穩(wěn)定值，在進(jìn)行分類準(zhǔn)確率對(duì)比時(shí)將k值統(tǒng)一設(shè)置為9。

圖2 15個(gè)數(shù)據(jù)集準(zhǔn)確率隨k的變化曲線

3.2 shapelets最優(yōu)集的表示

為了更加直觀地說(shuō)明本文工作，本節(jié)將DivTopKShapelet與和本文工作最相似的ShapeletSelction算法的最優(yōu)shapelets集合進(jìn)行比較，選取TwoLeadECG數(shù)據(jù)集，結(jié)果如圖3所示。shapelets最優(yōu)集指算法在取得最好分類效果時(shí)的shapelets集合。對(duì)于TwoLeadECG數(shù)據(jù)集，當(dāng)DivTopKShapelet算法的分類效果最好時(shí)，shapelets的個(gè)數(shù)為2，因此k取2。從圖中可以看出，在獲得最優(yōu)分類準(zhǔn)確率時(shí)，DivTopKShapelet算法可以有效篩選出形態(tài)上最具有代表性的2個(gè)shapelets，而shapeletSelection方法只能篩選出14個(gè)最優(yōu)shapelets，其中仍然存在一定的冗余；同時(shí)，DivTopKShapelet算法擁有更高的分類準(zhǔn)確率。

圖3 最優(yōu)shapelets集合對(duì)比

3.3 分類準(zhǔn)確率對(duì)比

為了說(shuō)明本文出的DivTopKShapelet算法能夠提高時(shí)間序列的分類準(zhǔn)確率，將該算法與傳統(tǒng)分類方法、ClusterShapelet算法和ShapeletSelction算法在15個(gè)UCR數(shù)據(jù)集上的分類準(zhǔn)確率進(jìn)行對(duì)比，從平均準(zhǔn)確率和相對(duì)準(zhǔn)確率兩個(gè)方面驗(yàn)證本文的DivTopKShapelet算法在時(shí)間序列分類問(wèn)題上的有效性。每種算法在相同數(shù)據(jù)集上運(yùn)行10遍，獲取平均值作為最終的準(zhǔn)確率，所選取的shapelet的個(gè)數(shù)設(shè)為k=9。

3.3.1DivTopKShapelet與傳統(tǒng)分類方法比較

本節(jié)選取C4.5、1-最近鄰(1-NearestNeighbor, 1NN)、樸素貝葉斯(NaiveBayes，NB)、貝葉斯網(wǎng)絡(luò)(BayesianNetwork，BN)、隨機(jī)森林(RandomForest，RanF)和旋轉(zhuǎn)森林(RotationForest，RoF)共6種分類方法，直接對(duì)15個(gè)數(shù)據(jù)集進(jìn)行分類，準(zhǔn)確率結(jié)果位于表1中C4.5、1NN、NB、BN、RanF和RoF中“單獨(dú)”所在的列；同時(shí)，將DivTopKShapelet方法分別與這6種分類方法進(jìn)行結(jié)合也對(duì)15個(gè)數(shù)據(jù)集進(jìn)行分類，準(zhǔn)確率結(jié)果位于相應(yīng)的“結(jié)合”所在列。而且為了表示方便，將15個(gè)數(shù)據(jù)集分別編號(hào)為1～15。

進(jìn)一步，為了說(shuō)明DivTopKShapelet方法與每種分類器結(jié)合后的表現(xiàn)，圖4給出了DivTopKShapelet與傳統(tǒng)時(shí)間序列分類方法之間的相對(duì)準(zhǔn)確率曲線。相對(duì)準(zhǔn)確率的值由DivTopKShapelet算法在數(shù)據(jù)集上結(jié)合6個(gè)分類器得到的準(zhǔn)確率減去相對(duì)應(yīng)傳統(tǒng)時(shí)間序列分類算法的準(zhǔn)確率得到。相對(duì)準(zhǔn)確率大于0表示DivTopKShapelet方法優(yōu)于傳統(tǒng)分類方法。

表1 DivTopKShapelet與傳統(tǒng)時(shí)間序列分類方法準(zhǔn)確率比較 %

圖4 DivTopKShapelet與傳統(tǒng)時(shí)間序列分類方法間的相對(duì)準(zhǔn)確率

從圖4可以看出，NB在13個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0，C4.5、1NN和BN在10個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0，RanF和RoF分別在9個(gè)和8個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0。這表明相比傳統(tǒng)分類方法，DivTopKShapelet算法可以提高大多數(shù)數(shù)據(jù)集的分類準(zhǔn)確率。

所有6個(gè)分類器在ECGFiveDays、Gun_Point、SonyAIBORobotSurface、SyntheticControl、Trace和TwoLeadECG這6個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率得均大于0。C4.5在Coffee數(shù)據(jù)集上的準(zhǔn)確率提升效果最好，為35.72%，1NN和RoF在SonyAIBORobotSurface數(shù)據(jù)集上的準(zhǔn)確率分別提高了27.79%和22.63%，NB在TwoLeadECG數(shù)據(jù)集上的準(zhǔn)確率提高了29.85%，BN和RanF在Coffee數(shù)據(jù)集上的準(zhǔn)確率分別提高了32.14%和28.57%。

3.3.2DivTopKShapelet和ClusterShapelet

本節(jié)對(duì)DivTopKShapelet算法和ClusterShapelet算法在6種分類器上的相對(duì)準(zhǔn)確率進(jìn)行比較，圖5為DivTopKShapelet與ClusterShapelet算法之間的相對(duì)準(zhǔn)確率曲線。

在圖5中，C4.5和RandomForest在13個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0，1NN和BN在12個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0，NB和RoF分別在11個(gè)和10個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0。與ClusterShapelet算法相比，DivTopKShapelet算法至少可以提高10個(gè)數(shù)據(jù)集的分類準(zhǔn)確率。

圖5 DivTopKShapelet與ClusterShapelet方法間的相對(duì)準(zhǔn)確率

在圖5中，6個(gè)分類器在15個(gè)數(shù)據(jù)集中的8個(gè)上的相對(duì)準(zhǔn)確率均大于0。C4.5在ECGFiveDays數(shù)據(jù)集上的準(zhǔn)確率提升效果最好，為48.43%，1NN和BN在SonyAIBORobotSurface數(shù)據(jù)集上的準(zhǔn)確率分別提高了37.44%和30.12%，NB在MoteStrain數(shù)據(jù)集上的準(zhǔn)確率提高了31.79%，RanF和RoF在ECGFiveDays數(shù)據(jù)集上的準(zhǔn)確率分別提高了29.85%和29.15%。

3.3.3DivTopKShapelet和ShapeletSelection

本節(jié)對(duì)DivTopKShapelet算法和ShapeletSelection算法在6種分類器上的相對(duì)準(zhǔn)確率進(jìn)行比較，結(jié)果如圖6所示。

從圖6可知，1NN在11個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0，C4.5和RoF在10個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0，NB在8個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0，BN和RanF在7個(gè)數(shù)據(jù)集上的相對(duì)準(zhǔn)確率大于0。這表明DivTopKShapelet算法在大多數(shù)的數(shù)據(jù)集上要優(yōu)于ShapeletSelection算法。

圖6中的6個(gè)分類器在Adiac和SonyAIBORobotSurface數(shù)據(jù)集上的相對(duì)準(zhǔn)確率均大于0。1NN在SonyAIBORobotSurface數(shù)據(jù)集上的準(zhǔn)確率提升效果最好，為32.61%，C4.5在SonyAIBORobotSurface數(shù)據(jù)集上的準(zhǔn)確率提高了16.97%，NB、BN、RanF和RoF在Adiac數(shù)據(jù)集上的準(zhǔn)確率分別提高了17.14%、16.37%、26.09%和23.02%。

圖6 DivTopKShapelet與ShapeletSelection方法間的相對(duì)準(zhǔn)確率

3.4 時(shí)間對(duì)比

表2給出了本文提出的DivTopKShapelet算法與ClusterShapelet算法和ShapeletSelection算法在6個(gè)分類器上的平均運(yùn)行時(shí)間對(duì)比，其中“加速倍數(shù)”為DivTopKShapelet算法對(duì)ClusterShapelet算法和ShapeletSelection算法的加速倍數(shù)，計(jì)算方法為分別用ClusterShapelet算法和ShapeletSelection算法的運(yùn)行時(shí)間除以DivTopKShapelet算法的運(yùn)行時(shí)間。其中“—”代表時(shí)間相對(duì)過(guò)長(zhǎng)，不再進(jìn)行比較。

從表2中可以看出，由于DivTopKShapelet算法相當(dāng)于對(duì)數(shù)據(jù)集進(jìn)行了降維，從n*m長(zhǎng)度的時(shí)間序列數(shù)據(jù)，轉(zhuǎn)換為n*k的矩陣，k?m，因此，DivTopKShapelet算法在所有的數(shù)據(jù)集上都有時(shí)間效率的提升。其中，在MedicalImage數(shù)據(jù)集上的加速效果最好，加速倍數(shù)達(dá)到了287.8。

由表2可知，與ShapeletSelection算法相比，DivTopKShapelet算法提升的時(shí)間效率更為明顯。由于ShapeletSelection算法在求取Shapelets候選集時(shí)采用未進(jìn)行優(yōu)化的求解算法，因此時(shí)間復(fù)雜度較高。

表2 DivTopKShapelet與ClusterShapelet和ShapeletSelction的平均運(yùn)行時(shí)間對(duì)比

4 結(jié)語(yǔ)

本文提出了一種基于多樣化top-kshapelets轉(zhuǎn)換的時(shí)間序列分類方法，解決了候選shapelets之間存在冗余和shapelets計(jì)算效率低的問(wèn)題。通過(guò)對(duì)候選shapelets集合進(jìn)行多樣化top-k查詢篩選出其中最具有代表性且互不相似的shapelets，實(shí)現(xiàn)對(duì)原始數(shù)據(jù)集的轉(zhuǎn)換和后續(xù)分類。實(shí)驗(yàn)結(jié)果表明，多樣化top-kshapelets轉(zhuǎn)換技術(shù)可以提高15個(gè)時(shí)間序列數(shù)據(jù)集中大部分?jǐn)?shù)據(jù)集分類的準(zhǔn)確率，并明顯提升分類速度。

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] 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): 149-182.

[3] 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.

[4] 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: Society for Industrial and Applied Mathematics (SIAM), 2013: 668-676.

[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] 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.

[7] HARTMANN B, LINK N.Gesture recognition with inertial sensors and optimized DTW prototypes [C]// SMC 2010: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics.Piscataway, NJ: IEEE, 2010: 2102-2109.

[8] XING Z, PEI J, YU P S, et al.Extracting interpretable features for early classification on time series [C]// SDM 2011: Proceedings of the 2011 SIAM International Conference on Data Mining.Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2011: 247-258.

[9] HE Q, DONG Z, ZHUANG F, et al.Fast time series classification based on infrequent shapelets [C]//ICMLA 2012: Proceedings of the 2012 11th International Conference on Machine Learning and Applications.Washington, DC: IEEE Computer Society, 2012, 1: 215-219.

[10] WISTUBA M, GRABOCKA J, SCHMIDT-THIEME L.Ultra-fast shapelets for time series classification [J].Journal of Data & Knowledge Engineering, arXiv preprint arXiv: 1503.05018, 2015.

[11] CHANG K-W, DEKA B, HWU W-M W, et al.Efficient pattern-based time series classification on GPU [C]// ICDM 2012: Proceedings of the IEEE 12th International Conference on Data Mining.Washington, DC: IEEE Computer Society, 2012: 131-140.

[12] HILLS J, LINES J, BARANAUSKAS E, et al.Classification of time series by shapelet transformation [J].Data Mining and Knowledge Discovery, 2014, 28(4): 851-881.

[13] 原繼東,王志海,韓萌.基于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.)

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

[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/.

This work is partially supported by the Natural Science Foundation of Jiangsu Province (BK20140192), the Youth Technology Foundation of China University of Mining and Technology (2013QNB16).

SUN Qifa, born in 1991, M.S.candidate.His research interests include time series data mining, clustering.

YAN Qiuyan, born in 1978, Ph.D., associate professor.Her research interests include time series data mining, streaming data mining.

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

Diversified top-kshapelets transform for time series classification

SUN Qifa1, YAN Qiuyan1,2*, YAN Xinming1

(1.SchoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,XuzhouJiangsu221006,China;2.SchoolofSafetyEngineering,ChinaUniversityofMiningandTechnology,XuzhouJiangsu221006,China)

Focusing on the issue that shapelets candidates can be very similar in time series classification by shapelets transform, a diversified top-kshapelets transform method named DivTopKShapelet was proposed.In DivTopKShapelet, the diversified top-kquery method was used to filter similar shapelets and select thekmost representative shapelets.Then the optimal shapelets was used to transform data, so as to improve the accuracy and time efficiency of typical time series classification method.Experimental results show that compared with clustering based shapelets classification method (ClusterShapelet) and coverage based shapelets classification method (ShapeletSelction), DivTopKShapelet method can not only improve the traditional time series classification method, but also increase the accuracy by 48.43% and 32.61% at most; at the same time, the proposed method can enhance the computational efficiency in 15 data sets, which is at least 1.09 times and at most 287.8 times.

time series classification; shapelets; diversified top-k

2016- 08- 12;

2016- 09- 07。

江蘇省自然科學(xué)基金資助項(xiàng)目(BK20140192)；中國(guó)礦業(yè)大學(xué)青年科技基金資助項(xiàng)目(2013QNB16)。

孫其法(1991—),男,山東棗莊人,碩士研究生,主要研究方向:時(shí)間序列數(shù)據(jù)挖掘、聚類; 閆秋艷(1978—),女,江蘇徐州人,副教授,博士, CCF高級(jí)會(huì)員,主要研究方向:時(shí)間序列數(shù)據(jù)挖掘、流數(shù)據(jù)挖掘; 閆欣鳴(1993—),女,江蘇徐州人,碩士研究生,主要研究方向:時(shí)間序列數(shù)據(jù)挖掘。

1001- 9081(2017)02- 0335- 06

10.11772/j.issn.1001- 9081.2017.02.0335

TP311.13

A