一种基于交通网格划分的出租车轨迹数据空间聚类方法.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：1.26M 资料格式：pdf 举报版权申诉

weixin_38598703-12093539-16359647332465957428.pdf-第1页.png

第1页 / 共9页

weixin_38598703-12093539-16359647332465957428.pdf-第2页.png

第2页 / 共9页

weixin_38598703-12093539-16359647332465957428.pdf-第3页.png

第3页 / 共9页

weixin_38598703-12093539-16359647332465957428.pdf-第4页.png

第4页 / 共9页

weixin_38598703-12093539-16359647332465957428.pdf-第5页.png

第5页 / 共9页

weixin_38598703-12093539-16359647332465957428.pdf-第6页.png

第6页 / 共9页

weixin_38598703-12093539-16359647332465957428.pdf-第7页.png

第7页 / 共9页

weixin_38598703-12093539-16359647332465957428.pdf-第8页.png

第8页 / 共9页

文本预览

中国科技论文在线 http://www.paper.edu.cn 一种基于交通网格划分的出租车轨迹数据空间聚类方法# 毛峰1，刘婷2，季民河1** 5 10 15 20 25 30 （1. 华东师范大学地理信息科学教育部重点实验室，上海 200241； 2. 杭州师范大学城市湿地与区域变化研究省重点实验室，杭州 310036）摘要：作为使用最为广泛的交通出行方式之一，出租车的运行轨迹中不但具有道路网络交通信息，还含有乘客的出行行为特征。对出租车轨迹进行有效的空间聚类有利于微观个体活动模式和宏观活动系统的城市空间结构的研究。本文提出了一种利用道路对城市空间进行交通网格划分，进而对大数据量出租车移动轨迹起讫点进行空间聚类的新方法。本文以中国上海市的出租车数据集作为研究案例，对所提方法进行了效果验证，并对方法结果及算法参数优化做了讨论。实验结果表明，与传统聚类方法相比，本研究所提方法能够更好的适应海量出租车轨迹数据，生成更为合理的空间聚类结果。关键词：空间聚类；出租车轨迹；交通网格中图分类号：U491 A spatial clustering method based on traffic grid for taxi trajectory data MAO Feng1, LIU Ting2, JI Minhe1 (1. The GIScience Key Lab, Education Ministry of China, East China Normal University, Shanghai 200241; 2. Zhejiang Provincial Key Laboratory of Urban Wetlands and Regional Change,Hangzhou Normal University,Hangzhou 310036) Abstract: Trajectory data of taxis, one of the most widely used inner-city travel modes, contain rich information about both road network traffic and travel behavior of passengers. Such data can be used to study the microscopic activity patterns of individuals as well as the macro system of urban spatial structures. A novel approach of spatial clustering based on traffic grid from the taxi trajectory dataset with a large number of point locations is proposed in this paper. A case study with a taxi trajectory dataset in Shanghai, China is presented to demonstrate and evaluate the proposed method. The results show that the proposed approach can adapt to massive taxi trajectory better than traditional clustering methods and generate more reasonable spatial clusters. Key words: spatial clustering; taxi trajectory; traffic grid 35 0 引言随着基础设施建设的完善和各城市出租车 GPS 平台的建成，基于出租车 GPS 数据的出行调查的样本覆盖范围越来越广，获取成本越来越低，且具有高时空分辨率的特点，是智能交通系统（ITS）中最常用的获取道路交通信息的手段之一[1]。目前各城市所开展的基于浮动车的交通调查工作大多采用出租车的形式，利用出租车大范围长期的轨迹数据分析一些较为宏观的城市交通和土地利用状况[2]。 40 但是，由于出租车 GPS 数据的高时间分辨率，造成其数据量极其庞大，处理这样的大数据十分困难，同时由于出租车 GPS 数据的高空间分辨率，造成不同车辆甚至同一车辆在基金项目：国家自然科学基金（40771138）；国家“十二五”863 计划重大专项课题（2013AA12A402）作者简介：毛峰(1984-)，男，博士生，主要研究方向：空间数据挖掘、城市计算通信联系人：季民河（1955-），男，教授，博士生导师，主要研究方向：出行模式研究. E-mail: mhji@geo.ecnu.edu.cn - 1 -

