基于歷史軌跡的個(gè)性化路線推薦算法的研究*

趙加坤 闞伊檸 趙燕子 劉小英

（西安交通大學(xué)軟件學(xué)院 西安 710049）

1 引言

隨著信息時(shí)代的到來，路徑導(dǎo)航［1］在我們?nèi)粘Ｉ钪杏兄匾匚?，私家車的出行活?dòng)離不開導(dǎo)航系統(tǒng)，與此同時(shí)人們對導(dǎo)航功能的需求也逐漸提高。過去的導(dǎo)航軟件只是根據(jù)我們所提供的起始和終止位置為我們推薦最優(yōu)的行駛路線，雖然方便實(shí)用，但往往所推薦的路線并不適用于所有人，這些導(dǎo)航軟件并沒有考慮到不同的司機(jī)有不同的駕駛習(xí)慣。如果導(dǎo)航可以自動(dòng)獲取用戶的偏好，再根據(jù)偏好過濾出最符合用戶需求的推薦路線，那么就將極大程度提高導(dǎo)航軟件的導(dǎo)航質(zhì)量。

因此，本文抓住了這一需求，在前人研究的基礎(chǔ)上豐富了軌跡數(shù)據(jù)的多樣性，修改了模型。在司機(jī)個(gè)人偏好上，不僅考慮了大眾所考慮的時(shí)間、距離和油耗的問題，還關(guān)注到一些經(jīng)驗(yàn)豐富的司機(jī)經(jīng)常會(huì)考慮的轉(zhuǎn)向開銷和信號燈等待的問題，進(jìn)一步對司機(jī)的個(gè)人行駛偏好建模，提出了一種根據(jù)司機(jī)不同的駕駛偏好來推薦個(gè)性化行駛路線的算法模型，同時(shí)文中還使用了大數(shù)據(jù)技術(shù)對車輛的歷史軌跡進(jìn)行存儲(chǔ)，可以保證軌跡數(shù)據(jù)的實(shí)時(shí)更新，提高軌跡的檢索速度，保證了推薦的效率。此方案大幅度提升了推薦路徑的合理性和準(zhǔn)確性，將在來自全國的私家車數(shù)據(jù)集上進(jìn)行驗(yàn)證，這些復(fù)雜的數(shù)據(jù)具有多樣性，也進(jìn)一步驗(yàn)證了文中方法的可用性。

2 相關(guān)工作

導(dǎo)航基本可以分為兩類：1）基于數(shù)字地圖的導(dǎo)航；2）基于軌跡數(shù)據(jù)的導(dǎo)航。

基于數(shù)字地圖的導(dǎo)航是傳統(tǒng)的導(dǎo)航方式，其原理相當(dāng)于數(shù)據(jù)結(jié)構(gòu)圖的最短路徑或者最優(yōu)路徑，其中最簡單的是Dijkstra［2］算法和A*［3］算法，主要應(yīng)用動(dòng)態(tài)規(guī)劃的原理去計(jì)算最短路徑，但是當(dāng)路網(wǎng)比較大、路線圖分支比較多時(shí)，這種算法會(huì)大大浪費(fèi)時(shí)間。在此基礎(chǔ)上，覃柯棚等［4］提出一種尋找最短路徑更加高效率的改進(jìn)算法，通過最小堆對算法進(jìn)行優(yōu)化，進(jìn)一步提升了算法的效能。這種方法更加注重效率，但是卻沒有考慮用戶的駕駛習(xí)慣。本文提出的方法更加看重軌跡推薦的質(zhì)量，把用戶的偏好考慮在內(nèi)，最終推薦出與用戶偏好最相符的行駛路線，適用于任何復(fù)雜路況下的個(gè)性化推薦。

