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

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


背景技术：

2.移动对象轨迹化简算法的研究是移动对象数据库研究领域的一个重要组成部分，它是伴随着移动电子产品的日益升级和普及而逐步产生和发展起来的，广泛应用于运动目标的跟踪定位、环境监测以及交通管理、基于位置的社交网络(lbsn)，路线导航轨迹推荐，目的地预测和用户的行为分析等许多领域。
3.智能手机、车载导航系统和可穿戴设备中的gps传感器通常产生大量的原始轨迹，增加了数据存储、传输和数据分析的成本。轨迹数据简化压缩是通过减少轨迹数据量以降低存储器空间，从而提高数据传输、存储和处理效率的方法，根据特定的算法减少冗余和存储空间，同时尽可能少地丢失信息或重新组织数据。目前的移动对象轨迹简化算法分为离线简化和在线简化。以往的简化算法中大多依赖轨迹的几何特性(例如轨迹点位置之间的关系,轨迹点方向角度之间的关系)，这些几何特性都可以用轨迹点的相对位置展现出来，而针对移动对象的速度这一重要特征的研究还不是很完善。
4.随着大数据技术在分析应用方面有效性的凸显，怎样设计出能够准确且高效率地存储轨迹的信息的轨迹简化优化算法是近几年重要的研究问题。


技术实现要素：

