面向時間序列有序分類的Shapelet 抽取算法

楊 駿，敬思遠，鐘 勇

(1.中國科學院成都計算機應用研究所 成都 610041；2.樂山師范學院電子信息與人工智能學院 四川 樂山 614000；3.中國科學院大學計算機科學與技術學院 北京 石景山區 100049；4.廳市共建智能終端四川省重點實驗室 四川 宜賓 644000)

時間序列有序分類（time series ordinal classification, TSOC）是時間序列數據挖掘領域的一項重要任務。該任務旨在訓練一個分類器，實現對類別標簽有序的時間序列數據的自動分類。與傳統時間序列分類[1]任務不同，TSOC 采用錯分代價來衡量算法有效性。如在醫療輔助診斷系統中，將危重型病癥錯分成輕型病癥的代價遠高于將其錯分成重型病癥的代價。除了醫療輔助診斷外，本任務在金融投資、氣象預測等領域都有重要應用。但目前關于該任務的研究非常少，尚處于起步階段[2]。

基于Shapelet 的時間序列分類近年來受到學界廣泛關注[3-5]。Shapelet 是指時間序列中具有良好分類能力的子序列，最早由文獻[6]提出，它采用Brute-Force 算法搜索子序列，并用信息增益（information gain, IG）對其分類能力進行評價，最后利用計算得到的Shapelet 構造決策樹。由Shapelet 構造的決策樹具有非常好的可解釋性。隨后，文獻[7]提出了ST（shapelet transformation）方法。該方法獲得Top-K 個最優Shapelet，然后將原始時間序列轉換到新的特征空間并采用傳統方法訓練分類器，使算法的分類能力大幅提升。但是，上述兩類算法都采用暴力方法搜索Shapelet，計算效率低。為解決該問題，文獻[8]提出了基于三角不等式的剪枝策略，以及提前計算距離的方法；文獻[9]用符號聚合近似（symbolic aggregate approximation, SAX）表示時間序列，采用隨機投射技術，計算最優Shapelet 集合；文獻[10]提出了基于隨機采樣的Shapelet 抽取算法；文獻[11]提出了基于隨機采樣的隨機Shapelet 森林算法gRSF；文獻[12]在上述工作基礎上進一步改進，提出了壓縮隨機Shapelet森林算法CRSF。CRSF 采用SAX 表示時間序列，通過隨機采樣構建一個高質量的Shapelet 池，然后從池中隨機選擇Shapelet 生成決策樹節點，提升了算法性能。近年來，基于Shapelet 構建深度學習模型也受到學界廣泛關注[13-14]，但考慮到深度神經網絡可解釋性不足，本文不再詳細介紹。

文獻[15]提出了基于Shapelet 的時間序列有序分類算法。該工作主要提出了兩項面向TSOC 的Shapelet 評價指標，Spearman 相關系數和Pearson相關系數。與IG 不同，這兩項評價指標通過計算Shapelet 與時間序列的歐式距離和標簽距離之間的相關系數來評價Shapelet。實驗結果表明，評價指標與IG 相比有效地降低了算法的錯分代價。但是，該方法中提出的Shapelet 評價指標都需要計算Shapelet 到時間序列的距離，計算效率較低。

本文提出一種基于覆蓋集中度和覆蓋優勢度的Shapelet 評價指標CD-Cover（concentration and dominance of coverage），以及一種面向時間序列有序分類的Shapelet 抽取算法。該算法采用SAX 表示時間序列，通過隨機采樣Shapelet，使用CD-Cover指標評價Shapelet，抽取最終的Shapelet 結果集。然后，通過ST 方法將時間序列數據集轉換到新的特征空間并訓練有序分類器。最后，在UCR 和UEA 時間序列分類資源庫[16]挑選適合TSOC 任務的11 個數據集上，采用CCR（correct classification rate）和Weighted-κ 兩個指標對所提算法進行了實驗驗證。

1 相關理論及問題描述

