宋奎勇, 王念濱, 王紅濱

(1. 哈爾濱工程大學 計算機科學與技術學院, 哈爾濱 150000； 2. 呼倫貝爾職業(yè)技術學院 信息工程系, 內蒙古 呼倫貝爾 021000)

0 引 言

多變量時間序列在工業(yè)、 醫(yī)療、 金融諸多領域廣泛存在, 如醫(yī)療中檢測病人心跳、 血壓、 脈搏數(shù)據(jù)； 機械振動中不同位置傳感器檢測齒輪故障數(shù)據(jù)。一些與時間相關的數(shù)據(jù)如基因、圖像也可通過數(shù)據(jù)變換成為時間序列。通常, 相較于單變量時間序列, 分類多變量時間序列會更復雜[1]。

在當前研究中, 多變量時間序列分類包括基于距離的、 基于特征的和基于集成學習的方法[1]。基于距離的方法考慮到同類之間距離較近而不同類之間距離較遠, 常用的距離度量有歐氏距離、 馬氏距離[2]、 動態(tài)時間彎曲(DTW： Dynamic Time Warping)距離[3]。DTW方法不但在單變量分類中有很好的效果, 在多變量分類中也有不錯的表現(xiàn)[4]。Shapelets[5-8]和深度學習[9-11]是當前基于特征多變量分類主流方法。Shapelets是通過學習得到的時間序列子序列, 此方法可解釋強、 準確度較高, 但是, 生成Shapelets的時間復雜度較高。近年來, 深度學習方法如卷積神經(jīng)網(wǎng)絡(CNN： Convolutional Neural Network)[12]、 循環(huán)神經(jīng)網(wǎng)絡(RNN: Recurrent Neural Network)[10]及長短期記憶網(wǎng)絡(LSTM: Long Short Term Memory)[11]在多變量分類中得到關注, 這些方法通過構建深度模型提取深度特征融合分類, 分類準確度較高, 但是, 與其他深度學習方法一樣可解釋性不強?；诩蓪W習方法[13-14]可以融合不同分類方法的優(yōu)點, 取長補短, 能取得較高的分類結果, 然而選擇適合的集成方法是一個挑戰(zhàn)。

集成學習通過組合多個基分類器為一個強分類器, 可以獲得比單一基分類器優(yōu)越的泛化性能。集成學習方法可分成兩大類： 一類是基分類器間存在強依賴關系, 必須串行生成的序列化方法, 如Boosting[15]； 另一類是基分類器間不存在依賴關系, 可同時生成的并行化方法, 如Bagging[16]和Random Forest[17]。筆者提出基于Shapelets的多變量D-S證據(jù)加權集成分類方法。首先, 使用Shapelets作為基分類器, 基分類器間不存在依賴關系, 且單個Shapelets分類準確度較高, 能得到“好而不同”的基分類器, 類似于Bagging方法策略； 其次, 使用D-S證據(jù)加權集成基分類器。不同基分類器性能不同, 使用基分類器分類準確率對基分類器加權, 基分類器分類準確率越高, 則在集成時所占權重越大, 如此集成分類器必然越準確。D-S證據(jù)理論集成能給出合理的結果, 并且為了減少證據(jù)沖突, 對證據(jù)施加限制側率。最后, 與經(jīng)典DTW及最新的深度學習、 集成學習方法進行了比對, 取得了較好的結果。

1 背景知識

1.1 Shapelets

單變量時間序列T={t1,t2,…,tn},T的長度為n,T對應類標簽為c,c∈C。若T兩個等長為l時間子序列s、r, 且l

(1)

定義1 給定長度為l的序列s及長度為n的序列T, 且l

(2)

定義2 一個Shapelets定義為f=(s,l,δ,c),s是長度為l的子序列,δ是分裂閾值,c是類標簽, 這里有

?(T,c)∈D?ddist(s,T)≤δ

(3)

在圖1中T為單變量時間序列,S為Shapelets, 最佳匹配位置為30, Shapelets的長度為20。

圖1 時間序列Shapelets示例Fig.1 Time series shapelets Example

1.2 D-S證據(jù)理論

