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

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

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

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

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

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

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

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

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

時間序列分類；shapelets；多樣化top-k

0 引言

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

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

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

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

1 符號與定義

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

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

定義2 信息增益。一個分裂點〈S,d〉的信息增益為:

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

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

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

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

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

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

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

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

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

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

定義6 相似shapelets。對于兩個時間序列的shapeletsSi和Sj(1≤i

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

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

2)對于任意兩個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)計算shapelets候選集；2)計算多樣化top-kshapelets集；3)對數(shù)據(jù)集進行轉(zhuǎn)換，并將轉(zhuǎn)換后的數(shù)據(jù)應(yīng)用于時間序列分類過程。

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

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

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

2.2 多樣化top-k shapelets集計算

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

在候選shapelets集合的基礎(chǔ)上，應(yīng)用定義5～6，構(gòu)造多樣化圖，具體過程見算法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)行)，并對shapelets候選集中的所有shapelets按信息增益的非遞增順序排序(第2)行)。然后，將所有的shapelets均設(shè)為多樣化圖的頂點(第3)～5)行)。對于圖中所有的頂點，按照定義6相似shapelets的計算方法，判斷所有的頂點兩兩之間是否相似(第8)行)。如果相似，那么這兩個頂點之間就會存在一條邊，可以將頂點加入到對方的鄰接節(jié)點中(第9)～10)行)。

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

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

2.2.2 查詢多樣化top-kshapelets

傳統(tǒng)的top-k查詢中，返回的結(jié)果僅僅基于對象的分值，而多樣化top-k查詢能夠既考慮結(jié)果的分值，又兼顧對象之間的相關(guān)性，移除結(jié)果中的冗余項。這種方法恰好能夠解決求解最優(yōu)shapelets集合的問題，具體過程見算法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，此時算法將會結(jié)束，并返回該shapelet；否則，對于多樣化圖中的其他節(jié)點，如果該節(jié)點的鄰接節(jié)點都不在kShapelets中，就可以將該節(jié)點加入到kShapelets中(第3)～8)行)。最后返回k個多樣化shapelets(第9)行)。

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

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

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

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

3 實驗結(jié)果和分析

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

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

3.1 shapelets長度和k值的確定

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

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

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

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

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

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

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

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

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

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

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

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

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

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

所有6個分類器在ECGFiveDays、Gun_Point、SonyAIBORobotSurface、SyntheticControl、Trace和TwoLeadECG這6個數(shù)據(jù)集上的相對準(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é)對DivTopKShapelet算法和ClusterShapelet算法在6種分類器上的相對準(zhǔn)確率進行比較，圖5為DivTopKShapelet與ClusterShapelet算法之間的相對準(zhǔn)確率曲線。

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

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

在圖5中，6個分類器在15個數(shù)據(jù)集中的8個上的相對準(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é)對DivTopKShapelet算法和ShapeletSelection算法在6種分類器上的相對準(zhǔn)確率進行比較，結(jié)果如圖6所示。

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

圖6中的6個分類器在Adiac和SonyAIBORobotSurface數(shù)據(jù)集上的相對準(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方法間的相對準(zhǔn)確率

3.4 時間對比

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

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

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

表2 DivTopKShapelet與ClusterShapelet和ShapeletSelction的平均運行時間對比

4 結(jié)語

本文提出了一種基于多樣化top-kshapelets轉(zhuǎn)換的時間序列分類方法，解決了候選shapelets之間存在冗余和shapelets計算效率低的問題。通過對候選shapelets集合進行多樣化top-k查詢篩選出其中最具有代表性且互不相似的shapelets，實現(xiàn)對原始數(shù)據(jù)集的轉(zhuǎn)換和后續(xù)分類。實驗結(jié)果表明，多樣化top-kshapelets轉(zhuǎn)換技術(shù)可以提高15個時間序列數(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剪枝和覆蓋的時間序列分類算法[J].軟件學(xué)報,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é)基金資助項目(BK20140192)；中國礦業(yè)大學(xué)青年科技基金資助項目(2013QNB16)。

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

1001- 9081(2017)02- 0335- 06

10.11772/j.issn.1001- 9081.2017.02.0335

TP311.13

A