基于轨迹的数据挖掘相关技术总结

之前项目中接触到了轨迹数据挖掘领域,始终都没有时间对轨迹数据挖掘进行整体的梳理和总结,现在抽几天时间来进行总结并进行记录。

目前非常多的数据都是轨迹数据,如共享单车骑行的数据,手机GPS导航的数据,定位数据,一些传感器数据等等。在未来5G的发展下,相信轨迹数据或时空类型的数据会更多,而且会更加的复杂。

以前接触的数据大多没有空间的概念,都是一些普通的数据样本。这些数据可以认为是空间独立的,因此在数据分析或挖掘时,使用起来更加的方便,其技术也相对于成熟。而轨迹数据不同,它同时具有时间和空间双维度,在建模的时候很多传统算法在应用时都存在一定的问题,如轨迹的距离度量,这么一个简单问题,在轨迹里面都会变得复杂。

通过本次项目的实施,也对轨迹数据涉及到的主要问题进行了梳理,一些涉及到的技术栈进行了总结,便于后面项目中遇到该类问题时进查阅,同时增加自己的理解。

轨迹数据涉及的技术栈

轨迹数据的技术栈基本和普通的技术栈涉及到的过程一致,但是过程中某个部分具有很大的差异,下图是经过梳理得到的整个轨迹数据的涉及到的技术栈,其中每个部分都含有很多部分。具体如下图所示:

轨迹数据挖掘技术栈

轨迹数据存储

轨迹数据的存储和普通的数据存储不同,轨迹数据属于GIS数据,包含了位置数据,而且轨迹的表示为几何图形中的Line格式。因此一般采用GIS数据库进行存储,目前比较流行存储数据对比如下表所示:

数据库名 分布式 空间对象 HDFS
ESRI GIS Tools for Hadoop yes yes (own specific API) yes
GeoMesa yes yes (Simple Features) yes
H2) (H2GIS) no yes (custom, no raster) no
Ingres) yes (if extension is installed) yes (custom, no raster) no
Neo4J-spatial[15] no yes (Simple Features) no
PostgreSQLwith PostGIS no yes (Simple Featuresand raster) no
Postgres-XL with PostGIS yes yes (Simple Featuresand raster) no
Rasdaman yes just raster no
RethinkDB yes yes no

目前比较流行的为PostgreSQL with PostGISGeoMesa数据库,支持Point, Line, Poly等几何图形的存储,而且包含了很多GIS相关的功能函数使用。目前,MySQL,MongoDB, Redis等都支持GEO,但是对轨迹数据支持不完整,阿里,腾讯都有自己的时空数据的数据库。

轨迹数据的处理

轨迹数据处理是非常重要的一环,数据处理包括,轨迹的压缩,噪声的过滤,轨迹分段等等。数据处理不仅会影响后面建模,对特征提取,后期应用都会有一定的影响。

轨迹压缩

轨迹数据可能存在的主要问题有:数据量大,噪声多,定位不准,位置偏移等,而数据压缩可以在一定程度上解决这些问题,比如减少数据量,在某些应用场景下,不需要非常密集(时间)的轨迹数据,那么数据压缩后可以减小数据量。数据压缩主要有离线压缩(批量)和在线压缩。

  • 离线压缩:Douglas-Peucker (DP),Top-Down Time Ratio(TDTR)等算法
  • 在线压缩:Reservoir Sampling,Slicing Window,open window等算法

轨迹平滑

空间轨迹是一个$(x,y)$点的序列,每个点都有一个时间戳。因为轨迹通常是由传感器测量的,所以它们不可避免地会出现一些错误,需要对数据进行平滑化处理。主要方法有:

  • 均值滤波
  • 中值滤波
  • 卡尔曼滤波(Kalman filter)
  • 粒子滤波

轨迹分割