D-S證據(jù)理論[18]是經(jīng)典概率論的推廣, 能滿足比貝葉斯理論更弱的條件, 具有直接表達“不確定”和“不知道”的能力。D-S證據(jù)理論用辨識框架Θ表示樣本空間, 它是一個有限集合, 集合中元素互不相容且構成完備性。Θ的冪集表示為2Θ, 冪集是Θ所有子集的集合。

定義4 設函數(shù)fBel： 2Θ→[0,1], 且滿足

(4)

則fBel稱為A的信任函數(shù), 它表示證據(jù)對A為信任程度。

定義5 設函數(shù)pl: 2Θ→[0,1], 且滿足

pl(A)=1-fBel(A), ?A?Θ

(5)

pl稱為似然函數(shù), 它表示對A為非假的信任程度, 而fBel(A)是對A為假的信任程度, 即對A的懷疑程度, 如圖2所示。

圖2 信息的不確定性Fig.2 Uncertainty of information

由于fBel(A)表示對A為真的信任程度, PI(A)表示對A為非假的信任程度, 而且PI(A)≥fBel(A), 稱fBel(A)和PI(A)分別為對A信任度的下限和上限, 記為[PI(A),fBel(A)], 其表示了對A的不確定區(qū)間。

定義6 設m為基本概率賦值函數(shù), 如果m(A)>0, 則稱A為Bel的焦元； 信任函數(shù)fBel的所有焦元聯(lián)合稱為核。

(6)

設fBel1,fBel2,…,fBeln是同一識別框架Θ上信任函數(shù),m1,m2,…,mn是其對應的基本概率分配函數(shù), 若m為m1,m2,…,mn的合成概率分配函數(shù), 則有

(7)

2 基于Shapelets多變量D-S理論加權集成分類

若m變量時序數(shù)據(jù)集T由Ti組成,Ti=[T1,T2,…,Tm],i∈[1,k], 其中Tj為第j個維數(shù)為n的單變量數(shù)據(jù)。為在單變量上學習基分類器, 首先把多變量數(shù)據(jù)重新劃分為m組單變量數(shù)據(jù),m變量數(shù)據(jù)集T共k個, 從每個多變量Ti中抽出單變量數(shù)據(jù), 重新組成一個單變量數(shù)據(jù)集。 如抽出T1組成新的單變量數(shù)據(jù)集T11,T12,…,T1k。這樣, 就把一個多變量數(shù)據(jù)集劃分成m個單變量數(shù)據(jù)集, 然后, 可以在訓練集上學習Shapelets并計算器分類準確率。

2.1 學習Shapelets并計算權重

Shapelets[5]是一組時間序列的子序列, 在本文中, 把Shapelets作為一個基分類器, 則m變量時間序列數(shù)據(jù)對應m個基分類器。為了在單變量上學習Shapelets并確定最優(yōu)閾值, 引入文獻[5]中基于最大熵方法確定最優(yōu)分裂閾值, 熵計算公式如下

(8)

其中mc是c類數(shù)據(jù)的數(shù)量,M是所有時間序列的數(shù)量。為了獲得基分類器Shapelets, 計算所有候選Shapelets最優(yōu)分裂閾值, 并把數(shù)據(jù)集分成DL和DR兩部分。若數(shù)據(jù)集DL和DR的熵為EL和ER, 則

(9)

在所有候選Shapelets中, 得到最大的IIG為Shapelets, 也就是基分類器。如圖3所示, 對二分類數(shù)據(jù)進行分類, 在數(shù)軸上實圓為一類, 方塊為一類, 中間帶箭頭的豎線位置為最優(yōu)分裂點, 在二分類中最優(yōu)分裂點把數(shù)軸分成兩部分。

圖3 最優(yōu)分裂閾值Fig.3 Optimal split threshold

從圖3可知, 最優(yōu)分裂點實圓點一邊出現(xiàn)了方塊, 在右側方塊一邊出現(xiàn)了實圓點, 這表示為錯誤的分類。則Shapelets分類準確率可計算為

(10)

