一种基于移动对象时空信息轨迹分段聚类的方法

摘要

本发明公开了一种基于移动对象时空信息轨迹分段聚类的方法，该基于移动对象时空信息轨迹分段聚类的方法包括：引入时间、速度和方向三个属性，并给出他们的相似度计算公式来分析移动对象轨迹内外部结构；首先根据轨迹的空间密度将轨迹划分成若干轨迹段，然后通过计算各轨迹段在空间、时间、速度和方向上的差异来判断轨迹段的相似度，最后，基于第一次聚类结果，将非显著簇中的轨迹段删除或并入邻近的显著簇，使聚类空间形态体现出全局性的移动规律。本发明提高了聚类效果，具有更强的应用价值，采用空间四叉树对轨迹段进行索引，在大规模轨迹数集环境下极大提升聚类效率，可对轨迹进行有效聚类。

主权项

一种基于移动对象时空信息轨迹分段聚类的方法，其特征在于，该基于移动对象时空信息轨迹分段聚类的方法包括以下步骤：第一步，轨迹和轨迹段：定义1轨迹：三维空间中的有序点集称为轨迹，轨迹TR_i定义：TR_i＝{p₁,p₂,…,p_k}，其中p_k＝{x_k,y_k,t_k}，分别代表该点的二维空间坐标和采用时间；定义2轨迹段：为TR_i内连续的部分三维点集，如：SubTrajectory_s＝{p₁,…,p_k}(1≤s≤k)，k为该轨迹段所属轨迹的采样点总数；第二步，Hausdorff距离：给定两个轨迹段P和Q，使用Hausdorff距离进行相似性测量：$\left\{\begin{array}{c}H(P,Q)=max[h(P,Q),h(Q,P)]\\ h(P,Q)=\underset{p\in P}{\max }\underset{q\in Q}{\min }d(p,q)\\ h(Q,P)=\underset{q\in Q}{\max }\underset{p\in P}{\min }d(q,p)\end{array}\right.$其中，d(p,q)为点p和q之间某个属性上的距离公式，Hausdorff距离用以量度轨迹段之间的空间和时间差异度；第三步，轨迹段速度：通过如下公式得到每个采样点速度：$v_p=\frac{dis\tan ce\left(p_{-},p\right)+dis\tan ce\left(p,p_{+}\right)}{t_{p_{+}}-t_{p_{-}}}$其中，p_‑为p点之前的相邻采样点，p₊为p点之后的相邻采样点，t_p‑和t_p+分别代表p_‑和p₊的采样时间；第四步，轨迹段方向轨迹段的总体移动方向之间方向差别，运动方向角：其中，(x_s,y_s)为轨迹段起点，(x_e,y_e)为轨迹段终点；第五步，轨迹段邻域：定义3轨迹段L_i的ξ邻域：N_ξ(L_i)：N_ξ(L_i)＝{L_i∈D|d(L_i，L_j)≤λ}；其中，D为所有轨迹段数据集合，轨迹段领域用以在DBSCAN轨迹密度聚类中，判断每个轨迹段的当前空间密度，进而将空间密度较大的轨迹段聚为同一组；第六步，轨迹分割；通过采样点在某个时间段内的速度变化来分割轨迹；定义4断点：假设存在一轨迹段,位于轨迹段上的任何两点之间的距离不超过阈值ε,并且这段子轨迹的采样点数s大于阈值Ε，则将这段子轨迹中的第[s/2]个点设置为断点，同时将位于这段子轨迹上其余的点删除；如果一条轨迹上有t个断点，则轨迹被分割为t+1个轨迹段；第七步，轨迹段相似性比较：轨迹段之间的相似性通过轨迹段之间的差异度获取，包括：空间差异度、时间差异度、方向差异度和速度差异度；第八步，VOC‑TC算法：对轨迹进行分割后，再利用DBSCAN密度算法，采用距离公式，对轨迹段进行聚类，设聚类簇C中包含的轨迹数目为簇基数n_cb，簇基数n_b与聚类中轨迹段数目n_c之比为簇显著度n_cs，给定阈值τ和γ，进行如下定义：定义5显著簇：C_sig＝{C|C∈O∩n_cb＞τ∩n_cs＞γ}，其中，O为第一次聚类的结果集，即簇基数n_b高于τ且簇显著度n_s高于γ聚类称为显著簇；定义6非显著簇：其中，O_sig为显著簇集合，即显著簇之外的聚类都为非显著簇；进行第二次聚类，将第一次聚类中非显著簇删除，同时将该其中包含的轨迹段归并到离其最小距离小于阈值μ且包含同一条轨迹的聚类中，最终获取那些能反映主题变化的显著簇，非显著簇的轨迹段归并到其他簇不会改变这些簇中的轨迹数量。