结合Canopy-K-means算法和出租车轨迹数据的公交车站预测方法

刘 旭，陈云波，施 昆，黄 强

(1. 昆明理工大学，云南 昆明 650093； 2. 昆明市规划编制与信息中心，云南 昆明 650500； 3. 成都理工大学，四川 成都 610059)

随着城市化进程的加快、城市规模的急剧扩张、人口数量的迅猛增长，公共交通对居民出行的意义显得越来越重要[1]。据统计，公共交通在城市中肩负着20%的全方位出行比例，并且这一比例仍在提升中[2]。为了在有限的空间中让公共交通的作用全部发挥，公交站点的合理选取和预测显得至关重要。出租车GPS数据是由每一台搭载卫星定位系统的出租车在一定的时间间隔点获取的，它能客观真实地反映居民出行乘车的热点区域、道路畅通情况、居民出行高峰期等[3]。因此，用其预测公交站点位置已经成为研究的热点。

目前，国内外许多学者基于出租车GPS数据展开了各种研究。针对公共交通站点预测，主要包括以下3个方面：①基于采集的实时GPS数据，针对公交车到站时间进行研究。如周雪梅等[7]通过采集的实时车辆定位信息，并考虑潜藏的平均瞬时速度及停留时间，建立了基于前车的预测模型，提出一种可能发生的延误模型；王武等[8]基于出租车轨迹数据改进了基于密度的聚类算法(DBSCAN)，找到上下车的具体位置，通过这种方法发现热点出行区域并判断公交车的候选地址。②通过研究客源的分布特征，预测客流量情况。Koshy和Arasan考虑公交站点的构成，开发了一个仿真拟模型来检验公交站点对交通流的影响[9]。③通过建立回归模型和预测模型对公共交通站点进行预测。周洋等[9]考虑网络节点的拓扑关系、路径和轨迹密度，构建了一种街道网络的基于移动轨迹数据提取网络位置关键功能的地理空间方法。

综上所述，虽然各种研究方法都对公交车站作了相关预测,但少有对公交车路线中各个站点位置的合理预测，以及公交车发车最优时间的预测。本文在已有的研究基础上，提出一种基于Canopy-K-means算法的公交车站预测方法。以武汉市13 d的出租车轨迹数据作为研究对象，取乘车点坐标数据作为研究内容，通过高效聚类获取居民出行热点区域，并采用数据统计和对比分析的方法预测公交站点分布的合理性和高峰期公交的发车时间间隔，为缓解交通拥堵现象和决策者合理分配公共交通资源提供决策辅助。

1 方 法

1.1 总体设计

为了预测公交站点位置，需要先找到居民出行的热点区域，再结合统计数据进行分析。本文基于出租车数据设计的公交车站方法如下：首先使用Hadoop分布式处理平台对海量GPS数据进行处理，得到居民出行点数据，以提取数据记录中每台车状态变化的临界点作为出行点坐标数据[11]；其次引入Canopy-K-means改进聚类算法，将提取出的出行热点区域按一定的参数进行聚类，获取出行热点区域；然后将出行热点区域中心点与已有的公交站点进行对比，分析已有公交站点的合理性，预测公交站台设定点的合理位置；最后结合数理统计方法，统计1 d中12个时段(每个时段2 h)的出行总量，预测公交车合适的发车频率。设计原理如图1所示。

图1 方法流程

1.2 基于Hadoop的Canopy-K-means算法原理

1.2.1 K-means算法

K-means算法是一种基于距离的聚类算法。簇的个数k由使用者提前给定，每一个簇是通过其质心(centroid)，即每个簇的中心点来描述。

K-means算法的工作流程为：首先随机确定k个初始点作为质心，然后将数据集中的每个点都分配到一个满足条件的簇中，即为每个点寻找距离其最近的质心，并将其分配给该质心所对应的簇。该步完成后，每个簇的质心更新为该簇中所有点的坐标的平均值[12]。K-means算法是聚类算法中使用最为广泛的算法之一，其用到的数学思想简单，但效率高，且在对“圆形-球形”性质集合进行分类时，可以达到良好的聚类结果[13]。

