轨迹数据挖掘：概述

《轨迹数据挖掘：概述》由会员分享，可在线阅读，更多相关《轨迹数据挖掘：概述（35页珍藏版）》请在金锄头文库上搜索。

1、轨迹数据挖掘：概述 Trajectory Data Mining: An Overview 位置采集和移动计算技术的进步已经产生了大量的空间轨迹数据， 这些数据代表了移动物体 （如人，车辆和动物）的移动性。在过去十年中，已经提出了许多技术来处理，管理和挖掘 轨迹数据，促进了广泛的应用。在本文中，我们对轨迹数据挖掘的主要研究进行了系统的调 研，提供了该领域的全景及其研究课题的范围。根据轨迹数据的推导，轨迹数据预处理，轨 迹数据管理以及各种挖掘任务（如轨迹模式挖掘，异常值检测和轨迹分类）的路线图，调研 探讨了连接，相关性，以及这些现有技术之间的差异。这项调研还介绍了将轨迹转换为其他 数据格式（如图

2、，矩阵和张量）的方法，可以应用更多的数据挖掘和机器学习技术。最后， 提出了一些公共轨迹数据集。 这项调研可以帮助塑造轨迹数据挖掘领域， 从而快速了解这一 领域对社区的影响。 类别和主题描述符： H.2.8 数据库管理： 数据库应用 - 数据挖掘， 空间数据库和 GIS; I.2.6 人 工智能：学习 - 知识获取 一般术语：算法，测量，实验 附加关键词和短语：时空数据挖掘，轨迹数据挖掘，轨迹压缩，轨迹索引和检索，轨迹模式 挖掘，轨迹异常值检测，轨迹不确定性，轨迹分类，城市计算 1.引言 空间轨迹是由地理空间中的运动物体产生的轨迹，通常由一系列时间顺序的点表示，例如p1 p2 pn，其中每个点包

3、括地理空间坐标集和时间戳，如p = (x, y, t)。 位置采集技术的进步产生了无数的空间轨迹，代表了各种移动物体（如人，车辆和动物）的 移动性。 这些轨迹为我们提供了前所未有的信息来了解移动物体和位置， 促进了基于位置的 社交网络Zheng 2011，智能交通系统和城市计算领域的广泛应用Zheng et al. 2014b。这些 应用的流行又要求系统地研究新的计算技术，以从轨迹数据中发现知识。在这种情况下，轨 迹数据挖掘已经成为越来越重要的研究课题， 引起了计算机科学， 社会学和地理学等众多领 域的关注。 在轨迹数据挖掘领域进行了深入和广泛的个人研究。然而，我们缺乏系统的评估，可以很好 地

4、塑造现有的研究领域和定位。面对大量出版物，社区对这些现有技术的联系，相关性和差 异性仍不甚清楚。 为此， 我们根据图 1 所示的范例进行了全面探索轨迹数据挖掘领域的综合 描述： 第一，在第 2 节中，我们将生成轨迹的数据源分为四组，列出了每个组中轨迹数据可以启用 的几个关键应用。 第二， 在使用轨迹数据之前， 我们需要处理诸如噪声过滤， 轨迹分割和地图匹配等诸多问题。 这个阶段称为轨迹预处理， 这是许多轨迹数据挖掘任务的基本步骤。 噪声滤波的目标是从轨 迹中去除可能由位置定位系统的差信号（例如，在城市峡谷中行驶时）引起的一些噪声点。 轨迹压缩是为了压缩轨迹的大小（为了减少通信，处理和数据存储中

5、的开销） ，同时保持轨 迹的效用。 停留点检测算法识别移动物体在一定距离阈值内停留一段时间的位置。 停留点可 以代表用户已经去过的餐厅或商场， 比轨迹中的其他点具有更多的语义含义。 轨迹分割通过 时间间隔，空间形状或语义含义将轨迹划分成片段，用于进一步的过程，如聚类和分类。地 图匹配旨在将轨迹的每个点投射到真正产生点的相应路段上。 我们详细介绍第 3 节中的轨迹 预处理。 第三，许多在线应用程序需要即时挖掘轨迹数据（例如，检测交通异常） ，呼吁有效的数据 管理算法可以从大轨迹语料库快速检索满足某些标准（例如时空约束）的特定轨迹。通常有 两种主要类型的查询：最近邻the nearest neig

