一種新的高階多元馬爾可夫鏈模型及其應用

闕素琴，張曉薇，滕忠銘

(福建農(nóng)林大學 計算機與信息學院，福建 福州 350002)

關(guān)鍵字：馬爾可夫鏈；多元馬爾可夫鏈；高階多元馬爾可夫鏈；參數(shù)估計

馬爾可夫鏈是人力資源[1]、金融[2]、互聯(lián)網(wǎng)應用[3]、音樂[4]、軟件測試[5]、土地覆蓋變化[6]、能源消耗[7]、語音識別[8]、微生物基因[9]、DNA序列[10]、信用風險[11]等許多研究領(lǐng)域的重要工具。探索不同分類數(shù)據(jù)序列之間的關(guān)系，建立更準確的預測模型是一個有意義的研究課題。

分類數(shù)據(jù)序列是由相互關(guān)聯(lián)的相同或相似的資源產(chǎn)生的，針對分類數(shù)據(jù)序列的預測，已經(jīng)提出了很多不同的模型，如Ching等[12-13]于2002年提出了一階多元馬爾可夫鏈模型，并于2009年改進了該模型，即在正態(tài)模型的后面添加負關(guān)聯(lián)部分，其特點是加快計算平穩(wěn)或穩(wěn)態(tài)解的收斂速度。Wang等[14]提出了一種改進的簡約多元馬爾可夫鏈模型，并發(fā)現(xiàn)了具有變異性的新收斂條件，可用于提高預測精度和收斂條件的最小化尺度。此外，Ching等[15]于2008年還提出了高階多元馬爾可夫鏈模型，并以DNA序列、銷售需求為例說明了所提出模型的預測能力。

隨著馬爾可夫鏈模型的發(fā)展及其應用，序列的數(shù)目可能會越來越大，序列的增大意味著有更多的參數(shù)需要被估計，從而不可避免地導致較高的計算成本。因此，減少模型需要被估計的參數(shù)的個數(shù)對數(shù)值計算具有重要的幫助。因此，Wang等[16]于2014年提出了一種增量式的多元馬爾可夫鏈模型，此模型探究了原始分類序列中增加一個新的序列后與原序列之間的關(guān)系，但此模型并沒有考慮高階多元馬爾可夫鏈的情形。為此，本文提出一種新的高階多元馬爾可夫鏈模型，其本質(zhì)是Wang的增量式模型在高階多元馬爾可夫鏈模型上的推廣，并通過數(shù)值實例說明本文所提出模型的有效性。

1 高階多元馬爾可夫鏈模型

定義 1隨機過程{St,t∈N}，N={0，1，2,…}，狀態(tài)空間 M={0，1，2,…，m}，對于任意的 t∈N，i，j，j0，…，jt-1∈M。若滿足

P{St+1=i∣S0=j0，S1=j1，…，St-1=jt-1，St=j}=P{St+1=i∣St=j}

則稱此隨機過程為馬爾可夫鏈。

定義2任意i，j∈M的，條件概率Pij=P{St+1=i∣St=j}稱為轉(zhuǎn)移概率。

令m×n階矩陣P=[Pij]是由Pij為元素構(gòu)成的一步轉(zhuǎn)移概率矩陣，其中。那么一元的馬爾可夫模型可表示為xt+1=Pxt，t∈N，這里xt表示t時刻狀態(tài)概率分布。當問題涉及到多個分類數(shù)據(jù)序列時，模型可以自然推廣到多元馬爾可夫模型。當有s個分類數(shù)據(jù)序列，多元馬爾可夫鏈模型可表示如下形式

這里λjk是模型中需要被估計的參數(shù)。

當多元馬爾可夫鏈中t+1時刻概率分布不僅僅依賴于時刻t的所有序列（包括它自己）的狀態(tài)概率分布時，Ching等[15]提出了一種如下形式的高階多元馬爾可夫鏈模型

在模型（2）中，如果令

那么（2）可用矩陣的形式表示如下

注意到在模型（2）中一共有ns2個需要被估計。令X是Xt的平穩(wěn)分布，即X滿足表達式X=QX。通過計算每個序列中各個狀態(tài)出現(xiàn)的比例，得到X的近似，那么參數(shù)可通過求解如下優(yōu)化問題得到

