基于出行方式及語義軌跡的位置預(yù)測模型

章靜蕾 石海龍 崔 莉

1(中國科學(xué)院計算技術(shù)研究所 北京 100190)2(中國科學(xué)院大學(xué) 北京 100049)

近年來，隨著GPS數(shù)據(jù)、LBS地理位置信息方便被獲得后，基于地理位置的服務(wù)也深受用戶的喜愛，這些服務(wù)程序通常都是利用用戶行徑的歷史地理位置信息來為用戶提供更方便、有效的服務(wù).有效的LBS服務(wù)不僅能夠提前告知用戶下一個位置的具體位置點，同時還能表示此位置的語義信息，如學(xué)校、超市、公寓等.這對用戶的行為活動計劃有所幫助，也提前給用戶的興趣偏好產(chǎn)生一定的影響.

位置預(yù)測技術(shù)就是通過獲取GPS軌跡數(shù)據(jù)，并對用戶日常行為活動和其日常的出行規(guī)律進(jìn)行分析，根據(jù)此分析結(jié)果結(jié)合用戶的歷史軌跡信息對下一個位置進(jìn)行預(yù)測.而只根據(jù)用戶當(dāng)前位置的地理信息并不能達(dá)到優(yōu)質(zhì)的效果，如圖1所示，給出了用戶的3條GPS軌跡的例子.

Fig. 1 An example of user’s location trajectory圖1 用戶位置軌跡示例

圖1中，按照地理位置軌跡分析，軌跡2和軌跡3離得更近.因此，在對軌跡2進(jìn)行位置預(yù)測時，基于地理位置軌跡的相似度，得到的結(jié)果會偏向于軌跡3.因此，只考慮地理位置信息進(jìn)行預(yù)測用戶的軌跡位置可能并不會達(dá)到令人滿意的結(jié)果.因此需要結(jié)合基于語義軌跡的挖掘來進(jìn)行輔助.這3條軌跡由位置所對應(yīng)的語義信息所組成，如公寓、公園、便利店、學(xué)校等.由圖1所知，軌跡1和軌跡2均為公寓，學(xué)校，便利店，隱含著軌跡1和軌跡2從語義上才是相似的.因此將用戶有相似行為活動規(guī)律通過語義軌跡表示出來，不僅能將沒有訪問過的位置加入考慮之中，同時也結(jié)合用戶行為活動對位置進(jìn)行預(yù)測.

另外盡管目前在對位置預(yù)測的問題中，不少研究也結(jié)合多方面因素進(jìn)行考慮，比如對軌跡中的2個興趣點之間的路徑進(jìn)行預(yù)測，并結(jié)合路徑對位置預(yù)測結(jié)果進(jìn)行提升，或者結(jié)合用戶之前沒有訪問過的地理位置信息對用戶的位置進(jìn)行預(yù)測等，然而目前研究沒有加入用戶的出行方式的因素.眾所周知，當(dāng)用戶進(jìn)行戶外行為活動時，根據(jù)其自身的行為偏好在興趣點之間進(jìn)行轉(zhuǎn)移時，不可避免需要進(jìn)行出行方式的選擇，因此出行方式同樣也反映出用戶外出的行為規(guī)律，這對位置的選擇和偏好也產(chǎn)生重要的影響.因此在對用戶軌跡數(shù)據(jù)進(jìn)行挖掘信息時，我們不僅要考慮位置軌跡所蘊含的語義信息，同時也要結(jié)合用戶的出行方式來挖掘用戶行為活動有助于提高位置預(yù)測技術(shù).

因此，本文提出一種結(jié)合軌跡信息數(shù)據(jù)及出行方式的未來位置預(yù)測模型，該模型分為2部分:1)在軌跡信息數(shù)據(jù)挖掘方面，本文首先通過對軌跡數(shù)據(jù)進(jìn)行分析，設(shè)計實現(xiàn)一種同時結(jié)合語義軌跡和位置軌跡模式的組合模型，即通過對語義軌跡和位置軌跡的頻繁模式挖掘得到相應(yīng)的頻繁軌跡集合，并對目標(biāo)軌跡分別進(jìn)行匹配得到預(yù)測結(jié)果的位置候選集.2)通過對軌跡數(shù)據(jù)和用戶的出行方式進(jìn)行分析，設(shè)計實現(xiàn)一種結(jié)合用戶出行方式和軌跡頻繁模式的模型，即根據(jù)用戶歷史軌跡序列和歷史出行方式序列建立模型預(yù)測得到未來位置結(jié)果候選集.最后根據(jù)2部分的結(jié)果候選集得到用戶最終的未來位置.

本文的主要貢獻(xiàn)有2個方面：

1) 提出一種同時結(jié)合語義軌跡和位置軌跡的位置預(yù)測算法，該算法根據(jù)語義軌跡進(jìn)行相似用戶的挖掘，并結(jié)合個人的語義軌跡和相似用戶的位置軌跡對未來位置結(jié)果進(jìn)行預(yù)測.

2) 提出一種結(jié)合用戶出行方式的位置預(yù)測算法，根據(jù)用戶軌跡和歷史出行方式建立Markov模型，對用戶的未來出行方式進(jìn)行預(yù)測.

最后結(jié)合這2個部分的結(jié)果得到最后預(yù)測的位置結(jié)果.

1 相關(guān)工作

近年來，隨著基于地理位置信息的服務(wù)技術(shù)的發(fā)展，與此相關(guān)的服務(wù)也在迅速發(fā)展，如導(dǎo)航路徑服務(wù)、交通流量擁塞管理、城市計算服務(wù)或者基于位置的廣告投放服務(wù)等.而在這些服務(wù)當(dāng)中，都是普遍基于未來位置預(yù)測技術(shù)之上產(chǎn)生的.

