摘要：提出了一種基于時空密度聚類的隱馬爾科夫模型對時空序列進行預(yù)測的方法。時空序列與一般的時間序列相比，最主要的特征是其時空依賴性以及時空非平穩(wěn)性。針對如何有效地預(yù)測不同尺度分布的時空序列的問題，本文采用基于時空密度聚類的隱馬爾科夫模型，該模型不僅能分析時空序列在時間和空間上的相關(guān)性，而且可以通過時空序列的分段有效地去除噪聲，提高模型預(yù)測的精度。本文采用該模型對藥品冷藏庫中的時空序列溫度數(shù)據(jù)進行分析預(yù)測，并與其他預(yù)測模型比較，結(jié)果顯示本文提出的方法更準(zhǔn)確有效。

　　關(guān)鍵詞：密度聚類；隱馬爾科夫模型；時空序列預(yù)測

0引言

　　近年來國內(nèi)外對時間序列的分析研究［1］取得了很多重要的研究成果，但是對時空序列的分析研究還比較少。時空序列是時間序列在空間上的擴展，是指在空間上有相關(guān)關(guān)系的多個時間序列的集合，時空序列數(shù)據(jù)是具有空間信息的時間序列數(shù)據(jù)集。

　　目前對時空序列數(shù)據(jù)［2］的建模與預(yù)測方法大致可以分為兩類：基于時序的預(yù)測方法，如時空自回歸移動平均模型(STARMA)、時空神經(jīng)網(wǎng)絡(luò)(STANN)、時空支持向量機(STSVM)［3］等；基于因果預(yù)測方法，如地理加權(quán)回歸(GWR)［4］等。STARMA模型只適合對平穩(wěn)時空序列進行預(yù)測，然而大多數(shù)時空序列在時間域和空間域上都顯示著非平穩(wěn)的特征；STANN模型和STSVM模型雖然預(yù)測效果較為不錯，但是它們有一個共同點，即模型對歷史樣本的依賴程度非常大，而時空序列經(jīng)常出現(xiàn)波動，錯誤的樣本會嚴重影響預(yù)測的精度。GWR方法是一種局域空間分析的方法，展示了研究區(qū)域內(nèi)部空間關(guān)系的變化，對研究區(qū)域整體趨勢有一定的局限性。

　　本文提出一種基于時空密度聚類［5］的隱馬爾科夫模型（Hidden Markov Model,HMM）［6］對時空序列進行預(yù)測。首先采用CP-PLR算法［7］對原始時空序列進行分段，然后采用基于時空密度的聚類方法對時空數(shù)據(jù)進行聚類，最后通過隱馬爾科夫模型進行數(shù)據(jù)預(yù)測，將預(yù)測結(jié)果與其他模型的預(yù)測結(jié)果相比較，驗證了該模型的高精度性、高有效性。

1問題建模

　　針對本文的情況，假設(shè)給定一個空間內(nèi)的一個時空序列，其在二維空間內(nèi)的分布情況如圖1所示。

　　本文采用隱馬爾科夫模型對時空序列進行預(yù)測，模型運行的原理是在原始時空序列中獲得模型所需要的隱狀態(tài)序列，而獲得隱含狀態(tài)的序列就需要先解決對原始時空序列的聚類問題。由上圖可知，時空序列在空間內(nèi)的分布不均勻，如果將時間與空間分別進行相似性的度量，不能很好地結(jié)合二者，而且聚類后的結(jié)果具有很大的偏差，這樣將導(dǎo)致預(yù)測精度嚴重降低。

　　根據(jù)時空序列時間和空間上的鄰近性，在時空聚類分析中，傳統(tǒng)的距離度量準(zhǔn)則難以直接用來描述時空實體間的相似性，本文需要采用特殊的時空聚類方法，該聚類方法在兼顧時空相關(guān)性的同時還能很好地對時空序列進行度量，而密度的概念對此是可以直接適用的。要得到基于時空密度聚類的隱馬爾科夫模型，首先必須解決以下幾個問題：（1）如何將原始帶噪聲的時空序列很好地分段而且達到去噪的目的；（2）如何將分段后的時空序列根據(jù)時空相關(guān)性進行聚類。

2算法架構(gòu)

　　基于時空密度聚類的隱馬爾科夫預(yù)測模型的整體架構(gòu)如圖2所示。首先采用分段算法將原始時空序列進行分段，然后采用STDBSCAN算法對分段數(shù)據(jù)聚類，利用聚類的結(jié)果建立隱馬爾科夫模型，最后對時空序列進行狀態(tài)預(yù)測?！?/p>

3時空序列的聚類

