馮冠璽，馬 超，石小川，張 典

（1.武漢大學 國家網(wǎng)絡(luò)安全學院；2.空天信息安全與可信計算教育部重點實驗室，湖北 武漢 430072）

0 引言

如今隨著互聯(lián)網(wǎng)、電子傳感器等滲透到社會的各個領(lǐng)域，全球每天都會誕生海量的時序數(shù)據(jù)。股市中的股價走勢、醫(yī)學領(lǐng)域的心電圖在一段時間內(nèi)的變化，以及行走時手機傳感器在x 軸、y 軸方向上的加速度變化都可看作時序數(shù)據(jù)，因此時序數(shù)據(jù)挖掘吸引了很多研究者關(guān)注。時序數(shù)據(jù)分類作為其基礎(chǔ)任務(wù)，近年來一直是研究的重點。目前，研究者們已提出上百種時間序列分類方法［1］。這些方法可分為3 類：①基于全局距離的分類方法；②基于特征的分類方法；③基于深度學習的分類方法。

基于全局距離的分類方法較為簡單。早期研究者直接將最近鄰方法（One Nearest Neighbor，1NN）和歐氏距離（Euclidean Distance）方法應(yīng)用到時序分類中，但無法處理因時間序列發(fā)生扭曲變形而無法匹配的問題，因此分類表現(xiàn)較差。為了解決這一問題，研究者嘗試使 用1NN 和動態(tài) 時間規(guī) 整（Dynamic Time Warping，DTW）距離方法［2］對時序數(shù)據(jù)進行分類。該方法雖在分類表現(xiàn)上優(yōu)于歐氏距離，但時間耗費更多。后續(xù)有學者陸續(xù)提出各種基于DTW 的分類方法的變種［3-4］，但基于全局距離的分類方法始終無法避免同一個問題：僅考慮全局特征會導(dǎo)致時間序列的局部特征被噪聲數(shù)據(jù)所淹沒。

為了解決這一問題，文獻［5］提出特征子序列（Shapelets）概念，至此基于特征的分類方法成為新的研究熱點。特征子序列可看作是一類時間序列中最具有辨識性的子段，由于該方法聚焦于尋找局部特征，因此在全局相似但局部差異較大的數(shù)據(jù)集中具有更好的表現(xiàn)。此外，特征子序列方法因能給出原時間序列中的關(guān)鍵部位，所以具有較強的可解釋性。在文獻［5］的基礎(chǔ)上，文獻［6］篩選出最佳的k 條特征子序列，并基于這些特征子序列將時間序列轉(zhuǎn)換為僅含有k 個屬性的個體，在進一步擴大了分類器選擇范圍的同時，降低了時序數(shù)據(jù)維度。此后的特征子序列相關(guān)研究主要致力于提高搜尋篩選特征子序列的速度和準確度兩個方向上。

隨著深度學習技術(shù)在機器視覺、自然語言處理等領(lǐng)域得到廣泛應(yīng)用［7-9］，研究者們開始嘗試將深度學習技術(shù)應(yīng)用于時間序列分類領(lǐng)域。文獻［10］將多層感知機（Multi Layer Perception，MLP）、全卷積神經(jīng)網(wǎng)絡(luò)（Fully Convolutional Networks，F(xiàn)CN）、殘差網(wǎng) 絡(luò)（Residual Networks，ResNet）等網(wǎng)絡(luò)模型應(yīng)用到時序分類任務(wù)中，其中有些模型取得了與傳統(tǒng)37 個分類器集成的COTE［11］方法相當?shù)谋憩F(xiàn)。然而，相較于具有較強可解釋性的傳統(tǒng)模型，深度學習模型被視為黑盒模型，研究者們很難從中找出模型的判斷依據(jù)。

綜上，基于特征子序列的方法雖具有較強的可解釋性，但受限于傳統(tǒng)機器學習的學習能力，無法生成準確的特征子序列以提高分類表現(xiàn)。得益于強大的學習、擬合能力，深度學習在時序分類的表現(xiàn)上優(yōu)于其他方法，但端到端的黑盒模型并不具有解釋性。

