时空轨迹数据挖掘研究

来源：二三娱乐

摘要 ................................................................................................................. i ABSTRACT ......................................................................................................... ii 第一章绪论 ...................................................................................................... 1

1.1 研究背景及意义 ............................................................................................... 1 1.2 国内外研究现状 ............................................................................................... 3

1.2.1 轨迹数据挖掘研究现状 ........................................................................ 3 1.2.2 空间聚类算法研究现状 ........................................................................ 5 1.2.4 研究现状分析 ........................................................................................ 5 1.3 本文的主要研究内容和创新点 ....................................................................... 6

1.3.1 本文的主要研究内容 ............................................................................ 6 1.3.2 本文创新点 ............................................................................................ 7 1.4 本文的组织结构 ............................................................................................... 7 第二章相关概念与技术 .................................................................................... 9

2.1 空间聚类相关算法 ......................................................................................... 9

2.1.1 基于划分的聚类算法 ............................................................................ 9 2.1.2 基于密度的聚类算法 .......................................................................... 10 2.1.3 基于网格的聚类算法 .......................................................................... 11 2.1.4 层次聚类算法 ...................................................................................... 12 2.2 时空轨迹相关概念与技术 ........................................................................... 13

2.2.1 轨迹数据的概念和表示类型 .............................................................. 13 2.2.2 时空轨迹数据挖掘流程 ...................................................................... 13 2.2.3 轨迹数据预处理 .................................................................................. 15 2.2.4 常见时空数据挖掘任务 ...................................................................... 17 2.3 本章小结 ......................................................................................................... 19 第三章基于网格的密度峰值空间聚类 ............................................................ 20

3.1 问题描述 ......................................................................................................... 20 3.2 密度峰值聚类算法 ......................................................................................... 20 3.3 基于网格的密度峰值空间聚类算法 ............................................................. 21

3.3.1 网格空间的密度与距离计算 .............................................................. 22 3.3.2 确定聚类中心 ...................................................................................... 23

第 I 页

3.3.3聚类算法与性能 ................................................................................... 25 3.4 实验分析 ......................................................................................................... 26

3.4.1 聚类结果 .............................................................................................. 26 3.4.1 仿真结果验证 ...................................................................................... 26 3.4.2 参数敏感性分析 .................................................................................. 29 3.4.3 运行效率分析 ...................................................................................... 31 3.5 本章小结 ......................................................................................................... 32 第四章时空轨迹向量化方法 ........................................................................... 33

4.1 问题背景与问题描述 ................................................................................... 33 4.2 时空轨迹转换为区域序列 ............................................................................. 36

1.2.1 停留点检测 ........................................................................................ 36 4.2.2 热点区域发现 ...................................................................................... 36 4.2.3区域序列匹配 ....................................................................................... 37 4.3 时空轨迹转换为动作序列 ............................................................................. 38

4.3.1 轨迹动作 .............................................................................................. 38 4.3.2 轨迹动作距离度量 .............................................................................. 40 4.3.3 轨迹转换为动作序列 .......................................................................... 41 4.4 轨迹序列嵌入 ................................................................................................. 43

4.4.1 连续词袋模型 ...................................................................................... 43 4.4.2 跳字模型 .............................................................................................. 45 4.4.3 层序softmax ........................................................................................ 46 4.4.4 负采样 .................................................................................................. 47 4.5 实验分析 ......................................................................................................... 48

4.5.1 数据集 .................................................................................................. 48 4.5.2 热点区域提取实验 .............................................................................. 49 4.5.3 轨迹动作提取实验 .............................................................................. 50 4.5.4 轨迹嵌入效率分析 .............................................................................. 51 4.6 本章小结 ......................................................................................................... 51 第五章基于轨迹向量的轨迹分析实验 ............................................................ 52

5.1 数据集及预处理 ............................................................................................. 52 5.2 基于轨迹区域向量的聚类实验 ..................................................................... 54 5.3 基于轨迹动作向量船只目标分类实验 ......................................................... 56

5.3.1 基于三层卷积网络的船只目标分类 .................................................. 56

第 II 页

5.3.2 实验结果分析 ...................................................................................... 57 5.4 本章小结 ......................................................................................................... 58 第六章总结与展望 ......................................................................................... 59

6.1 本文主要研究成果 ......................................................................................... 59 6.2 未来工作展望 ................................................................................................. 59 致谢 .............................................................................................................. 61 参考文献 ........................................................................................................... 62 作者在学期间取得的学术成果 ........................................................................... 67 作者在学期间取得的竞赛奖项 ........................................................................... 67

第 III 页

表目录

表 3.1 DPC与DPSCGNS算法的聚类准确率比较 ................................................... 27 表 4.1 轨迹动作提取 ................................................................................................... 50 表 4.2 不同参数下轨迹动作聚类的DBI ................................................................... 51 表 4.3 轨迹动作嵌入的效率分析 ............................................................................... 51 表 5.1 AIS数据集主要字段 ......................................................................................... 52

第 IV 页

图目录

图 1.1 船舶轨迹与地形示意图 ..................................................................................... 3 图 1.2 船舶轨迹的实际行为语义示意图 ..................................................................... 3 图2.1 K-means聚类基于对元素进行划分 .................................................................. 10 图 2.2 密度相关定义示意图 ....................................................................................... 10 图 2.3 STING算法的逐层网格结构 ........................................................................... 12 图 2.4 时空轨迹挖掘流程架构 ................................................................................... 14 图 2.5 轨迹MBR距离 ................................................................................................ 17 图 3.1 聚类中心和𝜌与𝛿的关系................................................................................... 24 图 3.2 𝛾以及其一阶差分与𝐺的关系曲线 .................................................................. 24 图 3.3 形状数据集 ....................................................................................................... 27 图3.4 DPSCGNS算法对形状数据集的聚类结果 ...................................................... 28 图 3.5 DPSCGNS在形状数据集上的聚类中心决策图 ............................................. 29 图3.6 高斯数据集在不同side 大小下的聚类结果 ................................................... 30 图 3.7 多种聚类算法的运行时间对比 ....................................................................... 31 图 4.1 轨迹频繁模式挖掘结果 ................................................................................... 33 图 4.2 基于用户位置的时空规律发现应用 ............................................................... 34 图4.3 轨迹向量化方法与文本处理方法对比 ............................................................ 35 图 4.4 轨迹转向点与夹角 ........................................................................................... 39 图 4.5 轨迹动作的错误划分 ....................................................................................... 41 图 4.6 CBOW模型结构 ............................................................................................... 44 图 4.7 Skip-Gram模型结构 ......................................................................................... 46 图 4.8 哈夫曼树结构示意图 ....................................................................................... 47 图 4.9 动物数据集轨迹点热力图分布 ....................................................................... 48 图4.10 动物数据集热点区域提取结果 ...................................................................... 49 图 4.11 基于道路信息的实验结果对比 ..................................................................... 49 图 5.1 丹麦水域AIS数据集 ....................................................................................... 52 图 5.2 轨迹的间隔时间与间隔距离分布 ................................................................... 53 图5.3 轨迹（部分）的异常与缺失 ............................................................................ 53 图 5.4 预处理后的轨迹（部分） ............................................................................... 54 图 5.5 停留点提取结果 ............................................................................................... 54 图5.6 轨迹热点区域提取结果 .................................................................................... 55

第 V 页

图5.7 轨迹区域向量聚类结果（K=20） ................................................................... 55 图5.8 丹麦主要港口位置 ............................................................................................ 56 图 5.9 TextCNN分类网络 ........................................................................................... 57 图 5.10 轨迹速度的时间累积分布 ............................................................................. 57 图 5.11 轨迹目标分类训练损失变化 ......................................................................... 58

第 VI 页

摘要

移动通信技术发展带动各行各业产生了海量的时空轨迹数据，也催生了大量对时空轨迹的数据挖掘研究，但目前对轨迹的挖掘研究多聚集于道路交通等领域，对开放空间轨迹的研究较少。本文以提取开放空间中目标运动轨迹下所蕴含的语义信息为动机，针对开放空间轨迹标注信息少、数据量大、不确定性高的特点，设计了轨迹向量化方法，将开放空间中的轨迹坐标转化为包含语义信息的轨迹向量，以完成其他轨迹挖掘任务。

本文首先针对基于密度的聚类算法时间复杂度较高的问题，对DPC算法进行了基于网格的改进，提出DPSCGNS算法，可以有效地提取任意形状的聚类，并且对参数具有鲁棒性，比其他基于密度的算法时间复杂度更低。其次提出轨迹动作的概念，设计了基于热点区域的轨迹区域序列化方法和基于轨迹动作的动作序列化方法，利用得到可以进行向量化分析的标注序列。使用一个简化的神经网络模型，词向量模型Word2vec对离散化的轨迹序列进行向量化分析，得到包含语义信息的轨迹向量。最后使用AIS船舶数据集设计轨迹向量聚类分析实验和轨迹目标分类实验，验证了使用轨迹向量进行轨迹数据挖掘任务的可行性，证明轨迹向量方法是有效的。

主题词：时空数据、空间聚类算法、轨迹向量化

第 i 页

ABSTRACT

The development of mobile communication technology has led to a large number of spatio-temporal trajectory data generated by various industries. It has also spawned a large number of data mining studies on spatio-temporal trajectories. However, the research on trajectory mining is mostly concentrated in the fields of road traffic and so on. less. In order to extract the semantic information contained in the target motion trajectory in open space, this paper designs the trajectory vectorization method for the open space trajectory with less information, large data volume and high uncertainty. The coordinates are transformed into trajectory vectors containing semantic information to accomplish other trajectory mining tasks.

In this paper, firstly, based on the high time complexity of density-based clustering algorithm, the grid-based improvement of DPC algorithm is proposed. The DPSCGNS algorithm is proposed, which can effectively extract clusters of arbitrary shapes and is robust to parameters. Time complexity is lower than other density-based algorithms. Secondly, the concept of trajectory action is proposed. The trajectory region serialization method based on hotspot region and the action serialization method based on trajectory action are designed. The annotation sequence that can be vectorized is obtained. Using a simplified neural network model, the Word2vec to embed discretized trajectory sequence to obtain a trajectory vector containing semantic information. Finally, using AIS ship dataset to design trajectory embedding clustering analysis experiment and trajectory target classification experiment, the feasibility of using trajectory vector for trajectory data mining task is verified, and the trajectory embedding method is proved to be effective.

Key Words：Spatial-Temporal Data, Spatial Clustering, Trajectory embedding

第 ii 页

第一章绪论

1.1 研究背景及意义

人类早已进入信息时代，无论何种行业，都伴随着海量数据点的生成。能够充分利用数据的行业或组织（如广告、电商、金融），则在信息化的大潮中崛起，突显了利用数据进行规律挖掘的重要性[1]。在1989年，学术界首次提出了“知识发现”的概念[2]。知识发现是利用数据进行发现数据背后蕴含的规律，并将规律总结为知识提供给决策者。随后便诞生了数据挖掘的专门学科[3]。由于数据挖掘技术的快速进步，各行各业产生了许多革新，也为基础设施与社会服务带来了便利[4]。

全球定位系统（Global Positioning System，GPS）和移动设备的普及已经引来了移动计算系统的流行，随之而来产生了数量庞大的空间轨迹，代表各种移动物体在室内和室外环境中的移动，例如人、车辆、动物和自然现象[5]。下面是一些例子。

1. 人的流动性：人们在很长一段时间内都在以空间轨迹的形式记录他们真实世界的运动。

主动记录：旅行者用GPS轨迹记录他们的旅行路线，目的是记录旅行并与朋友分享经验。自行车运动员和慢跑者记录他们的运动轨迹。在Flickr软件中，一系列地理标记的照片可以形成一个空间轨迹，因为每张照片都有一个位置标签和一个时间戳，对应于照片拍摄的地点和时间。同样地，在社交平台Square中，用户的“签到”可以被看作是一个轨迹，按时间顺序排序。

被动记录：一个携带手机的用户无意中产生了许多空间轨迹，这些轨迹是由信号基站的id和基站响应的时间戳所表示的。与此同时，信用卡的交易记录也表明持卡人的空间轨迹，因为每个交易都包含一个时间戳和一个表示交易设备位置的商家ID（Identity）。

2. 车辆的机动性：近年来，我们的日常生活中出现了大量配备GPS的车辆。例如，许多主要城市的出租车都配备了GPS传感器，这使他们能够以一定的频率向数据中心报告一个时间戳的位置。这些报告形成了大量的空间轨迹，可用于资源分配、安全管理和流量分析。

3. 动物的移动和自然现象：生物学家们为研究项目寻找动物的移动轨迹。类似地，气候学家们正忙着收集一些自然现象的轨迹，比如飓风、龙卷风和洋流。这些轨迹为科学家提供了关于他们正在研究的物体的丰富信息。

这些轨迹信息催生了对轨迹数据进行挖掘的研究，产生血多种类的轨迹数据挖掘任务，例如轨迹周期规律挖掘、轨迹序列模式挖掘、轨迹异常检测、轨迹聚类、轨迹预测等。

第 1 页

时空轨迹数据挖掘方兴未艾，在短短的几十年间，诞生了大量的研究内容，涉及行业领域十分广泛，并且不断涌现出新的热点[6]。然而，仅强调研究所取得的成果是片面的。需要认清的是，对时空轨迹数据挖掘的研究多关注于轨迹的表层的信息，未能深入挖掘轨迹内涵。此外在应用方面，仍存在覆盖行业面较窄，应用类型单一等不足[7][8][9][10]。

随着Web 2.0与位置采集和无线通信技术的快速发展,近年来出现了越来越多的基于位置的社交网络(Location-based Social Network，LBSN)，,如Foursquare, Facebook, Gowalla和Loopt等。用户可以根据兴趣点(Point-of-Interests，POI), 例如商店、餐厅、旅游景点, 通过移动设备方便地分享日常生活中的精彩经历。利用用户签到数据，实时进行个性化推荐，帮助用户了解新的兴趣点，探索新的区域(如城市)，从而方便广告商向目标用户投放移动广告。与传统桌面推荐系统提供“数字”信息(如电影推荐、音乐推荐等)不同的是，基于位置的推荐系统通常涉及移动用户和地理实体(如观光景点)，它们面临着更多的挑战，主要有以下几点。

1. 数据稀疏。要了解和评价一个兴趣点，用户必须亲自访问该兴趣点，因此成本比在线评价电影更昂贵。即使用户经常访问兴趣点，出于隐私或安全考虑，他通常也不会进行数字账号登录。因此，用户在社交网络中生成的签到数据比他们为电影和音乐生成的评级数据要少得多。这个问题困扰着大多数现有的协同过滤推荐系统。

2. 背景信息。基于位置的推荐不仅需要考虑个人偏好，还需要考虑时空背景

[11]

，因为用户在不同的时间和地点有不同的选择和需求。

3. 冷启动。冷启动是基于位置推荐领域的一个关键问题，因为每天都有许多

新的兴趣点出现，特别是在快速发展的地区。

4. 变化。个人偏好的动态是最后一个，但也是最关键的挑战。正如[12]分析的那样，用户的喜好随着时间的推移而改变。例如，用户在生完孩子后自然会对访问与父母相关的兴趣点感兴趣(例如，游乐场和游乐园)，可能会忽略他们的其他兴趣。准确地捕捉到这种变化已经被证明是具有商业价值的，因为它表明了访问和购买意图。

LBNS服务将轨迹本身所包含的信息与地理信息、人类行为结合到了一起，伴随着LBNS服务的发展，轨迹挖掘技术也上升到一个新的台阶，由原先关注于轨迹本身形态本身的简单挖掘技术，逐步转向与关注于轨迹背后目标本身行为目的为驱动的深层挖掘技术的研究上去，诞生了一系列挖掘深层语义信息的新方法，取得了卓越的成果，并且被广泛应用于工业系统中。

然而，基于位置的社交网络服务有着其特定的信息格式与场景，研究方法也与开放空间中的轨迹数据研究方法有着不小的差别。

第 2 页

图 1.1 船舶轨迹与地形示意图

一条船舶轨迹如图2所示，船舶行为可能受到航道、资源、岛屿等等信息的影响，同时也表现了船舶本身的行为目的，具有语义特征。图3标注出了船舶行进轨迹中的实际行为语义，可以看到相同行为的轨迹间具有类似特征，但并不能说相似轨迹形状一定具有相同的轨迹语义。要将实际轨迹数据中所包含的原本语义信息直接挖掘出来，往往需要丰富的领域知识和巨大的工作量。实际上如果能将轨迹本身所包含的语义信息提取出来，通过一定的形式转化为其他轨迹数据挖掘任务的基础，即可完成各种类型的轨迹挖掘任务。将挖掘轨迹深层语义的方法与开放空间轨迹数据相结合，将会使空间轨迹数据的研究水平大大提升。

图 1.2 船舶轨迹的实际行为语义示意图

1.2 国内外研究现状

1.2.1 轨迹数据挖掘研究现状 1.2.1.1 轨迹时空模式挖掘

轨迹模式挖掘关注于轨迹本身的模式。研究学者为了分析单个移动目标或多个移动目标的移动模式，提出了一些固定的轨迹模式，例如聚集/组模式[13][14][15][16]，顺序模式[17]和周期模式[18][19]。关于作为序列的每个轨迹，顺序模式通常被定义为至少δ条轨迹共享的子序列，其中δ是用户指定的阈值。Zheng等人[14]解决了在语义轨迹中挖掘顺序模式的问题，利用两步程序SPLITTER来发现细粒度的顺序模

第 3 页

式。 SPLITTER首先通过将相似位置分组在一起来检索粗略图案的集合，然后通过以自上而下的方式分割粗糙图案来导出细粒度图案。周期性模式是另一种常见的轨迹模式，其对于理解移动物体的行为是重要的。Li等人[18][19]解决了采矿周期问题。该工作分别解决了基于参考位置和概率模型检测周期和挖掘周期性运动行为的两个关键子问题。

1.2.1.2 轨迹聚类

