一种基于F-DBSCAN迭代聚类的机场巴士候选站点筛选方法

摘要

本发明涉及一种基于F‑DBSCAN迭代聚类的机场巴士候选站点筛选方法，通过应用F‑DBSCAN算法，有效地降低了聚类算法的时间复杂度，提升了数据量级，提高了数据挖掘的准确性，从而成功地从大量OD数据中挖掘出了乘客的最终去向聚集区域，为机场定制巴士候选站点的选取提供了准确的出行信息。

说明书

技术领域

本发明属于智能交通技术领域，特别涉及一种基于F-DBSCAN(Fast-Density-based spatial clustering of applications with noise,即快速的具有噪声的基于密度的聚类方法)迭代聚类的机场巴士候选站点筛选的方法。

背景技术

随着全国及全球之间的交流日益频繁和经济的快速发展，选择航空出行的乘客不断增加，这极大的促进航空运输业的发展。一般来说，机场是一个城市的重要大型交通枢纽，由于机场的特殊性，需要建立在离城市较远的地方，因此机场的交通规划重点为如何构建良好的城市交通，在不影响现有交通效率的情况下尽可能増加机场的服务范围。在枢纽机场地面交通的研究中，国外相关研究较为成熟，且已记入相关的政策法规，而近几年国内学者也有大量关于机场地面交通规划设计与优化研究等方向的学术研究。

北京首都机场已经拥有完善的交通运输网络，包括机场巴士，机场快轨，固定的出租车停靠点，以及近年来兴起的网约车。由于机场巴士采用固定的发车时段，而机场快轨需要多次转乘才能到达目的地，一些赶时间的乘客选择即时发车，并且直奔目的地的网约车或者出租车出行。这些交通出行数据构成了首都机场的公共交通出行OD数据，可以用于重新设计机场巴士线路站点，更好地满足机场出行需求。

发明内容

本发明的技术解决问题：克服现有技术对于不同交通方式数据分析不完整，数据量过小，准确度较低等缺陷，提供一种基于F-DBSCAN迭代聚类的机场巴士候选站点筛选方法，针对特大城市大数据量下的出行需求，能够提出一种行之有效的解法，对海量的乘客出行OD数据进行数据挖掘，分析得出从机场出发的乘客下车的热点聚集区域，为巴士的路线制定提供停靠站点候选站点的选取，从而为后续的定制巴士路线制定方案提供良好的前期数据准备。

本发明技术解决方案：一种基于F-DBSCAN迭代聚类的机场巴士候选站点筛选的方法，实现为：对各种出行的交通工具获得的数据进行预处理，根据预处理后的数据确定乘客的出行轨迹，得到乘客去向的离散终点的经纬度集；对乘客去向的离散终点的经纬度集进行密度聚类，在密度聚类过程中，采用快速DBSCAN聚类方法得出乘客的去向聚集区域，再对乘客的去向聚集区域的聚类结果，进一步进行迭代处理，得到迭代处理后乘客去向的聚集区域，即聚类结果，针对所述聚类结果，依据预设的规则匹配POI站点，最终确定出所需要的机场巴士候选站点。

所述预处理方法包括：各种出行的交通工具的不同订单数据的格式统一化的生成及权值设定，所述各种出行的交通工具的不同订单数据包括：网约车订单数据、出租车订单数据、机场巴士数据、公共汽车数据及地铁刷卡数据。

所述不同订单数据的格式统一化的生成具体包括：

a、统一网约车和出租车订单格式，输出格式为csv文件，字段分别为：刷卡或下订单的时间、上车地点经度、上车地点纬度、下车地点经度和下车地点纬度；

b、通过机场地铁线刷卡数据、机场巴士数据及公共汽车数据匹配出完整出行链，输出为与a步骤输出结果相同格式的csv文件。

所述不同订单数据的格式统一的生成还进一步包括订单数据的权值设定，将网约车和出租车订单生成的csv文件做一份拷贝，与地铁刷卡数据的csv文件做合并处理，网约车和出租车订单的刷卡比重设为2，地铁刷卡和机场巴士、公共汽车数据的比重设为1。

所述根据预处理后的数据确定乘客的出行轨迹，得到乘客去向的离散终点的经纬度；对乘客去向的离散终点的经纬度进行密度聚类，在密度聚类过程中，采用快速DBSCAN聚类方法得出乘客的去向聚集区域的过程如下：

