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

3092 Journal of Software 软件学报 Vol.32, No.10, October 2021

时,由于 K-means-AHC 算法在生成初始类簇时不必指定一个准确的 K 值,只需给出一个较大的初始值即可.即由
K-means-AHC 算法生成的初始类簇的数量要比目标数据集 D 的真实划分数量要多.本文中,K 的初始值定为
.
.
2 n 相应地,K-means-AHC 算法生成的初始类簇的数量|C|也为 2 n 其中,C 为生成的目标数据集 D 的初始划
.
分.具体而言,算法的第(1)步确定数据集 D 的初始类簇数量 2 n 第(2)步根据设定的初始类簇数量并利用
K-means-AHC 算法的第(1)步~第(4)步形成数据集 D 的初始划分.在第(3)步,利用 K-means-AHC 算法的第(5)步
逐步合并距离较近的相邻的类簇.与此同时,该步骤还在经验规则(2≤K≤ n )规定的 K 值范围内计算平均聚类
综合度 E(K).第(3)步的循环每进行 1 次,C 中类簇就减少 1 个.第(4)步利用 DAS 的定义计算不同 K 值下的指标
值.第(5)步利用公式(6)来寻找最佳类簇数 K opt .在 K opt 确定以后,数据集 D 的最优划分也相应地被确定下来,即
C={C 1 ,C 2 ,...,C Kopt }.

输入:数据集 D={x 1,x 2,…,x n};
输出:最佳类簇数 K opt 和数据集 D 的最优划分 C={C 1,C 2,...,C Kopt}.
(1) 根据数据集 D 的样本点的个数确定 K 的初始值,即 K=|C|= 2 n
;
(2) 利用 K-means-AHC 算法的第(1)步~第(4)步对数据集 D 进行划分,得到 D 的初始划分,即 C={C 1,C 2,..., C };
2 n
(3) for K= n down to 2 do
输入类簇数 K,对第(2)步得到的|C|个类簇利用 K-means-AHC 算法的第(5)步继续聚类;
根据公式(4),计算类簇数为 K 时的平均综合度 E(K);
|C||C|1;
(4) for K=2 to n do
根据第(3)步得到的 E(K),并利用公式(5)计算不同类簇数下的 DAS(K)指标值;
(5) 根据公式(6),得到最佳类簇数 K opt.

Fig.5 Algorithm of determining the optimal clustering number and optimal clustering partitioning
based on K-means-AHC and DAS
图 5 基于 K-means-AHC 和 DAS 的最佳类簇数和最优划分的确定算法

4 实验结果

表 1 列出了运行本文实验的计算机的配置环境.
Table 1 Experimental configuration details
表 1 实验配置具体环境
CPU Inter(R)Core(TM) i5-8265U@1.60GHz
RAM Samsung LPDDR3 2133MHz(8GB)
Hard Disk WDC PC SN720 SDAPNTW-512G-1127
操作系统 Microsoft Windows 10 家庭版
编程环境 Java8/J2EE

如表 2 和表 3 所示,本文使用 20 个合成数据集(下载自 http://cs.joensuu.fi/sipu/datasets/)和 6 个真实数据集
(下载自 https://archive.ics.uci.edu/ml/datasets.php)来验证 K-means-AHC 算法和 DAS 指标的性能.在这两个表中,
“K 的初始值”是 K-means-AHC 算法中目标数据集初始划分中的类簇的数目.
与此同时,K-means-AHC 算法的性能(运行时间,准确性和均方差)将和 5 种已有算法进行比.这 5 种算法分
别为经典的 K-means 算法、经典的凝聚型层次聚类算法(AHC)、基于密度参数的改进 K-means 算法(DPI-
K-means) [36] 、基于 Density Canopy 的改进 K-means 算法(DC-K-means) [32] 和基于密度峰值的聚类算法(DPC) [25] .
DAS 指标的性能(寻找最佳聚类数)将与当前已有的 5 个经典的聚类有效性指标(CH +[11] 、COP [12] 、DB [13] 、
Dunn +[14] 和 I +[15] )和 2 个最新提出的聚类有效性指标(CSP +[5] 和 STR +[43] )进行对比.在这些指标中,用“+”表示相应
的指标取最大值时得到的最佳类簇数,用“”表示相应的指标取最小值时得到的最佳类簇数.由于本文提出的
+
DAS 指标在指标函数取得最大值时获得最佳类簇数,故它被标记为 DAS .