洪文兴，陈明韬，刘伊灵，朱嘉诚，王明磊
(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 数据描述
本文采用的数据集为某市某品牌共享单车订单数据以及共享单车停车围栏数据.其中共享单车订单数据记录了每辆共享单车的开关锁的时间、开关锁状态以及所在的经纬度坐标，时间范围为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编码相同的数据，再通过经纬度坐标计算共享单车到这几个停车围栏中心的距离，距离最小的停车围栏即确定为该单车所属的停车围栏，为后续停车拥挤区域的识别打下基础.
停车拥挤区域的识别需要先将众多的共享单车停车围栏聚类为停车区域.常用的聚类方法有：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的聚类结果设计停车拥挤区域识别算法.
本文首先定义相关概念如下：
流入流量，记为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 实验结果分析
通过上述实验可以发现，基于“留存流量”的停车拥挤区域识别方法可以准确地识别出区域内留存流量较大的区域，但是无法识别出流量不大但是密度较大的区域；
反之，基于“留存密度”的停车拥挤区域识别方法可以准确地识别出区域内留存密度较大的区域，但是无法识别出密度不大但是流量较大的区域.所提出的基于“留存流量与密度的综合指标”的停车拥挤区域识别方法能够准确地同时识别出“留存流量”较大或“留存密度”较大的区域，相比于基于单一指标的识别方法，提高了准确性和可靠性.
本文基于某市某品牌共享单车订单数据和停车围栏数据，对共享单车停车拥挤区域的识别进行了研究，在对原始数据进行预处理后，使用GeoHash算法对原始经纬度坐标进行编码处理，并计算判断共享单车开关锁订单属于哪个停车围栏，使用HDBSCAN聚类算法将原始停车围栏聚类为停车区域，并提出了基于“留存流量与密度的综合指标”的停车拥挤区域识别方法对拥挤区域进行识别，通过分析和实地考察，区域识别效果符合实际情况.这一关键步骤为后续的共享单车引导调度奠定了坚实的基础.
猜你喜欢 经纬度围栏单车 共享单车为什么在国外火不起来意林彩版(2022年1期)2022-05-03TBS围栏灭鼠技术今日农业(2021年2期)2021-11-27围栏红蜻蜓·低年级(2020年12期)2020-06-20飞吧，单车读友·少年文学(清雅版)(2020年1期)2020-05-20动物园好孩子画报(2019年8期)2019-09-19基于经纬度范围的多点任务打包算法科技资讯(2018年10期)2018-10-26洗澡围栏发明与创新·大科技(2018年2期)2018-03-17对恶意破坏共享单车行为要“零容忍”领导决策信息(2017年9期)2017-05-04共享单车(外四首)岷峨诗稿(2017年4期)2017-04-20自制中学实验操作型经纬测量仪新课程·中旬(2017年1期)2017-03-27