(1)针对乘客去向的离散终点的经纬度集，遍历其中每一个离散的终点，对于其中每一个终点，通过其经纬度计算该终点与其余所有终点的距离，若距离小于设定的半径且满足该条件的终点达到规定的密度，则称这是一个簇，那么这个簇则被称为密度可达区域，并为该区域设置唯一的簇号；若距离小于设定的半径的终点个数没有达到规定的密度将该终点设置为噪声点；

(2)若已经聚类为一个簇，则在该簇内选取四个代表点进行密度可达区域的扩张，即再次聚类。四个代表点分别为：簇内与簇中心点经度相同，纬度分别为簇内最大、最小的两个点，以及簇内与簇中心点纬度相同，经度分别为簇内最大、最小的两个点，对这四个代表点聚类的过程中，若距离这些代表点小于设定的半径的终点的个数达到规定的密度，那么则形成了新的密度可达区域，将该区域与原簇的密度可达区域相接，并将这些终点的簇号设置与原簇一致。

(3)直到输入的数据集中的每个点都被遍历了一次，就完成了聚类。此时输出对应的数据结果，包括该点的经纬度，是否为噪声点的标记信息，以及相应的簇号。其中，未被归入任何一个簇的簇号默认为0；

(4)去除簇号为0、噪声点为1的数据，它们是未被归入任一簇内的噪声点数据，最终得到的结果即是乘客的去向聚集区域。

对所述对于乘客的去向聚集区域的聚类结果，需要进一步迭代处理的具体处理步骤如下：

(1)对于聚类之后的结果，生成csv文件。然后根据不同簇号统计相应的数据量，若某个簇内的数据量超过别的簇的平均数据量2倍以上，则该某个簇需要二次聚类，即迭代处理。从上述csv文件中抽取出对应簇号的数据，存入到新的csv文件，将上述csv文件中的相同数据剔除；

(2)将步骤(1)中抽取出来对应簇号的数据进行二次聚类，去掉数据中的簇号和噪声点标记信息，重新调整传入参数：即半径和聚类密度，再次进行聚类；

(3)将步骤(2)中二次聚类的文件剔除掉簇号为0、噪声点为1的数据，与第一次聚类的结果进行合并；两次聚类产生的簇号可有重复，实际指向的并不是同一块区域，需要对簇号重新编号，然后合并两个csv文件并输出，输出结果即为迭代处理后的乘客去向的聚集区域。

所述针对所述聚类结果依据预设的规则匹配POI站点，最终确定出所需要的机场巴士候选站点的具体方案为：

(1)将大厦、酒店、住宅小区及地铁站分别设置为第一、第二、第三和第四优先级；

(2)根据聚类结果，获取每个簇的中心点坐标。具体步骤为：使用mapgis软件，分别连接每个簇内的所有经纬度点构造出相应的空间区域，然后提取出中心点的坐标并输出；

(3)通过步骤(2)得到的与簇号相应个数的中心点坐标，对于这些坐标，首先对设定范围以内的区域进行POI(Point of Interests,即地理信息系统的兴趣点)的匹配，如果选取到符合要求的停靠站点，如果第一、第二级别的POI，则将最终结果输出，如果没有匹配到合适的站点，则需要进一步扩大匹配范围进行匹配；如果仍然没有匹配到第一、第二优先级的站点匹配到，则考虑第三、第四优先级的POI进行匹配；

(4)通过动态匹配POI的方法，得到每个簇对应的可选站点；

(5)综合考虑乘客消费能力、出行意愿偏好，设立试运营站点作为机场巴士候选站点。

本发明与现有技术相比的优点在于：本发明提供的机场巴士候选站点的选取方法在预处理阶段，遵循“大数据胜过好算法”的原则，统一不同来源的数据类型的格式，并大幅降低数据维度，以期能够在聚类过程中读取大量数据集的目的，最终提升聚类结果的正确性。本发明基于F-DBSCAN的聚类算法，改进了原生的DBSCAN密度聚类算法，进一步加大了聚类计算的数据量级。最终通过特定规则的POI匹配，可以满足不同需求的站点候选站点选取场景，结果收敛较快，同时具有较高的准确性。

附图说明

图1为本发明实施例提供的基于F-DBSCAN的机制巴士候选站点筛选方法流程图；

图2为本发明实施例中数据预处理的流程示意图；

