[發明專利]基于BDCH-DBSCAN的出租車載客熱點識別方法

有效

• 申請號: 201810130946.8
• 申請日: 2018-02-08
• 公開（公告）號: CN108415975B
• 公開（公告）日: 2021-07-27
• 發明（設計）人: 高尚兵;黃子赫;李木子;陳超;李勝東;周君;嚴云洋;陳曉兵;潘登峰;龔野
• 申請（專利權）人: 淮陰工學院
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/28
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 呂朦

本發明公開了一種基于BDCH?DBSCAN的出租車載客熱點識別方法，首先提供大量出租車GPS數據軌跡，從中剔除干擾數據；提取GPS數據軌跡中的上車數據點和下車數據點；對提取的數據點進行多線程分塊聚類，并采用DBSCAN算法分離出核心點，并獲取核心點的鄰居節點集，對核心點進行擴展簇操作，擴展簇指對核心點的鄰居點進行類簇劃分，并將大于最小簇點數的鄰居核心點及其領域添加進簇中；根據兩點之間的曲面距離找出掃描半徑內的鄰居節點，找出每個簇中的最大密度點，作為簇心，并對簇心集合再次循環聚類直至集合數量、精度滿足要求。本發明可以適應大規模數據、便于識別類簇中心、多線程聚類速度快、精確度高。

技術領域

本發明涉及交通大數據領域，尤其涉及一種基于BDCH-DBSCAN的出租車載客熱點識別方法。

背景技術

現今GPS軌跡數據作為交通大數據的一種，已被廣泛應用。大量出租車上下客點形成的上下客熱點對分析居民出行的時空分布、城市交通規劃有著重要意義。

現有技術中，基于出租車載客熱點的提取主要包括兩種方式：(1)通過劃分網格單元格的方式：如基于路網約束的DBSCAN改進算法，基于網格的K-Means交通熱區識別算法，利用數據場勢值閾值法探測軌跡點的聚集模式，提取熱點區域。(2)基于無監督的聚類方式：如結合當前環境軌跡特征的DBSCAN算法，基于MapReduce的從出租車軌跡提取熱點區域的分布并行算法，GBADBSCAN上下客熱點生成聚類算法。這些算法在聚類熱點區域中，均取得了較好的檢測效果，但是在大數據處理精確度上仍存在不足。

DBSCAN是最常用的一種基于密度的聚類方法。傳統的DBSCAN算法在聚類海量出租車行車軌跡數據點具有無法適應大規模數據、無法識別類簇中心、過程式單線程聚類速度慢等局限性。DBSCAN算法的基本原理是通過設定掃描半徑Eps和最小包含點數MinPts來找出數據點集合中密度相連的最大集合。在半徑Eps內含有超過MinPts數目的點叫做核心點；在半徑Eps內含有小于MinPts數目，并且是在核心點的鄰域內的點叫做邊界點；既不是核心點也不是邊界點的點叫做噪音點。但是，該方法只是簡單的考慮了數據點之間的距離和每個核心點所需要的最小包含點數，在數據量大的情況下，經常會出現簇中軌跡點過多、覆蓋面積較廣、可視化效果差、熱點無法被精確找到等問題。

發明內容

發明目的：為了解決現有技術存在的問題，既適用于大規模數據又能高效準確的找出類簇簇心，本發明提供一種基于BDCH-DBSCAN的出租車載客熱點識別方法。

技術方案：一種基于BDCH-DBSCAN的出租車載客熱點識別方法，包括以下步驟：

(1)提供大量出租車GPS數據軌跡，從中剔除干擾數據，每個GPS數據軌跡包括多個GPS數據點，每個GPS數據點包括載客狀態、經度、緯度；

(2)提取GPS數據軌跡中的上車數據點和下車數據點，若在該點之前的GPS數據點的載客狀態為空載狀態，在該點之后的GPS數據點的載客狀態為載客狀態，則判斷該點為上車數據點；若在該點之前的GPS數據點的載客狀態為載客狀態，在該點之后的GPS數據點的載客狀態為空載狀態，則判斷該點為下車數據點；

(3)對提取的上車數據點和下車數據點聚類進行分塊循環聚類，將數據以5000個為一組放入線程池中進行聚類，聚類設定掃描半徑Eps和最小簇點數MinPts，采用DBSCAN算法分離出核心點，并獲取核心點的鄰居節點集，所述鄰居節點集是以核心點為中心在半徑Eps范圍內的所有點的集合，鄰居節點集中的點為鄰居節點，對核心點進行擴展簇操作，擴展簇指對核心點的鄰居節點進行類簇劃分，類簇劃分指將每個點分配到對應點集內，由此形成一個個簇，并將大于MinPts的鄰居節點及其領域添加進簇中；

(4)找出簇心：根據上車數據點和下車數據點的經度、緯度，確定兩個數據點之間的曲面距離用來發現掃描半徑Eps內的鄰居節點；對每一個簇內點P進行密度計算，點P的鄰居節點個數占簇內總點數的比例記為P點密度；最后找出該簇中密度最大即所含鄰居節點數最多的點作為該簇的簇心；