楊冠儀,於志勇,郭文忠,黃昉菀

(福州大學數(shù)學與計算機科學學院,福建省網(wǎng)絡計算與智能信息處理重點實驗室,福建 福州 350108)

0 引言

時間序列數(shù)據(jù)隨處可見，并且每時每刻都在生成，如居民用電記錄、溫度變化、心電圖、網(wǎng)絡流量數(shù)據(jù)等.相關(guān)研究中，時間序列分類(time series classification,TSC)問題是其中的熱點問題之一.分類最終結(jié)果受到數(shù)據(jù)質(zhì)量、數(shù)據(jù)相似性和分類器的優(yōu)劣共同影響.研究表明，基于動態(tài)時間彎曲(dynamic time warping,DTW)距離的最近鄰分類器具有相當優(yōu)秀的分類效果[1].DTW能夠有效解決時間序列的不等長和局部形變問題[2].然而該距離基于動態(tài)規(guī)劃思想，具有較高的時間復雜度且對噪聲敏感.為提高DTW的度量效果，產(chǎn)生了許多圍繞DTW的研究工作.FastDTW[3]通過將序列投射到不同分辨率空間并產(chǎn)生多層最佳彎曲路徑的方法來加速DTW距離的計算.LB_Keogh和LB_Improved[4]分別通過限制搜索區(qū)域以加速計算.DDTW[5]計算每條待比較序列的斜率，用以替代原序列的點值，以解決DTW的“奇異”問題.WDTW[6]通過添加權(quán)重對具有相位差的時間序列點進行懲罰以避免由異常點帶來的干擾.此外，有研究者借鑒字符串處理的思想，提出了如LCSS、ERP[7]、TWED[8]等基于編輯距離的方法，同樣有效地提高了時序數(shù)據(jù)分類的精度.

考慮到現(xiàn)實生活中的時序數(shù)據(jù)存在一定的噪聲干擾，本研究認為在進行距離度量之前，有必要對數(shù)據(jù)進行降噪處理.目前常用的降噪方法有離散余弦變換(discrete cosine transform，DCT)、符號聚合近似(SAX)、奇異值分解(SVD)等[9].稀疏表示在信號領(lǐng)域和圖像領(lǐng)域有著廣泛的應用，如人臉識別、圖像重構(gòu)[10]、圖像去噪[11].鑒于稀疏表示在圖像去噪問題上的良好表現(xiàn)，本研究提出一種基于稀疏表示的最近鄰分類模型(SR-1NN)，將基于過完備字典稀疏化并重構(gòu)的序列1NN-EUD、1NN-DTW進行分類.在18個公開的時間序列數(shù)據(jù)集(UCR)[12]上的實驗表明，稀疏表示對于噪聲有一定的容忍性，在一定程度上可以提升分類模型的性能.

1 稀疏表示理論

給定長為n的時間序列y=(y1,y2,…,yn)T∈n×1以及一個構(gòu)建好的字典D∈n×m，稀疏表示認為y可以被近似表示為下式的線性組合：

(1)

其中:D=(d1,d2,…,dk,…,dm)被稱為字典，dk∈n×1稱為字典D的第k個原子，α=(α1,α2,…,αm)T∈m×1為y基于字典D形成的轉(zhuǎn)換域的近似表示.如果D是過完備的，即n

(2)

(3)

其中:ε表示重構(gòu)誤差.上式的對偶形式如下：

(4)

其中:k稱為稀疏度，表示向量α中非零項的最大個數(shù).

此外，由于重構(gòu)誤差或稀疏度事先難以確定，也可以根據(jù)拉格朗日定理同時進行優(yōu)化.式(3)～(4)可等價地轉(zhuǎn)化為無約束的優(yōu)化問題：

(5)

其中:λ用于平衡重構(gòu)誤差和解的稀疏性，一般來說，λ越大解越稀疏.