關(guān)于位置預(yù)測技術(shù)的研究，目前也有大批研究者對此進(jìn)行深入的探索并取得一定的成績.Chen等人[1]提出一種基于Markov模型的位置預(yù)測算法，對用戶的軌跡位置進(jìn)行挖掘，并考慮當(dāng)前時刻位置對未來位置的影響，由此對用戶的未來位置進(jìn)行預(yù)測.Yang等人[2]提出一種層次聚類的挖掘算法并使用一階Markov模型對位置進(jìn)行預(yù)測.然而該方法具有一定的限制性，即數(shù)據(jù)源是個人的歷史位置數(shù)據(jù)，因此模型也只適用于個人的行為活動挖掘，而不具有較強的泛化能力，不具有普適性.Monreale等人[3]提出一種新的方法對位置預(yù)測技術(shù)進(jìn)一步研究，該方法同時考慮位置的訪問順序、用戶訪問某個興趣點位置的訪問度和逗留該位置的時長3個因素，對位置進(jìn)行較高精確度的預(yù)測.

除了在使用用戶的歷史軌跡數(shù)據(jù)進(jìn)行挖掘來對未來位置進(jìn)行預(yù)測之外，部分研究者認(rèn)為只靠用戶的軌跡數(shù)據(jù)并不能對提高位置預(yù)測的精確度進(jìn)行更高的提升，因此需要引入額外的外源數(shù)據(jù)來輔助預(yù)測結(jié)果的精度，如社交網(wǎng)絡(luò)關(guān)系、歷史軌跡的路徑長度、不同地區(qū)的分布狀態(tài)、路徑道路的擁塞程度、事故報道和司機的駕駛習(xí)慣[4-7]等.類似地，研究者還會引入文本信息作為外源數(shù)據(jù)，如具有周期性階段的時間段和相應(yīng)的位置信息可以作為重要因素列入模型訓(xùn)練過程中[8].因此在對位置預(yù)測方面，我們不僅可以從大量的軌跡數(shù)據(jù)中提取有用的信息，同時也可以結(jié)合用戶行為活動中產(chǎn)生的外源數(shù)據(jù)作為輔助來提高位置預(yù)測結(jié)果的精確度.

2 TransPredict算法概述

本文分別引入語義軌跡模式挖掘和出行方式序列2個部分對未來位置進(jìn)行預(yù)測，總體描述流程如圖2所示.該框架主要包括結(jié)合語義軌跡和位置軌跡進(jìn)行頻繁模式挖掘、結(jié)合出行方式和位置軌跡進(jìn)行未來位置預(yù)測這2個模塊組成.

Fig. 2 The flow diagram for location prediction圖2 位置預(yù)測總框架圖

在語義軌跡模式挖掘模塊中，我們首先對所有用戶的歷史軌跡數(shù)據(jù)進(jìn)行處理，對由GPS點組成的軌跡挖掘出停留點(stay point)進(jìn)行軌跡分段；再對停留點進(jìn)行聚類得到興趣點位置軌跡，得到位置軌跡序列.通過對位置軌跡進(jìn)行語義化，將位置信息標(biāo)識成語義信息并得到語義軌跡，根據(jù)個人用戶的語義軌跡進(jìn)行頻繁模式挖掘，得到語義頻繁軌跡集合并建立相應(yīng)的語義模式樹.根據(jù)之前得到的語義軌跡，進(jìn)行聚類挖掘具有相似行為活動的用戶.由于只根據(jù)語義軌跡并不能得到具體預(yù)測未來位置的地理信息，因此需要結(jié)合位置軌跡數(shù)據(jù)來處理.由此，對相同簇內(nèi)所有用戶的位置軌跡集合挖掘頻繁模式集合，并建立相應(yīng)的位置軌跡樹.最后當(dāng)對用戶的目標(biāo)軌跡進(jìn)行預(yù)測時，將其與位置模式樹的路徑匹配得到候選軌跡集合及其位置得分，接著將候選軌跡路徑語義化后與語義模式樹進(jìn)行匹配，得到相應(yīng)的語義得分，根據(jù)兩者的得分加權(quán)獲得依據(jù)得分高低排序相應(yīng)的候選軌跡集合，候選軌跡下一個位置就是未來位置預(yù)測的結(jié)果.由此，結(jié)合語義軌跡和位置軌跡進(jìn)行預(yù)測時，不僅考慮其用戶自身歷史軌跡信息，同時考慮與其有相似行為活動用戶的軌跡信息對未來位置進(jìn)行預(yù)測.

在結(jié)合出行方式位置預(yù)測模塊中，給定用戶的歷史出行方式集合，將其轉(zhuǎn)化成出行方式序列，并結(jié)合目標(biāo)軌跡數(shù)據(jù)提取特征建立模型對未來出行方式進(jìn)行識別，然后結(jié)合目標(biāo)軌跡序列及其對應(yīng)的出行方式序列，建立Markov模型對未來位置進(jìn)行預(yù)測，得到由位置候選集及其相應(yīng)的概率值，最后結(jié)合其候選集和由語義軌跡模式挖掘模塊中得到的位置候選集選擇具有高得分高概率的位置作為最終的預(yù)測結(jié)果.

3 TransPredict算法設(shè)計與實現(xiàn)

3.1 基于語義及位置的頻繁模式挖掘

本節(jié)研究內(nèi)容是得到用戶的軌跡后，對多用戶的頻繁軌跡路徑進(jìn)行挖掘，同時結(jié)合常去位置的興趣度得到興趣點挖掘，結(jié)合兩者挖掘獲得用戶群體的日常行為規(guī)律.因此本節(jié)需要對不同用戶軌跡路徑進(jìn)行頻繁模式挖掘，并對目標(biāo)用戶軌跡進(jìn)行未來位置的預(yù)測.因此我們將先對軌跡語義化得到語義軌跡，并進(jìn)行相似用戶挖掘得到相應(yīng)的語義軌跡樹；然后對相似用戶的位置軌跡進(jìn)行頻繁模式挖掘得到位置軌跡集合，建立相應(yīng)的位置軌跡樹；最后對目標(biāo)軌跡結(jié)合語義模式集合和位置模式集合進(jìn)行相應(yīng)的路徑匹配，得到未來位置預(yù)測結(jié)果.

