基于隱馬爾科夫模型的時空序列預測方法*

柳姣姣，禹素萍，吳 波，姜 華，何風行，李鳳榮

(1.東華大學 信息科學與技術學院，上海 201620；2.中國科學院上海高等研究院 公共安全中心，上海 201210；3.中國科學院上海微系統(tǒng)與信息技術研究所 無線傳感網(wǎng)與通信重點實驗室，上海 200050)

基于隱馬爾科夫模型的時空序列預測方法*

柳姣姣1,2，禹素萍1，吳 波2，姜 華2，何風行2，李鳳榮3

(1.東華大學 信息科學與技術學院，上海 201620；2.中國科學院上海高等研究院 公共安全中心，上海 201210；3.中國科學院上海微系統(tǒng)與信息技術研究所 無線傳感網(wǎng)與通信重點實驗室，上海 200050)

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

密度聚類；隱馬爾科夫模型；時空序列預測

0 引言

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

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

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

1 問題建模

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

圖1 時空序列的空間分布平面圖

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

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

2 算法架構

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

圖2 基于時空密度聚類的隱馬爾科夫模型架構

3 時空序列的聚類

時空序列數(shù)據(jù)與一般的時間序列數(shù)據(jù)和空間數(shù)據(jù)相比，時空依賴性(或相關性)、時空異質(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)變化明顯的關鍵點，識別并剔除序列中的噪聲干擾，能有效地壓縮數(shù)據(jù),并保持較小的擬合誤差。

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

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

3.2 時空序列的聚類方法

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

(1)

(2)

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

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

隱馬爾可夫模型[12]是以馬爾科夫鏈為基礎演化而來。模型可以表示為λ=(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|λ)=P(O|Q,λ)P(Q|λ)

(3)

其中，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,λ)，最終的概率公式為：

(4)

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

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

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

4 實驗驗證

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

(5)

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

圖4 模型預測誤差對比曲線圖

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

5 結(jié)束語

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

[1] 章登義,歐陽黜霏,吳文李.針對時間序列多步預測的聚類隱馬爾科夫模型[J].電子學報,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.

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

[4] 劉美玲.時空地理加權回歸模型的統(tǒng)計診斷[D].西安：西安建筑科技大學,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.

[6] 彭子平,張嚴虎,潘露露.隱馬爾科夫模型原理及其重要應用[C].2008年中國信息技術與應用學術論壇,2008:138-139.

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

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

[9] Jiang Hua, Li Jing, Yi Shenghe,et al. A new hybrid method based on partitioning-based DBSCAN and antclustering[J]. Expert Systems With Applications,2011,38(8):9373-9381.

[10] BIRANT D, KUT A. ST-DBSCAN: an algorithm for clustering spatial-temporal data[J]. Data & Knowledge Engineering,2007,60(1):208-221.

[11] 張麗杰,李廉水,朱慧云.一種帶有虛擬變量的密度聚類算法[J]. 系統(tǒng)工程,2011,29(10):112-118.

[12] 章棟兵,姚寒冰,顏昕. 基于隱馬爾科夫模型的語義傾向性研究[J]. 微型機與應用,2010,29(17):71-73.

A method of spatio-temporal sequence prediction based on hidden Markov model

Liu Jiaojiao1,2, Yu Suping1, Wu Bo2, Jiang Hua2,He Fenghang2, Li Fengrong3

(1.School of Information Science and Technology, Donghua University, Shanghai 201620, China;2.Public Security Center, Shanghai Advanced Research Institute, Chinese Academy of Sciences, Shanghai 201210, China;3.Laboratory of the Wireless Sensor Networks and Communications, Chinese Academy of Sciences Shanghai Institute of Microsystem and Information Technology, Shanghai 200050, China)

A method of spatio-temporal sequence prediction based on hidden Markov model of spatio-temporal density clustering is proposed in this paper. Compared with the general time sequences, the most important features of spatio-temporal sequence are the spatial and temporal dependence and non-stationary. For the problem of how to effectively predict the spatio-temporal sequence of different scales, a hidden Markov model based on temporal and spatial density clustering is used. The model can not only analyze the correlation between time and space, but also can effectively remove the noise and improve the accuracy of the model prediction. In this paper, the model is used to analyze the temperature data of the drug storage. We compare this model with other prediction models. The results show that the proposed method is more accurate and effective.

density clustering; hidden Markov model; spatio-temporal sequence prediction

中國科學院無線傳感網(wǎng)與通信重點實驗室開放課題(2013001)；廣東省中國科學院全面戰(zhàn)略合作項目(2012B090400031)

TP301.6

A

1674-7720(2016)01-0074-03

柳姣姣，禹素萍，吳波，等.基于隱馬爾科夫模型的時空序列預測方法[J].微型機與應用，2016，35(1)：74-76,80.

2015-09-08)

柳姣姣(1990-)，女，碩士研究生，主要研究方向：無線傳感網(wǎng)絡。

禹素萍(1977-)，女，博士，副教授，碩士生導師，主要研究方向:機器視覺與圖像處理、模式識別。

吳波(1980-)，男，碩士研究生，工程師，主要研究方向：無線傳感網(wǎng)絡。