基于OLPP符號(hào)表示的時(shí)間序列分類算法

武天鴻 翁小清

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

0 引 言

時(shí)間序列通常是指按時(shí)間順序排列而成的一組數(shù)據(jù)，任何有序的實(shí)值型數(shù)據(jù)都可以當(dāng)作時(shí)間序列處理[1]。時(shí)間序列分類根據(jù)訓(xùn)練集中對(duì)象所構(gòu)建的分類模型，判別被分類對(duì)象所屬的類別[2]。時(shí)間序列分類已經(jīng)被廣泛應(yīng)用于生活的各個(gè)方面，如模式識(shí)別、工業(yè)控制、金融和交通等，但時(shí)間序列數(shù)據(jù)維度高，分類難度大。

時(shí)間序列符號(hào)表示是一種重要的時(shí)間序列分析方法，是指將連續(xù)的實(shí)值型數(shù)據(jù)表示成低維離散的符號(hào)序列數(shù)據(jù)。時(shí)間序列符號(hào)表示方法不僅簡單高效，對(duì)噪聲具有魯棒性，還可以利用來自文本處理、信息檢索和生物信息學(xué)等領(lǐng)域的算法，對(duì)于提高時(shí)間序列分類算法的性能和效率具有重要意義。SAX(Symbolic Aggregate approXimation)[3-4]是一種經(jīng)典的時(shí)間序列符號(hào)表示方法，該方法能較好地體現(xiàn)時(shí)間序列的整體趨勢(shì)且簡單高效。但SAX只適用于服從高斯分布的時(shí)序數(shù)據(jù)，且僅用分段的均值并不能很好地描述時(shí)間序列的局部特征，完全不同的時(shí)間序列可能會(huì)得到相似的符號(hào)表示，SAX的MINDIST距離度量的緊性較差，容易產(chǎn)生誤報(bào)。目前，大部分基于符號(hào)表示的時(shí)間序列分類研究主要集中在SAX性能的改進(jìn)上，符號(hào)化時(shí)只考慮了單個(gè)時(shí)間序列樣本的數(shù)據(jù)，沒有考慮數(shù)據(jù)集樣本間的近鄰關(guān)系對(duì)分類的影響，且降維過程中沒有利用類標(biāo)簽的信息，是無監(jiān)督的表示方法。

本文提出一種基于正交局部保持映射[5]符號(hào)表示的時(shí)間序列分類方法OLPP_SC(OLPP Symbolic Classification)。該方法使用OLPP 將原始高維的時(shí)間序列數(shù)據(jù)映射到低維空間，在降維的同時(shí)很好地保留數(shù)據(jù)在原始空間的局部近鄰結(jié)構(gòu)；利用信息增益在降維后的數(shù)據(jù)上尋找最佳符號(hào)區(qū)間劃分點(diǎn)，采用多重系數(shù)分箱技術(shù)[6]將維數(shù)約簡后數(shù)據(jù)離散表示成符號(hào)序列，最后根據(jù)最近鄰法對(duì)符號(hào)表示的時(shí)間序列進(jìn)行分類。OLPP_SC清晰地考慮了樣本間近鄰關(guān)系和類標(biāo)簽信息對(duì)符號(hào)化分類的影響，具有自適應(yīng)的符號(hào)區(qū)間分段點(diǎn)，且僅需要較少的維數(shù)和字母個(gè)數(shù)就能達(dá)到不錯(cuò)的分類效果，對(duì)于解決時(shí)間序列分類中的維數(shù)災(zāi)難問題具有重要意義，在計(jì)算資源和存儲(chǔ)資源較少的設(shè)備中具有適用性。

1 相關(guān)研究

1.1 正交局部保持映射

