Page 123 - 《软件学报》2021年第10期

朱二周 等:一种采用新型聚类方法的最佳类簇数确定算法 3095

其中,m i 为类簇 C i 中所有成员的个数,m ij 为类簇 C i 中的成员属于类簇 C j 的个数,K 是聚类的数目,m 是整个聚类
划分所涉及到的成员个数.本文中,将 Purity 指标的值转化为百分数来进行比较.
均方差((r))定义为
2
 ()r  N (x   r ) / N (8)
i 1 i
其中,N 代表算法运行的次数,x i 表示第 i 次运行的结果,r 表示所有运行结果的平均值.

(a) Column2 (b) Heart (c) German

(d) Iris (e) Haberman (f) Tae

Fig.7 Spatial distributions of the 6 real datasets after dimensionality reduction
图 7 降维后的 6 个真实数据集的结构分布图

表 4 给出了 6 种算法对 20 个合成数据集的处理结果.从表 4 所列数据可以看出,K-means-AHC 算法能够完
全正确地划分这些合成数据集,并在准确率、运行时间和稳定性等方面都有较好的表现.
在准确率方面,K-means-AHC 算法的平均准确率(均为 100%)是 6 种算法中最高的.AHC 算法的准确率与
K-means-AHC 接近.除了 Norm10 数据集以外,AHC 算法能够准确地得到其余 19 个数据集的聚类划分结果.DPC
算法可以得出 13 个数据集的准确聚类结果,对其余 7 个数据集也表现出较好的准确性.而其他 3 种算法均不能
获得很好的聚类划分结果.
在准确率的均方差方面,由于 AHC 算法总是合并相邻最近的类簇,DPI-K-means 和 DC-K-means 算法在初
始中心点的选择机制上都是寻找各自定义的密度最大的点,DPC 算法根据决策图确定中心点,因此这些算法在
每次运行过程中样本点的划分都一致,使得每次运行结果的聚类准确率不变,即准确率的均方差都为 0.虽然
K-means-AHC 算法和 K-means 算法都是随机选取初始中心点,但是 K-means-AHC 算法的稳定性明显比传统的
K-means 算法要好,在大多数情况下运行结果都一致.具体而言,K-means-AHC 算法准确率的均方差除了
Normal10 数据集之外均为 0.
在运行时间方面,DPC 算法的平均耗时最小,但运行时间在稳定性上不如 K-means-AHC 算法.K-means-
AHC 算法的平均耗时在小数据集上的表现稍大于 DPI-K-means 算法和 DC-K-means 算法,但在几个大数据集中,
K-means-AHC 算法的平均耗时要稍小于 DPI-K-means 和 DC-K-means 算法.K-means-AHC 算法的平均耗时也要
稍小于 K-means 算法的平均耗时,并远远小于 AHC 算法的平均耗时.在运行时间的均方差方面,K-means-AHC
算法在绝大多数情况下都表现出最好的稳定性,即耗时的均方差最小.