基于GPS数据的轨迹聚类算法研究.pdfVIP

摘要

近年来，随着带有全球定位系统(GlobalPositioningSystem，GPS)、无线通讯

功能和各种传感器的移动设备在智能交通系统(IntelligentTransportationSystem，

ITS)中的广泛应用，使得基于位置服务(Location-basedservices，LBS)的应用变得

非常普遍。移动对象随着时间的推移产生并收集到大量的轨迹数据，最常见的就

[1]

是车辆的GPS数据，它蕴含着大量的、有价值的信息，如：出租车有无绕路行

为、城市人口出行规律、路况信息等等，对解决城市生活中所存在的问题具有十

分重要的价值和意义。因此，已经有越来越多的专家学者研究和挖掘这些轨迹数

据。轨迹聚类技术作为数据挖掘领域中一种重要的数据分析方法，成为GPS数

据挖掘的研究热点之一。

轨迹聚类技术是一种简单、直接的从获取轨迹数据中获取知识的方法，目的

是将轨迹按相似度分配到不同的组或簇中，要求每个簇内的轨迹之间的相似度尽

可能高，不同簇的轨迹之间的相似性尽可能低。轨迹聚类可以用于发现车辆的运

动规律和行为模式，获取热点路径、预测车辆行为等研究。现有的轨迹聚类算法

有很多，但在效率和聚类效果方面仍存在许多待改进之处。本文关注GPS数据

的轨迹聚类算法研究课题，针对现存的问题开展了如下两个研究：

(1)针对轨迹密度聚类算法研究存在的效率问题，本文提出了一种基于轨迹

压缩的快速密度聚类算法(FastDensityClusteringAlgorithmBasedonTrajectory

Compression，F_DDBSCAN)。首先，分析现有的密度聚类算法效率问题的具体

诱因；其次，针对过采样所带来的轨迹聚类低效问题，采用轨迹压缩技术对轨迹

数据进行预处理，大大减少GPS采样点的数量，来提高算法的运行效率；最后，

通过在密度检测算法(DensityDetectionDbscanAlgorithm，DDBSCAN)中引入

kd_Tree以提高分区密度聚类的运行效率。以南京市的出租车轨迹数据为例，实

验结果表明，对比现有密度聚类算法及传统的聚类算法，本文所提出的

F_DDBSCAN算法在一定程度上提高了聚类的精确度和运行效率，实验结果明显

优于文中所对比的其他算法。

(2)针对上述轨迹聚类算法聚类精确度和鲁棒性有待提升问题，提出了一种

基于深度嵌入的轨迹聚类算法(TrajectoryClusteringAlgorithmBasedonDeep

Embedding，DETC)。前面所提出的F_DDBSCAN算法相较于传统的算法有一定

的优势，但精确度和鲁棒性仍有待改进，且现有大多数的轨迹聚类算法以轨迹的

时空特征为对象，而忽略了轨迹自身所固有的属性。本文所提出的DETC算法能

够很好地捕获轨迹的高维特征信息，以轨迹向量、轨迹角度、轨迹交叉、时间信

息为特征空间，使用深度神经网络(Deepneuralnetwork，DNN)同时学习特征表示

和聚类分配，在一定程度上提高整个聚类算法的准确性。对比实验结果表明，由

于深度神经网络较为复杂，增加了算法的计算开销，导致DETC算法的运行效率

要低于其他几种算法，但DETC算法在聚类的精确度和鲁棒性上明显优于其他

几种对比的聚类算法。

关键词：基于位置服务，GPS轨迹，轨迹聚类，F_DDBSCAN算法，DETC算法。

ABSTRACT

Inrecentyears,withthewidespreadapplicationofmobiledeviceswithGlobal

PositioningSystem(GPS),wirelesscommunicationfunctionsandvarioussensorsin

IntelligentTransportationSystem(ITS),thelocation-basedservices(Location-based

services,LBS)applicationshavebecomeverycommon.Movingobjects