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

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

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

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

基于多樣化top-kshapelets轉換的時間序列分類方法

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

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

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

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

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

0 引言

Shapelets 是描述時間序列局部特征的子序列，是時間序列中一種微小的局部模式，具有高度的辨識性[1]。基于shapelets的時間序列分類方法，能夠發現時間序列之間具有微小區別的局部特征，不僅分類精度高，對分類的結果也有很好的解釋能力，已經成為時間序列領域一個重要的研究主題，受到了越來越多的關注[2-5]，并被廣泛應用到聚類[6]、姿勢識別[7]、早期分類[8]等領域。

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

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

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

1 符號與定義

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

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

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

定義3shapelet。數據集D的shapelet是一個最優分裂點，它能將數據集D分成兩部分，使最終的信息增益的值最大。可表示如下:

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

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

給定一個整數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個結果的集合，其中沒有任意兩個元素是彼此相似的，同時這些元素所對應的總分值最大。

定義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的基礎上，本文提出相似shapelets及多樣化top-kshapelets的概念，用來求解最優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)；

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

2 本文方法

基于多樣化top-kshapelets轉換的分類方法包括三部分：1)計算shapelets候選集；2)計算多樣化top-kshapelets集；3)對數據集進行轉換，并將轉換后的數據應用于時間序列分類過程。

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

2.1 產生shapelets候選集

產生shapelets候選集的過程，是得到最優shapelets的基礎，原始算法復雜度過高，本文參考文獻[4]中的方法，對原始數據進行SAX轉換，從而大幅降低產生shapelets候選集所需的時間。

2.2 多樣化top-k shapelets集計算

2.2.1 構造多樣化圖

在候選shapelets集合的基礎上，應用定義5～6，構造多樣化圖，具體過程見算法1。

算法1 conShapeletGraph(allShapelets)。

輸入shapelets候選集allShapelets；

輸出 所有shapelets構成的多樣化圖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均設為多樣化圖的頂點(第3)～5)行)。對于圖中所有的頂點，按照定義6相似shapelets的計算方法，判斷所有的頂點兩兩之間是否相似(第8)行)。如果相似，那么這兩個頂點之間就會存在一條邊，可以將頂點加入到對方的鄰接節點中(第9)～10)行)。

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

圖1 候選shapelets構成的多樣化圖舉例

2.2.2 查詢多樣化top-kshapelets

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

2.3 基于多樣化shapelets的數據集轉換

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

2.4 算法時間復雜度分析

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

3 實驗結果和分析

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

為方便對比，本文將DivTopKShapelet算法與其他分類器的結合使用，統一都命名為DivTopKShapelet算法。首先運用DivTopKShapelet算法對訓練集求取最優shapelets集合，之后對訓練集進行轉換，結合其他分類算法構建分類器。

3.1 shapelets長度和k值的確定

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

圖2展示了隨著k的變化，15個數據集在6種分類器上平均準確率的變化。隨著k值的增加，數據集的準確率逐漸趨于一個穩定值，在進行分類準確率對比時將k值統一設置為9。

圖2 15個數據集準確率隨k的變化曲線

3.2 shapelets最優集的表示

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

圖3 最優shapelets集合對比

3.3 分類準確率對比

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

3.3.1DivTopKShapelet與傳統分類方法比較

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

進一步，為了說明DivTopKShapelet方法與每種分類器結合后的表現，圖4給出了DivTopKShapelet與傳統時間序列分類方法之間的相對準確率曲線。相對準確率的值由DivTopKShapelet算法在數據集上結合6個分類器得到的準確率減去相對應傳統時間序列分類算法的準確率得到。相對準確率大于0表示DivTopKShapelet方法優于傳統分類方法。

表1 DivTopKShapelet與傳統時間序列分類方法準確率比較 %

圖4 DivTopKShapelet與傳統時間序列分類方法間的相對準確率

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

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

3.3.2DivTopKShapelet和ClusterShapelet

本節對DivTopKShapelet算法和ClusterShapelet算法在6種分類器上的相對準確率進行比較，圖5為DivTopKShapelet與ClusterShapelet算法之間的相對準確率曲線。

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

圖5 DivTopKShapelet與ClusterShapelet方法間的相對準確率

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

3.3.3DivTopKShapelet和ShapeletSelection

本節對DivTopKShapelet算法和ShapeletSelection算法在6種分類器上的相對準確率進行比較，結果如圖6所示。

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

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

圖6 DivTopKShapelet與ShapeletSelection方法間的相對準確率

3.4 時間對比

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

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

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

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

4 結語

本文提出了一種基于多樣化top-kshapelets轉換的時間序列分類方法，解決了候選shapelets之間存在冗余和shapelets計算效率低的問題。通過對候選shapelets集合進行多樣化top-k查詢篩選出其中最具有代表性且互不相似的shapelets，實現對原始數據集的轉換和后續分類。實驗結果表明，多樣化top-kshapelets轉換技術可以提高15個時間序列數據集中大部分數據集分類的準確率，并明顯提升分類速度。

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].軟件學報,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。

江蘇省自然科學基金資助項目(BK20140192)；中國礦業大學青年科技基金資助項目(2013QNB16)。

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

1001- 9081(2017)02- 0335- 06

10.11772/j.issn.1001- 9081.2017.02.0335

TP311.13

A