由于求解l0范數(shù)最小化的稀疏表示問題是一個NP難問題，因此常采用貪心策略或凸松弛策略來得到其近似解.貪心策略在每次迭代時選擇最接近原始解的結(jié)果，最終通過迭代運算找到符合條件的近似解.此類策略的經(jīng)典算法為正交匹配追蹤(orthogonal matching pursuit,OMP)算法而凸松弛策略則采用將l0范數(shù)轉(zhuǎn)換為l1范數(shù)的形式，將非凸優(yōu)化問題轉(zhuǎn)換為凸優(yōu)化問題進行求解[13].此類策略的經(jīng)典算法有基追蹤(basic pursuit,BP)、最小角歸回(least angle regression,LAR)、最小絕對值收斂以及選擇算子 (least absolute shrinkage and selection operator，LASSO)等.其中，LASSO是對LAR算法的改進算法，其對應的目標函數(shù)如下：

(6)

2 基于稀釋表示的分類模型

2.1 稀疏表示對噪聲的容忍性

壓縮感知理論認為，如果信號是稀疏的、可壓縮的，那么利用少部分的觀測值即可重構(gòu)該信號，這些觀測值的數(shù)量遠少于利用如香農(nóng)采樣定律等理論所計算出的數(shù)量.受此啟發(fā)，當時間序列y基于字典可以獲得用于重構(gòu)序列的稀疏表示時，那么稀疏解中所保留的應為原序列y的主要特征，噪聲及冗余信息因為稀疏性的限制會被丟棄，這樣一來經(jīng)過稀疏表示后的重構(gòu)序列參與分類時將比原序列更加容易被區(qū)分.

為了證明這一想法，本研究設計了一組實驗，根據(jù)式(4)求解無噪序列與加噪序列基于過完備字典的稀疏解，并觀察求解過程中算法選中的原子及其對應的系數(shù)值.實驗中采用OMP算法，通過將稀疏度設為20來求解無噪序列與加噪序列的稀疏系數(shù).無噪序列y0是由方程y=30 sin(2t+150°)生成的包含541個采樣點的時間序列，過完備字典D的原子數(shù)設置為2倍的采樣數(shù)，即1 082個.加噪序列y1是通過在y0中添加高斯白噪聲生成的，其信噪比分別為5、10、15、20、25、30、35 dB，信噪比值越小，代表序列所含噪聲越大.圖1展示了原始無噪序列以及信噪比分別為10、20、30 dB的加噪序列.

圖1 原始序列與加噪序列的可視化圖Fig.1 Visualization of the original sequence and the noisy sequence

表1展示了當稀疏度為20時，無噪序列y0和加噪序列y1在同一個字典中選中原子的位置信息，其順序按稀疏系數(shù)從大到小排列.從表1中不難發(fā)現(xiàn)，具有不同信噪比的加噪序列所選中的前9個原子與無噪序列選中的除順序外完全相同.隨著信噪比的增大，加噪序列與無噪序列選中的相同原子的個數(shù)逐漸增加.當信噪比達到35 dB時，二者所提取的原子完全相同.這充分說明,序列稀疏化后，先保留的是主要特征.而當通過稀疏表示保留序列的主要信息后，可通過剔除冗余信息，有效屏蔽噪聲的干擾.

表1 原始序列與加噪序列所選中的原子在字典中的位置

續(xù)表1

2.2 基于稀疏表示的時間序列最近鄰分類模型(SR-1NN)

圖2 基于稀疏表示的1NN分類模型流程框圖Fig.2 Diagram of 1NN classification model based on sparse representation

基于2.1的結(jié)論，本研究提出一個基于稀疏表示的最近鄰分類模型(SR-1NN)，其流程框圖如圖2所示.

首先構(gòu)建過完備字典.字典的構(gòu)造方法分為解析法和學習法[14].解析法利用預先定義好的數(shù)學模型生成字典，如離散余弦變換、離散小波變換等；而學習法則通過訓練，從數(shù)據(jù)中得到字典.為簡便計算，采用解析法生成兩個過完備字典D1和D2進行性能比較.其中，D1為直接利用DCT變換生成的過完備字典，旨在將時間序列從原始空間轉(zhuǎn)換為特征空間，以獲取具有判別力的特征.考慮到時間序列y中可能含有噪聲e，字典D2采用由DCT方陣D和單位陣I構(gòu)成，此時式(1)可轉(zhuǎn)換為以下的形式[13]：

