基于移动用户时空轨迹特征的轨迹分类研究

［刘汉艳］

1 引言

随着移动通信及移动社交工具的快速发展，运营商获取了大量移动用户的时空轨迹数据，这些时空轨迹数据已经在智能交通、用户出行等方面具有重要的数据支撑作用。时空轨迹作为当前研究的热点，不少学者已经把相关的研究应用于移动目标识别、路径轨迹模式挖掘等领域。Gonzalez 等[1]人利用收集的GPS 数据，采用神经网络分类器自动识别用户出行的模式；肖艳丽等[2]人通过提取移动用户轨迹的停留时间、平均速度等特征后，采用神经网络对移动用户的出行模式进行识别，取得了更高的准确率；Jahangiri等[3]人使多种分类方法将用户轨迹划分为包括走路在内的5 种类别；除了上述学者对轨迹全局进行分类外，不少学者通过对轨迹使用多阶段分类的方法。Zhang[4]将一条用户轨迹划分为多种交通模式；朱进[5]等人提出基于层次运动特征的轨迹分类方法，对轨迹的运动特征分为全局特征和局部特征，然后采用分类的方法对用户的轨迹进行分类。然而，大规模的轨迹空间分布往往具有非平稳性，因此，轨迹数据在空间上的变化是不均匀的。除此之外，移动用户的轨迹数据具有自身独特性的特征：时空轨迹数据受到信号的影响而导致轨迹数据本身缺失或者是错误的问题；时空轨迹的分类准确度会受到时空的影响；同一个位置在不同时间的运动特征的差别很大；单个用户轨迹的特征的选取问题。本文针对上述问题，首先采用卡尔曼滤波方法对移动用户的轨迹进行预处理；然后根据移动用户轨迹自身的特点，提取用户轨迹的运动特征、形状特征、轨迹位置特征、时间特征等向量，以此反映不同用户的轨迹特点；最后，采用谱聚类的方法对移动用户的轨迹特征进行分类，实现移动用户轨迹的分类。

2 相关研究

2.1 轨迹的定义

轨迹是用来描述移动对象的运动状态，指移动对象随着时间的变化而产生的空间变化的序列。本文所指的移动用户的轨迹是指由于移动用户发生业务或者位置的移动被基站记录下来的一系列离散的时空坐标，其时空坐标一般指基站的坐标，移动用户在时刻tn的基站坐标一般标识为（xn，yn，tn）。由上述的定义可知，移动用户在一段时间内的离散空间轨迹traj=（（x1，y1，t1），（x2，y2，t2），…，（xn，yn，tn））。

2.2 轨迹特征

提取轨迹特征的目的在于将有助于轨迹分类的特征提取出来。轨迹特征包括：运动特征、形状特征、位置特征以及时间特征。

运动特征是指轨迹的速度、加速度、角速度等特征的平均数、标准差、变异系数、自相关系数、偏度系数、幅度、频率等可以反映一个用户轨迹运动特征的参数。

轨迹的形状特征是指轨迹的曲率、方向、转角等特征的平均数、标准差、变异系数、自相关系数、偏度系数等可以反映一个用户轨迹形状特征的参数。

轨迹的位置特征是指轨迹的运动路径长度、回旋半径等特征的平均数、标准差、变异系数、自相关系数、偏度系数等可以反映一个用户轨迹位置特征的参数。

轨迹的时间特征是指轨迹的起始时间、到达时间、持续时间、停留时间、时间间隔等特征的平均数、标准差、变异系数、自相关系数、偏度系数等可以反映一个用户轨迹时间特征的参数。

2.3 轨迹的相似性度量研究

