基于三维空间面积划分的轨迹相似性度量算法

针对大部分轨迹相似性度量算法无法区分方向相反轨迹的问题,提出了一种基于三维空间面积划分的三维三角分割(3TD)算法。首先,按照3TD算法的时间转换规则将轨迹集的绝对时间序列转变为相对时间序列;然后,在由经度、纬度以及时间三要素构成的三维空间坐标系中,通过划分规则将轨迹间面积分割成若干互不重叠的三角形,累加三角形面积并计算轨迹相似度;最后,在从船舶自动识别系统(AIS)收集的随机采样轨迹数据集上,与最长公共子序列(LCSS)算法和三角分割(TD)算法等进行了对比实验。实验结果表明:3TD算法对实验数据集中异向轨迹识别精确度达到100%;同时该算法面对海量数据集以及轨迹点部分缺失的数据集时,也能维持准确的度量结果以及较高的运算效率,能更好地适应异向轨迹相似度量工作。

基于分组地图匹配的异常轨迹检测

为提高轨迹数据的质量,提出一种轨迹点的多尺度综合映射算法。采用分组匹配的思想,依据每组特性剪枝无效的轨迹点,加快映射轨迹点的连接速度,快速得到路网轨迹。在此基础上,为有效进行异常轨迹的检测,提出一种基于分组地图匹配的异常轨迹检测算法,研究字符串相似性搜索,构建相似轨迹序列寻找代表轨迹,基于交叉点行驶状况对轨迹点进行约减,减少轨迹间的计算量,计算轨迹的异常阈值,判定异常轨迹。在真实的出租车数据集上进行实验,验证了提出方法的执行效率和准确性。

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

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

基于大数据的船舶活动轨迹规律挖掘方法

针对当前船舶轨迹聚类技术存在特征属性研究单一的问题,提出一种基于融合距离的多维度船舶轨迹聚类算法技术,该技术通过加入多个属性特征并采用新的距离度量算法,从时序性和复杂度两方面提出了新的解决思路。在聚类结果基础上,针对缺少轨迹规律特征刻画方法的问题,提出基于局部区域均值的典型轨迹算法技术,通过对各属性进行均值计算,实现同类轨迹集合中轨迹特征的具体描绘。

基于轨迹段DBSCAN的船舶轨迹聚类算法

船舶自动识别系统(Automatic Identification System, AIS)数据中蕴藏着大量的海上交通特征,为挖掘AIS数据中有关船舶运动规律有效的、潜在的信息,提出一种改进型轨迹段DBSCAN(Density-Based Spatitcal Clustering of Applications with Noise)的聚类算法。船位转向角和航速变化量作为信息度量对船舶轨迹进行分段,采用离散Frechet距离作为轨迹相似度度量,利用类似DBSCAN算法对轨迹段进行聚类,得出船舶运动典型轨迹。以天津港为例,采用改进的轨迹段DBSCAN算法对船舶轨迹进行聚类,能从一定程度上提高聚类的效果和准确率,为进一步研究船舶异常行为打下基础。

计算机兵棋作战实体轨迹聚类算法

针对计算机兵棋系统的实际应用,提出计算机兵棋实体轨迹聚类算法——CTECW(clustering trajectories of entities in computer wargames).算法分为3部分:轨迹预处理、轨迹分段聚类以及可视化表现.轨迹预处理将实体原始轨迹转化成实体简化轨迹,再进一步处理成轨迹分段;在DBSCAN算法的基本框架下引入DENCLUE算法中密度函数的概念,并基于提出的相似性度量函数对轨迹分段进行聚类;可视化表现将轨迹分段聚类的结果以赋有军事涵义的形式展现给参与兵棋推演的受训指挥员,体现出算法的实际应用价值.理论分析与实验结果表明,CTECW算法能够得到与TRACLUS算法比较接近的聚类结果,但计算效率却比TRACLUS算法要高,并且聚类结果不依赖于用户参数的仔细选择.

基于改进K-Medoids的组合聚类算法及异常值检测研究

采用聚类算法和异常值检测算法进行车辆轨迹信息的提取与挖掘,在交通控制与管理、道路拥堵时空分析与治理、用户出行线路规划与推荐,以及自动驾驶决策规划等应用中具有重要意义.针对现有聚类算法和异常值检测算法参数难以控制、算法存在随机性的不足,提出基于K-Medoids与DBSCAN组合的聚类算法.通过对模拟十字交叉路口数据集的训练,得到一个交叉路口最佳聚类模型,并用真实轨迹数据集验证、优化该模型.然后,将交叉路口区域内一段时间内的轨迹聚类数据流进行可视化再现,取得了异常轨迹少、聚类速度快的聚类效果,同时比较选择出算法各个参数的最优值.最后,通过参数传递使DBSCAN算法能够更精确地识别出异常轨迹,为交通治理与自动驾驶决策提供指导.

实时视频中的车辆运动轨迹的提取和聚类

利用运动物体轨迹的方向性、运动性和相互关系等典型特征对物体的运动轨迹进行聚类。首先利用改进的加权矢量Hausdorff距离作为度量运动物体轨迹相似度的方法,从而使之适用于空间距离有差别的运动物体轨迹的谱聚类问题;然后基于等周分割(ISO)算法,构造轨迹相似度矩阵,完成轨迹的粗聚类;最后利用轨迹的方向性特征和轨迹类间距对轨迹进行二次聚类,得到最终的轨迹聚类结果。

