聚类分析简单例子ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,一、系统聚类的基本思想,系统聚类的基本思想是：距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中。系统聚类过程是：假设总共有,n,个样品（或变量），第一步将每个样品（或变量）独自聚成一类，共有,n,类；第二步根据所确定的样品（或变量）“距离”公式，把距离较近的两个样品（或变量）聚合为一类，其它的样品（或变量）仍各自聚为一类，共聚成,n,1,类；第三步将“距离”最近的两个类进一步聚成一类，共聚成,n,2,类；,，以上步骤一直进行下去，最后将所有的样品（或变量）全聚成一类。为了直观地反映以上的系统聚类过程，可以把整个分类系统画成一张谱系图。所以有时系统聚类也称为谱系分析。除系统聚类法外，还有有序聚类法、动态聚类法、图论聚类法、模糊聚类法等，限于篇幅，我们只介绍系统聚类方法。,一、系统聚类的基本思想系统聚类的基本思想是：距离相近的样品（,二、类间距离与系统聚类法,在进行系统聚类之前，我们首先要定义类与类之间的距离，由类间距离定义的不同产生了不同的系统聚类法。常用的类间距离定义有,8,种之多，与之相应的系统聚类法也有,8,种，分别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和法。它们的归类步骤基本上是一致的，主要差异是类间距离的计算方法不同。以下用,d,ij,表示样品,X,i,与,X,j,之间距离，用,D,ij,表示类,G,i,与,G,j,之间的距离。,二、类间距离与系统聚类法在进行系统聚类之前，我们首先要定义类,1.,最短距离法,定义类,Gi,与,Gj,之间的距离为两类最近样品的距离，即为,(5.11),设,Gk,类与合并成一个新类记为,Gr,，则任一类与的距离为,(5.12),1.最短距离法,最短距离法进行聚类分析的步骤如下：,（,1,）定义样品之间距离，计算样品的两两距离，得一距离,阵记为,D,（,0,）,，开始每个样品自成一类，显然这时,D,ij,=,d,ij,。,（,2,）找出距离最小元素，设为,D,pq,，则将,G,p,和,G,q,合并成一个,新类，记为,G,r,，即,G,r,=,G,p,，,G,q,。,（,3,）按（,5.12,）计算新类与其它类的距离。,（,4,）重复（,2,）、（,3,）两步，直到所有元素。并成一类为,止。如果某一步距离最小的元素不止一个，则对应这些,最小元素的类可以同时合并。,最短距离法进行聚类分析的步骤如下：,【,例,5.1】,设有六个样品，每个只测量一个指标，分别是,1,，,2,，,5,，,7,，,9,，,10,，试用最短距离法将它们分类。,（,1,）样品采用绝对值距离，计算样品间的距离阵,D,（,0,）,，见表,5.1,表,5.1,【例5.1】设有六个样品，每个只测量一个指标，分别是1，2，,（,2,）,D,（,0,）,中最小的元素是,D,12,D,56,1,，于是将,G,1,和,G,2,合,并成,G,7,，,G,5,和,G,6,合并成,G,8,，并利用（,5.12,）式计算新类与其,它类的距离,D,（,1,）,，见表,5.2,表,5.2,（2）D（0）中最小的元素是D12D561，于是将G1,（,3,）在,D,（,1,）,中最小值是,D,34,D,48,2,，由于,G,4,与,G,3,合并，,又与,G,8,合并，因此,G,3,、,G,4,、,G,8,合并成一个新类,G,9,，其与其,它类的距离,D,（,2,）,，见表,5.3,表,5.3,（3）在D（1）中最小值是D34D482，由于G4与G,（,4,）最后将,G,7,和,G,9,合并成,G,10,，这时所有的六个样品聚为一类，其过程终止。,上述聚类的可视化过程见图,5.1,所示，横坐标的刻度表示并类的距离。这里我们应该注意，聚类的个数要以实际情况所定，其详细内容将在后面讨论。,图,5.1,最短距离聚类法的过程,（4）最后将G7和G9合并成G10，这时所有的六个样品聚为,聚类分析简单例子ppt课件,再找距离最小两类并类，直至所有的样品全归为一类为止。可以看出最长距离法与最短距离法只有两点不同：,一是类与类之间的距离定义不同；,另一是计算新类与其它类的距离所用的公式不同。,聚类分析简单例子ppt课件,3.,中间距离法,最短、最长距离定义表示都是极端情况，我们定义类间距离可以既不采用两类之间最近的距离也不采用两类之间最远的距离，而是采用介于两者之间的距离，称为中间距离法。,中间距离将类,G,p,与,G,q,类合并为类,G,r,，则任意的类,G,k,和,G,r,的距离公式为,(,1,4,0,)(5.15),设,D,kr,D,kp,，如果采用最短距离法，则,D,kr,=,D,kp,，如果采用,最长距离法，则,D,kr,=,D,kq,。如图,5.2,所示，,(5.15),式就是取它们（最长距离与最短距离）的中间一点作为计算,D,kr,的根据。,3.中间距离法,特别当,=,1,4,，它表示取中间点算距离，公式为,(5.16),图,5.2,中间距离法,特别当=14，它表示取中间点算距离，公式为,聚类分析简单例子ppt课件,聚类分析简单例子ppt课件,【,例,5.2】,针对例,5.1,的数据，试用重心法将它们聚类。,（,1,）样品采用欧氏距离，计算样品间的平方距离阵,D,2,（,0,）,，见表,5.4,所示。,表,5.4,【例5.2】针对例5.1的数据，试用重心法将它们聚类。表5.,（,2,）,D,2,（,0,）,中最小的元素是,D,2,12,D,2,56,1,，于是将,G,1,和,G,2,合,并成,G,7,，,G,5,和,G,6,合并成,G,8,，并利用（,5.18,）式计算新类与,其它类的距离得到距离阵,D,2,（,1,）,，见表,5.5,：,其中，,其它结果类似可以求得,（2）D2（0）中最小的元素是D212D2561，于是,（,3,）在,D,2,（,1,）,中最小值是,D,2,34,4,，那么,G,3,与,G,4,合并一个新类,G,9,，其与与其它类的距离,D,2,（,2,）,，见表,5.6,：,表,5.6,（3）在D2（1）中最小值是D2344，那么G3与G4合,（,4,）在中最小值是,12.5,，那么与合并一个新类，其与与,其它类的距离，见表,5.7,：,表,5.7,（4）在中最小值是12.5，那么与合并一个新类，其与与表,（,5,）最后将,G,7,和,G,10,合并成,G,11,，这时所有的六个样品聚为一类，其过程终止。,上述重心法聚类的可视化过程见图,5.3,所示，横坐标的刻度表示并类的距离。,图,5.3,重心聚类法的过程,（5）最后将G7和G10合并成G11，这时所有的六个样品聚为,聚类分析简单例子ppt课件,6.,可变类平均法,由于类平均法中没有反映出,G,p,和,G,q,之间的距离,D,pq,的影响，,因此将类平均法进一步推广，如果将,G,p,和,G,q,合并为新类,G,r,，类,G,k,与新并类,G,r,的距离公式为：,（,5.22,）,其中,是可变的且,1,，称这种系统聚类法为可变类平均法。,6.可变类平均法,聚类分析简单例子ppt课件,8.,离差平方和法,该方法是,Ward,提出来的，所以又称为,Ward,法。该方法的基本思想来自于方差分析，如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。具体做法是先将,n,个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使方差增加最小的两类合并，直到所有的样品归为一类为止。,设将,n,个样品分成,k,类,G,1,，,G,2,，,，,G,k,，用,X,it,表示,G,t,中的第,I,个样品，,n,t,表示,G,t,中样品的个数，是,G,t,的重心，则,G,t,的样品离差平方和为,8.离差平方和法,这种系统聚类法称为离差平方和法或,Ward,方法。下面论证离差平方和法的距离递推（,5.26,）式。,由于,由于,聚类分析简单例子ppt课件,聚类分析简单例子ppt课件,三、类间距离的统一性,上述八种系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯（,Lance,）和威廉姆斯（,Williams,）于,1967,年给出了一个统一的公式。,(5.28),其中,a,p,、,a,q,、,、,是参数，不同的系统聚类法，它们取不,同的数，详见表,5.8,。,这里应该注意，不同的聚类方法结果不一定完全相同，一般只是大致相似。如果有很大的差异，则应该仔细考查，找到问题所在；另外，可将聚类结果与实际问题对照，看哪一个结果更符合经验。,三、类间距离的统一性上述八种系统聚类法的步骤完全一样，只是距,表,5.8,系统聚类法参数表,表5.8 系统聚类法参数表,【,例,5.3】,假定我们对,A,、,B,、,C,、,D,四个样品分别测量两个变量和得到结果见表,5.9,。,试将以上的样品聚成两类。,表,5.9,样品测量结果,动态聚类法,【例5.3】假定我们对A、B、C、D四个样品分别测量两个变量,第一步：按要求取,K=2,，为了实施均值法聚类，我们将这些样品随意分成两类，比如（,A,、,B,）和（,C,、,D,），然后计算这两个聚类的中心坐标，见表,5.10,所示。,表,5.10,中的中心坐标是通过原始数据计算得来的，比如（,A,、,B,）类的，等等。,表,5.10,中心坐标,第一步：按要求取K=2，为了实施均值法聚类，我们将这些样品,第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算,A,到两个类的平方距离：,由于,A,到（,A,、,B,）的距离小于到（,C,、,D,）的距离，因此,A,不用重新分配。计算,B,到两类的平方距离：,第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品,由于,B,到（,A,、,B,）的距离大于到（,C,、,D,）的距离，因此,B,要分配给（,C,、,D,）类，得到新的聚类是（,A,）和（,B,、,C,、,D,）。更新中心坐标如表,5.11,所示。,表,5.11,更新后的中心坐标,由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配,第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，得结果见表,5.12,。,到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得到,K=2,的聚类结果是,A,独自成一类，,B,、,C,、,D,聚成一类。,表,5.12,样品聚类结果,第三步：再次检查每个样品，以决定是否需要重新分类。,