正交局部保持映射是由局部保留投影(Locality Preserving Projection,LPP)[7]衍生的一種線性維數(shù)約減方法。LPP可得到一個(gè)簡單的線性變換，這個(gè)線性變換能夠最優(yōu)地將時(shí)間序列數(shù)據(jù)在高維空間的局部幾何結(jié)構(gòu)信息保留到低維空間。LPP的變換向量是非正交的，數(shù)據(jù)重構(gòu)困難，而OLPP的變換向量是正交的，具有比LPP更強(qiáng)的局部保留能力。非線性降維方法如局部線性嵌入[8](Locally Linear Embedding,LLE)、等距映射[9](Isometric Mapping,IsoMap)以及拉普拉斯特征映射(Laplacian Eigenmaps,LE)[10]等，只能用于給定的數(shù)據(jù)集，缺乏將新數(shù)據(jù)或?qū)ο笥成涞降途S空間的泛化能力，不適合解決分類問題。由于OLPP對(duì)測(cè)試樣本的適用性，相較于非線性降維方法，OLPP更適用于分類問題。OLPP降維算法可應(yīng)用于人臉識(shí)別[11]和文本索引[12]等方面。OLPP的實(shí)現(xiàn)[5]可簡述如下：

OLPP方法尋找一個(gè)變換矩陣G，該變換矩陣能夠?qū)⒁阎呔S空間訓(xùn)練數(shù)據(jù)集X=[x1,x2,…,xk]∈Rm映射到低維空間數(shù)據(jù)集Y=[y1,y2,…,yk]∈Rd,(d?m)，即yi=GTxi。通過對(duì)如式(1)所示的最小值問題進(jìn)行優(yōu)化求解轉(zhuǎn)換矩陣G，約束條件為gTXDXg=1，其中g(shù)為轉(zhuǎn)換向量。

(1)

可以采用兩種模式構(gòu)造鄰近圖：KNN模式和Supervised模式。KNN模式是指采用歐氏距離計(jì)算數(shù)據(jù)點(diǎn)間的距離，選取最近的k個(gè)點(diǎn)作為近鄰構(gòu)造近鄰圖，是無監(jiān)督的方法；Supervised模式是指根據(jù)類標(biāo)簽將屬于同一類的數(shù)據(jù)點(diǎn)相連，是有監(jiān)督的方法。定義相似矩陣(或權(quán)重矩陣)S，Sij評(píng)估數(shù)據(jù)集的局部近鄰結(jié)構(gòu)，其數(shù)學(xué)定義如下：

(2)

式中：t為常數(shù)。

令變換矩陣G中的變換向量為{g1,g2,…,gk}，定義G(k-1)=[g1,g2,…,gk-1],B(k-1)=[G(k-1)]T(XDXT)-1G(k-1)，可通過如下方式迭代計(jì)算正交變換基向量：g1等于與(XDXT)-1XLXT的最小特征值對(duì)應(yīng)的特征向量；gk等于與式(3)的最小特征值對(duì)應(yīng)的特征向量。

M(k)={I-(XDXT)-1G(k-1)[B(k-1)]-1[G(k-1)]T}

(XDXT)-1XLXT

(3)

xi→yi=GTxi

(4)

式中：yi是d維向量；G是m×d變換矩陣。

降維后的兩個(gè)數(shù)據(jù)點(diǎn)在低維空間的歐氏距離可以表示為：

Dolpp(yi,yj)=‖yi-yj‖=

‖xi-xj‖

(5)

G為正交矩陣,GGT=I也是單位矩陣，原始數(shù)據(jù)集的空間結(jié)構(gòu)能夠被很好地保留。

1.2 信息增益

信息增益(Information Gain)[6]表示得知特征X的信息而使得類Y的信息的不確定性減少的程度。對(duì)于分類系統(tǒng)而言，假設(shè)Y={(s1,y1),(s2,y2),…,(sN,yN)}是由N個(gè)值與類標(biāo)簽對(duì)組成的列表，pyi是標(biāo)簽yi在Y中出現(xiàn)的頻率，則多分類的熵定義為：

(6)

若以sp為符號(hào)區(qū)間分割點(diǎn)，則sp的熵如下：

(7)

式中：YL={(si,yi)|si≤sp,(si,yi)∈Y};YR={(si,yi)|si>sp,(si,yi)∈Y}。分割點(diǎn)sp的信息增益為：

