基于頻繁軌跡序列模式挖掘的路徑推薦方法

段宗濤，任國亮，康 軍，黃 山，杜錦光，王倩倩

(長安大學 a.信息工程學院，b.陜西省道路交通智能檢測與裝備工程技術研究中心，西安 710064)

隨著全球衛星導航、物聯網、移動通信、大數據等技術與智能交通系統(intelligent transportation system，ITS)的深度融合，城市交通系統已經進入了智能交通時代，越來越多的各類移動對象在不同場景下的時空軌跡數據被采集和存儲到時空數據庫中。這些時空軌跡數據包含的大量知識需要進行快速有效的分析。在對各種時空軌跡的分析任務中，序列模式挖掘是其中最重要的任務之一。時空軌跡序列模式挖掘作為序列模式挖掘的一個重要研究分支，其可以定義為從海量的、異構的、含噪聲的移動GPS軌跡序列中提取潛在的、頻繁出現的、具有價值的軌跡序列的過程。通過對這些軌跡序列研究分析可以揭示出有價值的信息來用于廣泛的社會服務，如移動模式挖掘[1]、位置預測[2]、路徑推薦[3]和異常檢測[4]等。

時空軌跡路徑推薦作為數據挖掘的一個應用，主要是通過對移動對象的歷史軌跡進行挖掘以找出其行為潛在的時空規律性及其行為偏好，以此來為移動對象推薦合理、高效的運動路徑。出租車作為城市居民戶外出行普遍乘坐的交通工具，其對城市居民的出行生活有著舉足輕重的影響，而出租車司機對城市的路網結構以及交通情況有著很深的了解，他們經常利用他們的經驗知識在給定起始點-目的地(O—D)的情況下選擇行駛路線，這些蘊含經驗知識的行駛軌跡往往具有較高的成本效益，如行程距離短、行車時間少、行車速度快等。依據出租車司機的經驗軌跡模式來進行路徑推薦可以提供更加合理、準確、高效的行駛路線。在此背景下，本研究的目標是提供一種融合經驗路線的路徑推薦方法，以涵蓋出租車司機的行車經驗與偏好。當用戶給定一個起始點—目的地(O—D)的時候，應該解決以下幾個挑戰：1)如何將出租車歷史軌跡數據中蘊含的經驗知識融合到路徑推薦過程。2)如何針對給定的O—D進行個性化路徑推薦。3)證明路徑推薦方法的有效性。

針對以上問題，提出了一種基于頻繁軌跡序列模式的路徑推薦模型，首先，根據出租車的狀態信息(空載或載客)將原始GPS軌跡序列分段為子軌跡序列，并利用經過Map-matching的GPS軌跡數據中包含的城市路網路段信息將出租車GPS軌跡數據轉換為一種由道路編碼的表現形式，稱之為路段ID序列；然后將路段ID序列保存為.json格式的路段軌跡序列數據文件導入到MongoDB數據庫中，通過輸入起始路段ID、終止路段ID和某個時間段，就可以檢索出在該時段內經過這兩個路段ID的所有路段軌跡序列。接下來，使用序列模式挖掘算法PrefixSpan[5]挖掘頻繁軌跡序列對候選軌跡路徑集合進行優先級排序，針對頻繁軌跡序列中長短模式對候選路徑排序的影響差異較大的問題，提出了一種長短模式權重評估模型，最后，按照排序結果向用戶推薦評估值前Top-n的路徑。該方法有以下貢獻點：

1)提出了一種新的路段歷史軌跡序列數據庫。將出租車GPS軌跡數據轉換為一種由道路編碼表示的路段ID序列，然后轉換為數據文件并導入MongoDB數據庫中生成路段歷史軌跡序列數據庫，該數據庫使得用戶可以根據自己的需求快捷地檢索軌跡數據。

