[發明專利]一種軌跡聚類的方法、設備及存儲介質

有效

• 申請號: 201910936730.5
• 申請日: 2019-09-29
• 公開（公告）號: CN110826594B
• 公開（公告）日: 2022-08-09
• 發明（設計）人: 張平
• 申請（專利權）人: 成都華為技術有限公司
• 主分類號: G06V10/762
• 分類號: G06V10/762;G06K9/62
• 代理公司: 深圳市深佳知識產權代理事務所(普通合伙) 44285
• 代理人: 吳磊

一種軌跡聚類的方法，包括：獲取目標軌跡集合，其中包括多條軌跡；根據目標軌跡集合中每條軌跡的位置數據將目標軌跡集合中的軌跡進行劃分，得到多個目標軌跡子集；分別計算每個目標軌跡子集中不同軌跡之間的相似度；根據每個目標軌跡子集中不同軌跡之間的相似度與預設相似度閾值分別對每個目標軌跡子集中的軌跡進行聚類，得到聚類結果。本方案根據目標軌跡集合中的軌跡的位置數據將目標軌跡集合中的軌跡分到相應的不同目標軌跡子集中。對不同的目標軌跡子集進行軌跡聚類時，無須考慮目標軌跡子集之外的其它軌跡，可以快速計算軌跡相似度，降低了相似軌跡的發現開銷，從而降低了軌跡聚類的整體計算開銷。

技術領域

本申請涉及數據處理領域，尤其涉及一種軌跡聚類的方法、設備及存儲介質。

背景技術

位置傳感器是一種可以對行人、車輛等可移動個體進行定位的傳感器。在目前，全球定位系統(global positioning system，GPS)設備是最典型且常用的位置傳感器。此外，監控攝像頭、無線上網(wifi)探針、手機基站等具有固定位置的個體識別設備也可以看作位置傳感器，因為它們也能夠通過監聽的方式提供個體位置信息。出于城市智能化管理、安防等需求，利用位置傳感器收集各種實體(例如行人、車輛等)的時空位移數據，并且對這些時空位移數據進行數據挖掘分析的技術已經逐漸發展成熟，且應用前景廣闊，可以為城市安全、商業活動等方面的決策提供技術支持。

每個實體被位置傳感器記錄而生成的時空位移數據可以稱為軌跡。顧名思義，軌跡即一個實體隨著時間變化，其位置發生改變形成的路徑。軌跡由多個軌跡點組成，其中，每一個軌跡點表示位置傳感器對實體位置的一次記錄，描述了“某實體”在“某時刻”位于“某地點”。目前，軌跡聚類是數據挖掘領域內的一個研究熱點，軌跡聚類即將大量的軌跡中相似度符合一定條件的軌跡進行匯總。軌跡聚類在疑犯追蹤、異常行為發現、人流車流分析等方面具有重大的研究意義。例如，在治安應用場景下，同行人分析是軌跡聚類的一個具體應用，它可以幫助警方以現有的軌跡(可以是案犯同伙或者受害人的)作為查詢目標，查找與查詢目標相似度較高的軌跡，從而幫助警方進行同伙分析、嫌疑人確定等工作。

軌跡相似度的計算是軌跡聚類中的重點也是難點?，F有方法中使用的軌跡大多是由GPS設備生成的，軌跡點可能是任意位置，這導致在進行軌跡相似度計算時，需要枚舉兩條軌跡中每一對軌跡點的在空間上的距離關系，以及在時間上的時差關系，因此計算難度較高。在現有的軌跡聚類方法中，進行軌跡聚類時，需要對大量的軌跡進行軌跡相似度計算，從而在這些軌跡中發現相似軌跡，因此需要進行相似度計算的軌跡數量往往是十分龐大的，相似軌跡的發現開銷過大導致軌跡聚類的計算開銷過大，聚類效率較低。

發明內容

本申請實施例提供了一種軌跡聚類的方法及軌跡聚類設備，可以降低軌跡聚類時所需的計算開銷，提高聚類效率。

有鑒于此，本申請第一方面提供一種軌跡聚類的方法，該方法包括：獲取目標軌跡集合，該目標軌跡集合中包括多條軌跡，每條軌跡包括多個軌跡點，每個軌跡點攜帶位置信息和時間信息，在相同的區域中被采集得到的軌跡點的位置信息是相同的；根據該目標軌跡集合中每條軌跡的位置數據將目標軌跡集合中的軌跡進行劃分，得到多個目標軌跡子集，目標軌跡集合中任意兩條軌跡劃分到同一個目標軌跡子集的概率與該兩條軌跡對應的位置數據之間的相似度相關聯；分別計算每個目標軌跡子集中不同軌跡之間的相似度；根據每個目標軌跡子集中不同軌跡之間的相似度與預設相似度閾值分別對每個目標軌跡子集中的軌跡進行聚類，得到聚類結果，該聚類結果用于指示不同軌跡之間是否存在關聯關系。

由上述第一方面可知，由于本方案中針對目標軌跡集合中的軌跡的位置數據對目標軌跡集合進行劃分，可以實現以較高的概率將目標軌跡集合中位置數據相似度較高的軌跡分到相同的目標軌跡子集中。對不同的目標軌跡子集進行軌跡聚類時，無須考慮目標軌跡子集之外的其它軌跡，軌跡的相似度可以得到快速計算，降低了相似軌跡的發現開銷。