李曉娟

（四川大學計算機學院，成都610065）

0 引言

隨著人們對各種具有定位功能的智能設備的普遍使用以及基于位置的應用服務在日常生活中的廣泛應用，使得每天都會產(chǎn)生大量與位置相關的數(shù)據(jù)，而對這些數(shù)據(jù)的分析與探索成為近些年來的研究熱點之一。目前已有大量工作從事于基于GPS 軌跡的位置或用戶推薦、軌跡模式挖掘、軌跡分類以及異常檢測等領域的研究，其中基于GPS 軌跡的POI（Point Of Interest）推薦[1-7]、識別[8-9]以及與其他領域知識相結(jié)合的研究[10]更是引起越來越多研究者的關注，但很少有文獻專門針對基于GPS 軌跡的POI 類型的變化規(guī)律進行研究，這也正是本文工作的主要內(nèi)容。

基于GPS 軌跡的POI 推薦本質(zhì)上是一種位置推薦，主要考慮用戶所訪問位置的地理、時間以及語義因素等來設計各種推薦方法。文獻[3,4,7]用基于HITS 模型的系列推薦算法為用戶推薦POI 點，通過將每個用戶的軌跡按一定規(guī)則提取出停留點，例如在地理位置上進行密度聚類或K-means 聚類等，基于某種常識（如用戶趨向于訪問距離其近的POI 或用戶偏好訪問某類POI 等）構建用戶與POI 間的關系，針對每個用戶得到一個關于POI 的排序結(jié)果，從而將排序最靠前的k 個POI 點作為推薦結(jié)果。其他工作則使用不同方法為用戶提供POI 推薦服務，如文獻[5,6]采用貝葉斯方法解決POI 推薦問題，文獻[1,2]使用傳統(tǒng)推薦方法—協(xié)同過濾。但這些方法解決的問題本質(zhì)是對POI 的排序，并未探索多個POI 類型間的相互影響以及變化規(guī)律，也沒有將研究時間序列的向量自回歸模型應用到POI數(shù)據(jù)挖掘中。

由于室內(nèi)或城市的一些狹小空間內(nèi)，GPS 信號較差，甚至沒有，存在GPS 數(shù)據(jù)不夠精確的問題，POI 識別模型則是解決如何在GPS 數(shù)據(jù)不可信的情況下準確識別出現(xiàn)實存在的POI 點的問題。POI 識別模型可理解為一種特殊且復雜的停留點提取方法，雖然其可以準確識別出一個位置在現(xiàn)實中是否是人們都感興趣的地方。但其同樣沒有考慮POI 類型間的變化關系，更主要的是沒有考慮到多種不同POI 類型間的相互影響關系。

鑒于此，本文考慮多種不同POI 類型間的相互影響，提出新的停留點提取方法用于提取出用戶的POI點，還提出基于向量自回歸的POI 類型轉(zhuǎn)移演化算法BVAREA，用來探索和發(fā)現(xiàn)POI 類型轉(zhuǎn)移矩陣的變化規(guī)律，進一步預測未來幾期的POI 類型轉(zhuǎn)移矩陣。向量自回歸模型是經(jīng)濟學中最常用的模型之一，主要用于對時間序列的分析，本文是第一個將向量自回歸應用到GPS 數(shù)據(jù)挖掘中。而且可將本文工作應用到POI推薦服務中，以便提高推薦的準確性，有助于為用戶推薦一些有趣地方，以滿足用戶對新鮮事物的好奇心和嘗試性需求。還可用于POI 識別中，使其能更加準確地識別出現(xiàn)實存在的POI 點的類型，進一步研究用戶的行為習慣，從而為用戶提供更好的服務與體驗。除此之外，與其他學科結(jié)合在一起可解決新的問題，如文獻[19]將POI 和社會焦慮癥結(jié)合，對具有社會焦慮癥的人們進行研究以發(fā)現(xiàn)他們生活規(guī)律的不同。因此，對POI 類型的研究具有廣泛的應用價值和重要的研究意義。

