柳姣姣，禹素萍，吳 波，姜 華，何風(fēng)行，李鳳榮

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

基于隱馬爾科夫模型的時(shí)空序列預(yù)測(cè)方法*

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

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

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

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

圖1 時(shí)空序列的空間分布平面圖

本文采用隱馬爾科夫模型對(duì)時(shí)空序列進(jìn)行預(yù)測(cè)，模型運(yùn)行的原理是在原始時(shí)空序列中獲得模型所需要的隱狀態(tài)序列，而獲得隱含狀態(tài)的序列就需要先解決對(duì)原始時(shí)空序列的聚類問題。由上圖可知，時(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è)問題：(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è)。

圖2 基于時(shí)空密度聚類的隱馬爾科夫模型架構(gòu)

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í)間屬性的聚類問題。本文對(duì)分段后的數(shù)據(jù)集合S進(jìn)行聚類，即當(dāng)空間內(nèi)的兩個(gè)點(diǎn)同時(shí)滿足空間鄰近性與時(shí)間鄰近性兩個(gè)要求時(shí)則將兩點(diǎn)歸為一類[11]。聚類后的數(shù)據(jù)就可以用來(lái)建立隱馬爾可夫模型。聚類公式為：

(1)

(2)

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|λ)=P(O|Q,λ)P(Q|λ)

(3)

其中，P(O，Q|λ)為觀察序列O的概率，P(Q|λ)為隱藏狀態(tài)序列在此隱馬爾科夫模型下的概率。由于式(3)在隱馬爾科夫模型計(jì)算中計(jì)算量非常大，所以本文采用后向算法來(lái)解決概率計(jì)算的問題。根據(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,λ)，最終的概率公式為：

(4)

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

通過(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)序列：

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è)精度的均方根誤差公式為：

(5)

其中，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 模型預(yù)測(cè)誤差對(duì)比曲線圖

從圖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è)精度較高。

[1] 章登義,歐陽(yáng)黜霏,吳文李.針對(duì)時(shí)間序列多步預(yù)測(cè)的聚類隱馬爾科夫模型[J].電子學(xué)報(bào),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í)空序列數(shù)據(jù)分析和建模[D].廣州：中山大學(xué),2008.

[4] 劉美玲.時(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.

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

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

[8] 唐建波,鄧敏,劉啟亮.時(shí)空事件聚類分析方法研究[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] 章棟兵,姚寒冰,顏昕. 基于隱馬爾科夫模型的語(yǔ)義傾向性研究[J]. 微型機(jī)與應(yīng)用,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

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

TP301.6

A

1674-7720(2016)01-0074-03

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

2015-09-08)

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

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

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