基于稀疏表示的時間序列最近鄰分類

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

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

0 引言

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

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

1 稀疏表示理論

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

(1)

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

(2)

(3)

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

(4)

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

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

(5)

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

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

(6)

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

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

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

為了證明這一想法，本研究設計了一組實驗，根據式(4)求解無噪序列與加噪序列基于過完備字典的稀疏解，并觀察求解過程中算法選中的原子及其對應的系數值.實驗中采用OMP算法，通過將稀疏度設為20來求解無噪序列與加噪序列的稀疏系數.無噪序列y0是由方程y=30 sin(2t+150°)生成的包含541個采樣點的時間序列，過完備字典D的原子數設置為2倍的采樣數，即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在同一個字典中選中原子的位置信息，其順序按稀疏系數從大到小排列.從表1中不難發現，具有不同信噪比的加噪序列所選中的前9個原子與無噪序列選中的除順序外完全相同.隨著信噪比的增大，加噪序列與無噪序列選中的相同原子的個數逐漸增加.當信噪比達到35 dB時，二者所提取的原子完全相同.這充分說明,序列稀疏化后，先保留的是主要特征.而當通過稀疏表示保留序列的主要信息后，可通過剔除冗余信息，有效屏蔽噪聲的干擾.

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

續表1

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

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

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

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

y=y0+e=Dα+e

(7)

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

(8)

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

(9)

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

3 實驗

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

表2 部分UCR時間序列數據集信息

續表2

3.1 數據集簡介

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

圖3 六種類型數據曲線圖Fig.3 Graph of six types of time series

3.2 實驗設置

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

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

(10)

(11)

(12)

其中：c為類別個數，F1分數的值越高，說明分類效果越好.

3.3 實驗結果及分析

3.3.11NN-EUD與SR-1NN-EUD的分類結果比較

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

表3 六種類型數據在SR-1NN-EUD上最好分類結果的數據集個數

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

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

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

3.3.21NN-DTW與SR-1NN-DTW的分類結果比較

表4展示了六種類型數據在SR-1NN-DTW上最好分類結果的數據集個數.

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

表4 六種類型數據在SR-1NN-DTW上最好分類結果的數據集個數

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

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

圖4 數據集Lightning-2和 ShapeleteSim的分類結果Fig.4 The classification result of datasets Lightning-2 and ShapeleteSim

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

4 結語

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