單中南, 翁小清, 武天鴻

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

0 引 言

時間序列是指按時間次序有序排列的一組數據，任何有次序的實值序列都可當作時間序列來處理[1]。已有研究發(fā)現，時間序列數據常可廣泛見于金融、醫(yī)學、交通等諸多領域。建立準確的分類器需要大量的有類別標記的樣本數據，然而在現實應用領域，存在大量沒有類別標記的樣本數據，有標記的樣本數據很難獲得，或用人工標記樣本數據成本很高。半監(jiān)督分類(Semi-supervised classification, SSC)使用少量有標記的樣本數據和大量未標記數據建立分類器[2]。

目前，絕大多數已有的時間序列半監(jiān)督分類(Semi-supervised classification on Time Series, SSCTS)方法，都是對原始時間序列直接進行半監(jiān)督分類。由于時間序列樣本的維數(即長度)隨時間而不斷增加，當時間序列的維數較高時，會出現維災(curse of dimensionality)現象。為此，本文則采用了流形學習算法，在對時間序列原始數據降維的同時，還能具體考慮其在低維空間的內在結構。目前，研究指出，流形學習方法可以分為線性和非線性兩種[3]。其中，非線性方法包括等距映射[4](Isometric Mapping, IsoMap)、局部線性嵌入[5](Locally Linear Embedding, LLE)以及拉普拉斯特征映射(Laplacian Eigenmaps, LE)[6]等方法，這些方法只能在給定的數據集上運行，對新的數據缺乏泛化能力，即都沒有給出一種方法，將新的數據或對象映射到低維空間，所以這些方法不適合于半監(jiān)督分類問題；線性方法包括局部保持映射[7-8](Locality Preserving Projection, LPP)、鄰域保持嵌入[9](Neighborhood Preserving Embedding, NPE)、彈性保持映射[9](Elastic Preserving Projections, EPP)等方法。而據分析可知，LPP是一種線性的流形學習方法，在解決上述非線性算法存在問題的同時，還能使降維后的數據切實清晰地保持原數據的局部鄰域信息。在綜合了前述研究成果基礎上，本文即有針對性地提出了一種基于LPP的時間序列半監(jiān)督分類方法(LPP_SSCTS)。該方法首先使用LPP對時間序列樣本進行維數約減，然后對降維后的數據進行半監(jiān)督分類。

本文的論述結構安排如下：首先探討了本文研究的基礎背景和相關工作；其次，提出了基于LPP的時間序列半監(jiān)督分類算法；接下來，選取本文提出的方法與其它半監(jiān)督分類方法構建仿真實驗，并采用威爾克森符號秩檢驗(Wilcoxon Signed Ranks Test)對實驗結果進行對比，驗證算法的有效性；最后，給出了本文研究結論。

1 背景和相關工作

1.1 基本概念

定義1時間序列時間序列是一段時間內的一系列觀測值，用xi(t) [i=1, 2,...,n;t=1, 2,...,m]表示, 其中m是觀測值的個數，n是變量的個數[10]。當n=1 時，稱為單變量時間序列；當n≥2時，稱為多變量時間序列。本文的研究只是針對單變量時間序列。

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

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

1.2 局部保持投影

局部保持映射(Locality Preserving Projection, LPP)[7-8]作為一種線性降維方法，是非線性拉普拉斯(Laplacian)特征映射的線性近似。LPP在設計中考慮了數據的局部結構，使用 LPP 可以得到一個簡單的線性變換，這個線性變換在某種特定的意義上可以最優(yōu)地保持原數據集的局部鄰域信息。與非線性降維方法相比，LPP方法適用于新的樣本，因此，可以將LPP應用于半監(jiān)督分類問題。LPP的數學定義可表述如下：

