带重要点约束的经典轨迹相似度量新算法

在经典轨迹的相似度量问题中提出一个新问题:假设有待相似度量的经典轨迹和实时轨迹,在经典轨迹中存在部分点为重要点,实时轨迹受这些重要点约束。针对此问题,将经典轨迹和实时轨迹作为相似度量的两序列,重要点作为实时轨迹的约束序列,利用带约束的最长公共子序列理论提出带重要点约束的经典轨迹相似度量基础算法和快速算法。实验结果表明,快速算法比基础算法的计算时间减少了36%以上。

基于Hausdorff距离的轨迹相似性度量的航迹复原方法

面对有源和无源探测时存在的大量杂波等干扰,导致探测的重点目标航迹存在缺失的问题,采用基于Hausdorff距离的轨迹相似性度量方法,计算重点目标与探测数据中所有批次在距离-时间、方位-时间2个维度的双重Hausdorff距离。以加权Hausdorff距离为相似性度量排序,从探测数据中辨识出与重点目标航迹相似度最高的目标,实现在探测数据中准确辨识重点目标以及复原目标缺失航迹。实测数据验证表明,该方法简单高效,具有工程应用价值。

经典轨迹的鲁棒相似度量算法

针对经典轨迹与实时轨迹之间的大差异性,该文利用最长公共子序列理论,提出一种鲁棒的轨迹相似度量方法。该方法首先利用点到线段之间的距离判断经典轨迹的点与实时轨迹的线段是否一致;然后利用改进的多对1最长公共子序列算法,计算经典轨迹与实时轨迹之间的最长公共子序列长度;最后将最长公共子序列长度与经典轨迹的点数的比值作为经典轨迹与实时轨迹之间的相似度。实验说明该算法的鲁棒性,该算法能够有效解决经典轨迹与实时轨迹之间的大差异轨迹相似度量问题。

经典轨迹的相似度量快速算法

针对经典轨迹相似度量的耗时性,利用轨迹压缩算法,提出一种基于最长公共子序列(longest common subsequence,LCS)的相似度量快速算法。首先,对实时轨迹进行压缩,减少轨迹点数。然后,利用经典轨迹的点与实时轨迹线段之间的距离,根据改进的多对1 LCS长度公式,计算经典轨迹与实时轨迹之间的LCS长度。最后,将LCS长度与经典轨迹的点数的比值作为经典轨迹的相似度。实验说明,通过轨迹压缩能够减少60%以上的计算时间。

一种融合图结构的时空轨迹相似性查询算法

针对海量时空轨迹数据相似性查询速度慢的问题,提出一种融合图结构的时空轨迹相似性查询算法。从空间维和时间维将轨迹建模为图结构中的一条路径,设计了一种同步匹配空间和时间距离的轨迹相似性度量函数。在此基础上,设计了一种结合时间过滤的基于边的倒排索引结构支持轨迹时空相似性查询,同时利用距离上界的剪枝策略提高查询性能。计算返回的相似轨迹集合中每条轨迹的距离并进行排序,得到相似度最高的前k个轨迹。最后将所提算法与NTrajI算法、SHQ算法、SHQT算法在合成数据集和真实数据集上进行实验对比。结果表明:该算法在索引建立、查询效率和查询质量方面均优于其他对比方法,因此是可行而有效的。

一种移动物体时空轨迹聚类的相似性度量方法

针对利用最小包围盒(MBB)压缩的移动物体时空轨迹,为了能对其进行有效地聚类,提出了一个基于盒内数据点密度的轨迹间相似性度量公式.首先,把两条轨迹的相似性度量转化为两条轨迹上有时间交叠的MBB之间的相似性度量,这在很大程度上减少了数据存储量.其次,分析两条轨迹上有时间交叠的MBB之间影响相似性的因素:时间持续、空间距离和盒内数据点的密度.剖析这3个因素对轨迹相似性的影响作用,提出了利用MBB压缩的移动物体时空轨迹相似性度量公式.实验证明采用本公式对移动物体时空轨迹进行聚类,可以提高聚类结果有效性指标Dunn的值.

