孫 紅，陳 鎖

1(上海理工大學(xué)，上海 200093) 2(上?，F(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，上海 200093)

1 引 言

近年來(lái)，由于大數(shù)據(jù)時(shí)代的來(lái)臨，以及物聯(lián)網(wǎng)技術(shù)的廣泛應(yīng)用，各種移動(dòng)終端的大量普及，大量GPS數(shù)據(jù)隨之產(chǎn)生，各種軌跡數(shù)據(jù)也越來(lái)越容易獲得，對(duì)GPS軌跡數(shù)據(jù)的研究也越來(lái)越多.大部分終端設(shè)備都已裝有GPS模塊，這些終端設(shè)備因而可以記錄GPS位置序列，這些序列包含經(jīng)緯度，時(shí)間戳等信息.時(shí)空軌跡(Trajectory)是移動(dòng)對(duì)象的位置和時(shí)間的記錄序列.作為一種重要的時(shí)空對(duì)象數(shù)據(jù)類型和信息源，時(shí)空軌跡的應(yīng)用范圍涵蓋了人類行為、交通物流、應(yīng)急疏散管理、動(dòng)物習(xí)性和市場(chǎng)營(yíng)銷等諸多方面.時(shí)空數(shù)據(jù)的急劇增加，加之時(shí)空數(shù)據(jù)處理更為復(fù)雜，使數(shù)據(jù)處理任務(wù)日趨繁重的形勢(shì)更加嚴(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ù)測(cè)移動(dòng)對(duì)象的運(yùn)動(dòng)趨勢(shì)有著廣泛的應(yīng)用.比如能夠有效地在軌跡數(shù)據(jù)中發(fā)現(xiàn)隱藏的有價(jià)值的信息，如頻繁路徑、個(gè)性化興趣點(diǎn)以及移動(dòng)意圖等.這些結(jié)果將對(duì)未來(lái)的商業(yè)應(yīng)用以及管理活動(dòng)提供有力的信息保障.

本文通過(guò)分析時(shí)空軌跡數(shù)據(jù)，提出一種根據(jù)移動(dòng)對(duì)象經(jīng)過(guò)的軌跡，預(yù)測(cè)移動(dòng)對(duì)象下一個(gè)軌跡點(diǎn)，以及未來(lái)的終點(diǎn)位置的模型.

2 研究背景

對(duì)于移動(dòng)對(duì)象軌跡位置預(yù)測(cè)，近年來(lái)主要產(chǎn)生了兩種類型.一種是對(duì)歷史軌跡頻繁模式進(jìn)行挖掘進(jìn)而進(jìn)行預(yù)測(cè).另一種是基于馬爾可夫(Markov)模型，對(duì)歷史軌跡進(jìn)行建模并預(yù)測(cè).

軌跡頻繁模式挖掘算法，目前主要分為兩種：Apriori算法和PrefixSpan算法.一些研究將它們應(yīng)用到軌跡位置預(yù)測(cè)的建模中.一種基于廣度優(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用來(lái)發(fā)現(xiàn)運(yùn)動(dòng)軌跡的歷史頻繁項(xiàng)并生成預(yù)測(cè)模型.此外，Monreale等人[2]提出的WhereNext方法也不失為一種好的方法，該算法從歷史軌跡中提取具有幾種不同運(yùn)動(dòng)行為的運(yùn)動(dòng)模式，進(jìn)而生成預(yù)測(cè)模型.

馬爾可夫模型對(duì)軌跡序列建模中，有一些比較新的成果，比如Figueiredo等人[7]，他們使用不穩(wěn)定，瞬態(tài)且時(shí)間多樣化的軌跡序列，構(gòu)造出一種非參數(shù)模型用來(lái)對(duì)軌跡位置等做出預(yù)測(cè).文獻(xiàn)[9]使用了一種HITS-based模型來(lái)挖掘用戶軌跡興趣點(diǎn)，側(cè)重于分析軌跡全局的運(yùn)動(dòng)模式.

總的來(lái)說(shuō)，現(xiàn)有工作大多是依據(jù)大量移動(dòng)對(duì)象軌跡的重合部分，挖掘出軌跡相似行為，再用來(lái)做預(yù)測(cè).這種方式的缺點(diǎn)是：著重考慮表面發(fā)生的行為，對(duì)于事物內(nèi)在的隱含信息的考慮有所欠缺.

由于移動(dòng)物體產(chǎn)生的軌跡數(shù)據(jù)量比較大，而且這樣的數(shù)據(jù)還在不斷地增長(zhǎng)，因而對(duì)于以上兩種方法，模型的訓(xùn)練成本非常大.本文基于此原因，提出一種基于聚類分區(qū)域的隱馬爾可夫模型，經(jīng)過(guò)大量GPS數(shù)據(jù)的訓(xùn)練，得出最佳模型參數(shù)，最后通過(guò)隱狀態(tài)之間的轉(zhuǎn)移矩陣預(yù)測(cè)移動(dòng)對(duì)象軌跡最終位置.

3 聚類分區(qū)域的隱馬爾可夫模型

3.1 隱馬爾可夫模型(HMM)

馬爾可夫模型中，狀態(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)可能輸出的不同可觀察符號(hào)的數(shù)目M

3)狀態(tài)轉(zhuǎn)移矩陣A={aij}，其中，

aij=P(qt=sj|qt-1=si)，1≤i，j≤N

aij≥0

4)可觀測(cè)事件概率分布矩陣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一般來(lái)說(shuō)可以用以一個(gè)三元組來(lái)描述，μ=(A，B，π)，A為狀態(tài)轉(zhuǎn)移概率，B為符號(hào)發(fā)射概率，π為初始狀態(tài)概率分布.當(dāng)一些現(xiàn)象產(chǎn)生是由于某些事物本質(zhì)變化做決定時(shí)，用HMM進(jìn)行建模一般是非常有用的.因?yàn)镠MM能夠“深刻理解”事物的變化規(guī)律.HMM三個(gè)基本問(wèn)題及其解決方法如下：

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ǔ)言處理研究中有著非常廣泛的應(yīng)用，尤其是在語(yǔ)音識(shí)別領(lǐng)域，一段語(yǔ)音可以作為觀測(cè)序列，語(yǔ)音對(duì)應(yīng)的文字作為隱狀態(tài)，語(yǔ)音識(shí)別的首要任務(wù)就是求出最有可能發(fā)出該語(yǔ)音序列的隱狀態(tài)，將語(yǔ)音恢復(fù)成文字.通過(guò)一部分可觀測(cè)序列，可以預(yù)測(cè)對(duì)應(yīng)的隱狀態(tài)序列，基于此，本文將HMM模型移植到時(shí)空軌跡序列預(yù)測(cè)的問(wèn)題中.將大樣本時(shí)空軌跡序列，作為HMM的可觀測(cè)序列，將局部的時(shí)空坐標(biāo)點(diǎn)看成是附近某個(gè)隱狀態(tài)所發(fā)射出的觀測(cè)值，該隱狀態(tài)可以視為該局部區(qū)域的地標(biāo)點(diǎn).如圖2所示.

