基于2DSVD的多變量時間序列半監督分類①

單中南，翁小清，馬超紅

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

時間序列是指按時間次序有序排列的一組數據，任何有次序的實值序列都可當作時間序列來處理[1].時間序列數據廣泛地存在于金融、醫學、交通等領域.建立準確的分類器需要大量的有類別標記的樣本數據，然而在現實應用領域，存在大量沒有類別標記的樣本數據，有標記的樣本數據很難獲得，或用人工標記樣本數據成本很高.半監督分類(Semi-Supervised Classification，SSC)使用少量有標記的樣本數據和大量未標記的樣本數據建立分類器.目前，絕大多數時間序列半監督分類的研究工作都集中在單變量時間序列，對多變量時間序列(Multivariate Time Series，MTS)的半監督分類研究還比較少.在對MTS 進行半監督分類時，主要遇到兩方面的困難[2]：第一，MTS 中含有多個變量，且變量之間存在復雜的相關系；第二，不同MTS 樣本它們的長度不一定相等，這些困難使得標準的分類器很難直接使用.本文針對MTS 特性，采用二維奇異值分解(Two-Dimensional Singular Value Decomposition，2DSVD) 從MTS 樣本中提取特征矩陣，并與其他MTS 半監督分類方法進行性能對比，討論該方法在MTS 半監督分類的優勢.本文第1 節介紹背景和相關工作；第2 節提出了基于2DSVD 的MTS半監督分類算法；第3 節通過實驗將本文提出的方法與其它半監督分類方法進行比較，并采用威爾克森符號秩檢驗(Wilcoxon signed ranks test)對實驗結果進行對比，驗證算法的有效性；第4 節給出了本文結論.

1 背景和相關工作

1.1 基本概念

定義1.時間序列.時間序列是一段時間內的一系列觀測值，用xi(t)[i=1，2，…，n；t=1，2，…，m]表示，其中m是觀測值的個數，n是變量的個數[2].當n=1 時，稱為單變量時間序列，當n≥2 時，稱為多變量時間序列，通常用m×n矩陣存儲MTS.

定義2.P集合.P為訓練數據的一個集合，包括所有正類標記的樣本[3].在訓練開始時，P只包含少量的正類樣本，或許只包含一個正類樣本.隨著學習的繼續，先前U中一些沒有標記的樣本，被標記為正類樣本，并移動到了P集合，P集合包含樣本的數量也隨之增加.最終，集合P既包含原來有標記的正類樣本，也包括使用分類器從U 中選擇的樣本.

定義3.U集合.U是未標記樣本的集合[3].U中的樣本可以來自正類或者負類；通常情況下，U中的絕大多數樣本來自負類.

1.2 二維奇異值分解

Ding 等[4]對標準奇異值分解(即一維奇異值分解，1DSVD)進行了擴展，提出了基于行-行協方差矩陣以及列-列協方差矩陣的二維奇異值分解方法，2DSVD 是基于二維矩陣而不是基于一維向量[2].2DSVD 使用MTS 樣本構造行-行以及列-列的協方差矩陣，然后計算行-行及列-列協方差矩陣的特征向量用于MTS 樣本特征矩陣的提取.使用2DSVD 提取出的MTS 樣本的特征矩陣，它們的行數以及列數不僅比原始數據低，而且還清晰地考慮了原始數據的二維特性.

其中，||·||為L2 范數.

1.3 相關工作

時間序列的半監督分類方法可大致分為3 類[6，7]：基于實例、基于聚類以及基于模型的半監督分類方法.

