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

有效

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

1.一種基于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點密度；最后找出該簇中密度最大即所含鄰居節點數最多的點作為該簇的簇心；

(5)將簇心集合重新寫入軌跡點隊列中再次聚類，并設定載客熱點數量范圍，直到最終簇心集合數量即載客熱點數量達到設定的范圍。

2.根據權利要求1所述的基于BDCH-DBSCAN的出租車載客熱點識別方法，其特征在于，步驟(1)中剔除干擾數據的方法為：設定出租車最大行駛速度為Vmax；在GPS數據軌跡中提取一段時間內的GPS數據點，記為GPS軌跡序列T{p₁,p₂,...,p_k}，選擇保留滿足下式的GPS軌跡序列：

式中：distance(p_i+1,p_i)表示p_i+1到p_i的歐式距離；p_i,t表示采集p_i軌跡點的時間，(p_i+1,t-p_i,t)表示p_i+1點到p_i點之間的時間差；

若p_i不滿足上式，則p_i為跳變點，剔除該GPS數據軌跡。

3.根據權利要求1或2所述的基于BDCH-DBSCAN的出租車載客熱點識別方法，其特征在于，步驟(4)找出簇心的方法為：在獲取類簇操作時，記錄每一簇內節點的鄰居點集中點的個數；對每一簇內的點進行密度計算，所述密度為該點的鄰居點個數占簇內總點數的比例；找出簇中密度最大即所含鄰居節點數最多的點，作為該簇的簇心。

4.根據權利要求1或2所述的基于BDCH-DBSCAN的出租車載客熱點識別方法，其特征在于，步驟(4)中確定兩個數據點之間的曲面距離的方法為：

設兩個數據點之間的曲面距離為L，則：

a＝lat₁-lat₂

b＝lon₁-lon₂

式中，lat₁表示第一個數據點的緯度，lat₂表示第二個數據點的緯度，lon₁表示第一個軌跡點的經度，lon₂表示第二個軌跡點的經度，R表示地球半徑。

5.根據權利要求1或2所述的基于BDCH-DBSCAN的出租車載客熱點識別方法，其特征在于，步驟(1)中的GPS數據點還包括簇序號、簇熱點中心標識參數；所述簇序號為類簇編號，是每一類簇唯一的標識，用于區分各個類簇；所述簇熱點中心標識參數為標記計算出的類簇中心點。