這里‖·‖∞表示向量的無窮大范數(shù)。具體的估計過程可詳見參考文獻[15]。特別地，如果問題中增加一個分類序列，則模型（2）中已估計的ns2個需要被重新計算，從而估計參數(shù)一共為 n（s+1）2個。這意味著原先已估計的個的信息，在增加一個序列后被完全拋棄了，這給數(shù)值計算增加了較大復雜度。為此，提出了一種增量式的高階多元馬爾可夫鏈模型，使得已估計的信息可以得到充分利用，從而減少模型中需要估計參數(shù)的數(shù)目。

2 新高階多元馬爾可夫鏈模型

假設(shè)原s個分類數(shù)據(jù)序列的高階多元馬爾可夫鏈模型如（2）所示，當增加一個新的分類數(shù)據(jù)序列時，本文提出一種新的高階多元馬爾可夫鏈模型，表示如下

其中 B*（ij）的定義與式子（3）和（4）類似，只需將式子（3）和（4）中的用代替。另外，注意到當i≠j≠s+1 時，有 B*（ij）=ljB（ij）。

3 參數(shù)估計

4 數(shù)值實驗

4.1 簡單例子

考慮下面的 3 個分類數(shù)據(jù)序列 Y（1）={2,1,3,3,4,3,2,1,3，3,2,1}，Y（2）={2,4,4,4,4,2,3,3,1，4,3,3}，Y（3）={1,2,3,4,1,4,4,3,3，1,3,1}，其中Y（3）序列是新增加的數(shù)據(jù)序列。通過計算轉(zhuǎn)移頻率矩陣，并經(jīng)正規(guī)化處理后得到轉(zhuǎn)移概率矩陣，且分類數(shù)據(jù)序列的穩(wěn)態(tài)概率分布如下

已知前兩個分類數(shù)據(jù)序列的高階多元馬爾可夫鏈模型（階數(shù)n=2）中的為已估計參數(shù)，增加一個新的序列s3后，通過求解相應的線性規(guī)劃問題估計參數(shù)lj和，從而得到新的高階多元馬爾可夫鏈模型為

為了說明新模型的有效性，本文探究了傳統(tǒng)高階多元馬爾可夫鏈模型和新高階多元馬爾可夫鏈模型的CPU所用時間t（單位/s）、估計參數(shù)個數(shù)np（單位/個）、以及線性規(guī)劃中的目標函數(shù)值w，其中傳統(tǒng)高階多元馬爾可夫鏈模型的參數(shù)是通過使用參考文獻[15]中的方法計算得到。通過MATLAB軟件編程，并使用其內(nèi)置函數(shù)tic和toc記錄CPU所用時間t，具體的數(shù)值結(jié)果詳見表1，其中新模型和傳統(tǒng)模型估計參數(shù)的個數(shù)np分別由公式n（2s+1）+s和n（s+1）2計算得到。

表1 兩種高階多元馬爾可夫鏈模型的w、t和np比較

由表1可以看出：傳統(tǒng)高階多元馬爾可夫鏈模型和新高階多元馬爾可夫鏈模型在線性規(guī)劃中的目標函數(shù)值w一致，且新模型CPU所用時間少于傳統(tǒng)模型的所用時間，新模型的估計參數(shù)個數(shù)也少于傳統(tǒng)模型的估計參數(shù)個數(shù)。因此，新模型在時間消耗和參數(shù)控制上都優(yōu)于傳統(tǒng)的模型。

4.2 銷售需求預測

第二個例子以銷售需求序列來說明新的高階多元馬爾可夫模型的優(yōu)越性。由于市場需求波動較大，生產(chǎn)計劃和庫存控制對成本有著直接影響的關(guān)系。因此，研究庫存空間需求與整體增長的銷售需求之間的相互作用是公司迫切需要解決的問題。我們的目標是預測市場的銷售需求，使成本最小化。假設(shè)產(chǎn)品被分為6種可能的狀態(tài)(1,2,3,4,5,6)，例如：1=無銷售量，2=非常低的銷售量，3=低銷售量，4=標準銷售量，5=高銷售量，6=非常高的銷售量。從營銷和生產(chǎn)計劃的角度來看，這樣的標簽是有意義的。