K-means算法虽然高效，但缺点也很明显，主要分为两个方面：

(1) 中心点k个数的选取存在随机性，难以界定，对于需要处理的海量数据，无法判断数据中所有簇的个数。

(2) 使用这种算法对计算机的资源占用太高，计算每个点到中心点的距离时存在太多冗余。如果计算机资源消耗巨大，可能存在计算机死机的危险。

本文针对传统K-means算法主要的两个缺点进行改进，引入一种改进的K-means算法，提高算法聚类性能。

1.2.2 Canopy-K-means算法

传统的K-means算法由于初始聚类中心选择的随机性，算法结果随着中心点选择的不同而改变，最终会导致结果的不稳定性，因此可能会造成聚类结果的最优值不稳定的问题[14]。Canopy-K-means聚类算法是通过引入Canopy算法，初始化K-means算法的聚类中心，形成无数个相互重叠的簇，不在簇的范围内包含的点则视为噪声点被剔除。不断迭代多次后，簇的中心不断变化直至收敛，得到每个簇的中心点，中心点数据则被视为K-means数据的中心点。这样在聚类过程中，减少了随机中心点选取对聚类结果的主观影响。整个聚类流程如图2所示。

由图2可知，算法步骤为：

(1) 创建Job1,使用Canopy算法进行聚类。首先，在Map-reduce中创建第一个工作任务Job1。给定数据集A作为Canopy算法中心，并给Canopy算法指定阈值T1、T2(T1、T2表示以A集合中的点为中心的圆的半径)，再使用算法对数据集A=(a1，a2，…，an)进行聚类，收敛的迭代中心，即为聚类中心。

(2) 明确每个点所属类别。这里的类别指中心点所在的区域。若数据点Xi距Canopy的中心点Ai的距离小于T2，则认为Xi属于Ai类；若数据点Xi距中心点Ai的距离小于T1，则数据点Xi可能属于多个Ai,这时判断Xi距离哪个Ai最近则认为Xi属于该Ai。

图2 算法流程

(3) 得到K-means算法中心点。对步骤(2)得到的每个簇中的所有点求均值，把它们作为K-means算法的中心。

(4) 合并K-means中心。这一步是为了降低步骤(1)中确定T1、T2时的误差。由于半径过小会导致聚类后的中心点过多的问题，因此选择一定的范围，将中心点间距离过小的点合并求均值，即为K-means的中心点。

(5) 创建Job2,循环迭代产生Canopy中心，直至收敛。设立Flag作为判断依据，将步骤(4)中得到的中心点作为Canopy中心，产生新的簇。若收敛Flag值为true，则不需要再处理；若Flag值为false，证明还没有收敛，再代入步骤(2)中开始执行，直至收敛。该过程命名Job2,后面名称依次加1，作为文件命名，并且记录算法循环次数。

(6) 对每个Canopy内的点使用K-means算法进行精确聚类，这样就能避免传统的算法中对所有点进行精确聚类而产生的计算机开销过大的情况，从而求得热点出行区域。

Canopy-K-means算法在Hadoop上运行流程，如图3所示。

1.2.3 如何预测公交车站点和发车时间间隔

公交车站不合理分布会导致道路交通阻塞、客流量流通停滞等多方面危害[15]。在上文聚类中得到了乘客出行的热点分布区域，公交站点则最好设置在热点区域附近，才能有效缓解道路交通压力。通过对热点区域和已有站点的坐标位置进行对比，使用欧式距离，求得公交站点与聚类中心点的距离，从而有效分析公共交通站点分布的合理性。

图3 Canopy-K-means算法在Hadoop上的运行流程

利用上车点轨迹数据，将一天的时间分为12个不同时间段，统计每个时段内的客流量，分析客流量高峰存在的时间段和出现的原因。引入分析公式(1)，变量H表示客流总量，D表示车载总数，M为划分统计段的分钟数，求得最佳时间间隔t(保留整数),0.2为公交车承载量占总量的百分比。

(1)

2 试 验

2.1 数据集