已知Rn中的集合X={x1,x2,...,xk}，使用LPP方法找到變換矩陣A，將高維空間數據集X映射到低維空間Rl中的集合Y={y1,y2,...,yk} ,(l<

可通過解決最小化問題來得到變換矩陣A中的變換變量a，對此可寫作如下數學形式：

(1)

其中，S為相似矩陣，如果xi在xj的k近鄰中或xj在xi的k近鄰中，Sij=exp(-‖xi-xj‖2/t)，其它情況Sij=0，參數t為一個適當常數(本文設置為1)?？梢酝ㄟ^求解下面的廣義特征值問題來使目標函數(1)達到最小，其數學公式可表示為：

XLXTa=λXDXTa

(2)

因為Laplacian矩陣L和對角矩陣D都是對稱的和半正定的,故2個矩陣XLXT和XDXTy也是對稱的和半正定的。設a0,...,ad-1為式(2)的解，并已根據其特征值排序：0≤λ0≤ ... ≤λd-1。則嵌入結果將分別如式(3)～(4)所示：

xi→yi=ATxi

(3)

A=(a0,a1,...,al-1)

(4)

其中，yi為l維向量，A為n*l矩陣。

1.3 相關工作

時間序列的半監(jiān)督分類方法可大致分為3類[2]，即：基于實例、基于聚類以及基于模型的半監(jiān)督分類方法。對此，可做闡釋解析如下。

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

Nguyen等人[19]提出了一種PU學習算法LCLC(Learning from Common Local Clusters)，可以從未標記的集合U中有效地提取正類和負類樣本。LCLC是基于聚類的方法，采用了特征選擇策略，考慮了正類以及未標記實例的特征，從而使LCLC能夠更準確地評估簇或樣本之間的相似性。Nguyen等人[20]對LCLC算法加以改進，提出了En-LCLC算法。En-LCLC采用基于融合(ensemble)策略；通過多次執(zhí)行LCLC算法，降低了使用單個LCLC預測產生的潛在偏差。

Meng等人[21]提出了一種基于協同訓練的時間序列SSC方法，該方法在協同訓練階段使用HMM(hidden Markov model)和1-NN兩種學習器(learner)。Kim[22]將模式分類問題看作是混合生成模型(generative model)的密度估計問題，將其早期提出的有判別能力的混合模型的遞歸估計方法，擴展到了時間序列的半監(jiān)督分類；Kim[23]還提出了一種基于正則化框架(regularization framework)的半監(jiān)督學習算法；將熵最小化方法、半監(jiān)督支持向量機(S3VM)擴展到時間序列領域，采用HCRF(Hidden Conditional Random Field)模型捕獲時間序列數據中復雜的依賴結構。Xu等人[24]提出了一種基于圖的半學習框架，在使用harmonic Gaussian fields方法構造的圖上，使用類標簽的傳播，對沒有類別標簽的時間序列進行分類；Nooralishahi等人[25]基于growing neural gas(GNG)學習框架，提出了一種在線半監(jiān)督多通道(multi-channel)時間序列分類器。該方法能夠處理多通道時間序列，引入了一種標簽預測策略以減少誤分類。

在已有的半監(jiān)督分類算法中，都是直接使用時間序列原始數據進行半監(jiān)督分類，由于時間序列原始數據的維數隨時間而增高，存在“維災”現象，從而影響分類性能。本文提出的基于LPP的半監(jiān)督分類方法，對時間序列原始數據使用局部保持投影來提取高維空間數據的局部流形結構信息，在達到降維的目的同時，提高分類器的性能。

2 基于LPP的時間序列半監(jiān)督分類算法

2.1 訓練分類器

本文提出半監(jiān)督分類算法主要包括4個步驟，各步驟內容可分述如下。

(1)對未標記的原始數據集使用主成分分析(PCA)進行預處理，目的在于去噪聲處理和解決矩陣奇異性問題。

(2)構造鄰接圖，并對數據進行特征映射，得到降維后的數據。

(3)對降維后的數據隨機選取若干個正類樣本作為初始標記數據集P。計算集合U中每個樣本到集合P的歐氏距離，并將集合U中與集合P最近的樣本，從集合U中刪除，添加至集合P。

(4)重復(3)，直到滿足停止標準為止。

至此將研發(fā)推得基于LPP的時間序列半監(jiān)督分類算法的設計流程詳見如下。

算法1LPP_SSCTS(P,U,d,k,PCAratio,nseeds)

輸入：P表示初始訓練集，包含少量已標記正類樣本；U表示未標記數據集；d表示所降維數；k表示近鄰個數；PCAratio表示PCA率；nseeds值表示初始標記為正類樣本的個數

輸出：訓練好的分類器

Step1使用 PCA 將訓練集(P+U)投影到PCA子空間中，以達到去除噪聲的目的。

Step2用APCA表示PCA的變換矩陣，yi=APCATxi，xi∈訓練集(P+U)。

Step3在PCA子空間中，搜索yi的k最近鄰，構建鄰接圖G。

Step4計算相似性矩陣S，及拉普拉斯矩陣L，L=D-S，其中D為原始訓練集構成的對角矩陣。

Step5令列向量a0，a1，...，ad-1為公式(2)的解，按其特征值進行排序，即：0≤λ0≤λ1≤... ≤λd-1。

Step6由列向量組成的變換矩陣ALPP與APCA相乘得到所要求出的變換后的矩陣M。

Step7使用M與原始數據P+U相乘得到維數約減后的數據F。

Step8從F中隨機選取nseeds個正類樣本放入集合P。

Step9計算集合U中每個樣本到集合P的歐氏距離，將集合U中與集合P最近的樣本，從集合U中刪除，添加至集合P。

Step10重復Step9，直到滿足停止標準為止。

在Step10中，本文采用Wei等人[12]提出的停止標準，即在迭代過程中，當正類樣本的最小最近鄰距離在趨于穩(wěn)定后的第一次顯著下降時，即停止。LPP_SSCTS分為2個階段，對其可做解讀論述如下。

(1)Step1～Step6為數據降維階段：設訓練集中有m個長度為n的樣本。Step1中對訓練集使用PCA進行預處理的時間復雜度為O(m*n2)，Step2～Step6采用LPP對訓練集進行降維可分為2步：前者為k近鄰搜索，時間復雜度為O((n+k)*m2)[7-8，10]；后者為計算特征值，若將m維降到d維，時間復雜度為O((n+d)*n2)，因此LPP算法的復雜度為O((n+k)*m2+(n+d)*n2))。