时空轨迹相似性度量方法综述

时空轨迹数据是记录移动对象时间和空间的位置序列,它是研究移动对象最为重要的数据来源。时空轨迹数据的分析挖掘是空间数据挖掘的一个研究热点,它包括轨迹检索、轨迹分类、模式挖掘、异常检测等。在分析挖掘过程中,轨迹之间的相似性度量是一个关键问题。本文研究时空轨迹相似性度量方法,首先从理论意义和应用价值的角度分析时空轨迹相似性度量的重要性,然后根据度量方式的不同将时空轨迹相似性度量方法分为两大类:基于轨迹点的相似性度量方法和基于轨迹段的相似性度量方法。由于基于轨迹点的各种相似性度量方法的应用场景和对相似性的定义不同,再将其细分为全局匹配度量法和局部匹配度量法。对时空轨迹相似性度量方法进行分类的同时,也对各个类别中常用的相似性度量方法进行了详细阐述,分析它们的优缺点及应用场合,为时空轨迹分析挖掘提供参考。

农机运行轨迹相似性度量研究

近年来,“智慧农业”发展迅速。要实现作物生产全程智能化、无人化,需要综合应用互联网、大数据、3s、智能机器人等现代信息技术,通过改进、研发、应用新机械、新设备和新技术等一系列措施,实现育秧、插秧、田间管理、收获仓储与耕整地全过程智能化管理。控制设备按照既定轨迹移动是实现作物智能化生产的关键技术,对机械设备实际运行轨迹与设定运行轨迹进行的轨迹相似性度量是评价控制性能的重要指标。轨迹相似性度量是挖掘轨迹数据中设备运行模式的最重要步骤之一,也是轨迹数据管理中最重要的任务之一。分析轨迹数据量具有一定的挑战性,这在很大程度上归结于轨迹数据的时效性和离散性。轨迹相似性度量是用来计算轨迹之间的相似性程度的一类算法,目前文献中记载的算法种类多,但不同的轨迹相似性算法主要侧重解决不同类别的数据问题,且各有优缺点。本文主要对各种轨迹相似性度量方法进行分析比较,包括欧氏距离、动态时间规整、最长公共子序列、编辑距离、豪斯多夫距离、弗雷歇距离、单向距离以及多线位置距离,并对各项算法进行分析比较。

考虑轨迹相似度的综合客运枢纽 出租车合乘方法研究

针对综合客运枢纽出租车停靠点乘客滞留问题,提出一种考虑轨迹相似度的枢纽出租车合乘模型.以车辆数最小与总里程最短为目标,基于包围面积的轨迹相似度指标在形态上约束合乘后车辆的行驶轨迹.设计两阶段算法求解此NP-hard问题,第1阶段利用kmedoids方法对乘客需求聚类,第2阶段设计蚁群算法求解得到乘客匹配方案及合乘行驶路径.实测数据实验证明:该方法能较好优化车辆数和总里程,减少乘客等待时间;轨迹相似性度量约束能有效提高合乘后路径的JAC值,满足乘客希望合乘路径与原始路径差异最小化的心理.

基于有趣地点压缩的时空轨迹聚类

研究移动物体时空轨迹局部关键地点时空相似的聚类问题.根据移动物体的运动状态提取轨迹中的有趣地点,利用最小包围盒技术对这些有趣地点进行描述,得到基于有趣地点压缩的轨迹表示形式;然后给出一个时空属性相结合的相似性度量公式,对压缩表示的轨迹进行相似性度量;基于这个相似性度量公式对轨迹进行聚类,聚类方法采用层次聚类法.实验结果表明,本文提出的方法能有效地对移动物体时空轨迹进行聚类,由于采用了增量式的轨迹压缩方法,不仅提高了聚类的速度,而且还实现了增量式的轨迹聚类.

基于大货车GPS数据的轨迹相似性度量有效性研究