一些研究基于运动模式考虑了轨迹聚类的问题。希望分析的轨迹多来自一类或多类有着共同特点的运动目标，同类别的运动目标在运动方式中有着许多共同点，所以将轨迹聚类成具有相似运动模式的组是十分有意义的。时空数据聚类是一种无监督学习方法，通用技术是提取轨迹特征向量，检测相似性，然后聚类[20]。TODMIS [21]是一个从多源轨迹数据中挖掘聚类簇的一般框架。Johnson 等人提出使用自组织神经网络方法学习车辆轨迹分布模式，效果理想但需要足够高的采样率与较大的时间代价[22]；Gaffney等人对轨迹使用一个线性回归模型和EM算法进行聚类[23]，其对两个轨迹的度量使用完整轨迹的距离进行计算。但是现实中两条轨迹很难相似，为解决这个问题，Lee等人先对轨迹进行了轨迹分段，再建立起分段轨迹的聚类，并采用了 Trajectory-Hausdorff 距离进行距离度量[15]。Li等人进一步提出一个增强聚类算法来减小计算消耗和存储空间[16]。Lee和Li均采用了Aggarwal等人提出的一个Micro-and-Macro-clustering framework[24]。Liu等人[25]基于轨迹相关信息（例如，空间粒度，时间粒度，运动速度）以及位置的语义含义来识别运动对象组，解决了识别移动车辆的热点的问题，这实质上是一个聚类问题。由于热点可以被解释为车辆高人群的区域，因此聚类是解决热点区域提取问题的有希望的方法。与传统的基于密度的聚类相比，该工作采用基于移动性的聚类，其基于一个简单的原则，即高移动性（速度）的车辆可能意味着低拥挤程度，反之亦然。基于移动性的聚类比基于密度的聚类对轨迹数据集的大小更不敏感。

1.2.1.3 轨迹分类

轨迹分类旨在区分不同状态的轨迹或子轨迹，这些状态例如运动状态，交通模式和人类行为活动。基于用户兴趣点(point of interest, POI)，使用带有语义标签标记的原始轨迹或子轨迹可以将轨迹挖掘升华到更高层面，这实现了许多应用，例如旅行推荐，社交分享以及关联位置感知计算。

基于802.11无线信号，LOCADIO[26]采用隐马尔可夫模型将设备的运动分为两种状态：静止和移动。基于GSM信号的轨迹，Timothy等人[27]试图将用户的移动性分为三种状态，包括静止，行走和驾驶。Zhu等人[28]旨在根据其GPS轨迹推断出被占用，未被占用和停放的出租车的状态。

Zheng等人[29] [30]利用交通模式对用户的轨迹进行分类，交通模式包括驾驶，

第 4 页

骑车，公共汽车和步行。首先基于步行的分割方法将轨迹划分成段并提取一组特征，例如航向变化率，停止率和速度变化率，并将其馈送到决策树分类器中。基于推断结果，考虑到不同地点的不同运输模式之间的转移概率，进行基于图的后处理步骤以修正可能错误的推断。Liao等人[31] [32]提出了一种用于基于位置的活动识别和重要地点发现的分层推理模型。Yin等人[33]提出了一种基于DBN的推理模型，用于根据一系列WiFi信号推断用户的活动以及高级目标。

1.2.2 空间聚类算法研究现状

空间聚类算法是轨迹数据挖掘处理过程中常用的技术，多用于热点区域生成、轨迹聚类等任务中。

常见的聚类算法有以下几类：基于划分的聚类，如k-means；层次聚类，如Chameleon；基于密度的聚类，如DBSCAN（Density Based Spatial Clustering of Application with Noise）；基于网格的聚类，如STING（STatistical INformation Grid approach）。

基于密度的聚类算法可以发现具有任意形状以及带有单独噪声的聚类，在低维度数据中的表现优于其他种类的算法。所以基于密度的聚类在空间聚类任务使用更多，获得的效果更加理想。作为基于密度的聚类算法的代表，DBSCAN算法

[34]

可以发现任意形状的聚类，但算法需指定一个密度阈值，从而可以去除噪声点。

为提升DBSCAN在大型数据集中效率，Viswanath等人[35]提出了𝜌-DBSCAN算法，从数据集中提取领导者，再利用领导者扩展基于密度的聚类。Alex等人[36]在2014年提出了一种新的基于密度峰值的空间聚类算法（Density Peaks Clustering，DPC），用于发现相互距离较远的高密度区域。与k-means算法相比，DPC算法可以发现不规则形状的聚类，且可以自动获取聚类的个数，与DBSCAN算法相比，DPC可在噪声环境下聚类任意形状数据且实现简单，参数更容易选取[37]。许多研究提出了基于DPC的改进算法以提升算法的聚类效果。Mehmood等人[38]借鉴模糊聚类思想，对密度峰值进行合并以准确选择聚类中心。Gao等人[39]开发了一种新的非中心点分配策略和聚类合并与分裂过程，以适应密度峰值并动态调整聚类。Jiang 等人[40]提出了基于邻居距离曲线和合并聚类的DPC改进以自动确定𝑑𝑐的选择。DPC算法在空间数据集中能获得较好的聚类效果，由于需要计算所有点对间距离，具有𝑂(𝑛2)的时间复杂度。

1.2.4 研究现状分析

当前的时空轨迹数据挖掘研究方法分类繁多，应用广泛分布于各个领域，取得了较大的成果，然而当前的研究也存在着一些问题：

第 5 页

1. 当前时空轨迹数据挖掘研究对象主要集中于人与陆路交通工具，应用场景多为受限制的道路网络，这些场景中包含语义标注（例如路口、商铺、景点等），而在开放空间中，轨迹往往无任何其它标注信息，现有的许多方法不适用于开放空间轨迹数据。

2. 随着科技进步，特别是移动互联网的发展，时空轨迹数据量激增，许多算法效率较低，如何使得挖掘算法适应海量数据的计算，快速发现数据中所蕴含的有价值的模式，存在一定挑战。

3. 轨迹数据挖掘研究大多基于轨迹自身的形态规律，利用频繁模式挖掘、聚类等手段进行轨迹的模式挖掘，而忽略了轨迹内涵的深层语义信息。

1.3 本文的主要研究内容和创新点

本文的研究源自实际应用场景，从开放空间的轨迹（船舶、飞机或动物运动轨迹）中获得启发，挖掘大数据场景下与人类、动物相关的运动轨迹中所具有的语义信息。除数据量级较为庞大之外，这类数据最显著的特征是其反映了目标的群体性行为规律。

本文以提取开放空间中目标运动轨迹下所蕴含的语义信息为动机，基于空间数据聚类与轨迹向量化两个方面开展了理论研究，基于密度峰值聚类算法提出了基于网格改进，并构建了轨迹向量的生成方法。前者空间聚类算法作为后者轨迹向量化阶段的基础。最后，设计基于轨迹向量的轨迹分析实验，并以丹麦水域的AIS船舶数据为应用实例，验证了轨迹向量化方法的有效性。

1.3.1 本文的主要研究内容

（1）基于网格的密度峰值空间聚类算法

针对海量的轨迹数据处理效率问题，对DPC算法进行了改进，提出了基于网格的密度峰值聚类（Density Peaks Spatial Clustering by Grid Neighborhood Search，DPSCGNS）算法。

基于密度的空间聚类算法有着能够发现不规则形状聚类的优点。随着现今空间数据的数据量急剧增长，现有的空间聚类算法已无法满足海量数据的聚类任务。本研究在DPC算法的基础之上，针对聚类算法时间复杂度较高的问题，对算法进行了基于网格的改进，提出DPSCGNS算法利用网格维护轨迹点的邻域信息，克服了基于密度的聚类算法时间复杂度较高的缺点。改进的算法在多个仿真数据集以及真实船舶数据集上进行实验验证，表明算法可以有效地提取任意形状的聚类，并且对参数具有鲁棒性。与其他密度聚类算法的对比显示，DPSCGNS算法具有更好的效率，能够胜任大规模的空间数据聚类任务。

第 6 页

（2）轨迹向量化方法针对开放空间轨迹语义标注较少的问题，设计了开放空间轨迹序列化方法，并基于Word2vec模型将序列化的轨迹序列视为文本进行建模，提取带有语义信息的轨迹向量。

开放空间中的轨迹点的坐标具有连续性，在数据挖掘计算中呈现很高的维度，难以进行距离度量。设计了一种轨迹向量化方法，将轨迹转化为包含轨迹语义信息的向量序列，以便进行轨迹挖掘或分类、预测等任务。提出了轨迹动作的概念，设计了轨迹区域序列化方法和轨迹动作序列化方法，生成轨迹区域序列和动作序列。再将开放空间的轨迹从连续的二维空间点序列标注为区域序列和动作序列，从而得到可以进行向量化的标注序列。最后使用一个简化的神经网络模型，词向量模型Word2vec对离散化的轨迹序列进行向量化分析，得到包含语义信息的轨迹向量。

（3）基于轨迹向量的分析实验

使用AIS船舶数据集，针对轨迹向量设计聚类分析实验和轨迹的目标分类实验，验证轨迹向量方法的有效性。

轨迹向量类似于词向量，训练效果的好坏很难直接观测，需要在实际的学习任务中才能有所体现。为了验证本文的轨迹向量化方法的有效性，设计轨迹向量聚类分析实验，利用地理位置信息验证聚类类别中所包含信息的正确性。设计轨迹目标分类实验，利用AIS船舶的标注信息，基于轨迹向量进行轨迹目标分类的训练和测试。实验结果说明使用轨迹向量进行轨迹数据挖掘任务是可行的，验证了轨迹向量方法的有效性。

1.3.2 本文创新点

1. 提出了基于网格的密度峰值空间聚类算法，利用网格维护轨迹点的邻域信息，可以快速对大规模数据进行基于密度的聚类，能够提取不规则形状聚类，且对参数具有鲁棒性。

2. 提出轨迹动作的概念，使用分段轨迹的位置、运动时间、运动速度作为特征表示独立轨迹行为。

3. 设计了轨迹向量化方法框架，将轨迹转化为包含语义信息的区域向量序列和轨迹动作向量序列，获得的序列具有统一的形式，可以直接进行分类和预测等轨迹数据挖掘任务。

1.4 本文的组织结构

本文的组织结构：

第一章绪论。本章阐述时空轨迹数据挖掘的研究背景和研究意义，介绍时空

第 7 页

轨迹数据挖掘相关的研究现状，对目前的研究现状给出了分析，针对现状中存在的问题说明了本文的研究内容，最后梳理本文的组织结构。

第二章相关概念和技术。本章首先介绍了常用的空间聚类算法思路和原理，然后详细介绍了时空轨迹数据相关的概念和技术，其中包含时空轨迹相关概念、轨迹索引方法、轨迹度量方法以及轨迹挖掘相关的任务和概念。

第三章基于网格密度峰值空间聚类。本章首先给出了空间聚类的问题描述，其次介绍了DPC算法相关的概念说明和算法思路，然后提出了本文改进的DPSCGNS算法，通过多个数据集的实验验证，在聚类效果、参数敏感性、聚类效率三个方面对比了DPSCGNS算法与其他聚类算法。

第四章轨迹向量化方法。本章提出了一个轨迹向量化的框架，通过两种方法将轨迹分别转化为区域序列和轨迹动作序列，利用词向量模型对轨迹序列进行训练，获得可以嵌入的轨迹向量，最后对涉及算法进行简单的实验分析。

第五章基于轨迹向量的轨迹分析实验。本章首先介绍了丹麦水域AIS数据集及其标注信息，然后基于轨迹向量方法设计了向量聚类分析实验和轨迹目标分类实验，通过实验验证轨迹向量方法的有效性。

第六章总结与展望。本章总结了本文在轨迹数据挖掘研究方面的主要工作内容，并对本文研究中存在的问题和不足进行总结，提出了未来的工作方向。

第 8 页

第二章相关概念与技术

2.1 空间聚类相关算法

空间数据是一类与空间位置有关的数据，多从卫星遥感、GPS等设备所获取。大量的空间数据存放于例如地理信息系统（Geographic Information System，GIS）的空间数据库中，这些数据库通常具有完整的空间数据管理、索引、可视化与分析能力，但是对于包含轨迹对象深层语义的知识的挖掘和总结的能力仍然十分匮乏。研究基于密度聚类的空间数据挖掘技术，可以从空间数据库中挖掘知识，利用知识提升指挥与决策的智能化程度。常见的聚类算法有以下几类：基于划分的聚类，如k-means；层次聚类，如Chameleon；基于密度的聚类，如DBSCAN；基于网格的聚类，如STING。

2.1.1 基于划分的聚类算法

K-means算法以一个形式化的代价函数描述聚类划分[41] ，将聚类任务形式化为优化问题。其状态即为对待聚类目标的划分方法，而最优化函数是从输入数据集X与聚类方案C={𝑐1,𝑐2,…,𝑐𝑘}到实数空间的映射函数。

𝑘

𝐺𝑘−𝑚𝑒𝑎𝑛𝑠(𝑋,(𝑐1,𝑐2,…,𝑐𝑘))=∑∑𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒(𝑥,𝜇𝑖(𝑐𝑖))

𝑖=1𝑥∈𝑐𝑖

(2.1)

其中，distance为距离函数，而聚类中心𝜇i被定义为：

𝜇i(𝑐𝑖)=argmin∑𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒(𝑥,𝜇)2

𝜇∈𝑋′

𝑥∈𝑐𝑖

(2.2)

也可以将公式2.1写作：

𝑘

𝐺𝑘−𝑚𝑒𝑎𝑛𝑠(𝑋,(𝑐1,𝑐2,…,𝑐𝑘))=

𝜇1,𝜇2,…,𝜇𝑘∈𝑋

min

2()∑∑𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒𝑥,𝜇 𝑖′

𝑖=1𝑥∈𝑐𝑖

(2.3)

较直接的理解可以解释为求出k个聚类中心使得每个数据点到被划分的聚类中心的总距离最小。本质上是对每两个类别使用中心连线的中垂线进行划分，如图2.1所示。

直接求解该目标函数的最优解是一个非确定性多项式（non-deterministic polynomial，NP）问题，这类问题通常无法在有限时间内搜索得到结果，所以K-means使用一种简单的近似的求解算法，随机初始化k个聚类中心，不断迭代进行如下操作直到聚类中心不再变动或算法到达迭代次数上限：计算每个数据点距离最近的聚类中心并归为该类，之后以该类别中所有数据点的平均值来表示该类别

第 9 页

新的聚类中心。

图2.1 K-means聚类基于对元素进行划分

K-means算法会跌代收敛至局部最优解，但该局部最优解与全局最优可能存在很大的差距，所以为了获得更好的聚类结果，往往会多次随机初始聚类中心并迭代算法，从中选取最优的聚类结果。一些无监督学习方法可以作为启发式算法选择K-means的初始聚类中心。

2.1.2 基于密度的聚类算法

DBSCAN独创性地提出了使用密度进行聚类，其核心思想是一个聚类中的数据点周围总是密度较大，所以利用较大密度点之间的连接，即可获得聚类的结果

[34]

。为了计算数据点之间的连接，需要引入若干的记号与定义。

ϵ 图 2.2 密度相关定义示意图

给定数据集X，定义： 1. ϵ邻域（ϵ neighborhood）

给定邻域半径ϵ，𝑥𝑖∈𝑋，称 Nϵ(𝑥𝑖)={𝑥𝑗∈𝑋:𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒(𝑥𝑗,𝑥𝑖)≤𝜖}为𝑥𝑖的𝜖邻

第 10 页

域。显然有𝑥i∈Nϵ(𝑥𝑖)。 2. 密度（density）：设𝑥𝑖∈𝑋，称𝜌(𝑥𝑖)=|𝑁𝜖(𝑥𝑖)|为 𝑥i 的密度。密度是邻域内的样本个数，为整数值，并且与邻域半径ϵ相关。

3. 核心对象（core point）：给定核心点阈值𝑀𝑖𝑛𝑃𝑡𝑠，𝑥𝑖∈𝑋，若𝜌(𝑥𝑖)≥𝑀𝑖𝑛𝑃𝑡𝑠，则称 𝑥𝑖 为𝑋的核心点。记由𝑋中所有𝑋中核心点所构成的集合为𝑋_c ，并记优𝑋中的所有非核心点构成的集合为𝑋𝑛𝑐=𝑋\\𝑋𝑐。图2.2中红色点即为核心对象，圆的半径为邻域半径ϵ。

4. 直接密度可达（directly density-reachable）：如果𝑥𝑖位于𝑥𝑗的ϵ邻域中，且𝑥𝑗是核心对象，则称𝑥𝑖由𝑥𝑗直接密度可达。相反的情况则未必成立，除非𝑥𝑖也是核心对象，否则不能说𝑥𝑗由𝑥𝑖密度直达。如图2.2中，黄色对象可由核心对象直接密度可达。

5. 密度可达（density-reachable）：对于𝑥𝑖和𝑥𝑗,如果存在样本序列p1,p2,...,pT,满足p1=𝑥𝑖,pT=xj, 且pt+1由pt密度直达，则称𝑥𝑗由𝑥𝑖密度可达。这个定义的含义是密度可达关系可以传递给其他密度可达的起点。由直接密度可达的不对称性可以得出，密度可达同样也不满足对称性。图2.2中绿色对象可由任意红色对象密度可达。

6. 密度相连（density-connected）：对于𝑥𝑖和𝑥𝑗,如果存在核心对象样本𝑥𝑘，使𝑥𝑖和𝑥𝑗均由𝑥𝑘密度可达，则称𝑥𝑖和𝑥𝑗密度相连。与直接密度可达和密度可达不同，密度相连具有对称性的。图2.2中任意两个黄色对象间均密度向量。

DBSCAN的聚类思想是，从高密度的点出发，由所定义的密度关系将其余点合并，将所有点归类至多个类别，不同类别之间不相连。

同类别的一个聚类里可以存在一个核心对象或多个。只存在一个核心对象的情况下，聚类中的其他一般对象均与该对象密度相连。如果有多个对象，则聚类里的任意两个核心对象均满足直接密度可达的关系。聚类中所有核心对象的ϵ邻域里中的所有对象均属于该聚类。

DBSCAN算法遍历所有的未归类的对象，如果该对象是核心对象，则从该对象开始扩展所有满足直接密度可达关系的对象，并且把这些对象的ϵ邻域内的所有对象归类至集合，为一个簇。当所有核心对象都被遍历完后，剩余的未归类的非核心对象则被视为噪声。