通常，時間序列是按照固定時間間隔采集得到的數值型數據序列，可以表示為X=〈x1,x2,···,xm〉，xi∈R，m為時間序列的長度。進一步，將二元組T=〈X,c〉稱為時間序列樣本，c是時間序列樣本的類別標簽（簡稱標簽）。D={T1,T2,···,Tn}為一個時間序列數據集，其中，n稱為時間序列數據集的大小。Y={c1,c2,···,cQ}表示時間序列數據集D中所有樣本標簽的集合，Q是標簽數。在TSOC 問題中，要求Q≥3， 且標簽之間存在全序關系c1?c2?···?cQ。

時間序列數據通常都是高維實數，不僅需要大量存儲空間，而且計算代價也很高。文獻[17]提出一種時間序列的SAX 表示方法，將數值型時間序列轉換為符號型時間序列，可以達到數據降維、降低噪聲、節省存儲和簡化計算等目的。SAX 表示方法的轉換過程如下。

給定時間序列X=〈x1,x2,···,xm〉、動態窗口長度ω 和字母表Σ，將X平均分成段，得到其中為：

傳統的Shapelet 是指時間序列的任意子序列，本文的候選Shapelet 是基于SAX 表示的時間序列，下面給出其定義。

定 義 1（候選Shapelet） 給定SAX表示的時間序列，稱該時間序列的任意子序列為一個候選Shapelet，其中b和l分別表示候選Shapelet 在時間序列中的開始位置和長度，且

基于Shapelet 的時間序列分類，核心是找出最具代表性的候選Shapelet 集合，稱為Shapelet 抽取。

文獻[6]最早采用IG 對Shapelet 的分類能力進行評價。IG 也是當前研究和實踐中最常用的Shapelet 評價指標。文獻[7]提出了Kruskal-Wallis、F-statistic 和Mood's median 這3 種指標，并通過實驗證明了其有效性。但上述指標沒有考慮錯分代價，在TSOC 任務中表現不佳。文獻[15]提出了Spearman 相關系數和Pearson 相關系數兩項指標，充分考慮了類別有序這一特征。但是，兩項指標都需要計算Shapelet 到時間序列之間的距離，計算成本較高。

2 面向TSOC 的Shapelet 抽取算法

2.1 分類算法框架

本文設計的面向時間序列有序分類算法框架如圖1 所示。首先，采用SAX 方法將數值型時間序列數據集轉化為符號型時間序列數據集。然后，采用隨機采樣+布隆過濾+Shapelet 評價的策略，實現對Shapelet 的抽取。其中，隨機采樣+布隆過濾旨在提升算法效率以及進行預剪枝。該策略在文獻[18]中已被驗證有效。本文提出一種新的面向SAX 表示時間序列有序分類的Shapelet 評價指標CDCover。圖1 中圖標表示是否滿足約束條件，如果不滿足約束條件，繼續采樣和評價，否則，結束采樣評價。接下來，算法對抽取出的Shapelet 進行自相似移除，降低特征冗余度。最后，選取指定大小的Shapelet 集合作為數據集的新特征，使用新特征對原始時間序列進行特征空間轉換，并訓練有序分類器。

圖1 面向時間序列有序分類算法框架

2.2 Shapelet 評價指標CD-Cover

為提升Shapelet 評估效率，本節介紹一種適用于時間序列有序分類的Shapelet 評價指標CDCover。首先，給出覆蓋、覆蓋集中度和覆蓋優勢度的定義。

定 義 2 （覆蓋） 給定一個SAX 表示的時間序列數據集和 一個Shapelets，的標簽數為Q， 稱 Φ(s)=〈λ1,λ2,···,λQ〉為s在上的覆蓋。其中， λi為包含s的ci類時間序列樣本數。

定 義 3（覆蓋集中度） 給定Shapelets在時間序列數據集上的覆蓋Φ (s)=〈λ1,λ2,···,λQ〉，Q為的 標簽數。則s在上 的覆蓋集中度c on(s)定義為：