中国科技论文在线 http://www.paper.edu.cn 相同地点获取的 GPS 点，在空间上仍然表达为截然不同的位置对象，即便在出租车出现非常密集的地区，也极少在数据中出现两个完全重合的定位点，因此将多个理应具有相同空间信息的 GPS 点进行聚类是较好的解决方案[3]。 45 本文主要关注根据出租车上下车记录提取的轨迹起讫点（OD）信息，该信息仅记录乘客出行的起点和终点，而忽略掉行驶过程中的路径信息。从研究乘客行为的角度来说，出租车的行驶过程并不重要，乘客的上车地和下车地才是关注点，因此研究 OD 信息即是研究人的行为及与其所在空间的关联关系。通过对 OD 信息进行有效的空间聚类，有利于从散乱的 50 GPS 位置空间分布中提取出有意义的模式，进而对城市居民个体活动和城市空间结构开展深入研究。从技术上来说，聚类方法通常可分为划分方法、层次方法、基于密度的方法和基于网格的方法，这些方法各有优缺点，分别适用于不同的应用场景[4-8]。由于出租车轨迹在空间分布上的特殊性，上述各类方法均无法单独应用在以出租车轨迹为对象的聚类场景中。相比较 55 而言，基于区域划分和网格聚类的方法对于空间数据更为适用[9-10]。本文针对出租车轨迹数据提出了一种基于交通网格划分的 OD 点空间聚类方法，能够有效提高出租车 OD 点的聚类效果，这本质上是一种网格法与密度法相结合的改善方法。 1 方法论 1.1 基于交通网格划分的 OD 点空间聚类 60 由于出租车轨迹分布的特殊性，对其聚类通常比较困难，其一，出租车轨迹在全局区域范围内分布极不均匀，在城市中心呈现极大的聚集性，而在城市周边其分布又极为稀疏；其二，出租车轨迹在局部区域分布也不均匀，呈现出以城市干道为中心的线型聚集；其三，出租车轨迹可在空间上任意位置离散出现，难以划定噪声点，即使出现传统意义上的噪声点也具有其语义特征，不可轻易消除，需将其纳入到聚类中。为了更好地提高对出租车 OD 点进 65 行聚类的效果，本文提出了一种利用城市道路数据的基于交通网格划分的聚类方法。基于交通网格划分的聚类方法的过程和策略如图 1 所示。对于通过将 OD 点与交通网格叠加所形成的初始聚类簇，将出现两种情况需要予以解决，一是聚类簇过大且出现明显的聚类分化，即一个簇需要分裂成多个簇；二是簇过小需要与周边的簇进行合并。 70 1.2 聚类簇分割与合并在第一种情况中，需要判断聚类簇是否过大，以及聚类分化是否明显，为此本文引入两个参数：聚类簇大小的警戒值 θ 和最大密度因子 λ。当聚类簇的大小超过警戒值 θ 时，表示该簇过大，有可能需要将其进一步分割，但是分割过程并不是必须进行，在某些情况下，若原聚类簇中各点分布均匀完整且密度适当，则不必强制性地将其分割，为此引入聚类簇的密度的度量参数——簇密度指标[11]。为解释该参数，首先引入如下概念： 75 定义1 （相邻对象）对于给定对象 p 和给定搜索距离 k，聚类簇中所有与 p 的距离小于 k 的对象称为 p 的相邻对象。 - 2 -

