基于連續(xù)密度隱馬爾可夫的時間序列分類算法

李 霞

(武漢科技大學(xué)城市學(xué)院，湖北 武漢 430083)

1 引言

時間序列數(shù)據(jù)具有高維特性，在一個時間序列中，數(shù)據(jù)都包含在不同時刻的變化中。時間序列會按照某些模式變化，所以數(shù)據(jù)很容易存在一定噪聲[1]。因此，不同維度上數(shù)據(jù)的關(guān)聯(lián)性十分重要，有效檢測出冗雜數(shù)據(jù)，繼而完成高效挖掘及獲取信息，是當(dāng)前時間序列分類算法的研究重點(diǎn)。分類問題是數(shù)據(jù)挖掘的基礎(chǔ)，對于一個未知類型的時間序列，如何把它分配至某個預(yù)定義類別中，是分類的關(guān)鍵任務(wù)[2]，也是當(dāng)前相關(guān)領(lǐng)域的重點(diǎn)研究問題。

目前已有相關(guān)外學(xué)者對這一問題做出了研究，并取得了一定的研究成果。文獻(xiàn)[3]構(gòu)建了基于BP和樸素貝葉斯的時間序列分類模型。利用BP神經(jīng)網(wǎng)絡(luò)非線性映射能力和樸素貝葉斯分類器的穩(wěn)定性能，在少量標(biāo)記數(shù)據(jù)的情況下，把BP神經(jīng)網(wǎng)絡(luò)獲取的特征引入樸素貝葉斯分類器內(nèi)，從而實(shí)現(xiàn)時間序列分類。該方法分類效率較高，但僅能在時間序列數(shù)據(jù)較少時才能使用，實(shí)用性較差。文獻(xiàn)[4]提出一種端對端深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)模型BiGRU-FCN，采用不同網(wǎng)絡(luò)計算得到卷積神經(jīng)網(wǎng)絡(luò)在時序信息上空間特征和雙向循環(huán)神經(jīng)網(wǎng)絡(luò)在序列上雙向時序依賴特征，同時對單維時間序列進(jìn)行分類。但該方法分類精度不高，無法滿足實(shí)際應(yīng)用需求。

針對上述方法存在的問題，提出一種基于連續(xù)密度隱馬爾可夫的時間序列分類算法。首先對時間序列趨勢進(jìn)行特征提取，明確其隨時間變化產(chǎn)生的轉(zhuǎn)換趨勢，得到時間序列數(shù)據(jù)中的關(guān)鍵數(shù)據(jù)，為后續(xù)分類計算的有效提供幫助。其次建立連續(xù)密度隱馬爾可夫模型，并在模型中加入因子分析，繼而提高時間序列分類速率；最后將平穩(wěn)子空間分析和相對熵相結(jié)合，實(shí)現(xiàn)時間序列的準(zhǔn)確分類。

2 時間序列變化趨勢特征提取

在數(shù)據(jù)挖掘過程中，數(shù)據(jù)的時間序列極值點(diǎn)含有較多的數(shù)據(jù)信息，因此也將極值點(diǎn)稱為關(guān)鍵點(diǎn)[5]。每個點(diǎn)的趨勢值和該分段趨勢值的偏差是不確定的，確?；A(chǔ)趨勢的準(zhǔn)確提取是提取時間序列變化趨勢特征的根本條件，所以將時間序列趨勢分割點(diǎn)當(dāng)作重要點(diǎn)構(gòu)建分割目標(biāo)函數(shù)，利用貪婪搜索法求解時間序列分段值，從而提取變化趨勢特征，獲取數(shù)據(jù)信息。

時間序列X是一個通過n項和時間前后次序關(guān)聯(lián)的數(shù)據(jù)記錄構(gòu)成的序列，其結(jié)構(gòu)表達(dá)式如式(1)所示

(1)

式中，x(ti)表示ti時段的數(shù)據(jù)記錄，t1

假設(shè)各個數(shù)據(jù)記錄內(nèi)包括全部視察對象的發(fā)生時間和M種不同屬性，則將其描述為

x(ti)=(ti，x1(ti)，x2(ti)，…，xj(ti)，…xM(ti))

(2)

式中，xj(ti)代表數(shù)據(jù)記錄屬性j處于時間ti中的值。針對式(1)的時間序列而言，假設(shè)其第q個重要點(diǎn)是

x*(q)=x(tpq)

