高鲁棒性的改进最小生成树聚类算法

沈阳理工大学信息科学与工程学院 李云帆 陈禹铭 文 峰

聚类是一种应用广泛的无监督学习任务，目前的主流聚类方法种类繁多，但在实际应用中需要根据数据分布和具体要求选择聚类方法或设定超参数，十分不便。针对这一问题，提出了一种改进的最小生成树聚类算法，该算法通过充分利用簇规模信息，增强了其抗噪声的能力，同时可以处理不同形状、不同密度的簇。这种方法只需要设定聚类簇数一个超参数，此外还有易于实现、可解释性强等优点。实验结果表明，该改进算法具有更强的鲁棒性，在多种测试集上的聚类效果明显优于其他传统方法，并在图像分割应用上仍有着优秀的表现。

聚类是一种十分常见的无监督学习问题。根据算法思想不同，聚类算法可以分为很多种，如K-Means等基于划分的方法和DBSCAN等基于密度的方法。最小生成树(MST)聚类是一种基于图论的聚类方法，算法等价于使用各节点间的相似度对所有数据构建最小生成树，再将相似度大于阈值的边删去，从而得到一片森林，森林中每颗树视为聚类结果中的一个簇。

经典的最小生成树聚类算法具有分割阈值难以确定、易受离群点干扰、难以处理变密度数据等缺点。针对这些问题，本文提出基于簇规模信息的改进MST聚类算法，该算法只需给定聚类簇数，便可以通过计算并修改各边权重的方式得到自适应抗噪声的聚类结果。最终通过在模拟数据集和图像分割应用上的实验，证明了该方法的有效性。……