基于密度峰值的轨迹聚类算法

基于分割聚类框架的TRACLUS算法是轨迹聚类领域中具有代表性的方法。但TRACLUS在中心线两侧轨迹点偏离较大时，无法找到最优的分割点，同时又依赖于输入参数的精细调整。针对这些不足，该文提出一种新的基于密度峰值的轨迹聚类算法（trajectory clustering based on density peaks, TCDP）。TCDP包含两个步骤，首先，利用提升的基于最小描述长度的分割算法，将轨迹分割为子轨迹。通过引入平行夹边实现前向探测地分割，提高轨迹分割的准确性。其次，基于子轨迹聚类中心具有较高的局部密度并被低密度的子轨迹所围绕，而不同聚类中心之间存在较远距离的思想，实现了基于密度峰值的子轨迹聚类，以此增强算法对输入参数的鲁棒性。TCDP解决了TRACLUS算法的不足。实验结果表明，TCDP具有更好的轨迹聚类效果。

Trajectory clustering algorithm based on density peaks

Trajectory clustering is a useful approach to analyze trajectory data. Numbers of methods have been proposed in this field, of which TRACLUS is a representative trajectory clustering algorithm based on the partition and group framework. However, TRACLUS fails to find the optimal partitioning when trajectory points falling on both side of the center line are far away from the center line and is sensitive to the input parameters. Aiming at those vulnerabilities, a new trajectory clustering algorithm TCDP is proposed in this paper. TCDP is composed of two steps. In the first step, trajectories are partitioned into sub trajectories using the improved MDL partitioning algorithm which is more applicative and has higher precision than the partitioning algorithm used in TRACLUS. In the second step, a new sub trajectories algorithm is proposed. It is based on the idea that sub trajectory centers are surrounded by lower density sub trajectories and far from other sub trajectory centers. The new sub trajectories algorithm is robust to input factor. TCDP resolves the defects TRACLUS having. Meanwhile, the experiment shows TCDP performs better in quality of trajectory clustering.