欢迎来到天天文库
浏览记录
ID:30381557
大小:92.16 KB
页数:16页
时间:2018-12-29
《《转载层次聚类》word版》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、转载层次聚类层次聚类算法HierarchicalClusteringAlgorithms基本工作原理给定要聚类的N的对象以及N*N的距离矩阵(或者是相似性矩阵),层次式聚类方法的基本步骤(参看S.C.Johnsonin1967)如下:1.将每个对象归为一类,共得到N类,每类仅包含一个对象.类与类之间的距离就是它们所包含的对象之间的距离.2.找到最接近的两个类并合并成一类,于是总的类数少了一个.3.重新计算新的类与所有旧类之间的距离.4.重复第2步和第3步,直到最后合并成一个类为止(此类包含了N个对
2、象).根据步骤3的不同,可将层次式聚类方法分为几类:single-linkage,complete-linkage以及average-linkage聚类方法等.single-linkage聚类法(也称connectedness或minimum方法):类间距离等于两类对象之间的最小距离,若用相似度衡量,则是各类中的任一对象与另一类中任一对象的最大相似度。complete-linkage聚类法(也称diameter或maximum方法):组间距离等于两组对象之间的最大距离。average-linkag
3、e聚类法:组间距离等于两组对象之间的平均距离。average-link聚类的一个变种是R.D'Andrade(1978)的UCLUS方法,它使用的是median距离,在受异常数据对象的影响方面,它要比平均距离表现更佳一些.这种层次聚类称为"凝聚"法,由于它迭代合并所有分类。也有一种"划分"层次聚类法,与"凝聚"相反,它先将所有对象放在同一类中,并不断划分成更小的类,划分法一般很少使用。这两个网页特别值得一看。讲的非常好。这些天研究了一下层次聚类,偶尔发现了这个网址。下面是其他网页的一些关于层次聚类
4、的内容。参考一下层次聚类方法是不可逆的,也就是说,当通过凝聚式的方法将两组合并后,无法通过分裂式的办法再将其分离到之前的状态,反之亦然。另外,层次聚类过程中调查者必须决定聚类在什么时候停止,以得到某个数量的分类。最后,必须记住,在不必要的情况下应该小心使用层次聚类方法。最好用于有潜在层次结构的数据上。凝聚式方法是层次聚类中被广泛使用的方法。过程中,会产生一系列的分划:最初的是n个单成员的类,最后的划分是一个包含全部个体的单个类。凝聚式聚类有很多方法,但基本的操作是相似的,在每一步中,将距离最近的类
5、或者个体融合成一个类。方法之间的差异只是由不同的个体和组之间,或组与组之间的距离的计算方法而带来的。下面介绍一些常用的方法。单连锁(singlelinkage),又称最近邻(nearestneighbour)方法。这个方法使用数据的相似度矩阵或距离矩阵,定义类间距离为两类之间数据的最小距离。这个方法不考虑类结构。可能产生散乱的分类,特别是在大数据集的情况下。因为它可以产生chaining现象,当两类之间出现中间点的时候,这两类很有可能会被这个方法合成一类。单连锁也可以用于分裂式聚类,用来分开最近邻
6、距离最远的两组。全连锁(completelinkage),又称最远邻(furthestneightbour)方法。同样从相似度矩阵或距离矩阵出发,但定义距离为两类之间数据的最大距离。同样不考虑到类的结构。倾向于找到一些紧凑的分类。(组)平均连锁(groupaveragelinkage),又称为UPGMA(UnweightedPair-GroupMethodusingtheAverageapproach)。跟前两个方法一样,从相似度矩阵或距离矩阵出发,但定义距离为类间数据两两距离的平均值。这个方法倾
7、向于合并差异小的两个类。(距离)介于单连锁和全连锁之间。它考虑到了类的结构,产生的分类具有相对的鲁棒性。质心连锁(centroidlinkage),又称为UPGMC(UnweightedPaire-GroupMethodusingCentroidapproach)。不同于前面的方法,它从距离矩阵和原始数据出发,一般定义距离为平方欧几里得距离(可以使用其他距离测度方法,但是可能会对缺少原始数据的阐释,比如"质心"的概念),此距离为个体与组的质心(所有成员的原始数据均值),或组与组的质心距离。(待补充
8、)中值连锁(medianlinkage),又称为WPGMC(WeightedPair-GroupMethodusingCentroidapproach。跟前面的UPGMC不同的是,在计算组的质心时,将合成该组的两部分(组组,个体和组?)按照相同的权重计算,也就是说算出的质心实际上是组成该组的两部分的质心的均值。(待补充)Ward′smethod,又称离差平方和法(errorsumofsquarescriterion)。这个方法倾向于在每一步使组内的离差平方和的增量最小。所谓的离差平
此文档下载收益归作者所有