目前,中国货车上全球定位系统(GPS)的强制安装,使得利用包含时间、空间和速度等信息的货车轨迹数据来研究货车运行模式成为可能。基于距离的轨迹相似性度量算法,采用全国道路货运车辆公共监管与服务平台获取的货车GPS轨迹数据,对比分析其在货车轨迹模式识别中的应用。选用文献中最常用的4种基于距离的轨迹相似性度量算法,分别为离散弗雷歇距离(DFD)、动态时间规整(DTW)、最长公共序列(LCS)和实序列编辑距离(EDR)。试验结果表明:当使用二维地理空间轨迹数据(即经度和纬度)时,4种基于距离的轨迹相似性度量算法都能很好地对相似轨迹进行分类(正确率均高于85%),这与现有文献的结论一致。虽然一般认为二维轨迹相似性算法可以直接应用到多维轨迹数据,但是解决具体问题时可能出现的误差以及各种轨迹相似性算法的适用性仍然不确定。目前几乎没有文献对三维及其以上的多维轨迹数据进行实例分析研究,因而,通过相同路线上的三维GPS货车轨迹数据(包括经度,纬度和速度)对4种基于距离的轨迹相似性度量算法进行验证。将第3维速度加入到二维空间轨迹上后发现LCS算法对基于地理空间轨迹的速度模式分类效果优于其他3种基于距离的轨迹相似性度量算法。这说明运用LCS轨迹相似性度量算法来识别基于三维GPS轨迹的货车运行模式是可行的,LCS算法在货车运营管理等方面将有很大的应用潜力。

利用GPS轨迹二次聚类方法进行道路拥堵精细化识别

针对当前在精细识别道路拥堵时空范围方面研究的不足,提出一种利用GPS轨迹的二次聚类方法,通过快速识别大批量在时间、空间上差异较小且速度相近的轨迹段,反映出道路交通状态及时空变化趋势,并根据速度阈值确定拥堵状态及精细时空范围。首先将轨迹按采样间隔划分成若干条子轨迹,针对子轨迹段提出相似队列的概念,并设计了基于密度的空间聚类的相似队列提取方法,通过初次聚类合并相似子轨迹段,再利用改进的欧氏空间相似度度量函数计算相似队列间的时空距离,最后以相似队列为基本单元,基于模糊C均值聚类的方法进行二次聚类,根据聚类的结果进行交通流状态的识别和划分。以广州市主干路真实出租车GPS轨迹数据为例,对该方法进行验证。实验结果表明,该二次聚类方法能够较为精细地反映城市道路的拥堵时空范围,便于管理者精准疏散城市道路拥堵,相比直接聚类方法可以有效提升大批量轨迹数据的计算效率。

基于DBI和稀疏轨迹数据的交通状态精细划分与识别

浮动车轨迹数据已逐渐成为城市交通状态识别的主要数据源之一,但是现有基于浮动车轨迹数据的交通状态识别中多数是应用高精度或是多源轨迹数据。针对稀疏轨迹数据在城市交通状态识别中存在识别精度不高的问题,本文提出一种结合戴维森堡丁指数(DBI)和轨迹相似性度量的动态交通状态划分方法。首先,对轨迹数据和路网数据进行预处理并且建立不同时间片的路段轨迹集合;接着,依据轨迹速度-空间相似性,利用戴维森堡丁指数动态地扩展轨迹的空间维度,并根据轨迹相似性度量方法构建最佳车辆队列;然后,将前后不同的车辆队列进行二次处理,连接组成交通流簇;最后,基于模糊C均值聚类方法将交通流进行划分,实现路段交通状态的识别。采用厦门市厦禾路、湖滨西路和湖滨南路交叉路段上的真实出租车轨迹数据进行测试,结果表明,本文所提方法保证了车辆队列速度分布与原始轨迹速度分布基本一致,相比对比方法Kmeans++和ST-DBSCAN,本文方法均方根误差平均下降了18.77%和21.22%,并且在不同的实验路段表现更加稳定,可有效、可靠地运用稀疏轨迹数据识别城市交通状态,进而实现城市交通状态的精细分析。