[發明專利]一種基于車輛歷史軌跡的個性化路線推薦方法

有效

• 申請號: 201711266923.1
• 申請日: 2017-12-05
• 公開（公告）號: CN108303108B
• 公開（公告）日: 2020-05-22
• 發明（設計）人: 易先鋒;袁華
• 申請（專利權）人: 華南理工大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 馮炳輝

1.一種基于車輛歷史軌跡的個性化路線推薦方法，其特征在于，包括以下步驟：

1)對軌跡數據進行預處理：包括軌跡恢復、軌跡分割、去除浮動點、地圖匹配；

2)分場景進行路徑時間預測，熱門路徑采用KNN算法預測，非熱門路徑采用GBDT預測模型；

3)獲取用戶每條軌跡相對偏好，并對用戶所有軌跡根據其相對偏好進行聚類，獲得用戶偏好場景；

4)在每個偏好場景下，利用最優化的思想，采用梯度下降的方法計算用戶的偏好向量；

5)利用協同過濾思想，通過尋找相似用戶，利用相似用戶的歷史軌跡進行推薦；如果相似用戶沒有相應歷史軌跡，則建立多權重路網圖，根據用戶偏好向量，尋找一條開銷最小的路徑。

2.根據權利要求1所述的一種基于車輛歷史軌跡的個性化路線推薦方法，其特征在于：在步驟1)中，首先進行軌跡恢復，軌跡原始數據大多是雜亂無章的GPX點數據，需要按照時間以及司機這兩個屬性來恢復原始軌跡；接著進行軌跡分割，當軌跡中某段停留時間超過預設閾值后，分割成兩條獨立路徑來研究；再接著進行異常值處理，兩個點之間的速度超過正常范圍，就是異常值，需要去除；最后進行地圖匹配，采用HMM算法將GPX點匹配到實際路網上。

3.根據權利要求1所述的一種基于車輛歷史軌跡的個性化路線推薦方法，其特征在于：在步驟2)中，采用分場景分別預測的方法，對于熱門路徑采用KNN預測算法；而對于其它路徑則采用GBDT預測模型進行預測，具體步驟如下：

2.1)對于所有軌跡的起點、終點進行K-MEANS聚類，得到熱門區域；

2.2)對于熱門區域之間的軌跡再進行K-MEANS聚類，得到熱門軌跡；

2.3)對于每一條熱門軌跡，分別采用KNN預測算法進行預測，特征為：“是否周末(是，否)，時間段(每30分鐘為一個時間段，共48個時段)，天氣狀況(晴，多云，大霧，小雨，大雨，雪天)”，對特征采用“one-hot”處理，標簽為時間；調整K的個數，使得預測效果達到一個最佳狀態；

2.4)對于其它任意非熱門路徑，采用KNN預測代價很高，因為KNN尋找相似軌跡的時間開銷成本很大，因此使用GBDT預測模型，雖然預測精度不如KNN，但是對任意一條路徑都能夠預測，首先構造特征，特征為：“路徑上紅綠燈數、路徑上轉彎數、路徑最高時速限制、道路級別、車主ID、是否周末，時間段，軌跡總長度，軌跡GPX點個數，軌跡起始位置，軌跡中間位置，軌跡結束位置，起始點與城市中心距離，中間點與城市中心距離，終點與城市中心距離，天氣狀況”；其中非連續性特征“道路級別(高速、省道、普通道路)、車主ID、是否周末、時間段”采用“one-hot”處理；對于模型采用十折交叉驗證，不斷調整樹的個數、深度、學習率參數，具體方法為采用單一變量原則，最終使得模型預測效果達到一個最優狀態，將此預測模型序列化保存下來。

4.根據權利要求1所述的一種基于車輛歷史軌跡的個性化路線推薦方法，其特征在于：在步驟3)中，首先獲取同起點終點所對應的軌跡的各個開銷的最小值，然后求取用戶的每一條軌跡針對每一個開銷的相對偏好比率，最后對用戶所有軌跡的相對偏好進行聚類得到偏好場景，具體步驟如下：

3.1)首先獲取同起點終點所對應的軌跡的各個開銷的最小值；靜態開銷，能夠利用Dijkstra算法獲得；對于動態開銷，檢索出歷史軌跡中所有同起點終點的軌跡，然后利用步驟2)中的預測模型分別預測出用戶在每一條路徑上的動態開銷值，取最小值；這樣就得到了各個開銷的最小值，記為PC_min，PC_min＝{pc_1min,pc_2min,...,pc_mmin}；

3.2)對用戶偏好進行聚類；通過下面這個公式，計算用戶當前軌跡P對于第j開銷的偏好比率PR_j，式中pc_jmin是對應用戶當前軌跡的同起點終點的所有軌跡中，第j開銷的最小值，pc_j是用戶當前軌跡的第j開銷值，PR_j越大，說明用戶越偏好于這一個開銷；然后對用戶的偏好進行聚類，聚類方法如下：

3.2.1)對偏好比率PR排序，偏好比率越大的排在越前面；

3.2.2)利用最長公共前綴來進行聚類。