基于軌跡數(shù)據(jù)的導(dǎo)航大多把注意力放在軌跡挖掘［5］上，Letchner J等［6］在文章中首次提出了根據(jù)軌跡特點(diǎn)來進(jìn)行路徑選擇，打開了個(gè)性化推薦的大門，但是數(shù)據(jù)挖掘技術(shù)使用比較單一，未能得到足夠的軌跡代表性特征。Funke等［7］提出了用線性不等式的方式對個(gè)人的偏好向量進(jìn)行求解，但是這種方式需要假設(shè)用戶的歷史軌跡是開銷最小的，這種假設(shè)會(huì)與實(shí)際情況有一些和誤差。Yang等［8］認(rèn)為在不同的場景下用戶的偏好不同，通過SVM分類器的方式得出一個(gè)超平面的場景進(jìn)行個(gè)性化推薦，但是這種方式并不能窮舉場景，導(dǎo)致推薦的路線有些單一。Dai等［9］使用出租車的歷史軌跡為基礎(chǔ)進(jìn)行路徑的推薦，得到了很不錯(cuò)的效果，但是出租車的軌跡數(shù)據(jù)比較單一，對于用戶偏好的考慮不周全，本文進(jìn)一步對軌跡進(jìn)行挖掘，提取出更多的偏好特征，對偏好分布進(jìn)行更加精準(zhǔn)的建模，從而推薦出更適合用戶出行的路線。

另外，本文數(shù)據(jù)集來自全國各地的私家車歷史軌跡數(shù)據(jù)，提高了歷史軌跡的多樣性，在數(shù)據(jù)上更具有信服力。同時(shí)文中引用大數(shù)據(jù)存儲(chǔ)技術(shù)［10］，在軌跡數(shù)據(jù)索引上極大提高效率，集群的I/O性能［11］是影響整體性能的一個(gè)關(guān)鍵性因素，文中對性能進(jìn)行優(yōu)化，對I/O性能進(jìn)行實(shí)驗(yàn)驗(yàn)證其高效性。

3 算法模型

3.1 基本概念及整體框架

定義1（軌跡序列）一段行駛軌跡是由無數(shù)個(gè)軌跡點(diǎn)有序組成的一組序列Trj={t1，t2，…，tn}，其t中包含了軌跡點(diǎn)的地理坐標(biāo)信息。

定義2（軌跡分割）為了更好地對軌跡進(jìn)行聚類，我們需要根據(jù)實(shí)際情況把一段長軌跡分割為幾個(gè)不等長的有序軌跡序列Trj1={t1，t2，…，ti}，Trj2=

一般軌跡分割［5］分為四種：按時(shí)間間隔分割、按轉(zhuǎn)向分割、按軌跡形狀關(guān)鍵點(diǎn)分割以及按照停留點(diǎn)進(jìn)行分割。根據(jù)本文的數(shù)據(jù)特征，采用最后一種按照停留點(diǎn)進(jìn)行分割，如圖1所示，軌跡就可以分為，這兩條軌跡。

定義3（軌跡去噪）由于某一個(gè)或者某些個(gè)軌跡點(diǎn)的異常會(huì)為軌跡挖掘工作帶來不必要的麻煩，因此會(huì)采取一定的措施去避免這些麻煩。我們采用的方式是均值濾波和異常點(diǎn)舍棄兩種方案結(jié)合來對軌跡進(jìn)行去噪處理。

如圖2所示，均值濾波可以參考前后點(diǎn)的狀態(tài)對異常點(diǎn)進(jìn)行評估。異常點(diǎn)［5］探測方法在本文中主要考慮速度這個(gè)過濾條件，首先通過距離和時(shí)間間隔去計(jì)算該點(diǎn)的實(shí)時(shí)速度，這里設(shè)定閾值為120km/h，超過閾值的點(diǎn)被視為異常點(diǎn)，給予舍棄。

定義4（軌跡高斯混合模型）在軌跡高斯混合模型中，每一個(gè)高斯過程函數(shù)可以表示軌跡的一個(gè)特征，即軌跡的特征是由多個(gè)模型線性組合而成的，假設(shè)生成來自M個(gè)相互獨(dú)立的高斯過程線性組合的混合模型G={GP1，GP2，…，GPM}。

本文提出的個(gè)性化導(dǎo)航［12］方法主要分為三個(gè)部分：1）軌跡索引；2）個(gè)性化路徑獲取；3）個(gè)性化路徑確定。推薦整體框架圖如圖3所示。

圖3 推薦框架圖

3.2 軌跡檢索模型

3.2.1 數(shù)據(jù)庫結(jié)構(gòu)設(shè)計(jì)