inf_gain=Ent(Y)-Ent(Y,sp)

(8)

本文提出的時(shí)間序列符號(hào)表示方法，利用信息增益尋找符號(hào)區(qū)間的最佳劃分點(diǎn)，使每個(gè)分區(qū)中的大多數(shù)值對(duì)應(yīng)于同一個(gè)類，可以用同一個(gè)字母表示。這種有監(jiān)督的符號(hào)表示方法能夠充分利用類別的標(biāo)簽信息，有效提高訓(xùn)練模型的分類能力。

1.3 相關(guān)研究評(píng)述

基于符號(hào)表示的時(shí)間序列分類方法，根據(jù)時(shí)間序列數(shù)據(jù)轉(zhuǎn)化成符號(hào)序列的不同方式大致可以劃分為4類：基于趨勢(shì)分析，基于聚類或進(jìn)化計(jì)算，基于文本，基于頻率域。

針對(duì)SAX存在的缺陷，學(xué)者們提出的改進(jìn)方法大致可歸結(jié)為從局部趨勢(shì)特征描述、距離度量、符號(hào)區(qū)間劃分和序列分段4個(gè)方面，不同程度地提高算法分類性能，但是也不可避免地帶來一些新的問題，如參數(shù)選擇困難、計(jì)算復(fù)雜度高和維數(shù)約簡性能較差等。

Lkhagva等[13]提出使用每個(gè)分段的最小值、最大值和均值表示的 ESAX(Extended SAX)，字符串長度是SAX的三倍，且較SAX分類效果不顯著。將每個(gè)分段的線性回歸量化為字母表中一個(gè)符號(hào)的表示方法1d-SAX[14]在分段有噪聲時(shí)擬合誤差較大。首先將時(shí)間序列轉(zhuǎn)換成比值序列，再根據(jù)比值序列分段的趨勢(shì)特征進(jìn)行符號(hào)表示的方法[15-17]，在一定程度上保留原始時(shí)間序列的整體趨勢(shì)變化信息，但是對(duì)于變化特征不明顯的時(shí)間序列具有一定的局限。雖然符號(hào)與數(shù)值混合的表示方法[18-21]能夠顯著提高分類準(zhǔn)確率，但是不能應(yīng)用來自信息檢索、文本處理和生物信息學(xué)等領(lǐng)域算法，應(yīng)用領(lǐng)域受到限制。

為了減少SAX離散化過程中的信息丟失，Yin等[22]根據(jù)全局關(guān)鍵點(diǎn)將長時(shí)間序列分成若干個(gè)分段，依據(jù)各分段的趨勢(shì)特征對(duì)時(shí)間序列符號(hào)化，F(xiàn)uad等[23]對(duì)距離查找表進(jìn)行改進(jìn)提出UMD，這兩種方法在下界距離緊性和分類性能方面都好于SAX。Bai等[24]提出的rSAX通過小距離調(diào)整分段點(diǎn)使得彼此接近的點(diǎn)以更高的概率映射到相同符號(hào)。Sharabiani等[25]先使用SAX將時(shí)間序列轉(zhuǎn)化為符號(hào)序列，在符號(hào)序列上使用Bayesian規(guī)則和概率鏈規(guī)則建立模型BCM，然后用BCM對(duì)待測(cè)符號(hào)序列進(jìn)行分類，然而，BCM的分類準(zhǔn)確率與原始時(shí)間序列使用歐氏距離的1NN分類的準(zhǔn)確率差別不顯著。基于聚類和進(jìn)化計(jì)算的符號(hào)表示方法[26-31]，不管數(shù)據(jù)集是否具有Gaussian分布性質(zhì)都具有較好的適應(yīng)性，擴(kuò)展了SAX方法的適用范圍，但這類方法對(duì)于合適的聚類半徑、種群數(shù)量和進(jìn)化代數(shù)等參數(shù)的選擇是非常困難的，且所需存儲(chǔ)空間大、計(jì)算復(fù)雜度高。

