基于最小生成树的密度聚类算法研究

来源：计算机技术与发展杂志2022年第02期北京时间：

作者：王诚;高兴东

摘要：传统 DBSCAN 算法对密度分布不均匀的不平衡数据集的聚类效果并不理想,同时传统算法的聚类结果对邻域半径(Eps) 以及核心点阈值( MinPts) 敏感。 针对以上问题,改进了传统算法,提出了一种基于最小生成树的密度聚类算法(MST-DBSCAN) 。 由于对象之间的距离对聚类结果影响较大,为了更好地表示对象之间的距离特性,首先使用相互可达距离(mutual reachability distance)代替传统算法中的欧氏距离,表示数据集中对象与对象之间的距离,解决因密度分布不均匀导致效果不佳的问题;为了建立对象与对象之间的联系,同时保留对象之间的距离特性,引用 Prim 算法对数据集中的所有对象构建最小生成树;其次根据指定的簇的数目及最小簇对象数数目参数对得到的最小生成树进行剪枝;根据剪枝的结果,将剪枝后的各个部分进行聚类。 在公开的 UCI 数据集上的实验结果表明,提出的 MST - DBSCAN 算法与现有DBSCAN、OPTICS、KANN-DBSCAN 算法相比,在密度分布不均匀的数据集上聚类效果有所提升并且较原有传统算法有较高的聚类准确性。

关键词：DBSCAN;相互可达距离;密度聚类;最小生成树;不平衡数据集