其他
2020年初,一场突如其来的新冠疫情,使得公共卫生安全问题受到了全社会的广泛关注。与此同时,如何及时掌握人与人之间的病毒传播路径,及时发现确诊人员的密切接触者,成为了各地政府疫情防控最迫切的需求。JUST基于大规模轨迹数据,针对易感人群难以发现的问题,开发并提供了关联人群查询功能,通过对轨迹进行匹配挖掘,能够快速找出与确诊人员行动轨迹在时空维度有过“接触”的人群。其中,实现该功能的很重要的一项工作就是:如何衡量两条轨迹的相似性。下文将简要介绍一些常见的轨迹相似性度量方法。轨迹作为一种时空数据[1],指的是某物体在空间中的移动路径,通常表示为GPS点的序列,例如tr=,其中点pi=(lat,lng,t),表示该物体在t时刻位于地理坐标位置(lat,lng)上,lat和lng分别表示纬度和经度。图1:离散的GPS点序列组成轨迹大数据时代,随着车载导航系统的普及,海量的轨迹数据正在源源不断的产生,这些轨迹中蕴含着巨大的价值[2],例如可以进行交通流量分析和预测,为政府的城市规划提供建议;也可以进行轨迹聚类,发现那些被很多轨迹经过的道路,用于指导自行车道的规划;还可以进行驻留点检测,发现轨迹经常停留的区域等。图2:海量的轨迹数据(北京出租车轨迹)及其应用轨迹数据的分析处理非常具有挑战性,主要包含三个方面:1)轨迹数据量大;2)轨迹数据噪音多;3)轨迹数据获取途径多样。其中,轨迹相似性作为一项基础算法服务,衡量两条轨迹之间的距离大小,可为其上层应用提供支持,也是目前研究的热点之一。图3:轨迹相似性查询示意图相对于点与点或点与轨迹之间的距离度量,轨迹之间的距离度量更加的复杂,需要考虑的因素也更多,例如轨迹的采样率、考虑轨迹的时间信息和轨迹自身的噪音等。常见的轨迹相似性度量方法大致分类如下图所示。图4:轨迹相似性方法分类我们定义如下两条轨迹,长度分别为n和m,则:欧式距离(Euclidean