孫 紅,陳 鎖
1(上海理工大學(xué),上海 200093) 2(上海現(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,上海 200093)
近年來,由于大數(shù)據(jù)時(shí)代的來臨,以及物聯(lián)網(wǎng)技術(shù)的廣泛應(yīng)用,各種移動(dòng)終端的大量普及,大量GPS數(shù)據(jù)隨之產(chǎn)生,各種軌跡數(shù)據(jù)也越來越容易獲得,對GPS軌跡數(shù)據(jù)的研究也越來越多.大部分終端設(shè)備都已裝有GPS模塊,這些終端設(shè)備因而可以記錄GPS位置序列,這些序列包含經(jīng)緯度,時(shí)間戳等信息.時(shí)空軌跡(Trajectory)是移動(dòng)對象的位置和時(shí)間的記錄序列.作為一種重要的時(shí)空對象數(shù)據(jù)類型和信息源,時(shí)空軌跡的應(yīng)用范圍涵蓋了人類行為、交通物流、應(yīng)急疏散管理、動(dòng)物習(xí)性和市場營銷等諸多方面.時(shí)空數(shù)據(jù)的急劇增加,加之時(shí)空數(shù)據(jù)處理更為復(fù)雜,使數(shù)據(jù)處理任務(wù)日趨繁重的形勢更加嚴(yán)峻.因此,尋找有效的時(shí)空數(shù)據(jù)處理方法具有十分重要的意義.
時(shí)空大數(shù)據(jù)與非空間數(shù)據(jù)相比,具有空間性、時(shí)間性、多維性、海量性、復(fù)雜性等特點(diǎn).關(guān)于時(shí)空大數(shù)據(jù),目前存在一些技術(shù)前沿領(lǐng)域,如云計(jì)算方法和挖掘技術(shù).而預(yù)測移動(dòng)對象的運(yùn)動(dòng)趨勢有著廣泛的應(yīng)用.比如能夠有效地在軌跡數(shù)據(jù)中發(fā)現(xiàn)隱藏的有價(jià)值的信息,如頻繁路徑、個(gè)性化興趣點(diǎn)以及移動(dòng)意圖等.這些結(jié)果將對未來的商業(yè)應(yīng)用以及管理活動(dòng)提供有力的信息保障.
本文通過分析時(shí)空軌跡數(shù)據(jù),提出一種根據(jù)移動(dòng)對象經(jīng)過的軌跡,預(yù)測移動(dòng)對象下一個(gè)軌跡點(diǎn),以及未來的終點(diǎn)位置的模型.
對于移動(dòng)對象軌跡位置預(yù)測,近年來主要產(chǎn)生了兩種類型.一種是對歷史軌跡頻繁模式進(jìn)行挖掘進(jìn)而進(jìn)行預(yù)測.另一種是基于馬爾可夫(Markov)模型,對歷史軌跡進(jìn)行建模并預(yù)測.
軌跡頻繁模式挖掘算法,目前主要分為兩種:Apriori算法和PrefixSpan算法.一些研究將它們應(yīng)用到軌跡位置預(yù)測的建模中.一種基于廣度優(yōu)先搜索的Apriori算法結(jié)合自定義的運(yùn)動(dòng)函數(shù)和移動(dòng)軌跡模式,堪稱一種創(chuàng)新型的方法,可以參考Jeung等人[10]的相關(guān)文章.還有一種改進(jìn)版的Apriori算法,可參考Morzy[11]的相關(guān)文章.另一種主流算法是PrefixSpan算法,文獻(xiàn)[12]提出一種改進(jìn)型的PrefixSpan用來發(fā)現(xiàn)運(yùn)動(dòng)軌跡的歷史頻繁項(xiàng)并生成預(yù)測模型.此外,Monreale等人[2]提出的WhereNext方法也不失為一種好的方法,該算法從歷史軌跡中提取具有幾種不同運(yùn)動(dòng)行為的運(yùn)動(dòng)模式,進(jìn)而生成預(yù)測模型.
馬爾可夫模型對軌跡序列建模中,有一些比較新的成果,比如Figueiredo等人[7],他們使用不穩(wěn)定,瞬態(tài)且時(shí)間多樣化的軌跡序列,構(gòu)造出一種非參數(shù)模型用來對軌跡位置等做出預(yù)測.文獻(xiàn)[9]使用了一種HITS-based模型來挖掘用戶軌跡興趣點(diǎn),側(cè)重于分析軌跡全局的運(yùn)動(dòng)模式.
總的來說,現(xiàn)有工作大多是依據(jù)大量移動(dòng)對象軌跡的重合部分,挖掘出軌跡相似行為,再用來做預(yù)測.這種方式的缺點(diǎn)是:著重考慮表面發(fā)生的行為,對于事物內(nèi)在的隱含信息的考慮有所欠缺.
由于移動(dòng)物體產(chǎn)生的軌跡數(shù)據(jù)量比較大,而且這樣的數(shù)據(jù)還在不斷地增長,因而對于以上兩種方法,模型的訓(xùn)練成本非常大.本文基于此原因,提出一種基于聚類分區(qū)域的隱馬爾可夫模型,經(jīng)過大量GPS數(shù)據(jù)的訓(xùn)練,得出最佳模型參數(shù),最后通過隱狀態(tài)之間的轉(zhuǎn)移矩陣預(yù)測移動(dòng)對象軌跡最終位置.
馬爾可夫模型中,狀態(tài)是可見的,因此其又被稱為可視馬爾可夫模型(visible Markov model,VMM),狀態(tài)可見,在一定程度上限制了模型的適應(yīng)性.而在隱馬爾可夫模型(HMM)中,每個(gè)狀態(tài)是不可見的,可見的是各個(gè)狀態(tài)產(chǎn)生的事件的概率分布,狀態(tài)之間的轉(zhuǎn)換也是不可觀察的,可觀察的事件是由狀態(tài)產(chǎn)生的,每個(gè)狀態(tài)產(chǎn)生一個(gè)特殊分布的事件集合.圖1描述了隱馬爾可夫模型的基本原理.
圖1 隱馬爾可夫模型Fig.1 Hidden Markov model structure
一個(gè)HMM由如下幾個(gè)部分組成:
1)模型中隱狀態(tài)的數(shù)目N;
2)隱狀態(tài)可能輸出的不同可觀察符號的數(shù)目M
3)狀態(tài)轉(zhuǎn)移矩陣A={aij},其中,
aij=P(qt=sj|qt-1=si),1≤i,j≤N
aij≥0
4)可觀測事件概率分布矩陣B={bj(k)},其中,
bj(k)=P(Ot=vk|qt=sj),1≤j≤N;1≤k≤M
bj(k)≥0
5)初始狀態(tài)概率分布π={πi},其中,
πi=P(q1=si),1≤i≤N
πi≥0
一個(gè)HMM一般來說可以用以一個(gè)三元組來描述,μ=(A,B,π),A為狀態(tài)轉(zhuǎn)移概率,B為符號發(fā)射概率,π為初始狀態(tài)概率分布.當(dāng)一些現(xiàn)象產(chǎn)生是由于某些事物本質(zhì)變化做決定時(shí),用HMM進(jìn)行建模一般是非常有用的.因?yàn)镠MM能夠“深刻理解”事物的變化規(guī)律.HMM三個(gè)基本問題及其解決方法如下:
1)給定一個(gè)模型μ=(A,B,π),如何快速計(jì)算出觀察序列O=O1O2…OT的概率,即P(O|μ).
解決方法:前向算法、后向算法.
2)給定一個(gè)模型μ=(A,B,π),和一個(gè)已經(jīng)產(chǎn)生的觀察序列O=O1O2…OT,如何找出最可能產(chǎn)生觀察序列O的狀態(tài)序列Q=q1q2…qT.
解決方法:維特比算法.
3)給出大量觀察序列集,如何構(gòu)造出一個(gè)合適的隱馬爾可夫模型μ=(A,B,π).解決方法:Baum_Welch算法
HMM在自然語言處理研究中有著非常廣泛的應(yīng)用,尤其是在語音識別領(lǐng)域,一段語音可以作為觀測序列,語音對應(yīng)的文字作為隱狀態(tài),語音識別的首要任務(wù)就是求出最有可能發(fā)出該語音序列的隱狀態(tài),將語音恢復(fù)成文字.通過一部分可觀測序列,可以預(yù)測對應(yīng)的隱狀態(tài)序列,基于此,本文將HMM模型移植到時(shí)空軌跡序列預(yù)測的問題中.將大樣本時(shí)空軌跡序列,作為HMM的可觀測序列,將局部的時(shí)空坐標(biāo)點(diǎn)看成是附近某個(gè)隱狀態(tài)所發(fā)射出的觀測值,該隱狀態(tài)可以視為該局部區(qū)域的地標(biāo)點(diǎn).如圖2所示.
圖2 隱狀態(tài)及觀測值Fig.2 Hidden state and visible state
圖中黑色三角形即為隱狀態(tài),表示城市內(nèi)的多個(gè)地標(biāo),這些地標(biāo)可以看成是人群最愛去的地點(diǎn)的集合.以A點(diǎn)為例,周圍有1,2,3,4,5,6幾個(gè)GPS坐標(biāo)點(diǎn),它們分別是四條GPS軌跡中的點(diǎn),因?yàn)槎继幱贏點(diǎn)附近,因此可認(rèn)為它們是A狀態(tài)發(fā)射出的觀測點(diǎn),即它們服從A的發(fā)射概率分布.本文的任務(wù)之一就是要建立這樣的HMM模型,模型訓(xùn)練完成之后,輸入要預(yù)測終點(diǎn)的一段時(shí)空軌跡序列,即為觀測序列,然后通過相應(yīng)的算法求解出最佳隱狀態(tài)序列,通過隱狀態(tài)序列最后一個(gè)狀態(tài)以及轉(zhuǎn)移矩陣,計(jì)算出概率最大的下一個(gè)隱狀態(tài),再根據(jù)該隱狀態(tài)的發(fā)射概率分布計(jì)算出最有可能的發(fā)射值即為預(yù)測的終點(diǎn).整個(gè)流程如圖3所示.
HMM模型常用來進(jìn)行語音識別,一段語音的音節(jié)數(shù)量是很少的,一般是幾十個(gè),這樣的數(shù)量級,采用維特比算法來求解隱狀態(tài),即推斷語音對應(yīng)的文字或單詞,算法的執(zhí)行時(shí)間是非??焖俚?其原因是維特比算法的時(shí)間復(fù)雜度是O(N2T),其中N為發(fā)射出來的可觀測點(diǎn)的數(shù)目,T為狀態(tài)序列的長度.由于車輛一般都是往一個(gè)大致的方向行駛(一般不會存在繞著整個(gè)城市或局部區(qū)域反復(fù)行駛),因而一條完整的行駛路徑所穿過的地標(biāo)區(qū)域個(gè)數(shù)是比較少的,因而用維特比算法也是很快可以計(jì)算出最佳隱狀態(tài)序列.然而整個(gè)城市的所有地標(biāo)區(qū)域是非常多的,比如商場,運(yùn)動(dòng)場,小公園,小吃街等,實(shí)際上任何地方都可能成為車輛停止的終點(diǎn).因?yàn)闀r(shí)空序列終點(diǎn)的預(yù)測精度只要精確到一定的范圍內(nèi)即可,因此所有隱狀態(tài)的數(shù)量就非常多了,可能會有幾萬甚至幾十萬個(gè).如果針對整個(gè)城市建立一個(gè)含有如此龐大數(shù)量隱狀態(tài)的隱馬爾可夫模型(尤其是北上廣深這樣的特大城市),那么在用維特比算法求解隱狀態(tài)序列時(shí),遞歸算法將會非常耗時(shí),甚至很可能導(dǎo)致程序直接奔潰.本文針對該情形,設(shè)計(jì)了一種聚類分區(qū)域的隱馬爾可夫模型(Clustering Subregion Hidden Markov Model,即CSHMM).
圖3 算法流程圖Fig.3 Algorithm flow chart
3.2.1 產(chǎn)生隱狀態(tài)集
建模的第一步,是要確定所有的隱狀態(tài)集合,在本文中即為確定整個(gè)區(qū)域中的地標(biāo)點(diǎn)集合.
一般來說GPS經(jīng)緯度坐標(biāo)數(shù)值精確到小數(shù)點(diǎn)后4位即可明顯的區(qū)分兩個(gè)坐標(biāo)點(diǎn)為兩個(gè)不同的地點(diǎn)(相差幾十米至150米的兩個(gè)地點(diǎn)本文當(dāng)作同一地點(diǎn)),統(tǒng)計(jì)訓(xùn)練數(shù)據(jù)集中的所有不同地點(diǎn)出現(xiàn)的頻率fi.設(shè)置一個(gè)閾值r,將fi>r的所有地點(diǎn)標(biāo)記為地標(biāo).每個(gè)地標(biāo)使用其頻率作為權(quán)重.
其次,將得到的所有地標(biāo)點(diǎn)集,根據(jù)其權(quán)重進(jìn)行聚類,聚類的原則是:權(quán)重越高的地段所包含的區(qū)域面積越小,以使多個(gè)子區(qū)域包含的數(shù)量級相當(dāng).在此我們采用坐標(biāo)點(diǎn)的數(shù)量來代替區(qū)域面積,可以對此建立一個(gè)線性模型(也可以是非線性模型)來確定每個(gè)區(qū)域內(nèi)的大致坐標(biāo)點(diǎn)數(shù)目.本文采用一種改進(jìn)型的kmean——kmeans_cs如下函數(shù)模型來判定每個(gè)地標(biāo)周圍的坐標(biāo)點(diǎn)是否屬于該地標(biāo)的周邊區(qū)域:
設(shè)o為一個(gè)聚類中心點(diǎn),p為需要?dú)w類的點(diǎn),n為o類樣本集中包含p點(diǎn)的所有軌跡數(shù)量,o和p之間的距離D(o,p)采用如下定義:
D(o,q)=e‖o,p‖·‖o,p‖
(1)
其中||o,p||為o,p兩點(diǎn)的歐氏距離.由公式(1)可以看出兩個(gè)坐標(biāo)點(diǎn)的距離越近,則會有一個(gè)大于1的權(quán)重乘進(jìn)去使其增大.如果距離越大,那么乘上的權(quán)重會以指數(shù)增大,使得距離增加的更快.這樣會使得聚類的結(jié)果中面積越小的子區(qū)域包含的點(diǎn)越多,面積大的區(qū)域包含的點(diǎn)越少.改進(jìn)后的聚類算法可參考下文中2.2.2節(jié)中的聚類算法.
圖4大致描繪出映射建立結(jié)束后的圖形.
圖4 分區(qū)域后的隱狀態(tài)Fig.4 Hidden state after subregion
圖5中的黑色三角形即為隱狀態(tài),周圍的點(diǎn)即為隱狀態(tài)的發(fā)射符號集.
直觀表示如圖5所示.
圖5 隱狀態(tài)和觀測值的映射Fig.5 Mapping of hidden states and observation values
如圖4所示,首先通過聚類算法將城市中的所有地標(biāo)點(diǎn)進(jìn)行聚類,以此將全局區(qū)域分成若干個(gè)小區(qū)域,然后針對每個(gè)小區(qū)域,進(jìn)行HMM建模.模型建立完成以后,根據(jù)輸入的待預(yù)測的部分GPS軌跡,首先進(jìn)行區(qū)域匹配,選出最佳HMM模型,然后使用維特比算法針對該模型進(jìn)行預(yù)測.
3.2.2 聚類劃分子區(qū)域
由于地標(biāo)點(diǎn)數(shù)目太多,因而我們需要?jiǎng)澐肿訁^(qū)域,使得每個(gè)子區(qū)域內(nèi)的地標(biāo)點(diǎn)根據(jù)其權(quán)重均勻分布.劃分的原則是:子區(qū)域之間GPS軌跡跨越盡可能少.本文針對GPS軌跡的變化規(guī)律設(shè)計(jì)了一種改進(jìn)的k-means聚類算法,傳統(tǒng)的k-means算法采用歐氏距離來判斷點(diǎn)和點(diǎn)之間的類似程度,此方式會打破GPS軌跡坐標(biāo)的連貫性,即會大量出現(xiàn)同一條軌跡存在于多個(gè)子區(qū)域中,這是不符合要求的,因?yàn)楸疚男枰诿總€(gè)子區(qū)域單獨(dú)求解HMM模型,每個(gè)模型模擬了一個(gè)特定子區(qū)域GPS軌跡模式.基于該目的,本文提出一種能夠按照GPS軌跡來聚類的算法,該算法改進(jìn)了點(diǎn)和點(diǎn)之間的距離公式:
(2)
設(shè)o為一個(gè)聚類中心點(diǎn),p為需要?dú)w類的點(diǎn),n為o類樣本集中包含p點(diǎn)的所有軌跡數(shù)量,o和p之間的距離D(o,p)采用如下定義:
D(o,p)=tanh(n)×‖o,p‖
(3)
其中‖o,p‖為o,p兩點(diǎn)的歐氏距離.采用tanh函數(shù)來作為權(quán)重函數(shù).不采用sigmoid是因?yàn)閟igmoid自變量取值為0時(shí)函數(shù)值為0.5,而這里想要的是在區(qū)域p內(nèi)含有q點(diǎn)的軌跡數(shù)目為0時(shí),權(quán)重就變?yōu)?.
改進(jìn)后的聚類算法如下:
1)任選K個(gè)初始聚類中心Z1(1),Z2(1),Z3(1),…Zk(1);
根據(jù)樣本間的相互距離,將樣本分配到K個(gè)聚類區(qū)域,即若Min{d(Zi(k),X),i=1,2,…K} = d(Zj(k),X) = Dj(k),則X∈Sj(k),其中,k為迭代序號.
2)更新各個(gè)聚類中心Zj(k+1),其中j=1,2,3...K;
3)若Zj(k+1)≠Zj(k),則跳轉(zhuǎn)到步驟(2),將各個(gè)樣本重新分類,如此迭代;如果Zj(k+1)=Zj(k),j=1,2,…K,算法收斂,計(jì)算完畢.
對于每個(gè)子區(qū)域,其所有的地標(biāo)數(shù)據(jù)已經(jīng)確定,每個(gè)地標(biāo)周圍的稱為發(fā)射符號集的GPS坐標(biāo)點(diǎn)也已經(jīng)確定.已知的信息量比較充足,比如可以根據(jù)每個(gè)GPS坐標(biāo)的出現(xiàn)頻率,計(jì)算出發(fā)射概率矩陣B0.也可以根據(jù)大量軌跡來計(jì)算地標(biāo)與地標(biāo)之間的轉(zhuǎn)移概率,從而計(jì)算出轉(zhuǎn)移矩陣A0.
Baum-Welch算法是一種EM算法,專門用來訓(xùn)練HMM模型.EM過程保證算法一定能夠收斂到一個(gè)局部最優(yōu)點(diǎn),但是它不能保證找到全局的最優(yōu)點(diǎn).所以Baum-Welch算法不能保證找到全局的最優(yōu)模型.但是由于我們已經(jīng)知道了大致的解:狀態(tài)轉(zhuǎn)移矩陣A0和發(fā)射概率矩陣B0,如果將它們作為迭代的初始值,那么會有很大的概率收斂到全局最優(yōu)點(diǎn),并且訓(xùn)練的時(shí)間也大大減小.本文采用的Baum-Welch算法.
對于給定的隱馬爾可夫模型(HMM)μ和已知的觀察序列O=O1O2…OT,假設(shè)在t時(shí)刻該模型位于狀態(tài)si,在時(shí)間t+1時(shí)刻模型位于狀態(tài)sj,此概率ξt(i,j)可由如下公式計(jì)算獲得:
(4)
給定HMM的參數(shù)μ和觀察序列O=O1O2…OT,在時(shí)間t位于狀態(tài)si的概率γt(i)有下面的公式計(jì)算獲得:
(5)
而μ的參數(shù)可以有下面的公式重新估計(jì):
(6)
(7)
(8)
步驟1. 隨機(jī)給參數(shù)πi,aij,bj(k)賦值,并使其滿足如下約束:
由此得到新的模型μ0,令i=0,并用期望最大化算法(EM)重新估計(jì)模型的各個(gè)參數(shù);
步驟2. EM計(jì)算:
E步:由模型μi根據(jù)公式(4)和公式(5)計(jì)算出ξt(i,j)和γt(i);
M步:用E步得到的期望值,根據(jù)公式(6),公式(7),公式(8)重新估計(jì)參數(shù)πi,aij,bj(k),得到模型μi+1;
步驟3. 循環(huán)計(jì)算:
令i=i+1.重復(fù)執(zhí)行EM計(jì)算,直到πi,aij,bj(k)收斂.
對于給定的部分GPS軌跡序列,根據(jù)最后一個(gè)坐標(biāo)的位置,確定相應(yīng)的子區(qū)域,選取相應(yīng)子區(qū)域的HMM模型.將不在該子區(qū)域內(nèi)的坐標(biāo)點(diǎn)切除.使用靠近尾部的坐標(biāo)點(diǎn)作為可觀測序列.問題就變成了HMM模型的第二個(gè)問題.因此本文采用維特比算法來求隱狀態(tài)序列.算法如下:
步驟1. 初始化:
δ1(i)=πibi(O1),1≤i≤Nφ1(i)=0
步驟2. 歸納計(jì)算:
記憶回退路徑:
步驟3. 終結(jié):
步驟4. 路徑回溯:
求出隱狀態(tài)序列后,根據(jù)轉(zhuǎn)移矩陣A=[aij]和最后一個(gè)隱狀態(tài)qlast,求出下一個(gè)概率最大的可觀測坐標(biāo)點(diǎn)Pnext.求法如下:
(9)
其中l(wèi)ast為當(dāng)前時(shí)刻,next為下一時(shí)刻.
本文使用的數(shù)據(jù)集為T-Drive Trajectory data sample,來自微軟亞洲研究院(MSR),一共有10357個(gè)北京出租車在一周內(nèi)的GPS軌跡,每條軌跡提取出包含經(jīng)緯度和時(shí)間戳信息的子信息.實(shí)驗(yàn)選區(qū)75%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集,25%的數(shù)據(jù)作為測試數(shù)據(jù)集.代碼使用python語言,硬件配置為 Intel(R) Core(TM) i5-3320 2.60GHZ,12.0GB內(nèi)存,320GB硬盤的計(jì)算機(jī).
實(shí)驗(yàn)結(jié)果采用準(zhǔn)確率,召回率為評估標(biāo)準(zhǔn).
結(jié)果如圖6所示(準(zhǔn)確率和召回率為改進(jìn)kmeans后的結(jié)果,準(zhǔn)確率2和召回率2為不使用改進(jìn)的kmeanss).
圖6 kmeans和改進(jìn)型kmeans對模型效果的影響Fig.6 Effect of kmeans and improved kmeans on the model effect
結(jié)果分析:改進(jìn)kmeans后的算法導(dǎo)致模型準(zhǔn)確率和召回率提高了15%左右,說明改進(jìn)后的kmeans認(rèn)為同一個(gè)軌跡中的點(diǎn)更應(yīng)該屬于同一個(gè)聚類,因?yàn)檫@些點(diǎn)之間是有關(guān)聯(lián)的,有關(guān)聯(lián)的點(diǎn)之間的跳轉(zhuǎn),直接導(dǎo)致轉(zhuǎn)移概率的增大,因而會有更優(yōu)秀的準(zhǔn)確率.
結(jié)果如圖7所示(準(zhǔn)確率和召回率為改進(jìn)kmeans后的結(jié)果,準(zhǔn)確率3和召回率3為使用Apriori算法的結(jié)果,橫坐標(biāo)單位:萬條數(shù)據(jù),縱坐標(biāo)單位:百分比).
圖7 本文模型和其他模型性能對比Fig.7 Comparison of the performance of this model and other models
結(jié)果分析:改進(jìn)kmeans后的算法導(dǎo)致模型準(zhǔn)確率和召回率提高了8%左右.對比傳統(tǒng)關(guān)聯(lián)模式挖掘的算法,本文算法具有一定的優(yōu)勢.說明基于轉(zhuǎn)移概率的方式與挖掘時(shí)空序列軌跡相似度的方式相比,前者將一些影響軌跡趨勢的別的特征也考慮進(jìn)了模型中(即使沒有提取相關(guān)特征),因而會提高準(zhǔn)確度.
本文基于隱馬爾可夫模型,提出了一種預(yù)測移動(dòng)對象下一個(gè)位置的方法—基于聚類分區(qū)域的時(shí)空軌跡預(yù)測模型,該方法用以解決時(shí)空軌跡序列的預(yù)測問題.該模型首先通過聚類將一片區(qū)域內(nèi)的時(shí)空序列分成多個(gè)小區(qū)域,每個(gè)小區(qū)域內(nèi)再通過聚類確定多個(gè)隱狀態(tài)和發(fā)射序列,然后針對每個(gè)小區(qū)域進(jìn)行隱馬爾可夫模型的訓(xùn)練得出最終模型.預(yù)測時(shí)通過已知的時(shí)空序列,找到對應(yīng)的區(qū)域模型,通過維特比算法計(jì)算出最佳隱狀態(tài)序列,再結(jié)合轉(zhuǎn)移矩陣做出下一個(gè)軌跡點(diǎn)的預(yù)測,實(shí)驗(yàn)表明該方法在一定程度上提高了預(yù)測準(zhǔn)確率.
未來的工作中,可以使用機(jī)器學(xué)習(xí)或者深度學(xué)習(xí)的方式進(jìn)一步提高區(qū)域的劃分算法和軌跡聚類算法.