基于轨迹间时空关联性的数据聚类算法

Data Clustering Algorithm Based on Spatio-temporal Correlation between Trajectories

针对现有轨迹聚类算法中对轨迹之间的时空关联性考虑不足以及全局唯一距离阈值带来的算法的时空复杂度高以及聚类精度低的问题,提出了一种基于轨迹间时空关联性的数据聚类算法(The Data Clustering Algorithm Based on Spatio-temporal Correlation between Trajectories,DSCBT)。该方法主要包含两个阶段,在第一阶段中,首先根据最短停留时间限制和半径r确定初始中心代表点,然后将所在簇的最大距离作为该初始中心代表点对应的半径R,最后根据最短移动时间约束合并相邻的初始中心代表点并调整半径R,得到中心代表点集。第二阶段主要处理新增轨迹数据,首先将轨迹点与中心代表点集进行匹配,删除匹配成功的点产生新轨迹,然后对有聚类价值的新增轨迹执行第一阶段的操作,最后更新中心点集并完成聚类。实验结果表明,该算法能够有效降低算法的时间复杂度并提高聚类精度。

Aiming at the insufficient consideration of the spatio-temporal correlation between tracks in the existing trajectory clustering algorithms,as well as the high spatio-temporal complexity and low clustering accuracy of the algorithms brought about by the global unique distance threshold,a data clustering algorithm based on spatio-temporal correlation between tracks(The Data Clustering Algorithm Based on Spatio-temporal Correlation between Trajectories,DSCBT)is proposed.This method consists of two main stages.In the first stage,the initial center representative point is determined according to the minimum residence time limit and radius r,and then the maximum distance of the cluster is regarded as the radius R corresponding to the initial center representative point.Finally,according to the minimum moving time constraint,the adjacent initial center representative points are merged and the radius R is adjusted to get the center representative point set.In the second stage,the new track data is processed,firstly,the track point is matched with the center representative point set,and the points with successful matching are deleted to generate a new track,and then the first stage operation is performed on the new track with clustering value.Finally,the center point set is updated and the clustering is completed.Experimental results show that the algorithm can effectively reduce the time complexity of the algorithm and improve the clustering accuracy.