本文研究数据主要是基于2014年7月31日—2014年8月12日13 d的武汉市出租车轨迹数据，约3172万条，见表1。原始数据包含车辆ID、记录时间、车辆坐标经度、车辆坐标纬度、车辆速度、车头方向、车辆状态等12个字段信息。安装在出租车上的GPS信号接收器以30 s/次的采样速度采集数据。表1展示了数据记录模板。为了保护数据隐私，将经纬度坐标部分内容用“***”表示。车辆状态表示出租车是否载客，包括“1”和“0”值。“1”值意味着出租车有乘客，而“0”值意味着出租车里没有乘客。原始出租车轨迹数据必须经过数据过滤，主要包括两个方面：①出租车大多在市区活动，高层建筑容易影响GPS信号并阻碍信号的接收；②GPS接收机在通过地下隧道时不能接收信号，因此信号会中断[16]。

表1 出租车GPS数据的样本记录

由于这些问题，需要对原始数据进行预处理，步骤如下：①验证经纬度属性，查询纬度和经度数据是否在有效区域内。以武汉为研究区，武汉市的全纬度和经度范围为：经度113°41′—115°05′E和纬度29°58′—31°22′N。②需要核实旅客的状态，出租车的载客状态是“0”或“1”，删除了不在这个范围内的数据。③根据所选择的公交线路，找出该地区的出租车数据。本文以武汉580公交线(如图4所示)为试验对象，公交线路位于武汉汉阳区(如图5所示)，汉阳地区的数据足以支持整个试验，提取30°28′35″—30°36′34″N，114°7′—114°18′E范围内的数据。

图4 武汉市580路公交车路线

图5 武汉市汉阳区

2.2 公交车站点合理性分析

使用13 d内武汉市2046辆出租车的轨迹数据，并提取乘客在出租车上的坐标作为基本数据。利用Canopy-K-means均值聚类算法，分析了武汉市580条公交线路公交车站选址的合理性，并预测了公交站点的位置。分析过程分为以下两个步骤：①利用Canopy-K-means均值聚类算法，对武汉市汉阳区所有乘客点的坐标数据进行聚类，得到580路公交线路上的聚类中心点，聚类中心用于确定乘客的热点出行区域；②在地图上对公交站点的坐标数据和聚类后的坐标数据(包括聚类中心)进行可视化显示，并计算得到车站与集群中心之间的距离，然后进一步比较分析公交站点选址的合理性。

2.2.1 运用Canopy-K-means聚类算法确定聚类中心

首先，获取出租车上车地点数据，对数据进行预处理后，数据已经按车辆ID和时间排列，需要通过Map-reduce分布式处理系统提取载客信息由0变成1的节点数据，即为上车点坐标数据。其次，Canopy-K-means聚类算法需要分两步使用，Canopy算法聚类过程包含两个参数T1、T2(T1>T2)，其中T1、T2都表示数据集中的点距Canopy算法中心点Ci的距离,若距离小于T1，则将轨迹数据点放入以Ci为中心的限定范围中；若距离小于T1且小于T2,则将该点与Ci强关联，在使用K-means算法时则不需要计算数据点到给定随机点的距离，只需要计算数据点到Canopy中心点的距离即可。T1、T2的选取将影响聚类结果的效果。最后，经过多次迭代试验，确定T1的值为500 m、T2的值为250 m时，得到的效果最佳。

基于预处理后的上车点坐标数据得到聚类结果，并将结果进行可视化显示，如图6所示。由于本文研究主要对比了580路公交线路中公交站点位置的合理性，因此选取580路公交线路附近的Canopy聚类中心点进行可视化显示，否则显示的数据太多，消耗的计算机资源过多，不利于试验的顺利进行。可以看到，在580路公交车路线上出现了不同形状、不同位置的点集，特别地将聚类中心点用黑色点标注出来。

图6 算法聚类结果

2.2.2 对比公交站点地址和聚类中心点，预测合理的公交车站点

将现有的23个公交站点在地图上显示(如图7所示)，并和已获取的一系列中心点对比，求得现有公交站点和聚类中心的距离Xi,若Xi距离小于10 m，则认为该站点符合出行公共交通路线选择，若大于10 m，则认为该站点可以进行改进。试验结果如图8所示，23个公交站点中，Xi小于10 m的有18个，大于10 m的站点有5个。故23个公交点中有18个为合理公交站点，5个为不合理公交站点，预测成功率达78.26%。

