基于GeoHash和HDBSCAN的共享單車停車擁擠區域識別

洪文興，陳明韜，劉伊靈，朱嘉誠，王明磊

(1.廈門大學航空航天學院，福建廈門361102；2.廈門大學數學科學學院，福建廈門361005；3.北京航空航天大學軟件學院，北京100083)

共享單車作為一種“互聯網+”時代背景下的共享經濟的產物，具備零排放無污染、騎行便捷等特點，有助于解決市民出行的“最后一公里”問題[1].隨著以摩拜、哈啰為典型代表的共享單車的出現，騎行成為了一種出行習慣，但是共享單車的停車擁擠現象也隨之出現.停車擁擠現象會對城市交通帶來很大的壓力，因此如何對共享單車數據進行分析與挖掘，有效地定位共享單車早高峰時間的停車擁擠區域，成為緩解城市交通壓力的關鍵所在.

隨著共享單車的興起，越來越多的國內外學者從不同的視角對共享單車進行了研究，研究方向主要集中在共享單車的調度和優化策略[2-6]，共享單車的需求預測分析[7-11]，以及共享單車停車點的選址等[12-14].但是目前對如何高效地定位共享單車停車擁擠區域的研究相對較少，因此本文對共享單車的停車擁擠區域識別進行了研究.在其他不同的研究領域，劉濤等[15]使用改進后的DBSCAN(density-based spatial clustering of application with noise)聚類算法對某一海域中的船舶動態數據進行聚類，分析與識別出潛在的擁擠區域；邵敏華等[16]使用K均值(K-means)聚類算法對上海市中心城區道路網絡進行擁擠區域的聚類識別.但劉濤等[15]使用的改進后的DBSCAN聚類算法對輸入參數非常敏感，細微的參數變化會導致截然不同的聚類結果，邵敏華等[16]使用的K-means聚類算法需要事先指定聚類數目K，K值不同也會帶來聚類結果的巨大差異.

針對上述不足，本文在對共享單車訂單數據和停車圍欄數據進行數據預處理的基礎上，采用GeoHash算法處理經緯度坐標和計算判斷共享單車開關鎖訂單屬于哪個停車圍欄，并利用HDBSCAN(hierarchical density-based spatial clustering of application with noise)聚類算法將停車圍欄聚類為停車區域，并提出了基于“留存流量與留存密度的綜合指標”的停車擁擠區域識別方法，該方法克服了傳統的僅考慮單一指標的基于“留存流量”或“留存密度”方法所帶來的局限性.本研究為城市交通管理和共享單車的調度優化提供了數據支持，具備一定的理論與實際意義.

1 數 據

1.1 數據描述

本文采用的數據集為某市某品牌共享單車訂單數據以及共享單車停車圍欄數據.其中共享單車訂單數據記錄了每輛共享單車的開關鎖的時間、開關鎖狀態以及所在的經緯度坐標，時間范圍為2020年12月22日至2020年12月25日(共計4 d，均為工作日)；共享單車停車圍欄數據記錄了停車圍欄的名稱以及構成該停車圍欄的5個頂點經緯度坐標(第一個坐標和最后一個坐標經緯度相同).兩個數據集的字段信息如表1和表2所示.

表1 共享單車訂單數據字段信息

表2 共享單車停車圍欄字段信息

1.2 數據預處理

由于可能存在信號不良、單車故障和用戶誤操作等問題導致共享單車與服務器出現通信異常的情況，從而產生錯誤的訂單數據[17]，因此需要對原始的共享單車訂單數據進行預處理，以消除誤差影響.數據預處理主要包括以下兩個方面：

1) 由于早高峰的時間段為早上7:00—9:00，因此將訂單數據中的狀態更新時間不在該時間段內的數據剔除.

2) 對于連續開鎖或連續關鎖的訂單數據，即同一個共享單車標識ID的‘LOCK_STATUS’字段出現連續多行數據為0或為1，表示車輛鎖具發生了故障，要對這些異常數據進行處理，以免對后續分析造成影響：針對連續的開鎖數據，僅保留第一條數據；針對連續的關鎖數據，僅保留最后一條數據.

