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

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

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

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

基于轨迹相似性的用户LBS双重隐私保护方案

根据LBS的特点,为了有效提高隐私保护算法的执行效率,提出了一种基于轨迹相似性的用户LBS双重隐私保护方案。首先当用户发起LBS请求时,分别在用户起始位置和目标位置处的特定区域内生成k-1个随机位置,再随机生成连接起始位置和目标位置的k-1条假轨迹,计算出所有假轨迹和原始轨迹的相似程度,然后选出其中与原始轨迹相似度最低的假轨迹替代用户发起LBS请求;其次,对LBS位置数据集进行预处理,使用字典查询构建位置事务数据库,使用trie树结构存储所得到的位置数据和频率;最后,在trie树上进行频繁位置选取,并使用差分隐私下的拉普拉斯机制扰动位置频率。结果表明,与已有方法相比,对用户的位置隐私进行了双重保护,降低了隐私泄露风险的同时提高了隐私保护算法运算的效率。所提方案在理论分析和实验结果中,可以在安全,隐私和适用性方面取得改进。

海量地铁乘客轨迹相似性连接方法:以深圳地铁为例

当前主要的轨迹相似性连接方法都以GPS轨迹为研究对象。针对GPS轨迹的优化方法无法直接用于解决地铁乘客轨迹相似性连接的问题,充分利用地铁乘客轨迹的时空特征,借助轨迹的重复性和对称性,将轨迹从点序列转化为OD序列。以OD序列为基础的轨迹,长度是原轨迹的一半,对应的索引空间变小,后续的计算量也随之减少。着重研究了基于PPJoin+的轨迹连接算法在Spark平台上的设计与实现。在一个13结点Spark集群和一个包含500万个乘客轨迹集合(5.6亿条刷卡记录)的超大规模数据集上验证了该算法的有效性。实验结果显示,基于OD序列的PPJoin+算法的执行时间为14.0 min,比默认的点序列轨迹连接算法的节约了62.5%,比Dima连接算法的节约了78.2%,并表现出了良好的可扩展性。

轨迹相似性度量方法研究新进展

轨迹数据广泛应用于智能交通、自然保护、疫情防控等领域。轨迹相似性度量是轨迹查询分析中最复杂和耗时的操作之一,是轨迹数据管理领域的研究基础。文章首先将轨迹相似性度量方法按对时间信息是否敏感划分为时间敏感型和非时间敏感型,同时介绍了基于语义和深度学习的新型轨迹相似性度量方法;然后对每类度量方法进行了综合对比分析,并给出了各自的优缺点;最后对本领域未来的研究趋势进行了展望。

基于位置的社交网络用户轨迹相似性算法

为了提高在位置社交网络中匹配轨迹相似用户的准确性,提出了一种基于自适应密度聚类的用户轨迹相似性双重加权模型。首先,根据签到点的分布,提出基于聚类区域半径的自适应密度聚类算法,对签到点进行聚类,得到符合一定区域半径的自适应分层聚类区域。然后,针对用户相似性的计算,提出用户轨迹相似性双重加权模型:基于不同层次上权重不同及同一层次上不同签到区域权重不同2个原则。基于分层聚类区域,计算用户访问各分层的轨迹相似性;由于不同签到区域对相似度的表征能力不同,通过不同权重来计算具体层次上的相似性。进而,进行层次上的加权,获得用户总体的相似性。仿真表明,该方法能有效地分析出用户轨迹相似性,具备较高的准确性。

基于面积划分的轨迹相似性度量方法

大数据时代背景下,时空轨迹数据应用的场景日益增多且这些数据蕴含着大量的信息,而轨迹的相似性度量作为轨迹挖掘工作的关键步骤起着举足轻重的作用。但传统轨迹相似度量方法有着时间复杂度高、基于轨迹点判断而不够精确的问题。为了解决这些问题,提出了适用于无路网结构轨迹的以轨迹间面积度量为原理的三角分割(TD)方法轨迹相似度量方法。通过建立"指针"选择两轨迹间的轨迹点连线以构建互不重叠的三角形,累加三角形面积并计算轨迹相似度,通过在不同应用场景下设置的阈值来确认轨迹的相似情况。实验结果表明,与传统的基于轨迹点的空间轨迹相似度量方法--最长公共子序列(LCSS)方法和弗雷歇距离度量方法相比,所提方法提升了识别的准确度,且时间复杂度降低了接近90%,能更好地适应轨迹点分布不均匀的轨迹相似度量工作。

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

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

一种新的基于工况区分和轨迹相似性的RUL预测方法

针对运行过程中存在变工况的系统/设备,在相似性框架下提出了一种区分工况的剩余使用寿命(RUL)预测方法。首先,从状态监测数据中提取系统工况数据、初始数据和失效数据,建立针对特定工况的线性回归退化模型。然后,直接利用线性回归模型参数和训练样本运行数据建立系统的退化模式库,避免因采用非线性拟合带来的退化信息衰减,从而最大限度保留系统的退化信息,同时降低算法复杂度。RUL预测阶段,区分测试样本在每个运行周期的工况,分别计算测试样本健康指数,将测试样本运行轨迹与参考样本退化轨迹进行滑动窗口匹配。采用候选集加权方式得到测试样本的RUL。与原始相似性方法相比,基于工况区分和轨迹相似性的剩余使用寿命预测方法在预测准确率和运算效率上有较大提升。

基于改进LCSS的移动用户轨迹相似性查询算法研究