為了改善上述問題，本文首次提出將卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）中的卷積核（Kernel）作為特征子序列的概念，并據(jù)此改造CNN 網(wǎng)絡(luò)，使CNN 網(wǎng)絡(luò)能夠定位原時間序列的關(guān)鍵子段，從而增強了CNN 模型的可解釋性。

本文的主要貢獻如下：

（1）首次提出將CNN 網(wǎng)絡(luò)中的卷積核作為特征子序列的思想，拓寬了特征子序列的概念。

（2）改造CNN 網(wǎng)絡(luò)結(jié)構(gòu)，提出基于CNN 網(wǎng)絡(luò)模型提取特征子序列的方法。

（3）結(jié)合特征子序列思想提出一種針對時序領(lǐng)域的可解釋性算法。

（4）通過在 UCR 公開數(shù)據(jù)集上進行實驗，本文將Kernel-Shapelets 方法與現(xiàn)有基于全局距離的方法、基于特征的方法和基于深度學習的方法在分類表現(xiàn)、可解釋性等多個方面進行了比較。

1 概念與定義

1.1 時間序列

任何以時間先后順序排列的實數(shù)序列都可視為時間序列：

給定一條長度為m 的時間序列T，T中長度為l的子段被稱為時序子序列：

訓練集中所有時間序列的子序列組成了特征子序列的候選集。

1.2 距離度量

兩條時間序列之間的差異大小一般用“距離”概念來表示。在以往的研究中，研究者通常采用歐式距離作為距離度量公式。設(shè)兩條時間序列T和T′長度為m，其歐式距離計算公式為：

1.3 特征子序列

文獻［5］首次提出特征子序列（Shapelets）概念，并將特征子序列定義為時間序列中最能代表其類別特征的子序列。為了從數(shù)據(jù)集中篩選出最佳特征子序列，采用信息增益（Information Gain）作為特征子序列的評價標準，信息增益越大，越能代表該類時間序列。

1.4 基于特征子序列的數(shù)據(jù)表征

廣義上的基于特征子序列的數(shù)據(jù)表征（Shapelets Transformation）指通過某種映射將時間序列轉(zhuǎn)換到新的維度空間。例如，文獻［6］、［12］將k 條特征子序列與時間序列之間的歐式距離作為時序數(shù)據(jù)的k 維特征，其轉(zhuǎn)換過程如圖1所示。

Fig.1 Distance-based shapelets transformation method圖1 基于距離的特征子序列表征方法

2 相關(guān)工作

2.1 基于全局距離的分類方法

早期時序數(shù)據(jù)分類往往基于全局距離方法。研究者最早使用歐氏距離作為距離度量標準，該方法易于理解且計算簡單，但點對點的距離計算方式在面對同種類別但相位不同的兩條時間序列時，度量結(jié)果會存在很大誤差。為了解決這一問題，研究者將動態(tài)規(guī)劃引入到距離計算方法中，提出了DTW 算法［2］。通過動態(tài)規(guī)劃，DTW 能夠?qū)r間序列拉伸或收縮，從而盡可能減小相位偏移造成的誤差。但動態(tài)規(guī)劃算法的引入也導(dǎo)致DTW 算法的時間復(fù)雜度增長為O(n2)，其中n為時間序列長度，而歐氏距離的時間復(fù)雜度僅為O(n)。由于時間序列維度可以達到幾百甚至上千維，因此DTW 帶來了巨大的時間耗費。后續(xù)學者提出一系列DTW 算法加速的研究，但基于全局距離的分類方法始終無法解決時序數(shù)據(jù)局部特征被高維度和噪聲所淹沒的問題。

如圖2 所示，兩類樹葉整體形狀相似，但在葉柄部位，一類樹葉呈直角，另一類樹葉呈鈍角。通過順時針掃描，并計算樹葉輪廓與中心點之間的距離，可將樹葉輪廓延展為時間序列并進行分類。然而，當兩類樹葉整體輪廓相同而僅有少量局部不同時，基于全局距離的方法無法正確地進行分類。