將時(shí)間序列表示成符號(hào)序列后可利用自然語言處理的方法進(jìn)行分類，如：Boer等[32]使用Edit距離對(duì)符號(hào)序列進(jìn)行分類，分類性能好于Lin等[33]提出的BOP(Bag-Of-Patterns)模型；Senin等[34]提出將SAX與向量空間模型相結(jié)合的SAX-VSM模型。BOP和SAX-VSM可兼顧時(shí)間序列數(shù)據(jù)的局部特性和整體特性，對(duì)偏移量和噪聲具有魯棒性，分類準(zhǔn)確度高，但是，這類方法通常在訓(xùn)練階段的時(shí)間復(fù)雜度比較高，需要存儲(chǔ)空間也較大。

目前基于頻率域的符號(hào)表示分類方法的相關(guān)研究較少，主要是Schafer等[6]提出的SFA(Symbolic Fourier Approximation)以及以SFA為基礎(chǔ)的改進(jìn)算法[35-37]。SFA首先對(duì)時(shí)間序列進(jìn)行離散傅里葉變換，利用信息增益尋找前n個(gè)傅里葉系數(shù)的符號(hào)區(qū)間劃分點(diǎn)，并使用等寬離散方法對(duì)每一維系數(shù)進(jìn)行符號(hào)表示。基于頻率域的符號(hào)表示方法能夠有效解決分類任務(wù)中的維數(shù)災(zāi)難問題，而且能夠在一定程度上反映時(shí)間序列的整體變化趨勢(shì)。

武天鴻等[38]提出一種有監(jiān)督的時(shí)間序列符號(hào)化分類算法LDA_SC(LDA Symbolic Classification)，該算法考慮了樣本類別的標(biāo)簽信息對(duì)符號(hào)化分類的影響，分類效果好于已有方法。

大多數(shù)已有方法對(duì)原始時(shí)間序列進(jìn)行符號(hào)表示時(shí)，僅考慮了單個(gè)時(shí)間序列樣本的局部形態(tài)特征或整體趨勢(shì)，沒有考慮樣本之間的近鄰關(guān)系對(duì)符號(hào)化分類性能的影響。在分類問題中，清晰的樣本間近鄰關(guān)系能夠提高算法的分類性能，有監(jiān)督的符號(hào)表示方法具有更好的分類效果。

2 算法設(shè)計(jì)

2.1 符號(hào)近似表示

本文提出基于正交局部保持映射的符號(hào)表示方法SOLPPA (Symbolic OLPP Approximation)，該方法使用OLPP將時(shí)間序列的長度由n降到w(w?n)，采用數(shù)據(jù)自適應(yīng)的MCB方法，對(duì)維數(shù)約減后數(shù)據(jù)使用大小為a(2≤a≤20)的字母表進(jìn)行符號(hào)表示。使用SOLPPA將時(shí)間序列T近似表示成符號(hào)序列的過程如圖1所示。

圖1 SOLPPA符號(hào)近似表示過程

MCB是指根據(jù)每組數(shù)據(jù)的自身特點(diǎn)確定不同的離散間隔，各組數(shù)據(jù)之間離散間隔的分布是不同的，比如對(duì)時(shí)間序列的每一維數(shù)據(jù)可以采用等深或等寬的方式離散化，但是各個(gè)維度的數(shù)據(jù)的離散間隔分布不同。在SOLPPA算法中，使用信息增益確定降維后數(shù)據(jù)每一維的a-1個(gè)最佳分段點(diǎn)，即對(duì)應(yīng)a個(gè)符號(hào)的離散區(qū)間，落入任意區(qū)間的時(shí)間序列數(shù)據(jù)用相應(yīng)的符號(hào)表示。由于每維數(shù)據(jù)分段點(diǎn)的位置是不同的，長度為w的時(shí)間序列就有w組不同的分段間隔。這種方法能夠?qū)㈦x散化過程中的信息損失降到最小，在一定程度上提高分類準(zhǔn)確性。

2.2 距離度量

