基于混合聚類分析的共享單車停放點位置合理性研究

王霞 宋樹華 湯軍 劉遠剛

摘要：針對共享單車停放點位置優化的問題，以現有的共享單車停放點位置作為初始聚類中心點，對共享單車的定位數據做聚類，并且提出了結合K-MEANS聚類和緩沖區分析的混合聚類方法，來解決初始聚類中心點相靠近時出現的共享單車錯誤分類問題。將最終聚類結果作為建議的共享單車停放點位置，進而依據建議的共享單車停放點位置判斷現有的共享單車停放點位置的合理性，實驗結果表明這種混合聚類方法的聚類效果理想。

關鍵詞：混合聚類;共享單車;停放位置;合理性

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1007-9416（2019）07-0058-04

共享單車作為中國“新四大發明”之一，彌補了市民出行過程中“最后一公里”的空白。它為市民個人的出行需求提供了極大便利，但是共享單車的過度投放和疏于管理也阻礙著城市文明的建設[1]。

共享單車停放點位置的確定是展開共享單車規范化管理工作的第一步，在停放點選址問題上[2-5]，很多學者都選擇采用劃分法[6，8]或者層次法[7，8]對共享單車位置分布數據進行聚類。這些聚類方法得出的聚類結果未考慮已規劃停放點的位置合理性，而且當已規劃停放點的中心位置相鄰時，聚類的結果并不理想。

本文提出了結合K-MEANS聚類[9]與緩沖區分析的混合聚類方法，基于模擬數據采用混合聚類方法對停放點的位置合理性進行判斷，以求得到在已規劃的停放點中心位置相鄰情況下理想的聚類結果。

1 共享單車停放點位置合理性分析

1.1 共享單車停放點位置合理性問題分析

評價一個停放點的位置是合理的，即要避免出現以下情況：（1）已經施劃的停放點內沒有或長期只有很少數量的單車停放;（2）在經常有一定數量單車停放的地點沒有施劃停放點。現有停放點的選址主要依靠政府的土地規劃政策和規劃人員的經驗，存在一定施劃上的合理性但是對停放需求點的預測還不夠準確。

普遍認為，單車的停放位置在空間上數量多且集聚，則空間上形成的集聚區域可視為有單車停放需求的地點。由此可見，停放點的施劃與共享單車停放位置的分布情況有很大的關聯性，因此可以借助共享單車的定位數據結合現有停放點位置數據做聚類分析，得出的聚類結果的中心位置為有單車停放需求的地點，以有單車停放需求的地點為依據再對現有停放點的位置做出調整，能夠提高共享單車停放需求點預測的準確度。

1.2 基于混合聚類的共享單車停放點位置合理性判斷

本文提出的混合聚類結合了K-MEANS聚類和緩沖區分析[10]，本文稱引入緩沖區分析的聚類為緩沖區聚類。緩沖區聚類是為了解決現有停放點位置靠近時，可能會出現單車定位數據錯誤分類的情況。緩沖區聚類在以下應用場景中有現實意義，比如現有停放點施劃在較狹窄馬路的兩邊或是密集施劃在商業繁華地段時，若只對單車定位數據進行簡單的聚類，那么可能會出現聚類結果不準確的結果。

下面從緩沖區距離和緩沖區聚類算法描述兩方面說明緩沖區聚類。

1.2.1 緩沖區距離確定的算法描述

在進行緩沖區聚類之前首先要確定緩沖區距離，確定緩沖區距離的情形見圖1，基于共享單車停放點的形狀為矩形這一條件假設，需要輸入的數據為現有停放點區域數據M，確定緩沖區距離的算法如下：

（1）計算M兩兩之間中心點距離D，取min{D}的兩個現有停放區域記為停放區域1（R1）和停放區域2（R2）;

（2）確定line1和line2的直線方程;

（3）計算d1和d2;

（4）確定ρ0，ρ0=0.5d;判斷P（P1、P2）是否在R（R2、R1）上，若P落在R上，則對應的距離為有效距離，反之則為無效距離;取d1和d2中標記為有效距離的計算ρ0，若d1和d2都標記為無效距離，則計算R1所有頂點和R2所有頂點的最短距離標記為有效距離計算ρ0。（注：情形3和情形4為直線斜率為0和無窮的特殊情況，ρ0的計算步驟一樣。）;