中国科技论文在线 http://www.paper.edu.cn 80 图 1 基于交通网格划分的出租车 OD 点空间聚类完整过程 Fig. 1 The overall process of traffic grid-based clustering of taxi OD points 定义2 （最大/小簇内距离）对于给定对象 p，其所有相邻对象中离 p 最近的距离称为 p 的最小密度距离，设为 IDmin；对象 p 所有相邻对象中离 p 最远的距离称为 p 的最大密度距离，设为 IDmax，用公式可表达为 85 (1) (2) 其中，dist(p,q)为对象 p 与对象 q 的距离，该距离可以是欧氏距离、曼哈顿距离或其他任意预定义的距离函数，C 为某一聚类簇的元素集合，k 为搜索距离。定义3 （簇内极距比）对象 p 的密度距离 ID 为 p 的最大簇内距离与 p 的最小簇内距 90 离的比值，即 (3) 当 p 的相邻对象为空集，即给定 k 过小而不存在 q 时，属于例外情况，此时 IDmax(p)=IDmin(p)=0，则人为设置 ID(p)=1。类似的，若点 p 有 1 个邻居对象，则 IDmax(p)=IDmin(p)，其 ID(p)=1。 95 至此，由簇内极距比可以导出聚类簇的密度指标：定义4 （簇密度指标）对于某个聚类簇C，其密度指标为： (4) 其中，|C|为聚类簇 C 的大小。可以留意到，当聚类簇十分密集时，对于给定的 k 值， IDmax(p)通常远大于 IDmin(p)，ID(p)趋近于无穷大而导致 ρ 趋近于 0；当聚类簇十分疏松时， 100 对于给定的 k 值，IDmax(p)通常接近于 IDmin(p)，ID(p)趋近于 1 而导致 ρ 趋近于 1。可见， - 3 - 城市道路数据1、对道路线进行求交，得到路口数据2、基于道路路口建立泰森多边形，称为交通网格3、将OD数据与交通网格数据进行叠加，以交通网格对OD数据做初始聚类，得到初始聚类簇出租车OD数据4、对于过大且具有明显聚类分化的初始聚类簇，进行簇分割5、对于过小的初始聚类簇，与周边簇进行簇合并最终聚类簇7、以最终聚类簇中各点生成泰森多边形，并对每个聚类簇进行多边形合并，得到以多边形表示的出租车OD聚类簇6、重复4、5步骤直至每个聚类簇满足要求()(,)|(,)IDminpmindistpqqCdistpqk()(,)|(,)IDmaxpmaxdistpqqCdistpqk()()/()IDpIDmaxpIDminp()1/pCIDpC

中国科技论文在线 http://www.paper.edu.cn ρ 可作为标识聚类簇密度的指标，对于给定的最大密度因子 λ，当 ρ>λ 时表示该聚类簇过于疏松，有再进一步分割为多个簇的可能和必要。在获取的 OD 点初聚类结果中，若聚类簇过小（未达到极大阈值 ε）则需要与周边的簇进行合并，这里涉及到合并策略的问题，即如何确定与周边的哪个簇进行合并。本研究采用 105 的合并策略为道路直连相邻最小聚类簇，判断顺序为是否相邻，是否道路直连，是否最小，是否面积最小。为优化效率，这里提前建立泰森多边形的邻接表和道路连接表（表 1），表中字段 Src_Obj 为目标多边形，Nbr_Obj 为与其相邻的多边形，RdConn 标识二者是否通过道路连通，这里的连通是指直接连通，而非间接连通。判断时通过查表可直接找到与目标多边形相邻且道路连通的多边形，若有多个，则取其中最小的簇，若仍有多个，取面积最小的 110 簇作为最终的合并对象。表 1 TrafficGrid 邻接表 Tab. 1 Adjacency List for TrafficGrid ObjectID Src_Obj Nbr_Obj RdConn 1 2 … 1 1 … 5552 5568 … 0 1 … 1.3 算法描述图 2 所示为整个重聚类算法的伪代码，算法输入一组初始聚类簇集合 D，输出结果为最 115 终聚类簇集合 C。为保存最终聚类簇，算法一开始将 C 设置为空集合，接下来对集合 D 按簇大小从小到大进行排序，以便从每次从最小的簇开始处理（ⅰ）。算法的目的是将初始聚类簇集合 D 中的所有元素处理完毕，因此循环查询集合 D，只要 D 不为空集合，即内部仍然存在簇，则进行如下处理过程（ⅱ）：从 D 中取出第一个元素 Di（即 D 中最小的簇），若 Di 的大小小于阈值 ε，进行合并操作；若 Di 的大小大于阈值θ 且在给定的搜索范围 k 下 120 Di 的密度因子大于阈值 λ，进行分割操作；否则判断 Di 满足最终聚类簇条件，将 Di 存入最终聚类簇集合 C。在合并操作中，首先需要找出合并目标簇（ⅲ），GetNbrMergeCluster(Di)方法从 TrafficGrid 表中以 Src_Obj=Di，RdConn=1 为搜索条件，检索出所有满足条件的 Nbr_Obj 值，从中取最小的簇，若有多个相同大小的最小簇，则取交通网格面积最小的一个，设该簇为 125 Dk。将 Di 与 Dk 进行合并得到新簇 D’，且|D‘|=|Di|+|Dk|，并将 D’按大小顺序插回初始聚类簇集合 D 中（ⅴ）。分割操作本质上是对聚类簇做子聚类的过程，理论上该步骤可以采用任意适当的聚类算法。为求简单高效，本研究在子聚类过程中选择了 k-means 聚类算法，取聚类数为 2（即把目标簇一分为二）。为了减小随机性，在 kmeans 算法中，取相距最远的两点作为聚类中心， 130 而不是采用传统 kmeans 算法的随机聚类中心。算法结果为 Dx，Dy 两个子簇（ⅵ）。最后分别将 Dx 和 Dy 按其大小顺序插回到初始聚类簇 D 中。在聚类簇的分割-合并过程中，会出现无限循环（endless loop）的特殊情况，即分割后的两个聚类簇未达终止要求，在第二次循环过程中又因满足合并条件而被合并在一起，亦或者是相反。解决这种情况，规定在合并过程中若合并双方是由初始聚类簇分割而来，则无需 135 合并，将较小者直接存入最终聚类簇 C（ⅳ）。 - 4 -

