模式识别课件第五章聚类分析.pptVIP

层次聚类可以通过合并(agglomerative)和分裂(divisive)两种方法实现。合并（自低向上）时，每个样本各成一类，通过合并不同的类，减少类别数目。分裂（自顶向下）时，所有样本先归入一类，通过后续分裂，增加类别数目。下面主要介绍合并的方法。3分级聚类方法基于合并的分级聚类方法对于N个d维未知样本，其算法步骤为：⒈设初始的类别数，X={xi}，i=1，2，…，N。计算类间相似性度量距离矩阵D0，D0是xi间的两两距离矩阵。⒉找出最相似的两类(相似性度量距离最小)，假设为Xh，Xk，将其合并，Xj={Xh，Xk}。5.2.3分级聚类方法⒊计算合并后的类别之间的相似性程度的度量距离矩阵Dl。⒋若给定的类别数是c，，算法结束。①，算法结束。若没有给定类别数c，则②设定阈值T，当两类之间最小距离＞T时，算法结束。----基于合并的分级聚类方法5.2.3分级聚类方法讨论类间相似性度量的方法，假定每个样本之间用欧氏距离：⒈最近距离属于近邻算法，适用于类间分布较散，链状聚合。如果Xj={Xh，Xk}，即Xj是由Xh、Xk合并的。----基于合并的分级聚类方法5.2.3分级聚类方法假设有三种如图5.7所示的两维点集(a)、(b)、(c)。(a)(b)(c)图5.7在用最近距离作为相似性度量进行聚类时，若类别数等于2，则各点集的相应聚类结果如图5.8所示。----基于合并的分级聚类方法5.2.3分级聚类方法5.2.3分级聚类方法(a)(a)----基于合并的分级聚类方法----基于合并的分级聚类方法(b)(b)5.2.3分级聚类方法----基于合并的分级聚类方法(c)(c)5.2.3分级聚类方法图5.7(a)和(b)点集的唯一差别是(b)中出现了两个干扰点。从图5.8(b)中可见，这种相似性度量的缺点是只要在两个各自密集的点集之间存在一些位置互相靠近的点的路径，那么就很可能会把两个密集的点集(本应分属于两类的点集)聚集成一个类。----基于合并的分级聚类方法5.2.3分级聚类方法从图可见，当最终类别数为1时，以最近距离作为相似性度量进行样本点聚类的过程就是一棵最小生成树形成的过程。因此这是一种最小生成树算法。如果给出了最小生成树，可以根据它得到最近邻的聚类结果。只要把最小生成树中长度(距离)最大的一支去掉就得到2类的聚类结果，去掉第二长的分支，数据就分为3类，如此继续下去，就导出了基于分裂的层次聚类方法。----基于合并的分级聚类方法5.2.3分级聚类方法⒉最远距离属于近邻算法，适用于团状集群。取其中dmax最大的一对合并。如Xj={Xh，Xk}，dmax(Xi，Xj)=max{dmax(Xi，Xh)，dmax(Xi，Xk)}----基于合并的分级聚类方法5.2.3分级聚类方法在用最远距离作为相似性度量时，可以把聚类算法看成是产生一个图，图中同一个类的结点都是用棱线联结起来的。用图论的术语来说就是每个类构成一个完备子图。两个类之间的距离现在是由这两个类中相距最远的结点来确定的，对于图5.7的三种点集，当类别数等于2时，其相应的聚类结果见图5.9。----基于合并的分级聚类方法5.2.3分级聚类方法----基于合并的分级聚类方法(a)(a)5.2.3分级聚类方法----基于合并的分级聚类方法5.2.3分级聚类方法(b)从图(b)可见，它防止了两个密集点集通过某个路径聚为一类的可能性。(b)图(c)的结果则说明了这种相似性度量不能检出具有长条形状的聚类。(c)(c)显然，这种度量将使个别的远离点对聚类结果产生十分大的影响。----基于合并的分级聚类方法5.2.3分级聚类方法---基于合并的分级聚类方法5.2.3分级聚类方法均值距离这种相似性度量的效果介于上述两者之间。中心距离适用于球状、近似球状分布。12例5.1：c=2，N=5，n=2，X={x1=(0,1)T，x2=(7,5)T，x3=(2,2)T，x4=(1,1)T，x5=(5,5)T}。试用分级聚类方法进行分类。样本集如图5.10所示。图5.1012345678x1x2011023456x2x19x3x4x5----基于合并的分级聚类方法5.2.3分级聚类方法解：采用。②l=2，，dmean(X2，X5)最小。则X2={X2，X5}={x2，x5}，