基于时空模式的轨迹数据聚类算法

针对轨迹聚类算法在相似性度量中多以空间特征为度量标准,缺少对时间特征的度量,提出了一种基于时空模式的轨迹数据聚类算法。该算法以划分再聚类框架为基础,首先利用曲线边缘检测方法提取轨迹特征点;然后根据轨迹特征点对轨迹进行子轨迹段划分;最后根据子轨迹段间时空相似性,采用基于密度的聚类算法进行聚类。实验结果表明,使用所提算法提取的轨迹特征点在保证特征点具有较好简约性的前提下较为准确地描述了轨迹结构,同时基于时空特征的相似性度量因同时兼顾了轨迹的空间与时间特征,得到了更好的聚类结果。

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

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

航空器飞行轨迹相似性度量及聚类分析

基于相似性度量的飞行轨迹聚类能够为航线优化设计、空中交通管理智能化提供技术支持。对飞行轨迹数据进行预处理之后,引入欧氏距离和余弦相似度2种度量,分别构建实际轨迹与理想轨迹、实际轨迹之间的相似性矩阵,利用谱聚类方法对终端区实测飞行轨迹进行聚类,并针对不同相似性度量的特点进行对比分析。结果表明,基于实际轨迹与理想轨迹相似性以及基于混合度量计算实际轨迹间相似性的聚类结果均较为理想,能够有效识别盛行交通流和异常轨迹。

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

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

以运动方向为主导的轨迹相似性度量方法

考虑到移动对象的行为趋势体现在行驶距离与前进方向上,提出以运动方向为主导并兼顾形态距离特征的轨迹相似性度量方法。形态距离特征采用包围面积进行度量,运动方向特征分别采用真实平均方向、线性平均方向、最长公共方向序列3种形式进行度量,选取形态距离和运动方向的最优组合作为轨迹相似性度量的最终形式。北京市出租车GPS载客轨迹数据上的聚类应用结果表明,该相似性度量方法能够有效区分移动对象的趋势方向,且聚类准确率优于最长公共子序列方法。

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

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

基于RFID位置语义的室内移动轨迹聚类算法

面向室内空间的移动轨迹聚类有利于发现室内热点和用户移动模式。针对室内环境在定位技术、距离度量等方面的特殊性,充分考虑室内移动轨迹的空间和语义特征,提出一种基于无线射频识别(radio frequency identification,RFID)位置语义的室内移动轨迹聚类方法。该方法对原始轨迹提取特征点,可简化轨迹以降低算法时间复杂度;从空间形状和位置语义2个方面加权计算轨迹相似度,其中,空间相似度通过定义适用于室内三维空间的距离函数来计算,语义相似度计算基于最长公共子序列思想,并引入移动对象在轨迹点的到达时间和停留时间;利用线性表存储轨迹相似度,采用改进的层次聚类方法对移动轨迹进行聚类。实验结果表明,该方法能够有效地进行室内轨迹聚类并具有较高的效率。

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

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

汽车行驶轨迹数据密度峰值聚类算法研究

随着物联网、V2X和智慧城市等技术的广泛应用,大量的车辆轨迹数据得以记录保留。利用这些轨迹数据可以提取相关信息,例如计算最优路径、检测异常驾驶行为、监测城市交通流量以及预测车辆下一个位置等,轨迹聚类是关键技术之一。密度峰值聚类(density peaks clustering,DPC)作为一种简单有效的基于密度的聚类算法,算法中局部密度的定义未充分考虑数据样本密度分布不均时密度差异的影响,也没有适用于汽车行驶轨迹的相似性度量。此外,算法在遇到相对高维的数据时效果不佳。本文通过引入k近邻思想(k-nearest neighbor,KNN)和主成分分析法(principal component analysis,PCA)并且改进相似性度量,提出了一种适用于汽车行驶轨迹的密度峰值聚类算法。该算法首先使用PCA对高维数据进行预处理;然后采用k近邻思想重新定义局部密度;最后通过重新定义轨迹间的距离函数,摒弃了欧氏距离对分配策略的不良影响。通过对人工合成数据集的实验,证明了算法的可行性;同时算法的有效性也在实际汽车行驶轨迹数据上得到了验证。

基于iBAT和DTW算法的异常轨迹检测

首先使用iBAT算法进行轨迹异常检测,然后结合DTW算法进行相似性度量,进一步区分轨迹。

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

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

基于形态特征的终端区进场中心航迹识别方法

为了挖掘终端区进场航空器交通流的分布特征,量化分析空中交通的复杂性,提出了一种基于多特征航迹相似度和密度峰值聚类(density-peak clustering,DPC)的中心航迹提取方法。首先,采用单向距离(one way distance,OWD)计算航迹之间的形状和物理距离,并结合空管实际运行航迹数据特征,考虑航迹之间的位置属性和航向属性,定义多特征航迹相似度模型。其次,使用密度峰值聚类算法对航迹数据进行聚类分析,提取聚类结果中每一簇中具有最高密度的真实轨迹作为中心航迹。最后,对双流国际机场终端区历史航迹数据进行实验分析,使用轮廓系数指标和基于密度的指标进行评价,并与层次聚类算法进行对比。结果表明,轨迹被划分为8个不同形态的类簇,该方法可以直观有效的识别出轨迹的整体运动特征并精确提取出真实的中心航迹。