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

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

(i) Parallel6 (j) Ring2 (k) Ring3 (l) Ring4

(m) Semicircle2 (n) Semicircle3 (o) Semicircle3-2 (p) Semicircle4

(q) Norm4 (r) Norm6 (s) Norm10 (t) Norm12
Fig.6 Spatial distributions of the 20 synthetic datasets (Continued)
图 6 20 个合成数据集的结构分布图(续)

从图 6 中可以看出,这些数据集包含了 5 种不同的结构形状.其中,Circle2、Circle3、Circle4、Circle5 是圆
环状数据集;Parallel3、Parallel4、Parallel4-2、Parallel5、Parallel6 是直线型数据集;Ring2、Ring3、Ring4 是混
合型数据集; Semicircle2、Semicircle3、Semicircle3-2、Semicircle4 是半圆环形数据集;Norm4、Norm6、Norm10、
Norm12 是凸型数据集.图 7 所示为表 3 列出的 6 个真实数据集的三维空间分布图.这 6 个数据集均来自 UCI
机器学习真实数据集.由于除了 Hamberm 数据集外,其余 5 个真实数据集都是高维数据集,需要对它们进行降维
处理,才能在低维空间中展示出来,本文选择目前主流的降维方法 T-SNE(https://lvdmaaten.github.io/tsne)来对高
维数据进行降维处理.
K-means-AHC 算法的有效性评测将从运行时间、准确性和均方差这 3 个方面展开.与此同时,该算法的性
能将和 5 种已有算法,即 K-mean、AHC、DPI-K-means、DC-K-means 和 DPC 的性能进行对比.对于 K-means
算法和 DPI-K-means 算法,由于在通常情况下无法预知目标数据集的类簇数,则这两种算法运行时间的统计方
式为类簇数从 2 到 n 的总运行时间.对于 K-means-AHC 算法和 AHC 算法,其运行时间的统计方式为类簇数由
n 合并到 2 时的运行时间.对于 DC-K-means 和 DPC 算法,由于这两种算法不需要初始化类簇数,而是在运行
结束时直接得到一个由算法计算出的类簇数,因此,对 DC-K-means 和 DPC 算法的对比是直接计算这两种算法
的运行时长.
为了比较的准确性,我们对每种算法在特定数据集上运行 10 次,取 10 次运行结果的平均值和均方差.聚类
结果的准确性通常可以用外部评价指标来衡量,常用的外部评价指标有 F-Measure、Entropy、Purity 等指标,本
文使用 Purity 指标来评价聚类结果的准确性,其定义为

purity   K m i max   m ij   (7)
i 1 m  m i 