用于熱門路徑查詢的動態熱度路網的構建方法

陳依嬌，楊愷希

用于熱門路徑查詢的動態熱度路網的構建方法

陳依嬌，楊愷希

基于位置的服務在蓬勃發展的同時，產生出大量的用戶位置軌跡數據，同時基于軌跡數據的熱門路徑問題也越來越受到人們的重視。對于求解點到點熱門路徑的問題，一張帶有動態熱度信息的熱度路網是非常必要的。首先，提出了一個高效的交叉口生成算法，用于構建靜態的熱度路網，并在此基礎上提出一種新的時間段分割算法來使得路網中對應熱度邊動態化。采用希臘雅典的一部分卡車的GPS軌跡數據集，通過大量充分的實驗，印證了算法的合理性和高效性。

空間數據庫；軌跡數據挖掘；熱門路徑；隨時間動態變化

0 引言

隨著移動設備定位功能廣泛普及和基于位置的服務的蓬勃發展，用戶位置軌跡數據大量產生并被用在越來越多的研究領域中。為方便人們出行，熱門路徑提供了一種實用而新穎的路線參考，它從人們的位置軌跡數據中發現出行規律，從而幫助其他人找尋合適的路徑。

關于利用軌跡進行熱門路徑的研究，從路徑類型上可分為兩類：第一類是點到點的熱門路徑問題。該類問題最先由Chen[1]提出，同時假定沒有地圖路網數據。它采用類似密度聚類的方法聚類出路口，使用馬爾可夫模型計算路口之間的轉移概率，再根據出發點和目的地點求得一條最熱的路徑。它的缺點在于忽略了熱度路網的動態變化特性。RICK[2]是給出定點序列獲取連續通過其的熱門路徑方法，該方法能夠通過軌跡集構造可路由的路網并且在之上進行路徑規劃，這種方法對于低采樣率下的軌跡數據和無路網信息背景較為有效。TDHP[3]給出了解決給定兩點、出發時間和通過時間限制的動態熱門路徑問題的方法。

另一類是熱門路段問題，如Li[4]等人提出了路網下基于交通密度的熱門路徑方法 FlowScan。該方法利用邊和邊序列上的交通密度抽取熱門路徑，并假設兩條位置相近的邊會共享比較大的交通量，從而可能成為同一個熱門路徑的一部分。Sacharidis[5]等人提出了一種在線獲取距離查詢點較近的熱門路徑的方法。該方法著重考察在最近一段時間內的運動模式，并通過滑動時間窗口放棄過時的軌跡數據，另外還考慮了軌跡數據采集到的不確定性，提高結果的精確度。

另外，關于熱門路徑特點的分析也有一些成果。其中Guo[6]對軌跡數據進行了分析，其實驗結果體現出空間中軌跡點的密度隨時間產生了大幅變化。Li[7]的工作也能反映出熱度分布的動態特性。Ding[8]挖掘出在特定的一段時間內擁有相同移動路線的對象，并且發現他們有著周期性的移動規律。關于如何更好地表現和利用這種動態特性，文獻[9-11]采用每隔一段時間對軌跡點進行一次聚類，進而將GPS序列轉化為時間順序的簇序列。

本文針對點到點熱門路徑查詢同時沒有路網背景數據存在的情況，構建出一張帶有動態熱度信息的路網，以便進行熱門路徑查詢工作。其一，在很多情況下，路網信息并不存在，例如在一些自然環境如森林和沙漠中。當人們進行戶外活動如登山、徒步或劃船時，前人常走的路線往往包含著重要的參考信息。其二，路網的熱度信息需要符合動態性的變化規律。例如，初到一個城市的游客打算開車過程中欣賞道路兩旁的風光，白天陽光充足，擁有自然風光的道路成為首選，夜晚繁華街區的道路更佳。如果將所有游客的移動歷史軌跡進行收集并分析，會發現道路的熱度會有不同變化。最后，構建熱度路網并非是通常的構建路網和將熱度動態化的簡單累加，出于熱門路徑問題本身的特點，本文在構建熱度路網時更加重視那些熱度高的道路的生成而非所有道路的生成。

本文提出了一種用于熱門路徑查詢的動態熱度路網（記為GT）構建方法。

1 系統框架

本文系統包括軌跡數據預處理、靜態熱度路網構建和熱度路網動態化三部分。矩形內部展示了具體的系統框架如圖1所示：

圖1 系統框架

首先，利用位置點的采集時間和車輛id，劃分原始記錄為單獨的軌跡以表示一次時間和位置都連續的移動行為，然后，對軌跡插值，以減小低采樣率帶來的誤差。其次，以Traj_set為基礎生成交叉口，并通過統計學的方法構建GS。再次，通過時間段分割方法，利用時間段熱度的不同來模擬實際熱度的變化，最終構建出GT。從用戶的角度出發，其向服務器發出請求，服務器應答并在線計算熱門路徑，最后將結果返回。