Fig.2 Overall outline of the two types of leave圖2 兩類樹葉整體輪廓延展示意圖

2.2 基于特征子序列的分類方法

為了能夠提取出局部特征，2009 年Ye 等［5］首次提出特征子序列概念。與以往關(guān)注全局距離的分類方法不同，基于特征子序列的方法將關(guān)注點放在了局部特征。研究者將決策樹分類器與特征子序列篩選相結(jié)合，以信息增益為標準，在找出最佳特征子序列的同時，對時序數(shù)據(jù)進行分類。但其仍遺留兩個缺陷：一是分類器與特征子序列的提取過程緊耦合，無法使用除決策樹外的其他分類器；二是通過遍歷特征子序列候選集來搜索最佳特征子序列所花費的時間過長。為此，2014年Hills 等［6］將特征子序列與分類器解耦合，通過找出top-k 條特征子序列，計算時間序列與k 條特征子序列之間的距離，并將該k 個距離數(shù)值作為時間序列的k 維屬性值，通過這種方式表征后的數(shù)據(jù)集可使用各種分類器。同年，Grabocka 等［13］提出“Learning Time Series Shapelets（LTS）”概念，即特征子序列不再是從數(shù)據(jù)集中抽取得到的，而是通過學習得到的。研究者首先隨機初始化k 條特征子序列，分別計算k 條特征子序列與時間序列的距離作為邏輯回歸的k 個屬性值，并通過交叉熵損失函數(shù)調(diào)整k 條特征子序列對應(yīng)的權(quán)重及形狀。該方法將特征子序列選擇范圍從訓練集擴大到整個實數(shù)空間，但由于其整體模型采用邏輯回歸分類器，學習能力與分類表現(xiàn)并不理想。

2020 年，Dempster 等［14］提出隨機卷積核表征法（Random Convolutional Kernel Transform，ROCKET）方法，該方法將卷積核看作特征子序列，通過生成海量（默認為5 000個）、隨機大小、隨機權(quán)重的卷積核，將時序數(shù)據(jù)重新表征，并對表征后的數(shù)據(jù)使用線性分類器進行分類。由于無需學習、更新卷積核權(quán)重，ROCKET 方法的訓練速度遠超其他特征子序列方法。2021 年，研究者又提出Mini-ROCKET 方法［15］進一步加快了訓練速度，但海量的卷積核導(dǎo)致權(quán)重過于分散，無法分辨出原時間序列中對分類有重要影響的部位。

2.3 基于深度學習的分類方法

隨著深度學習在機器視覺、自然語言處理領(lǐng)域的迅猛發(fā)展，有研究者開始將深度學習技術(shù)應(yīng)用于時序數(shù)據(jù)挖掘中［16-17］。在時序數(shù)據(jù)分類領(lǐng)域，Cui 等［18］提出多尺度卷積神經(jīng)網(wǎng)絡(luò)MCNN，該方法首先將原始時間序列分別進行平滑、下采樣處理，并將處理后的時間序列與原序列拼接在一起，投放到只有一層卷積層的網(wǎng)絡(luò)模型中。雖然該方法能夠?qū)尉S時間序列擴展到多維，但需要進行大量的預(yù)處理，且實驗證明該方法的分類表現(xiàn)較差［10］。Fawaz 等［10］將MLP、ResNet、FCN、MCNN、t-LeNet［19］、MCDCNN［20］、Time-CNN［21］、TWIESN［22］等 9 種方法在公開數(shù)據(jù)集上進行了實驗對比，結(jié)果表明，基于卷積網(wǎng)絡(luò)框架的ResNet 與FCN 明顯優(yōu)于其他算法。相較于傳統(tǒng)模型，深度學習模型雖然具有更好的分類表現(xiàn)，但這些模型往往是端到端的黑盒模型，失去了可解釋性。深度學習可解釋性相關(guān)研究大多集中在計算機視覺領(lǐng)域，或者僅將已有的可解釋模型遷移到時序領(lǐng)域，很少有針對時序數(shù)據(jù)設(shè)計可解釋性模型的研究。