2)提出了一種基于頻繁軌跡序列模式的路徑推薦模型。根據用戶要求在路段歷史軌跡序列數據庫中檢索出符合條件的路徑，然后基于序列模式挖掘方法對候選路徑集進行排序，針對頻繁軌跡序列中長短模式對候選路徑排序的影響差異較大的問題，提出了一種長短模式權重評估模型。

3)依據真實的城市路網交通軌跡數據設定了4個模擬場景，通過模擬案例對該路徑推薦方法的分析結果表明，該推薦方法是具備合理性的，其為用戶推薦的路徑是符合大多數出租車駕駛員行車習慣的，如：行車距離短、行車時間少、平均速度高等；同時與最短路徑測試集相比較，推薦算法所推薦的路徑更加可靠、穩定；與傳統路徑推薦算法相比其運行速度更快。

1 相關工作

時空軌跡序列模式挖掘作為序列模式挖掘的一個重要研究分支，旨在從時空軌跡數據集中找出頻繁出現的序列模式，如普遍性規律或公共性頻繁路徑等。本文采用模式增長類算法PrefixSpan來挖掘頻繁軌跡序列模式，該算法在保證模式時序性和空間位置關系不變的情況下，能夠花費較短的時間挖掘出蘊含出租車司機經驗知識的頻繁路徑。

路徑推薦不僅是時空軌跡序列模式挖掘的一個主要應用，在其他技術研究領域也越來越受歡迎。例如，文獻[6]提出了一種基于地理標記照片的語義軌跡模式挖掘的軌跡推薦系統，該系統考慮了軌跡的時空順序和空間語義維度以及用戶的偏好約束，從帶有地理標記的照片中挖掘頻繁的旅行模式，然后提取出一組語義行程向用戶推薦。文獻[7]提出了一種通過深度神經網絡權重學習的上下文感知路徑推薦方法，該方法基于深度學習從歷史數據中提取與每個路線特征相關的權重知識，應用隨機規劃模型來解決權重丟失問題，在此基礎上通過利用加權最短路徑的目標值自定義深度神經網絡的損失函數來連接學習方法和優化問題。文獻[8]提出了一種基于用戶群動態群類的個性化旅游路徑推薦系統，該系統使用MapReduce編程模型優化的聚類方法來挖掘小群模式。文獻[9]提出了k最短路徑算法，在滿足用戶給定的閾值下，向用戶推薦k條彼此足夠不同且盡可能短的路徑。文獻[10]提出了一種基于混合交通模式的出行路線推薦模型，將路線推薦問題轉化為旅行路線圖中的最短路徑問題，相比于傳統最短路徑推薦模型，改變了單一交通規劃的方式，解決了單車出行方式的局限性。上述文獻依據路徑最短、語義結合、業務需求等方面向用戶推薦路徑，綜上所述，很少有研究考慮過將出租車司機行車經驗加入到路徑推薦方法中，即使用出租車軌跡數據在指定起點和終點的情況下，考慮出行的起始時間以及出行路徑的頻率，使用面向O—D和面向路徑結合的方法將隱藏在軌跡數據中的知識轉化為候選推薦路徑。

2 問題建模

本文利用經過Map-matching的GPS軌跡數據中包含的城市路網路段信息，將車輛原始GPS軌跡數據轉換為城市路網路段序列，將原始軌跡序列中車輛移動的地理位置、移動方向等空間特征用路段及其之間的順序來表示，將路段軌跡序列數據文件導入到MongoDB數據庫中，得到一個路段歷史軌跡序列數據庫，通過輸入起點、終點和出行時間段搜索得到一個候選路徑集，基于各個候選路徑中包含的頻繁路徑序列模式對其進行量化評估并進行排序，取出指定的前Top-n條路徑為用戶進行推薦。

2.1 路段歷史軌跡序列數據庫

首先從出租車原始軌跡數據中提取得到載客路段軌跡序列集和空載路段軌跡序列集數據文件，數據文件的格式為.json，其每一條軌跡段數據共包含6個字段信息。