1.3 GeoHash算法處理經緯度坐標

GeoHash算法是由Gustavo Niemeyer所提出的一種基于地理網格劃分的地理數據編碼技術[18]，通過兩次編碼過程將二維的經緯度坐標轉化為一個可進行前綴匹配信息檢索的一維字符串編碼[19]，字符串越長，編碼精度越高.

GeoHash算法的實現過程是先將經緯度表示的范圍視為二維平面矩形，之后分別對經度和緯度進行類二分法劃分，若目標經緯度在劃分區域內，則賦值為1，否則賦值為0，直至滿足設定的精度要求，得到一個二進制的編碼.隨即將奇數位作為緯度、偶數位作為經度，合并經緯度編碼.最后使用Base32編碼方式進行轉換，即可得到GeoHash編碼.

共享單車訂單數據和停車圍欄數據中有關地理位置的信息通過經緯度坐標保存，若直接使用經緯度坐標實現后續的停車圍欄聚類和擁擠區域的識別，在數據量較大的情況下由于索引利用率低等原因，會造成搜索效率低下等不良影響.因此本文使用GeoHash算法對經緯度坐標進行處理.共享單車訂單和停車圍欄數據中的經緯度坐標轉換為GeoHash編碼的流程圖如圖1所示.

圖1 GeoHash編碼算法流程圖Fig.1Flow chart of GeoHash encoding algorithm

本文使用Python語言來實現GeoHash編碼算法.對共享單車停車圍欄數據進行分析計算后發現，最長的圍欄長度約為84 m，因此使用7位的GeoHash編碼長度恰能保證圍欄的每一個頂點都落在同一塊GeoHash算法劃分的區域內.以經緯度坐標(118.126 619° E,24.495 537° N)為例，在運行GeoHash編碼算法后，即可得到7位的GeoHash編碼為‘wsk5253’.對共享單車訂單數據中的‘LATITUDE’和‘LONGITUDE’字段以及共享單車停車圍欄數據的‘FENCE_LOC’字段使用GeoHash編碼算法，可將經緯度信息轉換為GeoHash字符串編碼信息.之后，按順序查詢共享單車開關鎖訂單和停車圍欄某個頂點的GeoHash編碼相同的數據，再通過經緯度坐標計算共享單車到這幾個停車圍欄中心的距離，距離最小的停車圍欄即確定為該單車所屬的停車圍欄，為后續停車擁擠區域的識別打下基礎.

2 共享單車停車圍欄聚類

停車擁擠區域的識別需要先將眾多的共享單車停車圍欄聚類為停車區域.常用的聚類方法有：K-means聚類和DBSCAN聚類等.但這兩種聚類方法在共享單車停車圍欄聚類的場景下均存在一定的缺陷，本文最終使用HDBSCAN聚類方法，并通過實驗證明了HDBSCAN的聚類效果優于K-means和DBSCAN.

2.1 K-means聚類

K-means是一種非常經典的聚類算法[20]，因其原理簡單，可解釋性強而得到廣泛應用.K-means算法的聚類過程簡單地說就是把數據點按照某種相似度劃分到不同的簇中，使得同一簇內的數據點相似度盡可能的高，不同簇間的數據點相似度盡可能低.但是K-means有兩個明顯的缺陷：1)K-means對于非球形數據集的聚類效果不佳，然而實際的停車圍欄分布情況一般是呈非球形分布的，因此K-means算法的劃分效果不佳；2)K-means算法需要事先指定數據簇的數目，而在實際停車圍欄聚類中，無法事先確定最終的聚類簇的數目，因此實驗中需要反復試錯，才能得到最佳聚類簇的個數，這樣會大大提高計算的代價.從以上分析可知，K-means算法不適用于停車圍欄的聚類.

2.2 DBSCAN聚類