5.为了能够准确、高效率地存储移动对象的轨迹信息，本发明提供了一种基于特征选择的移动对象轨迹简化算法。
6.本发明提供的基于特征选择的移动对象轨迹简化算法，具体包含以下步骤：
7.s1、采用dbscan密度聚类算法对移动对象的轨迹数据进行处理，得到轨迹的速度区间；
8.s2、根据速度区间对移动对象的轨迹进行划分，得到与速度区对应的轨迹段；
9.s3、对每个轨迹段进行特征分析、选择简化算法，并对该轨迹段的轨迹数据进行简化处理；
10.s4、将每个轨迹段的简化结果合并、得到移动对象的轨迹简化结果。
11.可选的，设定时间间隔、采集移动对象的轨迹点p的数据，形成原始轨迹数据集。
12.可选的，所述轨迹点p的数据包含位置数据和速度数据。
13.可选的，对采集的原始轨迹数据集进行清洗，去除不合理的轨迹点，得到所述移动对象的轨迹t(p1,p2,...,p
n
)，其中，p
n
表示所述移动对象的第n个轨迹点。
14.可选的，步骤s1中，所述dbscan密度聚类算法用于对轨迹点p的速度数据进行处理。
15.可选的，步骤s2中，对所述移动对象的轨迹进行速度特征分析：
16.对于所述移动对象的轨迹t(p1,p2,...,p
n
)，计算相邻两个轨迹点p的平均速度，生成移动对象的速度标签t
v
＝(l1,l2,...,l
n
‑1)，l
n
‑1表示所述移动对象的第n
‑
1个速度值；计算速度标签t
v
的基尼系数，公式如下：
[0017][0018]
其中，n
‑
1表示速度标签t
v
中的速度值总数量；l
i
表示速度标签t
v
中第i个速度值；n(l
i
)表示速度标签t
v
中速度值等于l
i
的速度值个数。
[0019]
可选的，步骤s2中，所述轨迹划分的计算如下：
[0020][0021]
使用最小gini
split
将速度标签t
v
划分为两段和其中，n＝n
‑
1，表示速度标签t
v
中的速度值总数量；n1表示速度标签中的速度值总数量；n2表示速度标签中的速度值总数量；且n1 n2＝n。
[0022]
可选的，步骤s3中，对每个轨迹段进行方向特征分析，具体方法如下：
[0023]
测量轨迹段中每个轨迹点的切斜，与该轨迹段的起始轨迹点和终止轨迹点的连接线的夹角，计算得到该轨迹段的平均角度值，以及对应夹角大于平均角度值的轨迹点数量；
[0024]
当对应夹角大于平均角度值的轨迹点数量超过该轨迹段中轨迹点数量的一半，则该轨迹段的方向变化频繁、并采用angular算法对该轨迹段进行简化；
[0025]
当对应夹角大于平均角度值的轨迹点数量不超过该轨迹段中轨迹点数量的一半，则该轨迹段的方向变化不频繁、并对该轨迹段进行距离特征分析。
[0026]
可选的，所述距离特征分析具体方法如下：
[0027]
在轨迹段的低速区间中，计算相邻两个轨迹点的距离；
[0028]
当相邻两个轨迹点的距离低于5m，则轨迹点密集、并采用平均采用算法对该轨迹段进行简化；
[0029]
当相邻两个轨迹点的距离不低于5m，则轨迹点不密集，并采用td
‑
tr算法对该轨迹段进行简化。
[0030]
可选的，所述低速区间为轨迹段内速度位于0
‑
22km/h的轨迹。
[0031]
与现有技术相比，本发明提供的基于特征选择的移动对象轨迹简化算法将速度特征、方向特征和距离特征相结合、对移动对象进行轨迹简化，实现对运行时间、空间误差、速度误差、sed误差的进一步优化，避免的采用单一算法对移动对象进行整条轨迹进行简化，误差较大的问题。
附图说明
[0032]
图1为本发明所述基于特征选择的移动对象轨迹简化算法流程图；
[0033]
图2为本发明所述基于特征选择的移动对象轨迹简化算法示意图。
具体实施方式
[0034]
以下结合附图，通过详细说明较佳的具体实施例对本发明作进一步介绍。
[0035]
在采用本发明提供的轨迹简化算法处理移动对象轨迹数据之前，首先对移动对象的轨迹点p进行数据，形成原始轨迹数据集。采集的时间间隔可以设置在1
‑
5s；采集的轨迹点p的数据包含位置数据和速度数据。然后对采集的对采集的原始轨迹数据集进行清洗，去除不合理的轨迹点，得到所述移动对象的轨迹t(p1,p2,...,p
n
)，其中，p
n
表示所述移动对象的第n个轨迹点。一般，当采集的轨迹点的速度超过350km/h，则认为该轨迹点上数据不合理，应当去除。
[0036]
图1为本发明所述基于特征选择的移动对象轨迹简化算法流程图。本发明提供的移动对象轨迹简化算法用于对所述移动对象的轨迹t(p1,p2,...,p
n
)进行处理，具体步骤如下。
[0037]
采用dbscan密度聚类算法对移动对象轨迹点p的速度数据进行处理，得到轨迹的速度区间，根据速度区间对移动对象的轨迹进行划分，得到与速度区对应的轨迹段。具体的，对所述移动对象的轨迹进行速度特征分析：对于所述移动对象的轨迹t(p1,p2,...,p
n
)，计算相邻两个轨迹点p的平均速度，生成移动对象的速度标签t
v
＝(l1,l2,...,l
n
‑1)，l
n
‑1表示所述移动对象的第n
‑
1个速度值；计算速度标签t
v
的基尼系数，公式如下：
[0038][0039]
其中，n
‑
1表示速度标签t
v
中的速度值总数量；l
i
表示速度标签t
v
中第i个速度值；n(l
i
)表示速度标签t
v
中速度值等于l
i
的速度值个数。
[0040]
所述轨迹划分的计算如下：
[0041][0042]
使用最小gini
split
将速度标签t
v
划分为两段和其中，n＝n
‑
1，表示速度标签t
v
中的速度值总数量；n1表示速度标签中的速度值总数量；n2表示速度标签中的速度值总数量；且n1 n2＝n。
[0043]
继续对每个轨迹段进行方向特征分析或距离特征分析，并选择相应的简化算法对该轨迹段的轨迹数据进行简化处理。具体的，对每个轨迹段进行方向特征分析，具体方法如下：测量轨迹段中每个轨迹点的切斜，与该轨迹段的起始轨迹点和终止轨迹点的连接线的夹角，计算得到该轨迹段的平均角度值，以及对应夹角大于平均角度值的轨迹点数量；当对应夹角大于平均角度值的轨迹点数量超过该轨迹段中轨迹点数量的一半，则该轨迹段的方向变化频繁、并采用angular算法对该轨迹段进行简化；当对应夹角大于平均角度值的轨迹点数量不超过该轨迹段中轨迹点数量的一半，则该轨迹段的方向变化不频繁、并对该轨迹段进行距离特征分析。
[0044]
所述距离特征分析具体方法如下：在轨迹段的低速区间中，即速度位于0
‑
22km/h的轨迹部分，计算相邻两个轨迹点的距离；当相邻两个轨迹点的距离低于5m，则轨迹点密集、并采用平均采用算法对该轨迹段进行简化；当相邻两个轨迹点的距离不低于5m，则轨迹点不密集，并采用td
‑
tr算法对该轨迹段进行简化。将每个轨迹段的简化结果合并、得到移动对象的轨迹简化结果，如图2所示。图2为本发明所述基于特征选择的移动对象轨迹简化算法示意图；其中，所述移动对象的轨迹t根据轨迹点的速度数据得到轨迹的速度区间，进
而得到与速度区间对应的轨迹段sub
‑
t1，ε为该轨迹段采用的简化算法的阈值，不同的轨迹段的阈值可以不同，最后通过合并(merge)得到简化轨迹simplified trajectoryt'；v1、v2表示对应的轨迹段内部的速度分布；sub
‑
t1、sub
‑
t2表示根据速度v1、v2划分成的轨迹段；ε1表示轨迹段sub
‑
t1对应的阈值，ε2表示轨迹段sub
‑
t2对应的阈值；sub
‑
t1'表示使用阈值ε1的简化轨迹，sub
‑
t2'表示使用阈值ε2的简化轨迹，merge表示将轨迹段的合并，simplified trajectoryt'表示完整的简化轨迹
[0045]
尽管本发明的内容已经通过上述优选实施例作了详细介绍，但应当认识到上述的描述不应被认为是对本发明的限制。在本领域技术人员阅读了上述内容后，对于本发明的多种修改和替代都将是显而易见的。因此，本发明的保护范围应由所附的权利要求来限定。

