改进的DBSCAN密度聚类算法

摘要

针对基于密度的DBSCAN聚类算法对输入参数Eps敏感及算法时间复杂度高的问题,提出了一种基于数据分区和网格聚类相结合的密度聚类算法(PC-DBSCAN).首先,计算每个数据点到其K最近邻域内所有数据点的距离的平均值K-ave,根据每个数据点对应的K-ave值进行单维度聚类来实现数据分区,缓解了算法对全局参数Eps敏感的问题;其次,针对每一个数据分区,把其对应的数据空间划分成以Eps为网格阈值互不相交的网格单元,在确定核心对象时,只需要对数据点所在网格单元及其周围的网格单元进行遍历,避免了遍历数据空间中所有的数据点,优化了核心点的确定方式,降低了时间复杂度;最后,对各数据分区聚类结果进行合并.实验结果表明,改进后的算法是正确和高效的.