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

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

0引言

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

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

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

1問(wèn)題建模

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

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

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

2算法架構(gòu)

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

3時(shí)空序列的聚類

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

　　3.1時(shí)空序列的分段

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

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

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

　　3.2時(shí)空序列的聚類方法

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

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

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

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

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

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

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

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

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

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

4實(shí)驗(yàn)驗(yàn)證

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

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

　?。?］ 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.

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

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

　　［5］ 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án)虎,潘露露.隱馬爾科夫模型原理及其重要應(yīng)用［C］.2008年中國(guó)信息技術(shù)與應(yīng)用學(xué)術(shù)論壇,2008:138-139.

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

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