考慮兩條具有相同長度n的時(shí)間序列Q和C，它們之間的歐氏距離可表示為：

(9)

式中：qi和ci表示時(shí)間序列Q和C在時(shí)間點(diǎn)i的值。

(10)

(11)

2.3 算法步驟

本文提出的基于OLPP符號(hào)表示的時(shí)間序列分類算法主要包括三個(gè)步驟：(1) 使用OLPP將訓(xùn)練集和測(cè)試集從高維空間映射到低維空間；(2) 在降維后訓(xùn)練集的每一維上尋找符號(hào)區(qū)間分割點(diǎn)，根據(jù)分割點(diǎn)將降維后訓(xùn)練樣本表示成符號(hào)序列；(3) 利用訓(xùn)練集的分割點(diǎn)，將低維空間的測(cè)試樣本表示成符號(hào)序列并分類。基于OLPP符號(hào)表示的分類算法如下：

OLPP_SC(TRAIN,TEST,w,a,PCAratio,k，t)

輸入：訓(xùn)練集TRAIN，測(cè)試集TEST，OLPP降維數(shù)w，字母個(gè)數(shù)a，PCA率PCA_ratio，近鄰個(gè)數(shù)k和參數(shù)t。

輸出：分類準(zhǔn)確率accuracy。

Step1將TRAIN投影到PCA子空間，可通過PCA_ratio調(diào)整對(duì)原始數(shù)據(jù)降噪和消除矩陣奇異性的程度，PCA的轉(zhuǎn)換矩陣用WPCA表示。

Step2構(gòu)建鄰接圖P：在KNN模式中，若xi是xj的k近鄰或xj是xi的k近鄰，將xi與xj用一條邊相連,默認(rèn)t=1；在Supervised模式中，將屬于同類別的兩個(gè)樣本用一條邊相連，通過調(diào)節(jié)t值控制各邊權(quán)重，此時(shí)k不起作用。

Step3根據(jù)式(2)計(jì)算相似矩陣S及拉普拉斯矩陣G，L=D-S。

Step4根據(jù)式(3)，計(jì)算由正交基向量組成的轉(zhuǎn)換矩陣Gk={g1,g2,…,gk}。

Step5根據(jù)式(4)計(jì)算嵌入結(jié)果，yi=WTxi，其中W=WPCAGk。

Step6取出低維空間中訓(xùn)練集的某一維數(shù)據(jù)，根據(jù)式(6)-式(8)尋找信息增益最大的分段點(diǎn)sp1。

Step7分別在sp1前后兩段數(shù)據(jù)中找出分段點(diǎn)sp2和sp3，重復(fù)執(zhí)行，直至找出(a-1)個(gè)分段點(diǎn)，將該維數(shù)據(jù)劃分成a個(gè)區(qū)間，分別用a個(gè)不同字母表示。

Step8將每個(gè)樣本在該維的數(shù)據(jù)，根據(jù)其所在區(qū)間，轉(zhuǎn)換為相應(yīng)的字母。

Step9重復(fù)執(zhí)行Step 6-Step 8，直到訓(xùn)練集每一維數(shù)據(jù)都映射成字母，每個(gè)樣本也就表示成了符號(hào)序列。

Step10使用Step 5中的變換矩陣W，將TEST樣本映射到低維空間，使用TRAIN的分段點(diǎn)將低維空間的測(cè)試樣本表示成符號(hào)序列。

Step11使用最近鄰分類器，根據(jù)距離函數(shù)DIST對(duì)表示成符號(hào)序列的測(cè)試樣本進(jìn)行分類。