y=y0+e=Dα+e

(7)

將式(7)采用矩陣的符號表示，可得：

(8)

從而可以把式(2)轉(zhuǎn)換為：

(9)

在過完備字典構(gòu)造完后，根據(jù)式(3)～(4)或式(6)求解時間序列數(shù)據(jù)集X={x1,x2,…,xr}基于D1和D2的稀疏解，并結(jié)合其選中的原子重構(gòu)得到降噪后的數(shù)據(jù)集Y={y1,y2,…,yr}.需要特別說明的是，當利用字典D2重構(gòu)原始序列時，只需重構(gòu)D與α而丟棄I與e，就能夠?qū)崿F(xiàn)降噪的效果.最后計算Y中訓練數(shù)據(jù)與測試數(shù)據(jù)之間的歐氏距離與DTW距離，并結(jié)合1NN分類器進行分類.

3 實驗

歐氏距離( euclidian distance,EUD)直接計算序列點對點距離的平方和，DTW采用動態(tài)規(guī)劃思想計算最小距離，這兩種度量距離具有無參的特點，因此本研究采用這兩種方法進行距離計算，并衍生出SR-1NN-EUD與SR-1NN-DTW模型.將其用于公開的UCR時間序列數(shù)據(jù)集中，并與1NN-EUD，1NN-DTW的分類結(jié)果進行比較，部分數(shù)據(jù)集信息詳見表2.

表2 部分UCR時間序列數(shù)據(jù)集信息

續(xù)表2

3.1 數(shù)據(jù)集簡介

UCR時間序列分類數(shù)據(jù)倉庫 (UCR time series classification archive)是由Dau等人共同維護的時間序列公開數(shù)據(jù)倉庫，到2018年為止，該數(shù)據(jù)倉庫已收集128個單變量時間序列數(shù)據(jù)集以及30個多元時間序列數(shù)據(jù)集，囊括了Image、Spectro、Sensor、Simulated、Device、Motion、ECG等15種類型的數(shù)據(jù).所有數(shù)據(jù)都已經(jīng)過z-標準化處理，服從標準正態(tài)分布[15].實驗選取其中六種類型數(shù)據(jù)集，以便比較模型在不同類型數(shù)據(jù)上的差異.數(shù)據(jù)集的信息如表2所示，表中包含了數(shù)據(jù)集的名稱、類型、類別個數(shù)、訓練集樣本個數(shù)、測試集樣本個數(shù)以及每條時序樣本的長度.圖3展示了六種類型不同類別的數(shù)據(jù)曲線.

圖3 六種類型數(shù)據(jù)曲線圖Fig.3 Graph of six types of time series

3.2 實驗設置

實驗比較了時序數(shù)據(jù)基于字典D1,D2利用OMP算法和LASSO算法求解的分類結(jié)果.其中，OMP1是指通過設置稀疏度求解數(shù)據(jù)的稀疏表示(如式(4))，OMP2是指通過設置重構(gòu)誤差求解數(shù)據(jù)的稀疏表示(如式(3))，而LASSO算法則針對式(6)進行求解.需要說明的是，式(3)的目標函數(shù)涉及稀疏度k的調(diào)節(jié)，其范圍在[1,100]之間.式(4)涉及重構(gòu)誤差ε的調(diào)節(jié)，而式(6)涉及平衡參數(shù)λ的調(diào)節(jié).對于這兩個參數(shù)首先在[0.01,0.9]之間以0.01的步長循環(huán)，找到最優(yōu)參數(shù)ε0或λ0，然后在[ε0-0.1,ε0+0.1]的范圍內(nèi)以0.001的步長找最優(yōu)參數(shù).

本研究采用F1分數(shù)用于比較模型的分類性能.F1分數(shù)(F1-score)是基于精確率(precision)和召回率(recall)的調(diào)和平均，如下面式子所示：