　　時空序列數(shù)據(jù)與一般的時間序列數(shù)據(jù)和空間數(shù)據(jù)相比，時空依賴性(或相關(guān)性)、時空異質(zhì)性(或非平穩(wěn)性)是其最主要的特征。時空數(shù)據(jù)是時間和空間的組合，空間數(shù)據(jù)和時間序列的一些性質(zhì)在時空域中并不完全保持一致，例如在時間軸上信息是有明確的過去、現(xiàn)在和未來順序的，這種特征在空間域上并不存在，但是時空域卻繼承了這種時空特性。

　　3.1時空序列的分段

　　本文采用一種基于轉(zhuǎn)折點的PLR方法（CPPLR）進行時空序列的分段。首先通過搜索原始時空序列X={x1,x2,…xn}中的轉(zhuǎn)折點，并將這些轉(zhuǎn)折點用直線段連接起來,就得到了時空序列的一種分段線性表示，獲得分段后的時空序列轉(zhuǎn)折點的集合為S={xt1,xt2,…，xtN}，N為轉(zhuǎn)折點的數(shù)量，tN=n，終點默認為轉(zhuǎn)折點。CP-PLR方法能有效地發(fā)現(xiàn)原始序列中形態(tài)變化明顯的關(guān)鍵點，識別并剔除序列中的噪聲干擾，能有效地壓縮數(shù)據(jù),并保持較小的擬合誤差。

　　時空序列數(shù)據(jù)聚類分析過程中,不僅需要考慮時空序列的空間鄰近性，而且需要考慮在時間上體現(xiàn)的相似性。針對時空序列所具有時空相關(guān)性，為很好地對時空序列進行聚類，本文采用基于時空密度聚類中的STDBSCAN算法［8］。

　　時空密度聚類是空間密度聚類在時空域上的擴展，其采用密度作為實體間相似性的度量標(biāo)準(zhǔn)，將時空簇視為一系列被低密度區(qū)域（噪聲）分割的高密度連通區(qū)域。2006年，Wang等人在DBSCAN算法［9］的基礎(chǔ)上進一步考慮了時間維，發(fā)展了一種基于密度的時空聚類方法STDBSCAN，針對STDBSCAN算法需要過多輸入?yún)?shù)的缺點，參考文獻［10］中給出了經(jīng)驗設(shè)置方法。

　　3.2時空序列的聚類方法

　　STDBSCAN算法可以解決空間屬性、非空間屬性和時間屬性的聚類問題。本文對分段后的數(shù)據(jù)集合S進行聚類，即當(dāng)空間內(nèi)的兩個點同時滿足空間鄰近性與時間鄰近性兩個要求時則將兩點歸為一類［11］。聚類后的數(shù)據(jù)就可以用來建立隱馬爾可夫模型。聚類公式為：

　　Eps1表示空間屬性半徑,Eps2表示非空間屬性半徑。存在兩個點M(x1,y1,t1)和N(x2,y2,t2)，其中x,y代表空間屬性，t代表非空間屬性。當(dāng)M和N同時滿足式(1)和式(2)時，M和N點為Eps鄰近。

　　3.3基于時空密度聚類的隱馬爾科夫模型

　　隱馬爾可夫模型 ［12］是以馬爾科夫鏈為基礎(chǔ)演化而來。模型可以表示為λ=(A,B,π)，其中狀態(tài)轉(zhuǎn)移概率矩陣A={aij}，aij表示t時刻從狀態(tài)Si轉(zhuǎn)移到狀態(tài)Sj的概率；根據(jù)節(jié)點采集的原始數(shù)據(jù)計算出可觀察符號的概率分布矩陣B={bik}；初始狀態(tài)概率πi=P(q1=si)，它表示在初始時刻選擇某個狀態(tài)的概率。隱馬爾科夫模型的基本組成如圖3所示。

　　一個確定的隱馬爾科夫模型可以產(chǎn)生觀測序列O={o1,o2,…，oT}，ot表示在t時狀態(tài)為Si的觀察值。那么在隱馬爾科夫模型和隱藏狀態(tài)序列已知的情況下，隱藏狀態(tài)序列和可觀察狀態(tài)序列O的聯(lián)合概率為：

　　其中，P(O，Q|λ)為觀察序列O的概率，P(Q|λ)為隱藏狀態(tài)序列在此隱馬爾科夫模型下的概率。由于式（3）在隱馬爾科夫模型計算中計算量非常大，所以本文采用后向算法來解決概率計算的問題。根據(jù)以上兩步確定的隱馬爾科夫模型λ，定義在時刻t且狀態(tài)為qi的前提下，從t+1到T的部分觀測序列Ot+1,Ot+2,…,OT的概率為后向概率，記作：βt(i)=P(Ot+1，Ot+2,…,OT|st=qi,λ)，最終的概率公式為：

