基于LPP的時(shí)間序列半監(jiān)督分類

單中南, 翁小清, 武天鴻

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

0 引 言

時(shí)間序列是指按時(shí)間次序有序排列的一組數(shù)據(jù)，任何有次序的實(shí)值序列都可當(dāng)作時(shí)間序列來(lái)處理[1]。已有研究發(fā)現(xiàn)，時(shí)間序列數(shù)據(jù)?？蓮V泛見(jiàn)于金融、醫(yī)學(xué)、交通等諸多領(lǐng)域。建立準(zhǔn)確的分類器需要大量的有類別標(biāo)記的樣本數(shù)據(jù)，然而在現(xiàn)實(shí)應(yīng)用領(lǐng)域，存在大量沒(méi)有類別標(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ù)建立分類器[2]。

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

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

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

1.1 基本概念

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

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

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

1.2 局部保持投影

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

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

可通過(guò)解決最小化問(wèn)題來(lái)得到變換矩陣A中的變換變量a，對(duì)此可寫作如下數(shù)學(xué)形式：

(1)

其中，S為相似矩陣，如果xi在xj的k近鄰中或xj在xi的k近鄰中，Sij=exp(-‖xi-xj‖2/t)，其它情況Sij=0，參數(shù)t為一個(gè)適當(dāng)常數(shù)(本文設(shè)置為1)。可以通過(guò)求解下面的廣義特征值問(wèn)題來(lái)使目標(biāo)函數(shù)(1)達(dá)到最小，其數(shù)學(xué)公式可表示為：

XLXTa=λXDXTa

(2)

因?yàn)長(zhǎng)aplacian矩陣L和對(duì)角矩陣D都是對(duì)稱的和半正定的,故2個(gè)矩陣XLXT和XDXTy也是對(duì)稱的和半正定的。設(shè)a0,...,ad-1為式(2)的解，并已根據(jù)其特征值排序：0≤λ0≤ ... ≤λd-1。則嵌入結(jié)果將分別如式(3)～(4)所示：

xi→yi=ATxi

(3)

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

(4)

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

1.3 相關(guān)工作

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

Chen等人[11]在SSC算法中，使用一種基于DTW和ED相結(jié)合的特殊距離DTW-D，顯著地提高了分類的性能。Wei等人[12]針對(duì)正類中只有少量有標(biāo)記的樣本，使用歐氏距離建立基于最小最近鄰距離的分類器及停止準(zhǔn)則。Ratanamahatana等人[13]使用DTW(Dynamic Time Warping)距離來(lái)改進(jìn)樣本的選取并提出了新的停止準(zhǔn)則，該準(zhǔn)則基于未標(biāo)記樣本集中候選樣本與正類樣本的歷史距離；Begum等人[14-15]提出了一種基于最小描述長(zhǎng)度(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)。針對(duì)此問(wèn)題，Vinh等人[16-17]提供了后續(xù)改進(jìn)，并增加一個(gè)后處理步驟，使分類器更加精確。Vinh等人[18]還提出了一種基于約束的自訓(xùn)練算法，與正類集合最近的實(shí)例t，必須滿足約束條件DL(t|H)

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

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

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

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

2.1 訓(xùn)練分類器

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

(1)對(duì)未標(biāo)記的原始數(shù)據(jù)集使用主成分分析(PCA)進(jìn)行預(yù)處理，目的在于去噪聲處理和解決矩陣奇異性問(wèn)題。

(2)構(gòu)造鄰接圖，并對(duì)數(shù)據(jù)進(jìn)行特征映射，得到降維后的數(shù)據(jù)。

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

(4)重復(fù)(3)，直到滿足停止標(biāo)準(zhǔn)為止。

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

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

輸入：P表示初始訓(xùn)練集，包含少量已標(biāo)記正類樣本；U表示未標(biāo)記數(shù)據(jù)集；d表示所降維數(shù)；k表示近鄰個(gè)數(shù)；PCAratio表示PCA率；nseeds值表示初始標(biāo)記為正類樣本的個(gè)數(shù)

輸出：訓(xùn)練好的分類器

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

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

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

Step4計(jì)算相似性矩陣S，及拉普拉斯矩陣L，L=D-S，其中D為原始訓(xùn)練集構(gòu)成的對(duì)角矩陣。

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

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

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

Step8從F中隨機(jī)選取nseeds個(gè)正類樣本放入集合P。

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

Step10重復(fù)Step9，直到滿足停止標(biāo)準(zhǔn)為止。

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

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

(2)Step7～Step8為訓(xùn)練分類器階段，時(shí)間復(fù)雜度為O(m2)。

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

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

2.2 評(píng)估分類器

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

(5)

其中，K表示測(cè)試集中的正類樣本的個(gè)數(shù)，Npositive表示在前K個(gè)最接近P集合的樣本中，正類樣本的個(gè)數(shù)。

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

本節(jié)從Precision角度來(lái)評(píng)估LPP_SSCTS與原始方法的性能，研究采用的15個(gè)時(shí)間序列數(shù)據(jù)集均來(lái)自于UCR[26]檔案庫(kù)。

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

表1列出了15個(gè)時(shí)間序列數(shù)據(jù)集的主要特征，包括數(shù)據(jù)集名稱、類別數(shù)、訓(xùn)練集樣本數(shù)量、測(cè)試集樣本數(shù)量以及樣本長(zhǎng)度。選用數(shù)據(jù)集來(lái)自于工業(yè)、醫(yī)學(xué)、圖像、生物等領(lǐng)域。

3.2 性能比較

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

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

表2～4中的第2～4列分別給出了使用Wei_SSCTS，LPP_SSCTS的Precision以及相應(yīng)參數(shù)。

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

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

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

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

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

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

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

圖1 Synthetic_Control數(shù)據(jù)集Precision隨嵌入維數(shù)d的變化

Fig.1ThePrecisionofSynthetic_Controldatasetchangeswiththenumberofembeddingdimensiond

圖2 FaceAll數(shù)據(jù)集Precision隨嵌入維數(shù)d的變化

Fig.2ThePrecisionofFaceAlldatasetchangeswiththenumberofembeddingdimensiond

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

圖3 Beef數(shù)據(jù)集Precision隨k近鄰個(gè)數(shù)的變化

Fig.3ThePrecisionofBeefdatasetchangeswiththenumberofnearestneighbork

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

圖4 ECG200數(shù)據(jù)集Precision隨k近鄰個(gè)數(shù)的變化

Fig.4ThePrecisionofECG200datasetchangeswiththenumberofnearestneighbork

圖5 Symbols數(shù)據(jù)集Precision隨PCA率變化的情況

Fig.5ThePrecisionofSymbolsdatasetchangeswithPCAratio

圖6 Synthetic_Control數(shù)據(jù)集Precision隨PCA率變化的情況

Fig.6ThePrecisionofSynthetic_ControldatasetchangeswithPCAratio

4 結(jié)束語(yǔ)

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