同時本文在Geolife 數(shù)據(jù)上進行實驗，并與基于AR、MA 以及SES 的模型進行對比，結(jié)果表明，對于POI 類型轉(zhuǎn)移矩陣的預測，BVAREA 模型在MEA 和RMSE 標準上均優(yōu)于其他三個模型，在這兩個指標上預測的準確性最大分別可提高約9.23%、14.84%、14.78%、8.05%、14.1%、12.4%。

1 數(shù)據(jù)預處理

在預處理Geolife 數(shù)據(jù)前先給出一些相關定義，以便更好地理解接下來的工作。

定義1：（軌跡）一條軌跡Tr=＜P1,P2,…,Pn＞是由最基本的軌跡點Pi=（lat,lng,t）（1＜=i＜=n）按時間順序構成的，其中l(wèi)at、lng、t 分別表示地理位置的緯度、經(jīng)度以及用戶到達該位置時的時間戳。

定義2：（帶POI 類型的軌跡）已知一條原始軌跡Tr，則 其 對 應 的 帶POI 類 型 的 軌 跡TrType=＜PT1，PT2,…,PTn＞，PTi=（lat,lng,t,ty）是一個四元組，其中ty 表示根據(jù)GPS 點Pi得到的POI 類型，lat、lng、t 的含義和上面相同。

定義3：（POI 序列）POI 序列集合PoiSeq={PoiSeq1,PoiSeq2,…,PoiSeqN}，PoiSeqi=＜PTS1,PTS2,…,PTSM＞（1＜=i＜=N）是第i 個用戶的POI 序列，此序列中的任意一個點PTSj=（lat,lng,ts,te,ty）（1＜=j＜=m）是通過本文提出的新停留點提取方法得到的POI 點，lat、lng、ty、ts、te 分別表示用戶i 在訪問第j 個POI 點時所在地理位置的緯度、經(jīng)度、POI 類型以及到達該位置的起始時間和結(jié)束時間，M 表示POI 序列中POI 點的總數(shù)。

1.1 提取停留點的方法

本文受文獻[7]啟發(fā)，由連續(xù)軌跡點一般具有相同或相近的POI 類型，提出一種新方法用來從原始軌跡數(shù)據(jù)中提取出停留點。新方法涉及到兩個參數(shù)Nthreod和Tthreod，分別表示在提取出的停留點中包含原始軌跡點的最小個數(shù)和最大平均時間間隔。具體過程為，對任一帶有POI 類型的軌跡TrType，將第一個點作為臨時停 留 點PS，然 后 比 較 相 鄰 兩 點PTi和PTi+1（1＜i＜|TrType|）的POI 類型是否相同且時間間隔小于Tthreod，若滿足條件，則將PTi+1添加到臨時停留點PS 中，且PS大小加1。否則保存PS 到停留點列表中，同時生成一個新的空臨時停留點PS，將PTi+1添進去。依次類推，直到所有點被遍歷完。接著依次判斷停留點列表中每個停留點PS 與數(shù)量閾值Nthreod的大小，若小于數(shù)量閾值，判斷PS 的直接前驅(qū)和直接后繼的POI 類型是否相同，若相同，則將這三個連續(xù)停留點合并為一個，否則按公式（1）和（2）計算PS 與其直接前驅(qū)和直接后繼的avtime 和num，若avgtime 都小于Tthreod，則按這兩個值乘積的大小確定PS 應該合并到直接前驅(qū)還是直接后繼。否則合并到avgtime 小于Tthreod的停留點中，若都不小于Tthreod，則不合并，最后刪除小于Nthreod或類型未知的停留點，剩余的停留點便是本文提取出的最終的停留點，也被視之為POI 點，記為PTS。

1.2 確定最小POI 點數(shù)量的折衷方法