定義一軌跡段ID(TrajectoryID).前10位表示軌跡段起始點的年、月、日、時，第11～14位表示軌跡段起始點的分、秒，統一化為s表示(不超過3 600 s)，最后5位為對應出租車的車牌號。

定義二軌跡段狀態(State).表示該條軌跡段是空載還是載客(4：空載軌跡段，5：載客軌跡段)。

定義三由路段ID組成的軌跡段序列(Segment)。原始軌跡點通過地圖匹配映射到路網中的路段上，不同軌跡點對應的路段ID有可能相同也有可能不同。

定義四路段掩碼(Mask).其表示該路段軌跡序列中匹配到各個路段ID上軌跡點的個數。因此Segment和Mask的個數是一一對應的。

定義五時間戳序列(Timestamp).其每一項表示相鄰軌跡點之間的采樣時間間隔，單位為s，由于起始軌跡點前面不存在軌跡點，故其對應的時間間隔設置為0.

定義六軌跡段的其他信息序列(Other)。其表示由該軌跡段中一系列軌跡點按照先后順序匹配到路段上的經緯度信息、速度信息、航向角信息組成的序列。

通過將路段軌跡序列數據文件導入到MongoDB數據庫中，得到一個路段歷史軌跡序列數據庫TD1，其結構如表1所示。然后，構造一個路段索引哈希表結構HM，該哈希表的key代表軌跡數據中的路段ID，value為經過該路段ID的所有TrajectoryID，該哈希表結構保存在內存中供檢索路段使用，其具體的結構如表2所示。

表1 軌跡段數據表Table 1 Track segment data table

表2 路段索引結構表Table 2 Link index structure table

2.2 基于頻繁軌跡序列模式的路徑推薦方法

通常情況下，出租車司機相比其他出行群體具有更優的路徑選擇行為，即其選擇行駛的路徑往往具有行程距離短、行車時間少、行車速度快等特點，將此稱之為駕駛員的經驗行駛軌跡；基于大規模出租車歷史軌跡數據挖掘出出租車的頻繁軌跡序列模式，這些軌跡序列模式即出租車司機的經驗行駛軌跡。把這些頻繁軌跡序列模式用于為出行者進行路徑推薦的過程中，將會為其提供性價比較高的出行路線，從而實現合理化的路徑推薦。

對此本文設計了一種路徑推薦方法，其主要包括兩個階段：

1)查詢階段。對于給定的起點、終點和出發時間段，通過構建的歷史軌跡數據庫TD1和路段結構表HM可以搜索出滿足給定條件的所有軌跡路徑，它們構成了一個候選軌跡路徑集合。

2)排序階段。由于在1)中通過數據庫自帶的搜索引擎查詢出來的各軌跡路徑之間的優先級是不得而知的，即哪一條路徑更值得被推薦還無法確定，因此設計了一種長短模式權重評估模型對查詢出的所有候選路徑進行一個優先級排序，然后將排名前n的路徑推薦給用戶。

本文使用模式增長類算法PrefixSpan算法挖掘出租車的頻繁軌跡序列模式，具體算法流程見算法1，由于頻繁路段軌跡序列必為軌跡段數據中的子路段序列，即每條頻繁路段軌跡序列都會對應一個或多個軌跡段ID信息TrajectoryID，因此在進行結果保存的時候，為每條頻繁路段軌跡序列帶上其在原始軌跡段數據集中的軌跡段ID信息TrajectoryID，然后以TrajectoryID作為key，其對應的頻繁路段軌跡序列集合作為value(若有多條路段軌跡序列，中間用“;”隔開)輸出.json文件。

算法1 PrefixSpan算法

輸入：序列數據集S和支持度閾值min_sup

輸出：所有滿足支持度要求的頻繁序列集

i=1,αi←findPrefix(i)

S|αi←findProjection(αi)

for each elemLj∈αido

sum_i_Lj=count(Lj)