(10)

(11)

(12)

其中：c為類別個數(shù)，F(xiàn)1分數(shù)的值越高，說明分類效果越好.

3.3 實驗結(jié)果及分析

3.3.11NN-EUD與SR-1NN-EUD的分類結(jié)果比較

通過對三種稀疏求解方法和兩種字典組合而成的六種模型的分類結(jié)果匯總，表3展示了六種類型數(shù)據(jù)在SR-1NN-EUD上最好分類結(jié)果的數(shù)據(jù)集個數(shù).

表3 六種類型數(shù)據(jù)在SR-1NN-EUD上最好分類結(jié)果的數(shù)據(jù)集個數(shù)

首先，從字典的角度看，基于字典D2的分類模型其分類效果總體上比基于D1的分類模型效果好.這主要是因為歐式距離對噪聲沒有任何的處理能力，而基于DCT方陣D和單位陣I的字典D2的分類模型要求在重構(gòu)原始序列時，只需重構(gòu)D與α的部分，通過丟棄I與e的信息實現(xiàn)降噪的效果.其次，從稀疏求解方法上看，可以得到以下結(jié)論.

1) 采用OMP兩種求解方法的分類模型，其分類效果不相上下.根據(jù)圖3可以發(fā)現(xiàn)，對于Image和Sensor類型的數(shù)據(jù)集而言，其數(shù)據(jù)特征較為明顯，這意味著只需要提取少部分關(guān)鍵原子就足以區(qū)分類別.因此上述兩個類型的數(shù)據(jù)集比較適合采用基于稀疏度約束的OMP1模型.實驗結(jié)果還表明,這些數(shù)據(jù)集的最好結(jié)果對應的稀疏度大部分都在30以下.對于Motion和Spectro類型的數(shù)據(jù)集而言，其類別間的差異要小于其它類型的數(shù)據(jù)集.這說明類別間的差異僅僅依靠少數(shù)原子進行區(qū)分是不夠的.因此，更適合采用基于重構(gòu)誤差約束的OMP2模型，因為不同類別的數(shù)據(jù)基于同樣的重構(gòu)誤差有不同的稀疏度，從而能夠提取出具有區(qū)分能力的特征.

2) LASSO模型的表現(xiàn)整體不如OMP1和OMP2，這主要是因為LASSO模型是在重構(gòu)誤差和稀疏度之間通過調(diào)整參數(shù)λ取得平衡.這也就意味著其更側(cè)重于所有數(shù)據(jù)集的平均表現(xiàn)，而很難在一些特別適合于稀疏度約束(如Image類型)或重構(gòu)誤差約束(如Motion類型)的數(shù)據(jù)集中獲得最好的結(jié)果.

3.3.21NN-DTW與SR-1NN-DTW的分類結(jié)果比較

表4展示了六種類型數(shù)據(jù)在SR-1NN-DTW上最好分類結(jié)果的數(shù)據(jù)集個數(shù).

首先，從字典的角度看，基于字典D1的SR-1NN-DTW相較于1NN-DTW，在6種類型的數(shù)據(jù)上的分類效果均有提升.但是從表4中會發(fā)現(xiàn)，基于字典D2的SR-1NN-DTW在有些數(shù)據(jù)集上(如TwoLeadECG、Lightning-7、CBF,等)反而分類效果不如1NN-DTW.這主要是因為DTW距離對部分局部形變具有一定的處理能力，當采用具有降噪效果的字典D2時，雙重作用下可能會造成一些有用信息的丟失，從而導致分類精度的下降.因此，對于彈性度量距離而言，基于字典D1的稀疏表示更為合適.其次，從稀疏求解方法上看，采用基于稀疏度約束的OMP1模型的分類效果要好于其他兩種算法.這說明DTW距離能夠在一定程度上降低過大的重構(gòu)誤差對于相似度度量的影響，從而使得OMP1模型在利用稀疏度提取關(guān)鍵原子的同時，可以避免由于無法兼顧重構(gòu)誤差而造成的分類性能下降.

