转载 层次聚类.doc

转载 层次聚类 层次聚类算法Hierarchical Clustering Algorithms基本工作原理 给定要聚类的N的对象以及N*N的距离矩阵(或者是相似性矩阵),层次式聚类方法的基本步骤(参看S.C.Johnson in 1967)如下： 1.将每个对象归为一类,共得到N类,每类仅包含一个对象.类与类之间的距离就是它们所包含的对象之间的距离. 2.找到最接近的两个类并合并成一类,于是总的类数少了一个. 3.重新计算新的类与所有旧类之间的距离. 4.重复第2步和第3步,直到最后合并成一个类为止(此类包含了N个对象). 根据步骤3的不同,可将层次式聚类方法分为几类：single-linkage,complete-linkage以及average-linkage聚类方法等. single-linkage聚类法(也称connectedness或minimum方法)： 类间距离等于两类对象之间的最小距离，若用相似度衡量，则是各类中的任一对象与另一类中任一对象的最大相似度。complete-linkage聚类法(也称diameter或maximum方法)： 组间距离等于两组对象之间的最大距离。average-linkage聚类法： 组间距离等于两组对象之间的平均距离。 average-link聚类的一个变种是R.DAndrade(1978)的UCLUS方法,它使用的是median距离,在受异常数据对象的影响方面,它要比平均距离表现更佳一些.这种层次聚类称为凝聚法，由于它迭代合并所有分类。也有一种划分层次聚类法，与凝聚相反，它先将所有对象放在同一类中，并不断划分成更小的类，划分法一般很少使用。 这两个网页特别值得一看。讲的非常好。这些天研究了一下层次聚类，偶尔发现了这个网址。下面是其他网页的一些关于层次聚类的内容。参考一下 层次聚类方法是不可逆的，也就是说，当通过凝聚式的方法将两组合并后，无法通过分裂式的办法再将其分离到之前的状态，反之亦然。另外，层次聚类过程中调查者必须决定聚类在什么时候停止，以得到某个数量的分类。最后，必须记住，在不必要的情况下应该小心使用层次聚类方法。最好用于有潜在层次结构的数据上。 凝聚式方法是层次聚类中被广泛使用的方法。过程中，会产生一系列的分划：最初的是n个单成员的类，最后的划分是一个包含全部个体的单个类。凝聚式聚类有很多方法，但基本的操作是相似的，在每一步中，将距离最近的类或者个体融合成一个类。方法之间的差异只是由不同的个体和组之间，或组与组之间的距离的计算方法而带来的。下面介绍一些常用的方法。 单连锁(single linkage)，又称最近邻(nearest neighbour)方法。这个方法使用数据的相似度矩阵或距离矩阵，定义类间距离为两类之间数据的最小距离。这个方法不考虑类结构。可能产生散乱的分类，特别是在大数据集的情况下。因为它可以产生chaining现象，当两类之间出现中间点的时候，这两类很有可能会被这个方法合成一类。单连锁也可以用于分裂式聚类，用来分开最近邻距离最远的两组。 全连锁(complete linkage)，又称最远邻(furthest neightbour)方法。同样从相似度矩阵或距离矩阵出发，但定义距离为两类之间数据的最大距离。同样不考虑到类的结构。倾向于找到一些紧凑的分类。 (组)平均连锁(group average linkage)，又称为UPGMA(Unweighted Pair-Group Methodusing the Average approach)。跟前两个方法一样，从相似度矩阵或距离矩阵出发，但定义距离为类间数据两两距离的平均值。这个方法倾向于合并差异小的两个类。(距离)介于单连锁和全连锁之间。它考虑到了类的结构，产生的分类具有相对的鲁棒性。 质心连锁(centroid linkage)，又称为UPGMC(Unweighted Paire-Group Method using Centroid approach)。不同于前面的方法，它从距离矩阵和原始数据出发，一般定义距离为平方欧几里得距离(可以使用其他距离测度方法，但是可能会对缺少原始数据的阐释，比如质心的概念)，此距离为个体与组的质心(所有成员的原始数据均值)，或组与组的质心距离。(待补充) 中值连锁(median linkage)，又称为WPGMC(Weighted Pair-Group Method using Centroid approach。跟前面的UPGMC不同的是，在计算组的质心时，将合成该组的两部分(组组，个体和组?)按照相同的权重计算，也就是说算出的质心实际上是组成该组的两部分的质心的均值。(待补充) Ward′s method，又称离差平方和法(error sum of square