OLPP_SC根據(jù)OLPP構(gòu)造鄰接圖的兩種方法分為OLPP_SC的KNN模式和Supervised模式。OLPP_SC主要分為數(shù)據(jù)降維和符號(hào)表示兩個(gè)階段，Step 1是使用PCA對(duì)m個(gè)長度為n的樣本組成的訓(xùn)練集進(jìn)行預(yù)處理，其時(shí)間復(fù)雜度為O(m×n2)，Step 2搜索具有相同類標(biāo)號(hào)的樣本構(gòu)建鄰接圖，時(shí)間復(fù)雜度為O(n×m2)，Step 3-Step 5為計(jì)算正交基向量，若將n維降到d維，時(shí)間復(fù)雜度為O(d×m×n)；Step 6-Step 9為符號(hào)表示階段，用大小為a的字母表，將降維后的樣本表示成符號(hào)序列的時(shí)間復(fù)雜度為O((a-1)×m×d)，Step 10對(duì)表示成符號(hào)序列的測(cè)試樣本進(jìn)行分類，時(shí)間復(fù)雜度為O(m2)，所以算法總的時(shí)間復(fù)雜度為O((m×n2)+(n×m2)+(d×m×n)+((a-1)×m×d)+m2)。

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

本節(jié)對(duì)OLPP_SC在20個(gè)來自UCR[39]檔案庫的單變量時(shí)間序列數(shù)據(jù)集上的分類性能進(jìn)行評(píng)估，評(píng)估標(biāo)準(zhǔn)是分類準(zhǔn)確率。

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

20個(gè)時(shí)間序列數(shù)據(jù)集主要來自工業(yè)控制、人臉識(shí)別、醫(yī)療監(jiān)測(cè)等領(lǐng)域，表1描述了這些數(shù)據(jù)集的主要特征。

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

3.2 性能比較

將OLPP_SC方法的分類性能與SAX、ESAX、BCM、SAX_SM、LDA_SC五種方法進(jìn)行比較，評(píng)估標(biāo)準(zhǔn)為分類準(zhǔn)確率。為了實(shí)驗(yàn)對(duì)照，將字母個(gè)數(shù)限制在2～10之間。表2中分別給出了使用SAX、ESAX、BCM和LDA_SC四種方法在測(cè)試集上的分類準(zhǔn)確率及相應(yīng)參數(shù)，其中：w是符號(hào)序列的長度(即低維空間的維數(shù));a是字母表的大小;PCA_ratio是LDA_SC算法中的PCA比率。

表2 SAX、ESAX、BCM和LDA_SC的分類準(zhǔn)確率比較

表3給出了使用SAX_SM和OLPP_SC的兩種模式在測(cè)試集上的分類準(zhǔn)確率和相應(yīng)的參數(shù)設(shè)置，其中：PCA_ratio是OLPP_SC算法中的PCA比率，k是近鄰個(gè)數(shù);t是相似矩陣中的計(jì)算權(quán)重系數(shù)的常數(shù)。

表3 SAX_SM和OLPP_SC的兩種模式的分類準(zhǔn)確率

續(xù)表3

分析表2和表3中實(shí)驗(yàn)結(jié)果可知，OLPP_SC算法的兩種模式在20個(gè)數(shù)據(jù)集上分類的平均準(zhǔn)確率高于另外五種方法的平均準(zhǔn)確率，且OLPP_SC僅需要較少的維數(shù)就能夠達(dá)到較好的分類效果；OLPP_SC的Supervised模式的平均分類準(zhǔn)確率大于KNN模式的平均分類準(zhǔn)確率，Supervised模式分類性能比KNN模式的分類性能更好。