受軌跡數據集限制，熱度路網可能在精度和完整性方面遜于真實地圖路網，但能夠很好地抽取出主要路段的熱度信息，而冷僻的區域會被簡化甚至過濾掉，這種做法恰恰提高了查詢熱門路徑的準確度和效率。

2 問題的定義

定義1. 點p表示移動對象出現的地理位置，由三元組(lon,lat,t)構成，其中lon和lat分別為經度和緯度，t為采集時間。

定義2. 軌跡Traj表示一次時間和位置都連續的移動行為，由一組時間連續的點構成Traj:

定義 3. 交叉口 I(P,center)表示地理上的一個小型的復雜的區域，移動對象從各個方向進入后離開。其中P是一組經過I的軌跡點，同時center為P中點的中心位置。

定義4. 熱度邊ei,j(len,h)是介于兩個交叉口Ii和Ij.間的一條路段，其中ei,j.len代表ei,j的長度，ei,j.h代表ei,j的熱度。由于熱度的動態特性，ei,j.h是時間的函數 ei,j.h(t)

定義 5. 動態熱度路網是一個有向圖 GT(V,E)（簡稱為GT）：V={Ii}是一組交叉口的集合；E? V×V是一組熱度邊的集合。

問題定義給定一個軌跡數據集，以構建一個帶有動態熱度信息的路網GT。

3 方法介紹

3.1 構建靜態熱度網絡

通過軌跡數據還原路網地圖的研究工作已有很多，也有人開展過在無地圖路網背景下生成交叉口的研究。Fathi[12]利用分類的方法生成交叉口，但是需要準確的訓練數據。在文獻[1]中提出一種 CohExpanding算法，聚類得到交叉口，實驗表明他們的方法準確度非常高。不過CohExpanding在運行效率上并不令人十分滿意，本文在其基礎上提出一種改進算法 PartExpanding，在基本不影響準確度的前提下，大幅縮短了運行時間。

3.1.1 CohExpanding[1]算法簡介

CohExpanding算法利用了交叉口點密度和方向夾角兩特點。交叉口處減速慢行，軌跡點的密度會比其他區域高，而交叉口處兩點方向夾角接近π/2（同一條道路上移動時兩點方向的夾角接近于0或π）。算法提出點間相關度的概念：點p和q的相關度定義為：兩點歐式距離，β為兩點移動方向的夾角。一般認為，兩點距離越小，運動方向越接近垂直，p和q的相關度越大，當相關度超過一定值時，則稱p和q相關。

CohExpanding的思路類似于DBSCAN算法[13]。每次從軌跡數據集中任取一個不屬于任何交叉口的點p，對p調用expand算法：從p開始不斷向周圍擴展相關點直到再也找不到任何相關點為止。如圖2所示：

圖2 對p點進行expand

以p為圓心、以R為半徑劃定尋找相關點的圓，由于圓內p1，p2兩點都與p相關，則由p擴展到p1和p2。從p1出發擴展到p3，而p3找不到與它相關的點使得擴展停止，接著從p2出發擴展到p4，同樣p4找不到相關的點，擴展停止，此時expand停止并返回點簇P={p,p1,p2,p3,p4}。若|P|≥φ（φ是人為設定的），則得到一個交叉口I(P,center)。

3.1.2 PartExpanding算法的提出

CohExpanding準確度較高，但時間耗費大，處理一個包含50輛車總共26萬個點大小的數據集，該算法耗時超過20分鐘，而實際情況處理的數據量會大很多倍。進一步分析發現，CohExpanding會在非交叉口的區域進行大量無用計算。

如圖3所示：

圖3 expand的兩種情況

假定圖中所有點實際落在道路（非交叉口）上，同時所有點之間都不相關。在對p點執行完expand操作后，需要分別對p1,p2和p3執行相同的操作，即使這4個點所處的區域顯然不是交叉口。同時，由常理可知，落在道路上的點的數量要遠大于落在交叉口區域的數量，這意味著無用的expand操作耗費了總時間的一大部分。針對這一缺陷，最簡單的改進是不對p圓內點進行擴展，但是這有可能使本應落入交叉口中的點沒有落入交叉口如圖3(b)所示，假定q點附近實際有一交叉口，p1，p2和 p3被標記，當對 q調用expand時，p1點再次落入圓內，雖然p1與q相關，但是，p1不會被擴展，expand返回點簇P，假如恰好有那么q點處的交叉口就可能沒有被找到。

