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

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

基于时间约束的Hausdorff距离的时空轨迹相似度量

从海量的轨迹数据中发现用户的相似轨迹是实现基于位置的个性化服务推荐的关键技术之一.位置和时间是轨迹数据的两个重要属性,而已有的基于Hausdorff距离的轨迹相似度量只着重关注了位置属性.针对在计算轨迹间相似性时忽略了轨迹的时间属性这一问题,提出一种基于时间约束的Hausdorff距离的时空轨迹相似度量.利用滑动窗口挖掘两条较长轨迹中所有相似的子轨迹,进而判断较长轨迹间的相似性.实验结果表明,该时空轨迹相似度量具有更好的效果.     

基于DTW距离度量函数的DTW-TA轨迹匿名算法*

在传统的基于欧几里德距离函数的轨迹相似性计算过程中,要求轨迹等长且时间点对应,无法度量不等长且有局部时间偏移的轨迹相似性。因此在构造同步轨迹集合过程中产生信息损失较大,影响轨迹数据的可用性。为此,本文通过引进一种可以度量不等长且有局部时间偏移的轨迹间相似性的距离度量函数——DTW(Dynamic time warping)距离函数,提出一种新的轨迹匿名模型——（k,δ,p）—匿名模型,构造了DTW-TA(Dynamic time warping trajectory anonymity)匿名算法。在合成数据集和真实数据集下的实验结果表明,该算法在满足轨迹k-匿名隐私保护的基础上,减少了信息损失,提高了轨迹数据的可用性。     

移动对象轨迹时空相似性度量方法

在分析移动对象行为时,移动对象轨迹因包含大量的信息而具有重要的作用。在实际应用中移动对象常受限于空间网络而无法利用现有欧氏空间中轨迹及其距离处理技术。分析了道路网络空间轨迹相似性性质,提出一种移动对象轨迹建模的时空表示方法,能有效地将轨迹从道路网络空间转化到欧氏空间;同时提出了一种基于兴趣点POI（Points Of Interesting）距离的轨迹间相似性测量方法,有效地对轨迹进行化简并减少轨迹中节点的数目,从而降低算法时间复杂度。该方法不仅可以用于搜索相似轨迹,还可方便地应用到轨迹聚类的相关工作中。     

基于大地距离计算相似度的海上目标轨迹预测

目前基于相似度的移动目标轨迹预测算法一般根据数据的时空特性进行分类，无法体现算法自身的特点，为此提出一种基于算法特征的分类方法。轨迹相似度算法通常需要先计算两点之间的距离，再开展后续计算，而常用的欧氏距离（ED）只适用于目标在小区域范围内移动的问题。针对现有基于相似度的轨迹预测算法无法适用于移动范围比较大的海上目标轨迹预测的问题，提出使用大地距离代替ED进行相似度计算。首先，对轨迹数据进行预处理和分段；其次采用离散弗雷歇距离（FD）作为相似性度量；最后，利用模拟数据和实际数据进行测试。实验结果表明，当海上目标移动范围较大时，采用ED算法可能会得到不正确的预测结果，而所提算法可输出正确的目标轨迹预测结果。     

类自动车牌识别轨迹数据的伴随车辆组挖掘

自动车牌识别（ANPR）数据比私人全球定位系统（GPS）数据更易获得,且包含更有用的信息,但是相对成熟的针对GPS轨迹数据挖掘伴随车辆组方法并不适用于自动车牌识别数据,现有的少量自动车牌识别数据伴随车辆组挖掘算法存在重视轨迹相似而忽视时间因素的缺陷,因此提出一种基于轨迹特征的聚类方法挖掘伴随车辆组。针对自动车牌识别数据中采样点固定而采样时间不定的特点,通过轨迹中共现的次数判定两个对象构成伴随模式。该共现定义引入豪斯多夫距离,综合考虑轨迹的地点、方向和时间特征,旨在挖掘数据中采样点不同但采样点距离近且轨迹相似的伴随车辆组,以此提高伴随车辆组挖掘效率。实验结果表明,所提方法较现有方法更能有效挖掘伴随车辆组,识别非伴随模式数据,效率提升了近两倍。     

基于时空金字塔匹配的轨迹相似度算法

轨迹相似性度量是轨迹数据挖掘的基础问题。受设备型号、信号强度和周围环境的影响,轨迹数据具有噪声大、数据量大、采样不均匀等特征,给轨迹相似性度量带来了极大的挑战。因此,提出了基于时空金字塔匹配的轨迹相似度算法,通过在时间和空间维度上对轨迹进行不同粒度的划分,然后利用不同粒度的权重组合来衡量轨迹之间的相似性。该算法能够有效克服轨迹噪声的影响,同时兼顾了轨迹的时间特性和空间特性,并具有较低的计算复杂度。最后,利用真实的信令数据集和人工合成的全球定位系统数据集进行实验,实验结果证明了该算法在准确率和计算复杂度方面都优于目前的主流算法。     

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

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

应用Hausdorff距离的时空轨迹相似性度量方法

相似性度量方法的选取和稳健性对时空轨迹聚类结果的有效性是至关重要的.针对时空轨迹数据复杂的多重维度信息,选取空间维和时间维2个维度度量时空轨迹的相似性,提出一种应用Hausdorff距离的时空轨迹相似性度量方法.首先从时空轨迹的3个特性出发,提出面向相似性度量的时空轨迹重组策略;然后将传统的以点为中心进行相似性度量的思路转换为以轨迹段为中心,提出一个考虑时间同步性的时空轨迹段距离度量公式;最后鉴于传统的Hausdorff距离进行时空轨迹相似性度量具有时空轨迹整体形状特征的优点,针对其容易受时空轨迹局部空间分布影响和忽略时间维信息的缺陷,提出一种基于单位时间平均值Hausdorff距离的时空轨迹相似性度量方法.采用微博签到轨迹数据和出租车GPS轨迹数据进行轨迹时空聚类实验,将文中提出的时空轨迹相似性度量方法与已有的其他方法进行比较,实验结果表明,该方法可以有效地计算时空轨迹的相似性,满足时空轨迹聚类的需求.     

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

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

