一种快速移动对象轨道聚类算法

A fast moving objects trajectory clustering algorithm

针对已有轨道聚类(TRACLUS)算法的线段聚类模块需要对划分后的每条线段进行邻域查询的问题,将取样技术引入轨道聚类,提出一种快速移动对象轨道聚类(FTCS)算法。FTCS算法根据基于极大连通子图的合并原理,对核心线段的Eps邻域以及与该Eps邻域相重叠的所有轨道聚类进行合并,避免了TRACLUS算法中核心线段Eps邻域内线段的不必要邻域查询操作。在真实和合成轨道数据集上的大量实验结果表明,FTCS算法显著降低了邻域查询操作次数,在保持TRACLUS算法轨道聚类质量的同时,成倍提高了轨道聚类的时间效率。

Considering that the existing trajectory clustering （TRACLUS） algorithm needs neighborhood query for each line segment after partition, the paper introduces a sampling technique into trajectory clustering and proposes a fast moving objects trajectory clustering （FFCS） algorithm. The FTCS algorithm merges the Eps-neighborhood of core line segments with trajectory clusters that intersect with those Eps-neighborhoods according to the merging principle based on maximum connected subgraph, so it avoids the TRACLUS algorithm＇s unnecessary neighborhood query of line segmems that lie in Epsneighborhood of core line segments. The experimental results on real and synthetic trajectory data demonstrate that the FTCS algorithm reduces the number of neighborhood query remarkably and improves the efficiency of trajectory clustering while keeps the quality of trajectory clustering.