(2)Step7～Step8為訓練分類器階段，時間復雜度為O(m2)。

故而，算法的總時間復雜度為O((m*n2)+ (n+k)*m2+(n+d)*n2+m2)。

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

2.2 評估分類器

算法1僅包含來自U中的正類樣本，屬于一類分類器。本文采用測試集對分類器的性能進行測試，測試集中包含一些正類對象和其它類對象。采用經典的精確度(Precision)和召回率(Recall)來衡量分類器的性能。在本文中，精確度的值等于召回率的值，即假的負類(False negatives)數量與假的正類(False positives)數量相同。精確度的數學定義可表示如下：

(5)

其中，K表示測試集中的正類樣本的個數，Npositive表示在前K個最接近P集合的樣本中，正類樣本的個數。

3 實驗

本節(jié)從Precision角度來評估LPP_SSCTS與原始方法的性能，研究采用的15個時間序列數據集均來自于UCR[26]檔案庫。

3.1 數據集描述

表1列出了15個時間序列數據集的主要特征，包括數據集名稱、類別數、訓練集樣本數量、測試集樣本數量以及樣本長度。選用數據集來自于工業(yè)、醫(yī)學、圖像、生物等領域。

3.2 性能比較

將本文提出的基于LPP的半監(jiān)督分類方法(LPP_SSCTS)，與Wei等人[12]提出的方法(用Wei_SSCTS表示)的分類性能進行比較。在實驗中，將數據集中類別標記為1的樣本作為正類樣本，其它類樣本為負類樣本。在算法1中，初始正類樣本的個數nSeeds分別取不同值，實驗重復2 000次，表2～4中給出了nSeeds分別取1、3、5時2種方法的平均Precision。