图7 聚类中心和公交站点

2.3 预测公交车间隔时间

2.3.1 客源量的变化特征

目前，在上下班高峰期，公共交通路段经常面临大面积堵车现象[17]。据统计，一部分原因是因为路段中间经常会有公交车将路口卡死，或因路段上公交车太多导致交通拥堵。合理的安排公交车发车频率可有效缓解交通堵塞问题，降低公交车因为体积大而带来的问题，为人们出行提供便利。为研究人们在一周内不同时间的变化特征，将周一至周日的出行总量进行统计，如图9所示。由该图可知，乘客的出行规律与载客的时间分布紧密相关。除周一、周二、周三工作日上班时间外，出租车载客量始终处于较高的水平，以周六、周日出行总量最多。周六出行水平高于周日，这是由于周六处于假期的第一天，人们出游、购物、聚会正值高峰；相比较而言，周日载客量明显减少，因为部分人们在收假上班的状态，部分潜在乘客会选择在家休息以准备完成周一的新任务。

图8 聚类中心与公交站点对比

图9 一周内客流量变化

2.3.2 一天中不同时间段的客流量分析

为对一天中不同时段的客流量的变化特征进行分析，笔者对所有的乘车点位置数据进行了时间统计，以2 h作为时间间隔，统计12个时间段内的上车次数，然后进行对比分析，如图10所示。

由图10数据分析可得：

(1) 一周内每天的数据变化量的趋势相近，但依时段不同，客源量有较大的波动。工作日和周末的客源量有明显区别。周末在6:00以后出行的人数减少，且周末的波动更加平稳，工作日波动更为剧烈。

(2) 从出行时间上来看，0:00—6:00均处在客源量下降的趋势当中，这与人们的作息时间紧密相关；而6：00以后，人们开始出门上班，故在6：00—8：00区间为出行高峰期；8：00—10：00客源量达到顶峰，意味着堵车最有可能发生在这段时间内；接下来从10：00—16：00客源量相对平稳；16：00左右，客源量又开始呈小幅上升趋势，因为上班族下班、学生放学等因素；20：00开始，是夜生活最繁忙的时候，人们的出行量相对增多，变化最突出的是星期五，因为正逢下班放假时间，客流量出现短暂高峰期。

图10 一天中不同时段客流量变化

(3) 结合以上分析，8：00—10：00、14：00—16：00和20：00—22：00这3个时间段为客流量高峰期，分别对应的客流总量为10 000、8000、8500。式(1)中各参数值为：2 h是120 min，一辆普通公交车载客人数约为55人，则8：00—10：00区间内发车时间间隔为3 min，14：00—16：00区间发车时间间隔为4 min，20：00—22：00区间发车时间间隔为4 min。在其他时间段中适当地降低发车频率以减少道路拥堵情况。

3 结 语

本文研究以武汉市2014年7月31日—2014年8月12日总计13 d 2064台出租车的GPS轨迹数据为研究对象，通过Map-reduce分布式平台提取出租车客源上车位置数据，再结合Canopy-K-means算法对数据进行聚类，并对提取的出租车客源进行了量化；再结合武汉市580路公交车站点设站位置，对比分析了公共交通站点选址合理性，讨论分析了在不同时段公交车发车频率。研究表明：①武汉市580路公交路线中总共23个站点，其中18个站点设置合理，5个站点有待改进，预测准确度达到78.26%。在将来的规划中，选择在本试验中得出热点区域的中心作为公交车站选址是合适的。②在每天的8：00—10：00、14：00—16：00和20：00—22：00这3个时段可以适度提高公交车的发车频率，时间间隔分别为3、4、4 min，其他时段适当降低公交车发车频率，以减缓交通拥堵情况。

分析公共交通站点选址、公共交通发车频率能为城市规划者提供决策支持，真实反映客源的时空分布特性。该方法同时也存在一定的不足，如未考虑到乘客位置的不确定性对公交车站选址的影响，未利用多源数据进行综合性行分析，这将是后续研究的内容。