假設(shè)已給出了產(chǎn)品A，產(chǎn)品B，產(chǎn)品C和產(chǎn)品D這四類數(shù)據(jù)的序列,數(shù)據(jù)來源于參考文獻[15]。通過計算每個序列中每個狀態(tài)出現(xiàn)的比例，可以得到四個分類數(shù)據(jù)序列的初始概率分布如下

同樣的，考慮二階多元馬爾可夫模型，已知前四個分類數(shù)據(jù)序列的模型，其中的為已估計參數(shù)，此時增加一個新的序列（產(chǎn)品E）

利用新的高階多元馬爾可夫鏈模型估計得到：

根據(jù)所建的新高階多元馬爾可夫鏈模型得出：產(chǎn)品A與產(chǎn)品B密切相關(guān)的。特別是A產(chǎn)品的銷售需求很大程度上取決于B產(chǎn)品，主要原因是A產(chǎn)品和B產(chǎn)品的化學性質(zhì)是一樣的，為了營銷只是包裝不同而已。此外，產(chǎn)品C和產(chǎn)品E的關(guān)系也很相似，原因是它們有相似的產(chǎn)品味道。結(jié)果表明高階馬爾可夫模型對分析銷售需求關(guān)系是符合產(chǎn)品的實際情況，這對銷售需求的預測具有重要意義。

此外，本文利用傳統(tǒng)的和新的高階多元馬爾可夫鏈模型得到的預測序列Y（k）在t時刻的概率分布中取概率最大的那個狀態(tài)作為它的下一時刻的狀態(tài)，即

同樣的，在這個例子中，比較了傳統(tǒng)的高階多元馬爾可夫鏈模型和新的高階多元馬爾可夫鏈模型在線性規(guī)劃中的目標函數(shù)值（w）、CPU所用時間（t）和參數(shù)估計數(shù)目(np)的情況，具體見表2。另外，為了比較傳統(tǒng)和新的高階多元馬爾可夫鏈模型預測銷售需求的效果，表2列出了它們對各數(shù)據(jù)序列下一時刻所預測的狀態(tài)的概率。其中，傳統(tǒng)高階多元馬爾可夫鏈模型和本文所提出的新高階多元馬爾可夫鏈模型對產(chǎn)品A、產(chǎn)品B、產(chǎn)品C、產(chǎn)品D和產(chǎn)品E的預測狀態(tài)都為狀態(tài)6，狀態(tài)6，狀態(tài)6，狀態(tài)2和狀態(tài)2，且它們所對應的概率分別為0.4275，0.3978，0.6270，0.3581和0.3571。由表2可以得出這兩個模型在線性規(guī)劃中的目標函數(shù)值w以及預測效果上基本是一致的，但是新的高階多元馬爾可夫鏈模型CPU所用時間（0.0320 s）少于傳統(tǒng)模型的所用時間（0.0780 s）；新模型的估計參數(shù)個數(shù)僅僅22個，遠少于傳統(tǒng)模型的估計參數(shù)個數(shù)（50個）。為了進一步說明新模型的有效性，本文還分別分析了“產(chǎn)品 B、C、D、E 增加 A”、“產(chǎn)品 A、C、D、E 增加 B”、“產(chǎn)品 A、B、D、E 增加 C”以及“產(chǎn)品A、B、C、E增加D”的模型，得到了相似的結(jié)論。

表2 兩種高階多元馬爾可夫鏈模型的w，t，np以及預測狀態(tài)的比較

5 結(jié)論

本文提出了一種新的高階多元馬爾可夫鏈模型，該模型通過對原s個分類數(shù)據(jù)序列的高階多元馬爾可夫鏈模型的分析，建立原分類數(shù)據(jù)序列與增加一個序列后的新序列集之間的關(guān)系。正如在模型（5）的描述中所分析的那樣，新的高階多元馬爾可夫鏈模型只需要估計n（2s+1）+s個參數(shù)，這少于傳統(tǒng)模型的估計參數(shù)個數(shù)n（s+1）2。本文同時給出了新高階多元馬爾可夫鏈模型的參數(shù)估計方法，該估計方法最終將參數(shù)的計算轉(zhuǎn)化為一個線性規(guī)劃問題。最后通過兩個具體的數(shù)值例子說明了新模型在節(jié)省計算資源方面的優(yōu)越性，并且其預測性能與傳統(tǒng)模型基本保持一致。