(3)

式中，pq∈{1，2，…，n}代表第q個重要點(diǎn)在時間序列內(nèi)的方位，x(tpq)要符合以下關(guān)系的數(shù)據(jù)記錄

{[x(tpq-1)≤x(tpq)]∩[x(tpq+1)

(4)

{[x(tpq-1)≥x(tpq)]∩[x(tpq+1)>x(tpq)]}

(5)

根據(jù)以上公式可知，符合式(4)的重要點(diǎn)和局部極大值點(diǎn)相似，而符合式(5)的重要點(diǎn)與局部極小值點(diǎn)相似。若序列內(nèi)的點(diǎn)在平行線段內(nèi)，則線段中不包含重要點(diǎn)，該平行線段上的點(diǎn)均有可能是局部極值點(diǎn)。重要點(diǎn)與關(guān)鍵點(diǎn)的區(qū)別在于，關(guān)鍵點(diǎn)包含局部極值點(diǎn)和拐點(diǎn)，重要點(diǎn)中只有獨(dú)立的局部極值點(diǎn)[6]。

將有限長度的時間序列初始點(diǎn)與結(jié)束點(diǎn)當(dāng)作重要點(diǎn)，因為時間序列內(nèi)包含上升、穩(wěn)定及下降三種基礎(chǔ)變化趨勢，所以時間序列重要點(diǎn)的前后變化趨勢是完全不同的，但在鄰近重要點(diǎn)之間的時間序列內(nèi)的點(diǎn)擁有相同的基本走向[7]，所以重要點(diǎn)也是時間序列趨勢的轉(zhuǎn)折點(diǎn)，即時間序列趨勢的分割點(diǎn)。

為了更準(zhǔn)確地提取到時間序列數(shù)據(jù)特征，把時間序列分段值設(shè)定為k，將兩個目標(biāo)函數(shù)J2、J3實(shí)現(xiàn)最小化當(dāng)作目標(biāo)，選取分段位置及線性化方法組成時間序列分段線性近似方程

(6)

(7)

其中，J2表示時間序列趨勢值和分段基礎(chǔ)走向的偏差，a(ti)表示分段位置數(shù)據(jù)的特征值，在J2=0的情況下，即為時間序列分段線性近似值產(chǎn)生提取偏差；J3代表時間序列趨勢值序列和其分段趨勢值序列間的差異值。

在已知分段值的基礎(chǔ)上，為了對J2進(jìn)行優(yōu)化，就要將分段中每個點(diǎn)的基礎(chǔ)趨勢保持一致；而優(yōu)化J3則是要讓分段中每個點(diǎn)的趨勢值和該分段趨勢值的偏差為最小，兩個優(yōu)化目標(biāo)的定位不同，所以無法把多目標(biāo)問題簡單認(rèn)定成單目標(biāo)優(yōu)化問題。因為確?；A(chǔ)趨勢的準(zhǔn)確提取是時間序列趨勢特征提取的根本條件，所以把多目標(biāo)優(yōu)化問題轉(zhuǎn)變成以J2=0收斂條件下，最小化目標(biāo)函數(shù)J3的獨(dú)立目標(biāo)優(yōu)化問題

(8)

其中，aj為各個分段線性近似斜率值。sj，fj分別為時間序列分段的起始點(diǎn)和結(jié)束點(diǎn)。為了將上述優(yōu)化問題的求解過程進(jìn)行簡化，把該問題的描述模式進(jìn)行轉(zhuǎn)換。因為時間序列的重要點(diǎn)為時間序列基礎(chǔ)趨勢的自然切斷點(diǎn)，首先讓時間序列分段[sj，fj]內(nèi)不存在重要點(diǎn)，保證分段數(shù)k大于重要點(diǎn)分段值m-1。然后令上述時間序列分段進(jìn)行線性化近似，同時利用標(biāo)準(zhǔn)線性回歸方法推算各個分段線性近似斜率

(9)

把式(9)引入式(8)中，就能把原始優(yōu)化問題改變成求解時間序列最優(yōu)分段位置問題。利用解析式轉(zhuǎn)換已經(jīng)實(shí)現(xiàn)兩個目標(biāo)函數(shù)的最小化。理論意義上，時間序列分段數(shù)值是固定的，式(8)可利用窮舉搜索進(jìn)行求解，但是在分段個數(shù)較多時會發(fā)生組合爆炸，所以使用貪婪搜索方法進(jìn)行求解[8]。

首先將時間序列細(xì)致劃分成多個較短的原始分段，然后逐漸融合讓J3為最小值，且符合收斂條件J2=0的鄰域分段，直到實(shí)現(xiàn)設(shè)置的分段值為止。在原始階段，最大限度使用較小的原始分段長度，這樣可以減少分段趨勢值和趨勢值序列之間的偏差。但是，在分段融合時實(shí)現(xiàn)設(shè)定分段值k需要的迭代融合數(shù)量較多，計算量增加。所以，應(yīng)該在最大擬合偏差的前提下，使用較大的原始分段長度，降低分段融合過程中的計算量[9]，則理論意義的原始分段值的挑選可采用以下優(yōu)化問題來表示

(10)

其中，r表示原始分段長度，k表示設(shè)置的分段值，J為時間序列不分段的擬合偏差，δ是最高允許對應(yīng)擬合偏差。為了方便理解該優(yōu)化問題的運(yùn)算過程，將方法的具體步驟闡述如下：

(11)

式中，pq為第q個重要點(diǎn)位于時間序列的方位，在k

算出時間序列對照的趨勢數(shù)序列A及不分段時的擬合偏差J，任意給予一個原始分段長度r。按照m個重要點(diǎn)將時間序列進(jìn)行分割，構(gòu)成m-1個重要點(diǎn)分段，設(shè)定每個重要點(diǎn)分段均是長度為r的原始分段。若第j個重要點(diǎn)分段無法被r整分且分段長度nj≥r，則該重要點(diǎn)分段的第[nj/r]原始分段長度的取值范圍在r+1到2r-1之間，推算目前原始分段擬合偏差J3。

在分段融合階段，首先要明確可融合的鄰近分段集合，如果鄰近兩個分段的交界點(diǎn)不是重要點(diǎn)，則第j分段和第j+1分段就是可融合鄰近分段，可將變化趨勢特征記作

(12)

式中，u(ξ)∈[1，1]表示可融合鄰近分段的方位。通過上述過程可以了解時間序列數(shù)據(jù)隨時間改變產(chǎn)生的變化趨勢，獲得時間序列數(shù)據(jù)中的關(guān)鍵信息，為后續(xù)時間序列分類提供必要條件。

3 基于因子分析的連續(xù)密度隱馬爾可夫模型

隱馬爾可夫模型分為離散型與連續(xù)型。離散隱馬爾可夫模型利用向量量化技術(shù)把時間序列輸出設(shè)置成有限碼本，這樣會生成量化偏差[10]，模型精度較差。為了提升時間序列分類準(zhǔn)確率，根據(jù)時間序列的分布特征，選擇連續(xù)密度隱馬爾可夫模型，同時引入因子分析，構(gòu)建基于因子分析的連續(xù)密度隱馬爾可夫模型，用以對數(shù)據(jù)時間序列分類。

假設(shè)o∈RD代表D維觀測向量，x∈Rf為f維隱含參數(shù)，f<

(13)

因子分析下觀測向量計算過程為

o=∧x+u

(14)

式中，f維隱含參數(shù)x為因子參數(shù)或形態(tài)參數(shù)，u是觀測噪聲，順從平均值是μ、協(xié)方差矩陣是對角矩陣的高斯分布，D×f矩陣∧是一個觀測矩陣，代表形態(tài)向量x和觀測向量o之間的線性轉(zhuǎn)換關(guān)聯(lián)[11]。

使用參變量集合λ=[πi，aij，bj(o);1≤i，j≥N]代表某個N狀態(tài)連續(xù)密度隱馬爾可夫模型，集合中的π、a、b依次為模型的原始狀態(tài)分布、狀態(tài)移動概率矩陣和狀態(tài)輸出概率密度函數(shù)，bj(o)的值為對角協(xié)方差矩陣的高斯混合模式，將其描述為

(15)

其中，cjm、μjm、∑jm依次為狀態(tài)j的第m個混合參數(shù)、平均值向量及對角協(xié)方差矩陣。

為了完善模型的幀內(nèi)特征描述準(zhǔn)確性，運(yùn)用式(14)的因子分析矩陣高斯分布取代對角高斯分布，可得到

(16)

因此，將基于因子分析的連續(xù)密度隱馬爾可夫模型定義為

(17)

通過構(gòu)建連續(xù)密度隱馬爾可夫模型，可以最大限度保證時間序列分類速率，實(shí)現(xiàn)時間序列數(shù)據(jù)高效分類。

4 基于相對熵的時間序列分類算法

為了進(jìn)一步實(shí)現(xiàn)時間序列的精準(zhǔn)分類，引入平穩(wěn)子空間分析和相對熵設(shè)計時間序列分類算法。使用平穩(wěn)子空間分析方法訓(xùn)練集與測量集實(shí)施降維[12]，在降維后的空間內(nèi)，使用基于相對熵的近鄰算法將測量樣本進(jìn)行分類。

若第j類隨機(jī)過程Xj包含nj個觀察點(diǎn)，對該隨機(jī)過程進(jìn)行反復(fù)觀察，觀察次數(shù)為qj，可獲得qj個觀察序列，將其定義為

(18)

(19)

(20)

通過式(20)能夠得到時間序列數(shù)據(jù)的準(zhǔn)確類別，實(shí)現(xiàn)時間序列數(shù)據(jù)的精準(zhǔn)高效分類。

5 仿真研究

為了驗證本文方法的可靠性，設(shè)計仿真。選用為MATLAB仿真軟件作為仿真平臺，以Bay Area Bike Share’s 單車騎行數(shù)據(jù)(http：∥www.bayareabikeshare.com/open-data)作為仿真對象，在該數(shù)據(jù)集中選用200 Mb數(shù)據(jù)，將本文方法與文獻(xiàn)[3]、文獻(xiàn)[4]方法進(jìn)行仿真對比，測試三種方法對時間序列數(shù)據(jù)的分類準(zhǔn)確率及分類效率。

計算不同方法的分類錯誤率，以此為指標(biāo)判斷分類準(zhǔn)確率。數(shù)據(jù)時間序列分類錯誤率計算公式如下

(21)

通過式(21)能夠得到不同方法的分類錯誤率對比圖如圖1所示。

圖1 分類錯誤率對比圖

分析圖1可知，當(dāng)時間序列數(shù)據(jù)的類別數(shù)增長至4時，所提方法的分類錯誤率不再增加，保持在2%左右，文獻(xiàn)[3]方法的分類錯誤率大約是3%，文獻(xiàn)[4]方法分類錯誤率在類別數(shù)為5時不再發(fā)生變化，錯誤率為4.5%。文獻(xiàn)方法的分類錯誤率均高于所提方法，這是由于所提方法提取了時間序列趨勢特征，通過該特征構(gòu)建了連續(xù)密度隱馬爾可夫模型，能夠精準(zhǔn)分類相同時間序列趨勢的數(shù)據(jù)，因此所提方法時間序列分類精度較高，具備極強(qiáng)的優(yōu)越性。

對200 Mb時間序列數(shù)據(jù)分類，得到三種方法的分類時間對比圖，如圖2所示。

圖2 分類耗時對比圖

從圖2中可以看出，所提方法分類耗時23s，文獻(xiàn)[4]方法耗時28s，而文獻(xiàn)[3]方法伴隨樣本集合的增加，耗時逐漸增加，總耗時為45s。文獻(xiàn)方法僅適用于數(shù)據(jù)較少的序列分類，無法適用于數(shù)據(jù)量多的時間序列分類，適用性較差；而所提方法在連續(xù)密度隱馬爾可夫模型的基礎(chǔ)上引入了平穩(wěn)子空間分析，實(shí)現(xiàn)對隨機(jī)時間序列的快速觀察，通過相對熵的臨近算法確定不同時間序列的相似度，能夠快速得出最短距離類別，實(shí)現(xiàn)時間序列分類。綜上所述，所提方法的耗時最短，說明該方法的分類效率較高。

6 結(jié)論

為了提高時間序列數(shù)據(jù)分類的準(zhǔn)確率，同時保證分類速度，提出一種基于連續(xù)密度隱馬爾可夫的時間序列分類算法。提取時間序列趨勢特征，獲取數(shù)據(jù)內(nèi)主要信息，建立基于因子分析的連續(xù)密度隱馬爾可夫模型，然后使用平穩(wěn)子空間分析和相對熵完成時間序列的準(zhǔn)確分析。仿真結(jié)果表明，所提方法的分類準(zhǔn)確率較高，分類耗時較短，說明所提方法的分類效率高，具有一定的有效性。