DBSCAN算法的优点在于其能发现不规则形状的聚类，且不需要指定聚类数量。此外DBSCAN算法可以发现孤立的离群点（如图2.2中蓝色对象），视为噪声。DBSCAN的缺点是引入了额外的参数，并且时间效率较差。

2.1.3 基于网格的聚类算法

第 11 页

STING是一种多尺度的基于网格的聚类技术，它将聚类目标的空间区域以矩形单元作为分割，形成多层的不同尺度网格，之后再对不同尺度分割的矩形网格递归进行划分[42]。对于每种尺度的网格单元，形成单独的层次结构，不同尺度的层次之间，则由划分方法形成从属关系，有高层单元逐渐降低至底层单元。利用网格，STING统计了网格中的数据信息，并利用不同层次间的从属关系叠加计算，对于侧重于索引和查询的大数据量处理任务，STING具有快速高效的优点。

图 2.3 STING算法的逐层网格结构

STING的算法思想是从高层网格开始逐层处理每个网格，寻找聚类，当前网格，逐渐向底层网格递归。如果当前层的某个网格的统计信息已经不满足查询条件，则舍弃对该网格的查询，只递归其他网格的查询。

2.1.4 层次聚类算法

BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）算法是一种自底向上的层次聚类算法，其定义了聚类簇的聚类特征，并平衡树结构根据聚类特征来递归合并聚类[43]。

⃗⃗⃗⃗⃗设某簇中有N个D维的数据点，{𝑥⃗n}(n=1,2,...,N)，则该簇的聚类特征⃗𝐶𝐹⃗⃗⃗⃗⃗=⟨N,Σ⃗⃗l ,Σs⟩，其中N为该簇中数据点的数量，矢量定义为三元组：⃗𝐶𝐹

⃗⃗l=∑xΣ⃗⃗n=(∑𝑥𝑛1,∑𝑥𝑛1,...,∑𝑥𝑛𝐷)

n=1

n=1D

(2.4)

为各数据点的线性求和，标量

22T

Σs=∑x⃗⃗n=∑x⃗⃗n⃗⃗n=∑∑xnix

n=1

n=1i=1

(2.5)

为各数据点的平方和。

这种聚类特征的定义是具有可加性的，即两个簇合并后的簇的聚类特征等于

第 12 页

合并前两簇的聚类特征向量相加。定义聚类特征的目的是对簇的信息进行描述，以压缩合并计算时的扫描运算量，并且可以使用聚类特征定义簇间聚类，常用的簇间距离有形心欧基里得距离，形心曼哈顿距离，簇连通平均距离，全连通平均距离，散布恶化距离。

BIRCH为聚类特征构建了一颗平衡树，称为特征树，从一颗空树开始，逐渐将数据点插入到特征树中，并保持每次插入的特征树始终处于平衡状态。之后对构建的特征树进行修剪，以压缩数据量。构建完成的特征树代表了原数据在不同尺度上的聚类结构，其每个叶子节点即为一个较为紧凑的类别。直接利用现有的聚类方法例如K-均值算法对特征树的叶子节点进行聚类即可实现BIRCH的聚类结果。

2.2 时空轨迹相关概念与技术

2.2.1 轨迹数据的概念和表示类型

多来源的轨迹数据由不同系统与移动目标的传感器所采集，用以表示关于目标的位置信息，并且在时间维度上按某些采样率展示出一定的周期规律。这些轨迹数据描述了目标在空间中的位置随时间的变化经过采样后所保留的信息[44]。通常情况下，真实的目标轨迹是连续的，而设备所获取的时空数据点序列则是经过采样的结果[45]。

不同于其他时间序列数据，轨迹数据具有空间位置信息，可以用带时间戳的空间点𝑝𝑡𝑖∈𝑃表示轨迹序列中的元素，𝑝𝑡𝑖为多维空间点，且包含时间戳𝑡𝑖。考虑轨迹的空间与时间属性，可以将轨迹视为从时间𝑇∈𝑅+到𝑑维空间点𝑃∈𝑅𝑑的一个时间作为自变量的函数映射，即对于每个时间𝑡𝑖，𝑓将时间点𝑡𝑖单一地映射为点𝑝𝑡𝑖∈𝑃：

𝑓:𝑇→𝑃

可以得到轨迹的表示模型：

𝑇𝑟={𝑝𝑡1,𝑝𝑡2,…,𝑝𝑡𝑁}, 𝑡𝑖<𝑡𝑖+1

(2.6)

其中，𝑇𝑟表示轨迹，𝑁为轨迹的长度，轨迹序列中的元素𝑝𝑡𝑖={𝑥𝑖,𝑥𝑖,…,𝑥𝑖𝑑,𝑡𝑖}

(2.5)

对函数离散采样，所得的结果按时间顺序将轨迹点排列好可以形成轨迹序列，

包含𝑑维的空间坐标与时间𝑡𝑖，表示在𝑡𝑖时间，目标对象位于空间中的<

12𝑥𝑖,𝑥𝑖,…,𝑥𝑖𝑑>位置。

2.2.2 时空轨迹数据挖掘流程

移动目标的轨迹是从时域到目标所在运动区域（下称运动域）的连续函数。在动物跟踪中，目标通常在水中，地表或空气中自由移动。在这种情况下，运动域通常被建模为二维或三维的欧几里得空间。在车辆跟踪中，运动域通常被建模为模拟

第 13 页

道路网络的空间图。此外，移动目标的空间范围通常被忽略，使得在给定时间该目标的位置被建模为点。

图5.1展示了轨迹管理的流程架构。数据来源于若干对象，每个对象匹配具有唯一标识符id的移动设备。每个设备根据某种策略对其对象的位置进行采样。例如，设备可以以固定的频率（例如每秒）进行位置采样。位置记录具有格式(𝑡,𝑥𝑡,𝑦𝑡,𝑖𝑑)，代表时间𝑡处的采样位置是(𝑥𝑡,𝑦𝑡)。

一个对象的真实轨迹是不确定的。可以用对象的位置记录来创建对象的真实轨迹的近似值。通常来说，轨迹模式挖掘的现有技术通常假设目标的轨迹由折线（即一系列首尾相连的线段）给出。

采用服务器来存储和管理从所有设备收集的轨迹。处理轨迹的重要步骤有以下几点：

1.数据采集设备 1服务器2.预处理在线收集轨迹筛选轨迹设备 2设备 3 设备 n离线3.轨迹挖掘模式图 2.4 时空轨迹挖掘流程架构

1.数据收集。

在这一步中，设备将其位置记录提交给服务器。在线设备可以实时提交数据或者批量延迟提交数据。例如，设备可以在设备上尽快提交记录，或者在提交之前可以收集一小批记录以节省带宽。设备中存储的轨迹数据通过其他方式分批传送给服务器。例如，车辆中的流线导航装置偶尔可以连接到在线个人计算机，以便将位置记录传送到服务器。

2.预处理。

由于设备所采用的定位技术不完善，或是采用不同的采样策略，导致所收集的轨迹可能是不均匀的，或者质量较低。例如，本身应具有位置记录的轨迹在一些时刻缺失了对应位置的记录。

在预处理中，服务器“清理”数据并将其转换为标准格式为数据挖掘做准备。作为预处理的一部分，所确定轨迹的粒度和表示方法需要由服务器决定。例如，通

第 14 页

常选择一个合适的采样率，并决定一个轨迹是作为位置记录序列存储的，还是应该用时间到空间的分段线性函数来近似。

3.轨迹模式挖掘。

用挖掘算法（例如，轨迹聚类、频繁模式挖掘）发现所定义的轨迹中有价值的模式。

4.后处理。

这一步使应用程序能够分析或调整发现过程。例如，可以使用可视化工具以交互方式显示挖掘模式，这可以为挖掘算法找到更合适的参数值，或者发现下一步的研究问题。

2.2.3 轨迹数据预处理 2.2.3.1 轨迹查询

1．兴趣点-轨迹查询：询问POI，该兴趣点满足特定轨迹段的时空关系(例如K-近邻)；询问与指定点符合特定时空关系的轨迹。

兴趣点查询的一种基本类型是检索轨迹段中每个点的最近邻[46]。一些变体在路网环境中考虑了更实际的因素，即沿着轨迹的行进方向和目的地[47]。这样的兴趣点查询的目的是从许多点中找到一个点，例如一组加油站，在到达目的地的路上，从原来的路线(即离开路线，参观完加油站后返回)绕行是最小的。

当指定了一个特定的空间点时，可以查询轨迹或轨迹段。基于单点的查询[48][49]只查找到一个点的最近轨迹。类似地，关于轨迹的查询也可以查询在某一点附近的所有轨迹，例如在时间间隔500米以内的轨迹。在多点轨迹查询[50]中，给定一组具有顺序或不具有指定顺序的点，目标是从轨迹数据库中查找轨迹，使这些轨迹从地图上最好地连接指定的点。此查询在规划通过几个必去地点(如名胜古迹)的旅行路径时非常有用。

2.区域-轨迹查询：查询通过给定时空区域R的轨迹；给定轨迹查询其重叠或通过频繁的时空区域。

给定一个三维时空区域，轨迹查询搜索属于指定时空区域的轨迹段。这种类型的查询可用于支持流量分析和基于位置的服务。作为各种应用中的一种基本操作，这种查询类型得到了广泛的研究，并提出了各种索引(TB、3D-R树、STR树)。

虽然轨迹是相互独立的，但它们经常表现出共同的行为，比如在一段时间内通过一个小区域。用区域查询识别这些区域在轨迹聚类中很重要[15][51]。具体应用是根据与该用户相关的许多轨迹来确定某个用户在时间窗口中更可能传递的区域。

3.轨迹-轨迹查询：在一组轨迹中查询相似的轨迹；查询在距离阈值(即两个轨迹的最近接近点)范围内的轨迹。

第 15 页

轨迹-轨迹查询通常在轨迹数据库中查询相似的轨迹，试图对轨迹进行分类/聚类。轨迹分类/聚类可用于预测类标签等许多应用程序基于移动对象轨迹和其他特性,确定公路网络交通流,例如,或确定有趣的行为模式等等。一类轨迹查询发现常见子轨迹类[15]和另一类的目标是归类长轨迹在区域间的运动[16]。

2.2.3.2 轨迹相似性度量

相似度与距离是一组可以相互转化的量，存在着对应关系。在 KNN 查询以及轨迹聚类、分类等研究中，需要计算点或轨迹与轨迹的距离或相似度。

点 q 与轨迹 A 的距离 p 离 A 中最近点 q 的距离：

𝐷(𝑞,𝐴)=𝑚𝑖𝑛𝑝∈𝐴𝐷(𝑝,𝑞)

一种描述点集 Q 与轨迹 A 的距离的方法如下：

𝐷(𝑄,𝐴)=∑

𝑞∈𝑄

(2.7) (2.8)

𝑒𝐷(𝑞,𝐴)

Chen et al. 定义了 Best Connect Distance[52] 来度量一条轨迹与一些带有顺序或无顺序点的距离。

轨迹与轨迹的距离

一般使用所有轨迹中点的距离之和来度量轨迹整体的距离。如 Sum-of-Pairs [53]距离采用点距离之和为轨迹距离；DTW（Dynamic Time Warping）[54]试图对不同的长度的轨迹进行缩放，利用动态规划的方法计算一个使距离度量最小的缩放函数；最长公共子序列（Longest Common Sub-Sequence，LCSS) [55]试图寻找两个两条轨迹中最长的重叠子序列，其定义了两个轨迹点可以视为同一个点的邻域阈值，同样利用动态规划的思想求解这个最长的长度作为相似度；EDR 距离（Edit Distance on Real Sequence）[56]基于最长公共相似子序列，但并不计算最长距离，而是对不同的轨迹点给与惩罚值；编辑距离（Edit Distance，ED）[57]允许在轨迹序列上做三种操作增、删、改，计算使用这些操作完全消除一个序列与另一个序列的差别需要的最小操作次数。子轨迹间的距离度量

轨迹可以通过分割转化为线段所表示的子轨迹，轨迹的度量将更加便利。目前用来计算子轨迹间距离的方法主要有：

[58]

最小外包矩形（Minimum Bounding Rectangles，MBR）用来确定轨迹大体位

置，但不能表示轨迹内部形状等信息，其度量方式使用能够包裹轨迹的最小矩形边界。

𝐷(𝑇𝑆𝑖,𝑇𝑆𝑗)=‖(𝑚𝑎𝑥(𝑥𝑖𝑘),𝑚𝑎𝑥(𝑦𝑖𝑘))−(𝑚𝑎𝑥(𝑥𝑗𝑘),𝑚𝑎𝑥(𝑦𝑗𝑘))‖

(2.9)

第 16 页

图 2.5 轨迹MBR距离

Trajectory-Hausdof距离[59]用来测量轨迹段间距离，其包含垂直距离、

𝐷𝐻(𝑇𝑆𝑖,𝑇𝑆𝑗)=𝑤𝑖𝐷⊥+𝑤2𝐷∥+𝑤3𝐷𝜃

其中：

𝐷⊥𝑎+𝐷⊥𝑏

𝐷⊥=

𝐷⊥𝑎+𝐷⊥𝑏

𝐷∥=min (𝐷∥𝑎,𝐷∥𝑏) 𝐷𝜃=|𝑇𝑟2|·sin(𝜃)

(2.10) (2.11) (2.12) (2.13)

权重𝑤1，𝑤2，𝑤3为用户指定值。 2.2.4 常见时空数据挖掘任务 2.2.4.1 周期模式

轨迹数据的周期性模式挖掘涉及周期性目标行为规律的发现[60]，即在一定的时间间隔内遵循相同或近似路线的目标。这些周期性模式发现并解释了长时间移动历史（例如，每日，每周，每月和每年）中的周期性行为。

周期性模式对压缩移动数据也是有用的[61]，因为移动轨迹总是以稀疏的形式存在的。此外，周期性模式可以作为未来运动状态预测的基础[62]。而且，如果一个对象不能遵循确定的，规律的周期性行为，这可能是一个异常的环境变化或事故的信号。

当考虑目标移动时，期望一个目标在每个考虑的时间段重复其行为通常是不合理的。这意味着要确定的模式不应该是僵化的，而是应该允许对象行为在一个时期和下一个时期之间略有不同，但仍然会产生一个模式。此外，构成模式的行为也可能在时间上移动（例如，由于某些原因延迟）。

时空域中模式的近似性质增加了挖掘任务的复杂性。以及，产出模式的周期可能是不确定的。此外，相同数据中可能存在产生不同模式的不同时间跨度（例如，日和星期）。因此，轨迹数据的周期性模式挖掘应当考虑多种的建模方法以及有效的发现算法。

2.2.4.2 相对运动模式

给定轨迹的集合，捕捉和比较个体运动事件和组运动事件是具有挑战性的。为了便于轨迹数据分析，Laube等人的研究提出的相对运动（REMO）的概念[13]用来

第 17 页

识别运动物体轨迹集合中的类似运动。 “相对运动”一词是指不同运动物体在空间和时间上的运动属性之间的关系。

一种REMO模式描述了忽略移动物体的绝对位置的运动事件和模式。这意味着一组地理距离较远的物体可以被识别为属于同一组，只要它们具有相同的预定义运动特性。基本的运动模式包括（1）仅随时间变化的模式，（2）仅随对象变化的模式，以及（3）同时随时间和对象变化的模式。

另一种运动模式包括关于运动物体的绝对位置的空间约束[14][63]，这意味着在一段时间内，这些物体的运动出现在空间范围内（例如，矩形，圆形或椭圆形）。因此，这些模式是在捕捉地理上彼此接近的物体，这与基本运动模式不同。

其他的相对运动模式描述物体运动的聚合和分离。

聚合模式描述了在时间间隔以内的同组m个对象，其共享包含在给定空间范围内（例如具有半径r的圆中）的一些运动方向向量。这种模式捕捉了在一定区域内聚合的一组对象的行为。

相遇模式假设分布在一个地域的一些目标正在前往一个地点。在稍后的时间里，他们将根据他们目前的情况在这个地方相遇。为了在一个空间范围内找出这样一个（将要发生）的相遇点，相遇模式被定义为同组m个对象，这些对象将在k时间后同时到达给定的区域（即，当前运动位置包含在半径为r的圆内）。

发散模式是一个与聚集相反的概念，将空间发散模式与前一次相遇时的约束相结合。发散模式表现在图形中，其运动方向为“向后”而不是向前。

分离模式，就像发散模式是一个相反的融合概念一样，分离的概念与相遇的概念相反。这种模式捕捉形如同时离开会议这样的对象行为。

2.2.4.3 聚集模式

Gudmundsson等人[64]总结了REMO中的相遇和聚集模式的，根据移动对象的几何排列方式提供通用的定义。由此产生的新模式不需要REMO框架中的运动属性。新的模式定义考虑了运动物体的未来轨迹，使用新的遭遇和聚集模式根据运动物体的当前运动来捕捉将来可能发生的事件。

遭遇（Encounter）由同一组至少m个物体满足，假设它们保持当前的速度和方向，这些物体将同时到达半径为r的区域内。

聚集（Convergence）由同一组至少m个物体满足，假设它们保持当前的运动方向，这些物体将通过半径为r（不一定在同一时间）的区域。

流（Flock）[65]定义了两种类型的流行模式：一种是连续的物体移动，另一种是离散的物体移动。后者广泛用于数据库和数据挖掘研究。如果在连续k时间内至少有m个物体一起移动，同时停留在半径为r的圆内，则会产生离散的流。

2.2.4.4 轨迹聚类

第 18 页