表4 六種類型數(shù)據(jù)在SR-1NN-DTW上最好分類結(jié)果的數(shù)據(jù)集個數(shù)

3.3.3稀疏表示與其它分類器結(jié)合的性能比較

為比較稀疏表示對于最近鄰分類器與其它分類器模型的提升效果，本節(jié)實驗選取了最近鄰分類器、支持向量機(support vector machine,SVM)、決策樹(decision tree，DT)、隨機森林(random forest,RF)四個經(jīng)典機器學習分類器模型進行比較.其中1NN分類器的距離度量采用歐氏距離和DTW距離.綜合考慮3.3.1～3.3.2的實驗結(jié)果，對于SR-1NN-EUD模型和SR-1NN-DTW模型的稀疏表示求解方法本研究采用OMP1，SR-1NN-EUD模型的字典采用D2，SR-1NN-DTW模型的字典采用D1.SVM使用線性核函數(shù)，RF模型的樹的數(shù)量設置為20.圖4展示了數(shù)據(jù)集Lightning-2和 ShapeleteSim的數(shù)據(jù)分別采用直接輸入和經(jīng)過稀疏表示重構(gòu)后輸入分類器的分類結(jié)果.

圖4 數(shù)據(jù)集Lightning-2和 ShapeleteSim的分類結(jié)果Fig.4 The classification result of datasets Lightning-2 and ShapeleteSim

從圖中可以看出，稀疏表示對于1NN、SVM、DT、RF模型的分類效果均有提升，但提升幅度有所不同.首先，稀疏表示除了對1NN-EUD明顯有效之外，還對于DT具有很好的提升效果，原因在于決策樹模型根據(jù)數(shù)據(jù)特征，通過計算信息熵進行樹的構(gòu)建并分類，而經(jīng)過稀疏表示后的重構(gòu)序列提取了關(guān)鍵特征，使得決策樹模型選擇特征更加準確，因而SR-DT的分類精度提升很大.其次，對于RF分類器而言，由于其為基于DT的集成分類器，所以經(jīng)過改進后的SR-RF的提升空間小于SR-DT.最后，稀疏表示對SVM的提升效果一般，原因在于SVM通過找尋超平面與支持向量來劃分數(shù)據(jù)，在這一過程中，SVM對于數(shù)據(jù)有一定的抗噪能力和關(guān)鍵特征提取能力，因而稀疏表示雖然對于SVM的分類結(jié)果有提升，但提升不大.綜上所述，數(shù)據(jù)經(jīng)過稀疏表示重構(gòu)后輸入分類器的做法對于不同分類器的性能改善有所不同.針對抗噪能力弱或關(guān)鍵特征敏感的分類器(如1NN-EUD、DT)而言，結(jié)合稀疏表示技術(shù)均能取得較大幅度的分類精度提升.而對于本身具有一定的降噪和特征提取能力的分類器(如1NN-DTW、SVM)而言,結(jié)合稀疏表示技術(shù)雖然能提升一定的分類精度，但是提升空間有限.

4 結(jié)語

針對時序數(shù)據(jù)本身可能存在噪聲及冗余信息的問題，本研究借鑒稀疏表示理論在信號處理領(lǐng)域和圖像處理領(lǐng)域的出色表現(xiàn)，提出一種基于稀疏表示的時間序列最近鄰分類模型，將時序數(shù)據(jù)基于過完備字典進行稀疏分解并重構(gòu)，使得重構(gòu)序列中盡可能少地包含噪聲與冗余信息，最后將重構(gòu)序列進行距離計算并送入最近鄰分類器中進行分類.在自擬信號的仿真實驗與18個公開數(shù)據(jù)集上的實驗表明，SR-1NN模型能夠通過降低原始序列中的噪聲及冗余信息，進而提升傳統(tǒng)1NN分類器的性能.考慮到過完備字典的設計對稀疏表示的影響巨大，在未來的工作中，將進一步對其進行改進，并通過設置驗證集進一步優(yōu)化模型參數(shù).