基于特征选择的移动对象轨迹简化算法

技术领域

本发明属于计算机应用技术领域，具体设计一种基于特征选择的移动对象轨迹简化算法。

背景技术

移动对象轨迹化简算法的研究是移动对象数据库研究领域的一个重要组成部分，它是伴随着移动电子产品的日益升级和普及而逐步产生和发展起来的，广泛应用于运动目标的跟踪定位、环境监测以及交通管理、基于位置的社交网络(LBSN)，路线导航轨迹推荐，目的地预测和用户的行为分析等许多领域。

智能手机、车载导航系统和可穿戴设备中的GPS传感器通常产生大量的原始轨迹，增加了数据存储、传输和数据分析的成本。轨迹数据简化压缩是通过减少轨迹数据量以降低存储器空间，从而提高数据传输、存储和处理效率的方法，根据特定的算法减少冗余和存储空间，同时尽可能少地丢失信息或重新组织数据。目前的移动对象轨迹简化算法分为离线简化和在线简化。以往的简化算法中大多依赖轨迹的几何特性(例如轨迹点位置之间的关系,轨迹点方向角度之间的关系)，这些几何特性都可以用轨迹点的相对位置展现出来，而针对移动对象的速度这一重要特征的研究还不是很完善。

随着大数据技术在分析应用方面有效性的凸显，怎样设计出能够准确且高效率地存储轨迹的信息的轨迹简化优化算法是近几年重要的研究问题。

发明内容

为了能够准确、高效率地存储移动对象的轨迹信息，本发明提供了一种基于特征选择的移动对象轨迹简化算法。

本发明提供的基于特征选择的移动对象轨迹简化算法，具体包含以下步骤：

S1、采用DBSCAN密度聚类算法对移动对象的轨迹数据进行处理，得到轨迹的速度区间；

S2、根据速度区间对移动对象的轨迹进行划分，得到与速度区对应的轨迹段；

S3、对每个轨迹段进行特征分析、选择简化算法，并对该轨迹段的轨迹数据进行简化处理；

S4、将每个轨迹段的简化结果合并、得到移动对象的轨迹简化结果。

可选的，设定时间间隔、采集移动对象的轨迹点p的数据，形成原始轨迹数据集。

可选的，所述轨迹点p的数据包含位置数据和速度数据。

可选的，对采集的原始轨迹数据集进行清洗，去除不合理的轨迹点，得到所述移动对象的轨迹T(p

可选的，步骤S1中，所述DBSCAN密度聚类算法用于对轨迹点p的速度数据进行处理。

可选的，步骤S2中，对所述移动对象的轨迹进行速度特征分析：

对于所述移动对象的轨迹T(p

其中，n-1表示速度标签T

可选的，步骤S2中，所述轨迹划分的计算如下：

使用最小Gini

可选的，步骤S3中，对每个轨迹段进行方向特征分析，具体方法如下：

测量轨迹段中每个轨迹点的切斜，与该轨迹段的起始轨迹点和终止轨迹点的连接线的夹角，计算得到该轨迹段的平均角度值，以及对应夹角大于平均角度值的轨迹点数量；

当对应夹角大于平均角度值的轨迹点数量超过该轨迹段中轨迹点数量的一半，则该轨迹段的方向变化频繁、并采用Angular算法对该轨迹段进行简化；

当对应夹角大于平均角度值的轨迹点数量不超过该轨迹段中轨迹点数量的一半，则该轨迹段的方向变化不频繁、并对该轨迹段进行距离特征分析。

可选的，所述距离特征分析具体方法如下：

在轨迹段的低速区间中，计算相邻两个轨迹点的距离；

当相邻两个轨迹点的距离低于5m，则轨迹点密集、并采用平均采用算法对该轨迹段进行简化；

当相邻两个轨迹点的距离不低于5m，则轨迹点不密集，并采用TD-TR算法对该轨迹段进行简化。

可选的，所述低速区间为轨迹段内速度位于0-22km/h的轨迹。

与现有技术相比，本发明提供的基于特征选择的移动对象轨迹简化算法将速度特征、方向特征和距离特征相结合、对移动对象进行轨迹简化，实现对运行时间、空间误差、速度误差、SED误差的进一步优化，避免的采用单一算法对移动对象进行整条轨迹进行简化，误差较大的问题。

附图说明

图1为本发明所述基于特征选择的移动对象轨迹简化算法流程图；

图2为本发明所述基于特征选择的移动对象轨迹简化算法示意图。

具体实施方式

以下结合附图，通过详细说明较佳的具体实施例对本发明作进一步介绍。

在采用本发明提供的轨迹简化算法处理移动对象轨迹数据之前，首先对移动对象的轨迹点p进行数据，形成原始轨迹数据集。采集的时间间隔可以设置在1-5s；采集的轨迹点p的数据包含位置数据和速度数据。然后对采集的对采集的原始轨迹数据集进行清洗，去除不合理的轨迹点，得到所述移动对象的轨迹T(p

图1为本发明所述基于特征选择的移动对象轨迹简化算法流程图。本发明提供的移动对象轨迹简化算法用于对所述移动对象的轨迹T(p

采用DBSCAN密度聚类算法对移动对象轨迹点p的速度数据进行处理，得到轨迹的速度区间，根据速度区间对移动对象的轨迹进行划分，得到与速度区对应的轨迹段。具体的，对所述移动对象的轨迹进行速度特征分析：对于所述移动对象的轨迹T(p

其中，n-1表示速度标签T

所述轨迹划分的计算如下：

使用最小Gini

继续对每个轨迹段进行方向特征分析或距离特征分析，并选择相应的简化算法对该轨迹段的轨迹数据进行简化处理。具体的，对每个轨迹段进行方向特征分析，具体方法如下：测量轨迹段中每个轨迹点的切斜，与该轨迹段的起始轨迹点和终止轨迹点的连接线的夹角，计算得到该轨迹段的平均角度值，以及对应夹角大于平均角度值的轨迹点数量；当对应夹角大于平均角度值的轨迹点数量超过该轨迹段中轨迹点数量的一半，则该轨迹段的方向变化频繁、并采用Angular算法对该轨迹段进行简化；当对应夹角大于平均角度值的轨迹点数量不超过该轨迹段中轨迹点数量的一半，则该轨迹段的方向变化不频繁、并对该轨迹段进行距离特征分析。

所述距离特征分析具体方法如下：在轨迹段的低速区间中，即速度位于0-22km/h的轨迹部分，计算相邻两个轨迹点的距离；当相邻两个轨迹点的距离低于5m，则轨迹点密集、并采用平均采用算法对该轨迹段进行简化；当相邻两个轨迹点的距离不低于5m，则轨迹点不密集，并采用TD-TR算法对该轨迹段进行简化。将每个轨迹段的简化结果合并、得到移动对象的轨迹简化结果，如图2所示。图2为本发明所述基于特征选择的移动对象轨迹简化算法示意图；其中，所述移动对象的轨迹T根据轨迹点的速度数据得到轨迹的速度区间，进而得到与速度区间对应的轨迹段sub-T

尽管本发明的内容已经通过上述优选实施例作了详细介绍，但应当认识到上述的描述不应被认为是对本发明的限制。在本领域技术人员阅读了上述内容后，对于本发明的多种修改和替代都将是显而易见的。因此，本发明的保护范围应由所附的权利要求来限定。