其中fz為正確的分類數(shù)量,ftotal為分類數(shù)據(jù)總數(shù)。圖3給出的是二分類問題, 若是n分類, 則會選出n-1個Shapelets及對應的閾值, 現(xiàn)以三分類為例展示多類分類策略。如圖4所示, Ⅰ和Ⅱ是一組Shapelets, Ⅰ和Ⅱ的Shapelets和閾值在圖4上部。Ⅰ按照閾值σ1把數(shù)據(jù)集分成兩部分, 距離小于σ1的被分在A類, 距離大于σ1的被Ⅱ繼續(xù)劃分, 距離小于σ2的劃到B類, 距離大于σ2的劃到C類。若多于三分類問題, 則與三分類相似。

圖4 Shapelets多分類劃分策略Fig.4 Shapelets multi-classification partion strategy

多分類準確率計算方法與二分類類似, 模型分類準確率等于正確分類數(shù)量除以總數(shù)量?；诸惼鞣诸悳蚀_率反映基分類器的優(yōu)劣, 在多變量m個基分類器中, 準確率越高的基分類器在強分類器中所占權重越大。

2.2 D-S證據(jù)理論加權組合策略

在集成學習中, 要得到泛化性能強的集成, 集成學習中的個體分類器應盡可能相互獨立, 在本文中, Shapelets對應一個單變量的子序列, 多變量Shapelets相互之間獨立, 這為集成學習提供了條件。筆者提出使用D-S證據(jù)理論組合基本概率指派BPA(Basic Probability Assignment), 并在計算BPA時對基分類器加權, 最后在Dempster組合中提出解決證據(jù)沖突的策略。

2.2.1 BPA的生成方法

基本概率指派BPA是證據(jù)理論在實際應用中的關鍵問題, BPA直接影響到D-S證據(jù)組合的結果[19-21]。筆者依據(jù)Shapelets決策樹結構, 提出一種加權BPA生成方法, 如圖5所示。

在圖5中, 有3個從訓練集中學習到的Shapelets基分類器, 權重分別是70%、 90%、 50%?，F(xiàn)有一測試數(shù)據(jù), 已知此數(shù)據(jù)類別為A。經(jīng)3個分類器分類后, 其BPA如圖5a所示。經(jīng)D-S合成預測結果為B, 如圖5b所示。分析預測錯誤原因, 由于分類器3對B預測較高, 直接影響了預測的結果, 而分類器3的準確率只有50%。由此筆者給分類器加權, 權重就是分類器的分類準確率。經(jīng)過加權后, BPA如圖5c所示。加權后降低了分類器3對結果的影響, 經(jīng)計算得到分類結果為A。

若分類器權重為g, 加權前bBPA為bBPAb, 則加權后的概率指派bBPAa為

bBPAa=g*bBPAb

(11)

2.2.2 證據(jù)組合沖突解決方法

在D-S證據(jù)理論中, 存在證據(jù)沖突的問題[22], 融合高度沖突的證據(jù)會導致兩個結果： 一個是產生不合理與直覺相悖的結果, 如Zadeh悖論[23]； 二是融合后的結果合理, 但不利于決策。為得到較好的融合結果, 筆者設定兩個規(guī)則：

1) 選取部分分類準確率高的基分類器進行Dempster組合, 如分類準確率低于50%的基分類器舍棄;

2) 基分類器Shapelets在BPA生成時, 若類別較多, 則舍棄部分權重較小的BPA, 用不確定θ代替, 從而提高計算效率, 同時也符合D-S證據(jù)理論的基本思想。

以圖6為例, 若此數(shù)據(jù)集為4變量?；诸惼鞯臏蚀_率分別為80%,90%,70%,40%, 經(jīng)過規(guī)則1)篩選, 舍棄第4個基分類器。前3個基本概率指派函數(shù)為

m1=(A,B,C,D,E)=(0.640,0.180,0.090,0.045,0.045)

m2=(A,B,C,D,E)=(0.810,0.095, 0.048,0.024,0.024)

m3=(A,B,C,D,E)=(0.490,0.255,0.127,0.064,0.064)

設定權重低于0.1的類別被合并成θ, 經(jīng)過規(guī)則2)過濾后,θ取代了D,E

m1=(A,B,C,θ)=(0.640,0.180,0.090,0.090)

m2=(A,B,C,θ)=(0.810,0.095,0.048,0.048)

m3=(A,B,C,θ)=(0.490,0.255,0.127,0.127)

使用Dempster組合規(guī)則式(7)計算得到

m=m1⊕m2⊕m3=(0.97,0.015,0.007 5,0.007 5)

