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

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

小值定义为该类簇的簇间分离度,记为 sd(i):
sd ( )i  min {min{dist ( ,x x j ) | x  i C j , x  j C j }} (2)
i
C
j
1≤≤ | |, j i 
定义 3(聚类综合度,简称 csd). 本文将第 i 个类簇的簇间分离度和簇内紧密度之差与簇内紧密度和簇间分
离度之和的比值定义为聚类综合度,记为 csd(i):
sdi  ( )i
() cd
csd ()i  (3)
sdi  ()
() cd i
定义 4(平均聚类综合度,简称 E). 本文将所有类簇的聚类综合度的平均值定义为平均聚类综合度,记为
E(K):
()  
EK K csd ( )i K (4)
i 1
定义 5(聚类有效性指标,简称 DAS). 假设数据集 D 被 K-mean-AHC 算法分别划分成 K 和 K+1 个类簇,即
{C 1 ,C 2 ,...,C K }和{C 1 ,C 2 ,...,C K+1 }.其中,{C 1 ,C 2 ,...,C K }是 D 的最优划分,即 D 的聚类划分数量在 K 时形成拐点.本文
将 D 被划分成 K 个类簇的平均聚类综合度 E(K)与将 D 被划分成 K+1 个类簇的平均聚类综合度 E(K+1)的差定
义为衡量聚类效果的聚类有效性指标,记为 DAS(K):
DAS(K)=E(K)E(K+1) (5)
3.2 对DAS的解释
聚类有效性指标主要用于评价聚类算法对数据集的划分结果,而聚类有效性指标大多是通过簇内紧凑性
和簇间分离性的某种组合来构造的.从簇内紧凑性来说,基于距离度量,我们希望一个类簇的样本之间的距离越
小越好.但是考虑到类簇内部的最小距离和最大距离都不具有代表性,而平均距离对一些非凸结构的数据集也
无法适用,因此,本文通过在单个类簇内部构造最小生成树,用最小生成树的平均权重作为这个类簇的簇内紧凑
性的度量.另一方面,从簇间分离性来说,我们希望类簇与类簇之间的距离越大越好.因此,本文将不同类簇中的
样本点之间的最小距离的最小值作为簇间分离性的度量.
以图 2 为例来解释 DAS 的含义及其相关概念.在图 2 中,根据欧氏距离的度量,数据集的所有样本点被划分
成 4 个类簇(A,B,C,D).在每个类簇内部,样本点之间的连线代表着类簇内部的样本点的最小生成树.以类簇 A 为
例,根据定义 1,类簇 A 的簇内紧密度为 cd(A)=(e 1 +e 2 +e 3 +e 4 +e 5 +e 6 )/6.在各个类簇之间,h 1 、h 2 和 h 3 分别是类簇 A
到类簇 C、类簇 D 和类簇 B 之间的最小单链距离.根据定义 2,类簇 A 的簇间分离度为 sd(A)=min{h 1 ,h 2 ,h 3 }.

Fig.2 Distribution of clustering structure for the DAS
图 2 DAS 指标的类簇结构分布图
为了同时考虑簇内紧密度和簇间分离度,本文用 sd 与 cd 的差比上 sd 与 cd 的和作为聚类综合度 csd.在使
sd 和 cd 形成线性组合的同时,csd 也实现无量纲化.由于凝聚层次聚类(AHC)在每一次的迭代过程中总是将相邻
最近的类簇合并到一起,因此对于层次聚类的结果来说,类簇间的距离不会小于类簇内最小生成树的平均值,即