if(sum_i_Lj

αi.delete(Lj)

end for

for each elemLj∈αido

S|Lj←findProjection(Lj)

if(S|Lj=null ‖ each elem sumiLj∈count(S│Lj)

Return

然后，同樣將頻繁路段軌跡序列數據文件導入到MongoDB數據庫中，得到一個頻繁路段軌跡序列數據庫TD2，如表3所示。通過輸入某個軌跡段ID即可得到該軌跡段ID對應的頻繁路段軌跡序列集。

表3 頻繁路段軌跡序列數據表Table 3 Frequent trajectory data table

接下來，基于構建好的路段歷史軌跡序列數據庫TD1和頻繁路段軌跡序列數據庫TD2，對查詢階段的候選路徑集合設計了一種排序方法，具體步驟如下：

1)在數據庫TD1中輸入用戶給定的起始路段編號O，通過哈希表HM查找出所有經過起始路段的所有軌跡段ID集startSet，同樣，輸入終止路段編號D查找出所有經過終止路段的所有軌跡段ID集endSet,然后通過交集運算startSet∩endSet計算出經過這兩個路段ID的所有路段軌跡序列，根據用戶給定的起始時間t1-t2對其進行過濾得到滿足O—D和時間要求的軌跡段ID集合，最后使用數據庫TD1查詢過濾得到的軌跡段ID，就可以查詢出經過O和D并且滿足時間要求的所有路段軌跡序列及其對應的軌跡段ID，將其稱為候選路徑集合C1(C1中的所有軌跡序列僅保留以O開始以D結束的部分)。

2)對于候選路徑集合C1中的每一條路段軌跡序列Li，先提取出Li的軌跡段ID，即Ti，然后在數據庫TD2中查詢出Ti對應的頻繁路段軌跡序列集C2.

3)由于C2中每條頻繁路段軌跡序列Lj必是原始路段軌跡序列的一部分，因此對于候選路徑集合C1中每條路徑Li而言，Lj可能存在于Li中，也可能不存在，例如，當Li的長度小于Lj時，肯定不會在Li中匹配到Lj；而頻繁路段軌跡序列集C2中的每條頻繁路段軌跡序列Lj在候選路徑Li中的出現情況能反映出該條候選路徑是否更值得被推薦，即對于任意一條候選路徑Li而言，其在頻繁路段軌跡序列集C2中匹配到的頻繁軌跡序列模式越多，尤其是長模式，該路徑就越符合出租車駕駛員的出行習慣，越值得優先向用戶推薦。

接下來，對C2中每條頻繁路段軌跡序列Lj在候選路徑Li中進行模式匹配，若Lj完整存在于Li中，則用Lj長度與Li長度的比值表示Lj在Li中的匹配得分，否則，得分為0.最后將所有匹配得分求和即可得到候選路徑Li的總得分，其計算公式如式(1)所示。

(1)

4)根據式(1)算出候選路徑集合C1中每條候選路徑Li的總得分，再根據每條路徑的總得分降序排列，取出指定的Top-n條路徑為用戶進行推薦。

下面以一個例子具體地說明該過程，如圖1所示，在指定O—D對之后從數據庫中搜索出4條候選路徑集合C1，依次為l1={r1,r2,r3}；l2={r4,r5,r6,r8,r9}；l3={r4,r7,r8,r10,r11}；l4={r4,r12,r13,r14,r15,r16,r17,r18}，并根據軌跡段ID搜索找到對應的頻繁路段軌跡序列集C2，然后遍歷處理每一個軌跡段，對于路徑l1，遍歷他的頻繁路段軌跡序列集，{r1,r2}在l1中，得分為2/3，{r3,r20}有一半在l1中這種情況得分為0，{r19,r1,r2,r3,r20}的長度為5大于l1路徑長度，得分為0，所以經過計算路徑l1的總得分為0.667.路徑l2有兩個匹配頻繁項{r4,r5,r6}和{r8,r9}，總得分為3/5+2/5=1.路徑l3匹配的頻繁項為{r7,r8,r10}，匹配得分為3/5=0.6.路徑l4搜索到的頻繁項只有{r17,r18,r20}，不完整存在于路徑l4中，所以l4得分為0.最終根據匹配分數對4條路徑排序為l2>l1>l3>l4，路徑l2推薦給用戶的優先級最高，最不推薦用戶選擇路徑l4出行。