随着跟踪和监视设备的发展，收集了大量的目标轨迹数据，这使得从海量数据中提取有用的信息变得更加重要，且十分具有挑战性。轨迹聚类是一种有效的轨迹数据分析方法，轨迹聚类旨在获取轨迹数据内的空间，时间甚至潜在信息，因此它适用于多种轨迹应用场景。根据设备类型，物体移动甚至目的，以不同的格式记录轨迹数据。例如，GPS跟踪设备通过跟踪对象移动来生成轨迹，在某些特定情况下，会添加与物体移动相关的其他属性，例如速度，方向或加速度。对于图像数据，连续帧中的像素序列形成轨迹，类似于光流[66]。为了测量不同类型的轨迹数据之间的相似性，数据表示，特征提取和距离度量选择是轨迹聚类的重要预处理工作。例如，轨迹可以表示为矢量并且重采样到统一规格，之后使用欧几里德距离。轨迹也可以被视为概率分布的样本，例如，Bhattacharyya距离[67]用于测量两个分布之间的距离。根据标记数据的可用性，轨迹聚类方法分为三类：无监督，监督，半监督。无监督模型的目标是在没有人类专家监督或标记数据的情况下对数据进行聚类。通过分析未标记的数据集得到推理函数。通常，标记数据用于学习将数据映射到其标签（即簇）的功能，在轨迹聚类之前学习监督模型，然后通过该函数预测未标记数据的簇[68]。标记数据需要人工专家的手工工作的沉重负担。大型数据集是不可行的。半监督折衷了前两种模型。它由标记数据训练，并由未标记数据进行模型调整[69]。

2.3 本章小结

本章首先介绍了几种不同种类的空间聚类算法及其特点，将作为第三章内容的启发以及实验对比。然后按照轨迹数据挖掘流程，对轨迹数据的表示、预处理、相关挖掘任务进行了介绍。最后介绍了神经网络相关技术，将为第四章轨迹向量训练过程提供基础。

第 19 页

第三章基于网格的密度峰值空间聚类

基于密度空间聚类算法可以发现任意形状的聚类簇，在各种时空数据挖掘任务中表现良好。但由于统计密度需要计算每对点间的距离，基于密度的聚类算法往往时间效率较差。本章针对DPC算法时间复杂度较高，无法处理大规模数据的问题，提出改进的DPSCGNS算法。

3.1 问题描述

空间数据是一类与空间位置有关的数据，多从卫星遥感、GPS等设备所获取。大量的空间数据存放于例如GIS的空间数据库中，这些数据库通常具有完整的空间数据管理、索引、可视化与分析能力，但是对于包含轨迹对象深层语义的知识的挖掘和总结的能力仍然十分匮乏。研究基于密度聚类的空间数据挖掘技术，可以从空间数据库中挖掘知识，利用知识提升指挥与决策的智能化程度。

定义 3.1 空间聚类：

给定一个含有N个D维空间点的集合𝛬={𝑝1,𝑝2,…,𝑝𝑁}，每个点𝑝i由二元组(𝑥𝑖,𝑦𝑖)组成(1≤𝑖≤𝑁)。空间点聚类任务是通过聚类算法找到一种划分𝐶={𝑐1,𝑐2,…,𝑐𝐺}，将点集𝛬划分为不相交的𝐺个集合，其中𝑐𝑔={𝑝1𝑔,𝑝2𝑔,…,𝑝|𝑐𝑔|}(1≤

𝑔

𝑐𝑐𝑐

𝑔≤𝐺)。

3.2 密度峰值聚类算法

DPC算法是一种较为新颖的基于密度的聚类算法，其考虑空间聚类的一个特点，即聚类簇中心应当具有较大的密度，而密度较小的区域应当分布于更聚类的边缘区域。基于这样的一种假设，DPC算法考察两个与密度相关的量：第一，局部密度𝜌𝑖；第二，与高密度点之间的距离𝛿𝑖。

定义 3.2 局部密度：记𝑑𝑖𝑗为𝑝𝑖与𝑝𝑗间的距离，则局部密度𝜌𝑖的定义：

𝜌𝑖=∑𝜒(𝑑𝑖𝑗−𝑑𝑐)

𝑗

(3.1)

其中

