《转载层次聚类》word版

《《转载层次聚类》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)。这个方法倾向于在每一步使组内的离差平方和的增量最小。所谓的离差平