基于2DSVD的多變量時(shí)間序列半監(jiān)督分類①

單中南，翁小清，馬超紅

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

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

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

1.1 基本概念

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

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

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

1.2 二維奇異值分解

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

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

1.3 相關(guān)工作

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

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

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

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

2.1 訓(xùn)練分類器

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

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

分類器訓(xùn)練好之后，在使用分類器對待測樣本進(jìn)行分類時(shí)，如果待測樣本與任何一個(gè)標(biāo)記為正類樣本之間的距離小于閾值r，則該樣本分類為正類，否則為負(fù)類[8]，閾值r為正類樣本與其最近鄰之間距離的平均值.

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

2.2 評估分類器

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

3 實(shí)驗(yàn)

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

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

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

3.2 性能比較

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

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

從表2可以看出，當(dāng)初始正類樣本的個(gè)數(shù)nSeeds為1 時(shí)，2DSVD 在10 個(gè)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 符號秩檢驗(yàn)的概率p值都小于0.05，說明2DSVD 的分類性能顯著地好于其它四種方法.當(dāng)nSeeds 為3 或5 時(shí)，也可以得到相同的結(jié)論.從表2、表3、表4中還可以看出，各種方法的平均Precision隨著nSeeds增大而增大，說明增加初始正類樣本個(gè)數(shù)，能夠提高算法的分類性能.

表2 nSeeds=1 時(shí)各種方法的Precision

表3 nSeeds=3 時(shí)各種方法的Precision

表4 nSeeds=5 時(shí)各種方法的Precision

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

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

表5 Wilcoxon 符號秩檢驗(yàn)

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

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

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

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

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

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

4 結(jié)論與展望

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