基于LDA符號表示的時間序列分類算法

武天鴻 翁小清 單中南

(河北經貿大學信息技術學院 河北 石家莊 050061)

0 引 言

時間序列通常是指按時間順序排列而成的一組數據，任何有序的實值型數據都可以當作時間序列處理[1]。時間序列分類根據訓練集中對象所構建的分類模型，判別被分類對象所屬的類別[2]。時間序列分類已經被廣泛應用于模式識別、醫療診斷、工業控制和異常檢測等領域，時間序列數據維度高，分類難度大。

時間序列符號表示是指將連續的實值型數據表示成低維離散的符號序列數據，是一種重要的時間序列分析方法。時間序列符號表示方法不僅簡單高效，對噪聲具有魯棒性，還允許學者利用來自文本處理、信息檢索和生物信息學等領域的算法，對于提高時間序列分類算法的性能和效率具有重要意義。SAX(Symbolic Aggregate approXimation)[3-4]是一種經典的時間序列符號表示方法，該方法能較好地體現時間序列的整體趨勢且簡單高效。但是，SAX方法僅用分段的均值并不能很好地描述時間序列的局部特征，無法區分具有相同均值不同趨勢的時間序列，完全不同的時間序列可能會得到相似的符號表示；SAX的MINDIST距離度量的緊性較差，容易產生誤報，且該方法只適于服從高斯分布的時序數據。目前，基于符號表示的時間序列分類研究主要集中在SAX性能的改進上。在分類問題中，帶有先驗的分類方法能使分類性能大大提高，然而絕大多數基于符號表示的分類方法沒有考慮類別的先驗知識。

本文提出一種基于線性判別分析(Linear Discriminant Analysis，LDA)[5]符號表示的時間序列分類方法LDA_SC(LDA Symbolic Classification)，該方法清晰地考慮了樣本類別信息對符號化分類的影響，且具有自適應的符號區間分段點。LDA_SC使用線性判別分析將原始高維的時間序列數據映射到低維空間，投影后樣本在低維子空間具有更近的類內距離和更遠類間距離；利用信息增益在降維后的數據上尋找字符投影區間的最佳劃分點，減小信息損失；定義一種新的距離度量方法，根據最近鄰法對低維空間符號表示的時間序列進行分類。

1 相關研究

1.1 相關概念

本節簡要介紹正交局部保持映射及信息增益的基本理論，并對基于LDA的時間序列符號表示方法進行詳細介紹。

定義1時間序列。狹義上的時間序列是指一系列有時間順序的觀測值，m個觀測值，n個變量的時間序列可表示為xi(t)[i=1,2,…,n;t=1,2,…,m]，當n=1時，稱為單變量時間序列；當n≥2時，稱為多變量時間序列[6]。本文所提方法只針對單變量時間序列。

1.2 線性判別分析

時間序列維數由于隨著時間不斷增加，容易出現維災現象，為了研究方便和去除噪聲，需要對時間序列數據進行降維處理。線性判別分析LDA和主成分分析PCA(Principal Component Analysis，PCA)[7]是常用的兩種降維方法。PCA是一種表現很好的無監督數據降維方法，各主成分之間正交，能夠消除原始數據成分間的互相影響，但是如果存在方差較大的幾個方向是非正交的，會造成數據不再線性可分甚至不可分。LDA是一種有監督的數據降維方法，使用類別的先驗知識，將高維的數據樣本投影到具有最佳可分性的子空間，使得樣本在低維子空間有最大的類間距離和最小的類內距離。

假設含m個樣本的數據集D={(x1,y1),(x2,y2),…,(xm,ym)},其中任意樣本xi為n維向量，yi為樣本xi對應的類別標簽，yi∈{C1,C2,…,Ck}。首先計算所有類的樣本均值u和第i類的樣本均值ui，分別表示為:

(1)

(2)

式中：ni表示第i類所包含的樣本個數，xij表示第i類的第j個樣本。

根據u和ui計算類間散度矩陣(between-class Scatter matrix)和類內散度矩陣(within-class Scatter matrix)，分別表示為：

(3)

(4)

1.3 信息增益

信息增益(Information gain)[8]表示得知特征X的信息而使得類Y的信息的不確定性減少的程度。對于分類系統而言，假設Y={(s1,y1),(s2,y2),…,(sN,yN)}是由N個“值與類標簽”對組成的列表，多分類的熵定義為：

