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

李 霞

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

1 引言

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

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

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

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

在數據挖掘過程中，數據的時間序列極值點含有較多的數據信息，因此也將極值點稱為關鍵點[5]。每個點的趨勢值和該分段趨勢值的偏差是不確定的，確保基礎趨勢的準確提取是提取時間序列變化趨勢特征的根本條件，所以將時間序列趨勢分割點當作重要點構建分割目標函數，利用貪婪搜索法求解時間序列分段值，從而提取變化趨勢特征，獲取數據信息。

時間序列X是一個通過n項和時間前后次序關聯的數據記錄構成的序列，其結構表達式如式(1)所示

(1)

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

假設各個數據記錄內包括全部視察對象的發生時間和M種不同屬性，則將其描述為

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

(2)

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

x*(q)=x(tpq)

(3)

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

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

(4)

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

(5)

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

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

為了更準確地提取到時間序列數據特征，把時間序列分段值設定為k，將兩個目標函數J2、J3實現最小化當作目標，選取分段位置及線性化方法組成時間序列分段線性近似方程

(6)

(7)

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

在已知分段值的基礎上，為了對J2進行優化，就要將分段中每個點的基礎趨勢保持一致；而優化J3則是要讓分段中每個點的趨勢值和該分段趨勢值的偏差為最小，兩個優化目標的定位不同，所以無法把多目標問題簡單認定成單目標優化問題。因為確保基礎趨勢的準確提取是時間序列趨勢特征提取的根本條件，所以把多目標優化問題轉變成以J2=0收斂條件下，最小化目標函數J3的獨立目標優化問題

(8)

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

(9)

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

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

(10)

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

(11)

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

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

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

(12)

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

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

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

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

(13)

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

o=∧x+u

(14)

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

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

(15)

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

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

(16)

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

(17)

通過構建連續密度隱馬爾可夫模型，可以最大限度保證時間序列分類速率，實現時間序列數據高效分類。

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

為了進一步實現時間序列的精準分類，引入平穩子空間分析和相對熵設計時間序列分類算法。使用平穩子空間分析方法訓練集與測量集實施降維[12]，在降維后的空間內，使用基于相對熵的近鄰算法將測量樣本進行分類。

若第j類隨機過程Xj包含nj個觀察點，對該隨機過程進行反復觀察，觀察次數為qj，可獲得qj個觀察序列，將其定義為

(18)

(19)

(20)

通過式(20)能夠得到時間序列數據的準確類別，實現時間序列數據的精準高效分類。

5 仿真研究

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

計算不同方法的分類錯誤率，以此為指標判斷分類準確率。數據時間序列分類錯誤率計算公式如下

(21)

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

圖1 分類錯誤率對比圖

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

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

圖2 分類耗時對比圖

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

6 結論

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