3.1.1 語義軌跡的頻繁模式挖掘

在得到每個用戶的位置軌跡點后，首先對位置軌跡進(jìn)行語義映射并得到語義軌跡，具體算法過程見圖3所示:

Fig. 3 Frequent pattern mining based on semantic trajectory圖3 基于語義軌跡的頻繁模式挖掘

基于語義軌跡的頻繁模式挖掘算法的整體流程步驟：

1) 在獲得每個用戶的軌跡數(shù)據(jù)后，首先對每個點進(jìn)行停留點(stay point)的挖掘，即根據(jù)半徑和時間范圍進(jìn)行挖掘.在獲得stay point后，使用基于密度的聚類算法K-means進(jìn)行位置點的聚類，得到興趣點的挖掘.由此位置軌跡由這些興趣點位置所表示.

2) 對于得到由興趣點表示的軌跡后，將這些興趣點進(jìn)行語義化，即調(diào)用Openstreet API對位置點進(jìn)行語義標(biāo)識.由此不僅得到語義軌跡，同時得到位置的POI語義信息集合.

3) 對各個用戶的軌跡集使用PrefixSpan算法進(jìn)行序列頻繁模式的挖掘，即將語義軌跡挖掘出頻繁模式，得到頻繁語義軌跡集合.

4) 對挖掘的頻繁語義軌跡集合建立前綴樹，由此得到每個用戶的語義模式樹，用于對目標(biāo)軌跡進(jìn)行路徑匹配.

5) 對于每個用戶，使用MSTP軌跡相似度算法進(jìn)行兩兩比較，根據(jù)此來進(jìn)行用戶的層次聚類，最后得到基于相似語義路徑的用戶.

因此該算法可由以上5個部分所得.接下來將對算法的具體過程進(jìn)行展開介紹：

1) 語義軌跡的表示

根據(jù)GPS所表示的經(jīng)緯度和時間戳代表的位置點組成的軌跡，我們采用文獻(xiàn)[9]中的方法進(jìn)行停留點的挖掘，然后選擇基于K-means的聚類方法進(jìn)行興趣點的挖掘，由于該算法聚類得到的范圍一般都是以圓圈為主，因此符合一個真實位置范圍.由此GPS點組成的軌跡可表示成興趣點位置軌跡.

對于得到的用戶軌跡數(shù)據(jù)，我們對其進(jìn)行語義標(biāo)識的映射.對于興趣點位置，將其語義化標(biāo)識成語義軌跡，并將語義組成語義集合.如圖4中的3條軌跡，可以進(jìn)行語義化得到軌跡位置的語義標(biāo)識，并得到相應(yīng)的語義軌跡，如表1所示.

Fig. 4 An example of semantic trajectory圖4 語義軌跡示圖

Trajectory Location TrajectorySemantic TrajectoryTrajectory1Location1,Location2,Location4,Location5Apartment,School,Coffee House,SupermarketTrajectory2Location1,Location2,Location5Apartment,School,SupermarketTrajectory3Location1,Location3,Location4Apartment,Park,Supermarket

在將每個軌跡由位置軌跡轉(zhuǎn)換成語義軌跡后，每個用戶就有自己的語義軌跡集合.雖然每個用戶由于自身的興趣偏好不同，導(dǎo)致軌跡位置不一樣，但是不可否認(rèn)存在相似偏好的用戶，他們的主要行為是相同的.比如如果用戶是學(xué)生群體，那么他們白天的軌跡基本都是從家里到學(xué)校之間的軌跡路徑；如果是上班族，那么他們的軌跡基本是從家里到公司，可能也會途徑超市等地方.因此具有相似偏好的用戶群體能夠根據(jù)他們的語義軌跡被挖掘出來.

2) 語義頻繁模式挖掘

為了獲得用戶的頻繁行為活動，首先需要對用戶的語義軌跡進(jìn)行挖掘，除掉偶爾經(jīng)過興趣點，從語義上來挖掘其頻繁路徑.這里將采用PrefixSpan[10]算法來對用戶的每條語義軌跡進(jìn)行挖掘找到頻繁語義軌跡.由于該算法是對序列模式進(jìn)行挖掘，而軌跡在經(jīng)過每個語義位置的前后順序也非常重要，這也符合對具有序列形式的軌跡挖掘，因此將采用該方法來執(zhí)行.

對于語義軌跡模式，可以提供不同的規(guī)則來定義預(yù)測的方式.比如對于公寓，學(xué)校，便利店這個頻繁語義軌跡，我們可以得到當(dāng)用戶經(jīng)過公寓并到達(dá)學(xué)校后，可以預(yù)測他的下一個語義位置是便利店.然而越長的頻繁語義軌跡，它包含的頻繁子序列也越多.因此當(dāng)一個頻繁序列是以上語義序列時，則對應(yīng)的頻繁子序列分別為公寓，學(xué)校，便利店，公寓，學(xué)校，公寓，便利店，學(xué)校，便利店.

3) 語義軌跡模式樹的建立

當(dāng)對用戶的當(dāng)前位置和其語義軌跡逐個進(jìn)行匹配是非常耗時的，所以這邊為了能夠更有效且快速地進(jìn)行位置預(yù)測，將采用前綴樹的匹配算法實現(xiàn)，即建立語義軌跡樹 (semantic trajectory tree, STraj-Tree)來代表語義軌跡的集合.語義軌跡模式樹的建立過程參考文獻(xiàn)[11]所示.對于表1中由位置軌跡語義化后得到的語義軌跡集合可以挖掘相應(yīng)的語義軌跡頻繁模式.假設(shè)設(shè)置PrefixSpan的最小支持度為0.5，則滿足其支持度的所有頻繁模式如表2所示:

Table 2 The Frequent Trajectory in Semantic Trajectory Set表2 頻繁語義軌跡集合

Fig. 5 Semantic trajectory tree with support of its node圖5 語義軌跡樹及其節(jié)點支持度

圖5表示頻繁語義軌跡集合對應(yīng)的語義軌跡樹STraj-Tree.可以注意到樹的每個枝代表的就是一條頻繁的語義路徑，而該枝也同時包含許多頻繁路徑.如其中的路徑(公寓,1.0)→(學(xué)校,0.667)→(便利店,0.667)同時包含很多語義軌跡模式路徑，即公寓,學(xué)校,便利店,公寓，學(xué)校,公寓，便利店和學(xué)校，便利店.因此可以說軌跡模式樹是對語義軌跡模式集合的一種壓縮式集合形式.如果前綴樹中一條枝包含多個頻繁路徑，則該枝條路徑的支持度選擇所有頻繁路徑支持度中的最大值.另外，對于只有一個位置點的頻繁路徑，則從軌跡模式數(shù)中剔除，因為它對于預(yù)測位置沒有任何幫助.

4) 基于語義的相似用戶挖掘

在對軌跡進(jìn)行分析時，我們發(fā)現(xiàn)即使2條軌跡在位置上相似，但是若位置語義不同，預(yù)測的結(jié)果精確度不高，說明語義所帶的指示性含義要比實際位置軌跡所代表的含義更深刻.基于語義軌跡分析，我們發(fā)現(xiàn)相似語義軌跡的用戶，其也具有相似的興趣偏好.因為當(dāng)用戶的頻繁行為活動在語義上更具有相似性時，他們的下一個位置的預(yù)測結(jié)果不僅關(guān)聯(lián)該用戶自身的行為模式，同時也關(guān)聯(lián)具有相似語義行為的其他用戶，因此我們可以根據(jù)相似語義軌跡對相似行為偏好的用戶進(jìn)行聚類.

在對相似用戶進(jìn)行聚類時，我們需要對用戶的語義軌跡進(jìn)行相似度的衡量.首先采用最長公共子序列算法對不同軌跡得到公共相似序列，并用最大語義軌跡模式相似 (maximal semantic trajectory pattern similarity, MSTP-Similarity) 算法[12]來將公共序列和軌跡進(jìn)行相似度的計算，那么對于計算2個用戶的相似度，就是將2個用戶分別對軌跡進(jìn)行笛卡兒積式匹配計算，兩兩軌跡分別進(jìn)行計算，那么用戶的相似度就是其所有語義軌跡的相似度的平均值.由此可以來衡量2個用戶的相似性的程度.根據(jù)此相似度計算標(biāo)準(zhǔn)，最后用層次聚類算法對相似用戶進(jìn)行聚類，得到具有相似語義軌跡的用戶集合.

3.1.2 位置軌跡的頻繁模式挖掘

將語義軌跡模型建立后，由于預(yù)測得到的只能是位置語義信息，而不能得到具體位置坐標(biāo)，因此我們需要進(jìn)行地理位置信息的挖掘并建立頻繁位置軌跡模型.該算法具體過程如圖6所示.

由圖6看出，對位置軌跡進(jìn)行頻繁模式挖掘且模型建立的過程有4個步驟：

① 對于根據(jù)語義信息聚類后的用戶，對同簇中的相似用戶的位置軌跡合并；

② 對同簇中的位置軌跡，使用PrefixSpan算法進(jìn)行序列頻繁模式挖掘，得到頻繁位置軌跡集合；

Fig. 6 Frequent pattern mining based on location trajectory圖6 基于位置軌跡的頻繁模式挖掘

③ 對挖掘的頻繁位置軌跡模式建立Prefix-Tree前綴樹，同樣形成了位置軌跡樹；

④ 根據(jù)目標(biāo)軌跡對位置軌跡樹進(jìn)行路徑匹配并計算位置軌跡得分.

1) 位置軌跡頻繁模式挖掘

根據(jù)語義軌跡進(jìn)行相似用戶聚類之后，得到具有相似行為活動的用戶簇.在通過對用戶簇中所有軌跡的興趣點進(jìn)行聚類統(tǒng)一后，我們需要對頻繁的位置軌跡模式挖掘，挖掘出這些相似用戶實際位置的相似程度.同樣，采用PrefixSpan算法對位置軌跡進(jìn)行頻繁模式挖掘.比如，假設(shè)對表1中的3條位置軌跡進(jìn)行挖掘，設(shè)最小支持度為0.5，則可以得到相應(yīng)的頻繁位置軌跡有位置1，位置2，位置5，位置1，位置4.對于這些頻繁位置軌跡，可以得到相應(yīng)的支持度，具體如表3所示:

Table 3 The Frequent Trajectory in Location Trajectory Set表3 頻繁位置軌跡集合

2) 位置軌跡模式樹的建立

在對位置軌跡集合進(jìn)行頻繁模式挖掘后，得到頻繁的位置軌跡集合.同樣建立相應(yīng)的位置軌跡樹 (location trajectory tree， LTraj-Tree)來代表位置軌跡的集合.如圖7所示，軌跡樹的每條路徑就是頻繁子序列軌跡，路徑上的每一個節(jié)點代表興趣點位置序號和支持度.

Fig. 7 Location trajectory tree with support ofits node圖7 位置軌跡樹及其節(jié)點支持度

圖7所示為根據(jù)表3中的頻繁位置軌跡集合建立的位置軌跡樹.對于一條路徑上包含的多個位置軌跡，將進(jìn)行重疊處理，如果經(jīng)過某個節(jié)點上的路徑有多條，則選擇支持度最大的路徑作為該位置的支持度.同樣，由于只有一個節(jié)點的路徑并不能對位置預(yù)測提供幫助，因此將取消其路徑.

3.1.3 位置預(yù)測

