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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

2 問題建模

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

2.1 路段歷史軌跡序列數(shù)據(jù)庫

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

定義一軌跡段ID(TrajectoryID).前10位表示軌跡段起始點(diǎn)的年、月、日、時(shí)，第11～14位表示軌跡段起始點(diǎn)的分、秒，統(tǒng)一化為s表示(不超過3 600 s)，最后5位為對(duì)應(yīng)出租車的車牌號(hào)。

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

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

定義四路段掩碼(Mask).其表示該路段軌跡序列中匹配到各個(gè)路段ID上軌跡點(diǎn)的個(gè)數(shù)。因此Segment和Mask的個(gè)數(shù)是一一對(duì)應(yīng)的。

定義五時(shí)間戳序列(Timestamp).其每一項(xiàng)表示相鄰軌跡點(diǎn)之間的采樣時(shí)間間隔，單位為s，由于起始軌跡點(diǎn)前面不存在軌跡點(diǎn)，故其對(duì)應(yīng)的時(shí)間間隔設(shè)置為0.

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

通過將路段軌跡序列數(shù)據(jù)文件導(dǎo)入到MongoDB數(shù)據(jù)庫中，得到一個(gè)路段歷史軌跡序列數(shù)據(jù)庫TD1，其結(jié)構(gòu)如表1所示。然后，構(gòu)造一個(gè)路段索引哈希表結(jié)構(gòu)HM，該哈希表的key代表軌跡數(shù)據(jù)中的路段ID，value為經(jīng)過該路段ID的所有TrajectoryID，該哈希表結(jié)構(gòu)保存在內(nèi)存中供檢索路段使用，其具體的結(jié)構(gòu)如表2所示。

表1 軌跡段數(shù)據(jù)表Table 1 Track segment data table

表2 路段索引結(jié)構(gòu)表Table 2 Link index structure table

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

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

對(duì)此本文設(shè)計(jì)了一種路徑推薦方法，其主要包括兩個(gè)階段：

1)查詢階段。對(duì)于給定的起點(diǎn)、終點(diǎn)和出發(fā)時(shí)間段，通過構(gòu)建的歷史軌跡數(shù)據(jù)庫TD1和路段結(jié)構(gòu)表HM可以搜索出滿足給定條件的所有軌跡路徑，它們構(gòu)成了一個(gè)候選軌跡路徑集合。

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

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

算法1 PrefixSpan算法

輸入：序列數(shù)據(jù)集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

然后，同樣將頻繁路段軌跡序列數(shù)據(jù)文件導(dǎo)入到MongoDB數(shù)據(jù)庫中，得到一個(gè)頻繁路段軌跡序列數(shù)據(jù)庫TD2，如表3所示。通過輸入某個(gè)軌跡段ID即可得到該軌跡段ID對(duì)應(yīng)的頻繁路段軌跡序列集。

表3 頻繁路段軌跡序列數(shù)據(jù)表Table 3 Frequent trajectory data table

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

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

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

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

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

(1)

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

下面以一個(gè)例子具體地說明該過程，如圖1所示，在指定O—D對(duì)之后從數(shù)據(jù)庫中搜索出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}，并根據(jù)軌跡段ID搜索找到對(duì)應(yīng)的頻繁路段軌跡序列集C2，然后遍歷處理每一個(gè)軌跡段，對(duì)于路徑l1，遍歷他的頻繁路段軌跡序列集，{r1,r2}在l1中，得分為2/3，{r3,r20}有一半在l1中這種情況得分為0，{r19,r1,r2,r3,r20}的長(zhǎng)度為5大于l1路徑長(zhǎng)度，得分為0，所以經(jīng)過計(jì)算路徑l1的總得分為0.667.路徑l2有兩個(gè)匹配頻繁項(xiàng){r4,r5,r6}和{r8,r9}，總得分為3/5+2/5=1.路徑l3匹配的頻繁項(xiàng)為{r7,r8,r10}，匹配得分為3/5=0.6.路徑l4搜索到的頻繁項(xiàng)只有{r17,r18,r20}，不完整存在于路徑l4中，所以l4得分為0.最終根據(jù)匹配分?jǐn)?shù)對(duì)4條路徑排序?yàn)閘2>l1>l3>l4，路徑l2推薦給用戶的優(yōu)先級(jí)最高，最不推薦用戶選擇路徑l4出行。

圖1 路徑推薦實(shí)例Fig.1 Route recommendation example

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

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

輸入：起始路段ID編號(hào)O、終止路段ID編號(hào)D、時(shí)間段t1-t2、推薦路徑條數(shù)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)

為了評(píng)測(cè)算法推薦的路徑，本文從可靠性、穩(wěn)定性和合理性3方面來進(jìn)行評(píng)測(cè)[11]，具體定義如下：

(2)

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

(3)

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

3.1 算法效果

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

表4 OD對(duì)地址詳情Table 4 OD pair address details

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

使用本文提出的路徑推薦方法為4個(gè)用戶針對(duì)4組OD對(duì)分別進(jìn)行路徑推薦，推薦結(jié)果如表5-8所示，此處將軌跡段ID簡(jiǎn)寫為用戶ID加編號(hào)。

表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

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

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

為了更好地反映推薦路徑和最短路徑、測(cè)試集之間的差異，將實(shí)驗(yàn)結(jié)果進(jìn)行歸一化處理，如圖2所示，可以看出推薦算法推薦的路徑的得分要遠(yuǎn)遠(yuǎn)高于最短路徑和測(cè)試集，在4組實(shí)驗(yàn)中，推薦路徑的旅行時(shí)間相較最短路徑和測(cè)試集快10%～20%，路線距離大體上比測(cè)試集短接近于最短路徑，穩(wěn)定性和可靠性遠(yuǎn)遠(yuǎn)大于其他兩種數(shù)據(jù)集。具體來說，在OD1中推薦路徑的各項(xiàng)屬性值都是優(yōu)于測(cè)試集的，對(duì)比測(cè)試集更加具有合理性、可靠性和穩(wěn)定性。相較于最短路徑，雖然最短路徑的長(zhǎng)度要比本文算法推薦的路徑長(zhǎng)度短332 m，但是最短路徑花費(fèi)的時(shí)間更長(zhǎng)平均速度也更低，說明推薦路徑比最短路徑更具有合理性。同時(shí)最短路徑的穩(wěn)定性比推薦路徑低79.7%，可靠性低70.2%，這是因?yàn)槿藗兌稼呄蛴谶x擇最短路徑到達(dá)目的地，這樣會(huì)導(dǎo)致最短路徑上的車流量保持在一個(gè)很高的水平，出現(xiàn)交通堵塞現(xiàn)象的概率大大增加，所以距離短的路徑不一定路況好，而本文提出的算法考慮了出租車司機(jī)的行駛經(jīng)驗(yàn)(出租車司機(jī)會(huì)根據(jù)路況做出適當(dāng)?shù)穆肪€決策，從而更快地達(dá)到目的地)，向用戶推薦的路徑更加頻繁、可靠和適用，雖然該方法沒有明確的設(shè)計(jì)為推薦旅行長(zhǎng)度最短、時(shí)間最快的路徑，但是其推薦的路徑具備這些特性。

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

3.2 算法效率

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

圖3 算法執(zhí)行效率對(duì)比Fig.3 Comparison of algorithm execution efficiency

4 結(jié)束語

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