频数怎么求（如何识别城市交通中的频繁路径）
本文内容来源于《测绘通报》2021年第11期，审图号：GS（2021）7177号
出租车轨迹数据的频繁轨迹识别
邬群勇1,2,3, 王祥健1,2,3
1. 福州大学空间数据挖掘与信息共享教育部重点实验室, 福建 福州 350108;
2. 数字中国研究院(福建), 福建 福州 350003;
3. 卫星空间信息技术综合应用国家地方联合工程研究中心, 福建 福州 350108
基金项目：国家自然科学基金（41471333）；中央引导地方科技发展专项（2017L3012）
关键词：轨迹数据, 轨迹压缩, 轨迹相似度, 聚类簇, 频繁轨迹
引文格式：邬群勇, 王祥健. 出租车轨迹数据的频繁轨迹识别[J]. 测绘通报, 2021(11): 70-75.doi: 10.13474/j.cnki.11-2246.2021.341.
摘要
摘要：为识别城市交通中的频繁路径，本文提出了一种出租车轨迹数据的频繁轨迹识别方法。该方法首先对轨迹数据进行轨迹压缩，以降低计算复杂度；然后基于最长公共子序列和动态时间规整算法进行轨迹相似性度量计算，利用计算得到的轨迹间相似度生成距离矩阵；最后将生成的距离矩阵结合HDBSCAN算法进行聚类得到频繁轨迹。选取厦门岛内两个区域进行试验分析，结果表明，该方法能够识别出轨迹数据集中的频繁轨迹，进而得到城市区域之间通行的频繁路径，对道路规划、路径优化与推荐、交通治理等应用提供帮助。
正文
随着基于位置服务设备的不断普及，获取大规模的移动轨迹数据相比以往变得更加容易
挖掘时空轨迹数据，从中抽取出合适的轨迹模式，是分析与预测城市交通状况和时空轨迹数据挖掘研究中的一个重要课题。频繁模式挖掘算法主要分为两种挖掘模式：一种是基于Apriori算法的频繁模式挖掘，主要针对经典的Apriori算法进行改进，即加入时序特征，并且根据不同应用场景进行相应的优化。文献
本文考虑出租车轨迹的特征及出租车轨迹在城市路网中分布不均匀的特点，提出基于最长公共子序列和动态时间规整算法的轨迹相似性度量方法，并结合基于层次的密度聚类算法对轨迹集进行聚类，最后以厦门市出租车轨迹数据为例进行验证和分析，以期实现出租车轨迹数据集中频繁轨迹的识别。
1 研究方法
方法流程如图1所示。首先，从出租车轨迹数据中提取轨迹数据集，并对其进行轨迹压缩处理；然后，进行轨迹间的相似度计算，得到轨迹间的距离矩阵，矩阵中每一个元素对应一对轨迹间的相似度值；最后，采用HDBSCAN算法对得到的距离矩阵进行聚类分析，识别出轨迹数据集中的频繁轨迹。
图1 基于出租车轨迹数据的频繁轨迹识别流
1.1 轨迹压缩
定义一条轨迹tra, 由若干个轨迹点〈p1,p2,…,pn〉组成。其中，pi=(loni,lati,ti)且t1 出租车轨迹数据集{tra1,tra2,…,tran}中包含若干条轨迹，为使轨迹间的比较更加合理，从而增强频繁轨迹识别的现实意义，本文从出租车轨迹数据中提取起终点相同的轨迹组成轨迹数据集。 为了提升方法效率，需要先对轨迹进行压缩。压缩时需要对轨迹进行开放角计算，如图2所示，定义为式(1),若α<阈值，认为该轨迹点为关键点，则保留该轨迹点。轨迹压缩去除了轨迹中方向变化较小的中间点，得到的结果为原轨迹的子集，保留了原轨迹的主要形态特征。 图2 开放角计算 计算轨迹数据集中轨迹间的角度相似度时，需要先计算轨迹的转向方位角。在轨迹的每个轨迹点处建立直角坐标系，将当前轨迹点至下一轨迹点的连线与当前轨迹点x轴的夹角定义为轨迹的转向方位角，如图3所示，转向方位角的大小范围为[0°,360°)。 图3 轨迹转向方位角 一条轨迹tra 将序列X和序列Y的最长公共子序列(LCS)的长度作为轨迹tra1和轨迹tra2的角度相似度，可由递归公式对其进行求解，即 式中，LCS[i,j]表示序列X[x1,x2,…,xi]和序列Y[y1,y2,…,yj]的最长公共子序列长度；max表示取最大值。 然后对其进行轨迹归一化计算，所得的值越小，表明两条轨迹越相似。其计算公式为 式中，gL为归一化后的轨迹角度相似度；LCS[m,n]为轨迹tra1和轨迹tra2的转向方位角序列的最长公共子序列长度；lmax为轨迹tra1和轨迹tra2的转向方位角序列的长度最大值。 给定两条轨迹tra1 式中，DTW[i,j]为轨迹 对得到的动态时间规划距离进行归一化计算如下 式中，DTW[n,m]为轨迹tra1 式中，d为划分的组距；DTWmax、DTWmin分别为轨迹数据集中最大、最小动态时间规划距离；N为数据集中动态时间规划距离的数量。 轨迹间相似度的最终计算由角度相似度归一化值、距离相似度归一化值加权得到，即 Sim=WLgL+WDgD (7) 式中，Sim表示最终的轨迹相似度；WL表示轨迹角度相似度权重；WD表示轨迹距离相似度权重。 距离矩阵的定义：若轨迹数据集{tra1,tra2,…,tran}中有n条轨迹，则距离矩阵D为一个n×n的对称矩阵，如式(8)所示，矩阵元素Dij表示轨迹trai和轨迹traj之间的轨迹相似度。 给定轨迹数据集{tra1,tra2,…,tran},确定相似度计算权重WL和WD,试验表明轨迹距离相似度相较于轨迹角度相似度对聚类产生较大影响，因此在确定权重时设置WD>WL,计算得到轨迹的距离矩阵D,将距离矩阵输入聚类过程中。基于密度的层次聚类算法HDBSCAN (1) 调用代码库hdbscan。 (2) 将聚类器对象的距离参数metric设置为precomputed(自定义距离),设置聚类的主要参数min_cluster_size(最小类簇大小),以及其他参数(一般设为代码库提供的默认值)。 (3) 输入距离矩阵D到聚类器对象进行聚类。 (4) 得到聚类结果，聚类结果存储在聚类器对象的属性labels_中。它是一个整数数组，每个轨迹数据样本表示有一个整数，同一聚类中的轨迹被赋予相同的编号。类簇标签从0开始向上计数，类簇标签为-1的样本为噪声样本。轨迹数据集{tra1,tra2,…,tran}的聚类返回数组中，类簇标签不为-1且类簇标签相同的轨迹为同一频繁轨迹类型，类簇标签为-1的轨迹为噪声轨迹。 本文所用数据包括OpenStreetMap的路网数据及厦门岛2015年6月13日至2015年6月26日的出租车轨迹数据。出租车轨迹数据用于提取厦门高崎机场T3候机楼、厦门岛东渡码头、厦门火车站500 m范围内的轨迹，预处理后提取得到以厦门高崎机场T3候机楼为起点、东渡码头为终点的出租车轨迹507条，以东渡码头为起点、厦门火车站为终点的出租车轨迹354条。采用上述方法分别对两个数据集之间的频繁路径进行识别。 轨迹压缩的阈值为160°,对厦门机场到东渡码头之间的轨迹数据集进行轨迹压缩，507条出租车轨迹共含有11 447个轨迹点，轨迹压缩后共含有6161个轨迹点；字符标识的固定角度为20°;距离矩阵的计算中设置角度相似度权重WL为0.23、距离相似度权重WD为0.77,设置参数最小类簇大小为5,最终的聚类结果如图4所示。 图4 厦门机场T3候机楼到东渡码头之间轨迹聚类结果显示 由图4可知，本文方法能够很好地识别出厦门高崎机场T3候机楼到东渡码头的频繁轨迹，并且噪声轨迹明显区别于频繁轨迹所在路径。频繁轨迹中类簇0和类簇2包含的轨迹数量分别为203和242条，类簇1只有25条，表明类簇0和类簇2表示的路径为厦门机场到东渡码头最常行驶的路径；类簇1包含的轨迹数量很少，且其表示路径中大部分的路径都与类簇2表示的路径重合，在千亿大厦处的路口发生了路径转变，但剩余路径的距离并没有较大差距，这可能与当时的交通路况或司机的个人驾驶习惯有关。噪声类簇中包含许多与频繁轨迹表示不同的路径，其中可能包含因交通状况而选择其他路径、司机绕路行为等异常轨迹。 将轨迹压缩的阈值设置为160°,354条出租车轨迹共含有10 701个轨迹点，轨迹压缩后共含有5143个轨迹点；字符标识的固定角度为20°;设置角度相似度权重WL为0.3、距离相似度权重WD为0.7,聚类过程中设置参数最小类簇大小为7。最终的聚类结果如图5所示。 由图5可知，东渡码头到厦门火车站之间的频繁轨迹分为5个类簇，其中类簇2包含轨迹最多为135条轨迹，其次为类簇4包含60条轨迹，其余类簇包含轨迹数量相差不大，类簇0为19条，类簇1为25条，类簇3为31条。这表明类簇2代表的轨迹为打车从东渡码头到厦门火车站最常行驶的路径，其次为类簇4代表的路径。由于东渡码头和火车站两区域之间的通行距离较短、通行路径较多，除了最常行驶的两条路径之外，类簇0、类簇1、类簇3表示的路径也有部分司机行驶，且这3个类簇所表示的路径与最常行驶的路径存在部分重叠的路段，这表明从东渡码头到厦门火车站的通勤较灵活，有较多的路径可以选择。噪声类簇的数量达到84条，且可以看出有不少噪声轨迹与频繁轨迹所表示的路径相差甚远，但是噪声类簇也包含部分本该属于频繁类簇中的轨迹。由于东渡码头到厦门火车站之间的距离较短，且大部分轨迹之间的距离较接近，这使得计算轨迹相似度时，作为主要权重计算的轨迹距离相似度区分度并不是很大，结果最终的聚类结果并不如厦门机场T3候机楼到东渡码头之间轨迹聚类的效果好。 图5 东渡码头到厦门火车站之间轨迹聚类结果显示 出租车定位系统的广泛应用为识别城市交通频繁路径提供了新的方向。本文提出了一种新的出租车轨迹间的相似性度量方式，以此结合HDBSCAN算法实现对轨迹数据集中频繁轨迹的识别，并结合真实的轨迹数据和城市路网数据对该方法进行了验证。试验结果表明，该方法能够得到城市交通出行的频繁路径，但是在进行出租车轨迹间相似性度量时，参与计算的指标不够精细，使得聚类结果中噪声轨迹中的部分轨迹没有归类在正确的频繁类簇中。在今后的研究中将考虑增加更多的属性方法，使得轨迹相似度的计算更加精确，以此提升方法的稳定性。 作者简介 作者简介：邬群勇(1973-),男,博士,研究员,研究方向为时空数据分析与地理信息服务。E-mail:qywu@fzu.edu.cn 初审：杨瑞芳 复审：宋启凡 终审：金 君 往期推荐 资讯 ○ 测绘地理信息标准化进展 ○ 多地发布“三调”公报，主要数据成果全在这里了 ○ 新书 |《自然资源管理常用法律法规汇编（最新修订）》 ○ 关注 | 第一张全球地球化学图编制完成 会议 ○ 第一届中国生态系统遥感学术研讨会（三号通知） ○ 《测绘学报》2021年编委会会议在青岛召开 ○ 会议通知 | 2021中国地理信息科学理论与方法学术年会通知（第二号） ○ 关于第八届“测绘科学前沿技术论坛”再次延期召开的通知 《测绘学报》 ○ 智能驾驶环境感知 | 邸凯昌：深空探测车环境感知与导航定位技术进展与展望 ○ 智能驾驶环境感知 | 陈龙： 多智能体协同高精地图构建关键技术研究 ○ 智能驾驶环境感知 | 李德仁：测绘遥感能为智能驾驶做什么？ ○ 智能驾驶环境感知 | 邵晓航：语素关联约束的动态环境视觉定位优化 《测绘通报》 ○ 室内高精度三维测图新技术 ○ 面向上海城市数字化转型的新型测绘 ○ 图像全站仪及图像测量发展与展望 ○《测绘通报》2021年第11期目录 《北京测绘》 ○《北京测绘》2021年第9期摘要推荐 ○《北京测绘》2021年第8期摘要推荐（下） ○《北京测绘》2021年第8期摘要推荐（上） ○《北京测绘》2021年第7期摘要推荐（下） 《测绘科学技术学报》 ○ 《测绘科学技术学报》2021年第1期重点论文推荐 ○ 摘要 |《测绘科学技术学报》2021年第3期摘要推荐 ○ 摘要 |《测绘科学技术学报》2021年第2期摘要推荐 ○ 摘要 |《测绘科学技术学报》2021年第4期摘要推荐 ○ 摘要 |《测绘科学技术学报》2021年第5期摘要推荐 《地球信息科学学报》 ○ 《地球信息科学学报》2021年第10期佳文推介 ○ 《地球信息科学学报》2021年第9期佳文推介 ○ 《地球信息科学学报》2021年第11期佳文推介 ○ 专刊征稿：社会感知与地理大数据挖掘（征稿中） 《测绘工程》 ○ 摘要 |《测绘工程》2021年第5期摘要推荐 ○ 摘要 |《测绘工程》2021年第4期摘要推荐 ○ 摘要 |《测绘工程》2021年第6期摘要推荐 ○ 测绘教学 | 后疫情时代“线上+线下”混合教学模式创新——以测绘类课程视角 《中国空间科学技术》 ○《中国空间科学技术》2021年第6期摘要 ○《中国空间科学技术》2021年第5期摘要推荐 ○ 摘要 |《中国空间科学技术》2021年第3期摘要推荐 ○ 火卫二地形地貌探测综述 《卫星应用》 ○ 综述 | 北斗系统应用趋势分析 《Journal of Geodesy and Geoinformation Science》 ○《测绘学报（英文版）》（JGGS）LiDAR专刊发布 ○《测绘学报（英文版）》（JGGS）第一次编委会会议顺利召开 ○Special Issue on New LiDAR Technologies and Techniques ○ Stefano TEBALDINI et al. |《测绘学报（英文版）》（JGGS）精选论文 《Satellite Navigation》 ○ [综述]| 高扬教授：GNSS智能手机定位：进展、挑战、机遇和未来展望| SANA佳文速递 ○ 熊超教授：地磁暴期间夜间低纬电离层和赤道等离子体不规则体| SANA佳文速递 ○ 徐元博士：面向有色测量噪声下UWB/INS组合行人导航的分布式卡尔曼滤波| SANA佳文速递 ○ 杨飞博士：GNSS天顶对流层精化模型的构建与分析| SANA佳文速递 ○ 牛小骥教授：用半解析法分析GNSS/INS在铁路轨道测量中的相对精度| SANA佳文速递 《自然资源遥感》 ○ 《自然资源遥感》入驻“智绘科服”融媒体平台！ ○ 《自然资源遥感》征稿：“海岸带空间资源及生态健康遥感监测”专栏 ○ 摘要 |《自然资源遥感》2021年第3期摘要推荐 《Journal of Geovisualization and Spatial Analysis》 ○《Journal of Geovisualization and Spatial Analysis》入驻“智绘科服”融媒体平台！ ○ JGSA国际期刊2021年第5卷第2期论文摘要 声明:本文由"麦兜"发布，不代表"知识分享"立场，转载联系作者并注明出处：https://www.wuxiaoyun.com/life/170334.html1.2 轨迹相似度计算
1.2.1 基于最长子序列的轨迹角度相似性度量
1.2.2 基于动态时间规划距离的轨迹距离相似性度量
1.3 距离矩阵计算
1.4 基于密度层次聚类的频繁轨迹识别
2 实例分析
2.1 厦门机场T3候机楼到东渡码头之间轨迹分析
2.2 东渡码头到厦门火车站之间轨迹分析
3 结 论
○ 摘要 |《卫星应用》2021年第9期摘要推荐
○ 摘要 |《卫星应用》2021年第8期摘要推荐
○ 摘要 |《卫星应用》2021年第7期摘要推荐