當(dāng)給定用戶的軌跡數(shù)據(jù)后，我們不僅從軌跡語義上分析并得到用戶頻繁的行為路徑，同樣也從軌跡位置上分析得到相似用戶在實際位置行徑中的頻繁行為活動.由此得到基于個人軌跡建立的語義軌跡樹和基于相似行為用戶建立的位置軌跡樹.當(dāng)對目標(biāo)位置軌跡進(jìn)行位置預(yù)測時，我們將其對2棵軌跡樹進(jìn)行相應(yīng)的得分計算，最后對得分進(jìn)行加權(quán)得到相應(yīng)的匹配路徑集合，即:

Result_Score=α×Semantic_Score+ (1-α)×Location_Score,

(1)

其中,權(quán)值為ɑ，且滿足0<ɑ<1.這里L(fēng)ocation_Score表示當(dāng)前的路徑與位置軌跡樹的位置得分，Semantic_Score表示與語義軌跡樹進(jìn)行匹配得到的語義得分.我們首先進(jìn)行位置軌跡樹的得分計算，若大于0，則說明此路徑可作為候選路徑.由此對其轉(zhuǎn)換成相應(yīng)的語義路徑，并將此語義路徑與該用戶的語義軌跡樹進(jìn)行匹配得分，最后將兩者進(jìn)行加權(quán)得到相應(yīng)路徑的最后得分.另外，由于本模型是對具有語義軌跡聚類后的相同簇內(nèi)的用戶們的位置軌跡進(jìn)行建樹，因此若用戶為了隱私保護(hù)而關(guān)閉設(shè)備未獲取到位置信息，模型會挖掘該用戶其他時間段的軌跡信息的語義找到對應(yīng)的簇，當(dāng)對該用戶進(jìn)行預(yù)測時也會將其他用戶經(jīng)過的位置作為預(yù)測結(jié)果.因此若用戶出于隱私保護(hù)未上傳部分位置軌跡對模型不會造成重大影響.下面將對具體位置軌跡樹和語義軌跡樹得分的計算進(jìn)行介紹.

1) 位置軌跡樹得分

在得到當(dāng)前用戶的目標(biāo)軌跡位置點后，將其轉(zhuǎn)換成位置軌跡序列.另外由于該軌跡序列可能較長，因此在與位置軌跡模式樹進(jìn)行匹配時會耗時，我們采用半匹配算法[11]進(jìn)行匹配.

在對目標(biāo)軌跡T與位置軌跡樹路徑P的匹配進(jìn)行計算得分時，采用文獻(xiàn)[11]中的計算得分:

(2)

(3)

式(2)(3)表示在對目標(biāo)軌跡T和軌跡樹P進(jìn)行匹配時，首先從目標(biāo)軌跡T當(dāng)前位置開始(q=1)選取位置序列.其中β|T|-j表示離匹配位置越遠(yuǎn)的位置，其重要性越低.當(dāng)匹配Tj與Pi時，若相等，則將Pi的支持度作為匹配的得分Match_Score，最后根據(jù)目標(biāo)位置序列及軌技樹進(jìn)行匹配得到最后的得分.如圖8為匹配過程，假設(shè)路徑權(quán)值β=0.8，當(dāng)q=1時，用戶的位置軌跡序列為位置5，位置1，位置2，此時沒有與之匹配的路徑，因此得分為0.當(dāng)q=2時，位置軌跡序列為位置1，位置2，與模式樹的路徑(位置1,1.0)→(位置2,0.667)相匹配，因此相應(yīng)的得分為0.8×1.0+0.667.當(dāng)q=3時，位置軌跡序列與路徑(位置2，0.667)相匹配，因此得分為0.667.候選軌跡及相應(yīng)的得分計算如表4所示.由此就可以得到每條候選軌跡及相應(yīng)的地理位置得分，若該軌跡的得分為0，則去除該候選軌跡.

Fig. 8 The matching process of target path and LTraj-Tree圖8 目標(biāo)路徑與位置軌跡樹匹配過程

Candidate Location TrajectoryLocation ScoreLocation5,Location1,Location20Location1,Location20.8×1.0+0.667=1.467Location20.667

2) 語義軌跡樹得分

由于只根據(jù)地理位置的軌跡來進(jìn)行用戶的位置預(yù)測并不準(zhǔn)確，因此需要結(jié)合語義軌跡來進(jìn)行挖掘，因此在對目標(biāo)軌跡進(jìn)行分析時，也需要將其與語義軌跡樹進(jìn)行匹配得到相應(yīng)的語義得分.我們?nèi)匀徊捎冒肫ヅ渌惴ㄟM(jìn)行匹配得分.如圖9為例子，假設(shè)路徑權(quán)值β=0.8，則候選語義路徑為公寓，學(xué)校.當(dāng)q=1時，語義路徑公寓，學(xué)校與語義軌跡樹的路徑(公寓，1.0)→(學(xué)校，0.667)相匹配，因此相應(yīng)的語義得分為0.8×1.0+0.667.當(dāng)q=2時，語義軌跡與路徑(學(xué)校，0.667)相匹配，因此其相應(yīng)的得分為0.667.其計算語義得分的過程如表5所示.

Fig. 9 The matching process of target path and STraj-tree圖9 候選路徑與語義軌跡樹匹配過程

Candidate Semantic TrajectorySemantic ScoreSupermarket,Apartment,School0Apartment,School0.8×1.0+0.667=1.467School0.667

Fig. 10 The location prediction model with transportation mode圖10 結(jié)合出行方式的位置預(yù)測模型