記所有與p相關的點為集合P，總的來講，若P中的點離p點越遠，就越有可能由非交叉口進入交叉口，就越需要對它執行expand操作，否則其所處的位置還是更有可能屬于非交叉處。綜合考慮兩方因素，我們提出一種新的方法PartExpanding將P劃為穩定區域和不穩定區域，并規定在穩定區域中的點不需要 expand而不穩定區域中的點需要expand。具體劃分如下：我們將P中的點按照其與P的歐式距離由小到大排序，如圖4所示：

圖4 用γ進行區域劃分

3.1.3 邊靜態熱度的計算

在得到了全部的交叉口之后利用統計數構建靜態熱度路網。表1中是下面會用到的符號的說明如表1所示：

表 1 符號表

3.2 熱度路網動態化——時間段分割

本節介紹一種將熱度路網動態化的時間段分割算法TSPartition，首先給出時間段分割的定義。

定義6.時間段分割，就是對eij，將一天中的時間分割為若干連續的時間段

Chen[3]中提出了一種時間段分割算法TimeParti，本文借鑒了其方法，并做了兩點改進。第一，每條熱度邊分割后得到的時間段不應過多。時間段過多，不僅會帶來較高的存儲代價，同時會給熱門路徑查詢帶來很多時間上的消耗。TimeParti算法中只對聚類結果的聚合性進行了考察，缺乏對生成結果的數量的限制。TSPartition算法引入 vtsBound（算法1，第5行），對時間段數量進行有效地限制。第二，TimeParti算法得到的熱度函數在時間上是非連續的，對于沒有落在時間段內的時間，其熱度值永遠為 0。TSPartition將得到的時間段進行首尾拼接，并進行平滑處理，使得結果更加符合實際。

算法1: TimeParti輸入：eij.tSeq輸出：eij.vts1 ts0.creat(eij.tSeq); 2 vts.push(ts0); 3 Whiletruedo 4 max vts中SSE最大的vts[i]; 5 If(max.SSE SSEbound||vts.size vtsBound)←≤≥

6 Break; 7 vts.delete(max); 8 //采用不同的初始質心進行n次K-means試驗，每次試驗返回一對候選的時間段9 For i=0 to n-1 do 10 C1=max.FT+(max.center-max.FT)*i/n; 11 C2=max.LT-(max.LT-max.center)*i/n; 12 (tp1,tp2) ←K-means(C1,C2,max); 13 (ts1,ts2) ←使得SSE和最大的一對tp1和tp2; 14 vts.push(ts1);vts.push(ts2); 15 拼接時間段; 16 Returnvts;

4 實驗與分析

實驗分別考察構建熱度路網和時間段分割的算法性能。將PartExpanding和原有算法CohExpanding進行對比，從生成交叉口的數量和運行時間兩方面衡量PartExpanding的性能。其次，采用K-means作為TSPartition的對比算法，觀察兩者在時間段分割質量和速度上的差異。

4.1 數據集與預處理

實驗環境.所有算法使用Visual C++語言實現，實驗環境為AMD Athlon? 2 X4 610e Processor 2.40 GHz，2.00 GB內存，500 GB硬盤和Windows 8操作系統。

實驗數據.實驗采用與對比算法CohExpanding相同的數據集，即希臘雅典卡車的GPS軌跡數據。原始軌跡記錄共112203個軌跡點，平均采樣間隔30s，經過軌跡分段和插值等預處理，新的用于實驗的數據集Traj_set包含3943條軌跡共263386個軌跡點，平均采樣間隔10秒，軌跡平均點距不超過100米。

4.2 實驗結果

由于穩定閾值γ的大小可能對算法的效果有直接影響，所以本節首先考察算法隨γ增大的性能情況，挑選出最佳γ值作為PartExpanding的參數。然后對兩個算法的結果進行對比分析如圖5所示：

圖5 穩定閾值γ對熱度路網的影響

γ=0時算法退化為CohExpanding。圖5(a)中當γ上升到0.4到0.6時，交叉口數量只比γ=0時下降了不到10%，這說明PartExpanding確實只遺漏了很小一部分交叉點。圖5(b)中，當γ上升到 1，運行時間接近于零分鐘。這源于一旦一個點不需要擴展，那么會引發該點后面多個點不必擴展的連鎖反應。總之，認為當，既可以得到較高質量的交叉口，也能保證運行時間較短。下面的實驗中都設γ=6。

接著可視化算法結果以驗證算法的質量。如圖6所示：

圖6 PartExpanding結果顯示

我們調用API接口將通過PartExpanding構建的熱度路網投影在Google地圖上，結果表明其與CohExpanding的路網構建結果基本一致，熱度路網和真實路網的整體形態高度吻合，仔細觀察發現交叉口的位置基本落在地圖上真實的路口上，或者緊挨真實路口。不過從圖6中看出，仍有局部區域的邊較為冗余（如矩形內），這是由于該區域內軌跡點密度過大，導致很容易滿足邊生成的條件如圖7所示：