6、hbors和范围查询range queries。前者还与距 离度量相关联，例如两个轨迹之间的距离。另外，对于两种类型（历史和最近）的轨迹，需 要不同的管理方法。我们将在第 4 节介绍轨迹索引和检索。 第四，根据前两个步骤，我们可以进行挖掘任务，如轨迹模式挖掘，轨迹不确定性，异常值 检测和分类。 - 轨迹不确定性：物体连续移动，而其位置只能在离散时间进行更新，从而使运动物体在 两个更新之间的位置不确定。 为了增强轨迹的实用性， 一系列研究试图建模和减少轨迹的不 确定性。另一方面，一个研究的分支旨在用户公开她的轨迹时保护用户的隐私。我们在第 5 节回顾轨迹的不确定性。 - 轨迹模式挖掘：大量的空间

7、轨迹提供了分析移动对象的移动模式的机会，这可以通过包 含某种模式的个体轨迹或一组共享相似模式的轨迹来表示。 在第 6 节中， 我们调研了四种模 式策略：伴行模式，轨迹聚类，周期模式和频繁序列模式。 - 轨迹分类：使用受监督的学习方法，我们可以将轨迹或分段轨迹划分为某些类别，可以是行走（如远足和餐饮）或不同的运输模式，如步行和驾驶。我们在第 7 节中给出了轨迹分 类的例子。 - 轨迹异常检测：与轨迹数据中经常发生的轨迹模式不同，轨迹异常值可以是与某些相似 度量方面与其他项显着不同的项（轨迹或轨迹段） ，也可以是不符合预期模式的事件或观察 （由轨迹集合表示） （例如由车祸引起的交通拥堵） 。第 8

8、 节介绍轨迹数据的异常检测。 最后，除了研究原始形式的轨迹之外，我们还可以将轨迹转换为其他格式，如图，矩阵和张 量（见图 1 右侧） 。轨迹的新表征利用现有的挖掘技术（例如，图挖掘，协同过滤（CF） ，矩 阵因式分解（MF）和张量分解（TD） ） ，扩展和多样化了轨迹数据挖掘的方法。在第 9 节中， 我们给出转换的代表性例子。 这篇文章的贡献有四个方面。首先，本文介绍了轨迹数据挖掘的框架，为该领域定义了范围 和路线图。该框架提供了人们可以快速了解并进入该领域的全景图。第二，个人研究工作在 这个框架的每一层都有良好的定位， 分类和连接。 专业人员可以轻松找到解决问题所需的方 法，或找到未解决的问

9、题。第三，本文提出了将轨迹转移到其他格式的愿景，可以应用多种 现有的挖掘技术。这扩大了轨迹数据挖掘的原始范围，推进了该领域的方法和应用。第四， 我们收集人们可以获得各种公共轨迹数据集进行研究的来源列表。 我们还介绍了关于轨迹数 据研究的会议和期刊。 2.轨迹数据 在本节中， 我们将生成轨迹的数据源分为四个主要类别， 简要介绍了每个类别中的几个应用 场景。 代表人类流动性的轨迹数据可以帮助建立更好的社交网络Bao et al. 2015; Zheng 2011; Zheng et al. 2012b和旅游推荐Zheng and Xie 2011b; Zheng et al. 2011c; Zhe

10、ng et al. 2009b。 （1）人员流动：长期以来，人们以空间轨迹的形式，被动地，积极地记录着现实世界的运 动。 活动记录：旅行者使用 GPS 轨迹记录他们的旅行路线，以记住旅程并与朋友分享经验。自 行车和慢跑者记录运动分析的踪迹。 在 Flickr中， 一系列地理标记的照片可以制定空间轨迹， 因为每张照片都有一个位置标签和一个对应于照片拍摄地点和时间的时间戳。 类似地， 在基 于位置的社交网络中的用户的“签入”可以被视为轨迹，按时间顺序排列。 无线记录：携带移动电话的用户无意中产生由具有相应转换时间的小区塔 ID 序列表示的许 多空间轨迹。此外，信用卡的交易记录还指示持卡人的空间轨迹

11、，因为每个交易包含表示交 易发生的位置的时间戳和商家 ID。 （2）运输车辆的流动性：我们日常生活中出现了大量配备 GPS 的车辆（如出租车，公共汽 车，船只和飞机） 。例如，主要城市的许多出租车都配备了 GPS 传感器，可以以一定的频率 报告带时间戳的位置。这样的报告制定了大量可用于资源分配的空间轨迹Yuan et al. 2011b, 2013b，流量分析Wang et al. 2014; Yuan et al. 2013a，改善交通网络Zheng et al. 2011a。 （3）动物流动：生物学家一直在收集动物像老虎和鸟类的移动轨迹，目的是研究动物的迁 徙痕迹，行为和生活情况Lee e