根據(jù)上述方法提取出每個用戶的POI 點形成一個時間序列，所有用戶的POI 序列構成一個集合POISeq，經(jīng)統(tǒng)計分析，其中POI 點數(shù)量大于1000 的POI 序列只有78 個，基于此，本文采用折衷方法來平衡最小POI 點數(shù)量和滿足POI 點數(shù)量要求的用戶數(shù)量。這是一個循環(huán)過程，具體是：將低于1000 個POI點的序列構成集合POISeqS，設初始最小POI 點數(shù)量minNum 為0，預計提升minNum 后的新最小POI 點數(shù)量newNum 是POISeqS 的平均POI 點數(shù)量，則預計提升后用戶的下降率和POI 點數(shù)量的提升率按如下兩個公式計算，若userDroop 大于pointRise，則不提升POI點數(shù)量，并退出循環(huán)，否則提升POI 點數(shù)量，并將min-Num 設置為newNum，進入下一輪循環(huán)，直到userDroop大于pointRise 或到達迭代次數(shù)才停止循環(huán)。

2 POI類型轉(zhuǎn)移矩陣和向量

由于每個用戶的行為習慣具有一定的規(guī)律性和隨機性，本文使用POI 類型轉(zhuǎn)移矩陣序列來刻畫用戶訪問不同POI 類型時的變化規(guī)律，POI 類型轉(zhuǎn)移矩陣從一個獨特的角度反映出用戶訪問位置的行為習慣。通過對POI 類型轉(zhuǎn)移矩陣的研究可以間接地了解用戶的行為習慣和類型偏好。

定義4：（POI 轉(zhuǎn)移矩陣FTM）假設K 是POI 類型的種類數(shù)，存在矩陣FTM，對于矩陣中的任何一個元素ftmi,j（1＜=i，j＜=K）表示用戶訪問的POI 類型從PTSi轉(zhuǎn)移到PTSj的頻次，矩陣FTM 就是所謂的POI 類型轉(zhuǎn)移矩陣。

依據(jù)定義3，給定所有用戶在t 和t+1 時的POI 類型分布情況，可以生成t 時的POI 類型轉(zhuǎn)移矩陣FTMt。如圖1 所示，假設POI 序列的類型種類數(shù)是4，則t，t+1，t+2 時的POI 類型分布情況分別是圖1（a）～（c），用點的形狀表示不同的用戶，顏色代表不同類型的POI（即紅、綠、藍、紫分別表示POI 類型0、1、2、3），而（d）和（e）分別表示t 和t+1 時的POI 類型轉(zhuǎn)移矩陣。例如，圖1（a）中t 時的藍色圓點轉(zhuǎn)移為圖1（b）中t+1時的紅色圓點，對應到圖1（d）中FTMt的元素ftm2,0應為1；再如圖1（b）中的紫色方塊和五角星分別轉(zhuǎn)移為圖1（c）中的藍色方塊與五角星，對應到圖1（e）的FTMt+1的元素ftm3,2應為2。

為了方便研究POI 類型轉(zhuǎn)移矩陣隨時間的變化規(guī)律，在此定義了POI 類型轉(zhuǎn)移向量序列。

定義5：（POI 類型轉(zhuǎn)移向量序列FTV）：將上述POI 類型轉(zhuǎn)移矩陣序列中的每個POI 類型轉(zhuǎn)移矩陣FTMi橫向展開為一個類型轉(zhuǎn)移向量FTVi，所形成的序列FTV={FTV1,FTV2,…,FTVM-1}被稱為POI 類型轉(zhuǎn)移向量序列，其中M 的含義與定義3 相同。

例如，圖1 中的兩個POI 類型轉(zhuǎn)移矩陣形成一個序列FTM={FTMt,FTMt+1}，按定義5 展開的類型轉(zhuǎn)移向量序列是FTV={（1,0,0,1,0,0,1,1,1,0,0,0,0,0,0,0）,（0,1,0,1,0,0,0,0,0,0,0,1,0,0,2,0）}。若實驗數(shù)據(jù)有限，可考慮將POI 類型轉(zhuǎn)移矩陣的每一行或每一列視為一個向量，利用向量自回歸模型學習其相互間的影響，從而間接實現(xiàn)用向量自回歸模型學習和預測POI 類型轉(zhuǎn)移向量序列。

