- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
层次聚类可以通过合并(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},
文档评论(0)