式中， V ar(Φ(s))為 Φ(s)的 方差； Varmax為方差上界。根據方差性質可知，當覆蓋取值平均分布在值域兩端時取得最大值/，因此覆蓋集中度的方差上界Varmax=(1-Q)24。從上述定義容易看出，con(s)取值范圍為[0,1]，值越大，表明覆蓋的方差越小，覆蓋越集中。特殊情況下，如果s僅覆蓋一類時間序列，則方差為0， c on(s)值 為1；如果s僅覆蓋類別標簽最小和類別標簽最大的時間序列，且覆蓋比率相同，則方差達到上界，c on(s)值為0。

換言之，覆蓋優勢度為類別最高覆蓋率與次高覆蓋率之差。覆蓋優勢度d om(s)的取值范圍是[0,1]，值越大，表明覆蓋的優勢越明顯。如果Shapelets僅覆蓋一個類別的時間序列，則覆蓋優勢度為該類類別的覆蓋率。

定 義 5（CD-Cover） 給定Shapelets和時間序列數據集D︿，s在D︿上的覆蓋集中度和覆蓋優勢度分別為c on(s) 和 d om(s)， 則s的CD-Cover 評價值為：

式中， α是權重因子，用來調節覆蓋集中度和覆蓋優勢度的權重，默認兩者權重相同，即α 取0.5。如果覆蓋集中度越高，則 c on(s)值越大；如果覆蓋優勢度越大，則 dom(s)越 大，并且， σ(s)取值范圍為[0,1]。因此，如果CD-Cover 值越大，表明其分類能力越強。

下面，通過4 個算例來展示CD-Cover 指標的計算過程及其有效性。

算例1 時間序列數據集D︿ 標 簽Y=〈1,2,3,4〉，即Q=4， 且每類時間序列樣本數分別為 〈 5,5,2,2〉。如果給定一個Shapelets1， 且s1在 數據集上的覆蓋Φ(s1)=〈4,1,0,0〉。 則計算可得， Var(Φ(s1))=0.17，而Varmax=(1-4)2/4=2.25， 所以，s1的覆蓋集中度con(s)=1-0.17/2.25=0.924。根據定義4，覆蓋率為Π(s1)=〈4/5,1/5,0/2,0/2〉，因此，類別1 覆蓋率最高為0.8，類別2 覆蓋率次高為0.2。所以，覆蓋優勢度d om(s1)=0.8-0.2=0.6。根據式（4），計算s1的 CD-Cover 為σ(s1)=0.5×0.924+(1-0.5)×0.6=0.762。

算例3 算例1 相同的時間序列數據集D︿中，如果給定Shapelets3， 在上 的覆蓋Φ (s3)=〈1,1,0,0〉，則Var(Φ(s3))=0.125， con(s3)=1-0.125/2.25=0.944；s3在上的覆蓋率Π (s3)=〈1/5,1/5,0/2,0/2〉，覆蓋優勢度為d om(s3)=0.2-0.2=0 。 因此，s3的CD-Cover值為σ (s3)=0.5×0.944+(1-0.5)×0=0.472。

通過以上算例可以發現，CD-Cover 的目標是找出最優的Shapelet。這些Shapelet 覆蓋的時間序列集中在某個類別附近，且對該類時間序列有很高的覆蓋比例。如果Shapelet 覆蓋且只覆蓋一個類別的所有時間序列，其CD-Cover 值為1。

2.3 基于隨機采樣的Shapelet 抽取算法

基于隨機采樣的面向時間序列有序分類的Shapelet 抽取算法核心步驟算法如下。

算法第1 行：根據參數 ω和 Σ將原始時間序列訓練集D轉換為SAX 表示的時間序列訓練集。

算法第2、3 行：初始化Shapelet 結果集合S和布隆過濾器BF。本算法采用布隆過濾器檢索當前候選Shapelet 是否已經出現并評價，如果此前已經出現則不再進行評價，提升算法效率[18]。