为了解决由于移动用户轨迹数据具有随机性和繁杂性导致算法效率和精度低的问题,首先抽取用户轨迹时间位置序列,然后基于用户的逗留时长采用加权FP树挖掘移动用户的常驻区域以解决用户轨迹的随机性,最后提出结合用户出行的时间和地理因素的LCSS算法衡量用户轨迹相似性。实验证明,该算法具有一定的有效性和扩展性。

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

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

基于距离变换的轨迹群组相似性度量

从海量轨迹中挖掘移动对象的时空运动规律一直广受关注。轨迹数据的聚类、异常检测、多尺度概化等,都是以轨迹数据的相似性度量为基础的。相较于单一轨迹的相似性,轨迹群组的相似性受到尺度、轨迹数据的多维特征等多种因素的影响,缺乏广泛共识的度量方法。面向轨迹群组相似性度量的需求,本文提出了基于距离变换的轨迹骨架线提取方法,以实现轨迹群组的骨架线提取;并利用最长公共子序列算法开展轨迹群组骨架线的相似性度量;最后,基于GeoLife数据集对本文方法进行了验证。结果表明,基于距离变换的方法能够较好地顾及轨迹数据的多种形态特征。这可为轨迹群组相似性度量提供新思路。

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

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

使用轨迹指纹和地点相似性的地点推荐

针对传统的时空轨迹相似性度量算法中存在的计算复杂度高且不适于增量计算的问题,提出了基于相似哈希计算用户时空轨迹相似度的方法,同时使用逆轨迹频率(ITF)度量位置流行度对轨迹相似性的影响,将用户的历史轨迹编码为二进制轨迹指纹,并根据海明距离判断轨迹指纹之间的相似性,使得相似性计算可以在线性时间内完成;此外,改进了地点相似性算法,并将轨迹相似度和地点相似度相结合提出了基于地点和轨迹相似性的地点推荐算法。实验结果表明,本文的推荐方法在准确率、召回率和覆盖率方面能够取得较好的推荐效果,验证了所提方法的有效性。

基于多重运动特征的轨迹相似性度量模型

针对目前只能对单一运动特征(速度、方向等)进行轨迹相似性分析的不足,提出了基于多重运动特征的轨迹相似性度量,该度量对于分析和理解移动对象的运动行为和规律具有重要意义。将其应用于基于多重运动特征的运动序列模式发现。该相似性度量借鉴数据立方体的思想,将多重运动特征时间序列进行量化和符号化表示,在多重运动特征值域空间中计算两字符间的距离作为字符间替换代价,最终以加权编辑距离作为相似性度量。将该相似性度量与谱聚类方法相结合进行运动序列模式发现。实验以飓风数据为例,通过气象文献中飓风的发生与运动规律验证了模型的有效性。

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

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

改进DBSCAN算法在校园轨迹数据相似性的应用

针对如何更准确地分析校园无线网络数据中隐藏的社交关系亲密度,本文提出了改进DBSCAN时空聚类算法.首先,通过采集校园无线网络数据,在根据学生连接WiFi的地点,时间等信息形成时空轨迹.运用改进的算法对时空轨迹聚类.其次,对聚类结果进行特征轨迹提取,运用LCSS算法进行相似性对比,轨迹间相似度越高说明关系比较亲密;相似度越低,可能是较孤僻的学生,老师需要进一步排查和引导教育.最后,运用FinBI对轨迹聚类结果可视化展示.实验结果表明,该算法提高了聚类结果的准确性和有效性,为解决其他相似性问题提供思路.

基于时空切分和词向量相似性的轨迹伴随模式挖掘

设计了一种基于时空Hausdorff距离切分、词向量相似性的轨迹大数据挖掘方法,以准确高效地分析数据中的伴随规律,真实反映人群和车辆的流动行为。基于时序特征的一对三Hausdorff距离算法可以排除反向轨迹、挖掘伴随关系;利用时间滑动窗口切分得到的轨迹段集合可为相似性度量建立数据基础。而基于词向量的轨迹相似性度量方法,建立了轨迹和词句的类比关系,体现了轨迹的空间、时间和方向异质性,能较为准确地度量伴随轨迹在结构上的相似程度,为发现同类目标或检测频繁路径等提供参考依据。

一种基于语义轨迹的相似性连接查询算法

随着移动互联网的快速发展和智能移动设备的广泛普及,携带文本信息的轨迹数据量大量增加,随之而来的轨迹相似性查询研究也在如火如荼地开展。空间轨迹相似性研究是查询轨迹集合中相似轨迹的主要方法,即缩减轨迹数量。由于许多的轨迹都是携带大量文本信息的,而空间轨迹相似性研究考虑的是距离方面,缺少对于文本信息的考虑。针对这一问题,在空间相似性的基础上增加对于文本相似性的考虑,同时将整个空间网格化,通过采用计算空间文本相似性上下限进行范围查询,得到最终的结果,使得轨迹相似性查询更全面,也更具有说服力。

位置服务社交网络用户行为相似性分析

基于位置的社交网络(LBSN)能够支持用户分享地理位置信息,网站中保存用户访问真实世界地理位置的记录构成用户的行为轨迹,但LBSN用户相似性的分析并没有从用户的地理位置轨迹上加以考虑。为此,提出基于划分层次,在不同的邻域半径下密度聚类的方法,探索基于位置的服务(LBS)平台上用户地理位置上相似性的度量。该方法在不同空间位置比例尺下观察用户访问各个聚类区域的次数,进而利用向量空间模型(VSM)计算用户在各个层级的相似性,最终以不同权重叠加各层级的用户相似性值,得出用户在地理空间行为上的相似性。基于国内某大型位置社交网站真实用户数据的实验结果表明,该方法能有效识别出访问地理位置相似的用户。