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

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

所示.
输入:数据集 D={x 1,x 2,…,x n},类簇数 K 和初始类簇数 K 1;
输出:数据集 D 被分成 K 个类簇,即 C={C 1,C 2,…,C K}.
(1) 从数据集 D 中随机挑选 K 1 个点;
(2) 将选取的 K 1 个点作为数据集 D 的初始划分 C={C 1,C 2,…, C }的类簇中心,即 V={v 1,v 2,…, v };
K 1 K 1
(3) K-means 算法运行过程:
repeat
for i=1,2,…,n do
for j=1,2,…,K 1 do
计算 dist(x i,v j); //dist(x i,v j)表示 D 中的每个点 x i 与类簇中心 v j 的距离.
将 D 中的每个点 x i 分配至与之最近的类簇中心点 v j 所在的类簇 C j 中;
end for;
//计算误差平方和准则函数,判断函数值是否改变.
for j=1,2,…,K 1 do //计算每个类簇的平均值,将其作为新的中心点 v j.
j v   |C l 1 | j l x  | C j | ; //x l 表示类簇 C j 中的样本点的值,|C j|表示类簇 C j 中样本点的数量.
end for;
until 误差准则函数不变,得到划分好的 K 1 个类簇.
(4) AHC 算法运行过程:
repeat
计算得到的 K 1 个类簇中每对类簇 C i,C j 之间的距离 dist(v i,v j).
//dist(v i,v j)表示类簇与类簇之间的最小距离.
将距离最近的两个类簇(设为 C p 和 C q)合并为一个新的类簇 C r,即 C rC pC q,并更新|C||C|1;
until |C|≤K.
Fig.1 Workflow of the K-means-AHC algorithm
图 1 K-means-AHC 算法的工作流程

在图 1 所示的算法中,第(1)步、第(2)步为形成初始类簇的工作过程,而第(3)步和第(4)步则是主要的聚类划
分过程.其中,第(1)步和第(2)步从数据集 D 中随机挑选 K 1 个点作为数据集 D 的 K 1 个类簇的初始类簇中心点.
当 K 1 个类簇的初始类簇中心点确定以后,第(3)步开始运行 K-means 算法.首先,将数据集 D 中的样本点分配到
离其最近的中心点所在的类簇中,该过程计算时间大致为 nK 1 m,其中,m 表示样本点的维数;然后计算误差准
则函数,该步骤的大致计算时间为 nm;再计算每个类簇的均值,将其作为新的中心点,该步骤的计算时间大致为
nm.重复这 3 个步骤,直到误差准则函数值不变为止.假设需要重复 l 次,则整个第(3)步的计算时间大致为
lnK 1 m.第(4)步是 AHC 算法的运行过程,计算每对类簇之间的距离.然后将距离最近的两个类簇合并成一个,
2
重复执行,直到 C 中类簇的数量满足要求的 K 值为止.第(4)步的计算时间大致为(K 1 |C|)n .综合以上分析,整个
2
K-means-AHC 算法的计算时间大致为 lnK 1 m+(K 1 |C|)n .通常情况下,K 1 、m、l 和|C|的值要远远小于 n 的
2
值,故 K-means-AHC 算法的计算时间复杂度为 O(n ).
3 DAS:新的聚类有效性指标

本节首先给出 DAS 指标的定义,然后通过实例来解释该指标的含义及其设计的合理性.
3.1 DAS指标的定义
m
DAS 指标的定义是在欧氏空间下进行的,关于欧氏空间 R 的描述与第 2 节第 2 段相同.与此同时,假设数
据集 D 被 K-mean-AHC 算法划分成 K 个类簇,即 C={C 1 ,C 2 ,...,C K },且其中第 i(i=1,2,...,K)个类簇 C i 包含|C i |个样
本点.
定义 1(簇内紧密度,简称 cd). 本文将由类簇 C i 中所有样本点构成的最小生成树的平均权重定义为类簇 C i
的簇内紧密度,记为 cd(i):
cd(i)=W(C i )/(|C i |1) (1)
其中,W(C i )是类簇 C i 中所有样本点的最小生成树的权重.
定义 2(簇间分离度,简称 sd). 本文将第 i 个类簇中的样本点与其他不同类簇中的样本点之间最小距离的最