最后，我們使用式(1)來對每條候選路徑進(jìn)行計算總的得分.根據(jù)表4和表5中的每條路徑的位置得分Location_Score和語義得分Semantic_Score，進(jìn)行加權(quán)并得到最后的得分結(jié)果.假設(shè)權(quán)值ɑ=0.7，則對應(yīng)候選路徑位置1，位置2的最后得分為0.7×1.467+0.3×1.467=1.467.而對于另一條候選路徑位置2的最后得分為0.7×0.667+0.3×0.667=0.667.因此我們可以得到得分最高的候選路徑為位置1，位置2.因此對于目標(biāo)路徑位置5，位置1，位置2，其要預(yù)測的位置結(jié)果即為候選路徑的子節(jié)點的位置值.而如果當(dāng)最高的候選路徑?jīng)]有下一個節(jié)點的話，就選得分排第2的候選路徑的子節(jié)點作為預(yù)測結(jié)果，以此類推.由此我們結(jié)合語義軌跡和位置軌跡來對目標(biāo)軌跡匹配并依據(jù)相應(yīng)得分得到位置預(yù)測的候選集.

3.2 基于出行方式及語義軌跡的位置預(yù)測

本研究內(nèi)容是在對軌跡位置進(jìn)行預(yù)測時，只考慮軌跡數(shù)據(jù)并不能對位置預(yù)測結(jié)果精確度的提高產(chǎn)生更高的有效性，因此需要結(jié)合多源數(shù)據(jù)進(jìn)行考慮.本文將結(jié)合用戶的歷史出行方式以及根據(jù)用戶歷史軌跡數(shù)據(jù)來對用戶的未來位置進(jìn)行預(yù)測.

對于根據(jù)用戶得到的軌跡數(shù)據(jù)，結(jié)合興趣點位置間的距離、用時時長、出行方式等因素，并根據(jù)歷史出行方式，對其下一個出行方式進(jìn)行識別分析.結(jié)合得到的未來出行方式，同時根據(jù)歷史出行方式的先驗知識建立Markov模型對未來位置進(jìn)行預(yù)測并根據(jù)概率高低得到位置結(jié)果候選集.而在頻繁軌跡模式挖掘中，位置的預(yù)測結(jié)果是將位置軌跡樹中符合路徑的子節(jié)點位置提出來當(dāng)作預(yù)測的結(jié)果，然而一個節(jié)點有多個子節(jié)點，因此我們將這些多個子節(jié)點都提取出來當(dāng)作要預(yù)測的位置候選集，最后結(jié)合2部分位置候選集合中具有高概率值且高得分的結(jié)果作為最后的預(yù)測結(jié)果.整體算法如圖10所示.

我們可以根據(jù)未來出行方式及用戶歷史軌跡數(shù)據(jù)建立模型來對未來位置進(jìn)行預(yù)測.在對未來位置進(jìn)行預(yù)測的研究內(nèi)容中.我們將結(jié)合出行方式和歷史位置軌跡建立基于Markov模型的位置預(yù)測模型，該模型如圖11所示.其中將出行方式設(shè)置為對應(yīng)Markov模型中的狀態(tài)，軌跡位置則設(shè)為對應(yīng)模型中的觀測值.因此，設(shè)狀態(tài)對應(yīng)出行方式的集合M={m1,m2,…,mN}，觀測值對應(yīng)興趣點位置的集合D={d1,d2,…,dL}，其中N是出行方式的種類數(shù)，L是可能的不同位置數(shù).長度為T的交通模式序列W=(w1,w2,…,wT)，對應(yīng)的出行軌跡序列O=(o1,o2,…,ov).同時設(shè)置出行方式轉(zhuǎn)移矩陣R=[rij]N×N,其中:

rij=P(it+1=mj|w=mi),i=1,2,…,N;j=1,2,…,N.

rij表示時刻t到時刻t+1時出行模式從mi到mj模式的轉(zhuǎn)移概率值.

Fig. 11 The Markov model combined with transportation mode圖11 結(jié)合出行方式的Markov模型

用戶的歷史軌跡位置概率矩陣B=[bj(k)]N×M,其中:

bj(k)=P(ot=dk|wt=mj),

k=1,2,…,L;j=1,2,…,N.bj(k)表示時刻t時用戶在使用出行模式mj下行駛到興趣位置dk的概率值.同時結(jié)合出行方式的先驗知識，即θ作為用戶選擇出行方式的概率：θ=(θi).其中θi=P(w1=mi)是當(dāng)時刻t=1時選擇不同出行方式mi的概率.

本模型將結(jié)合用戶的出行方式先驗概率θ、出行方式之間的轉(zhuǎn)換概率R和得到的歷史軌跡對應(yīng)的位置概率B對未來位置進(jìn)行預(yù)測.其中隱藏的出行方式序列由其模式的初始概率和不同模式之間的轉(zhuǎn)換概率來決定，而用戶行徑的軌跡位置預(yù)測則由在不同出行模式下到達(dá)的位置概率和位置間轉(zhuǎn)換的概率來共同決定，最后根據(jù)不同的出行方式結(jié)合用戶的軌跡位置序列得到未來位置預(yù)測結(jié)果.

因此在計算最后的概率時，我們將計算最后位置的概率.如圖11所示，假設(shè)觀測到的位置序列為(o1,o2,o3)，其中o4為要預(yù)測的結(jié)果，且隱含出行方式序列為(m1,m2,m3)，其中m4為識別的未來出行方式結(jié)果，那么預(yù)測位置的概率為

P(oi=o4|w1=m1,w2=m2,w3=m3,w4=m4)=P(m1)×P(m1→o1)×P(m1→m2)×P(m2→o2)×P(m2→m3)×P(m3→o3)×P(m3→m4)×P(m4→o4),

由此可以得到o4為各個位置下的概率，最后根據(jù)概率的大小組合成位置候選集合.

在得到由頻繁模式挖掘得到的位置軌跡集合S1和由Markov鏈得到的位置軌跡集合S2后，將從S2中選出含有集合S1中的位置，并將概率最大的位置作為預(yù)測的位置，即可得到最后的預(yù)測結(jié)果.

4 實驗評估

4.1 實驗數(shù)據(jù)集