Wei 等[8]針對正類中只有少量有標記的樣本，使用歐氏距離建立基于最小最近鄰距離的分類器及停止準則.Ratanamahatana[9]等使用DTW (Dynamic Time Warping)距離來改進樣本的選取并提出了新的停止準則，該準則基于未標記樣本集中候選樣本與正類樣本的歷史距離；Chen[3]等在SSC 算法中，使用一種基于DTW 和ED 相結合的特殊距離DTW-D，顯著地提高了分類的性能.Begum 等[10，11]提出了一種基于最小描述長度(Minimum Description Length，MDL)的停止準則，該準則利用數據的內在性質去發現停止點；然而，時間序列在時間軸可能會存在扭曲(distortion)現象，出現不匹配點，Vinh 等[12，13]針對此問題進行了改進，并增加一個后處理步驟，使分類器更加精確.Vinh 等[14]還提出了一種基于約束的自訓練算法，與正類集合最近的實例t，必須滿足約束DL(t|H)＜DL(t)，才能添加到正類集合.另外，Vinh 等還定義了安全距離(safe distance)，當實例與正類集合之間的距離小于或等于安全距離，則將該實例放入正類集合中.

目前絕大多數研究工作集中在單變量時間序列半監督分類算法性能的提高，以及停止準則的改進方面，對MTS 半監督分類的研究很少.在對MTS 進行半監督分類時，主要存在變量之間的復雜相關關系以及樣本長度不一致等因素，使得標準分類器很難直接使用.Li 等[15，16]提出了兩種基于標準SVD 的特征提取方法(以下簡稱Li’s first、Li’s second 方法)用于MTS 分類，Li’s first 方法是將第1 個奇異向量u1與經過標準化后由奇異值組成的向量σnormalized相連，作為MTS 樣本的特征表示.Li’s second 方法將加權以后的第1 奇異向量w1u1與加權后的第2 奇異向量w2u2相連，作為MTS 樣本的特征表示.這兩種方法本質上屬于一維奇異值分解，但是MTS 包含變量維和時間維兩個維度，本文提出基于2DSVD 的半監督分類方法，從行和列兩個方向對MTS 樣本進行降維，清晰地考慮了MTS 樣本的二維特性.

2 基于2DSVD 的MTS 半監督分類算法

2.1 訓練分類器

本文提出的MTS 半監督分類算法主要包括4 個步驟：第一步，使用未標記數據集U來計算變換矩陣Ur以及Vs，獲取每個訓練樣本的特征矩陣；第二步，隨機選取若干個正類樣本的特征矩陣作為初始標記數據P；第三步，計算集合U中每個樣本到集合P的歐氏距離，將集合U中與集合P最近的樣本，從集合U中刪除，添加至集合P；第四步，重復第三步，直到滿足停止標準為止.

基于2DSVD 的MTS 半監督分類算法如算法1 所示.在步驟7 中，本文采用Wei 等[8]提出的停止標準，即在迭代過程中，當正類樣本的最小最近鄰距離在趨于穩定后的第一次顯著下降時，即停止.TWOSVDSSC分為兩個階段，步驟1-步驟5 為降維階段：設未標記數據集U中有M個MTS 樣本，算法的行-行協方差矩陣F為m×m矩陣，列-列協方差矩陣G為n×n矩陣[5]，由于對n×n矩陣進行奇異值分解的時間復雜度為O(n3)[2]，所以算法中步驟1-步驟4 的時間復雜度為O(m3+n3)；步驟5 是計算未標記數據集U中每一個MTS 樣本的特征矩陣，時間復雜度為O(M*r*s)，由于在MTS 樣本中，變量個數n以及參數r和s往往都遠小于樣本長度m，因此步驟1-步驟5 的時間復雜度主要取決于樣本長度；步驟6-步驟8 為訓練分類器階段，時間復雜度為O(M2).所以算法的復雜度為O((m3+n3)+(M*r*s)+M2).

分類器訓練好之后，在使用分類器對待測樣本進行分類時，如果待測樣本與任何一個標記為正類樣本之間的距離小于閾值r，則該樣本分類為正類，否則為負類[8]，閾值r為正類樣本與其最近鄰之間距離的平均值.