本文的軌跡數(shù)據(jù)存儲(chǔ)采用HBase［13］，首先在軌跡索引速度上，HBase性能遠(yuǎn)遠(yuǎn)好于傳統(tǒng)數(shù)據(jù)庫，尤其是在數(shù)據(jù)量很大的情況下，這種優(yōu)勢更加明顯，HBase的存儲(chǔ)形式是基于列存儲(chǔ)，每個(gè)列簇由不同文件保存，不同列簇是分開保存的；其次，HBase更適合存儲(chǔ)實(shí)時(shí)更新的數(shù)據(jù)。為了防止re?gion過多的情況，我們將所有車輛每一天的軌跡分段放在一個(gè)表中，rowkey使用時(shí)間戳+車牌的形式唯一標(biāo)識軌跡，這種方式方便對軌跡進(jìn)行快速索引［14］。

3.2.2 軌跡索引算法

軌跡檢索只需要找出同起點(diǎn)和終點(diǎn)的軌跡段即可，不需要考慮軌跡整體情況。軌跡索引算法如算法1所示。

給出一組起始和終止位置，我們可以在車輛的歷史軌跡中索引出滿足條件的軌跡段列表供個(gè)性化推薦使用。

3.3 偏好混合分布模型

3.3.1 用戶的行駛偏好挖掘

根據(jù)用戶的偏好進(jìn)行建模工作時(shí)，將路徑挖掘［15］出來的特征開銷越多，建模工作就越精確。Dai［9］等挖掘出距離、油耗和時(shí)間這三個(gè)開銷進(jìn)行建模，本文將在此基礎(chǔ)上增加轉(zhuǎn)向和紅綠燈這兩個(gè)開銷進(jìn)行進(jìn)一步建模。

3.3.2 距離開銷

整條路經(jīng)的距離就是兩兩軌跡點(diǎn)之間的距離和，軌跡點(diǎn)之間距離的計(jì)算本文借鑒了最廣泛的一種計(jì)算方法Haversin［16］，其計(jì)算方法如式（1）所示。

其中，r是地球半徑，φi和φj分別是兩點(diǎn)的緯度，λi和λj分別是兩點(diǎn)的經(jīng)度。

3.3.3 轉(zhuǎn)向開銷

汽車在筆直的路上行駛會(huì)節(jié)省油耗，反之如果是一條轉(zhuǎn)彎比較多的路徑就會(huì)相對耗油。軌跡路段轉(zhuǎn)角計(jì)算如圖4所示。

圖4 轉(zhuǎn)向示意圖

從上圖可以看出，A到B的一條軌跡，連續(xù)軌跡段在交匯點(diǎn)夾角表示為?，軌跡的夾角表示為Θ。a，b，c分別為夾角?的臨邊和對邊，則夾角?的計(jì)算方法如式（2）所示。

計(jì)算出?后，我們就可以得到轉(zhuǎn)角Θ的度數(shù)如式（3）所示。

3.3.4 油耗開銷

本文計(jì)算油耗開銷的方法使用SIDRA-Run?ning模型［17］，其中計(jì)算油耗公式如式（4）所示。

其中，F(xiàn)i是停留時(shí)間內(nèi)的油耗開銷，fr為其他時(shí)間內(nèi)的油耗開銷，xs為總的行駛路程。

3.3.5 時(shí)間開銷

一條路徑的時(shí)間開銷就是行駛完整條路經(jīng)所用的時(shí)間，也就是軌跡終點(diǎn)時(shí)間減去軌跡開始時(shí)間，計(jì)算公式如式（5）所示。

3.3.6 信號燈開銷

一般車輛在通過交通信號燈的時(shí)候總會(huì)產(chǎn)生一些消耗，所以一些司機(jī)在選擇路徑的時(shí)候?qū)⑼ㄟ^交通信號燈的開銷也考慮在內(nèi)。

3.4 偏好建模模型

為了形象地表示用戶的偏好，我們采取建模的方式。偏好建模離不開兩個(gè)定義：偏好率和偏好向量。偏好率就是用戶對一條軌跡兩個(gè)開銷的偏好比率，如式（6）所示。