(5)

式中：pyi是標簽yi在Y中出現的頻率。分割點sp的熵由下式給出：

(6)

式中：YL={(si,yi|si≤sp,(si,yi)∈Y}，YR={(si,yi)|si>sp,(si,yi)∈Y}。分割點sp的信息增益為：

inf_gain=Ent(Y)-Ent(Y,sp)

(7)

本文所提的時間序列符號符號化方法，使用信息增益尋找值的最佳劃分點，是一種有監督的離散化方法，能夠使每個分區中的大多數值對應于同一個類，可以用同一個字母表示。這種有監督的符號表示方法能夠提高訓練模型的分類能力。

1.4 相關研究評述

基于符號表示的時間序列分類方法，根據時間序列數據轉化成符號序列的不同方式大致可以劃分為4類，即基于趨勢、基于聚類或進化計算、基于文本以及基于頻率域的方法。針對SAX存在缺陷，學者們提出的改進方法大致可歸結為從局部趨勢特征描述、距離度量、符號區間劃分和序列分段四個方面，不同程度地提高算法分類性能，但是也不可避免地帶來一些新的問題，如參數選擇困難、計算復雜度高和維數約簡性能較差等。

Lkhagva等[9]提出使用每個分段的最小值、最大值和均值表示的ESAX(Extended SAX)，字符串長度是SAX的三倍。Malinowski等[10]提出將每個分段(segment)的線性回歸量化為字母表中一個符號的1d-SAX，該方法在分段有噪聲時擬合誤差較大。Yin等[11]提出根據全局關鍵點將長時間序列分成若干個分段，依據各分段的上升、下降和水平趨勢對時間序列符號化，避免了將時間序列等長劃分造成的重要信息丟失。首先將時間序列轉換成比值序列或導數序列，再根據轉換后序列分段的趨勢特征進行符號表示的方法[12-14]，在一定程度上保留原始時間序列的整體趨勢變化信息，但是對于變化特征不明顯的時間序列具有一定的局限。對于如何更好地劃分符號區間以減少離散化過程中的信息丟失，Bai等[15]提出rSAX通過小距離調整分段點使得彼此接近的點以更高的概率映射到相同的符號。Fuad等[16]對距離查找表進行改進提出UMD，該方法以落在每個分段區間內均值的最大值和最小值作為該字母表示的邊界，以邊界距離作為字母間的距離構建查找表，在下界距離緊性和分類性能方面都好于SAX。Sharabiani等[17]先使用SAX將時間序列轉化為符號序列，在符號序列上使用Bayesian規則和概率鏈規則建立模型BCM，然后用BCM對待測符號序列進行分類。然而，BCM的分類準確率與原始時間序列使用歐式距離的1NN分類的準確率差別不顯著。

符號與數值混合的表示方法[18-20]，雖然能夠顯著提高分類準確率，但是不能應用來自信息檢索、文本處理和生物信息學等領域算法，應用具有局限性；基于聚類和進化計算的符號表示方法，不管數據集是否具有Gaussian分布性質都具有較好的適應性，擴展了SAX方法的適用范圍，但這類方法對于合適的聚類半徑、種群數量和進化代數等參數的選擇是非常困難的，且所需存儲空間大、計算復雜度高。

將時間序列進行符號表示后可借鑒自然語言處理中的方法進行分類，如Boer等[21]提出使用Edit距離對符號序列進行分類，Senin等[22]提出的SAX-VSM模型，Lin等[23]提出基于BOP(Bag-Of-Patterns)模型及宋偉等[24]提出其改進算法。BOP模型和SAX-VSM模型考慮了時間序列數據的整體特性和局部特性，對偏移量和噪聲的影響不敏感，分類速度快且準確度高，但這類方法通常在訓練階段的時間復雜度比較高，需要的存儲空間較大。

Schafer等[8]提出一種基于離散傅里葉變換(DFT)的符號表示方法SFA(Symbolic Fourier Approximation)，并以SFA為基礎提出不同的改進算法[25-27]，SFA首先對時間序列進行離散傅里葉變換，取出前n個傅里葉系數，然后采用信息增益尋找系數的符號區間劃分點，并對每一維系數使用等寬離散將其表示成符號。使用信息增益尋找符號區間劃分點可減少離散過程中的信息損失，在一定程度上提高分類準確性。基于頻率域符號表示的分類方法，能夠有效解決分類任務中的維災問題，而且能夠在一定程度上反映時間序列的整體變化趨勢，但是目前這方面的相關研究較少，主要是以SFA為基礎的改進。

大多數已有方法對原始時間序列進行符號表示時，沒有考慮類別的先驗知識對分類性能的影響，是無監督符號化方法，然而在分類問題中，帶有較為準確的先驗的分類方法能使分類性能大大提高。

2 基于LDA符號表示的分類算法

2.1 符號近似表示

本文提出基于線性判別分析的符號近似表示方法SLA(Symbolic LDA approximation)，該方法使用LDA將長度為n的時間序列降到w維(w<

圖1 SLA符號近似表示過程

2.2 距離度量

(8)

2.3 算法設計

本文提出的基于LDA符號表示的時間序列分類算法主要包括三個步驟：

(1) 使用LDA將訓練集從高維空間映射到低維空間。

(2) 對降維后訓練集的每一維，計算信息增益最大分割點，使得兩個分割點之間的數據盡可能屬于同一類別，將降維后訓練樣本表示成符號序列。

上述歐盟第八和第九研發框架計劃預算經費比較凸顯了歐盟未來7年（2021—2027）科技創新政策的著力點，即歐盟將重點資助應對全球挑戰和以市場為導向的創新活動，這兩塊的資助經費都比“地平線2020”上浮30%～40%。尤其需要指出的是，歐盟意識到計劃下大量的研發成果未能及時發揮推動經濟、社會發展的價值，降低了歐盟科技計劃和政策的社會影響力，所以“地平線歐洲”大大強化了對以市場為導向的高風險、顛覆性創新活動的經費支持，專設了歐洲創新理事會，形成了支持市場化創新的兩個專項經費渠道，劃撥專款支持創新生態系統建設，從經費和制度構建上保障創新成果從實驗室走向市場，將知識資本轉化為社會經濟價值。

(3) 使用訓練集的分割點，將低維空間的測試樣本表示成符號序列，使用1NN分類器對測試樣本的符號序列進行分類。基于LDA符號表示分類算法如下：

LDA_SC(TRAIN,TEST,w,a,PCAratio)

輸入：訓練集TRAIN，測試集TEST，維數w，字母表大小a，PCA率PCAratio

輸出：分類準確率accuracy

Step1將TRAIN投影到PCA子空間，可調整PCAratio對原始數據降噪和消除矩陣奇異性，PCA的轉換矩陣用WPCA表示；

Step2根據式(1)、式(2)計算訓練集的樣本均值u和所有類的樣本均值ui;

Step3計算類間散度矩陣Sb及類內散度矩陣Sw；

Step6取出低維空間中訓練集的某一維數據，根據式(5)-式(7)尋找信息增益最大的分段點sp1；

Step7分別在sp1前后兩段數據中找出信息增益最大的分段點sp2和sp3，重復執行，直至找出(a-1)個分段點，將該維數據劃分成a個區間，分別用a個不同字母表示；

Step8將每個樣本在該維的數據，根據其所在區間，轉換為相應的字母；

Step9重復執行Step 6-Step 8，直到訓練集每一維數據都映射成字母，每個樣本也就表示成了符號序列；

Step10使用Step 5中的變換矩陣W，將TEST集樣本映射到低維空間，使用TRAIN集的分段點將低維空間的測試樣本表示成符號序列；

Step11使用最近鄰分類器，根據距離函數DIST對表示成符號序列的測試樣本進行分類。

3 實驗結果分析

本節對LDA_SC在20個來自UCR[28]檔案庫的時間序列數據集上的分類性能進行評估，評估標準是分類準確率。

3.1 數據集描述

表1列出了20個數據集的主要特征，包括數據集名稱、類別個數、訓練樣本總數、測試樣本總數和樣本長度。這些時間序列數據集主要來自生物、醫學、工業控制和圖像識別等領域。

表1 數據集描述

3.2 性能比較

將本文提出的算法與EU(對原始數據使用歐式距離分類)、SAX、ESAX和BCM四種算法的分類性能進行比較。為了實驗對照，本文將字母個數限制在2～10之間。表2和表3分別給出了使用五種方法在測試集上的分類準確率及相應參數，其中w是符號序列的長度(即低維空間的維數)，a是字母表的大小，PCA ratio是LDA_SC算法中的PCA比率，五種方法的最高準確率已在表2和表3中加粗顯示。

表2 EU、SAX和ESAX的分類準確率

表3 BCM和LDA_SC的分類準確率

續表3

對表2和表3中實驗結果進行分析，LDA_SC在20個數據集上的平均分類準確率高于另外四種方法的平均分類準確率，且LDA_SC僅需要較少的維數就能夠達到很好的分類效果；LDA_SC在15個數據集上的分類準確率高于BCM的分類準確率；LDA_SC在17個數據集上使用比SAX和ESAX更小的字母表，其中14個數據集分類準確率高于SAX，12個數據集分類準確率高于ESAX，說明LDA_SC只需要較小的字母表就能取得不錯的分類效果。

從表4可以看出，LDA_SC與EU、SAX、ESAX的Wilcoxon符號秩檢驗的概率p值都小于0.05，說明LDA_SC的分類性能顯著地好于這三種分類方法，LDA_SC與BCM的Wilcoxon符號秩檢驗的概率p值為0.052 2>0.05，LDA_SC與BCM差別不顯著，但是從兩種方法在數據集上的分類準確率來看，LDA_SC的分類效果好于BCM。

表4 Wilcoxon符號秩檢驗

3.3 參數對分類性能的影響

本文提出的LDA_SC算法有3個參數，即嵌入維數w、字母表大小a和PCAratio。

圖2給出在Synthetic_control數據集上，使用大小為8的字母表，當PCAratio=0.99時，準確率隨嵌入維數w的變化情況。圖3 給出了在Faceall數據集上，當字母表大小為8、PCAratio=0.99時，準確率隨嵌入維數w的變化情況。從圖2和圖3中可以看出，當嵌入維數w比較小時，分類準確率比較低，隨著嵌入維數w逐步增加，準確率快速上升并趨于穩定。LDA_SC僅需要較少的嵌入維數就可以獲得很好的分類效果，這一良好的維數約簡性能對于解決時間序列分類中的維災問題具有重要意義，且在計算資源和存儲資源較少的設備中具有適用性。

圖2 準確率隨嵌入維數w的變化

圖3 準確率隨嵌入維數w的變化(Faceall數據集)

圖4給出了在Synthetic_control數據集上，當PCAratio=0.99，w=10時，準確率隨字母表中字母個數的變化情況。圖5給出在Adiac數據集上，當w=88、PCAratio=0.97時，準確率隨字母表中字母個數的變化情況。綜合圖4和圖5可以看出，字母個數小于3個時，準確率相對較低，字母個數在4個到8個之間就能取得較好的分類效果，隨著字母個數繼續增加，準確率趨于平穩。字母表的大小對LDA_SC分類性能具有較大影響，LDA_SC不需要很大的字母表就能取得較好的分類效果，存儲距離查找表所占資源較少，且分類過程中的計算復雜性大大降低。

圖4 準確率隨字母個數a的變化

圖5 準確率隨字母個數a的變化(在Adiac數據集)

圖6給出了在SwedishLeaf數據集上，當a=10，w=94時，準確率隨PCAratio的變化情況。圖7展示了在Faceall數據集上，當a=8，w=67時，準確率隨PCAratio的變化情況。分析圖6和圖7可知，準確率在一定區域內波動，但是準確率隨PCAratio增大整體呈緩慢上升趨勢，PCAratio對LDA_SC的分類性能影響較小，如果PCAratio太小會造成過多的信息損失，一般在95%～100%之間取值能夠使LDA_SC具有較好的分類效果。

圖6 準確率隨PCA ratio變化(在SwedishLeaf數據集)

圖7 準確率隨PCA ratio變化(在Fcaeall數據集)

4 結 語

本文提出一種基于LDA符號表示的時間序列分類方法。該方法在降維去噪聲的同時最大化樣本的類間區分度，使用信息增益尋找分段點能夠盡可能地減少離散化過程中的信息丟失，在一定程度上提高分類準確性。在20個數據集上的實驗結果表明，本文提出的LDA_SC分類性能顯著好于已有的基于符號表示的時間序列分類方法，有監督的符號表示方法能有效提高分類性能。大部分現有方法主要針對單個時間序列樣本的局部形態特征或整體趨勢對其進行符號表示，沒有考慮數據集樣本間的近鄰關系對符號化分類的影響。如何將LDA_SC算法與向量空間模型結合以及如何將LDA_SC應用于多變量時間序列的分類，仍需進一步研究。