算法1.基于2DSVD 的MTS 半監督分類算法輸入：P 是初始訓練集，包含少量已標記正類樣本；U 是未標記數據集；nSeeds 是初始標記為正類樣本的個數.輸出：訓練好的分類器.1.計算U 中行-行協方差矩陣F；2.使用SVD 計算F 的特征向量，由F 的前r 個主要特征向量組成的變換矩陣Ur；3.計算U 中列-列協方差矩陣G；4.使用SVD 計算G 的特征向量，由G 的前s 個主要特征向量組成的變換矩陣Vs；5.計算U 中每個MTS 樣本的特征矩陣Mi；6.隨機選取nSeeds 個正類樣本放入集合P；7.計算集合U 中每個樣本到集合P 的歐氏距離，將集合U 中與集合P 最近的樣本，從集合U 中刪除，添加至集合P；8.重復步驟7，直到滿足停止標準為止.

2.2 評估分類器

算法1 僅包含來自U中的正類樣本，屬于一類分類器.本文采用測試集對分類器的性能進行測試，測試集中包含一些正類樣本和其他類樣本.采用經典的精確度(Precision)和召回率(Recall)來衡量分類器的性能.在本文中，精確度的值等于召回率的值，即假的負類(False negatives) 數量與假的正類(False positives)數量相同.精確度的定義如下所示[3]，其中K是指測試集中的正類樣本的個數，Npositive為在前K個最接近P集合的樣本中，正類樣本的個數.

3 實驗

3.1 數據集描述

本文實驗數采用的Lp1、Lp2、Lp4、Lp5 數據集[17]包含機器人在故障檢測后的力和扭矩測量值.每個故障的特征是在故障檢測后每隔一段時間收集的15 個力/扭矩樣本，Lp1、Lp2、Lp4、Lp5 數據集中每個樣本包含6 個變量；BCI 數據集[18，19]中MTS 樣本分為兩種類型：一種是被測試者用左手手指按計算機鍵盤時的腦電圖(EEG)情況，有208 個樣本；另一種是被測試者用右手手指按計算機鍵盤時的腦電圖情況，也有208 個樣本.數據集中每個樣本包含28 個變量；Japanese Vowels 數據集[20]記錄9 個男性在發日語的元音/ae/，這9 個男性對應的樣本個數分別為：61，65，118，74，59，54，70，80 以及59，數據集中每個樣本包含12 個變量；Wafer 數據集[21]記錄真空室傳感器監控半導體微電子的制造過程，每一個硅晶片的生產過程可以用含有6 個變量的MTS 樣本來描述，并被分為正?；虍惓深悾瑪祿邪?27 個MTS 樣本并被分為2 類：其中正常樣本有200 個，異常樣本有127；AUstralian Sign LANguage(以下簡稱AUSLAN)數據集[20]由隨機選取25 種手勢的MTS 樣本(總共675 個MTS 樣本)組成，每個樣本包含22 個變量；Character Trajectories 數據集[22]中所有樣本來自同一位作者，通過書寫單個字符來記錄筆尖(pen tip)軌跡，記錄時只考慮帶有單一落筆段的字符，每個樣本包含x 和y 坐標以及筆尖力度這3 個變量；Gas sensors 數據集[23，24]包含由MOX 以及溫度和濕度這三種傳感器組成的氣體傳感器，記錄來自3 種不同氣體所產生的觀測值，數據集中每個樣本包含10 個變量.表1列出了10 個MTS 數據集的主要特征.2DSVD 要求數據集中所有MTS 樣本具有相同長度.對于具有不同長度樣本的MTS 數據集，本文采用Rodriguez 等[25]提出的方法，將所有MTS 樣本的長度都延長到該數據集中最長MTS 樣本的長度.延長方法如下：如將長度為100 的MTS 樣本延長至120，只需將樣本中每5 個值中的一個值復制即可.該方法使得原樣本中的所有值都保留在延長后的樣本中，不會損失任何數據信息.

表1 數據集描述

3.2 性能比較

將本文提出的基于2DSVD 的MTS 特征提取方法，與基于擴展Frobenius 范數的距離DEros[26]、中心序列[27]、以及基于一維SVD 的Li’s first，Li’s second 方法[15，16]分類性能進行比較.在實驗中，將數據集中類別標記為1(class label=1)的樣本選為正類樣本數據，其它類樣本皆為負類樣本數據.在算法2.1 中，初始正類樣本的個數nSeeds分別取1、3、5 個，實驗重復100次，表2、3、4 給出了各種方法100 次實驗的平均Precision.