12、t al. 2007; Li et al. 2010c。 （4）自然现象的流动：气象学家，环保人士，气候学家和海洋学家正在忙于收集一些自然 现象的轨迹，如飓风，龙卷风和洋流。这些轨迹捕捉到环境和气候的变化，帮助科学家处理 自然灾害，保护我们生活的自然环境。 3.轨迹数据预处理 本节介绍了在开始挖掘任务之前处理轨迹所需的四项基本技术， 包括噪声滤波， 停留点检测， 轨迹压缩和轨迹分割。 3.1 噪声滤波 由于传感器噪声和其他因素， 如在城市峡谷中收到较差的定位信号， 空间轨迹永远不会完全 准确。 有时，错误是可接受的（例如，车辆的几个 GPS 点落在实际驾驶车辆的道路之外） ， 这可以通过地图匹

13、配算法来修复（在 3.5 节中介绍） 。在其他情况下，如图 2 所示，像 p5 这 样的噪声点的误差太大 （例如距离其真实位置几百米） ， 以得出诸如行进速度等有用的信息。 因此，在开始采矿任务之前，我们需要从轨迹中滤除这些噪点。虽然这个问题还没有完全解 决，但现有的方法分为三大类。 均值（或中值）滤波器均值（或中值）滤波器Mean (or Median) Filter：对于测量点zi， （未知）真实值的估计是zi 及其 n-1 个前驱在时间上的平均值（或中值） 。均值（中值）滤波器可以被认为是覆盖时间 上相邻zi值的 Sliding Window。在图 2 所示的例子中，如果我们使用 Sli

14、ding Window 大小为5 的均值滤波器，则。处理极端误差时，中值滤波器比均值滤波器鲁 棒性强。均值（中值）滤波器适用于处理具有密集表示的轨迹中的各个噪声点，如 p5。然 而，当处理多个连续的噪声点时，例如 p10，p11 和 p12，需要较大尺寸的 Sliding Window。 这导致计算的均值（或中值）和点的真实位置之间的误差更大。当轨迹的采样率非常低（即 两个连续点之间的距离可能长于几百米）时，均值和中值滤波器不再是很好的选择。 Kalman 和粒子滤波器和粒子滤波器Kalman and Particle Filters：从 Kalman 滤波器估计的轨迹是测量和运 动模型之间的

15、折衷。 除了给出符合物理学规律的估计之外，Kalman 滤波器还给出了诸如速 度等高阶运动状态的原理估计。虽然 Kalman 滤波器通过假设线性模型和 Guass 噪声来获得 效率，但是粒子滤波器放宽了这些假设，以获得更一般但效率较低的算法。Lee 和 Krumm 2011可以找到使用 Kalman 和粒子滤波器修复噪声轨迹点的类似教程的介绍。 粒子滤波的初始化步骤是从初始分布生成 P 粒子，j =1, 2, . . . , P。例如，这些粒子将具有 零速度并且在 Guass 分布的初始位置测量周围聚集。第二步是“重要性抽样” ，它使用动态 模型P(xi|xi-1)概率地模拟粒子在一个时间步长

16、上的变化。 第三步使用测量模型计 算所有粒子的“重要性权重” 。更重要的权重对应于更好地被测量支持的粒子。然后重要的权重被归一化，所以它们相加到一个。当从与归一化重要性权重成正比的中选择一组 新的 P 粒子时，循环中的最后一步是“选择步骤” 。最后，我们可以通过来 计算权重和。 Kalman 和粒子滤波器模拟测量噪声和轨迹的动力学。然而，它们取决于初始位置的测量。 如果轨迹中的第一点嘈杂，则两个滤镜的有效性会显着下降。 基于启发式的异常检测基于启发式的异常检测Heuristics-Based Outlier Detection： 虽然先前提到的滤波器在轨迹中 用估计值替代噪声测量，但是第三类方法通过使用异常值检测算法从轨迹直接去除噪声点。噪声滤波方法已被用于 T-Drive Yuan et al. 2010a， 2011a， 2013a和 GeoLife Zheng et al. 2009a 的; Zheng et al.2010项目，首先