何云斌, 董 恒, 万 静

(哈尔滨理工大学 计算机科学与技术学院, 哈尔滨 150080)

0 引 言

聚类分析是数据挖掘与机器学习中十分重要的一个研究领域，是在没有先验知识的情况下对数据进行分类，并以此分析数据的特点。经典聚类算法K-means算法[1]，简单高效、适用范围广，但是对聚类中心较为敏感，只能识别出球形簇。后来，科研工作者提出基于密度的聚类算法，克服了K-means的缺点，比如Huang等[2]提出了一种基于网格和基于密度的混合聚类算法GRPDBSCAN，该算法可以有效处理噪声点，且运算速率较高，自动生成邻域参数(ε,MinPts)。文[3]针对DPC算法在寻找聚类中心的过程时，计算复杂度高，无法在大规模数据集中应用的问题，提出基于网格筛选的SDPC算法。文[4]提出两步操作的改进K-means算法，将算法在MapReduce模型上进行实现。

这些聚类算法是针对静态型数据的聚类分析，在对静态型数据进行处理时，可以产生比较良好的聚类效果，但是对于移动型数据却难以奏效。这主要因为移动型数据具有移动特性，因此对于移动型数据的聚类处理，传统聚类算法处理效果较差，研究人员转向对移动型数据的聚类研究。

Kalnis[5]基于连续快照模型，提出了Moving Cluster模式，通过使用空间聚类算法对每张时间快照上的移动数据进行聚类处理，然后通过对比连续时间快照上簇之间Jaccard系数是否超过给定阈值，以判断移动数据是否组成Moving Cluster模式。在Moving Cluster基础上，科研工作者进行了改进，提出了Convoy[6]模式，并进一步提出了Swarm[7]模式。文[8]提出在开始先对快照上的移动对象进行聚类，然后在已有的聚类簇上使用KDS[9](动态数据结构)进行维护和修改。……