本文提出的方法Kernel-Shapelets 綜合了CNN 網(wǎng)絡(luò)的學習能力和傳統(tǒng)特征子序列的可解釋性，相比傳統(tǒng)機器學習模型，CNN 網(wǎng)絡(luò)強大的學習能力能生成更加精確的特征子序列，此外Kernel-Shapelets 首次提出利用特征子序列增強CNN 網(wǎng)絡(luò)模型的可解釋性。

3 Kernel-Shapelets卷積網(wǎng)絡(luò)模型

3.1 卷積核與特征子序列

本文認為特征子序列與卷積核之間具有很多相似性：①特征子序列在整條時間序列之上按照一定步長滑動并計算距離，而卷積核在輸入數(shù)據(jù)上也是按照一定步長進行滑動；②計算出一系列距離之后，以往的研究采用最小距離作為特征值，這與最小池化層的作用相同。本文通過公式推導(dǎo)可以得出：基于距離的表征方式可被視為基于卷積表征方式的特殊形式。

在文獻［5］、［6］、［12］、［13］中，研究者將時間序列與子序列之間的距離作為表征后的特征值，仍設(shè)時間序列為T，長度為m，特征子序列為S，長度為l，距離表征數(shù)學表達式如公式（5）所示：

基于以上推導(dǎo)，本文重新對特征子序列作出定義：任何一段實數(shù)序列，只要滿足如下要求便可視作特征子序列：①給定一條時間序列，該實數(shù)序列段能給出某種度量標準下的差異大??；②能通過該實數(shù)序列找出給定時間序列中的關(guān)鍵部分。

文獻［14］、［15］雖然同樣采用卷積核作為特征子序列，但其卷積核是隨機生成的，且在整個訓練過程中并沒有通過學習更新卷積核內(nèi)部權(quán)重，也無法通過卷積核定位原時間序列的關(guān)鍵部位。本文將利用CNN 網(wǎng)絡(luò)學習生成更精確的特征子序列，并基于學習生成的特征子序列給出原時間序列的關(guān)鍵部位。

3.2 全局平均池化與全局最大池化

3.1節(jié)以數(shù)學形式證明了使用全局最大池化操作與傳統(tǒng)Shapelets 方法采用最小距離作為特征在本質(zhì)上保持一致。此外，相比于全局平均池化（Global Average Pooling Layer，GAP），全局最大池化操作能夠保留更多位置信息。不同的池化操作對比如圖3所示。

全局平均池化得出的特征值為平均特征，即該特征值為輸入中每個位置數(shù)值的加權(quán)平均，該方式使得池化輸出丟失了精確的位置信息。而全局最大池化的輸出Outputpooling可通過argmax(Outputpooling)的方式迅速反向定位池化輸出所對應(yīng)輸入中的位置，即全局最大池化的輸出保留了位置信息，從而能夠定位原時間序列中的關(guān)鍵位置。

由于全局最大池化操作與傳統(tǒng)Shapelets 方法采用最小距離作為特征值的做法在本質(zhì)上保持一致，且全局最大池化輸出充分保留了位置信息，因此本文后續(xù)取消了全局平均池化層，而改用全局最大池化層。

Fig.3 Comparison of different pooling operations圖3 不同池化操作對比

3.3 網(wǎng)絡(luò)模型結(jié)構(gòu)

本文基于CNN 網(wǎng)絡(luò)模型進行特征子序列的生成。與文獻［10］中的CNN 網(wǎng)絡(luò)框架不同，為了能夠定位出原時間序列的關(guān)鍵部位，本文取消了全局平均池化層，改用全局最大池化層。整體模型如圖4所示。

Fig.4 Overall network framework structure圖4 整體網(wǎng)絡(luò)框架結(jié)構(gòu)