　　本文采用隱馬爾科夫模型作為對時空序列進行預(yù)測的系統(tǒng)模型，通過聚類算法處理時空序列獲得幾個隱含狀態(tài)，從而將時空序列預(yù)測問題轉(zhuǎn)化為狀態(tài)預(yù)測問題。

　　通過聚類算法聚類S序列，并將聚類看作K個隱狀態(tài)，基于時空密度聚類就可以建立狀態(tài)轉(zhuǎn)移矩陣A。同時以分段后的序列S作為觀測對象建立隱馬爾科夫模型，由式（4）產(chǎn)生預(yù)測序列的概率。

　　最后采用維特比算法預(yù)測最優(yōu)的狀態(tài)序列：

　　輸入：隱馬爾科夫模型λ=（A,B,π）和觀測序列S=xt1,xt2,…,xtN；輸出：最優(yōu)狀態(tài)序列S*=x*t1,x*t2,…，x*tN。

4實驗驗證

　　利用基于密度聚類的隱馬爾科夫模型對藥品冷藏庫內(nèi)的溫度進行預(yù)測，采用均方根誤差來衡量模型預(yù)測的精度，并且對同一個時空序列采用時空神經(jīng)網(wǎng)絡(luò)(STANN)、地理加權(quán)回歸(GWR)分別對其進行下一時刻溫度的預(yù)測，實驗中每隔15 min預(yù)測一次，然后計算均方根誤差的值，最后將三個模型的誤差值進行比較。衡量預(yù)測精度的均方根誤差公式為：

　　其中，Xmodel,i為下一時刻溫度的觀測值，Xobs,i為模型的預(yù)測值，n為預(yù)測的次數(shù)，均方根誤差的值越小說明預(yù)測精度越高。圖4為基于時空密度的隱馬爾科夫模型對藥品冷藏庫內(nèi)溫度預(yù)測方法與STANN模型、GWR方法預(yù)測誤差值的比較曲線圖。

　　從圖4中可以看出，本文提出的基于時空密度聚類的隱馬爾科夫模型對時空序列的預(yù)測具有較高的精度，在進行多步預(yù)測之后，誤差增長較小，而其他兩種模型的預(yù)測精度要遠低于基于時空密度聚類的隱馬爾科夫模型對時空序列的預(yù)測，而且隨著預(yù)測步數(shù)的增長，預(yù)測誤差也越來越大。

5結(jié)束語

　　在隱馬爾科夫預(yù)測模型的基礎(chǔ)上，針對時空序列不同于時間序列的特性，本文提出了基于時空密度聚類的隱馬爾科夫模型。首先根據(jù)時空密度聚類出隱馬爾科夫模型所需的隱狀態(tài)，然后采用隱馬爾科夫模型對隱狀態(tài)序列進行預(yù)測。經(jīng)實驗驗證，該模型能夠很好地預(yù)測時空序列，而且由于在處理原始時空序列的過程中能去除其中的噪聲，因此預(yù)測精度較高。

參考文獻

　?。?］ 章登義,歐陽黜霏,吳文李.針對時間序列多步預(yù)測的聚類隱馬爾科夫模型［J］.電子學(xué)報,2014（12）:2359-2364.

　　［2］ Cao Liying, San Xiaohui, Zhao Yueling,et al. The application of the spatiotemporal data mining algorithm in maize yield prediction［J］. Mathematical and Computer Modelling,2013,7(1):507-513.

　?。?］ 王佳璆.時空序列數(shù)據(jù)分析和建模［D］.廣州：中山大學(xué),2008.

　　［4］ 劉美玲.時空地理加權(quán)回歸模型的統(tǒng)計診斷［D］.西安：西安建筑科技大學(xué),2013.

　?。?］ STRAUSS C, ROSA M B, STEPHANY S. Spatiotemporal clustering and density estimation of lightning data for the tracking of convective events［J］. Atmospheric Research,2013,8(1):98-102.

　?。?］ 彭子平,張嚴虎,潘露露.隱馬爾科夫模型原理及其重要應(yīng)用［C］.2008年中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇,2008:138-139.

　?。?］ 方如果.基于相似性分析的時間序列數(shù)據(jù)挖掘算法研究［D］.杭州：浙江大學(xué),2011.

　?。?］ 唐建波,鄧敏,劉啟亮.時空事件聚類分析方法研究［J］.地理信息世界,2013(1):38-45.