表1 數據集描述

表2～4中的第2～4列分別給出了使用Wei_SSCTS，LPP_SSCTS的Precision以及相應參數。

分析可知，LPP_SSCTS在15個數據集上分類的平均Precision高于Wei_SSCTS的平均Precision。2種方法的平均Precision隨著nSeeds增大而增大，說明增加初始正類樣本個數，能夠提高算法的分類性能。從表5中可以看到，當nSeeds為1、3、5時，LPP_SSCTS與Wei_SSCTS的Wilcoxon符號秩檢驗的概率p值都小于0.05，說明LPP_SSCTS的分類性能顯著地好于Wei_SSCTS。

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

本文提出的LPP_SSCTS算法有3個參數，即：PCAratio、最近鄰k的數量、以及嵌入維數d。圖1給出了在Synthetic_Control數據集上，當PCAratio=0.66、且最近鄰數k= 10時，Precision隨嵌入維數d的變化情況。圖2給出了在FaceAll數據集上，當PCAratio=0.86、且最近鄰數k= 6時，Precision隨嵌入維數d的變化情況。從圖1和圖2可以看出，嵌入維數d對算法的性能有較大影響。當嵌入維數d比較小時，Precision比較低。產生這種情況，一種可能的解釋為數據集中不同的區(qū)域經過映射以后，在嵌入空間中重疊在了一起；隨著嵌入維數d逐步增加，Precision快速上升。

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

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

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

表5 Wilcoxon符號秩檢驗

圖1 Synthetic_Control數據集Precision隨嵌入維數d的變化

Fig.1ThePrecisionofSynthetic_Controldatasetchangeswiththenumberofembeddingdimensiond

圖2 FaceAll數據集Precision隨嵌入維數d的變化

Fig.2ThePrecisionofFaceAlldatasetchangeswiththenumberofembeddingdimensiond

圖3給出了在Beef數據集上，當PCAratio=0.99、嵌入維數d=15時，Precision隨k近鄰個數的變化情況。圖4給出了在ECG200數據集上，當PCAratio= 0.79、嵌入維數d=48時，Precision隨k近鄰個數的變化情況。從圖3和圖4中可以看出，Precision在一定區(qū)域內波動，k值對算法的性能影響相對較小。

圖3 Beef數據集Precision隨k近鄰個數的變化

Fig.3ThePrecisionofBeefdatasetchangeswiththenumberofnearestneighbork

圖5給出了在Symbols數據集上，當k=11、嵌入維數d=24時，Precision隨PCAratio的變化情況。圖6給出了在Synthetic_Control數據集上，當k=10、嵌入維數d為3時，Precision隨PCAratio的變化情況。從圖5和圖6可以看出，Precision在一定區(qū)域內波動，PCAratio對算法的性能影響相對較小。

圖4 ECG200數據集Precision隨k近鄰個數的變化

Fig.4ThePrecisionofECG200datasetchangeswiththenumberofnearestneighbork

圖5 Symbols數據集Precision隨PCA率變化的情況

Fig.5ThePrecisionofSymbolsdatasetchangeswithPCAratio

圖6 Synthetic_Control數據集Precision隨PCA率變化的情況

Fig.6ThePrecisionofSynthetic_ControldatasetchangeswithPCAratio

4 結束語

本文提出了一種基于局部保持投影的時間序列半監(jiān)督分類方法LPP_SSCTS。針對不同的數據集，LPP_SSCTS只需選擇恰當的參數就可以在解決維災和去除噪聲的同時，還能使降維后的數據可以清晰地保持原數據的局部鄰域信息。在15個時間序列數據集上的實驗結果表明，本文提出的算法顯著地好于Wei_SSCTS。如何選擇最優(yōu)的參數以及如何將LPP_SSCTS應用于多變量時間序列的半監(jiān)督分類，仍將亟待下一步的深入探索與研究。