算法第4 行：進入循環，當計時器超過限定時間，結束Shapelet 抽取。

︿D算法第5、6 行：隨機從 中選擇一條時間序列，然后從該時間序列中隨機抽取一個候選Shapelet。

算法第7、8 行：通過布隆過濾器判斷Shapelets是否已經出現；如果已出現，則跳過CD-Cover值計算，重新進行Shapelet 采樣。

算法第9、10 行：更新布隆過濾器，并計算候選Shapelets的CD-Cover 值。

算法第11、12 行：判斷當前候選Shapelets的CD-Cover 值是否大于給定閾值ε，只有評估值大于ε，才將其加入S，保證抽取高質量Shapelet。

算法第13、14、15 行：判斷抽取得到的Shapelet 集合大小是否大于預設數目N的兩倍，如果滿足條件，則從S中移除CD-Cover 值最小的候選Shapelet，同時將閾值 ε更 新為S中Shapelet 的最小CD-Cover 值。保留預設數N兩倍數量的候選Shapelet 是后續還要從中移除自相似的Shapelet。

算法第16 行：首先從S中移除自相似的Shapelet。自相似Shapelet 指的是兩個候選Shapelet取自同一條時間序列，且存在重疊部分。大量自相似的Shapelet 會造成特征空間冗余，降低算法分類效果。移除自相似Shapelet 的算法在文獻 [12,19]中均有介紹。最后，返回剩余候選Shapelet 中CDCover 值最高的N個Shapelet。

2.4 時間復雜度分析

如果時間序列數據集D 的大小為n，所包含的時間序列長度均為m，SAX 窗口大小為 ω。則經過轉換，采用SAX 表示的時間序列數據集D︿中包含n條字符形時間序列，每條長度均為t=「m/ω■。

在上述算法中，將原始時間序列轉換為SAX表示時間序列的時間復雜度為O(nm)（第1 行），移除自相似算法的時間復雜度依賴于候選Shapelet的數量，該數量遠小于時間序列數據集的大小n與長度m的乘積nm。因此，第1 行和第16 行的時間復雜度合計為O(nm)。

本文采用的隨機采樣框架設置了Shapelet 評價時間限制，通常應采用單位時間內的吞吐量來分析算法性能。但是，反過來，也可以通過分析抽取單個候選Shapelet 的時間復雜度來評價算法性能。Shapelet 抽取算法的主要時間開銷為CD-Cover 值計算，需要判斷候選Shapelet 是否存在于某條時間序列中。本文采用KMP 算法，其最壞時間復雜度為O(t)。在n條時間序列中進行字符串匹配，其最壞時間復雜度為O(tn)。該時間復雜度明顯低于文獻[15]提出的Spearman 相關系數和Pearson 相關系數的時間復雜度。換言之，在相同時間約束內，本文提出的算法抽取和評價的Shapelet 數量要遠多于文獻[15]提出的算法。

3 實驗與分析

為了驗證所提Shapelet 抽取算法的有效性，在公開數據集上進行實驗，訓練生成有序分類器，并采用不同指標來評價這些分類器的分類能力。

3.1 實驗準備

3.1.1 實驗環境和數據集

實驗硬件配置為Intel Xeon Gold 5215 CPU（2.5 GHz 主頻，8 核）和64 GB 內存。操作系統為Windows Server 2016。實驗工具采用Python3.6.8、時間序列挖掘工具包sktime 0.9.0 和有序分類開源框架ORCA（ordinal regression and classification algorithm）[20]。ORCA 的運行環境為MATLAB 2018b。

從時間序列分類資源庫UCR 和UEA[16]，根據以下條件篩選出11 個實驗數據集：1）類別標簽之間有明確的全序關系；2）類別數不小于3；3）時間序列長度相等。數據集的基本信息如表1 所示。

表1 實驗數據集

3.1.2 有序分類器和評價指標