表2、表3、表4給出了在10 個數據集上使用不同方法進行半監督分類的Precision.表中列2 和列3 給出了在數據集上使用基于擴展Frobenius 范數的距離DEros[26]以及中心序列[27]的方法進行分類的Precision；表中列4 和列5 給出了在數據集上使用Li’s first 以及Li’s fecond 方法進行分類的Precision；列6 給出了使用2DSVD 進行分類時最高的Precision以及相應參數r和s的值，其中，r和s分別表示使用2DSVD 方法得到對應特征矩陣的行及列的個數.

從表2可以看出，當初始正類樣本的個數nSeeds為1 時，2DSVD 在10 個MTS 數據集上分類的平均Precision 為 0.76，DEros的平均值為0.39，中心序列的平均值為0.63，Li’s First 以及Li’s Second 的平均值分別為 0.53 和0.52；從表5中可以看到，2DSVD 與其它4 種方法的Wilcoxon 符號秩檢驗的概率p值都小于0.05，說明2DSVD 的分類性能顯著地好于其它四種方法.當nSeeds 為3 或5 時，也可以得到相同的結論.從表2、表3、表4中還可以看出，各種方法的平均Precision隨著nSeeds增大而增大，說明增加初始正類樣本個數，能夠提高算法的分類性能.

表2 nSeeds=1 時各種方法的Precision

表3 nSeeds=3 時各種方法的Precision

表4 nSeeds=5 時各種方法的Precision

3.3 參數對半監督分類性能的影響

本文提出的分類算法有兩個參數：一個是行-行協方差矩陣的主要特征向量個數r，另一個是列-列協方差矩陣的主要特征向量個數s.圖1、圖2分別給出了在AUSLAN、Vowel 數據集上，將參數r固定為1，Precision隨參數s的變化情況.從圖1和圖2可以看出，當s=1 時，Precision最?。浑S著s 逐漸增加，算法的Precision快速上升，然后趨于平穩；所以，在算法的執行過程中，可以選取較大的s值來提高分類的Precision.

表5 Wilcoxon 符號秩檢驗

圖1 AUSLAN 數據集Precision 隨列-列協方差矩陣的主要特征向量個數s 的變化

圖2 Vowel 數據集Precision 隨列-列協方差矩陣的主要特征向量個數s 的變化

圖3給出了在AUSLAN 數據集上，將參數s固定為21，Precision隨參數r的變化情況.圖4給出了在Vowel 數據集上，將參數s固定為12，Precision隨參數r的變化情況.從圖3和圖4可以看出，當參數r增加時，分類的Precision趨于平穩；所以，在算法執行過程中，可以選取適當的r值即可.

圖3 AUSLAN 數據集Precision 隨行-行協方差矩陣的主要特征向量個數r 的變化

圖4 Vowel 數據集Precision 隨行-行協方差矩陣的主要特征向量個數r 的變化

在本文實驗中，參數r和s的選取方法如下[2]：首先選擇一個較大的s值，使得這s個列-列協方差矩陣的主要特征向量能夠描述列-列之間總變異(total column-column variations)的98%或99%，其次，讓r值從1 增加到m，其中m為觀測值個數，計算相對于每一個r值的所有訓練樣本的重構誤差平方和，最后根據重構誤差平方和的相對變化情況選取適當的參數r.

4 結論與展望

本文提出了一種基于2DSVD 的MTS 半監督分類方法，在10 個MTS 數據集上對該方法進行驗證，實驗結果表明，本文提出的算法顯著地好于基于一維SVD的Li’s First、Li’s Second 方法[15，16]，基于擴展Frobenius范數的距離DEros[26]，以及中心序列[27].雖然本文建立的是一類分類器，因此也可以很容易地修改本文提出的算法以適應多類問題.本文提出的算法有兩個參數r和s，如何自動地選擇最優的r和s值以及選取更優的分類器和停止標準值得今后進一步研究.