基于密度核心的出租车载客轨迹聚类算法

目前常见的轨迹聚类大多基于OPTICS、DBSCAN和K-means等算法,但这些聚类方法的时间复杂度随着轨迹数量的增加会大幅上升。针对该问题,提出一种基于密度核心的轨迹聚类算法。通过引入密度核心的概念,设计轨迹密度计算函数以获取聚类簇的致密核心轨迹,同时利用出租车载客轨迹自身的方向和速度等属性提取轨迹特征点,减少轨迹数据量。在此基础上,根据聚类簇中致密核心轨迹与参与聚类轨迹的相似度距离判断轨迹的匹配程度,进而聚合相似轨迹,并将聚类结果储存在聚类节点中。实验结果表明,与TRACLUS和OPTICS聚类算法相比,该算法能够得到更准确的聚类效果,并且时间效率更高。     

基于轨迹图像特征匹配的渔船轨迹相似度计算和轨迹分类

AIS(Automatic Identification System)是一种船舶的自动识别系统,可以提供船舶的时间戳、经纬度、航向角度、速度等数据信息.本文针对船舶航行轨迹多维度的特点以及对船舶轨迹预测的精确度和实时性的需求,提出了一种基于图像检测和匹配的计算轨迹相似度的方法.该方法首先将所有渔船轨迹数据进行可视化,再通过ORB(Oriented FAST and Rotated BRIEF)算法和BF(Brute-Force)匹配来计算轨迹图片相似度用于划分渔船轨迹类型.实验结果显示,通过该计算相似度的方法具有精度高、易实现的特点,与传统计算方法相比,其在处理轨迹数据的效率和速度更具有优越性.     

基于LCS的用户时空行为兴趣相似性计算方法

移动用户的位置轨迹中蕴含着用户的运动规律,行为模式等丰富的信息。重点关注用户轨迹中的停留区域,从轨迹间共同停留区域的时空重叠中挖掘用户行为兴趣的相似性,提出一种基于最长公共子序列的用户时空行为兴趣相似性计算方法。提取轨迹中的停留区域,利用最小包围盒技术描述轨迹中的停留区域,结合最长公共子序列算法提出一种基于最长公共子包围盒长度的用户相似性计算方法。实验收集60个志愿者6周的真实时空轨迹数据来评价该方法,实验结果表明该方法具有较高的准确率。     

划时区分段的动态时间规整算法

轨迹聚类是城市交通数据挖掘的重点之一,交通轨迹聚类算法是按照一定的相似度指标将轨迹划分成若干个类簇。在复杂的路网环境下,针对目前如DTW、SDTW等相似度计算方法准确性不高的问题进行了研究,提出了一种划时区分段的动态时间规整算法（SDTW+）进行相似度计算。该算法充分考虑了轨迹形状因素,能有效提高准确性。实验部分利用不同相似度算法,并结合层次聚类算法对实际车辆轨迹进行聚类,最终以平均轮廓系数和聚类成功率为评价指标,判断不同相似度算法的聚类效果。试验结果表明,采用所提算法相对于采用DTW、SDTW的平均轮廓系数分别提高33.86%,12.94%,同时聚类成功率也得到一定提高。     

基于EKF和数据融合的移动台跟踪定位算法

提出一种利用扩展卡尔曼滤波(EKF)算法实现移动台跟踪定位的改进算法。该算法在已获得移动台初始位置估计的基础上,利用 EKF对移动台的运动轨迹进行多次估计,获取多条跟踪轨迹,剔除偏差较大的轨迹并进行加权平均的数据融合处理,获取一条较优轨迹。再结合距离门限值对较优轨迹的点迹进行匹配管理,实现对较优轨迹的平滑处理,获得最优跟踪轨迹。仿真结果表明,该算法计算复杂度低、鲁棒性强,定位精度明显高于传统EKF跟踪定位算法。     

基于距离负相关性的轨迹相似性度量方法

With the development of wireless communication technology and positioning technology, trajectory data emerge in large quantities. Similarity measurement is used in the query and analysis of trajectory data. In this paper, an improved similarity measure- ment is proposed. By introducing the negative correlation between the distance of points and the similarity into the real sequence ed- iting distance, the robustness to noise is preserved and the sensitivity to difference is improved. We apply different similarity mea- sures to the trajectory privacy protection method based on cluster-reconstruction, and verify the effectiveness of the proposed trajec- tory similarity measure by experiment on the real data and the synthetic data.     

基于时间序列聚类的轨迹停留点检测算法

针对采样不规则轨迹的停留点检测准确性不高的问题,提出了一种基于时间序列聚类的停留点检测算法。首先基于数据场理论设计了一种综合考虑时空特性的混合特征密度测量方法,然后根据停留点中心密度比入口大的特性,采用过滤—精炼策略提取停留点。在过滤阶段,将时间连续且满足最小密度阈值的点作为候选停留点。在精炼阶段,通过最大阈值筛选出实际停留点。实验结果表明,该方法能够有效检测采样不规则轨迹中的停留点,相较于已有方法具有较高的准确性和较低的时间消耗。