第35个教师节晚上6点，“糖果之家”相约星期二，“大数据与智能决策”讨论班（Seminar）如期开启，本次讨论班以“轨迹数据挖掘”为题，研讨轨迹数据的时空特点及轨迹数据挖掘方法，由一名博士生讲解一篇国际期刊文献，共有青年教师、博士后、博士生和硕士生16人参加（一年级的硕士生与博士生去参加学校组织的开学典礼了），以下是研讨内容、文献信息及文献内容简介。

轨迹数据挖掘

图片来源：https://www.microsoft.com/en-us/research/project/trajectory-data-mining/

大数据时代下，随着移动互联网、手持移动设备、卫星导航系统和地理信息系统等的普遍应用以及数据收集效率的不断提高，使人们获得了大量的空间轨迹数据，这些数据代表了移动对象（如人，车辆和动物）的移动性。近年来，轨迹数据挖掘已成为数据挖掘的研究热点，在国内外赢得了广泛关注。同时，轨迹数据挖掘在众多领域得到应用，如交通管理、犯罪分析、疾病监控、环境监测、城市规划、应急管理、公共卫生与医疗健康等。轨迹挖掘作为一个新兴的研究领域，正致力于研发能够用于分析海量、高维的空间轨迹数据挖掘方法和技术，发掘空间轨迹数据中有价值的信息和知识。

轨迹数据具有时空序列性、采样频率差异性、数据质量差等特点。（1）轨迹数据是具有位置、时间信息的采样序列，轨迹点蕴含了对象的时空动态性，时空序列性是轨迹数据最基本的特征。（2）由于活动轨迹的随机性、时间差异较大的特征，轨迹的采样间隔差异显著，例如导航服务是以秒级或者分钟级进行采样，而社交媒体行为轨迹则是以小时或者以天作为间隔的采样。（3）采样频率的差异性增加了轨迹数据分析的难度。由于连续性的运动轨迹被离散化表示，受到采样精度、频率、位置的不确定与预处理方式的影响，导致轨迹数据质量较差，这给基于轨迹数据的分析带来一定的困难。

轨迹数据挖掘任务主要包括：轨迹数据预处理（噪声清洗、分段、停留点检测、压缩、地图匹配）、轨迹数据数据管理（索引与检索）、轨迹模式挖掘（时序模式、周期模式、共同移动模式、伴随模式等）、异常轨迹检测和轨迹分类等。关于轨迹数据挖掘的研究综述可参见文献：Yu Zheng. Trajectory Data Mining: An Overview. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3), Article 29: 1-41.

轨迹分段是轨迹数据预处理中的重要一环，通常可以分为如下三类方法：第一类轨迹分段方法是利用“时间间隔”分段。如果两个轨迹点之间的时间差较大，则进行分段，或者按照时间段将轨迹分段。第二类方法是基于轨迹的形状。基于轨迹点方向的角度变化大小分段，如果变化超过一定的阈值，则分段。也可以采用“线简化”算法，类似轨迹压缩算法，轨迹压缩点为分段点。第三类方法是基于语义信息，基于停留点分段。还有一种是基于出行模式的不同。当汽车行走比较慢的时候，有的路段可能被识别为步行路段，因此要考虑上下文。如果上下文都为行车路段，且中间的步行路段比较小。那么该路段就会被识别为行车路段。

讨论班研讨文献：Song Y, Song T, Kuang R. Path segmentation for movement trajectories with irregular sampling frequency using space-time interpolation and density-based spatial clustering [J]. Transactions in GIS. 2019, 23:558–578.

文章题目是《利用时空插值和基于密度的空间聚类对不规则采样频率的移动轨迹进行路径分割》。文章中的路径分割问题（即轨迹数据预处理中的轨迹分段问题）是指沿着移动轨迹发现停靠点，由Parent et al. (2013)定义。方法中的插值是指通过已知点的数据推求未知点数据。不规则采样频率通常是由原始数据的噪声或者嵌入式信号处理引起的，文章的研究目的是从不规则采样频率的移动轨迹数据中提取停靠点，并基于基础地理信息数据向停靠点添加语义信息。

文章中提出了一种四步法对不规则采样频率的移动轨迹数据进行路径分割，所谓四步法是指（1）数据预处理与参数标定（2）对移动轨迹进行时空插值，这里使用的方法是改进布朗桥模型(Song&Miller, 2014)（3）用基于密度的空间聚类来提取轨迹中的停靠点，这里使用的方法是C-DBSCAN(Gong et al., 2015)。（4）将基础地理信息数据标记在（3）中的停靠点上，从而分析出行者的出行目的。

文章利用明尼苏达州非营利性汽车共享服务组织HOURCAR提供的双子城GPS跟踪数据证明四步法的有效性，并于CB-SMoT模型(Palma et al., 2008)进行对比。实验结果表明，四步法可以检测出停靠点的位置并推断出出行者的活动类型，也可以将临近的停靠点聚成簇。与CB-SMoT相比，四步法可能会将短期停靠也检测出来，但得到的停靠点会更精准、更可靠。

本文所需前序阅读文献：

[1] (插值算法)  Song Y , Miller H J . Simulating visit probability distributions within planar space-time prisms [J]. International Journal of Geographical Information Science, 2014, 28(1):104-125.

[2] (聚类算法) Gong, L., Sato, H., Yamamoto, T., Miwa, T., & Morikawa, T. Identification of activity stop locations in GPS trajectories by density-based clustering method combined with support vector machines [J]. Journal of Modern Transportation, 2015, 23(3):202-213.

[3] (对比算法)  Palma A T , Bogorny V , Kuijpers B , et al. A clustering-based approach for discovering interesting places in trajectories.[C]// ACM Symposium on Applied Computing. DBLP, 2008.