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

（西安交通大學軟件學院 西安 710049）

1 引言

隨著信息時代的到來，路徑導航［1］在我們日常生活中有著重要地位，私家車的出行活動離不開導航系統(tǒng)，與此同時人們對導航功能的需求也逐漸提高。過去的導航軟件只是根據我們所提供的起始和終止位置為我們推薦最優(yōu)的行駛路線，雖然方便實用，但往往所推薦的路線并不適用于所有人，這些導航軟件并沒有考慮到不同的司機有不同的駕駛習慣。如果導航可以自動獲取用戶的偏好，再根據偏好過濾出最符合用戶需求的推薦路線，那么就將極大程度提高導航軟件的導航質量。

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

2 相關工作

導航基本可以分為兩類：1）基于數字地圖的導航；2）基于軌跡數據的導航。

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

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

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

3 算法模型

3.1 基本概念及整體框架

定義1（軌跡序列）一段行駛軌跡是由無數個軌跡點有序組成的一組序列Trj={t1，t2，…，tn}，其t中包含了軌跡點的地理坐標信息。

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

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

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

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

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

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

圖3 推薦框架圖

3.2 軌跡檢索模型

3.2.1 數據庫結構設計

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

3.2.2 軌跡索引算法

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

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

3.3 偏好混合分布模型

3.3.1 用戶的行駛偏好挖掘

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

3.3.2 距離開銷

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

其中，r是地球半徑，φi和φj分別是兩點的緯度，λi和λj分別是兩點的經度。

3.3.3 轉向開銷

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

圖4 轉向示意圖

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

計算出?后，我們就可以得到轉角Θ的度數如式（3）所示。

3.3.4 油耗開銷

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

其中，Fi是停留時間內的油耗開銷，fr為其他時間內的油耗開銷，xs為總的行駛路程。

3.3.5 時間開銷

一條路徑的時間開銷就是行駛完整條路經所用的時間，也就是軌跡終點時間減去軌跡開始時間，計算公式如式（5）所示。

3.3.6 信號燈開銷

一般車輛在通過交通信號燈的時候總會產生一些消耗，所以一些司機在選擇路徑的時候將通過交通信號燈的開銷也考慮在內。

3.4 偏好建模模型

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

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

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

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

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

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

3.5 獲取個性化路徑

根據索引出來的軌跡列表，進行個性化路徑導航。主要分為兩個過濾過程：相似偏好過濾、相似時間過濾和頻繁度。

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

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

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

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

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

4 實驗結果及分析

4.1 實驗目標

1）本文數據存儲選擇大數據技術，首先通過在軌跡提取速度上證明本文的改進方法具有一定價值。

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

4.2 評價指標

1）評價指標1

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

2）評價指標2

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

3）評價指標3

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

4.3 實驗結果及有效性分析

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

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

圖5 集群性能圖

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

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

圖6 軌跡相似度對比圖

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

3）推薦準確度CR值對比結果如圖7所示。

圖7 推薦準確度對比圖

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

5 結語

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

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