前三層的卷積層對原始時間序列進行去噪和特征提取。在3 層卷積操作后，通過全局最大池化層提取第三層卷積核各個通道與原時間序列之間的“距離”，之后通過線性全連接層進行分類。

3.4 特征子序列生成與原時間序列關(guān)鍵位置定位

卷積核越重要，越有可能成為特征子序列。在網(wǎng)絡(luò)模型壓縮過程中，一種較為簡潔的思路是：基于全連接層的權(quán)重絕對值大小對卷積核進行剪枝，絕對值越小越容易被丟棄。本文延用這種思想，將權(quán)重絕對值大小作為卷積核重要性的數(shù)值標準，以此篩選出top-k 個卷積核作為特征子序列。

在找出top-k 個卷積核作為特征子序列后，基于算法1找出關(guān)鍵部位：

算法1基于重要卷積核定位原時間序列的關(guān)鍵部分

算法1 詳細描述了基于重要卷積核定位原時間序列關(guān)鍵部分的過程。該過程主要分為兩部分，第一部分是將原時間序列輸入到訓練好的模型中，通過前向傳播獲取最后一層卷積層中對應(yīng)卷積核的輸出。通過對輸出進行遍歷，找到輸出中最大值所在位置。通過填充，卷積操作前后的維度與原輸入維度保持不變，因此卷積核輸出的最大值所在位置即為原時間序列中關(guān)鍵部分的起始時間點。圖5 展示了基于Kernel-Shapelets 方法定位出GunPoint 數(shù)據(jù)集的關(guān)鍵位置（彩圖掃OSID 碼可見）。

Fig.5 Locate key positions of GunPoint dataset based on Kernel-Shapelet method圖5 基于Kernel-Shapelet方法定位出GunPoint數(shù)據(jù)集關(guān)鍵位置

4 實驗結(jié)果與分析

4.1 實驗設(shè)置

為了驗證Kernel-Shapelets 模型所生成特征子序列的有效性，本文利用Kernel-Shapelets 方法生成的特征子序列對數(shù)據(jù)集進行重新表征，并使用隨機森林（Random Forest）作為分類器與其余基于特征子序列的方法以及深度學習模型在分類表現(xiàn)上進行比較。

本文的實驗環(huán)境基于Win10 系統(tǒng)，顯卡是NVIDIA Ge-Force RTX 2080Ti，代碼基于Python 3.9 實現(xiàn)，Pytorch 庫的版本為1.10.0。綜合參考文獻［10］中的實驗設(shè)置，同時為了能夠更公平地與其他模型進行橫向?qū)Ρ龋疚脑O(shè)置epochs 為2 000，學習率為0.001，每個數(shù)據(jù)集進行5 次實驗，取分類表現(xiàn)最接近平均準確率的模型作為最終的實驗?zāi)Ｐ?。在基于特征子序列表征的過程中，篩選出100 條特征子序列，并將任一條時間序列轉(zhuǎn)換為100維的特征向量。

4.2 數(shù)據(jù)集

UCR 時間序列倉庫集（http：//www.cs.ucr.edu/～eamonn/time_series_data/）中目前一共有128 個數(shù)據(jù)集，但多數(shù)數(shù)據(jù)集規(guī)模較小，訓練集中的時間序列條數(shù)在500 及以下的數(shù)據(jù)集有104 個。為了避免深度學習方法出現(xiàn)過擬合，本文選取倉庫中所有訓練集規(guī)模在1 500 條時序數(shù)據(jù)以上的數(shù)據(jù)集。數(shù)據(jù)集規(guī)模信息參見表1。

Table 1 Dataset size information表1 數(shù)據(jù)集規(guī)模信息

4.3 對比實驗

目前，針對時間序列的分類方法基本可分為基于全局距離的方法、基于特征的方法以及基于深度學習的方法，本文也采用這3 類方法進行實驗對比。在基于全局距離的方法中，選用分類表現(xiàn)較好的1NN+DTW 方法；在基于特征的方法中，選用Learning Shapelets 方法以及Fast Shapelets 方法，其中Learning Shapelets 屬于學習生成式方法，而Fast Shapelets 為抽取式方法；在基于深度學習的方法中，選用FCN 方法與MCDCNN 方法。