（5）結束算法。其中，M為現有停放點區域數據，M（e，Xe，Ye，length，width，angle），e代表M的編號，Xe代表e的中心點位置的x坐標，Ye代表e的中心點位置的y坐標，length代表e的長度，width代表e的寬度，angle代表e繞（Xe，Ye）逆時針旋轉角度; line1為經過R1兩個頂點的直線，且R1和R2上的所有頂點分別分布在line1的左右兩側;line2為經過R2兩個頂點的直線，且R1和R2上的所有頂點分別分布在line2的左右兩側;d1表示R1上的頂點到line2的最小值;d2表示R2上的頂點到line1的最小值; P1表示d1落在line2上的垂足;P2表示d2落在line1上的垂足;ρ0為緩沖區距離;d為有效距離。

1.2.2 緩沖區聚類算法描述

基于共享單車停放點的形狀為矩形這一假設，需要的輸入數據為待做緩沖區聚類的停放點區域N和待聚類的單車定位數據集S，算法如下：

（1）遍歷N，對N的長度和寬度各擴大ρ0，lengthN=lengthN+ρ0，widthN=widthN+ρ0;

（2）m=m+1;

（3）遍歷S（p，Xp，Yp），判斷點p是否在N內，若屬于，則（Xp，Yp）∈Cm;

（4）計算Cm的平均位置做聚類中心C0m，XC0m=，YC0m=;n=n+1;

（5）直到（XC0m，YC0m）不變，S=S-Cm;

（6）結束算法。其中，N為待做緩沖區聚類的停放點區域，N（e，Xe，Ye，length，width，angle），e代表N的編號，Xe代表e的中心點位置的x坐標，Ye代表e的中心點位置的y坐標，length代表e的長度，width代表e的寬度，angle代表e繞（Xe，Ye）逆時針旋轉角度;S（p，Xp，Yp）為共享單車定位數據集，p表示單車編號，Xp代表單車p的x坐標，Yp代表單車p的y坐標;聚類結果C（m，Cm），Cm是S中聚成一類的點集;m是聚類編號（初始值m=0）;聚類結果中心C0（m，XC0m，YC0m），XC0m是C0m的x坐標，YC0m是C0m的y坐標;迭代次數n，初始n=0。

1.2.3 混合聚類算法描述

基于共享單車停放點的形狀為矩形這一假設，設置K-MEANS聚類的k值為現有停放點數量，需要的輸入數據為現有停放點區域數據M和待聚類的單車定位數據集S，算法如下：

（1）統計現有停放區域長度最大值max{lengthM}和寬度最大值max{widthM}，ρ2=√max{lengthM}2+max{widthM}2;ρ1 =0.5ρ2;

（2）計算緩沖區距離ρ0;M的個數為k;

（3）遍歷M（e=0），（Xe，Ye）作為初始聚類中心;遍歷S（p=0），計算d（（Xp，Yp），（Xe，Ye）），若d（（Xp，Yp），（Xe，Ye））≤ρ1，則（Xp，Yp）∈Cm;

（4）計算Cm的平均位置做聚類中心C0m，XC0m=，YC0m= ;n=n+1;

（5）直到（XC0m，YC0m）不變，S=S-Cm，m=m+1;若m≤k，則進入步驟（3）;否則，進入步驟（6）;

（6）判斷S是否為空集，若否，則進入步驟（7）;若是，則進入步驟（12）;

（7）m=m+1;

（8）取S中第一個點（Xp0，Yp0）并將其從S中去除，（Xp0，Yp0）∈Cm;

（9）計算（Xp0，Yp0）與S中其它點集的歐氏距離d（（Xp0，Yp0）， （Xp，Yp）），若d（（Xp0，Yp0）， （Xp，Yp））≤ρ2，則（Xp，Yp）∈Cm;

（10）計算Cm的平均位置做聚類中心C0m，XC0m=，YC0m =;n=n+1;

（11）直到（XC0m，YC0m）不變，S=S-Cm;進入步驟（6）;

（12）計算M中兩兩之間的距離d（（Xei，Yei），（Xej，Yej）），獲得距離矩陣D[d（（Xei，Yei），（Xej，Yej））];

（13）遍歷D[d（（Xei，Yei），（Xej，Yej））]，若d（（Xe，Ye），（XM，YM））≤ρ2，則進行緩沖區聚類（算法見上），否則，結束算法。