中国科技论文在线 http://www.paper.edu.cn 算法 1 出租车 OD 点重聚类 // 输入： // D = {D1, D2,…, Dn} 一组聚类簇 // ε：聚类簇大小的极小阈值 // θ：聚类簇大小的警戒值 // λ：最大密度因子 // k：搜索距离 // 其中 ε<θ // 输出： // C = {C1,C2,...,Cm} 一组聚类簇 C = {} Sort(D) //(ⅰ) While D != {} Do //(ⅱ) Di = put(D) If |Di| < ε Then Dk = GetNbrMergeCluster(Di) //(ⅲ) If Dk 与 Di 是由初始聚类簇分割而来 Then //(ⅳ) Push(C, Di) D’ = Merge(Dk, Di) Insert(D, D’) //(ⅴ) Else If |Di| > θ and DD(Di,k) > λ Then {Dx,Dy} = kmeans(Di,2) //(ⅵ) Insert(D, Dx) Insert(D, Dy) Else Push(C, Di) 图 2 出租车 OD 点重聚类算法 Fig. 2 The re-clustering algorithm of taxi OD points 2 案例研究 140 2.1 研究区与数据本文的研究区域为中国上海市，该市公共交通（含地铁交通）客运量 1289.9 万人次/天，出租汽车 284.8 万人次/天，共有出租汽车 49111 辆[12]。本文所使用的出租车轨迹数据来自 4 个主要的出租汽车运营公司，采集时间段为 2009 年 5 月 15 日 0：00—24：00，反映了出租汽车一个运营日的出行特征。经过数据预处理，最后形成可用于分析的车辆样本 9349 辆， 145 共计 35856715 条记录，并从中提取出轨迹 OD 点。此外，本研究为实现基于交通网格的出租车 OD 点聚类，使用了上海市道路数据集，该数据集中共有道路 5494 条。对所有道路求交点，获得 5207 个路口，利用路口信息建立泰森多边形，得到交通网格，将落在同一个交通网格中的出租车 OD 点作为一个聚类簇，从而对原始的 OD 点进行一次初始聚类，由前文所述可知，聚类簇的数量与交通网格数相同，即共 150 得到 5207 个聚类簇（图 3）。 - 5 -