圖1 POI類型轉(zhuǎn)移矩陣序列

3 向量自回歸模型與對比模型

向量自回歸模型（Vector AutoRegressive，VAR）：是對單變量自回歸模型的推廣，它將多變量序列中的每個變量作為其他變量滯后值的函數(shù)來構建模型，從而研究多變量時間序列相互間的動態(tài)變化規(guī)律，即其滯后結(jié)構關系，假設Yt=（y1t,y2t,…,ykt）T是一個由k 個內(nèi)生變量構成的列向量，et=（e1t,e2t,…,ekt）是k 維隨機擾動向量，若滯后階數(shù)為p，則VAR 模型（記為VAR（p））表示為：

式中，Yt為t 時的POI 轉(zhuǎn)移向量，Φi是第i 個k×k維的待估計系數(shù)矩陣，擾動向量et～N( )0,Ω，其內(nèi)的變量之間可以相關，但是這些變量不存在自相關，即獨立同分布，并且與內(nèi)生變量也不相關。

在構建向量自回歸模型時，重要的一步是階數(shù)的確定，本文采用赤池信息準則（Akaike Information Criterion，AIC）來確定滯后階數(shù)p，取AIC 值最小時所對應的p 值，即為最佳滯后階數(shù)。AIC 的定義如下：

式（6）中的n=k（kp+1）為待估計的參數(shù)個數(shù)，其中k 為內(nèi)生變量個數(shù)；M 是POI 類型轉(zhuǎn)移向量序列的長度；l 可通過以下等式確定。

自回歸模型（Autoregressive Model，AR）：設yt是POI 類型轉(zhuǎn)移向量中一個分量的時間序列，p 階自回歸過程（AR（p））的形式如式（9）所示，表示序列yt的當前值是p 階滯后項與隨機擾動項et的線性組合，且隨機擾動項 et獨立于序列 yt-1,yt-2,…,yt-P。與VAR 相比，AR 模型反映出POI 轉(zhuǎn)移向量分量序列的變化只受其自身變化影響的過程，沒有考慮其他POI轉(zhuǎn)移向量分量對其變化的影響。針對每個POI 類型轉(zhuǎn)移向量的分量序列，本文分別為其對應的AR 模型篩選出最佳的滯后階數(shù)p，用于說明采用VAR 模型預測POI 轉(zhuǎn)移向量的有效性。

滑動平均模型（Moving Average，MA）：是另一種自相關模式。已知yt是POI 轉(zhuǎn)移向量中一個分量的時間序列，q 階滑動平均模型（MA（q））的公式化表示如下：

由以上公式可知，滑動平均模型的當前預測值是時間序列過去q 個時期的隨機擾動項或預測誤差的線性組合。與AR 模型對比，MA 模型中的參數(shù)θ 的取值對時間序列的影響沒有AR 模型的參數(shù)p 那么強烈，所以當存在較大隨機變化時，MA 模型一般不會改變時間序列的方向。同理，本文對于每個POI 轉(zhuǎn)移向量分量序列也選取出MA 模型的最佳階數(shù)q。

簡單指數(shù)平滑模型（Simple Exponential Smoothing，SES）：是一種特殊的加權平均法，是將時間序列的當期觀測值與當期預測值經(jīng)過權重求和得到下一期預測值，特點是為距離預測期較近的序列數(shù)據(jù)賦予較大的權重，且權重由近至遠按指數(shù)遞減規(guī)律下降。公式（11）是簡單指數(shù)平滑法通項的形式化表示，同時公式（12）給出其遞推表示法。

