[發明專利]一種基于密度峰值的自適應時空軌跡聚類方法

在審

• 申請號: 202011001436.4
• 申請日: 2020-09-22
• 公開（公告）號: CN112070179A
• 公開（公告）日: 2020-12-11
• 發明（設計）人: 陳犖;陳南宇;熊偉;鐘志農;吳燁;楊岸然;賈慶仁;歐陽雪;曹競之
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京市京大律師事務所 11321
• 代理人: 方曉明

本發明公開的屬于軌跡模擬技術領域，具體為一種基于密度峰值的自適應時空軌跡聚類方法，提出在軌跡間相似性度量方法中加入對時間維度的度量，采用Hausdorff距離通過生成時間同步子軌跡來計算軌跡間的整體相似度。該基于密度峰值的自適應時空軌跡聚類方法，能夠體現軌跡數據的時間同步性，在密度峰值聚類中引入KNN算法，重新定義了局部密度計算方法，解決了密度峰值聚類對參數敏感問題，同時提高了聚類質量，在聚類中心的選擇上提出了穩定的自適應選擇算法，理論分析與基于真實數據集的實驗結果證明了ATDP算法的穩定性和有效性，能夠在不同的應用背景下取得較好的聚類效果，準確反映移動目標的整體運動趨勢。

技術領域

本發明涉及軌跡模擬技術領域，具體為一種基于密度峰值的自適應時空軌跡聚類方法。

背景技術

不斷發展的定位技術和移動計算技術產生了大量的帶有時間戳的軌跡數據，這些時空數據具有豐富的隱含信息，比如漁船航行的軌跡數據能夠反映不同地區漁民的捕魚的方式和頻率作息，動物遷徙的軌跡數據能夠體現不同時間段內各個物種的整體運動趨勢，颶風登陸軌跡數據能夠揭示颶風登陸過程中的移動模式，軌跡聚類是聚類分析在時空軌跡上的擴展,通過將具有相同或相似屬性的時空對象進行分類，能夠分析出移動目標的運動規律，發現物體的運動模式，進而能夠預測其運動趨勢，在應急救援，交通規劃，災害預警等領域有著廣泛的應用。

傳統的軌跡聚類方法可以分為基于劃分的方法，基于網格的方法，基于層次的方法和基于密度的方法，對于時空軌跡數據聚類，目前大部分算法并沒有考慮時間維度對軌跡間相似性的影響，部分算法則是采用滑動窗口模型對固定窗口時間內的軌跡進行增量式的聚類，整個過程需要多次進行聚類計算，時間復雜度較高。

為解決時空軌跡聚類問題，本文提出在軌跡間相似性度量方法中加入對時間維度的度量，采用Hausdorff距離通過生成時間同步子軌跡來計算軌跡間的整體相似度，采用密度峰值聚類算法對軌跡進行聚類分析，為解決密度峰值聚類算法存在的密度核選取問題，引入KNN算法重新定義了局部密度，提高了聚類性能，為減少聚類過程中的人工干預，提出了一種穩定有效的聚類中心自動選擇方法，為實現聚類結果的動態可視化效果，提出了一種代表軌跡生成算法，能夠生成帶有時間戳的代表軌跡，并以向心參數化Catmull-Rom曲線對代表軌跡數據進行擬合，生成平滑曲線以更好地體現軌跡的運動趨勢。

發明內容

本部分的目的在于概述本發明的實施方式的一些方面以及簡要介紹一些較佳實施方式。在本部分以及本申請的說明書摘要和發明名稱中可能會做些簡化或省略以避免使本部分、說明書摘要和發明名稱的目的模糊，而這種簡化或省略不能用于限制本發明的范圍。

鑒于上述和/或現有軌跡聚類方法中存在的問題，提出了本發明。

因此，本發明的目的是提供一種基于密度峰值的自適應時空軌跡聚類方法，能夠體現軌跡數據的時間同步性，在密度峰值聚類中引入KNN算法，重新定義了局部密度計算方法，解決了密度峰值聚類對參數敏感問題，同時提高了聚類質量，在聚類中心的選擇上提出了穩定的自適應選擇算法，理論分析與基于真實數據集的實驗結果證明了ATDP算法的穩定性和有效性，能夠在不同的應用背景下取得較好的聚類效果，準確反映移動目標的整體運動趨勢。

為解決上述技術問題，根據本發明的一個方面，本發明提供了如下技術方案：

一種基于密度峰值的自適應時空軌跡聚類方法，其包括以下步驟：

S1：輸入軌跡數據T、參數K和q；

S2：由基于時間約束的Hausdorff距離度量算法計算軌跡間相似度，生成相似度矩陣M；

S3：由相似度矩陣M計算局部密度p_i，并且計算δ_i；

S4：計算γ_i，生成決策圖，并獲取決策臨界點θ_c，選取聚類中心p_c；