大部分轨迹相似性研究侧重于移动对象在自由空间的相似性，还有一部分研究是关注移动对象在受限空间的相似性，特别是在道路或者轨道网络上的相似性。当前的轨迹相似性一般都是扩展轨迹时间序列的时空相似性获得的。如Sinha 等人采用间隔时间作为轨迹时间特征，采用加权平均的欧式距离衡量个体间的时空相似性[6]；Kreveld 等[7]人以轨迹起始时间和持续时间为轨迹的时间特征，引入轨迹时空相似性来查找相同的子轨迹；Abraham 等[8]人考虑了轨迹的兴趣点和兴趣时间，然后采用类似编辑聚类的方法进行相似性研究。研究发现，轨迹的相似性度量主要依赖于轨迹间距离的定义，该“距离”主要指采用哪一种轨迹特征可以有效的衡量不同轨迹间的差别。比如：同一段道路的轨迹不应该由于时间的不同而具有时空相似性；同理，相同时间的不同道路上的轨迹不应该具有时空相似性。因此，在衡量移动用户时间轨迹的相似性时，必须考虑移动用户之间轨迹的时间、空间、运动、形状等多种特征，才能有效的衡量移动用户之间轨迹的相似性。

2.4 轨迹分类算法

在介绍轨迹分类前，先来介绍一下基于分类规则的时空轨迹预处理算法。分类规则算法的基本原理是：通过对训练数据进行分析，挖掘出某一个区域内轨迹支持度和置信度的阈值，然后对每一条轨迹进行遍历，如果该轨迹满足规定的条件，那么对轨迹进行特征提取，否则，该轨迹的特征为0。上述的轨迹预处理的优点在于能够剔除一部分随机的轨迹，大大减少了计算的复杂度。

在轨迹预处理之后，一般对轨迹的特征向量进行训练，建立分类器，然后再把实时的轨迹放进分类器中，实现轨迹模式的预测。分类方法有以下几种：神经网络[9,10]、支持向量机[11～13]、决策树[14～16]、谱聚类[17～19]、k-近邻[20,21]等。由于文章篇幅的限制，本文简单介绍支持向量机、决策树以及谱聚类算法实现的思路。

支持向量机在解决小样本、非线性及高维模式识别中具有很多优势，其处理数据思路：建立一个最优决策的超平面，使得平面两侧距离该平面最近的两类样本距离最大化。简而言之，就是找到一个超平面，使得不同类别样本之间的距离最大化。

决策树作为一种高效、可读性好的分类器，受到众多学者的追捧，其处理数据的思路：通过计算信息增益大小来判断当前的节点应该用什么特征来构建树，也就是说用计算出来的信息增益最大特征来构建决策树当前的节点。但是决策树存在特征选取困难和过拟合的问题是它计算精度的软肋。为了应对轨迹空间分布非平稳性、时空轨迹分类准确度受到时空影响以及特征数量的问题，本文采用谱聚类方法来实现用户轨迹分类，谱聚类算法无需事前确定特征向量的数量，还可对分布不均匀、任意形状的样本空间进行聚类分析，且聚类结果能收敛于全局最优。

谱聚类作为从图论演化出来的算法，在聚类中得到广泛应用。其主要思路为：所有的数据都视为空间的点，点之间可以用一条边连起来。“距离”较远的点的边权值较低，反之亦然，通过对所有数据点形成的图进行切图，让子图内部的边权值之和尽量高，子图之间的边权值之和尽量低，从而达到聚类的目的。谱聚类具有无监督、高效的特点，但是两点的“距离”的定义是复杂的，其需要根据不同的目标去选取每一个点的特征。有些“距离”可用两点之间的真实距离的倒数来衡量；但有些“距离”则需要用每一个点的特征向量来衡量，具体需要根据研究者的目的选取。

3 基于移动用户时空轨迹特征的轨迹分类

3.1 移动用户轨迹预处理

本文记录移动用户的轨迹是通过基站的位置来体现的，考虑到基站信号的不稳定、网络延迟等问题，因此本文采用动态卡尔曼滤波器[22]对用户轨迹进行过滤，以提高用户轨迹的准确性。如表1 是移动用户轨迹数据，通过对用户切换时间来计算移动用户当前的运动速度。基于移动用户位置和移动速度的动态卡尔曼滤波，能够实现用户轨迹信息的平滑。

