系统聚类的方法.ppt

聚类分析,1,聚类分析,一聚类分析的定义,二系统聚类的基本思想,三八种系统聚类方法,四类间距离的统一性,一、聚类分析的定义,“物以类聚，人以群分”。对事物进行分类，是人们认识事物的出发点，也是人们认识世界的一种重要方法。因此，分类学已成为人们认识世界的一门基础科学。,聚类分析就是分析如何对样品（或变量）进行量化分类的问题。通常聚类分析分为Q型聚类和R型聚类。Q型聚类是对样品进行分类处理，R型聚类是对变量进行分类处理。,二、系统聚类的基本思想,系统聚类的基本思想是：距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中。,系统聚类法是诸聚类分析方法中使用最多的一种，按下列步骤进行：,计算n个样品两两之间的距离，构成距离矩阵,合并距离最近的两类为一新类,计算新类与当前各类的距离。再合并、计算，直至只有一类为止,画聚类图，解释,将n个样品各作为一类,三、八种系统聚类方法,在进行系统聚类之前，我们首先要定义类与类之间的距离，由类间距离定义的不同产生了不同的系统聚类法。常用的类间距离定义有8种之多，与之相应的系统聚类法也有8种，分别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和法。它们的归类步骤基本上是一致的，主要差异是类间距离的计算方法不同。以下用dij表示样品Xi与Xj之间距离，用Dij表示类Gi与Gj之间的距离。,1.最短距离法,定义类与之间的距离为两类最近样品的距离，即为(1)设类与合并成一个新类记为，则任一类与的距离为(2),最短距离法进行聚类分析的步骤如下：（1）定义样品之间距离，计算样品的两两距离，得一距离阵记为D（0），开始每个样品自成一类，显然这时Dij=dij。（2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个新类，记为Gr，即Gr=Gp，Gq。（3）按（5.12）计算新类与其它类的距离。（4）重复（2）、（3）两步，直到所有元素。并成一类为止。如果某一步距离最小的元素不止一个，则对应这些最小元素的类可以同时合并。,1.最短距离法,【例1】设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。（1）样品采用绝对值距离，计算样品间的距离阵D（0），见表1,表1,1.最短距离法,（2）D（0）中最小的元素是D12D561，于是将G1和G2合并成G7，G5和G6合并成G8，并利用（5.12）式计算新类与其它类的距离D（1），见表2,表2,1.最短距离法,（3）在D（1）中最小值是D34D482，由于G4与G3合并，又与G8合并，因此G3、G4、G8合并成一个新类G9，其与其它类的距离D（2），见表3,表3,1.最短距离法,（4）最后将G7和G9合并成G10，这时所有的六个样品聚为一类，其过程终止。上述聚类的可视化过程见图1所示，横坐标的刻度表示并类的距离。这里我们应该注意，聚类的个数要以实际情况所定，其详细内容将在后面讨论。,图1最短距离聚类法的过程,1.最短距离法,2.最长距离法,再找距离最小两类并类，直至所有的样品全归为一类为止。可以看出最长距离法与最短距离法只有两点不同：一是类与类之间的距离定义不同；另一是计算新类与其它类的距离所用的公式不同。,2.最长距离法,最短、最长距离定义表示都是极端情况，我们定义类间距离可以既不采用两类之间最近的距离也不采用两类之间最远的距离，而是采用介于两者之间的距离，称为中间距离法。中间距离将类Gp与Gq类合并为类Gr，则任意的类Gk和Gr的距离公式为(140)(5)设DkqDkp，如果采用最短距离法，则Dkr=Dkp，如果采用最长距离法，则Dkr=Dkq。如图2所示，(5)式就是取它们（最长距离与最短距离）的中间一点作为计算Dkr的根据。,3.中间距离法,特别当=14，它表示取中间点算距离，公式为(6),图2中间距离法,3.中间距离法,4.重心法,5.类平均法,6.可变类平均法,由于类平均法中没有反映出Gp和Gq之间的距离Dpq的影响，因此将类平均法进一步推广，如果将Gp和Gq合并为新类Gr，类Gk与新并类Gr的距离公式为：（12）其中是可变的且1，称这种系统聚类法为可变类平均法。,7.可变法,该方法是Ward提出来的，所以又称为Ward法。该方法的基本思想来自于方差分析，如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。具体做法是先将n个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使方差增加最小的两类合并，直到所有的样品归为一类为止。设将n个样品分成k类G1，G2，Gk，用Xit表示Gt中的第I个样品，nt表示Gt中样品的个数，是Gt的重心，则Gt的样品离差平方和为,8.离差平方和法,8.离差平方和法,8.离差平方和法,这种系统聚类法称为离差平方和法或Ward方法。下面论证离差平方和法的距离递推（16）式。,8.离差平方和法,由于,8.离差平方和法,8.离差平方和法,8.离差平方和法,上述八种系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯（Lance）和威廉姆斯（Williams）于1967年给出了一个统一的公式。(18)其中ap、aq、是参数，不同的系统聚类法，它们取不同的数，详见表4。这里应该注意，