聚类分析简单例子-PPT.ppt

聚类分析简单例子聚类分析简单例子二、类间距离与系统聚类法二、类间距离与系统聚类法n在进行系统聚类之前，我们首先要定义类与类之间的距离，在进行系统聚类之前，我们首先要定义类与类之间的距离，由类间距离定义的不同产生了不同的系统聚类法。常用的类由类间距离定义的不同产生了不同的系统聚类法。常用的类间距离定义有间距离定义有8种之多，与之相应的系统聚类法也有种之多，与之相应的系统聚类法也有8种，分种，分别为最短距离法、最长距离法、中间距离法、重心法、类平别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和法。它们的归类均法、可变类平均法、可变法和离差平方和法。它们的归类步骤基本上是一致的，主要差异是类间距离的计算方法不同。步骤基本上是一致的，主要差异是类间距离的计算方法不同。以下用以下用dij表示样品表示样品Xi与与Xj之间距离，用之间距离，用Dij表示类表示类Gi与与Gj之间的距离。之间的距离。1.最短距离法最短距离法定义类定义类Gi与与Gj之间的距离为两类最近样品的距离，即为之间的距离为两类最近样品的距离，即为 (5.11)设设Gk类与合并成一个新类记为类与合并成一个新类记为Gr，则任一类与的距离为，则任一类与的距离为 (5.12)n最短距离法进行聚类分析的步骤如下：最短距离法进行聚类分析的步骤如下：（1）定义样品之间距离，计算样品的两两距离，得一距离）定义样品之间距离，计算样品的两两距离，得一距离 阵记为阵记为D（0），开始每个样品自成一类，显然这时，开始每个样品自成一类，显然这时Dij=dij。（2）找出距离最小元素，设为）找出距离最小元素，设为Dpq，则将，则将Gp和和Gq合并成一个合并成一个 新类，记为新类，记为Gr，即，即Gr=Gp，Gq。（3）按（）按（5.12）计算新类与其它类的距离。）计算新类与其它类的距离。（4）重复（）重复（2）、（）、（3）两步，直到所有元素。并成一类为）两步，直到所有元素。并成一类为 止。如果某一步距离最小的元素不止一个，则对应这些止。如果某一步距离最小的元素不止一个，则对应这些 最小元素的类可以同时合并。最小元素的类可以同时合并。n【例例5.1】设有六个样品，每个只测量一个指标，分别是设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。，试用最短距离法将它们分类。（1）样品采用绝对值距离，计算样品间的距离阵）样品采用绝对值距离，计算样品间的距离阵D（0），见，见表表5.1表表5.1（2）D（0）中最小的元素是中最小的元素是D12D561，于是将，于是将G1和和G2合合并成并成G7，G5和和G6合并成合并成G8，并利用（，并利用（5.12）式计算新类与其）式计算新类与其它类的距离它类的距离D（1），见表，见表5.2表表5.2 （3）在）在D（1）中最小值是中最小值是D34D482，由于，由于G4与与G3合并，合并，又与又与G8合并，因此合并，因此G3、G4、G8合并成一个新类合并成一个新类G9，其与其，其与其它类的距离它类的距离D（2），见表，见表5.3表表5.3 大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点（4）最后将）最后将G7和和G9合并成合并成G10，这时所有的六个样品聚为一，这时所有的六个样品聚为一类，其过程终止。类，其过程终止。上述聚类的可视化过程见图上述聚类的可视化过程见图5.1所示，横坐标的刻度表示并类所示，横坐标的刻度表示并类的距离。这里我们应该注意，聚类的个数要以实际情况所定，的距离。这里我们应该注意，聚类的个数要以实际情况所定，其详细内容将在后面讨论。其详细内容将在后面讨论。图图5.1 最短距离聚类法的过程最短距离聚类法的过程n再找距离最小两类并类，直至所有的样品全归为一类为止。再找距离最小两类并类，直至所有的样品全归为一类为止。可以看出最长距离法与最短距离法只有两点不同：可以看出最长距离法与最短距离法只有两点不同：一是类与类之间的距离定义不同；一是类与类之间的距离定义不同；另一是计算新类与其它类的距离所用的公式不同。另一是计算新类与其它类的距离所用的公式不同。3.中间距离法中间距离法最短、最长距离定义表示都是极端情况，我们定义类间距离最短、最长距离定义表示都是极端情况，我们定义类间距离可以既不采用两类之间最近的距离也不采用两类之间最远的可以既不采用两类之间最近的距离也不采用两类之间最远的距离，而是采用介于两者之间的距离，称为中间距离法。距离，而是采用介于两者之间的距离，称为中间距离法。中间距离将类中间距离将类Gp与与Gq类合并为类类合并为类Gr，则任意的类，则任意的类Gk和和Gr的距的距离公式为离公式为 (14 0)(5.15)设设DkrDkp，如果采用最短距离法，则，如果采用最短距离法，则Dkr=Dkp，如果采用，如果采用最长距离法，则最长距离法，则Dkr=Dkq。如图。如图5.2所示，所示，(5.15)式就是取它式就是取它们（最长距离与最短距离）的中间一点作为计算们（最长距离与最短距离）的中间一点作为计算Dkr的根据。的根据。n特别当特别当 =14，它表示取中间点算距离，公式为，它表示取中间点算距离，公式为 (5.16)图图5.2 中间距离法中间距离法n n n n【例例5.2】针对例针对例5.1的数据，试用重心法将它们聚类。的数据，试用重心法将它们聚类。（1）样品采用欧氏距离，计算样品间的平方距离阵）样品采用欧氏距离，计算样品间的平方距离阵D2（0），见，见表表5.4所示。所示。表表5.4（2）D2（0）中最小的元素是中最小的元素是D212D2561，于是将，于是将G1和和G2合合并成并成G7，G5和和G6合并成合并成G8，并利用（，并利用（5.18）式计算新类与）式计算新类与其它类的距离得到距离阵其它类的距离得到距离阵D2（1），见表，见表5.5：其中，其中，其它结果类似可以求得其它结果类似可以求得（3）在）在D2（1）中最小值是中最小值是D2344，那么，那么G3与与G4合并一个新合并一个新类类G9，其与与其它类的距离，其与与其它类的距离D2（2），见表，见表5.6：表表5.6（4）在中最小值是）在中最小值是12.5，那么与合并一个新类，其与与，那么与合并一个新类，其与与其它类的距离，见表其它类的距离，见表5.7：表表5.7（5）最后将）最后将G7和和G10合并成合并成G11，这时所有的六个样品聚为一类，这时所有的六个样品聚为一类，其过程终止。其过程终止。上述重心法聚类的可视化过程见图上述重心法聚类的可视化过程见图5.3所示，横坐标的刻度表所示，横坐标的刻度表示并类的距离。示并类的距离。图图5.3 重心聚类法的过程重心聚类法的过程6.可变类平均法可变类平均法由于类平均法中没有反映出由于类平均法中没有反映出Gp和和Gq之间的距离之间的距离Dpq的影响，的影响，因此将类平均法进一步推广，如果将因此将类平均法进一步推广，如果将Gp和和Gq合并为新类合并为新类Gr，类，类Gk与新并类与新并类Gr的距离公式为：的距离公式为：（5.22）其中其中 是可变的且是可变的且 1，称这种系统聚类法为可变类平均法。，称这种系统聚类法为可变类平均法。8.离差平方和法离差平方和法该方法是该方法是Ward提出来的，所以又称为提出来的，所以又称为Ward法。该方法的基法。该方法的基本思想来自于方差分析，如果分类正确，同类样品的离差平本思想来自于方差分析，如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。具体做法是先将方和应当较小，类与类的离差平方和较大。具体做法是先将n个样品各自成一类，然后每次缩小一类，每缩小一类，离个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使方差增加最小的两类合并，直到差平方和就要增大，选择使方差增加最小的两类合并，直到所有的样品归为一类为止。所有的样品归为一类为止。设将设将n个样品分成个样品分成k类类G1，G2，Gk，用，用Xit表示表示Gt中的第中的第I个样品，个样品，nt表示表示Gt中样品的个数，中样品的个数，是是Gt的重心，则的重心，则Gt的样品的样品离差平方和为离差平方和为n n n这种系统聚类法称为离差平方和法或这种系统聚类法称为离差平方和法或Ward方法。下面论证方法。下面论证离差平方和法的距离递推（离差平方和法的距离递推（5.26）式。）式。n由于由于n 三、类间距离的统一性三、类间距离的统一性n上述八种系统聚类法的步骤完全一样，只是距离的递推公式上述八种系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯（不同。兰斯（Lance）和威廉姆斯（）和威廉姆斯（Williams）于）于1967年给年给出了一个统一的公式。出了一个统一的公式。(5.28)其中其中ap、aq、是参数，不同的系统聚类法，它们取不是参数，不同的系统聚类法，它们取不同的数，详见表同的数，详见表5.8。n这里应该注意，不同的聚类方法结果不一定完全相同，一般这里应该注意，不同的聚类方法结果不一定完全相同，一般只是大致相似。如果有很大的差异，则应该仔细考查，找到只是大致相似。如果有很大的差异，则应该仔细考查，找到问题所在；另外，可将聚类结果与实际问题对照，看哪一个问题所在；另外，可将聚类结果与实际问题对照，看哪一个结果更符合经验。结果更符合经验。表表5.8 系统聚类法参数表系统聚类法参数表n【例例5.3】假定我们对假定我们对A、B、C、D四个样品分别测量两个变四个样品分别测量两个变量和得到结果见表量和得到结果见表5.9。试将以上的样品聚成两类。试将以上的样品聚成两类。表表5.9 样品测量结果样品测量结果动态聚类法动态聚类法第一步：按要求取第一步：按要求取K=2，为了实施均值法聚类，我们将这些，为了实施均值法聚类，我们将这些样品随意分成两类，比如（样品随意分成两类，比如（A、B）和（）和（C、D），然后计算），然后计算这两个聚类的中心坐标，见表这两个聚类的中心坐标，见表5.10所示。所示。表表5.10中的中心坐标是通过原始数据计算得来的，比如（中的中心坐标是通过原始数据计算得来的，比如（A、B）类的，）类的，等等。等等。表表5.10 中心坐标中心坐标第二步：计算某个样品到各类中心的欧氏平方距离，然后将第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类到两个类的平方距离：的平方距离：由于由于A到（到（A、B）的距离小于到（）的距离小于到（C、D）的距离，因此）的距离，因此A不不用重新分配。计算用重新分配。计算B到两类的平方距离：到两类的平方距离：n由于由于B到（到（A、B）的距离大于到（）的距离大于到（C、D）的距离，因此）的距离，因此B要要分配给（分配给（C、D）类，得到新的聚类是（）类，得到新的聚类是（A）和（）和（B、C、D）。）。更新中心坐标如表更新中心坐标如表5.11所示。所示。表表5.11 更新后的中心坐标更新后的中心坐标