[發明專利]一種基于密度聚類的熱點路徑分析方法

有效

• 申請號: 201910231648.2
• 申請日: 2019-03-26
• 公開（公告）號: CN110135450B
• 公開（公告）日: 2020-06-23
• 發明（設計）人: 徐欣;刁聯旺;易侃;李青山
• 申請（專利權）人: 中電萊斯信息系統有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 江蘇圣典律師事務所 32237
• 代理人: 胡建華;于瀚文

本發明公開了一種基于密度聚類的熱點路徑分析方法，針對將目標路徑表征為由若干路徑點構成的路徑點集合，構建相似度距離矩陣，比較兩兩路徑點集合之間的相似度，基于相似度距離矩陣、距離門限ε與密度門限MinPts采用密度聚類迭代式地計算路徑點集合構成的簇，最后將各簇的路徑集眾數的作為目標熱點路徑輸出。本發明的優點：(1)提出了針對目標路徑點集合的相似度比較方法；(2)密度門限MinPts的選擇具有一定的靈活性、魯棒性；(3)計算成本低，實現方法工程化。

技術領域

本發明涉及目標路徑分析挖掘領域，尤其涉及一種基于密度聚類的熱點路徑分析方法。

背景技術

眾所周知，當今目標路徑相關測量數據量越來越大，僅靠人工進行分析處理難以及時、準確的總結出目標路徑規律，難以及時支撐高實時的輔助決策。傳統的目標路徑分析預測技術大多針對目標位置測量數據，沒有基于關鍵路徑點進行分析，無法聚焦高層次的路徑特征、提取多粒度的目標路徑模式，計算成本高。

發明內容

發明目的：針對現有技術的問題，本發明提出一種基于密度聚類的熱點路徑分析方法，包括如下步驟：

步驟1，針對將目標路徑表征為由若干路徑點構成的路徑點集合，構建相似度距離矩陣；

步驟2，比較兩兩路徑點集合之間的相似度，基于相似度距離矩陣、距離門限ε與密度門限MinPts從路徑點集合中挖掘出核心路徑集，再根據針對核心路徑集的“直接密度可達”關系，采用密度聚類迭代式地生成由核心路徑集聚合成的簇；

步驟3，將各簇的路徑點集合眾數作為目標熱點路徑輸出。

相比傳統密度聚類中的相似度距離矩陣，步驟1中矩陣的行、列對應的不再是固定維數的向量，而是非固定長度的路徑點集合，步驟1包括：

步驟1-1，設定采集了n條目標路徑相對應的n個路徑點集合，每個路徑點集合對應一條目標路徑，而路徑點集合中的每個元素為對應目標路徑中的一個路徑點，則定義第i個路徑點集合P_i和第j個路徑點集合P_j之間的Jaccard距離JaccardDist(P_i,P_j)為：

步驟1-2，對路徑點集合排序：將n個路徑點集合首先按集合大小由大到小、其次按索引值由小到大排序，記為P₁、P₂、…、P_n，滿足|P₁|≥|P₂|≥…≥|P_n|；

步驟1-3，初始化相似度距離矩陣：設定距離門限ε，其取值范圍為0ε1，一般情況下可以取值為路徑點集合最近鄰距離的均值，即：

初始化相似度距離矩陣DistArray為空，其矩陣大小n×n，即矩陣的行數和列數均為n，因為相似度距離矩陣關于多角線對稱，所以只保留上三角部分。

步驟2創新性地提出了一種基于路徑點集合大小與距離門限ε的相似度比較策略(步驟2-3)，大大簡化了兩兩路徑點集合的相似度比較計算成本，并在集合型相似度距離計算的基礎上進一步創新性地提出了針對路徑點集合的“ε鄰域”、“核心路徑集”、“直接密度可達”、“間接密度可達”、“密度相連”的概念(步驟2-8、2-9)，從而將傳統針對固定維數向量的密度聚類規則拓展到集合型數據上，步驟2包括：

步驟2-1，設置當前集合索引：設置當前路徑點集合索引s＝1；

步驟2-2，設置待比較集合索引：設置待比較路徑點集合索引t＝s+1；