轨迹分割主要是对一个长轨迹分割为各个短的轨迹,将轨迹进行分解为不同段的轨迹。在很多应用场景下都会使用轨迹分割技术,目前也有很多轨迹分割算法,主要有:

  • 通过驻留点或停留点(stay point检测进行轨迹分割
  • 根据时间间隔进行轨迹分割
  • 根据轨迹点密度进行轨迹分割
  • 根据速度来进行轨迹分割

其中轨迹密度可以有很多方法进行检测,一般都基于密度聚类算法的改进算法来进行检测,如:K-中值算法,DJ-Cluster算法,cb_swot算法,MSN(Move-Stop-Noise)算法等。

数据管理

时空数据管理或轨迹数据管理,涉及到近邻查询,时间和空间维度的快速查询,空间索引等相关技术。而这一部分,一般GIS数据库都包含了相关的功能,只需要在创建表时,增加索引或使用相关功能函数即可。但是有时在工程应用时也会涉及到空间近邻匹配查询。

空间索引

空间索引的方法有很多,目前经常使用的有KD树,R树,四叉树及图等相关结构。但是目前效率较高还是基于图的索引,特别是在高维空间时。这里有一个关于NN索引查询效率对比:http://ann-benchmarks.com/

数据挖掘

轨迹数据的挖掘包含很多方面,基本传统机器学习的包含的,轨迹数据都包含在内。但是主要的一些方向有轨迹的分类,轨迹聚类,轨迹异常检测,轨迹推荐,轨迹的可视化等待。

论文解读-Trajectory Clustering: A Partition-and-Group Framework

这篇论文涉及到了轨迹数据挖掘过程的很多问题,该论文有很多值得借鉴的地方,因此对改论文进行说明,并对该论文中的所有短发框架进行了实现(python)。该论文涉及到了轨迹的数据处理,轨迹分割,轨迹距离度量,轨迹聚类,主要轨迹提取等待。

问题的提出

该论文主要从众多的轨迹中找出聚集在一期的分段轨迹部分,并合成新的轨迹。这样可以找出公共轨迹部分,密集轨迹部分等。如下图所示,其中方框内的部分就行需要找出的部分。

算法过程

轨迹的距离度量

轨迹的距离从3个方面进行度量,两个轨迹之间最远点和最短点之间的距离,轨迹的长度,轨迹的角度。三者的度量公式如下图所示:

trajectory distance

最终的总距离为:

其中权重为默认均为1,根据不同的应用场景可以修改权重。

Partition处理

轨迹的分段主要是通过MDL(最小描述长度)算法。通过找到轨迹的特征点来确定partition,通过计算两个点之间存在partition特征点时的MDL开销和不存在partition特征点时的开销,进行对比,从而确定特征点,并标记出来,算法相对较简单。最终将轨迹划分为了Segment,具体算法过程如下图所示:

trajectory partition

通过python实现后得到的测试结果如下图:

trajectory partition result

聚类

基本思想和DBSCAN算法一致,给定所有轨迹的Segment集合,输出聚类的集合。算法主要分为3个步骤,下面对这3个步骤进行简要说明:

  1. 对于每一条未分类的线段L,算法计算其的$\epsilon$邻域以判断该线段是否为核心线段。若L为核心线段,则程序跳转第2步。
  2. 计算核心线段的密度相连集合并把其加入该核心线段组成的簇中。如果新加入的线段未被分类,则把其加入队列Q中以做进一步扩展,因为该线段可能是核心线段;若新加入的线段不是核心线段,则不加入队列Q中。
  3. 计算每个簇的基数,若其值小于阈值,则算法将该簇淘汰,因为其不够密集。

可视化部分就不详细说明,可以参考论文。下面是将整个算法实现后,使用测试数据测试后的效果,算法可以设置不同的参数,得到的效果不同,如下图所示:

聚类和可视化效果

代码开源

GitHub: trajectory-cluster-https://github.com/MillerWu2014/trajectory-cluster