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

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

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

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

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

1 算法原理与设计

1.1 基于簇规模信息的修正系数

聚类算法需要克服的一大困难对噪声点的处理。

针对这一问题，本文的方法是引入平衡度修正系数的概念，通过对边权值的修改，来控制聚类效果，避免产生相对容量极小的类。生成树聚类中，每当分割一条边，均会将一个簇划分为两个簇，设两个簇的容量分别为m和n，则平衡度修正系数可以由两者归一化后的调和平均数开根号得到。记m和n的调和平均数为hm(m,n)，平衡度修正系数为Be，则有：

当m与n的和确定时，该函数图像如图1所示。可以看出，该函数具有良好性质，当两个簇容量相差较大时，平衡度修正系数较小，修正后的边权值降低，更不易于被分割，从而在一定程度上自适应地减少噪声干扰。

图1 平衡度修正系数与簇大小的关系

经典最小生成树聚类方法不能处理变密度数据，容易将噪声点单独分为一类。对于这一问题，本文的解决方案是引入正比于当前分割簇容量的权重，称为簇容量修正系数，这使算法更倾向于分割大的簇。设遍历森林时当前边所属簇的容量为C，该树相当于聚类过程中的一个簇，则当前边的簇容量修正系数Se为：

相比于传统最小生成树聚类算法，改进后的算法使用修正后的边权值We

'进行聚类。修正后的边权值由原边权值与两个修正系数相乘求得，即：

1.2 算法流程

算法1：基于簇规模信息的改进最小生成树聚类算法

输入：聚类簇数N，样本点集X

输出：标签列表Labels

步骤：

Step 1：计算样本点集X的相似度矩阵，构造最小生成树。

Step 2：遍历最小生成树的所有边，根据公式(3)计算修正后的边权值，并删去权值最大的边，增加一个簇。

Step 3：若簇数小于设定数，则重复Step 2，直到簇数达到目标数时聚类完毕，得到Labels。

2 实验

2.1 模拟数据集实验

以下是多个不同模拟数据集上对比实验的结果。本文将改进算法同小批量K-Means、DBSCAN、经典最小生成树聚类等算法进行对比实验，其中所有算法均已进行超参数调优，部分算法规定当簇内样本数小于最小簇容量时视为噪声点，实验结果如图2所示，最右侧一列为改进算法结果。

图2 不同数据集上的聚类实验结果

不难看出，改进后的最小生成树聚类算法在众多数据集上均具有非常强的优越性，可以拟合不同形状或不同密度的簇，适应性极强。缺点是速度略微慢于大部分聚类算法，经测试，这主要是由计算样本点相似度矩阵导致的。

2.2 图像分割实验

本文还将改进算法应用到了图像分割领域。对于一张位图，可以将其中每个像素点看作一个五维向量，前两维储存位置信息，后三位储存RGB值（对于四通道图像则为六维）。实际处理时可在两者间适当的加权或进行归一化。经实验验证，改进MST算法具有一定的无监督图像分割能力，分割结果如图3所示。其中左侧为图像原图，右侧为图像分割后的结果。

图3 图像分割实验结果

结论：本文提出了一种基于簇规模信息的改进最小生成树聚类算法，并在模拟数据集和实际应用中进行充分实验。实验结果表明，该方法聚类效果明显优于K-Means，DBSCAN等传统聚类算法，且仅需要设定聚类簇数作为超参数，便可以在聚类中适应不同形状或密度的簇，同时还具备一定抗噪声能力，在多种数据集上与图像分割应用中均具有很好的表现。