m(A)=0.97, 最后數(shù)據(jù)預測為A, 得到正確結果。多個基分類器的組合具有如下優(yōu)點[12]： 1) 能提高泛化能力; 2) 可降低陷入局部極小點的風險； 3) 擴大假設空間, 得到更好的結果。

2.3 時間復雜度分析

在筆者算法中, 由于使用了基于信息增益的Shapelets生成方法, 使用brute-force算法判斷大量的子序列時間復雜度為O(n2m4), 其中n為訓練集中時序數(shù)據(jù)數(shù)量,m是一條時序數(shù)據(jù)的長度。基于最小距離的提前終止策略和基于信息增益的熵剪枝策略被使用[5]。與生成Shapelets的時間復雜度相比, 計算Shapelets分類準確率及BPA的生成及Dempster組合的時間在O(n)的時間內即可完成, 所以這部分時間可忽略不計。

3 實驗驗證與結果分析

筆者使用JAVA語言在開源Weka框架內實現(xiàn)了算法。遵循文獻[8]中實驗方法, 對數(shù)據(jù)進行100倍重采樣, 對每種算法進行了多次試驗, 試驗結果取多次試驗平均值, 并與其他算法的結果進行比對。

3.1 實驗數(shù)據(jù)集

從UEA-UCR[24]中選取部分多變量時間序列數(shù)據(jù), 如表1所示, 共21個等長序列, 包括序列名稱、 訓練集數(shù)量、 測試集數(shù)量、 每個多變量包含單變量的序列數(shù)量、 序列的長度以及類別數(shù)量。這些數(shù)據(jù)集以ARFF格式存儲, 并在Weka[25]中打開。

表1 實驗數(shù)據(jù)集Tab.1 Experimental dataset

人類活動識別是基于加速度計數(shù)據(jù)或陀螺儀數(shù)據(jù)預測類別的問題, 數(shù)據(jù)是三維或六維坐標。BasicMotion是HAR中的一個, 該數(shù)據(jù)是學生戴著智能手表進行4類運動收集的3D加速度計和3D陀螺儀數(shù)據(jù), 4類活動分別是站立、 行走、 跑步和打羽毛球。 要求參與者記錄運動共5次, 并以10 Hz的頻率采樣數(shù)據(jù)10 s。筆者選取了BasicMotion一個實例進行了展示, 共4類運動, 每類包括三維數(shù)據(jù)X,Y,Z, 例如WalkingX,WalkingY,WalkingZ,加速度計數(shù)據(jù)如圖6所示。陀螺儀數(shù)據(jù)如圖7所示。

圖6 BasicMotion加速度計數(shù)據(jù)序列圖Fig.6 Sequence diagram of BasicMotion accelerometer data

圖7 BasicMotion陀螺儀數(shù)據(jù)序列圖Fig.7 Sequence diagram of BasicMotion cyro data

3.2 比對方法及分類準確率對比

筆者選取了5種不同類型方法進行對比, 包括DTW、 gRSF(generalized Random Shapelet Forest)、 MLCN(Multivariate LSTM-FCNs)、 MUSE(Multivariate Unsupervised Symbols and dErivatives)和HIVE-COTE(Hierarchical Vote Collective of Transformation-based Ensembles)。DTW應用到多變量中演化出兩種方法： DTWD是多變量依賴方法； DTWI是多變量獨立方法。若給定二維多變量序列Q和C, 則DTWD(Q,C)=DTW(QX,QY,CX,CY), DTWI(Q,C)=DTW(QX,CX)+DTW(QY,CY)。gRFS[26]是基于Shapelets廣義隨機森林算法, 該算法生成一組基于Shapelets的決策樹, 其中用于構建樹的實例的選擇和Shapelet的選擇都是隨機的。MLCN[11]是基于LSTM神經(jīng)網(wǎng)絡方法, 該方法把注意力模型引入到多變量分類中。MUSE[13]是一種無監(jiān)督符號表示與演化方法, 它首先使用滑動窗口方法構建多元特征向量, 然后按窗口和維度提取離散特征, 通過特征選擇去除非歧視性特征, 并由機器學習分類器進行分析。HIVE_COTE[14]使用概率投票分層結構集成5個基分類器, 從而顯著改善了集成結果。這5種不同類型的算法代表多變量分類最新的研究成果, 在不同的數(shù)據(jù)集上取得了較高的結果。為了驗證筆者算法, 與這5種算法在21個數(shù)據(jù)集上對比實驗, 實驗結果如表2所示。