图3为本发明实施例中改进原始聚类算法的原理示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合附图对本发明作进一步的详细描述。

图1为本发明实施例提供的基于F-DBSCAN迭代聚类的机场巴士候选站点筛选方法流程图，包括：

步骤101、对网约车、出租车订单数据，以及地铁刷卡数据进行预处理，具体执行过程如图2所示。

步骤1011、不同数据的格式统一化。

本发明实施例提供的巴士候选站点选取方法在预处理阶段，通过分析不同出行方式的OD数据，通过降维和统一化处理，得到固定日期内，起点一致(均为首都机场T2或T3航站楼附近一公里内为起点的出行数据)、格式一致的乘客出行链数据。具体步骤如下：

(1)针对网约车、出租车、地铁的订单或刷卡数据的字段类型不一致的情况做统一化处理。如地铁的刷卡数据包括上车站点，下车站点，卡号，刷卡时间等等；网约车的订单数据包括上、下车具体位置、经纬度，订单时间，而出租车的订单数据没有上下车具体位置，因此需要对所有的数据的格式进行统一化处理。包括：

a.对不需要的字段进行剔除：除上下车经纬度、刷卡时间或订单时间外的字段全部剔除(此步骤只处理网约车及出租车的订单数据，地铁刷卡数据在第3步中处理)。

b.统一数据格式，输出格式为csv文件，字段分别为：刷卡(订单)时间，上车经度，上车纬度，下车经度，下车纬度。

由于最终聚类结果只需要确定大致范围的聚集区域，而不需要精确到某某小区或者某某酒店，其中原因及最终选点的工作见步骤103及104。因此选择剔除网约车订单中的起始与终点位置的具体地点等冗余数据，可以大幅降低单条数据大小，从而提升数据量级，增加聚类结果的准确性。

(2)由于机场快轨与地铁刷卡系统是分离的，仅通过机场快轨的刷卡数据只可以确定乘客是从三元桥下车还是东直门下车，最终转乘其他线路的地铁的终点是不得而知的，因此需要对机场快轨数据的刷卡id与同日30分钟内的其他地铁刷卡数据进行匹配，从而确认对应乘客最终下车地点，将出行链加入到上述数据集中。具体实施步骤为：

a.将所有上车站号为25(T1、T2航站楼地铁站编号)、27(T3航站楼地铁站编号)，下车站号非25、27的乘客刷卡数据筛选出来，记录其卡号、下车站号及下车时间。

b.遍历当日全部刷卡数据，筛选出与步骤a中卡号相同、且上车站号与其下车站号一致、上车时间为下车时间之后半小时以内的数据。

c.步骤b中选出的数据即为完整的出行链，然后调取百度地图API查询上下车地点的经纬度，统一为步骤(1)中的格式后写入单独的csv文件。

步骤1012、数据筛选及权值设定。

最终需要的数据应当是以T1、T2及T3航站楼一公里内范围为起点，某一周北京市内任意离散点为终点的大量OD(经纬度)数据。因此需要对步骤1011处理后的数据的出发地点和出行时间进行筛选，即：

a、遍历步骤1011处理后的所有数据集，对第一个字段即时间进行筛选，筛选出某一周的全部刷卡数据，然后将第一个字段去掉，写入新的csv文件中，此时得到的是某周内全部的各种交通方式的出行数据。

b、遍历步骤a处理后的数据集，对csv文件中前两个字段组成的经纬度点与首都机场T1、T2、T3航站楼的经纬度数据分别进行比对，如果存在与某点的距离小于1km，则保留该行数据，否则去除该行数据。此时便得到了以首都机场出发、数据格式统一的所有OD数据。

随后需要设定不同订单数据的权值。因为地铁刷卡只属于一个人的记录，而网约车或者出租车通常为2个人或以上，根据综合研究分析，最终决定设定机场快轨刷卡记录的比重为1，网约车和出租车的订单数据比重为2较为合理。然后对上一步得到所有的网约车和出租车订单数据进行一次拷贝，然后与之前选取的地铁刷卡记录进行整合。

最后输出由地铁刷卡数据、网约车订单数据、出租车订单数据构成的起点全部为首都机场的OD经纬度数据。然后将csv文件中前两列数据全部删除，只留下终点的经纬度数据，再次降低单条数据大小来获取整体聚类效果的提升。