圖1 路徑推薦實例Fig.1 Route recommendation example

具體的算法如算法2所示。

算法2 頻繁軌跡序列模式路徑推薦算法

輸入：起始路段ID編號O、終止路段ID編號D、時間段t1-t2、推薦路徑條數n

輸出：得分前Top-n條路徑

C1←TD1.FindRoute(start=O,end=D,time=t1-t2)

for each candidateLi∈C1do

Ti←Li.getTrajID()

C2←TD2.FindFrequentSet(TrajID=Ti)

for each elemLj∈C2do

ifLi∈Ljthen

Li.score←Li.score+Lj.size÷Li.size

end for

C1.sortBy(key=Li.score)

C1.take(n)

為了評測算法推薦的路徑，本文從可靠性、穩定性和合理性3方面來進行評測[11]，具體定義如下：

(2)

定義八穩定性(Stability)。通過所推薦路線的速度的方差來量化其穩定性，方差越高表示速度的變化幅度越大，行程越不穩定，計算公式如式(3)所示。

(3)

3 實驗與分析

3.1 算法效果

本文采用模擬場景的方式對提出的路徑推薦算法進行分析與評估，實驗采用2016年9月1日到9月10日11 530輛西安市出租車GPS軌跡數據，軌跡數量為1 000多萬條，在進行實驗之前對數據進行預處理、軌跡分段和軌跡段編碼。假定有4名用戶A、B、C、D，用戶A在早高峰時段8:00-11:00出行，用戶B在午高峰時段14:00-17:00出行，用戶C在非高峰時段17:00-19:00出行，用戶D在晚高峰時段19:00-22:00出行，并指定了4組起止路段ID，分別為OD1(51483701132,51482708869)、OD2(51482702983,51482702631)、OD3(51483710281,51483701237)、OD4(51483708245,51483703286)。各個OD對所代表的實際地址如表4所示，頻繁軌跡序列模式挖掘算法的最小支持度閾值設置為3，n為3.

表4 OD對地址詳情Table 4 OD pair address details

這幾個位置都處于市中心地區，選擇這一領域的考慮因素如下。首先，這幾個地區有足夠的出租車司機和行駛軌跡數據來支持這路徑搜索實驗。復雜的交通狀況和城市中心地區頻繁的擁堵，使得利用經驗豐富的司機的路線決策經驗是有價值的。其次，由于中心地區人流量大，出租車司機傾向于到中心地區為乘客提供服務，因此，在中心地區可以觀察到比其他地區更多的軌跡數據，以支持路徑搜索任務。

使用本文提出的路徑推薦方法為4個用戶針對4組OD對分別進行路徑推薦，推薦結果如表5-8所示，此處將軌跡段ID簡寫為用戶ID加編號。

表5 OD1推薦路徑屬性值Table 5 Attribute value of recommended path at OD1

表6 OD2處推薦路徑屬性值Table 6 Attribute value of recommended path at OD2

表7 OD3處推薦路徑屬性值Table 7 Attribute value of recommended path at OD3

表8 OD4處推薦路徑屬性值Table 8 Attribute value of recommended path at OD4

下面從可靠性、穩定性兩個方面證明所提出的路徑推薦算法是可取的。將算法推薦路徑和最短路徑、測試集路徑的屬性進行比較。指定四組OD對，起止點的設置和上文相同，用戶出行時間為高峰時段8:00-11:00，使用加入了歷史軌跡信息的Dijkstra最短路徑算法尋找最短路徑，從歷史軌跡中隨機選取了50條符合起止點要求和時間要求的路徑作為測試集，將其數據屬性的平均值作為測試集結果。實驗結果如表9所示。