從表2中數(shù)據(jù)對比可以看出, 筆者算法在11個數(shù)據(jù)集上取得優(yōu)勢, 其中在BasicMotions和Epilepsy上與其他幾個算法都取得了100%的正確率。HIVE_COTE在FaceDetection和EthanolConcentration上取得領先, 并且整體表現(xiàn)優(yōu)異, 在大部分數(shù)據(jù)集上排在前列。DTWD算法好于DTWI, 并且在Handwriting和PenDigits上取得領先。MLCN整體表現(xiàn)一般, 深度學習方法有待進一步提高。MUSE方法在3個數(shù)據(jù)集上取得領先, 整體表現(xiàn)好于其他算法。

表2 不同方法試驗對比Tab.2 Test comparison of different methods

3.3 關鍵差異對比

對分類問題, 分類準確率是很好的衡量不同算法優(yōu)劣的標準, 但有的算法在一些數(shù)據(jù)集上表現(xiàn)好, 在另一些數(shù)據(jù)集上表現(xiàn)不好。為了進一步對比算法在所有數(shù)據(jù)集上的優(yōu)劣, 采用機器學習領域廣泛使用Friedman測試作為評價算法性能的標準, Friedman測試把所有算法在每個數(shù)據(jù)集上的分類準確率進行標記排名, 如排名“1”,“2”一直到N, 這樣M個算法在N個數(shù)據(jù)集上的排名組成N×M矩陣。然后計算每個算法的平均標記值

(12)

其中hij表示第i個算法在第j個數(shù)據(jù)集的標記值。當M和N足夠大時(M>5,N>10), 使用Friedman統(tǒng)計量

(13)

可以使用具有M-1個自由度的卡方分布近似。這樣不同算法的性能差異可以通過包含平均次序和無明顯差異算法組的關鍵差異圖[27](Critical Difference Diagram)表示。在21個數(shù)據(jù)集上采用100倍重采樣關鍵差異圖, 結果如圖8所示。

圖8中粗橫線表示這幾個算法屬于同一集團, 集團內算法效率差異不大。這些橫線是通過Wilcoxon有符號秩檢驗和Holm校正測試得到。可以看出, 筆者算法、 MUSE和HIVE-COTE屬于第1集團, 第2集團包括HIVE-COTE、 gRSF和MFCN, 第3集團包括gRSF、 MFCN、 DTWD和DTWI。

從表2和圖8中可以得到如下結果： 經(jīng)典的DTW算法在個別數(shù)據(jù)集上表現(xiàn)不錯, 但整體上不如最新的幾個算法； 深度學習算法MFCN并沒有表現(xiàn)出優(yōu)勢, 雖然它在圖像識別等方面表現(xiàn)優(yōu)異； MUSE和HIVE-COTE整體表現(xiàn)優(yōu)秀, 但是, MUSE會帶來巨大的內存開銷, 并且隨著問題規(guī)模的增加而急劇增加。在本次試驗的21個數(shù)據(jù)集上, 其內存使用為26 GByte[4]。而HIVE-COTE在分類準確率上不如MUSE； 筆者算法在準確率上取得一定的優(yōu)勢, 并且由于使用了減少沖突策略, 使集成花銷不大, 整體上資源花銷適中。

圖8 關鍵差異圖Fig.8 Differentiated graph analysis

4 結 語

當前, 多源傳感器用于檢測、 控制等方面, 這些傳感器產生大量多變量時間序列數(shù)據(jù)。充分利用這些數(shù)據(jù)有著巨大價值。筆者提出一種基于Shapelets的多變量D-S證據(jù)加權集成分類方法。對基分類器Shapelets加權, 增加分類準確率高的基分類器權重, 減少分類準確率低的基分類器權重, 得到了更準確的結果。近年來, 深度學習、 集成學習在多變量分類中得到更多的關注, 在以后的工作中, 把深度學習和集成學習應用于多變量分類、 多源數(shù)據(jù)融合中。