DBSCAN算法[21]是一種常用的基于密度的聚類算法.DBSCAN算法的基本思想是：對于聚類簇中的每一個點，在給定的半徑rEps范圍內應至少包含給定數目的點Mminpts[22].但是在使用DBSCAN算法聚類停車圍欄時，存在兩個較為嚴重的缺陷：1) 算法對領域最大半徑rEps這一輸入參數非常敏感，細微的參數變化就會使得聚類結果截然不同，并且也較難得知rEps參數的合理取值；2) DBSCAN聚類存在“鏈式傳導”的現象，即只要有少量的點斷開，就會導致本應被聚類同一個簇的點聚類為多個簇.在實際的停車圍欄聚類中，較難獲得準確的rEps值，因此也不能使用DBSCAN聚類方法用于停車圍欄的聚類.

2.3 HDBSCAN聚類

HDBSCAN聚類算法是DBSCAN算法和層次聚類算法的結合，它通過將DBSCAN聚類算法轉換為分層聚類算法，與DBSCAN算法類似，HDBSCAN算法也需要確定領域最大半徑rEps以及領域內的最少點數Mminpts，但是HDBSCAN算法引入了“層次聚類”的思想，通過對共享邊界點等共享數據對象的特殊處理，對初始的聚類簇進行層次合并，屏蔽了算法對rEps等輸入參數的敏感性[23]；此外，HDBSCAN算法通過生成最小生成樹與層次結構，并通過分裂來壓縮樹狀圖來避免了DBSCAN 算法的“鏈式傳導”問題，因此最終選擇HDBSCAN聚類算法用于共享單車停車圍欄的聚類.

通過實地勘察，該市內道路中雙向六車道加上綠化帶的距離一般為33 m左右，因此在HDBSCAN算法的基礎上加入了若聚類出的兩個簇小于33 m，則合并簇的規則，使得聚類效果更符合實際情況.使用HDBSCAN算法對該市的共享單車停車圍欄聚類，共聚類出1 729個簇，并將每個聚類離群點單獨作為一個簇，最終簇的數目為3 061個，即總共有3 061個停車區域.

2.4 聚類效果對比

為了證明在對共享單車停車圍欄聚類這一場景下HDBSCAN聚類算法的效果優于K-means和DBSCAN，設計了如下對比實驗.

首先，調整DBSCAN的rEps值和Mminpts值，使DBSCAN聚類出的簇的數目盡量接近1 729.通過實驗調參，當rEps=0.000 265，Mminpts=3時，聚類出的簇的數目為1 575，是最接近1 729的.因為沒有真實停車圍欄聚類樣本的標簽，因此實驗采用輪廓系數[24]和CH指數[25]作為比較DBSCAN和HDBSCAN聚類效果的評價指標，兩種評價指標如式(1)和(2)所示.

(1)

(2)

式(1)中：a(i)表示樣本i與同一簇內所有其他樣本之間的平均距離，b(i)表示樣本i與其距離最近的簇中所有樣本的平均距離，輪廓系數值越大，聚類效果越好；式(2)中：Tr(·)表示矩陣的跡，Bk表示組間協方差，Wk表示組內協方差，N為訓練集樣本數，k為類別數，CH指數越大，聚類效果越好.因為輪廓系數和CH指數在凸簇的得分通常會比其他類型的簇更高，因此無法同時比較K-means的聚類效果，僅比較DBSCAN和HDBSCAN算法，實驗結果如表3所示.

表3 DBSCAN和HDBSCAN聚類算法實驗對比結果

由表3可知，HDBSCAN算法的輪廓系數與CH指數都高于DBSCAN算法，說明HDBSCAN算法聚類出的簇同類樣本越接近，不同樣本間越遠離，聚類效果更好，因此相比于DBSCAN算法，HDBSCAN算法更適用于共享單車停車圍欄的聚類.

圖2 K-means聚類效果圖Fig.2Clustering effect chart of K-means