4 基于向量自回歸的POI類型轉(zhuǎn)移演化規(guī)律

首先根據(jù)原始GPS 軌跡數(shù)據(jù)集中的每條軌跡，通過百度地圖的逆地編碼得到具有POI 類型含義的軌跡TrType，基于TrType 采用本文提出的停留點提取方法及折衷方法為用戶提取出POI 點序列，進而得到隨時間不斷變化的POI 類型轉(zhuǎn)移向量序列，然后使用向量自回歸模型進行建模，從而預測出未來幾期的POI 類型轉(zhuǎn)移向量，具體過程如算法為：

算法1：基于向量自回歸的POI 類型轉(zhuǎn)移演化算法

輸入：經(jīng)停留點提取方法及折衷方式得到的POI序列集合POISeq={POISeq1，POISeq2，…，POISeqM}，和最小點數(shù)minNum，預測期數(shù)s

步驟：

1.初始化matrix[][][]//matrix[i][][]是第i 個POI 類型轉(zhuǎn)移矩陣

2.for POISequ ∈POISeq do

3.start ←POISequ.szie—minNum—1//截取距預測期最近的等長序列

4.for PTSi ∈POISequ do

5.if（i==start）then

6. prev ←PTSi

7. elif（i ＞start）

8. matrix[i-start-1][prev.ty][PTSi.ty]++

9.endif

10.endfor

11.endfor

12.for Ti ∈T do

13.FTVi ←matrix[i]//轉(zhuǎn)換POI 類型矩陣為POI類型向量

14.endfor

POI 類型轉(zhuǎn)移矩陣是用一種間接的方式來描述用戶的行為習慣和類型偏好，對于某個給定時期的POI類型轉(zhuǎn)移矩陣，表示了用戶群從一種POI 類型轉(zhuǎn)移到其他POI 類型的POI 頻次分布情況。針對每個用戶，按照時間先后順序排序其訪問的POI 點，如果此用戶從一個POI 到另一個POI，且這兩個POI 是在訪問上是相鄰的，則更新相應期的POI 類型轉(zhuǎn)移矩陣。具體而言就是，假設一個用戶在t0期訪問一個類型為tyi的POI，接著在t1期訪問另一個類型為tyj的POI，則對應的t0期的轉(zhuǎn)移矩陣中從類型tyi到類型tyj的元素被更新。據(jù)此生成定義5 中的POI 類型轉(zhuǎn)移向量，最后使用基于向量自回歸模型的POI 類型轉(zhuǎn)移演化算法挖掘出POI 在類型轉(zhuǎn)移方面的演化規(guī)律。

5 實驗分析

5.1 數(shù)據(jù)集

本文使用Geolife 數(shù)據(jù)集，此數(shù)據(jù)集是由182 個用戶在2007 年4 月到2012 年8 月期間生成的，一共有17621 條軌跡，每條軌跡是由含有地理位置緯度、經(jīng)度以及時間戳的點構成的序列，其中91.5%的軌跡是每1～5 秒鐘或5～10 米采樣一次。

表1 POI 語義表

如上述描述，本文利用百度地圖的逆地理編碼API 獲取每個原始軌跡點的POI 類型，并按表1 對獲取到的POI 類型進行標記，如果獲取到的POI 類型不是這四種中的任意一種，則將其標記為5，表示未知類型，得到定義2 所描述的帶POI 類型的軌跡TrType后，采用本文提出的停留點提取方法提取出每個用戶的POI 點，再用折衷方法篩選出滿足要求的POI 序列，最后根據(jù)定義4、5 計算出相應的用于各種模型的POI類型轉(zhuǎn)移矩陣序列和POI 類型轉(zhuǎn)移向量序列。

5.2 評價標準

本文將會預測未來s（1＜=s＜=30）個時刻的POI 類型轉(zhuǎn)移向量，所以使用離差標準化方法來歸一化向量分量的誤差，使其在同一數(shù)量級，即具有可比性，具體公式如下：