傳統ST 方法將抽取的Shapelet 用于訓練標準分類器，如支持向量機、隨機森林等。但標準分類器沒有考慮類別標簽有序的問題。實驗采用了3 種有序分類研究中常用的分類器SVC1V1[21]、SVOREX[22]和SVORIM[22]來驗證本文所提Shapelet抽取算法。其中，SVC1V1 是標量分類器，SVOREX和SVORIM 是有序分類器，這些分類器的實現均來自ORCA 開源框架[20]。

實驗采用CCR 和Weighted-κ 作為分類器分類能力的評價指標。前者是最常用的分類評價指標，但沒有考慮類別標簽有序的特征；后者是目前研究驗證的、更適用于評價有序分類能力的指標[23]。CCR和Weighted-κ 分別由式（5）和式（6）計算所得。

式中，n是時間序列測試集大小；ci和分別表示測試集中時間序列樣本Ti的實際標簽和分類器預測標簽； δ (ci,)是 Kronecker 函數，當且僅當ci和相同時，函數值為1，否則函數值為0。CCR 取值范圍為[0,1]，值越大，表明分類器性能越好。

Weighted-κ 取值范圍為[-1,1]，值越大，表明分類器的分類效果越好。

3.1.3 實驗參數設置

實驗中，本文提出的Shapelet 抽取算法的參數設置如表2 所示。其中CD-Cover 計算公式中的權重因子α 設置為0.5，換言之，設定覆蓋集中度和覆蓋優勢度有同等的重要性；Shapelet 抽取過程中根據候選Shapelet 的CD-Cover 值是否大于初始閾值ε決定是否對其保留， ε設置為0.5。此外，SAX 的參數 ω和 Σ分別設置為1 和10。這樣設置有兩個理由：1）文獻[12]通過實驗證明該設置在大部分數據集上能取得較好的分類結果；2）本文主要是利用SAX 的符號表示能力，即將數值型時間序列轉換為符號型時間序列，并不特別關注其對數據的維度約減能力。此外，訓練有序分類器的時候，3 種支持向量分類器的懲罰參數和核函數參數都設置為相同的搜索范圍 {10-3,10-2,···,102,103}，并采用5 折交叉驗證，搜索最優參數組合。時間約束 τ設定為300 s。

表2 實驗參數設置

3.2 實驗結果

本節首先驗證所提CD-Cover 指標的有效性。實驗將根據IG、Spearman 相關系數、Pearson 相關系數和CD-Cover 4 種評價指標抽取的Shapelet，分別用來訓練3.1.2 節中的3 種分類器，然后比較4 種指標在實驗數據集上的有序分類效果。由于算法具有隨機性，為保證結果的公平性，CCR 和Weighted-κ 結果都取50 次實驗的平均值。

1）CCR

采用3 種分類器SVC1VC、SVOREX 和SVORIM 在11 個數據集上進行實驗，得到的CCR 結果如表3 所示，表中IG、 ρ、 γ和 σ分別代表IG、Spearman 相關系數、Pearson 相關系數和CD-Cover指標。對每個數據集而言，同一分類器不同指標的CCR 最高值用粗體標注。表格最后的“勝出”，表示采用當前分類器的4 種Shapelet 評價指標中，各指標在11 個數據集上取得CCR 最優分類結果的數據集個數。如采用SVC1V1 分類器結合IG 評價指標，分別在第2、第6 和第9 個數據集上取得3 次最優分類結果。“排名”表示采用當前分類器的4 種Shapelet 評價指標中，各指標在11 個數據集上取得的CCR 值的平均排名。例如，采用SVORIM 分類器結合Pearson 相關系數，在11 個數據集上的平均排名為2.55。CD-Cover 指標在3 種分類器上“勝出”的數據集都是6 個（超過數據集的半數），且在3 種分類器上的平均排名都最高，分別為1.77、1.91 和1.86。

表3 不同Shapelet 評價指標的CCR 值

2）Weighted-κ