表1 移动用户的轨迹示意图

当移动用户在移动过程中遇到基站信号不稳定发生来回切换的问题，结合速度和位置的动态卡尔曼滤波得到的效果如图1 所示。

图1 移动用户轨迹信息平滑前后的效果图

从图1 可以看出，经过动态卡尔曼滤波处理的移动用户轨迹对轨迹有典型的平滑作用，在城市密集区域，由于基站信号发生来回切换，使得移动用户轨迹信息不能真实的反映用户移动的真正状态，因此，使用动态卡尔曼滤波生成的轨迹能够在很大程度上平滑用户轨迹信息。

3.2 提取移动用户时空轨迹的特征

经过动态卡尔曼滤波器平滑用户轨迹后，不仅需要考虑轨迹的时间特征，还要考虑轨迹的位置特征。也就是在选定的时间段和某个区域范围内，通过关联规则FPGrowth 方法[23]挖掘移动用户的轨迹分类规则，如果某条轨迹满足支持度和置信度阈值，则提取该移动用户某段轨迹的特征；否则，把该移动用户的某段轨迹特征设为0，作为异常轨迹分开处理。通过训练某个区域某个时间段的所有都移动用户轨迹，找到了基于该区域的分类轨迹以及轨迹运行模式的分类规则，得到的某个区域移动用户分类规则示意图，如图2 所示。

图2 某个区域的移动用户轨迹分类规则

图2 展现的是基于FP 树算法找到的满足区域分类规则的轨迹段，由于速度和发生业务的时间间隔的差异性，在某一个区域的轨迹也有不定的差异。经过关联规则处理后，下一步就是要提取轨迹段的特征向量。本文提取的轨迹特征包括：运动特征、形状特征、位置特征以及时间特征。其中运动特征的参数有加速度、速度；形状特征参数有曲率和转角；位置特征参数包括运动路径长度；时间特征参数包括：起始时间、到达时间、停留时间。通过计算上述参数的标准差、变异系数、偏度系数，形成24个轨迹特征向量。

3.3 采用谱聚类的算法对移动用户的轨迹进行分类

把每一个用户视为图论的一个点，这些点用边连接起来。距离较远两个点的边权重值较低；距离较近两个点的边权重较高。本文的边权重计算方法是计算点与点之间的特征向量的空间距离，如果两点之间的距离较小，则说明两个轨迹段的特征比较相似，反之亦然；对每个点的距离标准化处理后，采用谱聚类的算法对上述的轨迹段进行聚类，聚类的结果如图3 所示。

图3 谱聚类的用户轨迹分类结果

3.4 实验结果

本实验选取某条道路中不同时间段的用户移动轨迹进行试验，实验随机选取10 天固定的5 个时间段进行实验，实验的准确率如表2 所示。

表2 实验准确率

表2给出了不同时间段的轨迹数据在本实验的聚类准确率分析结果。从表2可以看出，在相同路段的轨迹数据量下，基于轨迹多特征的不同时间段产生的聚类结果准确率存在一定的差异性。闲时准确率比忙时准确率要高一些，这是因为闲时用户轨迹的时间、空间、运动、形状等多种特征更具有平稳性。由此可知，本文的算法能够较好地对移动用户的时空轨迹进行分类。

4 结束语

本文基于移动用户轨迹提出了移动用户时空轨迹的分类算法，首先是采用动态卡尔曼滤波对移动用户的轨迹进行平滑处理；接着，利用FP 树挖掘移动用户的轨迹分类规则，剔除噪音轨迹后再对满足条件的轨迹进行特征提取；最后采用谱聚类的方法对移动用户的轨迹进行分类。实验证明，利用该方法能够在一定程度上提升移动用户轨迹分类的准确率。