其中ci(T)和cj(T)分別為對于軌跡T的兩個(gè)開銷。

用 戶 的 偏 好 向 量P=p1，p2，…，pm，其 中為開銷的個(gè)數(shù)，pi代表偏好比率的分布。對應(yīng)本文中提及的“距離，轉(zhuǎn)向，油耗，時(shí)間，信號燈”這五個(gè)開銷，得到10個(gè)偏好比率，如算法2。

混合高斯分布（Gaussian Mixture Model，GMM）［18］，用來表示復(fù)雜的分布［19］，文中每個(gè)偏好向量P中的每個(gè)pi都可以用混合高斯分布來表示。根據(jù)EM算法求出GMM參數(shù)如算法3。

為了計(jì)算用戶是否有明顯的偏好，本文將8000多輛車的軌跡分成兩部分，50%作為訓(xùn)練集，50%作為測試集。同時(shí)計(jì)算出偏好向量，然后進(jìn)行差異對比。計(jì)算差異的公式如式（7）所示。

計(jì)算出的差異越小，就代表軌跡的特征越明顯，個(gè)性化推薦就會(huì)越有意義。本文對8000多輛車進(jìn)行差異計(jì)算，我們從中抽取差異值小于0.1的5200輛車進(jìn)行個(gè)性化推薦實(shí)驗(yàn)。

3.5 獲取個(gè)性化路徑

根據(jù)索引出來的軌跡列表，進(jìn)行個(gè)性化路徑導(dǎo)航。主要分為兩個(gè)過濾過程：相似偏好過濾、相似時(shí)間過濾和頻繁度。

1）相似偏好過濾，用于不同的用戶在選擇軌跡的時(shí)候具有不同的偏好，所以本文選擇與用戶偏好最為相近的軌跡作為推薦軌跡。計(jì)算不同軌跡的偏好相似度用JS散度計(jì)算方法，如式（8）。

其中，P1、P2為推薦軌跡和真實(shí)軌跡的偏好比率，JS的分布值越小，代表軌跡就越相似，推薦的就越準(zhǔn)確。

2）相似時(shí)間過濾，基于不同的時(shí)間段，路況也會(huì)有所不同，所以我們把時(shí)間分為每天24個(gè)時(shí)間段，每個(gè)時(shí)間段一個(gè)小時(shí)，推薦軌跡時(shí)按照相似時(shí)間段優(yōu)先策略進(jìn)行推薦最合理。

3）雖然檢索出的TOP-K條軌跡都是最符合用戶偏好的，但是往往人們越是常走的就越是容易被大家認(rèn)可的，計(jì)算軌跡頻繁度［20］的公式如式（9）所示。

其中，m為組成路徑的路段個(gè)數(shù)，count為路段被經(jīng)過的次數(shù)。從TOP-K中選擇頻繁度較高的路線作為最終推薦路線。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)?zāi)繕?biāo)

1）本文數(shù)據(jù)存儲(chǔ)選擇大數(shù)據(jù)技術(shù)，首先通過在軌跡提取速度上證明本文的改進(jìn)方法具有一定價(jià)值。

2）本文的方法根據(jù)已有方法改進(jìn)而來，通過與原有方法進(jìn)行比對，證明本文的改進(jìn)方法有效。

4.2 評價(jià)指標(biāo)

1）評價(jià)指標(biāo)1

在不同的時(shí)間段對大數(shù)據(jù)集群的性能進(jìn)行測試，分別統(tǒng)計(jì)磁盤IO性能和集群網(wǎng)絡(luò)流量走勢。

2）評價(jià)指標(biāo)2

對于一段測試軌跡，用戶實(shí)際走的路線定為R1，個(gè)性導(dǎo)航路線定為R2，通過JAC的值來判斷兩段軌跡的相似性，JAC計(jì)算方法如式（10）所示。

3）評價(jià)指標(biāo)3

本文推薦方法與原有推薦方法準(zhǔn)確度比對，通過CR值來進(jìn)行分析，用戶實(shí)際走的路線定為R1，個(gè)性導(dǎo)航路線定為R2，原有推薦算法推薦路線為R3，若CR值大于1，則默認(rèn)準(zhǔn)確度有提升，計(jì)算方法如式（11）所示。