表4 給出了采用3 種分類器結合4 種Shapelet評價指標在11 個數據集上獲得的Weighted-κ 結果。由表4 可知，在11 個數據集上，CD-Cover 指標在3 種分類器上分別取得了6 次、6 次和7 次最優的表現。同時，CD-Cover 指標在3 種分類器上都取得了最高的平均排名，分別為1.77、1.64 和1.50。

表4 不同Shapelet 評價指標的Weighted-κ 值

3.3 實驗分析

為了更清晰地對實驗結果進行分析，將3.2 節的實驗數據繪制為散點圖，如圖2 所示。3 個散點圖分別代表CD-Cover 與IG、Spearman 相關系數和Pearson 相關系數在3 種算法、11 個數據集上“一對一”比較的結果，每個散點圖中散點數目合計33 個。圖2 的橫坐標和縱坐標分別表示采用CD-Cover 指標與對比指標得到的CCR 值。散點如果正好處于對角線上，表明采用兩種指標得到的CCR 值相同；如果散點處于對角線右下方，表明采用CD-Cover 指標得到的CCR 值更優；如果散點處于對角線左上方，表明采用對比指標得到的CCR 值更優。從圖2 可以發現，大多數散點處于對角線右下方，或者在對角線附近；明顯處于對角線左上方的散點數目較少。

圖2 CD-Cover 與3 個指標的CCR 值比較

圖3 為采用CD-Cover 指標與采用3 個對比指標得到的Weighted-κ 值對比結果。圖3 的橫坐標和縱坐標分別表示采用CD-Cover 指標與對比指標得到的Weighted-κ 值。可以發現，圖3 的大多數散點都處于對角線右下方區域，且相對圖2 而言，偏離對角線更明顯。圖2 和圖3 表明，與采用的3 種對比指標相比，CD-Cover 指標無論是CCR 還是Weighted-κ，都能得到更好的結果。

圖3 CD-Cover 與3 個指標的Weighted-κ 值比較

3.4 計算效率分析

參與比較的仍然是3.3 節的4 種評價指標。區別在于，IG、Spearman 和Pearson 相關系數不需要將原始時間序列進行SAX 表示。有序分類器只選擇SVORIM 分類器，分類器的評價指標選擇Weighted-κ。基于不同Shapelet 評價指標的Shapelet抽取算法均持續運行20 min，并記錄下每分鐘的Weighted-κ 值。為保證穩定性，實驗結果為50 次實驗的均值，結果如圖4 所示。

圖4 的每個子圖4a～圖4k 分別對應單個數據集的實驗結果。所有子圖的橫坐標均表示Shapelet抽取算法的執行時間（min），縱坐標表示基于不同評價指標抽取的Shapelet 訓練的SVORIM 分類器，在測試數據集上獲得的Weighted-κ 值。分析圖4 可以發現：1）在不同執行時間內，基于CDCover 指標抽取Shapelet 訓練分類器的結果，整體上優于其他3 種評價指標；2）基于CD-Cover 指標抽取Shapelet，在較短時間內就能獲得高質量的抽取結果（Colposcopy 數據集為8 min，其余數據集均為2～5 min）。根據上述實驗結果可知，本文所提的CD-Cover 評價指標在計算效率上明顯優于其他3 個評價指標，因為給定相同時間限制，基于CD-Cover 指標的方法能夠評估更多的Shapelet。

4 結 束 語

針對當前基于Shapelet 的時間序列有序分類研究中，采用Spearman 相關系數和Pearson 相關系數進行Shapelet 抽取時計算效率較低的問題，本文提出了一種基于SAX 表示時間序列的Shapelet 評價指標CD-Cover，以及一種基于隨機采樣的Shapelet 抽取算法。在11 個時間序列數據集上進行了實驗。實驗結果證明了CD-Cover 評價指標以及所提Shapelet 抽取算法的有效性，且展示了其在計算效率上的優越性。下一步將繼續研究時間序列長度不相等的情況，并將算法擴展至多元時間序列，并結合實際應用對時間序列有序分類問題進行深入研究。