中国科技论文在线 http://www.paper.edu.cn (a) (b) 图 3 基于交通网格的初始聚类。(a)所求得的路口及其交通网格。(b)利用交通网格得到的 OD 点初始聚类。 Fig.3 Initial clustering based on traffic grids. (a) The intersections and traffic grid. (b) The initial clusters 155 generated by traffic grid. 2.2 出租车 OD 点聚类结果与参数优化的讨论利用算法 1，设 ε=100，θ=200，λ=0.03，k=100，5207 个初始聚类簇被重聚类为 2850 个最终聚类簇，基于最终聚类簇中的出租车 OD 点生成泰森多边形，并将同一聚类簇的多边形合并，合并结果可参见图4。 160 在算法 1 中共需要输入 4 个参数：聚类簇大小的极小阈值（ε）、聚类簇大小的警戒值（θ）、：最大密度因子（λ）和搜索距离（k）。其中 ε 用于控制聚类簇的理论最小值，这意味着 ε 取值越大，最终得到的聚类簇普遍更大，反之亦然。同样，θ 用于控制大聚类簇的规模。最终聚类簇的大小大多数被限制在区间[ε, θ]中。但是仍然会有大小在此区间之外的聚类簇存在，小于 ε 的聚类簇是由某个聚类簇分割的结果又无法被合并到其他周边簇而产生， 165 大于 θ 的聚类簇是由于其密度因子未达到分割要求。总体而言，ε、θ 并无最优化的取值，其输入取决于实际的聚类分辨率需求。图4 所示为相同 λ 和 k（λ=0.03，k=100）、不同 ε 和 θ 组合取值下的聚类结果及其局部细节，其中左图为 ε=250，θ=500 的聚类结果，右图为 ε=100， θ=200 的聚类结果。可以看到，二者的聚类结果在总体形状上差异不大，左图基本是在右图的基础上合并部分聚类簇而得，使得其簇的数量减少，单个簇的规模更大。而 ε 和 θ 产生的 170 微小变化则不会影响到最终聚类结果。 λ 和 k 的取值相对复杂，且对于不同的聚类簇，在计算其密度因子时，计算结果与 k 具有一定的相关关系，为研究这种相关性，本文在不同的 k 值下计算了所有 5207 个初始聚类簇的密度因子并统计了计算结果的平均值、中位数和四分位数。本研究发现，k 的取值与密度因子的平均值、中位数和四分位数都能用幂函数进行很好的拟合，回归模型建立如下： 175 (7) 其中，y1 为密度因子的平均值，y2 为密度因子的中位数，y3 为密度因子的四分位数， (5) (6) x 为搜索距离。对公式(6)求导搜索距离对密度因子平均值的一阶导数，可以发现，当 k>200 180 后，k 值的增长对 y 值变化的影响开始减弱，当 k>500 后 k 值的变化对 y 值的影响极其微弱。对中位数和四分位数的研究亦能反映相同情况。这意味着较大的 k 值取值能够得到更为稳定 - 6 - 0.423211.39,0.989yxR0.680221.28,0.932yxR0.677230.81,0.941yxR

中国科技论文在线 http://www.paper.edu.cn 的密度因子计算结果。但是另一方面，由 k 增大带来的计算量也将相应增大。根据密度因子的定义，在理想状况下，对于一个点分布均匀的区域，当搜索距离增大 1 倍，搜索区域内的 185 点数量将增大为原来的 4 倍，为得到密度距离，需要计算搜索区域内任意两点之间的距离，该过程的时间复杂度为 O(n2)，因此 k 的增大所带来的计算消耗是非常可观的。综合以上分析和研究区域数据的实际情况，本研究认为 k 值取值在 100 到 300 之间是合理的。在确定 k 值后，最大密度因子 λ 可取整体密度因子的中位数或四分位数。取中位数意味着规模过大的初始聚类簇中将有一半需要参与重聚类过程被分割，而取四分位数则意味着需要重聚类的簇占四分之三。 190 图 4 不同的 ε 和 θ 取值聚类结果的对比 Fig. 4 Comparison of clustering results with different ε and θ. 2.3 对比验证本文将所提算法与传统常用空间聚类算法 DBSCAN 做了对比验证分析。DBSCAN 算法 195 的聚类结果对其参数 ε 和 MinPts 的设置较为敏感，其准确性依赖于参数设置的正确性。通过实验，我们认为将参数设置为 ε=25，MinPts=3，对于本研究所采用的数据集来说是较为合理的。我们将本研究的数据集分别应用本文所提方法和 DBSCAN 聚类算法进行空间聚类，并进行比较（图 5）。可以看到，通过 DBSCAN 算法所做的聚类结果在地块合并后产生了大量空白区域，在 OD 点分布稀疏的地方该现象更为明显。另外，DBSCAN 算法将密集区 200 域的大量点合并，减少了密集区域聚类簇的数量，降低了该区域聚类簇的空间分辨率。 - 7 -

