论文部分内容阅读
【摘 要】公交运行线路的制定需要了解区域内乘客最常用的通勤线路，本文提出了一种基于Apriori算法、DBSCAN算法和模糊支撑树聚类的公交路线聚合算法，可以在已知路网拓扑结构以及区域内客流OD特征的条件下，求解区域内的典型路线。本文基于深圳市公交IC卡数据验证了所提出方法的有效性。
【关键词】公交路线聚合；典型路线；Apriori算法；DBSCAN算法；模糊支撑树聚类
1.引言
随着经济的发展和人口数量的增加，我国一线城市逐渐暴露出公共交通运载能力与出行需求不匹配的问题，交通区域发展出现了不平衡的态势。以深圳市为例，城市内不同的地区职住分离特征愈来愈明显。目前深圳市以福田、南山、罗湖为主要就业地，以宝安、龙华、龙岗为主要居住地，因上班导致的平均通勤距离达到17.9公里。特殊的城市空间结构，给深圳市的城市交通带来大规模潮汐性出行需求。而由于传统的公交网络的布设不符合如今的出行需求总量，导致有效的供给能力不能满足群众多样化、多层次的出行需求，使得有条件的市民倾向于选择个体化出行方式。大量私家车的上路给交通运输网络带来极大的压力，加重了城市道路的拥堵现象，也加剧了空气污染等问题。
为了应对上述问题，在当今互联网+兴起的大背景下，定制公交的概念被提出。定制公交可以以用户提交的需求数据为主，结合公共交通数据、小区住房数据以及地理信息等多维度数据，通过人工智能、机器学习、聚合算法等各种大数据技术，聚合生成线路，为白领用户提供一人一座，家（住宅区）和公司（办公区）之间直达的定制出行服务。大数据技术的应用有助于公交车线路的高效配置，提高车辆的有效路段里程，进而提高交通运输效率；此外，大数据分析也具有较高预测能力，可降低误报和漏报的概率，可随时针对公共交通的动态性给予实时监控。因此，在驾驶者无法预知交通的拥堵可能性时，大数据亦可帮助用户预先了解。除了提升用户的出行体验，也对缓解交通拥堵有很大价值。
为了合理地设置定制公交的线路，需要对行人的出行需求进行调查，掌握乘客的出行规律，并从需求中分析典型的出行路线用于制定行车路线。目前，很多研究者致力于研究基于公交IC卡等数据提取出出行需求特征的方法，一般将出行特征表示为OD矩阵的形式，矩阵中各个元素表示所研究区域的两个区块之间的出行需求。然而，如何基于提取的OD矩阵分析挖掘出最典型的车辆行车线路，仍然是需要不断研究的一个问题，目前，大多研究都将这个问题转化为聚类问题，例如K-means聚类等。
本文提出了一种公交路线聚合算法，在分析得到交通路网拓扑结构的情况下，采用Apriori算法[1]和DBSCAN算法[2]对人们的公共交通出行路线、公交站点、出行时段进行分析归类。随后分析现有公交信息，确定候选典型行车路线，最后根据模糊支撑树聚类算法实现出行路线最优化，本文所提出的算法的流程图如图1。
2.算法介绍
2.1 城市道路网络拓扑建模方法
将城市道路网络的拓扑结构抽象为网络模型，目前主要有两种方法：一种称为为主方法（Primal aproach），是将道路的交叉口抽象为图的节点，连接交叉口之间的路段抽象为边或弧；这种方法的特定是简单直观，保留了较完整的地理相关性，是传统交通网络建模方法，也是目前大部分GIS软件所采用的建模方法。另一种为对偶法（Dual approach），可以认为是主方法的对偶，即将道路抽象为节点，道路与道路的连接关系表示为图的边或弧。一条完整道路的构建是将连续的路段按一定的规则综合而成，目前主要有轴线法、名称法和角度法。其中，轴线法采用轴线代表道路，是依据人的视觉将近似直线的路段合并为一条道路并用一条轴线表示；名称法是指在合并路段时依据道路的名称，将具有相同名称的路段连接在一起；角度法的合并原则是依据格斯塔的连续性原则，通过计算路段与路段的夹角，并根据设定的夹角阈值生成道路。
实践中这两种建模方法各有特点。主方法直观简单，保留了路网的布局特点；对偶法忽略了地理实体的一些地理意义，如地理位置、道路长宽等，更适合探索网络结构下的功能意义。对偶法中合并路段的几种方法也各有优缺点。例如，轴线法轴线的生成主要依据人的视觉判断，合并规则引入主观因素，因此不同的人可能得到不同的轴线地图，即方法不具有唯一性；名称法的局限性在于合并规则完全依赖属性信息，忽略了空间特性并丧失了直观性，在缺少道路名称信息或信息不准确的情况下无法完成；角度法的合并则完全从图形角度考虑，不受人为因素和属性因素影响。
2.2 基于Apriori算法和DBSCAN算法的公交路线聚类
（1）Aprioi算法
Apriori算法是常用的用于挖掘出数据关联规则的算法，它用来找出数据值中频繁出现的数据集合，找出这些集合的模式有助于我们做一些决策。比如在常见的超市购物数据集，或者电商的网购数据集中，如果我們找到了频繁出现的数据集，那么对于超市，我们可以优化产品的位置摆放，对于电商，我们可以优化商品所在的仓库位置，达到节约成本，增加经济效益的目的。
Aprior算法的目标是找到样本中最大K值的K项频繁集，本文采用支持度作为频繁集的判定标准。例如如果找到符合支持度的频繁集AB和ABE，就保留ABE，因为AB是2项频繁集，而ABE是3项频繁集。
Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁2项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁K项集的集合即为算法的输出结果。
（2）DBSCAN算法
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。 DBSCAN的几个概念：
Ε邻域：给定对象半径为Ε内的区域称为该对象的Ε邻域；
核心对象：如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象；
直接密度可达：对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达；
密度可达：对于样本集合D，给定一串样本点p1，p2….pn，p= p1，q= pn，假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达；
密度相连：存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。
2.3 基于模糊支撑树聚类算法生成区域内典型行车路线
区域典型行车路线库由模糊支撑树聚类算法实现。根据OD站点信息利用模糊支撑树聚类算法的程序生成最优定制公交出行路线。最终该区域中各OD间的最优公交出行线路通過聚合构成区域典型行车路线。下面是对模糊支撑树聚类算法的介绍：
（1）支撑树
支撑树算法也叫生成树算法，在图论的数学领域中，如果连通图 G的一个子图是一棵包含G 的所有顶点的树，则该子图称为G的生成树（SpanningTree）。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。常用的生成树算法有DFS生成树、BFS生成树、PRIM 最小生成树和Kruskal最小生成树算法。
（2）模糊支撑树聚类方法
模糊决策树算法是传统决策树算法的一个扩充和完善，使得决策树学习的应用范围扩大到了能处理不确定性。模糊决策树学习的归纳结果与传统的比较，由于合理地处理了不精确信息，从而有着更强的分类能力及稳健性，使得知识表示的方式更为自然。由于能生成不同水平和不同置信度的推理规则，故而提供了一种构造专家系统的有效途径，并可为决策者提供丰富的决策信息。
3.实验结果
本文采用深圳市2012年8月6日至2012年8月10日的全市公交 IC 卡刷卡数据，以及相应时期的车站坐标、线路长度以及站距数据，来验证本文所提出的算法。选用这五天数据的原因为，这五天为连续工作日（周一至周五），并且没有假期。而在此阶段，学生大多已经放假，其中的通勤乘客主要是以上班为主，满足本文的研究对象。
对该周工作日的地铁刷卡卡数及记录数进行统计，得到表格如下：
随后统计每张卡的刷卡次数，统计结果如图3：
通过设置合理的支持度阈值，基于Aprioi算法可以成功地识别乘客的通勤线路
为了解决共站问题，即有些车站实质上是一个车站，却因为线路不同，有不同的站号；有些车站距离很近，乘客有多种出行选择，而不同车站识别结果却不同；本文采取利用 DBSCAN 算法对站点进行聚类。算法输入的数据为深圳公交车站站距位置表，其中包括了公交、地铁的车站站距以及坐标。全表共有 61136 个不同的车站，将车站标识以及坐标输入算法程序，之后新建字段―新车站标识‖，将算法识别后的结果，每个簇赋新值存入新车站标识中。在运行完算法后，最终得到新车站标识 7264 个。将全部 61136 个站点压缩为 7264个站点，压缩率 11.88%，为解决共站问题起到了很好的效果。
通勤乘客的出行时段虽然较为规律和固定，但是却又有波动性，尤其是下班时间。一般上班时间是有要求固定的，而下班时间却并不固定，因为会有加班或是下班后有活动的特殊情况。因此，采用时段模糊处理。改进方法后，再次对通勤乘客进行了识别，识别结果如下：
随后我们基于模糊支撑树聚类生成了区域内的典型行车路线，所得到的结果与我们先验的认知较为相符。
4.结束语
本文提出了一种公交路线聚合算法，基于交通路网拓扑结构和出行客流OD特征，采用Apriori算法、DBSCAN算法和模糊支撑树聚类算法分析区域内每位乘客的通勤路线并最终求解了区域内的典型行车路线。本文、基于深圳市公交IC卡刷卡数据对所提出的算法进行了验证，证明了本文提出的算法的有效性。
基金项目：深圳市科技计划项目（KJYY20160331162313860）
参考文献：
[1] Agrawal R，Srikant R.Fast algorithms for mining association rules[M]// Readings in database systems（3rd ed.）.Morgan Kaufmann Publishers Inc.1996.
[2] Ester M，Kriegel H P，Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]// International Conference on Knowledge Discovery & Data Mining.1996.
（作者单位：深圳市东部公共交通有限公司）
【关键词】公交路线聚合；典型路线；Apriori算法；DBSCAN算法；模糊支撑树聚类
1.引言
随着经济的发展和人口数量的增加，我国一线城市逐渐暴露出公共交通运载能力与出行需求不匹配的问题，交通区域发展出现了不平衡的态势。以深圳市为例，城市内不同的地区职住分离特征愈来愈明显。目前深圳市以福田、南山、罗湖为主要就业地，以宝安、龙华、龙岗为主要居住地，因上班导致的平均通勤距离达到17.9公里。特殊的城市空间结构，给深圳市的城市交通带来大规模潮汐性出行需求。而由于传统的公交网络的布设不符合如今的出行需求总量，导致有效的供给能力不能满足群众多样化、多层次的出行需求，使得有条件的市民倾向于选择个体化出行方式。大量私家车的上路给交通运输网络带来极大的压力，加重了城市道路的拥堵现象，也加剧了空气污染等问题。
为了应对上述问题，在当今互联网+兴起的大背景下，定制公交的概念被提出。定制公交可以以用户提交的需求数据为主，结合公共交通数据、小区住房数据以及地理信息等多维度数据，通过人工智能、机器学习、聚合算法等各种大数据技术，聚合生成线路，为白领用户提供一人一座，家（住宅区）和公司（办公区）之间直达的定制出行服务。大数据技术的应用有助于公交车线路的高效配置，提高车辆的有效路段里程，进而提高交通运输效率；此外，大数据分析也具有较高预测能力，可降低误报和漏报的概率，可随时针对公共交通的动态性给予实时监控。因此，在驾驶者无法预知交通的拥堵可能性时，大数据亦可帮助用户预先了解。除了提升用户的出行体验，也对缓解交通拥堵有很大价值。
为了合理地设置定制公交的线路，需要对行人的出行需求进行调查，掌握乘客的出行规律，并从需求中分析典型的出行路线用于制定行车路线。目前，很多研究者致力于研究基于公交IC卡等数据提取出出行需求特征的方法，一般将出行特征表示为OD矩阵的形式，矩阵中各个元素表示所研究区域的两个区块之间的出行需求。然而，如何基于提取的OD矩阵分析挖掘出最典型的车辆行车线路，仍然是需要不断研究的一个问题，目前，大多研究都将这个问题转化为聚类问题，例如K-means聚类等。
本文提出了一种公交路线聚合算法，在分析得到交通路网拓扑结构的情况下，采用Apriori算法[1]和DBSCAN算法[2]对人们的公共交通出行路线、公交站点、出行时段进行分析归类。随后分析现有公交信息，确定候选典型行车路线，最后根据模糊支撑树聚类算法实现出行路线最优化，本文所提出的算法的流程图如图1。
2.算法介绍
2.1 城市道路网络拓扑建模方法
将城市道路网络的拓扑结构抽象为网络模型，目前主要有两种方法：一种称为为主方法（Primal aproach），是将道路的交叉口抽象为图的节点，连接交叉口之间的路段抽象为边或弧；这种方法的特定是简单直观，保留了较完整的地理相关性，是传统交通网络建模方法，也是目前大部分GIS软件所采用的建模方法。另一种为对偶法（Dual approach），可以认为是主方法的对偶，即将道路抽象为节点，道路与道路的连接关系表示为图的边或弧。一条完整道路的构建是将连续的路段按一定的规则综合而成，目前主要有轴线法、名称法和角度法。其中，轴线法采用轴线代表道路，是依据人的视觉将近似直线的路段合并为一条道路并用一条轴线表示；名称法是指在合并路段时依据道路的名称，将具有相同名称的路段连接在一起；角度法的合并原则是依据格斯塔的连续性原则，通过计算路段与路段的夹角，并根据设定的夹角阈值生成道路。
实践中这两种建模方法各有特点。主方法直观简单，保留了路网的布局特点；对偶法忽略了地理实体的一些地理意义，如地理位置、道路长宽等，更适合探索网络结构下的功能意义。对偶法中合并路段的几种方法也各有优缺点。例如，轴线法轴线的生成主要依据人的视觉判断，合并规则引入主观因素，因此不同的人可能得到不同的轴线地图，即方法不具有唯一性；名称法的局限性在于合并规则完全依赖属性信息，忽略了空间特性并丧失了直观性，在缺少道路名称信息或信息不准确的情况下无法完成；角度法的合并则完全从图形角度考虑，不受人为因素和属性因素影响。
2.2 基于Apriori算法和DBSCAN算法的公交路线聚类
（1）Aprioi算法
Apriori算法是常用的用于挖掘出数据关联规则的算法，它用来找出数据值中频繁出现的数据集合，找出这些集合的模式有助于我们做一些决策。比如在常见的超市购物数据集，或者电商的网购数据集中，如果我們找到了频繁出现的数据集，那么对于超市，我们可以优化产品的位置摆放，对于电商，我们可以优化商品所在的仓库位置，达到节约成本，增加经济效益的目的。
Aprior算法的目标是找到样本中最大K值的K项频繁集，本文采用支持度作为频繁集的判定标准。例如如果找到符合支持度的频繁集AB和ABE，就保留ABE，因为AB是2项频繁集，而ABE是3项频繁集。
Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁2项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁K项集的集合即为算法的输出结果。
（2）DBSCAN算法
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。 DBSCAN的几个概念：
Ε邻域：给定对象半径为Ε内的区域称为该对象的Ε邻域；
核心对象：如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象；
直接密度可达：对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达；
密度可达：对于样本集合D，给定一串样本点p1，p2….pn，p= p1，q= pn，假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达；
密度相连：存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。
2.3 基于模糊支撑树聚类算法生成区域内典型行车路线
区域典型行车路线库由模糊支撑树聚类算法实现。根据OD站点信息利用模糊支撑树聚类算法的程序生成最优定制公交出行路线。最终该区域中各OD间的最优公交出行线路通過聚合构成区域典型行车路线。下面是对模糊支撑树聚类算法的介绍：
（1）支撑树
支撑树算法也叫生成树算法，在图论的数学领域中，如果连通图 G的一个子图是一棵包含G 的所有顶点的树，则该子图称为G的生成树（SpanningTree）。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。常用的生成树算法有DFS生成树、BFS生成树、PRIM 最小生成树和Kruskal最小生成树算法。
（2）模糊支撑树聚类方法
模糊决策树算法是传统决策树算法的一个扩充和完善，使得决策树学习的应用范围扩大到了能处理不确定性。模糊决策树学习的归纳结果与传统的比较，由于合理地处理了不精确信息，从而有着更强的分类能力及稳健性，使得知识表示的方式更为自然。由于能生成不同水平和不同置信度的推理规则，故而提供了一种构造专家系统的有效途径，并可为决策者提供丰富的决策信息。
3.实验结果
本文采用深圳市2012年8月6日至2012年8月10日的全市公交 IC 卡刷卡数据，以及相应时期的车站坐标、线路长度以及站距数据，来验证本文所提出的算法。选用这五天数据的原因为，这五天为连续工作日（周一至周五），并且没有假期。而在此阶段，学生大多已经放假，其中的通勤乘客主要是以上班为主，满足本文的研究对象。
对该周工作日的地铁刷卡卡数及记录数进行统计，得到表格如下：
随后统计每张卡的刷卡次数，统计结果如图3：
通过设置合理的支持度阈值，基于Aprioi算法可以成功地识别乘客的通勤线路
为了解决共站问题，即有些车站实质上是一个车站，却因为线路不同，有不同的站号；有些车站距离很近，乘客有多种出行选择，而不同车站识别结果却不同；本文采取利用 DBSCAN 算法对站点进行聚类。算法输入的数据为深圳公交车站站距位置表，其中包括了公交、地铁的车站站距以及坐标。全表共有 61136 个不同的车站，将车站标识以及坐标输入算法程序，之后新建字段―新车站标识‖，将算法识别后的结果，每个簇赋新值存入新车站标识中。在运行完算法后，最终得到新车站标识 7264 个。将全部 61136 个站点压缩为 7264个站点，压缩率 11.88%，为解决共站问题起到了很好的效果。
通勤乘客的出行时段虽然较为规律和固定，但是却又有波动性，尤其是下班时间。一般上班时间是有要求固定的，而下班时间却并不固定，因为会有加班或是下班后有活动的特殊情况。因此，采用时段模糊处理。改进方法后，再次对通勤乘客进行了识别，识别结果如下：
随后我们基于模糊支撑树聚类生成了区域内的典型行车路线，所得到的结果与我们先验的认知较为相符。
4.结束语
本文提出了一种公交路线聚合算法，基于交通路网拓扑结构和出行客流OD特征，采用Apriori算法、DBSCAN算法和模糊支撑树聚类算法分析区域内每位乘客的通勤路线并最终求解了区域内的典型行车路线。本文、基于深圳市公交IC卡刷卡数据对所提出的算法进行了验证，证明了本文提出的算法的有效性。
基金项目：深圳市科技计划项目（KJYY20160331162313860）
参考文献：
[1] Agrawal R，Srikant R.Fast algorithms for mining association rules[M]// Readings in database systems（3rd ed.）.Morgan Kaufmann Publishers Inc.1996.
[2] Ester M，Kriegel H P，Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]// International Conference on Knowledge Discovery & Data Mining.1996.
（作者单位：深圳市东部公共交通有限公司）