其次，為比較聚類方法在單車停放場景的聚類效果，進一步結合地理可視化方法，對3種聚類方法的結果進行分析.設置K-means算法中的聚類簇數目為1 729來訓練模型.分別采用K-means、DBSCAN和HDBSCAN算法對該市的共享單車停車圍欄進行聚類，并選取該市的呂嶺路為例，通過可視化展示的方法來比較聚類效果.聚類結果如圖2和3所示.

如圖2所示，呂嶺路道路下方藍色與橙色的點分別是K-means中的不同簇，K-means方法將本該被聚類為一個簇的距離較近的點錯誤地聚類為兩個簇，不符合實際情況.從理論上分析，K-means算法對球形分布的數據聚類效果較好，而實際的共享單車停車圍欄跟隨道路而分布，因此分布情況較為狹長，不屬于球形數據，因此K-means無法獲得較好的結果.如圖3(a)和(b)所示，分別是DBSCAN和HDBSCAN的聚類可視化結果，與K-means算法對比，基于密度的DBSCAN和HDBSCAN算法都能很好地對狹長分布的數據聚類.此外，DBSCAN算法雖然可以將右側相鄰密集的點正確聚類為一個簇，但左側的兩個點應屬于同一個簇，卻被錯誤地聚類為兩個簇，不符合實際情況.反觀HDBSCAN算法，不但可以將右側相鄰密集的點聚類為一個簇，還可以正確地將左側離的稍遠的點聚類為同一個簇，實驗結果符合實際情況.

圖3 DBSCAN和HDBSCAN聚類效果對比圖Fig.3Comparison of DBSCAN and HDBSCAN clustering effects

通過上述實驗可以發現，無論是理論指標還是實際應用，HDBSCAN都具有更佳的聚類效果.第3節將基于HDBSCAN的聚類結果設計停車擁擠區域識別算法.

3 停車擁擠區域識別

本文首先定義相關概念如下：

流入流量，記為Aarrival_flow，是指在某一個停車區域內共享單車的流入次數，表現為在該停車區域中關鎖，即對應共享單車訂單數據中‘LOCK_STATUS’字段為1；

流出流量，記為Ddeparture_flow，是指在某一個停車區域內共享單車的流出次數，表現為在該停車區域中開鎖，即對應共享單車訂單數據中‘LOCK_STATUS’字段為0.

傳統的停車擁擠識別方法包括了基于“留存流量”和“留存密度”兩種，但這兩種方法都僅考慮了一種指標，無法同時考慮流量和密度的因素對停車擁擠區域進行識別，具有一定的局限性.為了解決這一問題，本文提出了基于“留存流量與留存密度的綜合指標”的識別方法.

3.1 基于“留存流量”的識別方法

“留存流量”定義為流入流量減流出流量，留存流量越大，則該停車區域中留存的車輛越多.給出“留存流量”的計算公式如下：

Nnetflow=Aarrival_flow-Ddeparture_flow.

(3)

給出“停車區域面積”定義如下：

(4)

其中：FAi為某個停車區域中第i個停車圍欄的面積；Ttotal_area為簇內所有停車圍欄的面積和，即為該停車區域的總面積.

按照“留存流量”從高到低的順序對停車區域進行排序，選取停車擁擠現象最嚴重的前5個停車區域部分信息字段如表4所示.

表4 按“留存流量”識別的停車擁擠現象最嚴重的前5個區域部分信息

如表4所示，按“留存流量”識別的停車擁擠現象最嚴重的前5個區域，擁有較大的停車區域面積以及較大的“留存流量”.為了更直觀地展示識別效果，使用Python的繪圖庫Folium在該市地圖上繪制按照“留存流量”識別的停車擁擠現象最嚴重的前40個停車區域如圖4 所示.

圖4 按“留存流量”識別的停車擁擠現象最嚴重的40個區域Fig.4The 40 areas with the worst parking congestion identified by “retained traffic”

從圖4中可以看出，停車擁擠區域一般集中在殿前街道、禾山街道以及軟件園等區域附近.基于“留存流量”識別停車擁擠區域具有一定的局限性，它無法有效識別出留存流量不大，但同時停車面積也較小的區域，這部分區域的停車擁擠程度也可能相對較高.