技术特征：
1.一种基于特征选择的移动对象轨迹简化算法，其特征在于，包含以下步骤：s1、采用dbscan密度聚类算法对移动对象的轨迹数据进行处理，得到轨迹的速度区间；s2、根据速度区间对移动对象的轨迹进行划分，得到与速度区对应的轨迹段；s3、对每个轨迹段进行特征分析、选择简化算法，并对该轨迹段的轨迹数据进行简化处理；s4、将每个轨迹段的简化结果合并、得到移动对象的轨迹简化结果。2.如权利要求1所述的基于特征选择的移动对象轨迹简化算法，其特征在于，设定时间间隔、采集移动对象的轨迹点p的数据，形成原始轨迹数据集。3.如权利要求2所述的基于特征选择的移动对象轨迹简化算法，其特征在于，所述轨迹点p的数据包含位置数据和速度数据。4.如权利要求2所述的基于特征选择的移动对象轨迹简化算法，其特征在于，对采集的原始轨迹数据集进行清洗，去除不合理的轨迹点，得到所述移动对象的轨迹t(p1,p2,...,p
n
)，其中，p
n
表示所述移动对象的第n个轨迹点。5.如权利要求3所述的基于特征选择的移动对象轨迹简化算法，其特征在于，步骤s1中，所述dbscan密度聚类算法用于对轨迹点p的速度数据进行处理。6.如权利要求4所述的基于特征选择的移动对象轨迹简化算法，其特征在于，步骤s2中，对所述移动对象的轨迹进行速度特征分析：对于所述移动对象的轨迹t(p1,p2,...,p
n
)，计算相邻两个轨迹点p的平均速度，生成移动对象的速度标签t
v
＝(l1,l2,...,l
n
‑1)，l
n
‑1表示所述移动对象的第n
‑
1个速度值；计算速度标签t
v
的基尼系数，公式如下：其中，n
‑
1表示速度标签t
v
中的速度值总数量；l
i
表示速度标签t
v
中第i个速度值；n(l
i
)表示速度标签t
v
中速度值等于l
i
的速度值个数。7.如权利要求6所述的基于特征选择的移动对象轨迹简化算法，其特征在于，步骤s2中，所述轨迹划分的计算如下：使用最小gini
split
将速度标签t
v
划分为两段和其中，n＝n
‑
1，表示速度标签t
v
中的速度值总数量；n1表示速度标签中的速度值总数量；n2表示速度标签中的速度值总数量；且n1 n2＝n。8.如权利要求1所述的基于特征选择的移动对象轨迹简化算法，其特征在于，对每个轨迹段进行方向特征分析，具体方法如下：测量轨迹段中每个轨迹点的切斜，与该轨迹段的起始轨迹点和终止轨迹点的连接线的夹角，计算得到该轨迹段的平均角度值，以及对应夹角大于平均角度值的轨迹点数量；当对应夹角大于平均角度值的轨迹点数量超过该轨迹段中轨迹点数量的一半，则该轨迹段的方向变化频繁、并采用angular算法对该轨迹段进行简化；当对应夹角大于平均角度值的轨迹点数量不超过该轨迹段中轨迹点数量的一半，则该
轨迹段的方向变化不频繁、并对该轨迹段进行距离特征分析。9.如权利要求8所述的基于特征选择的移动对象轨迹简化算法，其特征在于，所述距离特征分析具体方法如下：在轨迹段的低速区间中，计算相邻两个轨迹点的距离；当相邻两个轨迹点的距离低于5m，则轨迹点密集、并采用平均采用算法对该轨迹段进行简化；当相邻两个轨迹点的距离不低于5m，则轨迹点不密集，并采用td
‑
tr算法对该轨迹段进行简化。10.如权利要求9所述的基于特征选择的移动对象轨迹简化算法，其特征在于，所述低速区间为轨迹段内速度位于0
‑
22km/h的轨迹。
技术总结
本发明公开了一种基于特征选择的移动对象轨迹简化算法，包含以下步骤：采用DBSCAN密度聚类算法对移动对象的轨迹数据进行处理，得到轨迹的速度区间；根据速度区间对移动对象的轨迹进行划分，得到与速度区对应的轨迹段；对每个轨迹段进行特征分析、选择简化算法，并对该轨迹段的轨迹数据进行简化处理；将每个轨迹段的简化结果合并、得到移动对象的轨迹简化结果。本发明提出的基于特征选择的移动对象轨迹简化算法，先根据速度特征划分轨迹段，然后在轨迹段内进行方向特征判断或距离特征判断，从而选择适合各轨迹段的简化算法，实现执行时间和误差度量的优化，提升简化效果。提升简化效果。提升简化效果。


技术研发人员：任帅帅 杨智应
受保护的技术使用者：上海海事大学
技术研发日：2021.04.26
技术公布日：2021/6/29