本文設計兩個度量標準MAE（平均絕對誤差）和RMSE（標準誤差）來衡量VAR 模型的預測性能，分別表示為公式（14）和公式（15），其中的k 表示POI 轉(zhuǎn)移向量的維數(shù)。

5.3 參數(shù)設置與結(jié)果分析

本文依據(jù)前期對帶有POI 類型的軌跡數(shù)據(jù)的分析將POI 的類型數(shù)設置為4，分別標記為表1 所示。另一個參數(shù)便是向量自回歸模型滯后階數(shù)的確定，由于AIC 值越小，模型就越能有效地反映變量間的關系，因此選取能夠使AIC 值取最小時對應的滯后階數(shù)，如圖2 所示，本文VAR 模型的滯后階數(shù)都應設為1。

圖2 根據(jù)AIC確定滯后階數(shù)

為了驗證BVAREA 在POI 類型轉(zhuǎn)移向量上的預測性能，本文將基于AR、MA 和SES 的模型作為其對比方法，這三種模型都是針對單個時間序列的。為了方便描述，將這四種模型簡稱為VAR、AR、MA 和SES模型。

本文使用這四種模型分別預測接下來30 期的POI 類型轉(zhuǎn)移向量，并與實際的POI 類型轉(zhuǎn)移向量進行對比，分別計算出MAE 和RMSE 指標的值，從而反映出不同模型的預測性能。正如圖7、圖8 所示，VAR模型的預測性能最好，就MAE 評價指標而言，VAR 模型有28 期的MAE 值都低于AR、MA、SES 模型；對于RMSE 指標，其中有25 期是VAR 模型低于其余三個模型，這說明考慮多序列之間的相互影響對POI 類型轉(zhuǎn)移向量的預測至關重要。VAR 模型與AR 模型相比，在MAE 標準上，VAR 模型的預測性能最高可以提高大約9.23%，最低可提升約1.83%；在RMSE 標準上，VAR 模型預測性能的準確性大約可提升1.16%-8.05%，表明同時考慮多個POI 類型轉(zhuǎn)移向量的分量序列有助于提高預測的準確性。與MA 和SES 模型相比，雖然有時的預測準確性要低于這兩種模型之一，但這正體現(xiàn)出POI 類型轉(zhuǎn)移向量分量序列具有一定的隨機特性。就MAE 指標而言，VAR 模型在最好情況下可以比MA 模型提高大約14.84%的準確性，比SES 模型可提高約14.1%；根據(jù)RMSE 指標，VAR 模型分別比MA 模型和SES 模型提高14.78%和12.4%。

圖3 在未來30個預測上不同方法的MAE值

圖4 在未來30個預測期上不同方法的RMSE值

6 結(jié)語

本文在GPS 數(shù)據(jù)挖掘中發(fā)現(xiàn)現(xiàn)有工作很少有將多個POI 類型的相互影響同時考慮在內(nèi)，基于此，本文提出一種新的停留點提取方法，目的是從原始軌跡數(shù)據(jù)中提取出需要的POI 點，同時用一種折衷方式平衡每個POI 序列中POI 點的數(shù)量和滿足POI 點數(shù)量要求的用戶數(shù)量，然后利用本文提出的基于VAR 模型的POI類型轉(zhuǎn)移演化算法學習POI 類型轉(zhuǎn)移矩陣的變化規(guī)律并預測未來幾期的POI 類型轉(zhuǎn)移矩陣。最后在真實數(shù)據(jù)集上進行實驗，通過與基于AR、MA 以及SES 模型的對比，說明本文提出方法的有效性。本文是第一個將VAR 模型應用到GPS 數(shù)據(jù)挖掘中的，同時POI 類型轉(zhuǎn)移矩陣以與之前工作不同的角度來反映用戶訪問位置的行為習慣和大眾偏好，且可將本文工作應用到POI 推薦、POI 識別等有關POI 的領域中。