[發明專利]一種出行軌跡聚類方法、裝置及設備

有效

• 申請號: 201710288748.X
• 申請日: 2017-04-27
• 公開（公告）號: CN107122461B
• 公開（公告）日: 2019-08-13
• 發明（設計）人: 徐麗麗;高睿
• 申請（專利權）人: 東軟集團股份有限公司
• 主分類號: G06F16/35
• 分類號: G06F16/35;G06F16/29
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 劉曉菲;王寶筠

本申請實施例公開了一種出行軌跡聚類方法、裝置及設備，減少出行軌跡聚類的計算量，提高出行軌跡的聚類效率。所述方法包括：獲取用戶的多條出行軌跡，所述多條出行軌跡均分別包括起點、終點以及位于二者之間的中間點；分別利用所述多條出行軌跡的起點和/或終點，對所述多條出行軌跡進行聚類，得到第一出行軌跡集合，所述第一出行軌跡集合包括起點和/或終點相匹配的出行軌跡，所述第一出行軌跡集合中出行軌跡的條數大于或等于第一閾值；利用各條出行軌跡中的中間點，對所述第一出行軌跡集合中的出行軌跡進行聚類，得到第二出行軌跡集合，所述第二出行軌跡集合包括起點和中間點均分別相匹配的出行軌跡，和/或，終點和中間點均分別相匹配的出行軌跡。

技術領域

本申請涉及大數據領域，尤其涉及一種出行軌跡聚類方法、裝置及設備。

背景技術

用戶的出行軌跡是用戶行為的重要組成部分，通過對用戶出行軌跡進行分析，可以得到很多重要的信息。用戶的出行軌跡通常是根據用戶在一段時間內的位置信息(例如GPS信息)得到，通過對位置信息進行分析，可以得到用戶經常走的路線，以便預先為用戶推送關于該路線的路況，以幫助用戶規避擁堵風險，或者可以為用戶推送經常走的路線的周邊美食、商家信息等。此外，還可以為路線相同的用戶進行好友推薦、推送拼車等服務。那么就涉及到如何從大量的用戶出行軌跡中找到相同的出行軌跡的問題，所謂相同出行軌跡的含義是指兩條及以上出行軌跡的起點、終點以及中間點均分別相匹配，而且出行軌跡的方向相同。

現有技術通過密度聚類的方法將相同的出行軌跡聚為一類。具體步驟如下：首先，將每條出行軌跡分別看作是一個具有方向和長度的2n維向量，n為出行軌跡中位置信息采樣點的個數。然后，計算兩兩向量之間的歐式距離和夾角，若兩個向量之間的歐式距離滿足距離條件，且二者之間的夾角滿足夾角條件，則認為這兩條出行軌跡相同，并將這兩條出行軌跡聚為一類。

現有技術的這種聚類方法計算量大，效率較低，尤其是出行軌跡中采樣點的個數較多的時候。所以目前需要一種計算量較小、效率較高的出行軌跡聚類方法。

發明內容

本申請實施例提供一種出行軌跡聚類方法、裝置及設備，減少出行軌跡聚類的計算量，提高出行軌跡的聚類效率。

本申請實施例提供了一種出行軌跡聚類方法，所述方法包括：

獲取用戶的多條出行軌跡，所述多條出行軌跡均分別包括起點、終點以及位于二者之間的中間點；

分別利用所述多條出行軌跡的起點和/或終點，對所述多條出行軌跡進行聚類，得到第一出行軌跡集合，所述第一出行軌跡集合包括起點和/或終點相匹配的出行軌跡，所述第一出行軌跡集合中出行軌跡的條數大于或等于第一閾值；

利用各條出行軌跡中的中間點，對所述第一出行軌跡集合中的出行軌跡進行聚類，得到第二出行軌跡集合，所述第二出行軌跡集合包括起點和中間點均分別相匹配的出行軌跡，和/或，終點和中間點均分別相匹配的出行軌跡。

可選的，所述中間點包括轉彎點，所述轉彎點與前第n個點的連線和所述轉彎點與后第n個點的連線之間的夾角在預設夾角范圍內，所述n為大于或等于1的整數。

可選的，所述方法還包括：

從所述第一出行軌跡集合中確定由具有相同個數的中間點的出行軌跡形成的第三出行軌跡集合；

所述利用各條出行軌跡中的中間點，對所述第一出行軌跡集合中的出行軌跡進行聚類包括：

利用各條出行軌跡中的中間點，對所述第三出行軌跡集合中的出行軌跡進行聚類。

可選的，所述方法還包括：

若所述第三出行軌跡集合中出行軌跡的條數大于或等于第二閾值，則執行利用各條出行軌跡中的中間點，對所述第三出行軌跡集合中的出行軌跡進行聚類的步驟。