采用Wilcoxon符號(hào)秩檢驗(yàn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行進(jìn)一步評(píng)價(jià)。從表4可以看出，OLPP_SC的KNN模式與SAX、ESAX、BCM、SAX_SM的Wilcoxon符號(hào)秩檢驗(yàn)的概率p值都小于0.05，說明OLPP_SC_KNN的分類性能顯著地好于這四種分類方法。OLPP_SC_KNN的平均分類準(zhǔn)確率高于LDA_SC，但分類效果與LDA_SC差別不顯著；OLPP_SC的Supervised模式同時(shí)考慮了樣本間近鄰關(guān)系和類別的標(biāo)簽信息，OLPP_SC_Supervised與另外五種算法的Wilcoxon符號(hào)秩檢驗(yàn)的概率p值都小于0.05， 說明OLPP_SC_Supervised的分類效果顯著好于其他算法，樣本間的近鄰關(guān)系對(duì)符號(hào)化分類效果具有重要影響。

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

3.3 參數(shù)對(duì)分類性能的影響

本文提出的OLPP_SC算法的KNN模式有4個(gè)參數(shù)，即嵌入維數(shù)w、字母表大小a、PCA_ratio和近鄰個(gè)數(shù)k，Supervised模式有4個(gè)參數(shù)，即嵌入維數(shù)w、字母表大小a、PCA_ratio和參數(shù)t。

圖2給出了OLPP_SC的KNN模式在Synthetic_control數(shù)據(jù)集上，當(dāng)嵌入維數(shù)為20，k=9，PCA_ratio=0.99時(shí)，準(zhǔn)確率隨字母表大小a的變化情況。圖3給出了OLPP_SC的Supervised模式在Synthetic_control數(shù)據(jù)集上，當(dāng)嵌入維數(shù)為22，t=8，PCA_ratio=1時(shí)，準(zhǔn)確率隨字母表大小a的變化情況。分析圖2和圖3可以得出，字母個(gè)數(shù)小于3時(shí)，accuracy相對(duì)較低，字母個(gè)數(shù)在4～6之間分類準(zhǔn)確率較高，隨著字母個(gè)數(shù)繼續(xù)增加，準(zhǔn)確率趨于平穩(wěn)。字母表的大小對(duì)OLPP_SC的分類性能具有較大影響，OLPP_SC僅需要較小的字母表就能取得不錯(cuò)的分類效果，不需要太多的資源存儲(chǔ)距離查找表，分類計(jì)算復(fù)雜性也較低。

圖2 KNN模式準(zhǔn)確率隨a的變化(Snthetic_control數(shù)據(jù)集)

圖3 Supervised模式準(zhǔn)確率隨a的變化(Snthetic_control數(shù)據(jù)集)

圖4給出了OLPP_SC的KNN模式在Facefour數(shù)據(jù)集上，使用大小為8的字母表，k=7，當(dāng)PCA_ratio=0.99時(shí)，準(zhǔn)確率隨嵌入維數(shù)w的變化情況。圖5給出了OLPP_SC的Supervised模式在Synthetic_control數(shù)據(jù)集上，使用大小為8的字母表，t=8，當(dāng)PCA_ratio=0.99時(shí)，準(zhǔn)確率隨嵌入維數(shù)w的變化情況。分析圖4和圖5可知，當(dāng)嵌入維數(shù)w比較小時(shí)，分類準(zhǔn)確率比較低，隨著嵌入維數(shù)w逐步增加，準(zhǔn)確率快速升高并趨于穩(wěn)定。這說明嵌入維數(shù)對(duì)OLPP_SC具有較大影響，OLPP_SC不需要很高的嵌入維數(shù)就可以獲得很好的分類效果，良好的維數(shù)約簡性能對(duì)于解決時(shí)間序列分類中的維數(shù)災(zāi)難問題具有重要意義，且對(duì)計(jì)算資源和存儲(chǔ)資源較少的設(shè)備具有適用性。

圖4 KNN模式準(zhǔn)確率隨w的變化(Facefour數(shù)據(jù)集)

圖5 Supervised模式準(zhǔn)確率隨w的變化(Synthetic_control數(shù)據(jù)集)

圖6給出了OLPP_SC的KNN模式在Synthetic_control數(shù)據(jù)集上，當(dāng)字母個(gè)數(shù)為8，嵌入維數(shù)為25，k=7時(shí)，準(zhǔn)確率隨PCA_ratio變化的情況。圖7展示了OLPP_SC的Supervised模式在Synthetic_control數(shù)據(jù)集上，當(dāng)字母個(gè)數(shù)為8，降維數(shù)為22，t=8時(shí)，準(zhǔn)確率隨PCA_ratio變化的情況。分析圖6和圖7可知，準(zhǔn)確率在一定區(qū)域內(nèi)波動(dòng)，PCA_ratio對(duì)OLPP_SC算法性能影響較小。PCA_ratio的主要作用是消除噪聲和矩陣奇異性，如果PCA_ratio太小會(huì)造成信息損失過多，一般PCA_ratio的取值為80%～100%。

圖6 KNN模式準(zhǔn)確率隨PCA_ratio變化(Synthetic_control數(shù)據(jù)集)

圖8和圖9分別給出OLPP_SC的KNN模式在gun-point數(shù)據(jù)集和Oliveoil數(shù)據(jù)集上，使用大小為6的字母表，嵌入維數(shù)為20，當(dāng)PCA_ratio=0.99時(shí)，準(zhǔn)確率隨近鄰個(gè)數(shù)k的變化情況。可以看出，近鄰個(gè)數(shù)k對(duì)分類性能影響較大，通常選取較小的k值就能達(dá)到較好的分類效果，k值取得越小，表示的線性結(jié)構(gòu)越明顯，但是若鄰域過小，無法保證距離較遠(yuǎn)的數(shù)據(jù)間有足夠的聯(lián)系，算法不穩(wěn)定；如果k值較大則會(huì)無法較好地逼近局部線性結(jié)構(gòu)，且計(jì)算量較大，準(zhǔn)確率較低。

圖8 KNN模式準(zhǔn)確率隨k的變化(gun-point數(shù)據(jù)集)

圖9 KNN模式準(zhǔn)確率隨k的變化(Oliveoil數(shù)據(jù)集)

權(quán)重的設(shè)置與空間結(jié)構(gòu)的保留情況有很大關(guān)系，調(diào)節(jié)OLPP鄰接圖各邊上的權(quán)重大小可通過改變t值實(shí)現(xiàn)，當(dāng)t取無窮大時(shí)，權(quán)重逼近于1，此時(shí)可看作是LPP相似矩陣的推廣，t的取值與局部保留規(guī)模有關(guān)。圖10 給出OLPP_SC的Supervised模式在Trace數(shù)據(jù)集上，當(dāng)字母個(gè)數(shù)為9，嵌入維數(shù)為35，PCA_ratio=0.99時(shí)，準(zhǔn)確率隨t的變化情況。圖11是OLPP_SC的Supervised模式在Synthetic_control數(shù)據(jù)集上，當(dāng)字母個(gè)數(shù)為8，嵌入維數(shù)為22，PCA_ratio=0.99時(shí)，準(zhǔn)確率隨t的變化情況。分析圖10和圖11可得出，參數(shù)t對(duì)算法具有較大影響，t的值選取過大或過小都會(huì)使算法的分類準(zhǔn)確率降低，恰當(dāng)?shù)剡x取t值能夠使OLPP_SC得到較好的分類效果。

圖10 Supervised模式準(zhǔn)確率隨參數(shù)t的變化(Trace數(shù)據(jù)集)

圖11 Supervised模式準(zhǔn)確率隨參數(shù)t的變化(Synthetic_control數(shù)據(jù)集)

4 結(jié) 語

本文提出的基于OLPP符號(hào)表示的時(shí)間序列分類方法，在降維去噪的同時(shí)清晰地保留了樣本間的近鄰關(guān)系，使用信息增益尋找分段點(diǎn)能夠減少離散過程中的信息丟失，且有效利用樣本的類別信息。在20個(gè)時(shí)間序列數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，OLPP_SC好于已有的基于符號(hào)表示的時(shí)間序列分類方法，清晰的樣本間近鄰關(guān)系能夠提高算法的分類性能，有監(jiān)督的符號(hào)表示方法具有更好的分類效果。本文提出的OLPP_SC方法在目前使用全局統(tǒng)一的鄰域參數(shù)，對(duì)于如何根據(jù)樣本分布尋找自適應(yīng)的參數(shù)有待討論，如何將該算法與向量空間模型結(jié)合以及如何將OLPP_SC應(yīng)用于多變量時(shí)間序列的分類，還需要進(jìn)步一研究。