步骤102、根据预处理后的订单数据，对数据进行聚类分析。

通过步骤101，已经获取到了不同交通方式出行的以首都机场为起点的终点经纬度数据，只需要对该数据进行聚类，便可以得出从北京首都机场出站的乘客的去向聚集区域。这也是本发明的核心思想。聚类方法采用改进的F(ast)-DBSCAN聚类方法。

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

具体的DBSCAN聚类算法步骤：输入为T1、T2及T3航站楼出发的每一条出行轨迹的终点的经纬度点组成的数据集，入参为：预设半径及最小区域密度。算法的参数选择与实际业务场景相关，对于本发明，半径应当是乘客所能容忍的最长的步行距离，而密度应当与巴士的座位数量、每一趟线路途经的站点数目等因素相关。经过严谨的分析及多次的入参调优，发现将半径设为500米，区域密度设为80(人次)有较好的聚类效果。算法的流程为：

a、遍历每一个经纬度点，对于每一个点，计算其余所有点与之距离，若距离小于设定的半径且满足该条件的点达到规定的密度，则称这是一个簇，那么此时该区域被成为密度可达区域，并为其设置唯一的簇号。否则，则将该点设置为噪声点。正因如此，DBSCAN算法天生对噪声点的排除有良好的机制，非常适用于本发明。因为公共交通数据的经纬度数据不免会有脏数据，而脏数据的附近500米通常不会有80个点，那么该点则会直接被设为噪声点。因此该算法具有较好的容错机制。而其它的聚类算法如k-means、k-medoids等算法是没办法做到的。

b、若已经聚类为一个簇，则对于该簇内除了中心点外的其余所有点进行再次聚类，步骤同上。即若这些点的500米附近仍然有80个以上的点，那么则将该区域与原簇相接，并将当前簇号设置为与原簇号一致。这样得到的簇通常为一个狭长的区域。而这个结论也是由实际问题决定的，是符合基本认知的。

c、直到数据集中的每个点都被遍历了一次，则它们应当都有了相应的状态，如被设置为噪声点，或是被归为某个簇内，此时将结果输出。输出的结果应当按照对应的簇号分别整体输出。如输出文件应当从上到下为簇号为50、49、48…直到0的经纬度点集，每条数据的第三列应当是其簇号，第四列应当为是否为噪声点的标记，规定噪声点则标位1，否则为0。

d、此时去除簇号为0、噪声点为1的行，它们是未被归入任一簇内的噪声点。最终得到的结果即是第一次聚类的结果。

将聚类的结果(经纬度点)投影到MapInfo，可以发现一些居民密度较低的区域如丰台区、石景山区等地，聚类效果较好，而一些居民密度较大的区域如望京、天通苑等区域的点全部连成了一体，没有较为明显的分隔。这是由于算法的输入中密度是固定的，而不同地区的人群分布密度是不尽相同的，所以第一次设定的密度和半径往往不能把密度较大区域的聚集区域区分开，而密度可达区域又是不断扩张的，导致此区域的聚集区域全部连成了一体，部分区域聚类效果较差。因此，本发明创新的提出了迭代聚类，具体实施步骤为：

a、对于第一次聚类之后的结果，根据不同簇号统计相应的数据量。若某个簇内的数据量值较为异常，如大多数的簇内点集个数为80-150左右，而某个簇达到了数百甚至上千，则该簇需要二次聚类。抽取出对应簇号的数据，存入到新的csv文件，将源文件中的相同数据剔除。

b、将步骤a中抽取出来的数据进行二次聚类，去掉其簇号和噪声点标记，降低输入半径及密度(对于本发明，经过分析及多次调参实验，将半径设置为250米，密度设置为60有较好的效果)，再次进行聚类，此时，可以得到密集区域的较为理想的聚类效果。

c、将步骤b中二次聚类的文件剔除掉簇号为0、噪声点为1的数据，与第一次聚类的结果进行合并。但是由于两次聚类产生的簇号可能有重复，而他们实际指向的并不是同一块区域，需要对簇号重新编号，然后合并两个csv文件。