1, 𝑎<0(3.2) 𝜒(𝑎)={

0, 𝑎≥0

参数𝑑𝑐称为截断距离(Cut-off distance)。公式3.1的含义是局部密度等于与第𝑖个数据点之间的距离小于截断距离𝑑𝑐的数据点的个数。𝑑𝑐的确定，可以利用排序后所有𝑑𝑖𝑗的顺序，按比例选取第𝐾个值作为𝑑𝑐。

第 20 页

定义 3.3 与高密度点之间的距离𝛿： 𝑁

按{𝜌𝑖}𝑁𝑖=1进行排序可以获得序列{𝑞𝑖}𝑖=1，满足：

𝜌𝑞1≥𝜌𝑞2≥⋯≥𝜌𝑞𝑁

则可以定义与高密度点的距离𝛿𝑖

𝛿𝑞𝑖={

min{𝑑𝑞𝑖𝑞𝑗},

𝑗<𝑖𝑗≥2

(3.3)

𝑖≥2

(3.4)

max{𝛿𝑞𝑗}, 𝑖=1

这个定义描述了点与最近的更高密度的点距离，对于密度最大的点，其距离等于与其他点的最大距离。

根据上述定义求得在给定𝑑𝑐下的𝜌𝑖与𝛿𝑖，并同时计算每个点最近的更高密度点的编号𝑛𝑖，

0, 𝑖=1𝑛𝑖将用于计算非聚类中心点的归类属性。

𝑛

𝑛𝑞𝑖={

arg min{𝑑𝑞𝑖𝑞𝑗},

𝑗<𝑖

𝑖≥2

(3.5)

𝑐

确定聚类中心{𝑚𝑖}𝑖=1，并初始化聚类中心点的归属属性{𝑐𝑖}𝑁𝑖=1，具体为

𝑐𝑖={

𝑘, 点𝑖为聚类中心，且属于类别k−1, 其他情况

(3.6)

最后将所有非聚类中心点按照𝑛𝑖归类。由于𝑛𝑖点的密度总是大于𝑖点，利用序列{𝑞𝑖}𝑁𝑖=1顺序进行计算，即可保证在归类点𝑞𝑖时，𝑛𝑞𝑖总是已经被归类。

DPC算法有着与DBSCAN相同的效率问题。在局部密度ρ和高密度点之间距离δ计算过程中，需要计算和枚举每两个点之间的距离，时间复杂度为O(n^2 )，对于数量庞大的空间数据，时间消耗过多。另一个严重的问题在于存储空间，例如对于N=100000的数据集，将消耗37G的内存空间存储点之间的距离。低维度下DBSCAN算法存在基于R-树的优化[98]，但DPC算法要求计算的截断距离内点过多，即使使用R-树等数据结构也很难优化效率。总之，该算法在一般的实验环境中很难实现大数据的处理，所以需要使用本文提出的DPSCGNS算法。

3.3 基于网格的密度峰值空间聚类算法

DPC算法利用了聚类的密度以及聚类间的距离关系，能够聚类不规则形状的类别，同时保证了大聚类不被错分为若干小聚类。算法在效果上表现良好，但性能存在问题，难以处理大量数据的聚类。

DPC算法有着与DBSCAN相同的效率问题。在局部密度𝜌和高密度点之间距离𝛿计算过程中，需要计算和枚举每两个点之间的距离，时间复杂度为O(𝑛2)，对于

第 21 页

数量庞大的开放空间轨迹数据，时间消耗过多。另一个严重过的问题在于存储空间，例如在starkey数据中共有166885点，将消耗103G的内存空间存储点之间的距离。该算法在一般的实验环境中很难实现大数据的处理。

在DPC算法中，对于𝑖点的局部密度𝜌𝑖和高密度点距离𝛿𝑖的计算过程中，只有距𝑖点的距离在截断距离𝑑𝑐之内的点产生了贡献。为了解决大数据中的密度聚类，本文对DPC算法进行了改进，利用网格维护邻域信息，避免所有点对间的距离计算，以适用于大数据量的二维空间点聚类，引入了基于网格的密度峰值空间聚类（DPSCGNS）算法。

3.3.1 网格空间的密度与距离计算

DPC算法在计算𝑖点的局部密度𝜌𝑖和高密度点距离𝛿𝑖的过程中，只有距𝑖点的距离在截断距离𝑑𝑐之内的点产生了贡献。而在大规模空间数据集中，聚类数量往往较多，聚类仅受有有限范围内的数据影响。所以DPSCGNS算法利用网格进行邻域点的搜索。首先需要将空间坐标映射至网格空间，将原始数据的计算转化为网格单元的计算。

数据集𝛬共含有𝑑个维度，数据在各个维度上的存在最大值与最小值，度维𝑖的取值范围在区间[𝑙𝑖,ℎ𝑖)中，𝑖=1,,…,𝑑，则𝑆=[𝑙1,ℎ1)×[𝑙2,ℎ2)×…×[𝑙𝑑,ℎ𝑑)就是数据空间。利用给定的边长𝑠𝑖𝑑𝑒对数据空间进行划分，将原始数据空间转换为等大小的网格空间，网格中第𝑖个维度的网格数量为：

ℎ𝑖−𝑙𝑖

𝑢𝑖=⌈⌉

𝑠𝑖𝑑𝑒

则总的网格数量：

𝑊=∏𝑢𝑖

𝑖

(3.7)

(3.8)

为了进行下一步的计算，需要对数据集进行网格划分，即按照每个数据点在网格划分中的下标，计算数据点所映射到的网格。对于数据𝑝，它第𝑖维度的值𝑥𝑖所对应的网格下标为：

𝑥𝑖−𝑙𝑖(3.9)

𝑖𝑛𝑑𝑒𝑥𝑖=⌈⌉

𝑠𝑖𝑑𝑒

多个数据点可能落于同一个网格中。对于落于同一个网格中的数据点，利用同一个网格计算邻域值，可以有效地加快计算速度。

将𝑊个网格按任意顺序排序，可定义第𝑖个网格的数据点数量𝑤𝑖，表示经坐标变换后落于网格𝑏𝑙𝑜𝑐𝑘𝑖={𝑧1,𝑧2,…,𝑧𝑑}内的数据点数量,其中(𝑧𝑗∈{1,2,…,𝑢𝑗})。

重新定义DPSCGNS算法中的局部密度𝜌与距高密度点的距离𝛿

第 22 页

𝑤𝑗, 𝑤𝑖>0

𝜌𝑖={𝑑𝑖𝑠𝑡(𝑏𝑙𝑜𝑐𝑘𝑖,𝑏𝑙𝑜𝑐𝑘𝑗)<𝑑𝑐𝑒𝑙𝑙

0, 𝑤𝑖=0

∑

(3.10)

其中网格间的距离dist定义为网格各个维度的下标之差的平方和，即欧氏距离。

计算每个点的局部密度时，要枚举邻域内所有下标距离小于𝑑𝑐的点，考虑邻域点与当前点的相对位移是固定的，在具体操作时，可以预处理𝑑𝑐半径的邻域内所有点的相对位移集合，在计算每个点的局部密度时利用集合搜索所有相关节点。

直接计算𝛿𝑖的效率仍是网格数量𝑊的平方级的，为了优化算法的效率，按

𝑁{𝜌𝑖}𝑁𝑖=1进行排序获得序列{𝑞𝑖}𝑖=1，满足：

𝜌𝑞1≥𝜌𝑞2≥⋯≥𝜌𝑞𝑁

则高密度点的距离𝛿𝑖定义如下：

(3.11)

{𝑑𝑖𝑠𝑡(𝑏𝑙𝑜𝑐𝑘𝑞𝑖,𝑏𝑙𝑜𝑐𝑘𝑞𝑗)},𝑖≥2且𝑤𝑞𝑖>0 min

𝑗<𝑖(3.12) 𝛿𝑞𝑖= max{𝛿𝑞𝑗}, 𝑖=1且𝑤𝑞𝑖>0

𝑗≥2 0, 𝑤𝑞𝑖=0 {

计算𝛿时，从点i的最近邻域开始，逐渐向外扩展直到找到第一个密度大于𝜌𝑖的网格单元，即为最近的高密度网格。

3.3.2 确定聚类中心

聚类算法应当能提取数据中密度较大的类别，同时防止将同一聚类错分为距离过近的多个类别。聚类算法应当能提取数据中密度较大的类别，同时防止将同一聚类错分为距离过近的多个类别。DPC算法给出了一种根据局部密度𝜌与高密度点之间的距离𝛿来确定的聚类中心的方法，认为局部密度大且与更高密度点的距离远的点更可能是聚类中心。

计算一个综合𝜌与𝛿的量

𝛾𝑖=𝜌𝑖𝛿𝑖

(3.13)

第 23 页

（a）聚类中心（b）𝜌与𝛿的关系曲线

图 3.1 聚类中心和𝜌与𝛿的关系

DPSCGNS利用𝛾𝑖来确定的聚类中心。显然，越大的𝛾𝑖表示点𝑖越可能是聚类中心节点，假设需要将数据聚为𝐺类，只需按照𝛾𝑖对点进行排序，即可确定前𝐺个局部密度较大且距高密度点较远的聚类中心。

显然，越大的𝛾𝑖表示点𝑖越可能是聚类中心节点，只需按照𝛾𝑖对点进行排序，即可确定前𝐺个局部密度较大且距高密度点较远的聚类中心。

在聚类数量不明确时，𝛾𝑖同样能作为𝐺选取的参考，排序后的前50个𝛾𝑖与𝐺的关系如图3.2（a），图中可以观察到在聚类数𝐺=15时，曲线发生了明显波动，在对𝛾𝑖进行一阶差分后，曲线中的突起更加明显，在实际的使用中，可以使用这种方法进行聚类数目的确定。

（a）𝛾与𝐺的关系（b）𝛾的一阶差分与𝐺的关系

图 3.2 𝛾以及其一阶差分与𝐺的关系曲线

第 24 页

由于一个网格中只有一个密度与距离，表示同一个网格中的点最多只有一个聚类中心，无法表示多个聚类中心。实际上在根据𝛾𝑖=𝜌𝑖𝛿𝑖选取聚类中心的过程中，只要𝛾𝑖与网格的比例足够大，落于每个网格中数据点中的将只存在至多一个聚类中心。

直观来说网格足够小至每个网格只有一个数据点时，定理是显然的，但过小的间距会使需要枚举的网格过多，导致算法的时间效率下降。在大规模数据集中，聚类中心的min𝛿𝑖总是很大的，这使得网格可以足够大以容纳多个点在同一网格中。越大的网格边长，算法的运行效率越高，但聚类的准确度会下降。𝑠𝑖𝑑𝑒的选取跟数据密集程度有关，数据集的点数越多，网格划分应当越密集，而聚类数越多，则意味着数据的分布越不均匀，网格可以相对稀疏。根据实践经验，𝑠𝑖𝑑𝑒的大小可以使用公式3.14进行估计即可获得较好结果。

max(ℎ𝑖−𝑙𝑖)

𝑠𝑖𝑑𝑒< (𝑖=1,,…,𝑑)

⁄5√𝑛𝐺3.3.3聚类算法与性能

根据公式3.10和公式3.12求得在给定𝑑𝑐下的𝜌𝑖与𝛿𝑖，并同时计算每个点最近的更高密度点的编号𝑛𝑖，

arg min{𝑑𝑖𝑠𝑡(𝑏𝑙𝑜𝑐𝑘𝑞𝑖,𝑏𝑙𝑜𝑐𝑘𝑞𝑗)},

𝑗<𝑖𝑛𝑞𝑖={

0, 𝑖=1

𝑛𝑖用于计算非聚类中心点的归类属性。

𝑛

(3.14)

𝑖≥2

(3.15)

𝑐

确定聚类中心{𝑚𝑖}𝑖=1，并初始化聚类中心点的归属属性{𝑐𝑖}𝑁𝑖=1，具体为

𝑐𝑖={

−1, 其他情况

列{𝑞𝑖}𝑁𝑖=1顺序进行计算，即可保证在归类点𝑞𝑖时，𝑛𝑞𝑖总是已经被归类。算法3.1 DPSCGNS算法

输入：数据集𝛬，聚类数目𝐺，网格边长𝑠𝑖𝑑𝑒，截断距离𝑑𝑐。输出：𝐶={𝑐1,𝑐2,…,𝑐𝐺}。

1. 利用公式3.7与3.9将原数据集𝛬转化为网格数据𝑤𝑖𝑗。

𝑘, 点𝑖为聚类中心，且属于类别k

(3.16)

最后将所有非聚类中心点按照𝑛𝑖归类。由于𝑛𝑖点的密度总是大于𝑖点，利用序

2. 预处理𝑑𝑐半径内点的位移集合，利用公式3.10计算网格单元的局部密度𝜌。

3. 对𝜌进行排序获得𝑞𝑖，按照𝑞𝑖顺序进行R-树节点的顺序插入与最近邻查询，利用公式 3.12 计算与高密度点的距离𝛿，同时利用公式3.15计算高密度点的

第 25 页

编号𝑛𝑖。 4. 由𝜌和𝛿绘制决策图，在决策图中选择𝐺个聚类核心。

5. 按照公式3.16为𝐺个核心创建𝐺个聚类，如果网格点𝑝不是核心，将其分配给邻居所属的聚类。

6. 将对应网格中的每个点分配给该网格归类的聚类，获得聚类结果𝐶={𝑐1,𝑐2,…,𝑐𝐺}。

由于利用了网格，直观上算法的时间复杂度与网格总数𝑊密切相关。此外，本文针对空间数据聚类，仅分析二维的情况。

步骤1中计算𝑤𝑖过程的时间复杂度是𝑂(𝑁+𝑊)的，步骤2中计算𝜌的过程式𝑂(𝑊𝑑𝑐𝑒𝑙𝑙2)的，步骤3中𝛿和𝑛的计算的复杂度是𝑂(𝑊(log𝑊+𝑅))，𝑅=𝑎𝑣𝑒𝑟𝑎𝑔𝑒(𝛿𝑖2)，括号中前项为排序时间，后项为邻域搜索的平均复杂度，后续步骤5与步骤6中的数据点归类的时间复杂度是𝑂(𝑁+𝑊)的。总的时间复杂度为𝑂(𝑊(log𝑊+𝑅+𝑑𝑐𝑒𝑙𝑙2))。真实数据中，R总是远小于 𝑑𝑐𝑒𝑙𝑙的，log𝑊的数量级也很小，所以时间复杂度可以化简为𝑂(𝑊(𝑑𝑐𝑒𝑙𝑙2))。

在步骤2与步骤3的计算过程中，需要遍历每个网格，并计算每个网格中的𝜌与𝛿，导致理论复杂度较高。但真实中数据的不均匀，数据在网格中的重复度较高，需要枚举的网格总数是远小于𝑁和𝑊的。所以，在大规模空间数据集上，算法的实际复杂度要远低于理论的复杂度。

3.4 实验分析

3.4.1 聚类结果

本节分三个方面，分别分析算法的聚类效果、参数敏感性与运行效率。由于𝑠𝑖𝑑𝑒参数受不同数据集的尺度影响，为了使参数更加直观，给出了𝑥轴的网格数𝑢𝑥代替𝑠𝑖𝑑𝑒参数。

3.4.1 仿真结果验证

为了验证DPSCGNS聚类算法具有提取不规则形状聚类的能力，本文选择了四个形状数据集，flame，Aggregation ，Jain’s，Compound数据集进行聚类实验，包含人工合成的不规则形状二维数据，具有不规则的形状与密度。数据聚类的分布结果如图3.3。

DPSCGNS在各个形状数据上的聚类结果如图3.4所示。

所有数据的实验中，对DPSCGNS算法的参数𝑠𝑖𝑑𝑒与𝑑𝑐进行了调优，𝑠𝑖𝑑𝑒对结

第 26 页

(a) flame (b) Aggregation

(c)Jain’s (d) S1

图 3.3 形状数据集

表 3.1 DPC与DPSCGNS算法的聚类准确率比较

数据集类别 Flame Aggregation Moons Compound 2 7 2 6 DPC 准确率(%) 100 99.62 100 71.18 类别 2 7 2 6 DPSCGNS 准确率(%) 99.2 99.37 100 69.93 果的影响不明显，在3.4.2节中也有实验验证。Flame数据包含2个分布均匀的不规则形状聚类，算法成功地将两个聚类区分出来，在两个聚类容易混淆的边界处也进行了恰当的区分。Aggregation数据包含7个分布不规则聚类，并且含有聚类的边缘存在接触的情形，算法成功地给出了聚类的区分，并在聚类边缘处给出了均衡的划分。Jain数据包含了2个不规则的聚类，同时聚类内部的密度不均匀，算法仍

第 27 页

然能给出较好的划分。对于Compound数据集，大部分聚类被成功发现。由于右侧的稀疏数据点的聚类失败了。所以左侧的环形被分成了两类。出现这个问题的原因是，DPC的算法本身很难发现密度过于不平衡的聚类。所以改进的DPSCGNS算法的也具有同样的特点。DPC算法与DPSCGNS算法的准确率对比如表5.1。

(a) flame, 𝑠𝑖𝑑𝑒=0.2，𝑑𝑐=3.6，𝐺=2 (b) Aggregation，𝑠𝑖𝑑𝑒=0.7，𝑑𝑐=20，𝐺=7

图3.4 DPSCGNS算法对形状数据集的聚类结果

DPSCGNS聚类中心的决策图如图3.5，从决策图中可以看出，算法对于flame、Aggregation、Jain数据的决策点区分十分明显，在Compound数据集的决策图中，算法对于左侧的环形的决策点距离非聚类点较近，这是因为该聚类的密度与其他聚类的局部密度差别较大。

四个数据集上的实验结果说明，本文所改进的DPSCGNS算法在聚类效果上保留了DPC在聚类效果上的特点，能够完成空间数据集中，不规则形状数据的聚类任务。

第 28 页

(a) flame (b) Aggregation

3.4.2 参数敏感性分析

为了分析引入的网格边长参数对聚类效果的影响，选取高斯分布数据集进行实验，数据集共有5000数据点，数据边界干扰明显，聚类难度较大。

在固定𝑑𝑐=50000的前提下，将side从1000减小至25，对聚类结果如图3.6所示，并在图中标识了聚类中心点。当side大于200时，聚类结果的边界较光滑，聚类中心也均分布于高密度点的中心附近。side在100和50时，聚类结果在边界处有微小的畸变，但算法仍能较好的聚类每个类别的中心位置。当𝑢𝑥为30时，聚类形状在边界处出现了明显的网格状分界，说明此时对于边界处的数据类别已不可信，但算法仍能发现聚类的主要区域与聚类中心。

第 29 页

图3.6 高斯数据集在不同side 大小下的聚类结果

第 30 页

实验结果说明DPSCGNS算法对于网格边长参数具有一定的鲁棒性，允许算法在处理大规模数据时增大网格边长以获得更好的效率。

3.4.3 运行效率分析

为了对比算法效率，选择了DBSCAN、ρ-DBSCAN、DPC、k-means算法与DPSCGNS算法进行对比实验。实验数据为AIS船舶数据集，包含丹麦水域在2014年4月中的3亿条轨迹点数据。为了均匀选取不同规模的数据，选取了在经度范围56.37°N~59.05°N，纬度范围7.85°W~13.02°W之内的较密集数据，并对所有输入的数据按时间排序，并截取前1000-1000万条数据。

参数设定为：K-means (G=50)，DPSCGNS(side=0.003，dc=0.01，G=50)，DBSCAN (MinPts=200，eps=0.01)，ρ-DBSCAN (ρ=0.001，MinPts=200，eps=0.01)，DPC (dc=0.01，G=50)。

图 3.7 多种聚类算法的运行时间对比

图3.7给出了每种方法在AIS数据集上的运行时间，数据规模与运行时间轴均为对数形式。图中未出现的点代表某算法在过大的数据规模中，无法在限定的时间内给出结果，本文限定的时间是16小时。可以看到，当n大于10万时，DPC没有结果；当n大于50万时DBSCAN没有结果。然而，即使n= 1000万，KMDD，ρ-DBSCAN和K-means都可以在不到700秒内停止。在用时随数据规模的增长速度方面，k-means最慢，DPSCGNS次于ρ-DBSCAN但优于朴素的DBSCAN，原始的DPC增长最快。

综合考虑，DPSCGNS算法可以发现不规则形状聚类，效果与DPC接近，优于其他的算法。而在大规模数据下，DPSCGNS算法的速度较快。DPC算法则不能处理大型数据集。所以对于精度要求不高的情形下，本文算法具有一定的实用价值。

第 31 页

3.5 本章小结本章首先给出了空间聚类的问题描述，然后介绍了DPC算法相关的概念说明和算法思路，在DPC算法的基础之上，提出了本文改进的DPSCGNS算法，分析了算法的运行时间，通过多个数据集的实验验证，在聚类效果、参数敏感性、聚类效率三个方面对比了DPSCGNS算法与其他聚类算法。

第 32 页

第四章时空轨迹向量化方法

人类与动物的运动轨迹中蕴含着丰富的信息，其中包含了目标本身的行为习惯、地理等客观因素的影响。由于开放空间轨迹本身的复杂性与不确定性，难以直接进行挖掘、预测等任务，目前的轨迹挖掘任务通常也针对不同的应用进行特殊的方法设计。本章设计一种轨迹向量化方法，将开放空间轨迹映射为包含轨迹运动的语义信息的向量，使轨迹数据的向量序列表示能够适应不同种类的轨迹数据挖掘的任务。

4.1 问题背景与问题描述

动物、人类（交通工具）等动目标的轨迹中通常包含了目标的主观目的与任务，通过基于轨迹的数据挖掘，可以发现动目标运动行为中所包含的知识，发现人类以及交通工具中的运动行为知识可以改善我们的日常生活，发现自然界所包含的运动知识有助于更好地利用自然，将知识应用于商业活动中将产生巨大的社会财富，将知识应用于军事活动中则会极大地增强国家安全力量。

轨迹数据挖掘算法着眼于轨迹的形态、运动状态、地理位置等信息，常见的基于轨迹的数据挖掘任务有频繁模式挖掘、轨迹预测、轨迹分类、轨迹聚类等。不同的轨迹数据挖掘任务利用了不同层次的信息。

轨迹频繁模式挖掘利用位置与运动状态两个信息进行频繁模式地挖掘，挖掘结果例如图4.1。

教学楼5min6min操场食堂2min4min宿舍图 4.1 轨迹频繁模式挖掘结果

第 33 页

从放学后的学生运动轨迹中所挖掘出的两条常见路径为，由教学楼到操场再到宿舍、由教学楼到食堂再到宿舍。两条路径不仅在出现的频率上表现了峰值特性，在路径的特点上，如路径用时也表现出一致性。这种挖掘模式考虑了轨迹所聚集的区域与区域之间的关联，但只能发现轨迹序列中的频繁项，无法挖掘大量轨迹数据中所包含的深层语义信息。

基于用户位置的研究关注于轨迹的位置信息，利用Markov链、隐Markov链、神经网络的模型进行轨迹数据的预测，从而给用户推荐更好的出行信息。

用户位置轨迹图 4.2 基于用户位置的时空规律发现应用

如图4.1所示，基于用户位置的研究利用了轨迹的区域和地点作为输入，分析区域与地点之间的关联。尽管对于用户习惯等长期行为模式有着良好的效果，但忽略了运动状态信息，无法处理短期、相对高采样的轨迹数据。此外这些研究往往利用了已标注的签到信息，开放空间中的无标注轨迹数据则需要额外的处理过程。

在开放空间中的轨迹缺少标注信息，同时我们既关注于轨迹的地理位置信息，又关注于目标的运动状态。为了挖掘开放空间中轨迹所包含的深层语义信息，需要综合轨迹挖掘与基于位置的规律发现方法。

轨迹数据由若干带有时间戳的轨迹点组成，是一种序列数据。同为序列数据的自然语言文本的处理过程中，有一种序列分析方法，词向量模型（Word2vec）。Word2vec方法通过对文本分词、对词语进行神经网络学习最终对每个参与语义的词语生成一个词向量，词向量包含了词语的上下文语义关系，对于文本的分类与生成具有较好的效果。同时在基于位置的研究中，也有不少研究利用词向量模型处理带标注的位置序列。受Word2vec模型启发，希望将这种向量化方法应用于开放空间中的轨迹数据，从而生成对于轨迹分类、预测任务具有良好效果的轨迹向量。本文针对开放空间轨迹具有不确定性大，难以离散化的特点，设计了轨迹序列的离散化处理方法，并将Word2Vec方法应用于轨迹序列，提取出带有语义信息的轨迹点向量。

第 34 页

轨迹数据集文本数据集停留点提取变速、转向点提取轨迹动作文本分词热点区域去除低频词、停用词文本预处理轨迹序列构造轨迹序列嵌入词向量嵌入轨迹向量表示词向量轨迹聚类、分类、预测等任务文本分类、生成等任务图4.3 轨迹向量化方法与文本处理方法对比

轨迹向量化方法与文本处理的词向量方法对比如图4.3。类比于文本处理的词向量模型，本文的轨迹向量化研究步骤分为三步：

1. 轨迹序列化，基于轨迹位置信息以及运动状态，将轨迹分段再转化为轨迹段序列。本章中，提出了两种侧重点不同的轨迹序列化方法，一种仅基于轨迹点位置，适用于低采样轨迹，另一种基于位置与运动状态信息，适用于高采样轨迹。

2. 轨迹向量化，利用基于神经网络的词向量模型Word2vec对轨迹段序列进行向量化。

3. 利用轨迹向量进行实际的轨迹预测、分类等任务。由于这些任务仅使用轨迹向量模型所获取的向量，本章将不涉及这类实验，而在第五章中设计实验验证本章提取的轨迹向量化方法对轨迹挖掘任务的有效性。

第 35 页

4.2 时空轨迹转换为区域序列

先介绍一种常用的区域序列化的方法，先根据轨迹速度提取轨迹中国的停留点，再利用热点区域发现方法寻找高密度的区域，最后将轨迹匹配至高密度区域中，去除重复点形成区域序列。

热点区域被定义为空间中存留轨迹点较密集的区域，为了计算这些区域，往往采取聚类的方式获得轨迹点归属类别，之后再利用有归类的轨迹点进行区域划分。热点区域发现中可以使用不同的聚类算法，在本章中，选择第三章基于网格聚类算法进行轨迹点聚类。由于利用网格进行聚类，在后续的区域划分过程中，只需要利用网格进行区域的标注与划分即可。

1.2.1 停留点检测

定义4.1 轨迹点速度：给定轨迹𝑇𝑟={𝑝1,𝑝2,𝑝3,…,𝑝𝑁}，其中每个点𝑝=(𝑥,𝑦,𝑡)包含位置坐标𝑥、𝑦以及时间戳t，定义两个轨迹点𝑖,𝑖+1之间的速度为

𝑣𝑖𝑠=𝑑𝑖𝑠(𝑖+1,𝑖)/(𝑡𝑖+1−𝑡𝑖)

其中距离为欧氏距离

𝑑𝑖𝑠(𝑖,𝑗)=√(𝑥𝑖−𝑥𝑗)+(𝑦𝑖−𝑦𝑗)

使用前后两段速度的平均值作为第i个点处的速度

𝑠

𝑣𝑖−1+𝑣𝑖𝑠(4.3) 𝑣𝑖=

式中的计算需要点i的前后点，所以对于一条轨迹的起始点与终点，直接将该

(4.1) (4.2)

点处的速度定义为与最近点间的速度。

𝑣𝑖=𝑣𝑖𝑠 𝑖=1 𝑠

𝑣𝑖=𝑣𝑖−1 𝑖=𝑁

𝑠𝑠

𝑣𝑖−1+𝑣𝑖 𝑣= 其他情况{𝑖2

利用速度标注，可以定义轨迹中的停留点𝑝𝑠𝑡𝑜𝑝：

𝑝𝑠𝑡𝑜𝑝={𝑝𝑖|𝑣𝑖≤𝑣𝑐𝑢𝑡},𝑖=1,2,…,𝑁

其中𝑣𝑐𝑢𝑡为使用者定义的速度阈值。 4.2.2 热点区域发现

热点区域是动目标活动分布较为集中的区域，这些区域通常表示目标对一些常见地标、设施的青睐。利用热点区域可以分析目标轨迹中所包含的行为意图，所以热点区域也常被用来进行各类挖掘算法的预处理。

第 36 页

(4.4)

(4.5)

本节的处理过程中，对4.2.1中预处理后的轨迹停留点，利用基于网格的密度峰值聚类算法进行聚类（第三章研究内容），以得到轨迹点分布密度较高的区域，热点区域的发现过程如算法所述。算法 4.1 热点区域发现

输入：轨迹集𝑋，𝑣𝑐𝑢𝑡，网格边长𝑠𝑖𝑑𝑒，网格最小数量阈值𝑢𝑚𝑖𝑛。输出：热点区域集合𝐴={𝑎1,𝑎2,…,𝑎𝑚}，其中𝑎𝑖为网格组成的连续区域。 1. 对所有轨迹，根据𝑣𝑐𝑢𝑡，利用4.2.1节中的方法提取停留点𝑝𝑠𝑡𝑜𝑝

2. 按照网格边长𝑠𝑖𝑑𝑒，建立方形网格空间𝐺，将轨迹集𝑋映射至网格空间，统计每个网格中映射的停留点数量，去除停留点小于𝑢𝑚𝑖𝑛的网格，剩余停留点密集的网格𝐺′。

3. 利用第三章中的DPSCGNS算法对密集的网格𝐺′进行聚类，获得对于每个停留点密集的网格的聚类类别划分𝐶={𝑐1,𝑐2,…,𝑐𝑘}

4. 从每个聚类中最高密度的点开始，扩展紧邻的同类别的网格，扩展所得每个类别的网格所组成的集合即为热点区域集合𝐴={𝑎1,𝑎2,…,𝑎𝑚}。

算法主要分为四个步骤，步骤1中利用4.2.1节中介绍的停留点提取方法提取停留点；步骤2剔除停留点较少的无用网格，避免干扰，此步骤类似于文本处理中的低频词过滤；步骤3使用了第三章中提出的DPSCGNS算法进行网格聚类，获得网格的类别划分。步骤4中忽略每个聚类的不相连部分，获得连续的热点区域。关于第三步需要说明网格聚类的截断距离𝑑𝑐，在第三章中已经给出了合理的求解方法。此外，由DPSCGNS所获得聚类保证了网格所组成的空间是连续的，这保证了输出的结果也是连续的。

下面分析算法4.1的时间复杂度。步骤1中停留点提取算法需要对所有的轨迹数据进行处理，对于N条轨迹而言，停留点提取的时间复杂度为𝑂(𝑁)；步骤3中所有需要扫描所有的停留点，时间复杂度为𝑂(𝑀)，𝑀为停留点个数，远小于N；

2)步骤3中聚类算法复杂度为O(W(𝑑𝑐)，其中W为网格数量，受网格数量与

DPSCGNS的截断距离𝑑𝑐影响最大，所以只要给定较适中的网格数量，可以达到较高的效率。步骤4中的扩展过程是与网格数量呈线性的，复杂度为𝑂(𝑊)。总的时

2)间复杂度为O(N+W(𝑑𝑐)。

4.2.3区域序列匹配

聚类获得的热点区域对象，仍不能直接轨迹处理的数据使用，需要将轨迹匹配至热点区域，形成区域序列。具体规则首先对提取出的热点区域进行标号，

1. 对区域序列进行标号

2. 逐点处理每条轨迹，对于一个轨迹点，如果落于属于某聚类区域的网格

第 37 页

中，则将其映射为对应的区域标号，否则忽略该点。 3. 将轨迹中连续的相同标号视为一个标号，去除重复的序列。所得序列即为可以进行嵌入的轨迹区域序列。

4.3 时空轨迹转换为动作序列

4.2节中的轨迹区域序列构造只利用了轨迹的停留点所形成的热点区域，区域序列能够用于发掘区域之间的关联以及目标往返于各个区域间的规律，但存在两个问题：

1、区域序列构造只利用了停留点，只能用于挖掘轨迹停留时所发生的行为规律，忽略了运动状态改变时所蕴含的规律。而运动状态的改变在许多轨迹数据中往往代表着一些重要的含义，例如船舶的巡航、车辆受道路限速、动物遭遇天敌而转向等等。

2、停留点检测所需的速度阈值为固定值，对于不同类别的动目标轨迹，无法同时进行挖掘。

鉴于以上问题的存在，本研究提出了使用轨迹动作进行序列化的方法。 4.3.1 轨迹动作

轨迹动作被定义为轨迹中一段平稳的运动状态，可以通过运动状态变化过大的轨迹点对轨迹进行分段，将轨迹划分为运动较为平稳的子轨迹段。具体使用运动速度和运动方向来进行划分，即按照运动速度与运动方向变化过大的轨迹点对轨迹进行分段。首先定义变速点与转向点。

定义 4.2 变速点：变速点被定义为前后轨迹发生较大速度变化的轨迹点。为了提取累积变化过大的点，避免轨迹采样率过大导致速度过于平滑，我们采用滑动窗口的方法来统计轨迹点前后的速度，如果前后轨迹的平均速度变化过大，则将此轨迹点视为变速点。给定轨迹𝑇𝑟={𝑝1,𝑝2,𝑝3,…,𝑝𝑁}，其中每个点𝑖有一个速度𝑣𝑖，速度的定义由4.2.1小节中给出。轨迹𝑇𝑟中的轨迹点i是变速点当前仅当：

(∑𝑊

𝑖

𝑖+𝑊

(4.6)

𝑣𝑗−∑𝑣𝑗)>𝛿𝑣

𝑗=𝑖+1

𝑗=𝑖−𝑊+1

上式中𝑊表示滑动窗口大小，𝛿𝑣表示轨迹的速度变化阈值，二者都需要通过实验给定。

第 38 页

p1p22图 4.4 轨迹转向点与夹角

p33p44p5

定义 4.2 转向点：转向点被定义为前后轨迹方向变化较大的轨迹点。给定一条轨迹𝑇𝑟，为每个点定义其方向变化的角度，即前后轨迹点连线的夹角。图4.4中显示出了轨迹点的方向变化角度，由于夹角需要轨迹点前后存在其他轨迹点，所以轨迹的开始与结束节点不存在方向变化。

轨迹点的变化方向可以使用轨迹前后点连线的向量计算求得，角∆𝑖的计算公

式为：

𝑝⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗𝑝𝑖𝑝𝑖+1𝑖−1𝑝𝑖·⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗

∆𝑖=arccos()

‖𝑝‖‖‖⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗𝑝∗𝑝⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗𝑝𝑖−1𝑖2𝑖𝑖+12

针和逆时针的。规定顺时针角度为正值，并定义：

∆𝑖 𝑖𝑓 ∆𝑖≤𝜋∆′={ 𝑖∆𝑖−2𝜋 𝑖𝑓 ∆𝑖>𝜋

动影响，我们同样采用滑动窗口的方法统计轨迹点的方向变化。

′′

给定滑动窗口大小𝑊，在轨迹方向变化序列∆′={∆′2,∆3,…,∆𝑁−1}中，轨迹点𝑖

(4.7)

值得注意的是，反三角函数的计算结果总是正值，但轨迹的夹角确实分为顺时

(4.8)

使用根据角度正负修正后的角度∆′为了避免受轨迹细节扰𝑖进行转向点的提取。

是转向当且仅当：

𝑖

∑∆′j≥𝛿𝑑

𝑗=𝑖−𝑊

(4.9)

其中𝛿𝑑是用户指定的方向阈值。

有了变速点与转向点的定义，我们可以利用这些点来对轨迹进行分段，所得的子轨迹即为轨迹动作。一个的轨迹动作中的点具有相近的运动方向与运动速度，符合对行为的常规认知。

定义 4.4 轨迹动作：在轨迹𝑇𝑟中，一个轨迹动作被定义为一段长度为𝐾子轨迹𝑆={𝑝𝑠,𝑝𝑠+1,…,𝑝𝑠+𝐾−1}，满足两个条件：（1）𝑝𝑠和𝑝𝑠+𝐾−1均是变速点或转向点。（2）𝑝𝑠+1,𝑝𝑠+2,…,𝑝𝑠+𝐾−2中不存在任何变速点或转向点。

由轨迹动作的定义可以轻松推出一条轨迹中可以存在多个轨迹动作，且多个

第 39 页

轨迹动作之间不存在相交区间。利用轨迹动作的定义可以将除开始与结尾外的轨迹划分为多个轨迹动作，这些轨迹动作覆盖了子轨迹中段的所有轨迹点。轨迹动作可以表示轨迹在某一位置实施了某行为，则轨迹动作序列将原始轨迹表示成了一系列行为的序列。然而这种轨迹动作划分是模糊的，由于轨迹数据的不确定性，很容易出现轨迹被错误划分或划分不准确的情形，为了对轨迹动作做规整，还需要做后续处理，例如轨迹动作聚类。

4.3.2 轨迹动作距离度量

轨迹动作聚类类似于子轨迹聚类，需要设计相应的度量函数，才能比较两条子轨迹间的距离大小。为表示子轨迹的特征属性，首先引入如下定义：

定义 4.4 子轨迹重心：被定义为一段子轨迹中所有轨迹点的平均位置。对于二维空间中的轨迹点，我们利用算术平均计算所有轨迹点的每一维轨迹向量。给定长度为𝐾的子轨迹𝑆={𝑝1,𝑝2,…,𝑝𝐾}，其中轨迹点𝑝𝑖=(𝑥𝑖,yi)，轨迹重心𝑐𝑝为一个二元组𝑐𝑝=(𝑥𝑐𝑝,𝑦𝑐𝑝)，并且：

𝑥𝑐𝑝𝑦𝑐𝑝

=∑𝑥𝑖 K1

=∑𝑦𝑖 K

𝑖=1𝑖=1𝐾𝐾

(4.10)

(4.11)

轨迹动作中的子轨迹重心代表了轨迹动作发生的地理位置，是一个较为重要的特征。

定义 4.5 子轨迹速度：被定义为子轨迹中所有轨迹点的平均速度。速度不同于位置的计算，较大的速度具有较大的累积效果，所以使用几何平均来计算所有轨迹点的速度。给定长度为𝐾的子轨迹𝑆={𝑝1,𝑝2,…,𝑝𝐾}，其中轨迹点的速度序列为𝑉={𝑣1,𝑣2,…,𝑣𝐾}，子轨迹平均速度𝑣计算如式：

𝐾

(4.12)

𝑣=√∏𝑣𝑖

𝑖=1

定义 4.6 子轨迹移动距离：被定义为子轨迹中所有轨迹点间的累计距离。给定长度为𝐾的子轨迹𝑆={𝑝1,𝑝2,…,𝑝𝐾}，子轨迹移动距离𝑑𝑖𝑠计算如式：

𝑑𝑖𝑠=∑‖𝑝⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗𝑖+1𝑝𝑖‖2 K−1

𝑖=1𝐾−1

(4.13)

另一种方法是取首尾点的距离，但是这种定义方法忽略了轨迹做折线运动的距离，使得属性在某些情况下不具代表性，相较而言，累计距离更能代表轨迹动作。

第 40 页

我们使用轨迹的重心、速度、移动距离作为轨迹动作的特征，进行轨迹动作的距离度量。

定义 4.7 轨迹动作距离：给定两个轨迹动作𝑎1,𝑎2，距离度量函数𝐴𝑐𝑡𝐷𝑖𝑠𝑡(𝑎1,𝑎2)通过轨迹的重心c𝑝、速度𝑣、移动距离𝑑𝑖𝑠来进行比较： 𝐴𝑐𝑡𝐷𝑖𝑠𝑡(𝑎1,𝑎2)

=‖(𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑑(𝑥1)−𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑑(𝑥2),𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑑(𝑦1)−𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑑(𝑦2),𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑑(𝑣1)−𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑑(𝑣2),𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑑(𝑑𝑖𝑠1)−𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑑(𝑑𝑖𝑠2))‖2

式中𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑑表示归一化函数。在计算时，轨迹动作对应的子轨迹中不同特征的值域不相同，所以需要对轨迹动作的不同特征做归一化处理。

从轨迹动作距离的定义中可以看出，轨迹动作距离度量具有对称性，即𝐴𝑐𝑡𝐷𝑖𝑠𝑡(𝑎1,𝑎2)=𝐴𝑐𝑡𝐷𝑖𝑠𝑡(𝑎2,𝑎1)，同时轨迹动作距离的大小能够体现轨迹动作之间的差异性大小。

由上述定义，轨迹动作的距离实质上是四维向量间的距离计算，所以聚类算法可以使用第三章中的DPSCGNS算法。

4.3.3 轨迹转换为动作序列

类比于热点区域提取中的兴趣点聚类，轨迹转换为动作序列的过程需要对轨迹动作进行聚类，以提取不同的轨迹动作簇，继而对轨迹动作进行标记。4.3.2小节中定义的轨迹动作是四维向量，所以可以采用第三章中的DPSCGNS算法进行聚类，既可以提取轨迹动作中基于密度的簇，又可以提升聚类的效率，增强对大规模数据集的处理能力。

(4.14)

p1p1'p2p3p4p5p2'p4'

图 4.5 轨迹动作的错误划分

p3'轨迹动作聚类得到的结果是轨迹动作簇，还需要将轨迹转换为动作序列。4.3.1小节中提到，轨迹动作的划分是不精确的，可能存在一些扰动会导致轨迹被过细致

第 41 页

的划分，又因为轨迹划分的互不相交特性，正确的轨迹动作可能会被忽视，如图4.5′′中所示，𝑝1至𝑝5的轨迹本应被归类至绿色的轨迹动作𝑝1至𝑝4，但由于𝑝3点的扰动导

致被错误的划分为两个轨迹动作。聚类的结果是对目标运动规律在一定程度上的总结，是知识的体现，所以我们在本小节中将轨迹转换为动作序列，同时利用聚类获得的知识修正轨迹动作划分不精确导致的谬误。首先为每个聚类簇定义代表动作。

定义 4.8 代表动作：DPSCGNS算法的结果中，一个轨迹动作聚类的代表动作被定义为，属于该轨迹动作聚类且密度最高的网格所表示的轨迹动作。这表示周围所有网格的更高密度点均为代表动作的网格，代表动作更具有代表性。

对于每条轨迹，遍历轨迹中的每个转向点和变速点，考虑是否忽略该转向点和变速点。该点将前后的轨迹动作分割开，如果去除该点，则两个轨迹动作会被合并为一个轨迹动作。我们比较分割开的轨迹动作与合并轨迹动作到所有代表动作的最短距离，如果去除该转向点或变速点可以使距离更短，说明合并后的轨迹动作更符合轨迹挖掘规律，应当去除该转向点或变速点。不断迭代合并轨迹动作直到轨迹中无法去除任何转向点或变速点，将轨迹转换为动作标号即可。

轨迹转换为动作序列的完整算法如算法4.2。算法4.2 轨迹转换为动作序列

输入：轨迹集𝑋，窗口大小𝑊，阈值𝛿𝑣和𝛿𝑑，网格边长𝑠𝑖𝑑𝑒，聚类类别𝐾。输出：轨迹动作聚类集合𝐴𝑐𝑡={𝐴1,𝐴2,…,𝐴𝑚}，其中集合𝐴𝑖包含若干轨迹动作。轨迹转换后的动作序列𝑌。

1. 对所有轨迹，利用4.3.1节中的方法提取轨迹转向点和变速点，利用转向点和变速点将轨迹划分为轨迹动作。

2. 利用DPSCGNS算法对轨迹动作进行聚类，获得轨迹动作聚类集合𝐶以及对应每个类别的代表动作，即最大密度的轨迹动作𝑆𝑦𝑚={𝑠1,…,𝑠𝐾}。 3. 对于每条轨迹，遍历轨迹中的每个转向点和变速点，该点前后存在两个轨迹动作𝑎1和𝑎2，并且两个动作到其对应聚类的代表动作的轨迹动作距离为𝑑𝑖𝑠1和𝑑𝑖𝑠2。忽略该转向点或变速点，合并两个轨迹动作为𝑎3，并计算𝑎3到𝑆𝑦𝑚中所有代表动作的距离中的最短距离𝑑𝑖𝑠3。如果𝑑𝑖𝑠1+𝑑𝑖𝑠2>𝑑𝑖𝑠3，则去除并转向点或停留点，合并轨迹动作。

4. 迭代处理步骤3，直到所有轨迹中的轨迹动作都无法被合并。

5. 将经过合并处理后的轨迹按其中轨迹动作的类别进行标号，得到转换后的轨迹动作序列𝑌。

算法主要分为五个步骤，步骤1中利用4.3.1节中介绍的提取方法进行转向点和变速点的提取；步骤2使用了第三章中提出的DPSCGNS算法进行轨迹动作聚

第 42 页

类，获得轨迹动作的类别划分以及代表动作这一步中需要注意网格边长对不同的维度具有不同的量纲；步骤3利用聚类结果忽略轨迹中多余转向点与变速点，合并轨迹动作，减少轨迹由于扰动产生的轨迹动作错误划分。关于网格聚类的两个参数，即聚类数𝑘和截断距离𝑑𝑐的选择，同样利用在第三章中给出了的求解方法，而K则由用户指定，通常通过实验确定。

下面分析算法4.2的时间复杂度。步骤1中停留点提取算法需要对所有的轨迹数据进行处理，滑动窗户的移动过程是线性的，所以对于N条轨迹而言，变速点和转向点的提取的时间复杂度为𝑂(𝑁)；步骤2中由于是四维向量，则聚类算法理

4)论复杂度为O(W(𝑑𝑐)，其中W为网格数量，虽然实际的时间效率远好于理论中，

但为了获得更好的效率，仍需要压缩网格数量，使得截断半径内遍历的网格数𝑑𝑐减小；步骤3中所有需要扫描所有的变速点及转向点，设变速点和转向点数量为𝑀，时间复杂度为𝑂(𝑀)；第四步中迭代处理第三步的扫描过程，由于一条轨迹中某处的轨迹动作很难被多次合并，所以迭代次数可以视为是常数，则合并步骤的时间复

4)杂度仍为𝑂(𝑀)。𝑀远小于𝑁，则总的时间复杂度为O(𝑁+W(𝑑𝑐)。

时间复杂度分析得知算法的时间消耗主要由聚类算法产生。虽然理论时间复杂度不低，但由于网格空间中的数据变得更加稀疏，所以实际的时间效率仍然可以接受。

4.4 轨迹序列嵌入

序列嵌入是将非数值型的序列数据转换为数值型序列数据的过程，是对非数值序列数据进行挖掘、分类、预测的前提。本节使用Word2vec模型对4.2和4.3节中处理的轨迹区域序列和轨迹动作序列进行嵌入，从而得到带有语义信息的轨迹向量。

Word2vec词向量模型是一种用于自然语言处理的神经网络嵌入模型，它可以将文本序列中的词映射至统一的向量空间，得到可以计算相互间距离的词向量，这种方法常被应用于各类的文本分类、生成问题中。而在复杂网络、轨迹交通数据处理领域，也有许多新兴研究使用Word2vec进行嵌入实验，以达到更好的模型效果。

Word2vec主要有两种不同的具体模型实现[97]，一种是连续词袋（CBOW）模型，另一种是跳字（skip-gram）模型。二者模型类似，skip-gram模型根据目标词来预测目标词的上下文，CBOW模型则正相反，通过上下文来预测目标词。skip-gram适用于大规模数据量的训练，而CBOW模型则更适用于小数据集。

4.4.1 连续词袋模型

第 43 页

训练过程中，CBOW模型的输入是一个特定词语前后相连的若干词的词向量，而输出就是这特定的一个词的词向量。

输入层x1k隐藏层输出层x2khiyjN维V维xckC×V维图 4.6 CBOW模型结构

图4.6显示了具有C个字上下文的CBOW模型结构。模型分为输入层、隐藏层和输出层，输入层共有C个词{𝐱1,…,𝐱𝑐}的one-hot表示形式，共𝐶×𝑉维，隐藏层是𝑁维向量，从输入层每个词的位置到隐藏层共享一个𝑉×𝑁维的矩阵𝐖，矩阵𝐖的每一行就是需要学习的词向量。从隐藏层至输出层是一个𝑁×𝑉维的矩阵𝐖′，将隐藏层向量映射为输出层，即当前出现每个词的概率。

当计算隐藏层输出时，CBOW模型不是直接复制输入层上下文字的输入向量，而是计算输入层上下文字向量的平均值作为隐藏层输入。并使用输入层至隐藏层权重矩阵和平均向量的乘积为输入层的输出，传递给隐藏层向量𝐡。

1 𝐡=𝐖·(𝐱1+𝐱2+⋯+𝐱𝐶)

𝐶(4.15) 1

=·(𝐯𝑤1+𝐯𝑤2+⋯+𝐯𝑤𝐶)

𝐶

其中𝐶是上下文中的单词数，𝑤1,𝑤2,…,𝑤𝐶是上下文中的单词，v𝑤是单词𝑤的输入向量。𝐖是从输入层至隐藏层的一个V×N的权重矩阵，从隐藏层到输出层是另

第 44 页

′一个不同的权重矩阵𝐖′={𝑤𝑖𝑗}，其是一个N×V的矩阵。利用这些权重参数，可

以计算词汇表中每个单词的分数𝑢𝑗。

′

𝑢𝑗=𝐯𝑤·𝐡 𝑗

(4.16)

′

其中𝐯𝑤是矩阵W′的第𝑗列。之后利用使用一个指数线性分类模型softmax来获𝑗

得单词的后验分布，这是一个多项分布。

𝑝(𝑤𝑗|𝑤𝐼,1,…,𝑤𝐼,𝑐)=

∑𝑉′exp(𝑢)𝑗𝑗′=1

exp (𝑢𝑗)

(4.17)

利用最大似然估计定义损失函数为：

𝐸=−log𝑝(𝑤O|𝑤𝐼,1,…,𝑤𝐼,𝐶)

𝑉

=−𝑢𝑗∗+log∑exp(𝑢𝑗′)

𝑗′=1𝑉

′′

=−𝐯𝑤·𝐡+log∑exp(𝐯𝑤·𝐡) 𝑂𝑗

𝑗′=1

𝑇

(4.18)

其中𝑤𝑂为观测词，对应的𝑢𝑗∗为其输出。对其求导得到梯度为：

∂𝐸∂𝐸∂𝑢𝑗

′

𝐸𝐻==∑·=∑𝑒𝑗·𝑤𝑖𝑗

𝜕ℎ𝑖𝜕𝑢𝑖𝜕ℎ𝑖

𝑗=1

𝑉

(4.19)

其中𝑒𝑗为输出层误差。 4.4.2 跳字模型

Mikolov等人提出了skip-gram模型，图4.7显示了skip-gram模型的结构。它与CBOW模型相反，目标词现在位于输入层，上下文词位于输出层。

Skip-Gram仍然使用𝐯𝑤𝐼来表示输入层上唯一字的输入向量，这意味着𝐡只是复制输入层至隐藏层权重矩阵𝐖与输入词𝑤𝐼的点积。我们复制下面𝐡的定义：

𝐡=𝐖·𝑤𝐼≔𝐯𝑤𝐼

至输出矩阵计算每个输出：

𝑝(𝑤𝑐,𝑗=𝑤𝑂,𝑐|𝑤𝐼)=

exp (𝑢𝑐,𝑗)∑𝑉𝑗′=1exp(𝑢𝑗′)

(4.21) (4.20)

在输出层，输出𝐶个多项分布，而不是输出一个多项分布。使用相同的隐藏层

其中𝑤𝑐,𝑗是输出层第𝑐个位置上的第𝑗个词; 𝑤𝑂,𝑐是输出上下文单词中的实际第𝑐个词；𝑤𝐼是唯一的输入词。因为输出层的所有位置共享相同的权重，所以其实对于所有的𝑐，𝑢𝑐,𝑗是相同的。

第 45 页

利用最大似然估计定义损失函数为： 𝐸=−log𝑝(𝑤𝑂,1,𝑤𝑂,1,…,𝑤𝑂,1|𝑤𝐼)

𝐶

∗)exp(𝑢𝑐,𝑗𝑐

=−log∏

𝑐=1

𝐶

∑𝑉𝑗′=1exp(𝑢𝑗′)

𝑉

(4.22)

∗+𝐶·log∑exp(𝑢′) =−∑𝑢𝑗𝑐𝑗

𝑐=1

𝑗′=1

损失函数的梯度为：

𝑉

𝐶

′

EH𝑖=∑(∑𝑒𝑐,𝑗·𝑤𝑖𝑗)

𝑗=1𝑐=1

(4.23)

其中𝑒𝑐,𝑗为输出层第𝑐个位置的误差。

输出层y1j输入层隐藏层hiy2jxkN维V维ycjC×V维图 4.7 Skip-Gram模型结构

4.4.3 层序softmax

由于词典大小𝑉往往很大，直接使用梯度下降算法对CBOW和skip-gram模型进行求解会消耗太多资源。为解决这个问题，Morin and Bengio在2005年提出了

第 46 页

层序softmax方法改进word2vec的优化过程。层序softmax不再对单词表中每个词提供一个预测值，而使用树形结构分层次对输出词进行预测。层序softmax在输出层构建了一颗哈夫曼树，哈夫曼树是一颗二叉树，其基于最小化数据量的思想，可以对一个词典中的词依据词频进行编码，每个叶子节点代表一个词，使得编历文本中所有词所经过的树节点最少。图4.8为层序softmax构建的哈夫曼树结构示意图。

w1w2w3w4wV-1wV

图 4.8 哈夫曼树结构示意图

在进行预测时，网络为哈夫曼树的每一层输出一个值，之后根据每层的输出值判断向左或向右分叉，沿着树形结构达到叶子节点表示的词。通过使用层序softmax，可以将每个位置的预测值数量由词典大小𝑉，降低为至log𝑉 级别，极大地加快了训练速度。

4.4.4 负采样

Word2vec模型的计算量之所以大是因为预测向量长度𝑉过长，为了减少计算量，负采样是一种比层序softmax更为简单的方法：为了处理一个迭代计算的节点太多，可以只计算一些值得计算得分的节点。对于每一个词，在模型训练时只从V个词中选取𝐾个进行更新。

显然，需要将输出词保留在基本事实中作为正样本。此外需要对几个负面例子进行采样，称为负采样。采样词的分布，也即噪声分布可以是任意的，可以用实验来确定，也可凭经验确定一个好的分布。

在word2vec中（ Mikolov等人，2013b），作者不使用产生明确定义的后多项分布的负抽样形式，而是每个输出单词实例使用以下简化的训练目标函数：

第 47 页

𝐾′′

𝐸=−log𝜎(𝑣𝑤𝐡)−∑log𝜎(𝑣𝑤𝐡) 𝑂𝑖

𝑖=1

𝐓

(4.24)

其中{𝑤𝑖|𝑖=1,…,𝐾}是从噪声分布𝑃𝑛(𝑤)中采样的K个词。𝐡是隐藏层的输出值。在skip-gram模型中𝐡=𝐯𝑤𝑐；在CBOW模型中，𝐡=𝐶 ∑𝐶𝑐=1𝐯𝑤𝑐。矢量𝐯w是单

′

词𝑤的输入向量，取自输入层至隐藏层的权重矩阵的一行；𝐯𝑤是输出向量，取自隐

藏层至输出层的权重矩阵的一列。

目标函数的梯度为：

′

∂𝐯𝑤𝐡∂𝐸∂𝐸𝑗′𝑇′

EH==′𝑇·=(𝜎(𝐯𝑤𝐡)−𝑡)𝐯 𝑗𝑤𝑗𝑗

𝜕𝐡𝜕𝐯𝑤𝑗𝐡𝜕𝐡

𝑇

(4.25)

4.5 实验分析

本节中，对本章所涉及的各个算法进行实验分析。 4.5.1 数据集

本文选择了Starkey动物数据集进行聚类实验。Starkey遥感数据集是从1993年至1996年的秋季收集的。它存储于一个文本表格中，其中包括从保护区中的动物获得的287136个数据点。数据集中包含鹿群、驼鹿等动物，构成了丰富的动物遥感数据集，其中驼鹿共有166885个数据点，占比最大。进行数据收集活动的采样频率较高，为研究者进行额外分析提供了许多可能性。原始数据使用UTM坐标，可以直接进行距离计算，相比于经纬度坐标，无需进行转换。

图 4.9 动物数据集轨迹点热力图分布

网格数为500*1200，缓冲区半径为20时，轨迹点分布的热力图如图4.9所示。

第 48 页

图中红色部分表示轨迹点密度较高的区域，随着颜色向绿色过渡，密度逐渐降低。 4.5.2 热点区域提取实验

首先对轨迹数据进行停留点提取，取𝑣𝑐𝑢𝑡=0.06𝑘𝑚/ℎ，共提取7247个停留点。取网格数为50*80，𝑢min=20，𝑑𝑐=2.5，聚类数量为20，利用算法4.1进行热点区域提取，区域聚类的结果如图4.11。从图中可以看出，热点区域提取所得结果将热力图中的高密度区域中心提取出来，同时做了准确的划分。

图4.10 动物数据集热点区域提取结果

(a) 热点区域提取 (b) 原始轨迹聚点类

图 4.11 基于道路信息的实验结果对比

第 49 页

从数据集中提取额外的道路信息与栖息地信息，将额外信息与热点区域提取结果相对比，如图4.4，图中代表道路的线条的宽度表示了该道路的真实级别。图4.4(a)为热点区域提取的结果，可以观察到热点区域的边界表现了主要道路的形态，而热点区域也较好的呈现了Starkey地区南北两个主要栖息地位置。与(b)中使用原始轨迹点进行聚类的结果对比，可以观察到原始轨迹点聚类未能在东部的主要道路区分两个区域，而热点区域提取算法成功地将两个区域分隔开来。

4.5.3 轨迹动作提取实验

固定滑动窗口大小𝑊=2，使用不同的变速点与转向点参数进行实验，轨迹动作的提取结果如表4.1

表 4.1 轨迹动作提取

参数 𝛿𝑣=0.03,𝛿𝑑=𝜋/3 𝛿𝑣=0.1,𝛿𝑑=𝜋/3 𝛿𝑣=0.2,𝛿𝑑=𝜋/3 𝛿𝑣=0.5,𝛿𝑑=𝜋/3 𝛿𝑣=0.03,𝛿𝑑=𝜋/4 𝛿𝑣=0.1,𝛿𝑑=𝜋/4 𝛿𝑣=0.2,𝛿𝑑=𝜋/4 𝛿𝑣=0.5,𝛿𝑑=𝜋/4 变速点数 65222 30148 13437 5209 65222 30148 13437 5209 转向点数 121659 121659 121659 121659 轨迹动作数量 46677 27879 24173 22869 34071 22350 18265 16854 83409 83409 83409 83409 由于轨迹动作并非二维三维数据，难以通过可视化方法进行评价，这里引入了DBI（Davies-Bouldin Index）指标作为轨迹动作聚类结果的评价指标，通过对轨迹动作进行聚类，验证轨迹动作提取的效果。

DBI指标用于评价聚类结果的随机性，随机性越低表示聚类结果所包含的信息越丰富。计算公式为：

𝑎𝑣𝑔(𝐶𝑖)+𝑎𝑣𝑔(𝐶𝑗)1

𝐷𝐵𝐼=∑max()

𝑗≠𝑖𝐾𝑑𝑖𝑠𝑡(𝜇𝑖,𝜇𝑗)

𝑖=1𝐾

(4.26)

其中𝑎𝑣𝑔(𝐶𝑖)表示聚类𝑖中所有样本间的平均距离，即： 2

avg(C)=∑𝑑𝑖𝑠𝑡(𝑥𝑖,𝑥𝑗)

|𝐶|(|𝐶|−1)

1≤𝑖≤𝑗≤|𝐶|

(4.27)

𝜇𝑖表示聚类𝑖的中心点，在本实验中，使用聚类的代表动作表示。

对轨迹动作进行聚类，验证固定网格数量为30*40*30*30，聚类类别𝐾=60，不同参数获得聚类结果的DBI评价指标如表4.2。DBI数值在𝛿𝑣=20,𝛿𝑑=𝜋/4时取到最高值，说明在此参数下，轨迹动作的提取效果较好。

第 50 页

表 4.2 不同参数下轨迹动作聚类的DBI 参数 𝛿𝑣=3,𝛿𝑑=𝜋/3 𝛿𝑣=10,𝛿𝑑=𝜋/3 𝛿𝑣=20,𝛿𝑑=𝜋/3 𝛿𝑣=50,𝛿𝑑=𝜋/3 𝛿𝑣=3,𝛿𝑑=𝜋/4 𝛿𝑣=10,𝛿𝑑=𝜋/4 𝛿𝑣=20,𝛿𝑑=𝜋/4 𝛿𝑣=50,𝛿𝑑=𝜋/4 4.5.4 轨迹嵌入效率分析

DBI 0.392 0.41 0.453 0.366 0.378 0.421 0.47 0.363 由于轨迹嵌入方法所生成的结果为多维向量，无法直观进行分析，本章不进行向量的有效性验证，而在第五章中设计基于轨迹向量的轨迹挖掘实验，验证本章所设计的轨迹嵌入方法的有效性。本小节对轨迹序列的嵌入方法进行时间效率的分析实验，向量维度为5，负采样的𝑉取30。

表 4.3 轨迹动作嵌入的效率分析

模型 CBOW Skpi-gram CBOW Skip-gram 训练方法层序softmax 层序softmax 负采样-30 负采样-30 轨迹动作数量 18265 18265 18265 18265 运行时间/s 11.2 45.4 10.6 28.0 从表中可以观察到，CBOW模型的训练时间明显低于Skip-gram，训练方法的比较中，可以发现负采样对提升Skip-gram速度有着明显的效果，而两种训练方法对CBOW则不明显。

4.6 本章小结

本章首先设计了一种轨迹序列化的流程框架，然后介绍了基于热点区域的轨迹序列化方法，之后提出了轨迹动作的概念并设计了基于轨迹动作的轨迹序列化方法。其次利用词向量模型对轨迹序列进行向量训练。最后基于动物数据集设计了分析实验对本章涉及的三个算法进行了验证。

第 51 页

第五章基于轨迹向量的轨迹分析实验

轨迹向量在原理上可以用于向量聚类分析、轨迹聚类、分类、预测等任务，本章中设计区域向量聚类分析与轨迹目标分类实验，验证轨迹向量对于各种轨迹分析挖掘任务的有效性。

5.1 数据集及预处理

实验数据为丹麦水域AIS船舶数据集，本实验使用在2014年4月份与5月份前十天的数据，分别包含3亿和1亿条轨迹点数据。轨迹数据分布于经度范围52°N~63.05°N，纬度范围2.85°W~18.02°W之间。

图 5.1 丹麦水域AIS数据集

AIS数据集的每条信息包含多种相关字段，主要字段有时间戳、MMSI、经纬度位置、船只类型，如表5.1。

表 5.1 AIS数据集主要字段

字段 Timestamp MMSI Latitude Longitude Ship type （单位米）：

含义时间戳水上移动通信业务标识码（唯一）纬度经度船只类型示例 01/04/2018 00:00:00 2194006 55.538917 5.033400 fishing 由于经纬度坐标无法计算几何距离，首先通过式5.1和5.2转化为UTM坐标20037508.34

180

(5.1)

𝑢𝑡𝑚.𝑥=𝑙𝑜𝑛𝐿𝑎𝑡.𝑥 ∗

第 52 页

𝜋(5.2) log(tan((90+𝑙𝑜𝑛𝐿𝑎𝑡.𝑦)∗360))

𝑢𝑡𝑚.𝑦= 𝜋180轨迹间隔距离分布与间隔时间分布如图5.2。从图5.2(a)中可以看出轨迹的时间间隔在低频位置呈现出条纹状起伏，说明采样的频率高且较为规律，数据较为整齐。从图5.2(b)中可以看出，轨迹的间隔距离多位于500以内，且存在200与400的两个高峰值。

(a) 轨迹的间隔时间分布 (b) 轨迹的间隔距离分布

图 5.2 轨迹的间隔时间与间隔距离分布

从图5.3中可以观察到轨迹存在一定的异常点与缺失，体现在其中的过长的直线连线。本文没有涉及轨迹补全的内容，所以选择了根据轨迹间隔大小对轨迹数据进行分段的预处理方法。设定轨迹间隔距离阈值𝛿𝑝=10000，从轨迹中所有间隔距离小于𝛿𝑝的位置对轨迹进行切割，将轨迹划分为两段。划分效果如图5.4，图5.4中蓝色线条为间隔过大的被切割的部分，其余部分使用红色与黄色区别距离间隔，红色越深，距离间隔越大。

图5.3 轨迹（部分）的异常与缺失

第 53 页

图 5.4 预处理后的轨迹（部分）

5.2 基于轨迹区域向量的聚类实验

取𝑣𝑐𝑢𝑡=0.06𝑘𝑚/ℎ进行停留点提取实验，部分轨迹停留点效果如图5.5所示，所有轨迹共提取获得停留点218197个停留点。由于轨迹分布范围较广，在停留点聚类的过程中需要增加网格数量，以满足在局部的停留点密度计算。

图 5.5 停留点提取结果

取网格数量300*300，𝑑𝑐=5，𝑢min=3，将轨迹停留点聚为250类，聚类结

第 54 页

果如图5.6所示。可以看出图中轨迹停留点聚类对应了原始轨迹的高密度区域，这些区域多显示出了港口、海峡等特殊地点的位置。

图5.6 轨迹热点区域提取结果

图5.7 轨迹区域向量聚类结果（K=20）

将轨迹转化为区域序列向量后所得的轨迹向量，对轨迹向量用K-means聚类算法得到20类向量聚类（图5.7），通过对丹麦主要港口的比对（图5.8），图中灰色聚类包含了大部分的中部的主要港口，而图中深红色聚类则包含了东部的主要港口，此外，浅绿色聚类包含了北部的渔场，而南部单独的运河河道被聚为同一

第 55 页

类别。聚类类别存在与特定语义的位置的对应关系，说明向量本身具有语义特征。

图5.8 丹麦主要港口位置

5.3 基于轨迹动作向量船只目标分类实验

5.3.1 基于三层卷积网络的船只目标分类

使用三层卷积网络对船只目标进行分类，分类标签从AIS数据集中获得，分类的目标属性有渔船、帆船、客船、救援船等。基于TextCNN设计三层的卷积网络对AIS数据进行目标分类实验。

TextCNN网络是2014年提出的用来做文本分类的卷积神经网络，由于其结构简单、效果好，在文本分类、推荐等NLP领域应用广泛，其网络结构如图5.9。

Embedding：第一层是图中最左边的𝑛乘𝑘的轨迹向量矩阵，每行是轨迹向量，维度=𝑘，可以类比为语句中的词语。

Convolution：然后经过 kernel_sizes=(2,3,4) 的一维卷积层，每个kernel_size 有两个输出 channel。

MaxPolling：第三层是一个1-max pooling层，这样不同长度轨迹经过pooling层之后都能变成定长的表示。

FullConnection and Softmax：最后接一层全连接的 softmax 层，输出每个类别的概率。

对多分类问题，使用交叉熵（cross entropy）作为损失函数，其定义如式5.1：

𝑙𝑜𝑠𝑠=−∑∑𝑦𝑖𝑗𝑙𝑜𝑔𝑦̂𝑖𝑗

𝑛

𝑖=1𝑗=1𝑛

𝑘

(5.3)

其中𝑦𝑖𝑗代表第𝑖个标签的第𝑗个分量。

第 56 页

图 5.9 TextCNN分类网络

5.3.2 实验结果分析

首先对轨迹进行动作提取，滑动窗口𝑊=5，取𝛿𝜃=4，𝛿𝑣则根据速度的时间累积分布选取，如图5.10。图中除低速区域外，速度的两个峰值分别位于2.8与8左右，经单位换算后的速度为渔船的行驶速度10节以及其它高速船只的20节速度。此处𝛿𝑣选取低速区域到第一个峰值距离的1/4，即0.7。实验共提取轨迹动作77820个，该实验中轨迹动作相比于原始数据较少的原因是轨迹采样率高，变化较为平缓。

𝜋

图 5.10 轨迹速度的时间累积分布

将轨迹动作聚类为100类，同时为了配合分类网络的计算，轨迹向量的维度设定为20，对轨迹进行向量训练并将轨迹转换为动作序列，动作序列作为目标分类网络的输入。船只共30个分类，取其中较多的五类，运输船（Tanker），渔船（Fishing），客船（Passenger），货船（Cargo），军舰（Military），共1089艘船只的航迹。

实验中对数据采取80%/20%的比例划分训练集与验证集。如图5.11 所示，训练集与验证集的交叉熵损失随着训练的代数增加而呈下降趋势，当训练损失下降至一定程度后，验证集损失在一定范围内波动，但整体趋于平稳。

第 57 页

图 5.11 轨迹目标分类训练损失变化

另取五月前10天AIS数据集的进行测试，共包含1亿个轨迹数据点。经过处

理后的有效目标船只共235艘。使用𝐹1−𝑠𝑐𝑜𝑟𝑒作为测试的评价指标，其平衡了准确率与召回率：

𝐹1=

𝑇𝑃

2𝑃𝑅

𝑃+𝑅

𝑇𝑃

(5.4)

其中准确率𝑃=𝑇𝑃+𝐹𝑃，召回率𝑅=𝑇𝑃+𝐹𝑁。

模型在测试集上的F1-score为53.3%，说明了5类目标至少有半数以上被分为

了正确的类别。虽然模型在准确率的评价上并不是很高，利用轨迹向量进行的分类仅依靠轨迹自身的信息就能将部分目标区分开来，证明了使用轨迹向量化方法进行轨迹分析挖掘的可行性与有效性。

5.4 本章小结

本章选取了丹麦水域AIS数据集，对轨迹点进行了向量训练，并基于聚类算法验证了轨迹向量所对应的地理及语义信息。然后设计基于三层卷积网络的轨迹目标分类实验，利用AIS船舶的标注信息，基于轨迹向量进行轨迹目标分类的训练和测试。实验结果说明使用轨迹向量进行轨迹数据挖掘任务是可行的，验证了轨迹向量方法的有效性。

第 58 页

第六章总结与展望

6.1 本文主要研究成果

本文以提取开放空间中目标运动轨迹下所蕴含的语义信息为动机，基于空间数据聚类与轨迹向量化两个方面开展了理论研究，所做的工作如下：

1. 针对基于密度的聚类算法时间复杂度较高的问题，对DPC算法进行了基于网格的改进，提出DPSCGNS算法利用网格维护轨迹点的邻域信息，克服了基于密度的聚类算法时间复杂度较高缺点。改进的算法在多个仿真数据集以及真实船舶数据集上进行实验验证，表明算法可以有效地提取任意形状的聚类，并且对参数具有鲁棒性。与其他密度聚类算法的对比显示，DPSCGNS算法具有更好的效率，能够胜任大规模的空间数据聚类任务。

2.设计了一种轨迹向量化方法，将轨迹转化为低维向量序列，以便进行轨迹挖掘或分类、预测等任务。设计了基于热点区域的轨迹区域序列化方法和基于轨迹动作的动作序列化方法，生成轨迹区域序列和动作序列，再将开放空间的轨迹从连续的二维空间点序列标注为区域序列和动作序列，从而得到可以进行向量化分析的标注序列。最后使用一个简化的神经网络模型，词向量模型Word2vec对离散化的轨迹序列进行向量化分析，得到带有语义的轨迹向量。

3. 基于轨迹向量的分析实验

使用AIS船舶数据集，针对轨迹向量设计聚类分析实验和轨迹的目标分类实验，验证轨迹向量方法的有效性。对轨迹点进行了向量训练，并基于聚类算法验证了轨迹向量所对应的地理及语义信息。设计基于三层卷积网络的轨迹目标分类实验，利用AIS船舶的标注信息，基于轨迹向量进行轨迹目标分类的训练和测试。实验结果说明使用轨迹向量进行轨迹数据挖掘任务是可行的，验证了轨迹向量方法的有效性。

6.2 未来工作展望

由于学业时间有限，本文研究中仍存在一些不足之处亟待改进，需开展进一步工作。

1. 基于网格的密度峰值聚类算法虽然可以以较大的网格划分换取较高的时间效率，但网格边界处的划分仍存在瑕疵，理论上可以对分类边界处的网格进行基于密度的简单处理，使得聚类边界更加光滑，结果更加合理。

2. 训练轨迹向量所定义的轨迹动作目前利用了轨迹的速度、转角信息进行了

第 59 页

划分，但划分方法较为简单，没有综合整条轨迹进行分段划分。未来希望能有更加全面的划分方法可以使轨迹动作更能代表轨迹的行为特征。

3. 由于时间原因，对轨迹向量化方法有效性验证的实验较少，实验效果未经细致调试，结果较为粗糙。未来将针对更多数据集开展轨迹的聚类、预测等实验，对比轨迹向量在不同任务、不同数据集中的表现。

第 60 页

致谢

尽管抛出了些许异常，我的研究生任务终于运行完毕，返回了默认返回值。三年间，我最需要感谢的，也是最希望感谢的，是我的导师白亮教授，老师给了我足够的空间，同时也给了我足够的支持，如果不是您，恐怕我没有信心能够为研究生时代提交一份满意的源代码。

其次我要感谢我的师母胡艳丽老师，与胡老师的交流中，胡老师在学业与精神上给予我的鼓励，使我能够静下心，努力向前。

感谢师兄卢聪，师妹任秋芋，师弟罗灿、李涵在读研期间对我的帮助。感谢王江学长在研究方面的建议。

感谢实验室的小伙伴刘爽、张莉莉、梁经韵，能够与你们一同学习打拼真的很幸运。

感谢“八人寝室”的伙伴们，感谢“小胖子”，在我完成论文的过程中给予我无尽的支持，你们是我永远都会记得的挚友。

第 61 页

参考文献

[1] Cios K J, Kurgan L A. Trends in data mining and knowledge discovery[M]. Advanced techniques in knowledge discovery and data mining. Springer, London, 2005: 1-26.

[2] Zhu X，Davidson I. Knowledge Discovery and Data Mining：Challenges and Realities[M]. New York:Hershey，2007.

[3] Fayyad U M, Piatetsky-Shapiro G, Smyth P, et al. Advances in knowledge discovery and data mining[J]. 1996.

[4] Zheng Y，Zhou X. Computing with spatial trajectories[M]. New York:Springer New York Dordrecht Heidelberg London,2011.

[5] Zheng Y. Trajectory data mining: an overview[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2015, 6(3): 29.

[6] Giannotti F , Pedreschi D . Mobility, Data Mining and Privacy : Geographic Knowledge Discovery[M]. Springer Publishing Company, Incorporated, 2008.

[7] Rao K V, Govardhan A, Rao K V C. Spatiotemporal data mining: Issues, tasks and applications[J]. International Journal of Computer Science and Engineering Survey, 2012, 3(1): 39.

[8] Shekhar S，Zhang P，Huang Y. Data Mining and KnowLedge Discovery Handbook[M]. Berlin：Springer，2010：837-854.

[9] Fischer MM，Nijkamp P. Handbook of Regional Science[M]. Germany：Springer Berlin Heidelberg，2014：1173-1195.

[10] 刘大有, 陈慧灵, 齐红, 等. 时空数据挖掘研究进展[J]. 计算机研究与发展, 2013, 50(2): 225-239.

[11] Eagle N , Pentland A . Reality mining: sensing complex social systems[J]. Personal and Ubiquitous Computing, 2006, 10(4):255-268.

[12] Gilbert E, Karahalios K. Predicting tie strength with social media[C]// Sigchi Conference on Human Factors in Computing Systems. 2009.

[13] Laube P, Kreveld M V, Imfeld S. Finding REMO — Detecting Relative Motion Patterns in Geospatial Lifelines[M]// Developments in Spatial Data Handling. 2005.

[14] Laube P , Purves R S . An approach to evaluating motion pattern detection techniques in spatio-temporal data[J]. Computers, Environment and Urban Systems, 2006, 30(3):347-374.

[15] Lee J G, Han J, Whang K Y. Trajectory clustering:a partition-and-group framework[C]// Acm Sigmod International Conference on Management of Data. 2007.

[16] Lee J G , Han J , Li X , et al. Traclass: Trajectory Classification Using

第 62 页

Hierarchical Region-Based and Trajectory-Based Clustering[J]. Proceedings of the VLDB Endowment, 2008, 1(1).

[17] Li Z , Ding B , Han J , et al. Swarm: Mining Relaxed Temporal Moving Object Clusters[J]. Proceedings of the VLDB Endowment, 2010, 3(1):723-734.

[18] Li Z, Ding B, Han J, et al. Mining periodic behaviors for moving objects[C]//Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2010: 1099-1108.

[19] Li Z, Ji M, Lee J G, et al. Movemine: Mining moving object databases[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. ACM, 2010: 1203-1206.

[20] Yuan G, Sun P, Zhao J, et al. A review of moving object trajectory clustering algorithms[J]. Artificial Intelligence Review, 2017, 47(1): 123-144.

[21] Liu S, Wang S, Jayarajah K, et al. TODMIS: mining communities from trajectories[C]// Acm International Conference on Conference on Information & Knowledge Management. 2013.

[22] Johnson N, Hogg D. Learning the distribution of object trajectories for event recognition[J]. Image and Vision computing, 1996, 14(8): 609-615.

[23] Gaffney S, Smyth P. Trajectory clustering with mixtures of regression models[C]//KDD. 1999, 99: 63-72.

[24] Aggarwal C C, Han J, Wang J, et al. A framework for clustering evolving data streams[C]//Proceedings of the 29th international conference on Very large data bases-Volume 29. VLDB Endowment, 2003: 81-92.

[25] Liu Y, Kang C, Gao S, et al. Understanding intra-urban trip patterns from taxi trajectory data[J]. Journal of geographical systems, 2012, 14(4): 463-483.

[26] Krumm J , Horvitz E . LOCADIO: inferring motion and location from Wi-Fi signal strengths[C]// The First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, 2004. MOBIQUITOUS 2004. IEEE, 2004.

[27] Sohn T , Varshavsky A , Lamarca A , et al. Mobility Detection Using Everyday GSM Traces[C]// Proc of International Conference on Ubiquitous Computing. 2006.

[28] Zhu Y , Zheng Y , Zhang L , et al. Inferring Taxi Status Using GPS Trajectories[J]. Computer Science, 2012.

[29] Zheng Y , Li Q , Chen Y , et al. Understanding mobility based on GPS data[C]// International Conference on Ubiquitous Computing. ACM, 2008.

[30] Zheng Y , Liu L , Wang L , et al. Learning Transportation Mode from Raw GPS Data for Geographic Application on the Web[C]// International Conference on World Wide Web. DBLP, 2008.

[31] Liao L , Fox D , Kautz H A . Learning and Inferring Transportation Routines[C]// Proceedings of the Nineteenth National Conference on Artificial

第 63 页

Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, July 25-29, 2004, San Jose, California, USA. 2004.

[32] Patterson D , Liao L , Fox D , et al. Inferring High Level Behavior from Low Level Sensors.[J]. Proc Ubicomp, 2003, 2864:73--89.

[33] Yin J , Chai X , Yang Q . High-level Goal Recognition in a Wireless LAN[C]// Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, July 25-29, 2004, San Jose, California, USA. DBLP, 2004.

[34] Tran T N , Drab K , Daszykowski M . Revised DBSCAN algorithm to cluster data with dense adjacent clusters[J]. Chemometrics and Intelligent Laboratory Systems, 2013, 120(Complete):92-96.

[35] Venkatkumar I A. Comparative study of data mining clustering algorithms[C]// International Conference on Data Science & Engineering. IEEE, 2017.

[36] Bonchi F, Gionis A, Gullo F, et al. Chromatic correlation clustering[C]// Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 2012.

[37] Jain A K. Data clustering: 50 years beyond k-means[C]//Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, Berlin, Heidelberg, 2008: 3-4.

[38] Jiang S, Pang G, Zhang L. Enhanced Chameleon Clustering Algorithm [J][J]. Journal of Chinese Computer Systems, 2010, 31(8): 1643-1646.

[39] Hou J, Gao H, Li X. DSets-DBSCAN: a parameter-free clustering algorithm[J]. IEEE Transactions on Image Processing, 2016, 25(7): 3182-3193.

[40] Samarah S. Grid-based hierarchy structure for mining and querying vehicular ad-hoc networks[C]//Proceedings of the second ACM international symposium on Design and analysis of intelligent vehicular networks and applications. ACM, 2012: 63-68.

[41] Arthur D, Vassilvitskii S. k-means++:the advantages of careful seeding[C]// Eighteenth Acm-siam Symposium on Discrete Algorithms. 2007.

[42] Wei W, Yang J, Muntz R R. STING: A Statistical Information Grid Approach to Spatial Data Mining[J]. 1997.

[43] Xian L I. Heterogeneous data clustering algorithm of BIRCH[J]. Computer Engineering & Applications, 2009.

[44] Atluri G, Karpatne A, Kumar V. Spatio-Temporal Data Mining: A Survey of Problems and Methods [J]. ACM Computing Surveys, 2017, 1(1).

[45] Nanni M. Clustering methods for spatio-temporal data [D]. Pisa, Italy: University of Pisa, 2002.

[46] Bao J, Zheng Y, Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data [C]// International Conference on Advances in Geographic Information Systems. ACM, 2012: 199-208.

第 64 页

[47] Yoon H, Zheng Y, Xie X, et al. Social itinerary recommendation fro m user-generated digital trails [J]. Personal & Ubiquitous Computing, 2012, 16(5): 469-484.

[48] Tsoukatos I, Gunopulos D. Efficient Mining of Spatiotemporal Patterns [C]// International Symposium on Advances in Spatial and Temporal Databases. Springer-Verlag, 2001: 425-442.

[49] Cao H, Mamoulis N, Cheung D W. Mining frequent spatio-temporal sequential patterns [C]// 5th IEEE International Conference on Data Mining, IEEE, 2005: 82-89.

[50] Verhein F, Chawla S. Mining Spatio-temporal Association Rules, Sources, Sinks, Stationary Regions and Thoroughfares in Object Mobility Databases [C]// International Conference on Database Systems for Advanced Applications. Springer Berlin Heidelberg, 2006: 187-201.

[51] Verhein F, Chawla S. Mining spatio-temporal patterns in object mobility databases [J]. Data Mining & Knowledge Discovery, 2008, 16(1): 5-38.

[52] Li Z. Spatiotemporal pattern mining: algorithms and applications [M]. Frequent Pattern Mining. Springer, Cham, 2014: 283-306.

[53] Zhang J, Zheng Y, Qi D, et al. Predicting Citywide Crowd Flows Using Deep Spatio-Temporal Residual Networks [J]. Artificial Intelligence, 2018.

[54] Zheng Y, Zhang L, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories [C]// International Conference on World Wide Web. ACM, 2009: 791-800.

[55] Zheng V W, Zheng Y, Xie X, et al. Collaborative location and activity recommendations with GPS history data [C]// Proceedings of the 19th international conference on World Wide Web. ACM, 2010: 1029-1038.

[56] Chen L, M. Tamer Özsu, Oria V . Robust and fast similarity search for moving object trajectories[C]// Acm Sigmod International Conference on Management of Data. ACM, 2005.

[57] Shekhar S , Yoo J S . Processing in-route nearest neighbor queries: a comparison of alternative approaches[C]// ACM-GIS 2003, Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems, New Orleans, Louisiana, USA, November 7-8, 2003. ACM, 2003.

[58] Frentzos E , Gratsias K , Pelekis N , et al. Algorithms for Nearest Neighbor Search on Moving Object Trajectories[J]. GeoInformatica, 2007, 11(2):159-193.

[59] Theodoridis Y . Novel Approaches in Query Processing for Moving Object Trajectories[C]// International Conference on Vldb. DBLP, 2000.

[60] Chen Z , Shen H T , Zhou X , et al. Searching trajectories by locations: an efficiency study[C]// Association for Computing Machinery Special Interest Group on Management of Data International Conference. Association for Computing Machinery, 2010.

[61] Jeung H , Yiu M L , Zhou X , et al. Discovery of Convoys in Trajectory

第 65 页

Databases[J]. Computer Science, 2010, 1(1):1068-1080. [62] Tao Y, Papadias D. MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries.[C]// VLDB 2001, Proceedings of, International Conference on Very Large Data Bases, September 11-14, 2001, Roma, Italy. DBLP, 2001:431-440.

[63] Su H, Zheng K, Wang H, et al. Calibrating trajectory data for similarity-based analysis[C]// ACM SIGMOD International Conference on Management of Data. ACM, 2013:833-844.

[64] Song R, Sun W, Zheng B, et al. PRESS: a novel framework of trajectory compression in road networks[J]. Proceedings of the Vldb Endowment, 2014, 7(9):661-672.

[65] Shang J, Zheng Y, Tong W, et al. Inferring gas consumption and pollution emission of vehicles throughout a city[J]. 2014:1027-1036.

[66] Cai G , Lee K , Lee I . A Framework for Mining Semantic-Level Tourist Movement Behaviours from Geo-tagged Photos[C]// Australasian Joint Conference on Artificial Intelligence. Springer International Publishing, 2016.

[67] Li X , Hu W , Hu W . A Coarse-to-Fine Strategy for Vehicle Motion Trajectory Clustering[C]// 18th International Conference on Pattern Recognition (ICPR 2006), 20-24 August 2006, Hong Kong, China. IEEE, 2006.

[68] Yun-JunGao, ChunLi, Gen-CaiChen, et al. Efficientk-Nearest-NeighborSearchAlgorithmsforHistoricalMovingObjectTrajectories[J]. 计算机科学技术学报(英文版), 2007, 22(2):232-244.

[69] Gurung S , Lin D , Jiang W , et al. Traffic Information Publication with Privacy Preservation[J]. ACM Transactions on Intelligent Systems and Technology, 2014, 5(3):1-26.

第 66 页

作者在学期间取得的学术成果

[1] Shaotong Luan, Cong Lu, Liang Bai, Haoran Wang. Density Peaks Spatial Clustering by Grid Neighborhood Search. 2nd IEEE International Conference on Computer Systems, Electronics and Control. Dalian, China, 2018. 438-444.

作者在学期间取得的竞赛奖项

[1] 2016年CCF大学生计算机系统与程序设计竞赛银奖 [2] 2017华为软件精英挑战赛总决赛二等奖 [3] 2018华为软件精英挑战赛总决赛最优美代码奖 [4] 2018阿里巴巴全球调度算法大赛一等奖

第 67 页

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文