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

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

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

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

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

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

1 數(shù) 據(jù)

1.1 數(shù)據(jù)描述

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

表1 共享單車訂單數(shù)據(jù)字段信息

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

1.2 數(shù)據(jù)預(yù)處理

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

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

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

1.3 GeoHash算法處理經(jīng)緯度坐標(biāo)

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

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

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

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

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

2 共享單車停車圍欄聚類

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

2.1 K-means聚類

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

2.2 DBSCAN聚類

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

2.3 HDBSCAN聚類

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

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

2.4 聚類效果對比

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

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

(1)

(2)

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

表3 DBSCAN和HDBSCAN聚類算法實驗對比結(jié)果

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

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

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

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

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

通過上述實驗可以發(fā)現(xiàn)，無論是理論指標(biāo)還是實際應(yīng)用，HDBSCAN都具有更佳的聚類效果.第3節(jié)將基于HDBSCAN的聚類結(jié)果設(shè)計停車擁擠區(qū)域識別算法.

3 停車擁擠區(qū)域識別

本文首先定義相關(guān)概念如下：

流入流量，記為Aarrival_flow，是指在某一個停車區(qū)域內(nèi)共享單車的流入次數(shù)，表現(xiàn)為在該停車區(qū)域中關(guān)鎖，即對應(yīng)共享單車訂單數(shù)據(jù)中‘LOCK_STATUS’字段為1；

流出流量，記為Ddeparture_flow，是指在某一個停車區(qū)域內(nèi)共享單車的流出次數(shù)，表現(xiàn)為在該停車區(qū)域中開鎖，即對應(yīng)共享單車訂單數(shù)據(jù)中‘LOCK_STATUS’字段為0.

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

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

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

Nnetflow=Aarrival_flow-Ddeparture_flow.

(3)

給出“停車區(qū)域面積”定義如下：

(4)

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

按照“留存流量”從高到低的順序?qū)ν＼噮^(qū)域進行排序，選取停車擁擠現(xiàn)象最嚴重的前5個停車區(qū)域部分信息字段如表4所示.

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

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

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

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

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

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

(5)

按照“留存密度”從高到低的順序?qū)ν＼噮^(qū)域進行排序，選取停車擁擠現(xiàn)象最嚴重的前5個停車區(qū)域部分信息字段如表5所示.

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

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

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

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

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

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

(6)

(7)

(8)

按照“綜合指標(biāo)”從高到低的順序?qū)ν＼噮^(qū)域進行排序，選取停車擁擠現(xiàn)象最嚴重的前5個停車區(qū)域部分信息字段如表6所示.

表6 按“綜合指標(biāo)”識別的停車擁擠現(xiàn)象最嚴重的前5個區(qū)域部分信息

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

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

圖6 按“綜合指標(biāo)”識別的停車擁擠現(xiàn)象最嚴重的40個區(qū)域Fig.6The 40 areas with the worst parking congestion identified by the "comprehensive indicator"

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

3.4 實驗結(jié)果分析

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

4 結(jié) 論

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