4.4 實驗結(jié)果分析

各模型分類準確率的實驗結(jié)果如表2 所示。從表中可以看出，Kernel-Shapelets 的分類表現(xiàn)與FCN 十分接近，且優(yōu)于其他分類器。

Table 2 Performance of each classifier表2 各模型分類準確率

從圖6 的臨界差分圖（critical difference diagram）中也可以看出，本文提出的Kernel-Shapelets 優(yōu)于其他Shapelets方法，僅次于FCN 模型，但本文方法提供了更強的可解釋性，且對于長序列時序數(shù)據(jù)，經(jīng)過特征子序列重新表征后的數(shù)據(jù)集規(guī)模更小。

Fig.6 critical difference diagram on classifiers圖6 各分類器之間臨界差分圖

以FordB 為例，通過選取100 條特征子序列對數(shù)據(jù)集進行表征，表征后的數(shù)據(jù)集規(guī)模由3 636*500 變?yōu)? 636*100，而準確率僅由0.819 下降為0.801。表3 展示了表征前后的數(shù)據(jù)集規(guī)模大小變化與準確率下降情況。

Table 3 Comparison of size and accuracy before and after representation of long series datasets表3 長序列數(shù)據(jù)集表征前后規(guī)模及準確率對比

在可解釋性表現(xiàn)方面，以GunPoint 數(shù)據(jù)集為例對Kernel-Shapelets 的可解釋性進行說明。本文分別通過Kernel-Shapelets 方法和Learning Shapelets 方法生成兩條特征子序列，并基于這兩條特征子序列將數(shù)據(jù)集中的每條時間序列轉(zhuǎn)換為具有二維特征的個體。圖7 展示了經(jīng)過表征后，GunPoint數(shù)據(jù)集不同類別個體的分布情況。

從圖7（a）中可以清楚地看出，經(jīng)過Kernel-Shapelets表征后，不同類別個體之間的界限更加清晰，研究者可更加清晰地指出不同類別之間的差異。而在圖7（b）中，基于Leaning Shapelets 表征后的數(shù)據(jù)集個體界限仍然不夠分明，這也從一定程度上解釋了Kernel-Shapelets 的分類表現(xiàn)優(yōu)于Leaning Shapelets 的現(xiàn)象。

5 總結(jié)與展望

在時序數(shù)據(jù)分類領(lǐng)域，深度學習模型相較于其余分類模型具有更好的分類表現(xiàn)，但缺少了可解釋性。綜合借鑒深度學習的學習能力和特征子序列的可解釋性，本文提出一種基于卷積網(wǎng)絡(luò)生成特征子序列的方法Kernel-Shapelets，該方法基于全連接層權(quán)重篩選出top-k 個卷積核作為特征子序列，并將這些卷積核對應(yīng)的全局最大池化層的輸出作為特征值。通過采用UCR 時序倉庫中訓練集規(guī)模在1 500 以上的數(shù)據(jù)集進行實驗，證明了Kernel-Shapelets 的分類表現(xiàn)優(yōu)于其他特征子序列模型，能夠在保證分類表現(xiàn)不下降或輕微下降的情況下提高模型的可解釋性。

Fig.7 Representation of GunPoint based on Kernel-Shapelets and Learning Shapelets圖7 基于Kernel-Shapelets與Learning Shapelets表征后的GunPoint數(shù)據(jù)集

本文提出的方法雖然能夠提高模型的可解釋性，且分類表現(xiàn)優(yōu)于其他特征子序列模型，但基于特征子序列方法的超參數(shù)尋優(yōu)問題仍未得到解決。在本文中子序列的數(shù)目和長度仍采用經(jīng)驗值，因此如何設(shè)計模型以規(guī)避超參數(shù)，或通過模型學習得到這兩個參數(shù)的最優(yōu)值將成為下一步研究方向。