圖2 隱狀態(tài)及觀測(cè)值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ā)射出的觀測(cè)點(diǎn)，即它們服從A的發(fā)射概率分布.本文的任務(wù)之一就是要建立這樣的HMM模型，模型訓(xùn)練完成之后，輸入要預(yù)測(cè)終點(diǎn)的一段時(shí)空軌跡序列，即為觀測(cè)序列，然后通過(guò)相應(yīng)的算法求解出最佳隱狀態(tài)序列，通過(guò)隱狀態(tài)序列最后一個(gè)狀態(tài)以及轉(zhuǎn)移矩陣，計(jì)算出概率最大的下一個(gè)隱狀態(tài)，再根據(jù)該隱狀態(tài)的發(fā)射概率分布計(jì)算出最有可能的發(fā)射值即為預(yù)測(cè)的終點(diǎn).整個(gè)流程如圖3所示.

3.2 聚類分區(qū)域的隱馬爾可夫模型——CSHMM

HMM模型常用來(lái)進(jìn)行語(yǔ)音識(shí)別，一段語(yǔ)音的音節(jié)數(shù)量是很少的，一般是幾十個(gè)，這樣的數(shù)量級(jí)，采用維特比算法來(lái)求解隱狀態(tài)，即推斷語(yǔ)音對(duì)應(yīng)的文字或單詞，算法的執(zhí)行時(shí)間是非?？焖俚?其原因是維特比算法的時(shí)間復(fù)雜度是O(N2T)，其中N為發(fā)射出來(lái)的可觀測(cè)點(diǎn)的數(shù)目，T為狀態(tài)序列的長(zhǎng)度.由于車輛一般都是往一個(gè)大致的方向行駛(一般不會(huì)存在繞著整個(gè)城市或局部區(qū)域反復(fù)行駛)，因而一條完整的行駛路徑所穿過(guò)的地標(biāo)區(qū)域個(gè)數(shù)是比較少的，因而用維特比算法也是很快可以計(jì)算出最佳隱狀態(tài)序列.然而整個(gè)城市的所有地標(biāo)區(qū)域是非常多的，比如商場(chǎng)，運(yùn)動(dòng)場(chǎng)，小公園，小吃街等，實(shí)際上任何地方都可能成為車輛停止的終點(diǎn).因?yàn)闀r(shí)空序列終點(diǎn)的預(yù)測(cè)精度只要精確到一定的范圍內(nèi)即可，因此所有隱狀態(tài)的數(shù)量就非常多了，可能會(huì)有幾萬(wàn)甚至幾十萬(wàn)個(gè).如果針對(duì)整個(gè)城市建立一個(gè)含有如此龐大數(shù)量隱狀態(tài)的隱馬爾可夫模型(尤其是北上廣深這樣的特大城市)，那么在用維特比算法求解隱狀態(tài)序列時(shí)，遞歸算法將會(huì)非常耗時(shí)，甚至很可能導(dǎo)致程序直接奔潰.本文針對(duì)該情形，設(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)集合.

