單中南，翁小清，馬超紅

(河北經(jīng)貿(mào)大學 信息技術(shù)學院，石家莊 050061)

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

1 背景和相關(guān)工作

1.1 基本概念

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

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

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

1.2 二維奇異值分解

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

其中，||·||為L2 范數(shù).

1.3 相關(guān)工作

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

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

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

2 基于2DSVD 的MTS 半監(jiān)督分類算法

2.1 訓練分類器

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

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

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

算法1.基于2DSVD 的MTS 半監(jiān)督分類算法輸入：P 是初始訓練集，包含少量已標記正類樣本；U 是未標記數(shù)據(jù)集；nSeeds 是初始標記為正類樣本的個數(shù).輸出：訓練好的分類器.1.計算U 中行-行協(xié)方差矩陣F；2.使用SVD 計算F 的特征向量，由F 的前r 個主要特征向量組成的變換矩陣Ur；3.計算U 中列-列協(xié)方差矩陣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中的正類樣本，屬于一類分類器.本文采用測試集對分類器的性能進行測試，測試集中包含一些正類樣本和其他類樣本.采用經(jīng)典的精確度(Precision)和召回率(Recall)來衡量分類器的性能.在本文中，精確度的值等于召回率的值，即假的負類(False negatives) 數(shù)量與假的正類(False positives)數(shù)量相同.精確度的定義如下所示[3]，其中K是指測試集中的正類樣本的個數(shù)，Npositive為在前K個最接近P集合的樣本中，正類樣本的個數(shù).

3 實驗

3.1 數(shù)據(jù)集描述

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

表1 數(shù)據(jù)集描述

3.2 性能比較

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

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

從表2可以看出，當初始正類樣本的個數(shù)nSeeds為1 時，2DSVD 在10 個MTS 數(shù)據(jù)集上分類的平均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 時，也可以得到相同的結(jié)論.從表2、表3、表4中還可以看出，各種方法的平均Precision隨著nSeeds增大而增大，說明增加初始正類樣本個數(shù)，能夠提高算法的分類性能.

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

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

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

3.3 參數(shù)對半監(jiān)督分類性能的影響

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

表5 Wilcoxon 符號秩檢驗

圖1 AUSLAN 數(shù)據(jù)集Precision 隨列-列協(xié)方差矩陣的主要特征向量個數(shù)s 的變化

圖2 Vowel 數(shù)據(jù)集Precision 隨列-列協(xié)方差矩陣的主要特征向量個數(shù)s 的變化

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

圖3 AUSLAN 數(shù)據(jù)集Precision 隨行-行協(xié)方差矩陣的主要特征向量個數(shù)r 的變化

圖4 Vowel 數(shù)據(jù)集Precision 隨行-行協(xié)方差矩陣的主要特征向量個數(shù)r 的變化

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

4 結(jié)論與展望

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