3.2 基于“留存密度”的識別方法

“留存密度”定義為“留存流量”除以停車區域總面積，“留存密度”越大，則該停車區域內車輛密集程度越高.給出“留存密度”的計算公式如下：

(5)

按照“留存密度”從高到低的順序對停車區域進行排序，選取停車擁擠現象最嚴重的前5個停車區域部分信息字段如表5所示.

如表5所示，按“留存密度”識別的停車擁擠現象最嚴重的前5個區域，普遍面積較小但區域內“留存密度”較高.為了更直觀地展示識別效果，使用Folium在該市地圖上繪制按照“留存密度”識別的停車擁擠現象最嚴重的前40個停車區域如圖5所示.

從圖5中可以看出，停車擁擠區域一般集中在湖濱南路、禾山街道以及軟件園等區域附近.基于“留存密度”識別停車擁擠區域同樣具有一定的局限性，它無法有效識別出“留存密度”不高但“留存流量”較高的停車擁擠區域.

表5 按“留存密度”識別的停車擁擠現象最嚴重的前5個區域部分信息

圖5 按“留存密度”識別的停車擁擠現象最嚴重的40個區域Fig.5The 40 areas with the worst parking congestion identified by "retention density"

3.3 基于“留存流量與密度的綜合指標”的識別方法

給出“留存流量與密度的綜合指標”的定義如下：

(6)

(7)

(8)

按照“綜合指標”從高到低的順序對停車區域進行排序，選取停車擁擠現象最嚴重的前5個停車區域部分信息字段如表6所示.

表6 按“綜合指標”識別的停車擁擠現象最嚴重的前5個區域部分信息

結合表4～6可以發現，使用“綜合指標”所識別出的停車擁擠現象最嚴重的5個停車區域同時包含了使用“留存流量”和“留存密度”所識別出的停車擁擠區域，證明使用“綜合指標”能夠克服單一指標所帶來的局限性.

為了更直觀地展示識別效果，使用Folium在該市地圖上繪制按照“綜合指標”識別的停車擁擠現象最嚴重的前40個停車區域如圖6所示.

圖6 按“綜合指標”識別的停車擁擠現象最嚴重的40個區域Fig.6The 40 areas with the worst parking congestion identified by the "comprehensive indicator"

通過觀察地圖信息和實地走訪調研可知，這些停車擁擠區域所處地區均為企業密集區域、學校、醫院以及商業區附近，例如軟件園、雙十中學、中山醫院以及五一文化廣場等地，這些區域的人流量較大，對于共享單車的需求也較大，因此容易造成共享單車的停車擁擠現象，證明了識別出的停車擁擠區域符合實際用戶用車與停車情況.

3.4 實驗結果分析

通過上述實驗可以發現，基于“留存流量”的停車擁擠區域識別方法可以準確地識別出區域內留存流量較大的區域，但是無法識別出流量不大但是密度較大的區域；反之，基于“留存密度”的停車擁擠區域識別方法可以準確地識別出區域內留存密度較大的區域，但是無法識別出密度不大但是流量較大的區域.所提出的基于“留存流量與密度的綜合指標”的停車擁擠區域識別方法能夠準確地同時識別出“留存流量”較大或“留存密度”較大的區域，相比于基于單一指標的識別方法，提高了準確性和可靠性.

4 結 論

本文基于某市某品牌共享單車訂單數據和停車圍欄數據，對共享單車停車擁擠區域的識別進行了研究，在對原始數據進行預處理后，使用GeoHash算法對原始經緯度坐標進行編碼處理，并計算判斷共享單車開關鎖訂單屬于哪個停車圍欄，使用HDBSCAN聚類算法將原始停車圍欄聚類為停車區域，并提出了基于“留存流量與密度的綜合指標”的停車擁擠區域識別方法對擁擠區域進行識別，通過分析和實地考察，區域識別效果符合實際情況.這一關鍵步驟為后續的共享單車引導調度奠定了堅實的基礎.