本发明另一个创新便是对区域扩张的过程进行了简化，原始算法区域扩张的原因是如果不进行区域扩张，那么本应是一个同密度可达区域，却会被划分成数个甚至数十个相互重叠的区域，与现实情况完全不符。但是原始算法的密度扩张过程过为繁琐，造成了大量数据的重复计算。因此本发明提出了以当前区域上下左右四个点来代替整个区域的点进行区域扩张，具体步骤如图3所示：以p为中心点的簇以p1,p2,p3,p4四个点为代表点代替整个簇内除p点外其余所有点进行区域扩张，这样就大幅减少了区域扩张的数量级，虽然对计算结果的精度造成了部分的缺失，但是是值得的。因为本步骤得到的聚类结果最终只需要计算出整个区域的中心，然后根据业务场景来进行POI的匹配，对原始区域的区域形状并不敏感。因此，该算法的改进是非常有成效的。

因此，改进后的完整算法具体步骤如下：

即：先将所有的点设置为未访问，然后对于每一个数据集中的经纬度点，找出与该点距离不大于预设半径的所有点的集合，如果该集合的数据量小于给定的密度参数，则将该点设置为噪声点；否则，选取中心点同经度、纬度分别为最大和最小的两个点，以及同纬度，经度分别为最大、最小的两个点共四个点来作为整个密度可达区域的代表点，重复以上聚类过程，对区域进行扩张。最后将扩张后的区域的簇号与原簇号统一，上述即为改进后的DBSCAN算法的完整步骤。

改进的算法与原始算法没有流程上的差别，但是改进了原生算法中计算过于繁杂的区域扩张过程，造成了精度的下降，但是获得了效率的提升。而对于本发明精度的下降并无实际影响。因此通过上述改进的DBSCAN算法，可以高效的筛选出机场巴士候选站点。

步骤103、计算出聚集区域中心的经纬度，根据预设的规则匹配POI。动态扩展POI的匹配结果。

由步骤102，可以得到数十个甚至上百个聚集区域，这些区域只是一些散乱的经纬度点，每个簇有对应的簇类别号。对于每一个簇，应当设立一个或多个站点作为最终动态组线的备选站点。因此首先需要获取整个区域的中心经纬度，然后从中心向外寻找合适的停靠站点，而站点的选取规则是根据业务场景来设定的。对于本发明，站点的最终选取应当是一些知名的标志性建筑，这样可以使得下订单的乘客可以及时选取到合适的站点，对于吸引乘客选择此方式出行有正面积极作用。同时还涉及到应当有容纳巴士调头或者停靠的地理条件等因素。因此经过综合分析与考虑，设定优先级别依次为：知名大厦->知名酒店->住宅小区->地铁站等。

因此，具体实施步骤如下：

a、首先获取所有簇的中心，本发明选用mapgis软件，分别对每个簇内的所有点连接造区，然后提取label点的坐标进行输出。

b、通过步骤a，可以得到与簇号相应个数的中心点坐标，对于这些坐标，首先对其五百米以内的区域进行POI的匹配。如果选取到符合要求的停靠站点，如知名大厦或酒店，则将最终结果输出。如果没有匹配到合适的站点，则需要进一步扩大匹配范围，如加大到1000米范围内，如果还是没有第一、第二优先级的站点匹配到，则可以考虑第三、第四优先级的POI进行匹配。该方法仅做参考，具体问题应当具体对待。

c、通过这样一种动态匹配POI的方法，最终得到每个簇对应的合理的停靠站点。

步骤104、综合分析选取试运营的代表区域。

巴士应当设定试运营阶段，试运营阶段可以揭露出一些研究中没有考虑到的现实问题，如乘客的消费能力，乘客的出行意愿偏好，哪些区域的乘客更愿意拿金钱去换取时间，以及某些路线的制定可能受交通管制或者某些不可抗力因素导致线路不畅通等等情况，从而对研究中这些没有考虑到的因素及时调整，提出合理的解决方案。而首批站点的的选取应当由以下几个因素决定：消费能力水平、地区分布人群特征等。根据经验分析得出高端商务人士可能更愿意采取该出行方式。综合考虑可以选取望京，西二旗等区域内步骤103中选取的站点为首批试营业站点。考虑到可能存在飞机转高铁的出行需求，可以增设北京南站等区域。

总之，本发明在预处理阶段，降低了单条输入数据的大小，大幅提升了数据的量级，提升了最终结果的正确性。在聚类过程中，选取了快速DBSCAN迭代聚类的方法，将不同情况的区域通过迭代的方式高效的求出聚类结果，并最终通过符合业务场景的POI匹配来改善实际业务的盈利点。

以上所述仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。