一般來(lái)說(shuō)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ù)量級(jí)相當(dāng).在此我們采用坐標(biāo)點(diǎn)的數(shù)量來(lái)代替區(qū)域面積，可以對(duì)此建立一個(gè)線性模型(也可以是非線性模型)來(lái)確定每個(gè)區(qū)域內(nèi)的大致坐標(biāo)點(diǎn)數(shù)目.本文采用一種改進(jìn)型的kmean——kmeans_cs如下函數(shù)模型來(lái)判定每個(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)的距離越近，則會(huì)有一個(gè)大于1的權(quán)重乘進(jìn)去使其增大.如果距離越大，那么乘上的權(quán)重會(huì)以指數(shù)增大，使得距離增加的更快.這樣會(huì)使得聚類的結(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ā)射符號(hào)集.

直觀表示如圖5所示.

圖5 隱狀態(tài)和觀測(cè)值的映射Fig.5 Mapping of hidden states and observation values

如圖4所示，首先通過(guò)聚類算法將城市中的所有地標(biāo)點(diǎn)進(jìn)行聚類，以此將全局區(qū)域分成若干個(gè)小區(qū)域，然后針對(duì)每個(gè)小區(qū)域，進(jìn)行HMM建模.模型建立完成以后，根據(jù)輸入的待預(yù)測(cè)的部分GPS軌跡，首先進(jìn)行區(qū)域匹配，選出最佳HMM模型，然后使用維特比算法針對(duì)該模型進(jìn)行預(yù)測(cè).

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軌跡跨越盡可能少.本文針對(duì)GPS軌跡的變化規(guī)律設(shè)計(jì)了一種改進(jìn)的k-means聚類算法，傳統(tǒng)的k-means算法采用歐氏距離來(lái)判斷點(diǎn)和點(diǎn)之間的類似程度，此方式會(huì)打破GPS軌跡坐標(biāo)的連貫性，即會(huì)大量出現(xiàn)同一條軌跡存在于多個(gè)子區(qū)域中，這是不符合要求的，因?yàn)楸疚男枰诿總€(gè)子區(qū)域單獨(dú)求解HMM模型，每個(gè)模型模擬了一個(gè)特定子區(qū)域GPS軌跡模式.基于該目的，本文提出一種能夠按照GPS軌跡來(lái)聚類的算法，該算法改進(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ù)來(lái)作為權(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為迭代序號(hào).

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ì)算完畢.

3.3 分區(qū)域進(jìn)行HMM的模型訓(xùn)練

對(duì)于每個(gè)子區(qū)域，其所有的地標(biāo)數(shù)據(jù)已經(jīng)確定，每個(gè)地標(biāo)周圍的稱為發(fā)射符號(hào)集的GPS坐標(biāo)點(diǎn)也已經(jīng)確定.已知的信息量比較充足，比如可以根據(jù)每個(gè)GPS坐標(biāo)的出現(xiàn)頻率，計(jì)算出發(fā)射概率矩陣B0.也可以根據(jù)大量軌跡來(lái)計(jì)算地標(biāo)與地標(biāo)之間的轉(zhuǎn)移概率，從而計(jì)算出轉(zhuǎn)移矩陣A0.

Baum-Welch算法是一種EM算法，專門用來(lái)訓(xùn)練HMM模型.EM過(guò)程保證算法一定能夠收斂到一個(gè)局部最優(yōu)點(diǎn)，但是它不能保證找到全局的最優(yōu)點(diǎn).所以Baum-Welch算法不能保證找到全局的最優(yōu)模型.但是由于我們已經(jīng)知道了大致的解：狀態(tài)轉(zhuǎn)移矩陣A0和發(fā)射概率矩陣B0，如果將它們作為迭代的初始值，那么會(huì)有很大的概率收斂到全局最優(yōu)點(diǎn)，并且訓(xùn)練的時(shí)間也大大減小.本文采用的Baum-Welch算法.

對(duì)于給定的隱馬爾可夫模型(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)收斂.

3.4 使用模型進(jìn)行預(yù)測(cè)

