一种基于自适应网格划分和决策图的聚类算法研究

摘要

为了减少大规模数据集在聚类过程中的计算复杂度和运行时间,本文提出了一种基于自适应网格划分和决策图的聚类算法AGPCA.首先,采用相对熵自适应划分数据空间,形成明显的稀疏网格和稠密网格.将网格作为聚类对象,降低以点为对象之间的距离计算复杂度.之后,依据决策图思想确定簇心网格对象,并通过Kd树完成邻接网格的查找和合并以实现聚类.以多个标准数据集和真实的出租车GPS轨迹数据作为测试对象,并与现有一些先进的聚类算法进行对比实验.实验结果表明所提算法结合了网格划分和局部距离判断的优点,具有较高的准确性和运行效率.