4.3 實(shí)驗(yàn)結(jié)果及有效性分析

實(shí)驗(yàn)所用的數(shù)據(jù)為全國私家車真實(shí)的軌跡數(shù)據(jù)，將具有偏好的5200輛車的歷史軌跡作為訓(xùn)練集，從中選取1000輛車的隨機(jī)軌跡數(shù)據(jù)作為驗(yàn)證集，再選取600輛車的隨機(jī)軌跡數(shù)據(jù)作為測試集。本文TOP-K中K的選值為5。

1）集群磁盤IO性能走勢圖如圖5所示。

圖5 集群性能圖

其中淺灰線表示讀數(shù)據(jù)，深灰線表示寫數(shù)據(jù)磁盤、網(wǎng)絡(luò)等指標(biāo)均能夠基本符合或靠近理論值。從上面兩張圖可以看出在集群進(jìn)行讀寫軌跡數(shù)據(jù)的時(shí)候，磁盤讀速度為135MB/s，寫速率為40MB/s。按照這樣來計(jì)算，持續(xù)一天不間斷的進(jìn)行導(dǎo)出，總數(shù)據(jù)量約在7.8T左右；持續(xù)一天不間斷的進(jìn)行導(dǎo)入，總數(shù)據(jù)量約在3.2T。性能遠(yuǎn)遠(yuǎn)超過傳統(tǒng)數(shù)據(jù)庫。

2）軌跡相似度JAC值對比結(jié)果如圖6所示。

圖6 軌跡相似度對比圖

從圖中可以看出本文所改進(jìn)的推薦軌跡與用戶時(shí)機(jī)選擇的軌跡更加相近，JAC的值大幅度提高代表著本文的推薦結(jié)果更有效。

3）推薦準(zhǔn)確度CR值對比結(jié)果如圖7所示。

圖7 推薦準(zhǔn)確度對比圖

將本文的推薦方法的準(zhǔn)確度與原文的相比，得到的平均值結(jié)果為1.102，說明在平均情況下，本文所推薦的路徑更能讓用戶滿意，更能符合用戶的需求。

5 結(jié)語

車輛導(dǎo)航與我們每個(gè)人的生活息息相關(guān)，它不僅僅可以在你迷路的時(shí)候提供一條最佳路線，還可以根據(jù)我們的駕駛偏好進(jìn)行個(gè)性化推薦，這也正是本文所研究的意義。本文與之前方法在軌跡相似度和推薦準(zhǔn)確度的對比上都有明顯的提高，相似度80%以上的軌跡提高了近一倍，推薦準(zhǔn)確度的平均值也穩(wěn)定在1以上，同時(shí)也保證了軌跡提取的實(shí)時(shí)性，這說明本文的方法具有一定的價(jià)值。

在接下來的工作中，我將著重在數(shù)據(jù)挖掘上進(jìn)行研究，本文所涉及到的用戶偏好還很局限，這就需要更多的軌跡挖掘來發(fā)現(xiàn)更多的軌跡特征，這些軌跡特征可以幫助我們更好地對用戶的偏好進(jìn)行建模，找到與用戶行駛習(xí)慣更相近的路線。同時(shí)，要想在功能上對導(dǎo)航進(jìn)行完善，行駛時(shí)間的預(yù)測也是很重要的功能，在本文研究的基礎(chǔ)上對行駛路線所花費(fèi)時(shí)間的預(yù)測也是日后工作的內(nèi)容，由于不同的時(shí)間會(huì)有不同的路況，再加上天氣的影響，行駛時(shí)間的預(yù)測也將面臨巨大的挑戰(zhàn)。在未來的車輛導(dǎo)航發(fā)展中，個(gè)性化路徑推薦將占有越來越重要的的地位，隨時(shí)間的推移，越來越多軌跡的出現(xiàn)也會(huì)幫助我們提取到越來越多的用戶特征，但同時(shí)也對軌跡的處理和存儲(chǔ)造成巨大的挑戰(zhàn)。但我相信，我們一定會(huì)逐漸優(yōu)化算法，提高性能，從而推薦出準(zhǔn)確率更高的個(gè)性化路線。