圖7 兩種交叉口生成算法的比較

圖7考察了兩種算法的效率。隨著軌跡點數量增多，PartExpanding的運行時間和網格索引訪問的點的數量呈緩慢線性增長如圖7(a)所示，而CohExpanding表現遜色很多如圖7(b)所示

4.3 TSPartition算法性能分析

本節從時間段分割的質量和速度上衡量TSPartition算法如圖8所示：

圖8 兩種時間段分割算法的性能比較

圖8(a)中縱坐標為平均一條邊的SSE，SSE越大說明分割結果質量越差。由圖8可以看出TSPartition的分割質量明顯優于K-means。這是因為K-means不能在簇對之間重新分布質心，這樣只能得到局部最優，而 TSPartition由于多次指派不同的初始質心，使得其不太受初始化問題的影響。圖8(b)反映出TSPartition時間消耗要高于K-means，這是因為它需要多次調用K-means。

5 總結

本文提出了一種用于熱門路徑查詢的動態熱度路網構建方法。它首先利用密度聚類，提出PartExpanding算法從軌跡數據中抽取出交叉口進而生成熱度邊，并通過統計學方法得到對應每條熱度邊的靜態熱度信息，構建出一張靜態熱度路網。然后，在將邊熱度動態化的過程中，又提出了一種新的時間段分割方法 TSPartition，對已有工作進行了改進。本文以希臘卡車GPS軌跡為實驗數據，通過大量實驗和可視化結果證明了提出的方法的有效性和高效性。

[1] Chen Z, Shen H T, Zhou X. Discovering popular routes from Trajectories[C]//Data Engineering (ICDE), 2011 IEEE 27th International Conference on. IEEE, 2011: 900-911.

[2] Wei L Y, Zheng Y, Peng W C. Constructing popular routes from uncertain trajectories[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012: 195-203.

[3] Chen Y J, Yang KX, Hu H, et al. Finding Time-Dependent Hot Path from GPS Trajectories[C].//WAIM, 2014, accepted paper.

[4] Li X, Han J, Lee J G, et al. Traffic density-based discovery of hot routes in road networks[M]//Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg, 2007: 441-459..

[5] Sacharidis D, Patroumpas K, Terrovitis M, et al. On-line discovery of hot motion paths[C]//Proceedings of the 11th international conference on Extending database technology: Advances in database technology. ACM, 2008: 392-403.

[6] Guo D, Liu S, Jin H. A graph-based approach to vehicle trajectory analysis[J]. Journal of Location Based Services, 2010, 4(3-4): 183-199.

[7] Li Q, Zeng Z, Zhang T, et al. Path-finding through flexible hierarchical road networks: An experiential approach using taxi trajectory data[J]. International Journal of Applied Earth Observation and Geoinformation, 2011, 13(1): 110-119.

[8] Li Z, Ding B, Han J, et al. Mining periodic behaviors for moving objects[C]//Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2010: 1099-1108.

[9] Kalnis P, Mamoulis N, Bakiras S. On discovering moving clusters in spatio-temporal data[M]//Advances in spatial and temporal databases. Springer Berlin Heidelberg, 2005: 364-381.

[10] Fosca Giannotti, Mirco Nanni, Fabio Pinelli, Dino Pedreschi.[C]Trajectory pattern mining. InKDD, pages 330-339, 2007.

[11] Jeung H, Yiu M L, Zhou X, et al. Discovery of convoys in trajectory databases[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 1068-1080.

[12] Fathi A, Krumm J. Detecting road intersections from gps traces[M]//Geographic Information Science. Springer Berlin Heidelberg, 2010: 56-69.

[13] Ester M, Kriegel H P, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//KDD. 1996, 96: 226-231.

Constructing Time-Dependent Hotness Road Network for Hot Path Query

Chen Yijiao, Yang Kaixi
(School of Computer Science and Technology, Fudan University, Shanghai 201203, China)

With the booming development of LBS, a huge number of users’ location trajectory data are produced and hot path problems based on trajectories are paid more and more attention. For the end-to-end hot path problem, a hotness road network with time-dependent hotness information is essential. In this paper, we first employ an efficient algorithm to generate intersections to construct a static hotness road network, then do time slot partition to make it time-dependent. The dataset is truck trajectories in Athens, Greece. Extensive experiments show that our algorithms outperform the baseline approaches in terms of both effectiveness and efficiency.

Spatial DataBase; Trajectory; Data Mining; Hot Pathtime-Dependence

TP311

A

1007-757X(2014)06-0038-05

2014.04.17)

陳依嬌(1989-)，女，復旦大學，碩士研究生，研究方向：空間數據庫和軌跡數據挖掘，上海，201203

楊愷希(1991-)，男，復旦大學，碩士研究生，研究方向：空間數據庫和軌跡數據挖掘，上海，201203