管理决策模型与方法-聚类分析.ppt

管理决策模型与方法(聚类分析部分),(适用于信息管理与信息系统、工商管理专业 30H)主讲教师：屈春艳,工商管理学院信息管理教研室,第三章 聚类分析,聚类分析，亦称群分析或点群分析，它是研究对样品或指标进行分类的一种多元统计分析方法(它是研究多要素事物分类问题的数量方法)。所谓的类通俗地说就是相似元素的集合。什么是分类？分类是将一个观测对象指定到某一类(组)。,工商管理学院信息管理教研室,分类的问题可以分成两种：一种是对当前所研究的问题已知它的类别数目，且知道各类的特征(如分布规律、或知道来自各类的训练样本)，我们的目的是要将另一些未知类别的个体正确归属于其中某一类，这是判别分析所要解决的问题。另一种是事先不知道研究问题应分成几类，更不知道观测的个体的具体分类情况，我们的目的正是需要通过对观测数据所进行的分析处理，选定一种度量个体接近程度的统计量、确定分类数目、建立一种分类方法，,工商管理学院信息管理教研室,并按亲近程度对观测对象给出合理的分类。这种问题在实际中大量存在，它正是聚类分析所要解决的问题。,工商管理学院信息管理教研室,第一节 聚类分析的方法,聚类分析的职能是建立一种分类方法，其基本原理是，根据样品(本)自身的属性，用数学方法按照某些相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。,工商管理学院信息管理教研室,聚类分析的方法,聚类分析的内容十分丰富，按其聚类的方法可分为以下几种：1、系统聚类法：开始每个对象自成一类，然后每次将最相似的两类合并，合并后重新计算新类与其它类的距离或相近性测度。这一过程一直继续直到所有对象归为一类为止。2、调优法(动态聚类法)：首选对n个对象初步分类，然后根据分类的损失函数尽可能小的原则对分类进行调整，直到分类合理为止。,工商管理学院信息管理教研室,聚类分析的方法,3、最优分割法(有序样品聚类法)：开始将所有样品看成一类，然后根据某种最优准则将它们分割为二类、三类，一直分割到所需的k类为止。这种方法适用于有序样品的分类问题，也称为有序样品的聚类法。4、模糊聚类法：利用模糊集理论来处理分类问题，它对经济领域中具有模糊特征的两态数据或多态数据具有明显的分类效果。,工商管理学院信息管理教研室,聚类分析的方法,5、图论聚类法：利用图论中最小支撑树的概念来处理分类问题，创造了独具风格的方法。6、聚类预报法：利用聚类方法处理预报问题，在多元统计分析中，可用来做预报的方法很多，如回归分析和判断分析。但对一些异常数据，如气象中的灾害性天气的预报，回归或判断分析处理的效果都不好，而聚类预报弥补了这一不足，这是一个值得重视的方法。,工商管理学院信息管理教研室,R型聚类分析,聚类分析根据分类对象的不同分为R型和Q型在大类。R型是对变量(指标)进行分类处理，R型聚类分析的目的有以下方面：(1)可以了解变量间及变量组合间的亲疏关系；(2)对变量进行分类；(3)根据分类结果及它们之间的关系，在每一类中选择有代表性的变量作为重要变量，利用少数几个重要变量进一步作分析计算，如进行回归分析或Q型聚类分析等。,工商管理学院信息管理教研室,Q型聚类分析,Q型是对样品进行分类处理。Q型聚类分析的目的主要是对样品进行分类。分类的结果是直观的，且比传统分类方法更细致、全面、合理。当然使用不同的分类方法通常会得到不同的分类结果。对任何观测数据都没有惟一“正确的”的分类方法。实际应用中，常采用不同的分类方法，对数据进行分析计算，以便对分类提供意见，并由实际工作者决定所需要的分类数及分类情况。,工商管理学院信息管理教研室,第二节 聚类要素的数据处理,为了对样品(或变量)进行分类，就必须研究它们之间的关系。描述样品间亲疏相似程度的统计量很多，目前用得最多的是距离和相似系数，这两个统计量与变量的类型密切相关，为此我们首选分析一下变量的类型。,工商管理学院信息管理教研室,一、变量的类型,根据变量取值的不同可将变量分为以下几种：1、名义变量：变量值是几个没有次序之分的不同状态，它给变量值赋予名称。例如，性别、汽车品牌、职业、血型、是否患病、喜爱的颜色等等都是名义变量。2、有序变量：变量值是严格有次序的不同状态。例如产品按质量分为：不好、一般、好、很好。文化程度分为高、中、低等。,工商管理学院信息管理教研室,一、变量的类型,3、区间变量(或间隔变量)：区间变量是有顺序大小的数值变量，且数值间的差值是有意义的。例如考虑温度，40度比10度热30度，而40度和10度是相对于人们取定的0度而言的。这类变量对减法：两值之差是意义的；但对两值的比率是没有意义的。4、比率变量(比例变量)：比率变量也是数值变量，不仅数值之差有意义，而且要求有绝对的零点，两数值的比率也是很重要。,工商管理学院信息管理教研室,上述四类变量中，名义变量和有序变量也称为属性变量(或定性变量)，有时也称为离散变量；而区间变量和比率变量称为定量变量，有时也称为连续变量。不同类型的变量在定义距离或相似性质测度时有很大差异。本章主要讨论定量数据的聚类分析问题。,工商管理学院信息管理教研室,二、聚类要素的数据处理,在聚类分析中，聚类要素的选择是十分重要的，它直接影响分类结果的准确性和可靠性。在分类研究中，被聚类的对象常常是多个要素构成的。不同要素的数据往往具有不同的单位和量纲，因而其数值的差异可能是很大的，这就会对分类结果产生影响。因此当分类要素的对象确定之后，在进行聚类分析之前，还要对聚类要素进行数据处理。假设有m个被聚类的对象(样品)，每一个被聚类对象(样品)都有X1，X2，Xn个要素(指标或变量)构成。它们所对应的要素数据可用表31给出。,工商管理学院信息管理教研室,表31 观测数据及特征值,工商管理学院信息管理教研室,表3-1中 均值,工商管理学院信息管理教研室,标准差,1、中心化变换(标准化),分别求出各聚类要素所对应的均值，以各要素的数据减去相应要素的均值，即,工商管理学院信息管理教研室,中心化变换是一种标准化处理方法，变换后数据的均值为0，而协差不变，即协差阵为,其中,工商管理学院信息管理教研室,中心化变换是一种方便地计算样本协差阵的变换。,2、总和标准化变换,分别求出各聚类要素所对应的数据的总和，以各要素的数据除以该要素数据的总和，即,工商管理学院信息管理教研室,这种标准化方法所得的新数据,工商管理学院信息管理教研室,满足,3、标准差的标准化(标准化变换),即,工商管理学院信息管理教研室,4、极大值标准化(变换),即,工商管理学院信息管理教研室,经过这种标准化所得的新数据，各要素的极大值为1，其余各数值小于1。,5、极差正规化变换(规格化变换),即,工商管理学院信息管理教研室,经过这种标准化所得的新数据，各要素的极大值为1，极小值为0；极差为1，其余的数值均在0与1之间。数据是无量纲的量。,举例,表3-2给出了某地区九个农业区的七项经济指标，其极差正规化变换处理后的数据如表3-3所示。,工商管理学院信息管理教研室,表32 某地区九个农业区的七项经济指标数据,工商管理学院信息管理教研室,表33 极差正规化变换处理后的数据,工商管理学院信息管理教研室,6、极差标准化变换,即,工商管理学院信息管理教研室,7、对数变换,即,工商管理学院信息管理教研室,对数变换可将具有指数特征的数据结构化为线性数据结构。,此外，还有平方根变换，立方根变换等。它们的主要作用是把非线性数据结构变为线性数据结构，以适应某些统计方法的需要。,第三节(样品间的)距离和相似系数的计算,距离是事物(样品)之间差异性的测度，而相似系数则是其相似性的测度，所以距离和相似系数是聚类分析的依据和基础。当聚类要素的数据处理工作完成以后，就要计算分类对象(样品)之间的距离或相似系数，并依据距离或相似系数的矩阵结构进行聚类。,工商管理学院信息管理教研室,一、距离的计算,设观测数据,工商管理学院信息管理教研室,列成表31的形式。如果我们把每一个分类对象(样品，共m个)的n个聚类要素看成n维空间的n个坐标轴，则每一个分类对象的n个要素所构成的n维数据向量就是n维空间中的一个点(即m个样品看成n维空间中的m个点)。这样，各分类对象之间的差异性就可以由它们所对应的n维空间中点之间的距离度量。,关于距离的说明：,用,工商管理学院信息管理教研室,对于定量变量，常用的距离有:,1、绝对值距离,工商管理学院信息管理教研室,2、欧氏距离,工商管理学院信息管理教研室,3、明科夫斯基(Minkowski)距离,工商管理学院信息管理教研室,4、切比雪夫距离,工商管理学院信息管理教研室,当明科夫斯基距离p时，有,5、兰氏距离,工商管理学院信息管理教研室,这是由Lance和Williams最早提出的，故称为兰氏距离，定义为,这是一个无量纲的量，克服了明氏距离与各指标的量纲有关的缺点，且兰氏距离对在的奇异值不敏感，这样使得它特别适合高度偏倚的数据。但兰氏距离也没有考虑变量间的相关性。,明氏距离和兰氏距离都是假定变量之间相互独立，即在正交空间中讨论距离，但在实际问题中，变量之间往往存在着一定的相关性，为克服变量之间相关性的影响，可以采用马氏距离。,工商管理学院信息管理教研室,6、马氏距离,工商管理学院信息管理教研室,其中S-1为样本协差阵的逆矩阵。,马氏距离虽然可以排除变量之间相关性的干扰，并且不受量纲的影响，但是在聚类分析处理之前，如果用全部数据计算均值和协差阵来求马氏距离，效果不是很好。比较合理的办法是用各个类的样本来计算各自的协差阵，同一类样品间的马氏距离应当用这一类的协差阵来计算，但类的形成需要依赖于样品间的距离，而样品间合理的马氏距离又依赖于类，这就形成了一个恶性循环，因此在实际聚类分析中，马氏距离也不是理想的距离。为了克服变量之间相关性的影响，可采用斜交空间距离。,工商管理学院信息管理教研室,7、斜交空间距离,工商管理学院信息管理教研室,由于变量之间存在着不同程度的相关关系，在这种情况下，用正交空间距离来计算样品间的距离，易产生形变，从而使得用聚类分析进行分类时的谱系结构发生变形。在n维空间中，为使具有相关性变量的谱系结构不发生变形，采用斜交空间距离，即令,在数据标准化处理下，,工商管理学院信息管理教研室,举例,据表33中的数据，计算九个农业区之间的绝对值距离矩阵如下：,工商管理学院信息管理教研室,二、相似系数的计算,样品间的亲疏程度除了用距离描述外，也可用相似系数来表示。常用的相似系数是夹角余弦和相关系数。,工商管理学院信息管理教研室,1、夹角余弦,工商管理学院信息管理教研室,工商管理学院信息管理教研室,2、相关系数,工商管理学院信息管理教研室,工商管理学院信息管理教研室,举例,据表33中的数据，用夹角余弦公式计算，可得如下的相似系数矩阵：,工商管理学院信息管理教研室,三、变量间相似系数和距离的计算(略),聚类分析方法不仅用来对样品进行分类，有时需要对变量进行分类。在对变量进行分类时，通常采用相似系数来表示变量之间的亲疏程度。这部分内容感兴趣的同学可参见指定的参考书或其它相关书籍。,工商管理学院信息管理教研室,第四节 系统聚类法,系统聚类法是目前在实际应用中使用最多的一类方法。它是将类由多变到少的一种方法。本节m个样品的聚类问题。观测数据记为表31的形式，m个n 维的样品记为：,工商管理学院信息管理教研室,一、系统聚类法的基本思想和基本步骤,设有m个样品，每个样品测得n项指标。系统聚类方法的基本思想是：首先定义样品间的距离（或相似系数）和类与类之间的距离，一开始将m个样品各自自成一类，这里类间的距离与样品间的距离是等价的；然后将距离最近的两类合并，并计算新类与其它类的类间距离，再按最小距离准则并类。这样每次缩小一类，直到所有的样品都并成一类为止。这个并类过程可以用谱系聚类图形象地表达出来。,工商管理学院信息管理教研室,系统聚类法它的基本步骤,数据变换：可以使用上节介绍的方法对数据进行变换。数据变换的目的是为了便于比较、计算上的方便或改变数据的结构。选择度量样品间距离的定义（如欧氏距离）及度量类间距离的定义（如最短距离法，参见下面“系统聚类分析的方法”）。计算m个样品两两间的距离，得样品间,工商管理学院信息管理教研室,系统聚类法它的基本步骤(续),一开始（第一步：）m个样品各自构成一类，类的个数k=m个类：,工商管理学院信息管理教研室,此时类间的距离就是样品间的距离,即,系统聚类法它的基本步骤(续),每次合并类间距离最小的两类为一新类。此时类的总个数k减少1类，即,工商管理学院信息管理教研室,画谱系聚类图；,决定分类个数及类的成员。,例,设有5个产品，每个产品测得一项指标X，其值如下：1,2，4.5，6,8。试对5个产品按此指标进行分类。解：设样品间的距离取为欧氏距离，类间的距离取为类间的最短距离，根据上面介绍的步骤，计算如下：,工商管理学院信息管理教研室,一开始m个样品各自构成一类，得5个类：,工商管理学院信息管理教研室,即类的个数k=5。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,：,因此时类的总个数k=4大于1类，重复并类过程。,工商管理学院信息管理教研室,此时类的总个数k减少1类，变为k3，故把此步得到的新类记为CL3。,工商管理学院信息管理教研室,因此时类的总个数k=3大于1，重复并类过程。,：,工商管理学院信息管理教研室,因此时类的总个数k=2大于1类，重复并类过程。,工商管理学院信息管理教研室,并类过程至此结束。,画谱系聚类图,工商管理学院信息管理教研室,11,CL4,CL3,CL2,CL1,确定类的个数及各类的成员,工商管理学院信息管理教研室,12,若分为两类，则,；,，,若分为三类，则,；,确定类的个数及各类的成员,工商管理学院信息管理教研室,12,若分为四类，则,若分为五类，则,，,；,谱系聚类图的使用目的,有了谱系聚类图，用户希望分为几类，都可以从谱系聚类图中得到分类结果。到底分为几类最合适？这里并没有绝对正确的原则，一般可根据实际问题的不同，从谱系聚类图直观看出，通过分界值(阈值)给出分类，也可以用近似的统计检验来验证分类个数如何选取更合适(后面将有较详细叙述)。,工商管理学院信息管理教研室,二、系统聚类分析的方法,系统聚类法的聚类原则决定于样品间的距离(或相似系数)及类间距离的定义，类间距离的不同定义就产生了不同的系统聚类分析方法。下面介绍常用的几种系统聚类分析方法。,工商管理学院信息管理教研室,1、最短距离法(SINgle linkage),最短距离法是将类与类之间的距离定义为,工商管理学院信息管理教研室,工商管理学院信息管理教研室,工商管理学院信息管理教研室,以下，我们以某地区九个农业区的七项经济指标所形成的距离矩阵，用最短距离聚类法对某地区的九个农业区进行聚类分析。,前例,九个农业区之间的绝对值距离矩阵如下：,工商管理学院信息管理教研室,第一步，在99阶距离矩阵D中，非对角,工商管理学院信息管理教研室,D1,10=mind14,d19=min2.19,2.62=2.19D2,10=mind24,d29=min1.47,1.66=1.47D3,10=mind34,d39=min1.23,1.20=1.20D5,10=mind54,d59=min4.77,4.84=4.77D6,10=mind64,d69=min2.99,3.06=2.99D7,10=mind74,d79=min4.06,3.32=3.32D8,10=mind84,d89=min1.29,1.40=1.29,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G2 G3 G5 G6 G7 G8 G10G1 0G2 1.52 0G3 3.10 2.70 0G5 5.86 6.02 3.64 0G6 4.72 4.46 1.86 1.78 0G7 5.79 5.53 2.93 0.83 1.07 0G8 1.32 0.88 2.24 5.14 3.96 5.03 0G10 2.19 1.47 1.20 4.77 2.99 3.32 1.29 0,第二步，在上一步骤中所得到的新的88阶距离矩阵中，非对角元素中最小者为d57=0.83，故将G5与G7归并为一类，记为G11，即G11=G5，G7。再分别按照最短距离法递,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G2 G3 G6 G8 G10 G11G1 0 G2 1.52 0G3 3.10 2.70 0G6 4.72 4.46 1.86 0G8 1.32 0.88 2.24 3.96 0G10 2.19 1.47 1.20 2.99 1.29 0G11 5.79 5.53 2.93 1.07 5.03 3.32 0,第三步，在第二步所得到的新的77阶距离矩阵中，非对角线元素中最小者为d28=0.88，故将G2与G8归并为一类，记为G12，即G12=G2，G8。再分别按最短距离法递推公式,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G3 G6 G10 G11 G12G1 0G3 3.10 0G6 4.72 1.86 0G10 2.19 1.20 2.99 0G11 5.79 2.93 1.07 3.32 0G12 1.32 2.24 3.96 1.29 5.03 0,第四步，在第三步中所得到的新的66阶距离矩阵中，非对角线元素中最小者为为d6,11=1.07，故将G6和G11归并为一类，记为G13，即G13=G6，G11=G6，（G5，G7）。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G3 G10 G12 G13G1 0G3 3.10 0G10 2.19 1.20 0G12 1.32 2.24 1.29 0 G13 4.72 1.86 2.99 3.96 0,第五步，在第四步中所得到的新的55阶距离矩阵中，非对角线元素中最小者为 d3,10=1.20，故将G3和G10归并为一类，记为G14，即G14=G3，G10=G3，（G4，G9）。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G12 G13 G14 G1 0G12 1.32 0 G13 4.72 3.96 0G14 2.19 1.29 1.86 0,第六步，在第五步中所得到的新的44阶距离矩阵中，非对角线元素中最小者为 d12,14=1.29,故将G12和G14归并为一类,记为G15,即G15=G12,G14=(G2，G8),(G3,(G4，G9)。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G13 G15 G1 0G13 4.72 0G15 1.32 1.86 0,第七步，在第六步中所得到的新的33阶距离矩阵中，非对角线元素中最小者为 d1,15=1.32,故将G1和G15归并为一类,记为G16,即G16=G1,G15=G1,(G2,G8),(G3,(G4，G9)。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G13 G16 G13 0G16 1.86 0,第八步，将G13和G16归并为一类。此时，所有分类对象均被归并为一类。综合上述聚类过程，可以做出最短距离聚类谱系图（如下图所示）。,工商管理学院信息管理教研室,G10,G11,G12,G13,G14,G15,G16,G17,2、最长(远)距离法(COMplete method),最长距离法是将类与类之间的距离定义,工商管理学院信息管理教研室,工商管理学院信息管理教研室,最长(远)距离聚类法使两类合并后与其他类的距离是原来两类的类间距离的最大者，它加大了合并后的类与其它类的距离，具有空间距离扩张性质。对于前述之例，最长(远)距离聚类法的聚类过程如下：,第一步，在99阶距离矩阵D中，非对角,工商管理学院信息管理教研室,D1,10=maxd14,d19=max2.19,2.62=2.62D2,10=maxd24,d29=max1.47,1.66=1.66D3,10=maxd34,d39=max1.23,1.20=1.23D5,10=maxd54,d59=max4.77,4.84=4.84D6,10=maxd64,d69=max2.99,3.06=3.06D7,10=maxd74,d79=max4.06,3.32=4.06D8,10=maxd84,d89=max1.29,1.40=1.40,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G2 G3 G5 G6 G7 G8 G10G1 0G2 1.52 0G3 3.10 2.70 0G5 5.86 6.02 3.64 0G6 4.72 4.46 1.86 1.78 0G7 5.79 5.53 2.93 0.83 1.07 0G8 1.32 0.88 2.24 5.14 3.96 5.03 0G10 2.62 1.66 1.23 4.84 3.06 4.06 1.40 0,第二步，在上一步骤中所得到的新的88阶距离矩阵中，非对角元素中最小者为d57=0.83，故将G5与G7归并为一类，记为G11，即G11=G5，G7。再分别按照最长距离法递,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G2 G3 G6 G8 G10 G11G1 0 G2 1.52 0G3 3.10 2.70 0G6 4.72 4.46 1.86 0G8 1.32 0.88 2.24 3.96 0G10 2.62 1.66 1.23 3.06 1.40 0G11 5.86 6.02 3.64 1.78 5.14 4.48 0,第三步，在第二步所得到的新的77阶距离矩阵中，非对角线元素中最小者为d28=0.88，故将G2与G8归并为一类，记为G12，即G12=G2，G8。再分别按最长距离法递推公式,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G3 G6 G10 G11 G12G1 0G3 3.10 0G6 4.72 1.86 0G10 2.62 1.23 3.06 0G11 5.86 3.64 1.78 4.48 0G12 1.52 2.70 4.46 1.66 6.02 0,第四步，在第三步中所得到的新的66阶距离矩阵中，非对角线元素中最小者为为d3,10=1.23，故将G3和G10归并为一类，记为G13，即G13=G3，G10=G3，（G4，G9）。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G1 G6 G11 G12 G13G1 0G6 4.72 0G11 5.86 1.78 0G12 1.52 4.46 6.02 0 G13 3.10 3.06 4.84 2.70 0,第五步，在第四步中所得到的新的55阶距离矩阵中，非对角线元素中最小者为 d1,12=1.52，故将G1和G12归并为一类，记为G14，即G14=G1，G12=G1，（G2，G8）。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G6 G11 G13 G14 G6 0G11 1.78 0 G13 3.06 4.84 0G14 4.72 6.02 3.10 0,第六步，在第五步中所得到的新的44阶距离矩阵中，非对角线元素中最小者为 d6,11=1.78,故将G6和G11归并为一类,记为G15,即G15=G6，G11=(G6，（G5，G7）)。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G13 G14 G15 G13 0G14 3.10 0G15 4.84 6.02 0,第七步，在第六步中所得到的新的33阶距离矩阵中，非对角线元素中最小者为 d13,14=3.10,故将G13和G14归并为一类,记为G16,即G16=G13,G14=(G3,(G4,G9),(G1,(G2，G8)。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G15 G16 G15 0G16 6.02 0,第八步，将G15和G16归并为一类。此时，各个分类对象均被归并为一类。综合上述各聚类步骤，可做出最长距离聚类的谱系图（如下图所示）。,工商管理学院信息管理教研室,G10,G11,G12,G13,G14,G15,G16,G17,3、直接聚类法,直接聚类法，是根据距离或相似系数矩阵的结构一次并类得到结果，是一种简便的聚类方法。它先把各个分类对象单独视为一类，然后根据距离最小或相似系数最大的原则，依次选出一对分类对象，并成新类。如果其中一个分类对象已归于一类，则把另一个也归入该类；如果一对分类对象正好属于已归的两类，则把这两类并为一类。每一次归并，都划去该对象所在的行与行序相同的列。那么，经过m-1次就可以把全部分类对象归为一类，这样就可以根据归并的先后顺序做出聚类分析的谱系图。,工商管理学院信息管理教研室,例,用直接聚类法对某地区的九个农业区进行聚类分析，距离矩阵如下：,工商管理学院信息管理教研室,第一步，在距离矩阵D中，除对角线元素以外，d49=d94=0.51为最小者，故将第4区与第9区并为一类，划去第9行和第9列；,工商管理学院信息管理教研室,第二步，在余下的元素中，除对角线元素以外，d75=d57=0.83为最小者，故第5区与第7区并为一类，划掉第7行和第7列；,工商管理学院信息管理教研室,第三步，在第二步之后余下的元素之中，除对角线元素以外，d82=d28=0.88为最小者，故将第2区与第8区并为一类，划去第8行和第8列；,工商管理学院信息管理教研室,第四步，在第三步之后余下的元素中，除对角线元素以外，d43=d34=1.23为最小者，故将第3区与第4区并为一类，划去第4行和第4列，此时，第3、4、9区已归并为一类。,工商管理学院信息管理教研室,第五步，在第四步之后余下的元素中，除对角线元素以外，d21=d12=1.52为最小者，故将第1区与第2区并为一类，划去第2行与第2列，此时，第1、2、8区已归并为一类；,工商管理学院信息管理教研室,第六步，在第五步之后余下的元素中，除对角线元素以外，d65=d56=1.78为最小者，故将第5区与第6区并为一类，划去第6行和第6列，此时，第5、6、7区已归并为一类；,工商管理学院信息管理教研室,第七步，在第六步之后余下的元素中，除对角线元素以外，d31=d13=3.10为最小者，故将第1区与第3区并为一类，划去第3行和第3列，此时，第1，2，3，4，8，9区已归并为一类。,工商管理学院信息管理教研室,第八步，在第七步之后余下的元素中，除去对角线元素以外，只有d51=d15=5.86，故将第1区与第5区并为一类，划去第5行和第5列，此时，第1，2，3，4，5，6，7，8，9区均归并为一类。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,G10,G11,G12,G13,G14,G15,G16,G17,根据上述步骤，我们可以做出聚类过程的谱系图:,直接聚类法虽然简便，但在归类过程中是划去行和列的，因而难免有信息损失。因此直接聚类法并不是最好的系统聚类法。以下给出的聚类方法，仅作为了解。,工商管理学院信息管理教研室,4、中间距离法或中线法(MEDian method),如果类与类之间的距离既不采用两类间的最近距离，也不采用最远的距离，而是采用介于两者间的距离，这种方法称为中间距离法。,工商管理学院信息管理教研室,上式中：,工商管理学院信息管理教研室,5、重心法(CENtroid method),上述的最短距离法、最长距离法、中间距离法在定义类与类之间的距离时，没有考虑每一类中所包含的样品个数。如果将两类间的距离定义为两类重心间的距离，这种聚类方法称为重心法。对样品分类而言，每一类的重心就是属于该类样品的均值。,工商管理学院信息管理教研室,设某一类,工商管理学院信息管理教研室,如果样品间的距离定义为欧氏距离，则有,6、类(组)平均法(AVErage linkage),重心法虽然有较好的代表性，但并未充分利用各个样品的信息，有人提出用两类样品两两之间平方距离的平均作为类之间的距离，即,工商管理学院信息管理教研室,采用这种类间距离的聚类方法,称为类平均法。,则,工商管理学院信息管理教研室,类平均法是一种使用比较广泛、聚类效果较好的方法。,7、可变类平均法(FLExible-beta method),类平均法的类间距离递推公式中，没有反映,工商管理学院信息管理教研室,工商管理学院信息管理教研室,8、可变法及McQuitty相似分析法(MCQ),工商管理学院信息管理教研室,并把此方法称为McQuitty相似分析法。,9、离差(距离)平方和法(WARD),工商管理学院信息管理教研室,离差平方和法是Ward(1936)提出的，也称为Ward法。它基于方差分析思想，如果类分得正确，则同类样品之间的离差平方和应当较小，不同样品之间的离差平方和应当较大。,工商管理学院信息管理教研室,个类的总离差平方和为,工商管理学院信息管理教研室,Ward法的基本思想是，先将,，,Ward法把两类合并后增加的离差平方和看成类间的平方距离，即令,工商管理学院信息管理教研室,工商管理学院信息管理教研室,当样品间距采用欧氏距离时，上式可表示为,工商管理学院信息管理教研室,在实际应用中，离差平方和法应用比较广泛，分类效果较好。但它要求样品间距离必须采用欧氏距离。,除上述这些系统聚类方法外，还有几种系统聚类分析方法在SAS/STAT软件的CLUSTER过程中给出。如最大似然谱系聚类(EML)、密度估计法(DEN)、两阶段密度估计法(TWO)等。,工商管理学院信息管理教研室,三、系统聚类方法的统一和比较,1、系统聚类方法的统一 上述介绍的各种系统聚类分析方法中，除直接聚类法外，其余八种方法的聚类的步骤完全一样，所不同的是类与类之间的距离用不同的定义方法，因而得到不同的递推公式，Lance和Williams于1967年首先给出了统一公式，这样为编制统一的计算程序提供了很大的方便。,工商管理学院信息管理教研室,工商管理学院信息管理教研室,八种系统聚类方法的距离参数值,工商管理学院信息管理教研室,2、系统聚类方法的简单性质,(1)单调性,工商管理学院信息管理教研室,离差平方和法都具有单调性，只有重心法和中间距离法不具有单调性。(2)空间的浓缩与扩张 以前述之例来说明该性质。比较最短距离法和最长距离法的并类过程及相应的距离矩阵可以看出，每一步都有,工商管理学院信息管理教研室,这种性质称为最长距离法比最短距离法扩张；或称最短距离法比最长距离法浓缩。,对系统聚类方法，有如下结论：,类平均法(或中间距离法)比最短距离法扩张，而且比最长距离法浓缩；类平均法比重心法扩张，而且比离差平方和法浓缩。太浓缩的方法不够灵敏，太扩张的方法当样品容量大时容易失真。类平均法比较适中，相对于其它方法不太浓缩也不太扩张，而且具有单调性。因而是一种应用广泛、聚类效果较好的方法。系统聚类各种方法的比较还可以从其它方面的性质来研究，比如系统结构性、最优化性质等，各种方法的比较目前仍是值得研究的一个课题。,工商管理学院信息管理教研室,四、类个数的确定,聚类分析中，类的个数如何确定的问题是一个十分困难的问题，人们至今仍未找到令人满意的方法；但这又是一个不可回避的问题。迄今为止，我们只是直观地叙述了“类”的概念，并未给出严格的定义，但要对各种不同的类给予统一的定义是比较困难的，“类”的概念是一个模糊的概念。当然可以从不同的角度给出类的不同定义，但在实际应用中，人们并不完全从类的定义来确定类。下面介绍确定类个数的几种常见方法。,工商管理学院信息管理教研室,1、由适当的阈值确定,选定某种聚类方法，按系统聚类的步骤并类后，得到一张谱系聚类图。聚类图(或简称谱系图)只反映样品间(或变量间)的亲疏关系，它本身并没有给出分类，需要规定一个临界相似尺度，用以分割谱系图而得到样品(或变量)的分类。比如前述5个产品例，用最短距离法得谱系聚类图(如下图),给定临界值(阈值),2、根据数据点的散布图直观地确定类的个数,如果考察的指标只有二个，则可通过数据点的散布图直观地确定类的个数。如果有三个变量，可以绘制三维散布图并通过旋转三维坐标轴由数据点的分布来确定应分几个类(使用SAS软件)。当考察的指标在三个以上时，可以由这些指标综合出二个或三个综合变量后再绘制数据点在综合变量上的散布图，从而直观地确定分类个数。,工商管理学院信息管理教研室,3、根据统计量确定分类个数,在SAS/STAT软件的CLUSTER过程中，提供一些统计量(如半偏R2统计量、伪F统计量、伪t2统计量等)可近似地检验类的个数如何选择更合适。(具体方法略),工商管理学院信息管理教研室,4、根据谱系图确定分类个数的准则,Bemirmen(1972年)提出了应根据研究的目的来确定适当的分类方法，并提出了一些根据谱系图来分析的准则。准则A：各类重心之间的距离必须很大；准则B：确定的类中，各类所包含的元素都不要太多；准则C：类的个数必须符合实用目的；准则D：若采用几种不同的聚类方法处理，则在各自的聚类图中应发现相同的类。应当指出，关于类个数如何确定问题，至今还没有一个合适的标准，也就是说对任何观测数据都没有惟一“正确的”的分类方法。,工商管理学院信息管理教研室,作业,已知6个样品两两之间的距离矩阵,试按最短距离法进行聚类，并画出谱系图。,1 2 3 4 5 6,