在本次實驗中，我們將采用微軟亞洲研究院的Geolife項目中的數(shù)據(jù)[13]，采用17個在2007-04—2008-10的用戶數(shù)據(jù)，共400萬條數(shù)據(jù).數(shù)據(jù)中用戶外出時選擇的出行方式包括走路、騎自行車、坐公交車、坐汽車(出租車)、輕軌等.根據(jù)以上數(shù)據(jù)，將選擇80%的軌跡數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，測試數(shù)據(jù)源則為余下的數(shù)據(jù)集.

4.2 實驗設(shè)計

本次實驗主要分為2個部分：1)對結(jié)合語義軌跡和位置軌跡的軌跡頻繁模式挖掘的位置預(yù)測算法進(jìn)行有效性驗證；2)對結(jié)合出行方式和軌跡頻繁模式挖掘建立的位置預(yù)測模型進(jìn)行有效性驗證.

4.2.1 結(jié)合語義軌跡的位置預(yù)測算法驗證

在本次實驗中主要包括2部分實驗內(nèi)容：1)對算法中存在的閾值進(jìn)行合理性調(diào)試，并觀察閾值對結(jié)果精確度的影響；2)對整個算法框架進(jìn)行在不同閾值下的結(jié)果驗證.在本次實驗中，第1部分是對2個閾值進(jìn)行調(diào)整，第1個閾值是對語義模式樹和軌跡模式樹2種加權(quán)結(jié)合得分的權(quán)值設(shè)定，通過對語義模式樹權(quán)值和位置模式樹權(quán)值的高低調(diào)整來分析兩者對于最后預(yù)測位置結(jié)果的影響；第2個閾值是在前綴匹配算法中，對于軌跡位置距離要預(yù)測的位置遠(yuǎn)近進(jìn)行加權(quán)的權(quán)值設(shè)定.軌跡中距離當(dāng)前軌跡位置越近，位置距離的權(quán)值設(shè)置越高，使其對要預(yù)測位置的結(jié)果產(chǎn)生影響，本次實驗也將從結(jié)果中來確定算法的有效性.

我們將對算法中各個參數(shù)的范圍設(shè)定進(jìn)行分析，并討論關(guān)于參數(shù)對預(yù)測結(jié)果的影響.

1) 對語義模式樹和位置模式樹的權(quán)值α進(jìn)行討論.為了防止其他閾值變量對結(jié)果的影響，將設(shè)定β=1，即對軌跡上的位置權(quán)值都設(shè)為相等，以免其值對預(yù)測結(jié)果產(chǎn)生不必要的影響.同時，為了說明閾值對結(jié)果的影響性，我們對支持度分別為11%和15%這2種情況進(jìn)行分析，驗證閾值對結(jié)果的影響.實驗結(jié)果如圖12所示：

Fig. 12 The accuracy of prediction result with semantic parameter ɑ圖12 語義參數(shù)ɑ對預(yù)測結(jié)果的精確度

從圖12中我們看到，對于語義參數(shù)α<0.6時，其參數(shù)值越高，對語義模式樹賦予的權(quán)值也越重，其預(yù)測結(jié)果的精確度也越高，這表明結(jié)合語義軌跡后的精確度提高；當(dāng)α=0.6時達(dá)到85%的精確度，驗證了語義軌跡對位置預(yù)測的有效性.我們相信：因為有相同語義的用戶進(jìn)行聚類后，有相似行為活動的用戶其經(jīng)常活躍的興趣區(qū)域大致也是相同的.但是當(dāng)語義參數(shù)α越接近1時，精確度反而會下降，這也說明了只考慮語義軌跡而不考慮位置軌跡，得到的實際位置預(yù)測精確度也不會很高，說明位置軌跡也需要考慮，并且是不可或缺的一部分.

2) 分析軌跡位置的距離參數(shù)β對預(yù)測結(jié)果的有效性.在對軌跡進(jìn)行預(yù)測時，我們有理由相信，距離要預(yù)測的位置越近，其對預(yù)測的結(jié)果越有影響；而距離要預(yù)測的位置越遠(yuǎn)，說明去過這些地方的時間越久，對要預(yù)測的位置的影響力并不是很大.因此需要對位置的不同權(quán)值進(jìn)行分析，并觀察權(quán)值大小對預(yù)測結(jié)果的影響.為了驗證參數(shù)β對結(jié)果的有效性和必然性，我們同樣查看2種不同的支持度下的預(yù)測結(jié)果.在這里同樣對支持度取11%和15%，查看不同支持度下的結(jié)果.結(jié)果如圖13所示:

Fig. 13 The accuracy of prediction result with locationdistance parameter β圖13 位置距離參數(shù)β對預(yù)測結(jié)果的精確度

根據(jù)圖13中的結(jié)果可得，隨著距離參數(shù)β的值越大，其預(yù)測位置的精確度也越高，達(dá)到84%左右，說明軌跡上距離要預(yù)測的位置近的權(quán)值越大，對位置結(jié)果的預(yù)測越有效；而在軌跡上的位置來說，距離要預(yù)測的位置越遠(yuǎn)，其對預(yù)測結(jié)果的影響也越小，這也證實了我們猜想的正確性.

綜上所述，根據(jù)對2種不同閾值的分析，得到2種參數(shù)各自對位置預(yù)測的結(jié)果，不僅證明了語義軌跡對于位置預(yù)測的有效性，同時也證明了在軌跡上距離當(dāng)前預(yù)測位置越近的對預(yù)測結(jié)果的影響越大.

4.2.2 結(jié)合出行方式的位置預(yù)測模型

在本次實驗當(dāng)中，我們將采用4.1節(jié)中介紹的實驗數(shù)據(jù)集，對軌跡進(jìn)行興趣點位置的挖掘，并對總的興趣點位置進(jìn)行總的位置統(tǒng)一并由固定個數(shù)的興趣點位置來表示軌跡.在得到由興趣點位置表示的軌跡后，我們同時得到相應(yīng)位置之間所使用的出行方式及時長、位置間距離等屬性來對后續(xù)的實驗進(jìn)行驗證.