中国科技论文在线 http://www.paper.edu.cn (a) (b) 图 5 基于交通网格聚类方法与 DBSCAN 聚类算法对比。 (a)应用基于交通网格的聚类方法生成的聚类结 205 Fig. 5 A comparison of the traffic grid-based clustering and the DBSCAN algorithm. (a) The result of traffic grid-based clustering method proposed in this paper. (b) The result of DBSCAN clustering method 果。(b)采用 DBSCAN 算法生成的聚类结果 3 结论本文提出了一种基于交通网格划分的出租车原始 GPS 轨迹数据空间聚类方法，并以上海市的案例研究对所提方法进行了验证，结果表明该方法能够有效地处理海量 GPS 轨迹数 210 据，从大量 GPS 轨迹点中识别出具有特定语义信息的自然区域，提高出租车 OD 点的聚类效果。本文所提的聚类方法具有如下优点：首先该方法能够在不同点密度分布的区域创建相应密度的聚类簇。这意味着在高密度区域，算法将创建足够数量的聚类簇以保证足够大的数据分辨率，而在低密度区域，算法会创建较少的聚类簇以降低数据冗余，从而降低出租车轨迹数据不均匀分布特征的影响。其次，该方法对空间位置的分布形状不敏感，即使出租车轨 215 迹大多呈条带状分布，算法亦能很好的检测到。大体上，本文所提出的方法有如下几方面的限制。首先，该方法依赖于路网数据，路网的准确性和时效性会对分析结果的准确度和精度产生影响，在快速城镇化推进的中国城市中这种影响更为明显，解决办法之一可以考虑利用 OpenStreetMap 这样的众包地图进行数据的快速迭代；其次，本方法仅适用于出租车 GPS 轨迹数据，对于智能手机、移动通讯等其他 220 城市传感器数据的适用性和有效性并未作出检验和评估。 [参考文献] (References) 225 230 235 [1] Schäfer R-P, Thiessenhusen K-U, Brockfeld E, Wagner P. A traffic information system by means of real-time floating-car data[A]. ITS World Congress 2002[C]. Chicago, 2002. 1-8. [2] Li Q, Zhang T, Wang H, Zeng Z. Dynamic accessibility mapping using floating car data: a network-constrained density estimation approach[J]. Journal of Transport Geography, 2011, 19(3): 379-393. [3] Guo D, Zhu X, Jin H, Gao P, Andris C. Discovering Spatial Patterns in Origin‐Destination Mobility Data[J]. Transactions in GIS, 2012, 16(3): 411-429. [4] Han J, Kamber M, Pei J. Data mining: concepts and techniques[M]. San Francisco: Morgan Kaufmann Publisher, 2006. [5] Zhang T, Ramakrishnan R, Livny M. BIRCH: an efficient data clustering method for very large databases[A], Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data[C]. Montreal: ACM, 1996. 103-114. [6] Ankerst M, Breunig M M, Kriegel H-P, Sander J. Optics: Ordering points to identify the clustering structure[A]. Proceedings of the ACM SIGMOD International Conference on Management of Data[C]. Philadelphia: ACM, 1999. 49-60. [7] Ester M, Kriegel H-P, Sander J, Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise[A]. Proceedings of the 1996 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. Portland: AAAI, 1996. 226-231. - 8 -

分享到：

赞收藏

资料库

一种基于交通网格划分的出租车轨迹数据空间聚类方法.pdf

相关推荐

开发技术

热门标签

最新资料