英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
基于凝聚层次聚类的最优聚类数确定方法
摘要
在聚类分析中，确定最佳聚类数对聚类质量至关重要。从样本几何的角度出发，定义了样本聚类离散度和样本聚类综合度两个概念，并设计了新的聚类有效性指标。此外，提出了一种基于凝聚层次聚类(AHC)算法的最优聚类数确定方法。新的索引和方法可以评估由AHC产生的聚类结果，并为多种类型的数据集确定最佳聚类数，例如线性的、流形的、环形的和凸结构的。理论研究和实验结果表明了该指标和方法的有效性和良好性能。
关键词—聚类分析、聚类有效性指数、层次聚类、聚类数量。
I .导言
聚类分析是模式识别和机器学习领域的一个重要研究课题。
聚类是根据一些相似性标准将样本分成许多类，以便同一类中的样本尽可能相似，而不同类中的样本尽可能不同。研究者们提出了许多聚类算法，并得到了广泛的应用。它们可以大致分为两类:分区的和分层的。分区算法处理输入数据，并创建一个分区，将数据分组到集群中。相比之下，分层算法构建了一个称为集群层次结构的嵌套分区集。一般来说，层次聚类算法通过基于树图[1]的聚集或分割方法将数据集分成不同的聚类。聚集聚类从单个聚类开始，通过连续合并聚类获得层次结构，而分裂聚类
聚类从包含所有点的单个聚类开始，并且通过迭代地分割聚类来进行[2]。在分层聚类算法中，凝聚层次聚类(AHC)因其时间复杂度低和计算稳定性好而成为主要的聚类算法之一。分层算法比分区算法能提供更多的聚类结果，但是如何从众多的聚类结果中获得最佳的分区是一个值得研究的课题。因为聚类层次结构的每一层都是由对应于聚类数目的阈值来确定的，所以最优划分问题可以被理解为确定最优聚类数目的问题。已经进行了一些研究来确定分层聚类中的最优聚类数[2]-[9]。古路查嘉等人[2]提出了对扩展划分集方法的搜索以及一种新的聚类有效性指数，被称为文本-独立的最优性和偏好性，以寻找分层聚类中的最佳划分。Nasibov和Kandemir-Cavas [3]将有序加权平均(OWA)算子与分层聚类相结合，以确定聚类之间的距离，然后计算均方根标准差和R平方有效性指数，以评估分层聚类算法的结果。然而，他们没有做足够的研究来调整OWA算子的最佳权重以获得最佳的聚类结果。Chen等人[8]提出了一种分层方法，该方法首先通过扫描数据集获得聚类特征，并聚集生成数据集的分层划分，然后针对不同的划分增量地构造聚类质量曲线，最后使用对应曲线极值的划分来估计对应的最优聚类数。他们指出他们所提出的方法可用于测量非凸结构型数据。
然而，他们没有描述实验数据集的详细分布。Hu等[9]提出了一种新的聚类有效性指标，通过定义聚类结果的紧密性和可分性来确定层次聚类中的最优聚类数。由于论文没有具体说明构建相似矩阵的相似性度量方法，因此我们无法验证实验结果。
基于AHC算法，我们提出了一种新的聚类有效性指标，该指标能够有效地评估线性、流形、环形和凸结构等多种类型数据集的聚类结果。应用新指标，提出了一种确定最优聚类数的方法。理论研究和实验结果表明了该方法的有效性和良好性能。
算法1 AHC
步骤1:一开始，每个数据点自己形成一个簇，即Gi = {}(i = 1，2，...，n)。
步骤2:找出集群中每对对象之间的距离，并构造距离矩阵D = ，其中c是集群的数量。
步骤3:将彼此更接近的簇(假设它们是和)合并成一个新的簇，其元素为 cup; ，并设c = c-1。
步骤4:检查集群的数量。如果类别号c大于所需的簇数，则转到步骤2；否则，执行步骤5。
步骤5:输出聚类结果。
本文的其余部分组织如下。第二节简要介绍了AHC算法。第三节提出了一个新的有效性指数。第四节描述了一种确定最佳聚类数的新算法。第五节给出了合成数据集和真实数据集的实验结果。第六节讨论了如何将该方法扩展到其他聚类算法。最后，在第七节提供出了结论。
二.按照自下而上和自上而下的方法，层次聚类算法可以分为成簇算法和分裂算法。本文主要研究AHC算法。聚集过程从n个单独的簇开始，然后通过连续合并簇形成一个序列。考虑到数据集是{x1，x2，...xn}和是第k个合并过程中的第I个聚类，AHC算法由算法1 [10]组成。
AHC算法有三个主要的距离度量:单向联系、完全联系和平均联系[11]。当单个链接度量用在聚类之间的距离时，AHC算法也被称为最近邻聚类算法。假设我们有n个样本，并试图使用单个链接形成c个簇，计算复杂度如下[12]，[13]。
1)一次性的计算n(n1)个点间距离；时间复杂度为O(n)。
2)将结果放在点间距离表中；空间复杂度为O(n)。
3)遍历完整列表，找到第一次合并的最小距离对，并保留最小距离索引；因此，对于第一凝聚步骤，时间复杂度为O(n(n1))= O(n)。
4)遍历列表中未使用的距离，并在不同的聚类中找到最小的一个，用于任意聚集步骤；时间复杂度为O(n)。
通常，c远远小于n(clt;lt;n)。因此，用单向联系机构，AHC算法的空间复杂性
是O()，AHC算法的全时间复杂度是O()= O()。
在大多数情况下，具有单个链接的AHC算法对于线性、多种要素的、环形的和凸数据是相对稳定和有效的。因此，在我们的实验中，我们使用单一链接度量来进行数据集的聚类分析。
- 一种新的聚类有效性指数聚类结果的评价称为聚类有效性分析。一般来说，为了显示数据集的内部结构，一个好的聚类划分应该使同一聚类中的样本尽可能地相似，而不同聚类中的样本尽可能地不同。从距离度量的角度来看，最优聚类划分是同时最小化簇内距离和最大化簇间距离。在现有的有效性指标中，有许多指标可以分析聚类结果并确定最优聚类数。好的业绩指标主要包括卡林斯基-哈拉巴什指数([14])、戴维斯-博尔丁指数([15])、西尔指数([16)、克尔扎诺夫斯基-赖(吉隆坡)指数([17])、加权内间(温特)指数([18])、[19]。在这些指数中，CH指数、DB指数和KL指数计算作为聚类中心的样本的平均值，这对于非凸结构数据集可能是无效的。Sil指数表示单个样本的聚类有效性，它可能忽略每个聚类中所有样本的共同特征。此外，Wint索引的相似性间和相似性内的定义存在一些缺陷，这对于非凸数据集可能是无效的。由于这些指标的缺陷，很难为非凸结构数据集正确地找到最佳聚类数。为了解决这个问题，我们设计了一个新的聚类有效性指标——紧分离比例指标。CSP指数可以评估由AHC算法产生的聚类结果，并确定线性、流形、环形和凸数据集的最佳聚类数。
A、标准普尔指数的定义及相关概念
假设Dnn是数据集X的距离矩阵，通过使用AHC算法，我们得到数据集X的树形图，即H = {H1，H2，...，Hn}。在树形图中，任何层，如Hk，都包括c簇，每个簇都包含ni样品。我们使用聚类内紧密度来度量同一聚类中样本的相似性，使用聚类间分离来度量不同聚类中样本的相似性。
定义1:假设Hk是由AHC算法产生的树形图的一层，并且有c个聚类{G1，G2，...，Gc}在Hk中，每个簇包含ni样品，i = 1，2，...我们将第I个聚类中所有样本的最小生成树的平均权重作为聚类内紧密度cd(i)，定义如下:
其中，W(Gi)是ith聚类中所有样本的最小生成树的权重。
定义2:假设Hk是由AHC算法产生的树形图的一层，并且有c个聚类{G1，G2，...，Gc}在Hk中，每个簇包含ni样品，i = 1，2，...我们将聚类I中的样本和其他聚类中的样本之间的最小距离的最小值作为聚类间分离sd(i)，其定义如下:
图1。聚类结构分布图。
sd(i) = (2)
其中dist(xi，x j)是集群间样本xi和x j的欧几里德距离，即dist(xi，x j)=|| xi- x j||；|·|代表欧几里德距离。
定义3:假设Hk是由AHC算法产生的树形图的一层，并且有c个聚类{G1，G2，...，Gc}在Hk中，每个簇包含ni样品，i = 1，2，...我们将群I的群间分离和群内紧密度之间的差异作为群分散度sscd(i)，其定义如下:
sscd(i)= sd(i)-cd(i)=
(3)
定义4:假设Hk是由AHC算法产生的树形图的一层，并且有c个聚类{G1，G2，...，Gc}在Hk中，每个簇包含ni样品，i = 1，2。...我们将聚类I的聚类间分离和聚类内紧密度之和作为聚类综合度sacd(i)，其定义如下:
sacd(i) = sd(i) cd(i)= (4)
定义5:假设Hk是由AHC算法产生的树形图的一层，并且有c个聚类{G1，G2，...，Gc}在Hk中，每个簇包含ni样品，i = 1，2。...我们将聚类离散度与聚类综合度之比作为聚类综合指数，定义如下:
CSP(i)
= sscd ( i )/ sacd ( i)
= = (5)
B.综合服务价格指数分析
为了反映数据的簇内紧密性和簇间分离性，我们提出了CSP指数。基于样本的几何结构，CSP指数以一个聚类中的样本为研究对象，分析聚类结果的有效性。为了方便地解释CSP指数和相关概念的含义，我们使用图1的分布图来说明CSP指数。
在图1中，数据集的所有样本分布在三个近似的圆中，并且可以被聚类成三个聚类，由j、I和k表示。我们可以使用AHC算法对数据集进行聚类。我们将数据点视为图1中的节点，并使用边在每个集群中的节点之间形成路径。当使用单个链接度量来测量集群之间的距离时，最近的邻居节点确定两个最近的集群。群集I和群集j的合并对应于在群集I和群集j中最近的一对节点之间添加一条边。因为链接群集的边总是在不同的群集之间，所以生成的图从不具有任何闭环或回路。如果允许它继续，直到所有的簇都被链接，结果是最小生成树[13]。为了更好地解释图1的聚类结构，使用图论的术语，我们给出以下定义和定理，其中G = (V，E)表示具有顶点集V和边集E的图，|V|是顶点数，|E|是边数。
定义6:如果T = (VT，ET)是图G = (V，E)的子树，T是c-近邻最小生成树，当且仅当它满足下列性质，其中c是分枝数。
1)极小性:T是诱导子图G的最小生成树G[]。
2)最近邻:MAX{W(e)|e isin; ET } le; W(c)，其中W(e)是边的权值，W(c)是图g的最小生成树中的第个最大权值
图2。连接分支图。
定理1:假设T = (VT，e T)是图G = (V，E)的最小生成树。对于任何1 le; c le; |V |，我们从T中移除权重值大于W(c)的边，并产生c个连通分支，标记为Tk = (Vk，Ek) (k = 1，2，...，c)。得到的分支Tk是图G的最近邻最小生成树
证明:因为从T中移除的边的权重都大于W(c)，所以最大{W(e)|e isin; Ek } le; W(c)，即Tk满足定义6的最近邻条件。我们需要证明极小性，这可以用矛盾来证明。假设c个连通分支之一不是图G的c-近邻最小生成树，我们将其视为Tp = (Vp，Ep)，它不是最小生成树。诱导子图必须有最小生成树；我们将其视为Tq = (Vp，Eq)，W(Tq ) lt; W(Tp)。为了容易理解符号，我们用图2的图表来说明证明过程。当c连接的分支Tk = (Vk，Ek ) (k = 1，2，...，p，...c)重新连接权重值大于W(c)的C1移除边，生成的生成树T是图g的最小生成树。从图2中，我们可以看到红色虚线连接每个连接的分支并生成最小生成树T。我们设置W(T ) = W(T1) W(T2) ，...， W(Tp) ，...， W(Tc) W，其中Wre表示C1去除边缘的总重量值。然而，W(T1) W(T2) ，...， W(Tp) ，...， W(Tc) Wrsquo;gt;W(T1) W(T2) ，...， W(Tq ) ，...， W(Tc) 表明T不是图G的最小生成树。这与假设T是图G的最小生成树是矛盾的。因此，假设Tp不是图G的c-近邻最小生成树是不成立的。因此，我们证明了每一个c连通分支都是图g的c-近邻最小生成树
定理1表明，在获得数据集的连通加权图的最小生成树T之后，通过从T中去除c-1最大边，我们获得了图G的一组c-近邻最小生成树，即我们获得了c个簇。c-1最大的边是c-1
两个集群之间的最小距离。在图1的聚类结构中，我们显示了数据集中所有样本的最小生成树。如果样本被分成三个聚类，则只需要从最小生成树中移除边AB(聚类i和聚类k之间的最小距离)和边CD(聚类i和聚类j之间的最小距离)。集群j是离集群i最近的集群。如果集群j满足集群间可分性的要求，其他集群也将满足该要求。此外，如果聚类i的样本不能被聚类到聚类i中，聚类j将是它们的最佳选择。因此，对聚类i及其最近邻聚类j的研究具有重要意义。
聚类有效性的标准是使聚类结果达到簇内紧密性和簇间可分性。从簇内紧密度的角度，基于距离度量，我们期望簇I的簇内距离尽可能小。同一聚类中样本的最小距离和最大距离都不具有代表性。通过以上研究，我们知道聚类I中的样本可以组成一个c-近邻最小生成树。使用聚类I中样本的最小生成树的平均权值来度量聚类I的聚类内紧密度是合适的。另一方面，从聚类间可分性的角度来看，我们期望聚类I与其最近邻聚类j之间的聚类间距离尽可能大。将聚类I和聚类j中样本之间的平均距离作为两个聚类的聚类间可分性是不合适的。一般来说，最小簇间距离在簇划分中起着重要作用。因此，我们使用簇I和簇j之间的最小簇间距离e2来度量簇i的簇间可分性。为了考虑这两个因素，我们使用它们的线性组合来使索引函数成为递增函数。我们使用聚类离差度sscd(i)，等于sd(i) (-cd(i))，来评估聚类结果。很明显，sscd(i
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239092]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