其中，現有停放點區域數據M（e，Xe，Ye，length，width，angle），e代表M的編號，Xe代表e的中心點位置的x坐標，Ye代表e的中心點位置的y坐標，length代表e的長度，width代表e的寬度，angle代表e繞（Xe，Ye）逆時針旋轉角度;共享單車定位數據集S（p，Xp，Yp），p表示單車編號，Xp代表單車p的x坐標，Yp代表單車p的y坐標;聚類結果中心C0（m，XC0m，YC0m），m是聚類編號（初始值m=0），XC0m是C0m的x坐標，YC0m是C0m的y坐標;聚類結果C（m，Cm），Cm是S中聚成一類的點集;聚類距離閾值ρ1和ρ2;緩沖區擴大距離為ρ0;d（i，j）表示點對象i與點對象j的歐氏距離;D[d（i，j）]表示點對象之間的距離矩陣;迭代次數n，初始n=0。

1.2.4 共享單車停放點位置合理性判斷流程

判斷共享單車停放點位置合理性分為兩大步：（1）對單車定位數據進行聚類分析，獲得聚類結果;（2）以聚類結果為依據對現有停放點位置合理性進行判斷。具體流程圖如圖2所示。

2 程序實現

2.1 數據說明

借助python生成了142條具有位置信息的共享單車模擬數據和6條具有中心位置信息和長寬信息的現有停放點（矩形）模擬數據。

對單車定位與停放區域模擬數據做可視化，如圖3所示，點表示為單車定位數據，方塊表示為現有的停放區域數據。

2.2 結果分析

2.2.1 聚類

經過34次迭代后得到單車數據初始聚類結果，如圖4所示，其中用圓圈標記的是相鄰現有停放區的中心位置，此種情況視為可能會出現聚類結果不理想的情況，需要進一步進行緩沖區聚類。

經過緩沖區聚類后的結果如圖5所示，相比較初始聚類結果，原來聚為三類的經緩沖區聚類后聚成了兩類，且聚類結果中的元素發生了變動。兩類之間有明顯的分割線，這條分割線的現實代表可能是一條狹窄的馬路，從聚類結果可看出單車數據被很好的分類了。

2.2.2 判斷

依據最終聚類結果對現有停放區域的位置合理性做判斷，調整結果如圖6所示，深色區域對應的聚類中心與現有停放區的中心位置相差無幾，但是聚類結果中的元素數量太少，因此判斷是要取消施劃的停放區域;淺色區域對應的聚類中心與現有停放區的中心位置相差無幾，聚類結果中的元素數量多，因此判斷是保留不動的停放區域;叉點記號缺少對應的現有停放區，聚類結果中的元素數量多，因此判斷是要新增的停放區域。

3 結語

本文提出的混合聚類算法，較為針對性的解決了現有停放點區域相鄰時所出現的聚類元素錯亂的問題，得出的聚類結果較為理想。以此為依據對現有停放區域的位置做調整是較為科學合理的，能夠為共享單車規范化管理的良性發展奠定基礎，進一步能夠促進共享單車生態環境與城市其他生態環境的和諧共處。

參考文獻

[1] 黃多巍，散園園.共享單車對城市道路交通的影響及對策[J].城市道橋與防洪，2018，2018（02）：42-43+9.

[2] I.Frade，A.Ribeiro. Bike-sharing stations： A maximal covering location approach[J].Transportation Research Part A，2015，2015（82）：216-227.

[3] 高楹，宋辭，舒華，等.北京市摩拜共享單車匯源時空特征分析及空間調度[J].地球信息科學，2018，20（8）：1123-1138.

[4] 白江龍.基于Spark平臺的共享單車騎行分析[D].內蒙古：內蒙古大學，2018.

[5] Yan Pan， Ray Chen Zheng， Jiaxi Zhang， et al. Predicting bike sharing demand using recurrent neural networks[J]. Procedia Computer Science，2019，2019（147）：562-566.

[6] 史豫坤.基于Hadoop的共享單車停放點選址方法的研究[D].安徽：安徽理工大學，2018.

[7] 索源.基于出行需求波動的共享單車停放點選址規劃研究[D].北京：北京交通大學，2018.

[8] 郝洪星，朱玉全，陳耿，等.基于劃分和層次的混合動態聚類算法[J].計算機應用研究，2011，28（1）：51-53.

[9] 陶瑩，楊鋒，劉洋，等.K均值聚類算法的研究與優化[J].計算機技術與發展，2018，28（06）：90-92.

[10] 徐鋒.基于矢量的空間對象緩沖區生成算法[C]//廣西測繪學會：全國測繪科技信息網中南分網第三十次學術信息交流會論文集.廣西：廣西人民出版社，2016：523-525.