表9 推薦路徑和最短路徑、測試集比較結果Table 9 Comparison results of recommended path,shortest path,and test set

為了更好地反映推薦路徑和最短路徑、測試集之間的差異，將實驗結果進行歸一化處理，如圖2所示，可以看出推薦算法推薦的路徑的得分要遠遠高于最短路徑和測試集，在4組實驗中，推薦路徑的旅行時間相較最短路徑和測試集快10%～20%，路線距離大體上比測試集短接近于最短路徑，穩定性和可靠性遠遠大于其他兩種數據集。具體來說，在OD1中推薦路徑的各項屬性值都是優于測試集的，對比測試集更加具有合理性、可靠性和穩定性。相較于最短路徑，雖然最短路徑的長度要比本文算法推薦的路徑長度短332 m，但是最短路徑花費的時間更長平均速度也更低，說明推薦路徑比最短路徑更具有合理性。同時最短路徑的穩定性比推薦路徑低79.7%，可靠性低70.2%，這是因為人們都趨向于選擇最短路徑到達目的地，這樣會導致最短路徑上的車流量保持在一個很高的水平，出現交通堵塞現象的概率大大增加，所以距離短的路徑不一定路況好，而本文提出的算法考慮了出租車司機的行駛經驗(出租車司機會根據路況做出適當的路線決策，從而更快地達到目的地)，向用戶推薦的路徑更加頻繁、可靠和適用，雖然該方法沒有明確的設計為推薦旅行長度最短、時間最快的路徑，但是其推薦的路徑具備這些特性。

圖2 推薦路徑與最短路徑、測試集比較(歸一化)Fig.2 Comparison of recommended path,shortest path,and test set attributes (normalized)

3.2 算法效率

為了驗證本文算法的效率，選擇Dijkstra算法和A*算法進行對比實驗[12]，Dijkstra算法主要特點是從起始點開始，采用貪心算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節點，直到擴展到終點為止，A*算法使用了一個特別的估價函數f(n)=g(n)+h(n)，其中g(n)表示從起始搜索點到當前點的代價(通常用某結點在搜索樹中的深度來表示)，h(n)表示當前結點到目標結點的估值。實驗數據和上文相同，在劃定的區域(實驗中使用的軌跡數據是經過指定起止點的)中使用Dijkstra算法和A*算法尋找最短路徑，將實驗數據分為10組，如：1 d、1～2 d、1～3 d、…、1～10 d，指定起始路段ID為51483701132、終止路段ID為51482708869，用戶出行時間為高峰時段8:00-11:00，算法運行時間如圖3所示。從圖中可以看出本文提出的推薦算法相比于另外兩種傳統算法快得多。

圖3 算法執行效率對比Fig.3 Comparison of algorithm execution efficiency

4 結束語

本文提出了一種基于頻繁軌跡序列模式的路徑推薦方法：基于歷史軌跡數據構建路段軌跡序列數據庫、路段索引表和頻繁路段軌跡序列數據庫，根據用戶要求搜索得到候選路徑集。利用所提出的頻繁路徑序列長短模式權重評估模型，基于各個候選路徑中包含的頻繁路徑序列模式對其進行量化評估并進行排序，取出評估值前Top-n條路徑為用戶進行推薦。為了評估該路徑推薦方法的合理性，本章最后設定了4個模擬場景，通過模擬案例對該路徑推薦方法的分析結果表明，該推薦方法是具備合理性的，其為用戶推薦的路徑是符合大多數出租車駕駛員行車習慣的。同時實驗研究證明，與傳統的最短路徑算法相比，該推薦算法推薦的路徑在行駛時間、路徑長度、平均速度、可靠性和穩定性方面表現更好，對比一般測試集更有優勢，算法的運行速度更快。