本部分實驗的內(nèi)容主要分為2大部分：1)根據(jù)軌跡中所經(jīng)過的歷史出行模式及相應(yīng)的興趣點位置對未來出行方式進(jìn)行預(yù)測；2)根據(jù)未來出行方式、歷史出行方式及歷史位置對未來位置進(jìn)行概率計算得到最后的結(jié)果.

4.2.2.1 出行方式識別算法驗證

在本節(jié)實驗中，我們根據(jù)用戶的軌跡數(shù)據(jù)所經(jīng)過的歷史出行方式，對未來的出行方式進(jìn)行識別.根據(jù)軌跡數(shù)據(jù)中我們將提取興趣點位置之間的用戶經(jīng)過的路徑長度、用戶用時時長、當(dāng)前興趣點的類別以及當(dāng)前的出行方式進(jìn)行特征提取，并采用隨機森林模型進(jìn)行建立模型，我們將采用80%的實驗數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，剩下的數(shù)據(jù)將作為測試數(shù)據(jù)來對模型進(jìn)行精確度驗證.我們將對每個用戶都進(jìn)行實驗，實驗結(jié)果如表6所示：

Table 6 The Transportation Recognition Accuracy ofEach User表6 各用戶的出行方式識別結(jié)果

表6所示為對每個用戶的出行方式的識別精確度的結(jié)果，可以看出識別結(jié)果在80%左右，因此識別精確度較高，模型具有較強的泛化能力.

4.2.2.2 未來POI位置的預(yù)測實驗

在本次實驗中，我們將根據(jù)4.2.2.1節(jié)中得到的未來出行方式以及歷史軌跡位置數(shù)據(jù)，基于Markov模型，得到下一個的位置結(jié)果結(jié)合，并得到概率從高到低排列的位置集合，然后從第1部分結(jié)果中得到的候選位置集合選擇概率最大的作為預(yù)測結(jié)果.

在本次實驗中，我們將對此實驗數(shù)據(jù)仍采用80%作為訓(xùn)練數(shù)據(jù)，剩下的數(shù)據(jù)作為測試數(shù)據(jù).我們將仍用17個用戶的軌跡數(shù)據(jù)來進(jìn)行實驗，并將所有用戶的均值作為最后的精確度.在實驗中，為了證明我們算法的有效性，我們將用結(jié)合語義和位置軌跡的位置預(yù)測算法SemanticPredict的和本模型算法TransPredict的結(jié)果進(jìn)行對比，同時根據(jù)不同支持度下的算法得到的精確度變化查看模型的有效性和泛化能力.具體結(jié)果如圖14所示：

Fig. 14 The comparison of TransPredict model algorithom and SemanticPredict model algorithom圖14 TransPredict模型算法與SemanticPredict模型算法精確度的對比

由圖14中的結(jié)果所示，在結(jié)合出行方式數(shù)據(jù)之后，本模型算法TransPredict得到的位置預(yù)測精確度達(dá)到86%左右，同時在不同支持度下要始終比根據(jù)頻繁模式軌跡的模型SemanticPredict得到的精確度高，且平均高5%.另外本模型算法TransPredict的變化趨勢隨著支持度的增加是穩(wěn)定地下降，因此可以得到我們的模型具有普適性和較強的泛化能力.最后，由于本方法使用來自微軟亞洲研究院的數(shù)據(jù)，故將與同樣使用該數(shù)據(jù)的文獻(xiàn)[14]對位置進(jìn)行預(yù)測的方法進(jìn)行比較.由于本方法同時結(jié)合用戶的出行方式，采用用戶路徑數(shù)據(jù)均包含大于等于2次不同的方式，即用戶的路徑中包含至少多于2種不同的位置.因此本方法將與文獻(xiàn)[14]中歷史位置數(shù)量大于2種的結(jié)果進(jìn)行比較.由圖14可得本方法最高精確度能達(dá)87%左右，而該論文中使用同樣的數(shù)據(jù)集，當(dāng)歷史位置個數(shù)大于2時進(jìn)行實驗所達(dá)到的準(zhǔn)確率最高在85%左右，因此可得在對未來位置預(yù)測時本方法能給出更高準(zhǔn)確率的結(jié)果.

5 結(jié) 論

本文提出一種挖掘軌跡信息數(shù)據(jù)同時結(jié)合出行方式的外源數(shù)據(jù)建立未來位置預(yù)測模型.在軌跡信息數(shù)據(jù)挖掘方面，本文首先通過對軌跡數(shù)據(jù)進(jìn)行分析，設(shè)計實現(xiàn)一種同時結(jié)合語義軌跡和位置軌跡模式的組合模型，通過對語義軌跡進(jìn)行頻繁模式挖掘得到語義軌跡結(jié)合并挖掘相似用戶簇.再對相似用戶的位置軌跡進(jìn)行模式挖掘得到位置軌跡集合，得到2種不同方式的集合.最后在對軌跡位置進(jìn)行預(yù)測時，對目標(biāo)軌跡進(jìn)行匹配得到預(yù)測結(jié)果的位置.

在結(jié)合出行方式作為外源數(shù)據(jù)方面，通過對軌跡數(shù)據(jù)和用戶的出行方式進(jìn)行分析，設(shè)計實現(xiàn)一種結(jié)合用戶出行方式和用戶頻繁模式結(jié)合的模型，即根據(jù)用戶的GPS軌跡數(shù)據(jù)，以及用戶的歷史出行方式對用戶的未來出行方式建立的模型進(jìn)行預(yù)測，同時結(jié)合根據(jù)用戶的行為活動和軌跡頻繁模式挖掘得到的位置候選集合，使用Markov模型對用戶的下一個位置預(yù)測得到結(jié)果.最后結(jié)合2部分模型得到的候選集獲得最終未來位置的結(jié)果.實驗方面通過在真實數(shù)據(jù)集上進(jìn)行實驗，驗證本模型位置預(yù)測結(jié)果具有較高的精確度且具有較強的泛化能力.