Page 230 - 《软件学报》2021年第12期

3894 Journal of Software 软件学报 Vol.32, No.12, December 2021

mutual information,简称 NMI)是广泛用于聚类质量评估的聚类评价指标,用于度量方法结果与标准结果之间的
相似度,其定义如下:
C X C Y ⎛ C ⋅ N ⎞
2 ∑∑
−⋅ C ⋅ log⎜ ⎜ ij ⋅ ⎟ ⎟
ij
i
NMI = i= 1 j= 1 ⎝ CC j ⎠ (10)
C X ⎛ C C Y ⎛ C j ⎞
∑ C ⋅ i log ⎜ i ⎞ ⎟ + C ⋅ ∑ j log ⎜ ⎟
i= 1 ⎝ N ⎠ j= 1 ⎝ N ⎠
其中,N 是数据样本总数;C X 和 C Y 分别是数据集的真实划分和算法聚类结果包含的簇数;C ij 表示同时属于真实
划分簇数 i 和聚类结果簇数 j 的样本数量.NMI 的取值范围为[0,1],其值越大,表示聚类结果与真实结果越匹配.
针对采样质量,本文引入代表点间平均欧式距离(average euclidean distance of representative points,简称
AEDRP)和距离方差(variance of representative points,简称 VRP)以及新设计综合覆盖率(comprehensive coverage
rate,简称 CCR)来评价选取代表点的显著性和覆盖性.代表点间平均欧式距离越大,距离方差越小,说明选取的代
表点的显著性越好.综合覆盖率考虑反映在合理代表点个数下,代表点集对原始数据集的覆盖程度.值越大,说
明选取的代表点的覆盖性越好.其定义如下:
N
− R ∑ ( Idist (:, )j min ≤ d mean )
CCR = e N NR ⋅ , ij ,i∈ , R j ∈ NR (11)
N
NR
其中,N R 是算法划分的类数即代表点数目,N NR 是非代表点数,R 和 NR 分别为代表点集和非代表点集;dist(i,j)是
代表点 i 和非代表点 j 间的欧式距离,dist(:,j) min 是非代表点 j 与所有代表点之间的最小距离;d mean 是整个数据集
中数据点间的平均欧式距离;I(⋅)为指示函数.CCR 值综合考虑代表点占原始数据大小的比例以及代表点对数据
集在一定范围内的覆盖程度,通常情况下,选取更多数量的代表点能够明显提升代表点对数据集的覆盖程度.因
此,在不考虑选取代表点数量的情况下去比较代表点对数据集的覆盖程度是不合理的,所以在评价时引入与代
表点数目相关的系数,可以更为合理地评价代表点对数据集的覆盖程度.当然,在采样问题中,覆盖度是更被看
重的问题,因此在 CCR 评价指标中,代表点数目的影响权重较小,代表点对数据集覆盖程度的影响权重较大.
5.2 数值数据实验分析
在 3 组 UCI 标准数据集和 4 组人工合成数据集上进行代表性样本采样实验,数据集详情见表 2.

Table 2 Descriptions of numerical experimental data sets
表 2 数值型实验数据集描述
数据集 大小 类数 是否平衡
1 Iris 150 3 是
2 wine 178 3 否
3 yeast 1 484 10 否
4 Set 1 200 4 是
5 Set 2 450 3 是
6 Set 3 800 6 否
7 Set 4 1 200 8 是
真实数据集 iris,wine,yeast 来源于 UCI,人工合成数据集 Set 1~Set 4 是随机生成的二维数据集,均符合正态
分布,其样本分布情况如图 3 所示.对每个数据集,依据公式(9)计算任意数据集内样本点间的相似度.4 种算法的
AP 阻尼系数λ设为 0.9,HAP 算法和 ISAP 算法的分区子集大小设为数据规模的 0.2 [23] ,如果子集规模超过 500,
则设为 500.采样选取每个最终簇的一组数据(算法输出的代表点)作为代表点.
在实验过程中,调整 IAPNA 算法参数 pc、ISAP 算法截断参数θ和变动幅度参数δ进行多次实验.参数 pc 在
真实数据集上的数值来源于文献[16],参数θ,δ以及人工数据集上的 pc 综合算法输出的簇数和采样质量选取.最
终实验参数设置见表 3.