俞庆英，赵亚军，叶梓彤，胡 凡，夏 芸

（1.安徽师范大学计算机与信息学院，安徽芜湖 241002；2.安徽师范大学网络与信息安全安徽省重点实验室，安徽芜湖 241002）

0 概述

随着定位、通信和存储技术的快速发展，车辆行驶轨迹数据、用户活动轨迹数据以及飓风轨迹数据等大量移动对象的轨迹数据可被搜集和存储。轨迹数据中包含丰富的时空语义信息，从中可挖掘出众多有价值的信息［1-2］。聚类分析是常用的数据挖掘方法，其被广泛用于图像分析［3］、模式识别［4］、知识发现［5］以及生物信息学［6］等领域。近年来，研究人员针对不同的应用领域提出多种聚类算法，主要包括以BIRCH 为代表的基于层次的聚类算法［7］、以STING为代表的基于网格的聚类算法［8］、以K-means 为代表的基于划分的聚类算法［9-10］，以及以DBSCAN 为代表的基于密度的聚类算法［11-12］。然而上述算法主要用于点数据的聚类，不能直接用于轨迹数据的聚类。

对轨迹数据聚类可获得移动对象的代表性路径，从而掌握其周期性行为规律［13］。由于轨迹数据中包含大量时间、空间和形状等固有特征信息，因此大部分轨迹聚类方法先进行基于轨迹数据对象的相似性度量，再通过改进传统聚类算法来实现轨迹数据聚类。例如，目前使用最广泛的TRACLUS［14］轨迹聚类算法先基于轨迹分段进行相似性度量，再利用传统DBSCAN 算法实现轨迹聚类。DBSCAN 算法可形成任意形状的簇并能有效处理噪声点，但由于该算法在执行过程中会重复遍历整个数据集来搜索某个样本的邻域集合，因此处理大数据集的耗时较长，时间复杂度为O（n2），并需要较大内存和I/O 开销。……