對(duì)于給定的部分GPS軌跡序列，根據(jù)最后一個(gè)坐標(biāo)的位置，確定相應(yīng)的子區(qū)域，選取相應(yīng)子區(qū)域的HMM模型.將不在該子區(qū)域內(nèi)的坐標(biāo)點(diǎn)切除.使用靠近尾部的坐標(biāo)點(diǎn)作為可觀測(cè)序列.問(wèn)題就變成了HMM模型的第二個(gè)問(wèn)題.因此本文采用維特比算法來(lái)求隱狀態(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è)概率最大的可觀測(cè)坐標(biāo)點(diǎn)Pnext.求法如下：

(9)

其中l(wèi)ast為當(dāng)前時(shí)刻，next為下一時(shí)刻.

4 實(shí)驗(yàn)與分析

本文使用的數(shù)據(jù)集為T-Drive Trajectory data sample，來(lái)自微軟亞洲研究院(MSR)，一共有10357個(gè)北京出租車在一周內(nèi)的GPS軌跡，每條軌跡提取出包含經(jīng)緯度和時(shí)間戳信息的子信息.實(shí)驗(yàn)選區(qū)75%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集，25%的數(shù)據(jù)作為測(cè)試數(shù)據(jù)集.代碼使用python語(yǔ)言，硬件配置為 Intel(R) Core(TM) i5-3320 2.60GHZ，12.0GB內(nèi)存，320GB硬盤的計(jì)算機(jī).

實(shí)驗(yàn)結(jié)果采用準(zhǔn)確率，召回率為評(píng)估標(biāo)準(zhǔn).

4.1 本文模型使用kmeans和改進(jìn)型kmeans結(jié)果對(duì)比

結(jié)果如圖6所示(準(zhǔn)確率和召回率為改進(jìn)kmeans后的結(jié)果，準(zhǔn)確率2和召回率2為不使用改進(jìn)的kmeanss).

圖6 kmeans和改進(jìn)型kmeans對(duì)模型效果的影響Fig.6 Effect of kmeans and improved kmeans on the model effect

結(jié)果分析：改進(jìn)kmeans后的算法導(dǎo)致模型準(zhǔn)確率和召回率提高了15%左右，說(shuō)明改進(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)移概率的增大，因而會(huì)有更優(yōu)秀的準(zhǔn)確率.

4.2 本文模型和其他模型對(duì)比

結(jié)果如圖7所示(準(zhǔn)確率和召回率為改進(jìn)kmeans后的結(jié)果，準(zhǔn)確率3和召回率3為使用Apriori算法的結(jié)果，橫坐標(biāo)單位：萬(wàn)條數(shù)據(jù)，縱坐標(biāo)單位：百分比).

圖7 本文模型和其他模型性能對(duì)比Fig.7 Comparison of the performance of this model and other models

結(jié)果分析：改進(jìn)kmeans后的算法導(dǎo)致模型準(zhǔn)確率和召回率提高了8%左右.對(duì)比傳統(tǒng)關(guān)聯(lián)模式挖掘的算法，本文算法具有一定的優(yōu)勢(shì).說(shuō)明基于轉(zhuǎn)移概率的方式與挖掘時(shí)空序列軌跡相似度的方式相比，前者將一些影響軌跡趨勢(shì)的別的特征也考慮進(jìn)了模型中(即使沒(méi)有提取相關(guān)特征)，因而會(huì)提高準(zhǔn)確度.

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

本文基于隱馬爾可夫模型，提出了一種預(yù)測(cè)移動(dòng)對(duì)象下一個(gè)位置的方法—基于聚類分區(qū)域的時(shí)空軌跡預(yù)測(cè)模型，該方法用以解決時(shí)空軌跡序列的預(yù)測(cè)問(wèn)題.該模型首先通過(guò)聚類將一片區(qū)域內(nèi)的時(shí)空序列分成多個(gè)小區(qū)域，每個(gè)小區(qū)域內(nèi)再通過(guò)聚類確定多個(gè)隱狀態(tài)和發(fā)射序列，然后針對(duì)每個(gè)小區(qū)域進(jìn)行隱馬爾可夫模型的訓(xùn)練得出最終模型.預(yù)測(cè)時(shí)通過(guò)已知的時(shí)空序列，找到對(duì)應(yīng)的區(qū)域模型，通過(guò)維特比算法計(jì)算出最佳隱狀態(tài)序列，再結(jié)合轉(zhuǎn)移矩陣做出下一個(gè)軌跡點(diǎn)的預(yù)測(cè)，實(shí)驗(yàn)表明該方法在一定程度上提高了預(yù)測(cè)準(zhǔn)確率.

未來(lái)的工作中，可以使用機(jī)器學(xué)習(xí)或者深度學(xué)習(xí)的方式進(jìn)一步提高區(qū)域的劃分算法和軌跡聚類算法.