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

1、管理决策模型与方法管理决策模型与方法(聚类分析部分聚类分析部分)(适用于信息管理与信息系统、工商管理专业适用于信息管理与信息系统、工商管理专业 30H)主讲教师：屈春艳主讲教师：屈春艳工商管理学院信息管理教研室第三章第三章 聚类分析聚类分析 聚类分析，亦称群分析或点群分析，它是聚类分析，亦称群分析或点群分析，它是研究对样品或指标进行分类的一种多元统计研究对样品或指标进行分类的一种多元统计分析方法分析方法(它是研究多要素事物分类问题的数它是研究多要素事物分类问题的数量方法量方法)。所谓的类通俗地说就是相似元素的。所谓的类通俗地说就是相似元素的集合。集合。什么是分类？什么是分类？分类是将一个观测对

2、象指定到某一类分类是将一个观测对象指定到某一类(组组)。工商管理学院信息管理教研室 分类的问题可以分成两种：分类的问题可以分成两种：一种是对当前所研究的问题已知它的类一种是对当前所研究的问题已知它的类别数目，且知道各类的特征别数目，且知道各类的特征(如分布规律、或如分布规律、或知道来自各类的训练样本知道来自各类的训练样本)，我们的目的是要，我们的目的是要将另一些未知类别的个体正确归属于其中某将另一些未知类别的个体正确归属于其中某一类，这是判别分析所要解决的问题。一类，这是判别分析所要解决的问题。另一种是事先不知道研究问题应分成几另一种是事先不知道研究问题应分成几类，更不知道观测的个体的具体分类

3、情况，类，更不知道观测的个体的具体分类情况，我们的目的正是需要通过对观测数据所进行我们的目的正是需要通过对观测数据所进行的分析处理，选定一种度量个体接近程度的的分析处理，选定一种度量个体接近程度的统计量、确定分类数目、建立一种分类方法，统计量、确定分类数目、建立一种分类方法，工商管理学院信息管理教研室 并按亲近程度对观测对象给出合理的分类。并按亲近程度对观测对象给出合理的分类。这种问题在实际中大量存在，它正是聚类分这种问题在实际中大量存在，它正是聚类分析所要解决的问题。析所要解决的问题。工商管理学院信息管理教研室第一节第一节 聚类分析的方法聚类分析的方法 聚类分析的职能是建立一种分类方法，聚类

4、分析的职能是建立一种分类方法，其基本原理是，根据样品其基本原理是，根据样品(本本)自身的属性，自身的属性，用数学方法按照某些相似性或差异性指标，用数学方法按照某些相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。亲疏关系程度对样本进行聚类。工商管理学院信息管理教研室聚类分析的方法聚类分析的方法 聚类分析的内容十分丰富，按其聚类的方聚类分析的内容十分丰富，按其聚类的方法可分为以下几种：法可分为以下几种：1 1、系统聚类法：开始每个对象自成一类，、系统聚类法：开始每个对象自成一类，然后每次将最相似的两类合并，合并后重新然后每

5、次将最相似的两类合并，合并后重新计算新类与其它类的距离或相近性测度。这计算新类与其它类的距离或相近性测度。这一过程一直继续直到所有对象归为一类为止。一过程一直继续直到所有对象归为一类为止。2、调优法、调优法(动态聚类法动态聚类法)：首选对：首选对n个对个对象初步分类，然后根据分类的损失函数尽可象初步分类，然后根据分类的损失函数尽可能小的原则对分类进行调整，直到分类合理能小的原则对分类进行调整，直到分类合理为止。为止。工商管理学院信息管理教研室聚类分析的方法聚类分析的方法 3 3、最优分割法、最优分割法(有序样品聚类法有序样品聚类法)：开始：开始将所有样品看成一类，然后根据某种最优准将所有样品看

6、成一类，然后根据某种最优准则将它们分割为二类、三类，一直分割到所则将它们分割为二类、三类，一直分割到所需的需的k k类为止。这种方法适用于有序样品的分类为止。这种方法适用于有序样品的分类问题，也称为有序样品的聚类法。类问题，也称为有序样品的聚类法。4、模糊聚类法：利用模糊集理论来处、模糊聚类法：利用模糊集理论来处理分类问题，它对经济领域中具有模糊特征理分类问题，它对经济领域中具有模糊特征的两态数据或多态数据具有明显的分类效果。的两态数据或多态数据具有明显的分类效果。工商管理学院信息管理教研室聚类分析的方法聚类分析的方法 5、图论聚类法：利用图论中最小支撑树的概念来处理分类问题，创造了独具风格的

7、方法。6、聚类预报法：利用聚类方法处理预报问题，在多元统计分析中，可用来做预报的方法很多，如回归分析和判断分析。但对一些异常数据，如气象中的灾害性天气的预报，回归或判断分析处理的效果都不好，而聚类预报弥补了这一不足，这是一个值得重视的方法。工商管理学院信息管理教研室R R型聚类分析型聚类分析 聚类分析根据分类对象的不同分为R型和Q型在大类。R型是对变量(指标)进行分类处理，R型聚类分析的目的有以下方面：(1)可以了解变量间及变量组合间的亲疏关系；(2)对变量进行分类；(3)根据分类结果及它们之间的关系，在每一类中选择有代表性的变量作为重要变量，利用少数几个重要变量进一步作分析计算，如进行回归分

8、析或Q型聚类分析等。工商管理学院信息管理教研室Q Q型聚类分析型聚类分析 Q Q型是对样品进行分类处理。型是对样品进行分类处理。Q Q型聚类分型聚类分析的目的主要是对样品进行分类。分类的结析的目的主要是对样品进行分类。分类的结果是直观的，且比传统分类方法更细致、全果是直观的，且比传统分类方法更细致、全面、合理。面、合理。当然使用不同的分类方法通常会得到不当然使用不同的分类方法通常会得到不同的分类结果。对任何观测数据都没有惟一同的分类结果。对任何观测数据都没有惟一“正确的正确的”的分类方法。实际应用中，常采的分类方法。实际应用中，常采用不同的分类方法，对数据进行分析计算，用不同的分类方法，对数据

9、进行分析计算，以便对分类提供意见，并由实际工作者决定以便对分类提供意见，并由实际工作者决定所需要的分类数及分类情况。所需要的分类数及分类情况。工商管理学院信息管理教研室第二节第二节 聚类要素的数据处理聚类要素的数据处理 为了对样品为了对样品(或变量或变量)进行分类，就必须进行分类，就必须研究它们之间的关系。描述样品间亲疏相似研究它们之间的关系。描述样品间亲疏相似程度的统计量很多，目前用得最多的是距离程度的统计量很多，目前用得最多的是距离和相似系数，这两个统计量与变量的类型密和相似系数，这两个统计量与变量的类型密切相关，为此我们首选分析一下变量的类型。切相关，为此我们首选分析一下变量的类型。工商

10、管理学院信息管理教研室一、变量的类型一、变量的类型 根据变量取值的不同可将变量分为以下几根据变量取值的不同可将变量分为以下几种：种：1 1、名义变量：、名义变量：变量值是几个没有次序之变量值是几个没有次序之分的不同状态，它给变量值赋予名称。例如，分的不同状态，它给变量值赋予名称。例如，性别、汽车品牌性别、汽车品牌、职业、血型、是否患病、职业、血型、是否患病、喜爱的颜色等等都是名义变量。喜爱的颜色等等都是名义变量。2 2、有序变量：、有序变量：变量值是严格有次序的不变量值是严格有次序的不同状态。例如产品按质量分为：不好、一般、同状态。例如产品按质量分为：不好、一般、好、很好。文化程度分为高、中、

11、低等。好、很好。文化程度分为高、中、低等。工商管理学院信息管理教研室一、变量的类型一、变量的类型 3、区间变量、区间变量(或间隔变量或间隔变量)：区间变量是区间变量是有顺序大小的数值变量，且数值间的差值是有顺序大小的数值变量，且数值间的差值是有意义的。例如考虑温度，有意义的。例如考虑温度，40度比度比10度热度热30度，而度，而40度和度和10度是相对于人们取定的度是相对于人们取定的0度而度而言的。这类变量对减法：两值之差是意义的；言的。这类变量对减法：两值之差是意义的；但对两值的比率是没有意义的。但对两值的比率是没有意义的。4 4、比率变量、比率变量(比例变量比例变量)：比率变量也比率变量也

12、是数值变量，不仅数值之差有意义，而且要是数值变量，不仅数值之差有意义，而且要求有绝对的零点，两数值的比率也是很重要。求有绝对的零点，两数值的比率也是很重要。工商管理学院信息管理教研室 上述四类变量中，名义变量和有序变量也上述四类变量中，名义变量和有序变量也称为属性变量称为属性变量(或定性变量或定性变量)，有时也称为离，有时也称为离散变量；而区间变量和比率变量称为定量变散变量；而区间变量和比率变量称为定量变量，有时也称为连续变量。量，有时也称为连续变量。不同类型的变量在定义距离或相似性质不同类型的变量在定义距离或相似性质测度时有很大差异。本章主要讨论定量数据测度时有很大差异。本章主要讨论定量数据

13、的聚类分析问题。的聚类分析问题。工商管理学院信息管理教研室二、聚类要素的数据处理二、聚类要素的数据处理 在聚类分析中，聚类要素的选择是十分重要的，在聚类分析中，聚类要素的选择是十分重要的，它直接影响分类结果的准确性和可靠性。在分类研它直接影响分类结果的准确性和可靠性。在分类研究中，被聚类的对象常常是多个要素构成的。不同究中，被聚类的对象常常是多个要素构成的。不同要素的数据往往具有不同的单位和量纲，因而其数要素的数据往往具有不同的单位和量纲，因而其数值的差异可能是很大的，这就会对分类结果产生影值的差异可能是很大的，这就会对分类结果产生影响。因此当分类要素的对象确定之后，在进行聚类响。因此当分类要

14、素的对象确定之后，在进行聚类分析之前，还要对聚类要素进行数据处理。分析之前，还要对聚类要素进行数据处理。假设有假设有m个被聚类的对象个被聚类的对象(样品样品)，每一个被聚类，每一个被聚类对象对象(样品样品)都有都有X1，X2，Xn个要素个要素(指标或变指标或变量量)构成。它们所对应的要素数据可用表构成。它们所对应的要素数据可用表3 31 1给出。给出。工商管理学院信息管理教研室表表31 观测数据及特征值观测数据及特征值 变量变量样品样品X1Xj XnX(1)x11 x1j x1n X(i)xi1 xij xin X(m)xm1 xmj xmn均均 值值标准差标准差s1 sj sn工商管理学院信

15、息管理教研室1xjxnx表3-1中 均值工商管理学院信息管理教研室),2,1(11njxmxmiijj标准差),2,1()(1112njxxmsmijijj1 1、中心化变换、中心化变换(标准化标准化)分别求出各聚类要素所对应的均值，以各要素的数据减去相应要素的均值，即工商管理学院信息管理教研室),2,1;,2,1(*njmixxxjijij 中心化变换是一种标准化处理方法，变换后数据的均值为0，而协差不变，即协差阵为)(*ijsSS 其中 工商管理学院信息管理教研室mttjtimtjtjitiijxxmxxxxms1*111)(11 中心化变换是一种方便地计算样本协差阵的变换。2 2、总和标

16、准化变换、总和标准化变换 分别求出各聚类要素所对应的数据的总和，以各要素的数据除以该要素数据的总和，即工商管理学院信息管理教研室),2,1;,2,1(1*njmixxxmiijijij 这种标准化方法所得的新数据 工商管理学院信息管理教研室*ijx满足),2,1(11*njxmiij3 3、标准差的标准化、标准差的标准化(标准化变换标准化变换)即 工商管理学院信息管理教研室),2,1;,2,1(*njmisxxxjjijij 这种标准化方法所得的新数据*ijx各要素的平均值为0，标准差为1，即有 1)(11,0112*1*mijijjmiijjxxmsxmx而且标准化后的数据*ijx与变量的量

17、纲无关。4 4、极大值标准化、极大值标准化(变换变换)即工商管理学院信息管理教研室 经过这种标准化所得的新数据，各要素经过这种标准化所得的新数据，各要素的极大值为的极大值为1 1，其余各数值小于，其余各数值小于1 1。),2,1;,2,1(max*njmixxxijiijij5 5、极差正规化变换、极差正规化变换(规格化变换规格化变换)即工商管理学院信息管理教研室 经过这种标准化所得的新数据，各要素的极大值为1，极小值为0；极差为1，其余的数值均在0与1之间。数据是无量纲的量。),2,1;,2,1(minmaxmin*njmixxxxxijiijiijiijij举例举例 表表3-23-2给出了

18、某地区九个农业区的七项给出了某地区九个农业区的七项经济指标，其极差正规化变换处理后的数据经济指标，其极差正规化变换处理后的数据如表如表3-33-3所示。所示。工商管理学院信息管理教研室表表3 32 2 某地区九个农业区的七项经济指标数据某地区九个农业区的七项经济指标数据 工商管理学院信息管理教研室区代号区代号 指指 标标 人均耕地人均耕地x x1 1(亩亩/人人)劳均耕地劳均耕地x x2 2(亩亩/个个)水田比重水田比重x x3 3(%)(%)复种指数复种指数x x4 4(%)(%)粮食亩产粮食亩产x x5 5(kg/(kg/亩亩)人均粮食人均粮食x x6 6(kg/(kg/人人)稻谷占粮食稻

19、谷占粮食比重比重x x7 7(%)(%)G14.414.4116.4016.405.635.63 113.60113.60 300.70300.701036.401036.4012.2012.20G24.724.7214.5714.570.390.3995.1095.10 184.90184.90 683.70683.700.850.85G31.841.844.474.475.285.28 148.50148.50 462.30462.30 611.10611.106.496.49G42.692.697.917.910.390.39 111.00111.00 297.20297.20 632.

20、60632.600.920.92G51.221.223.183.1872.0472.04 217.80217.80 816.60816.60 791.10791.1080.3880.38G61.231.233.163.1643.7843.78 179.60179.60 598.20598.20 636.50636.5048.1748.17G71.121.122.722.7265.1565.15 194.70194.70 712.60712.60 634.30634.3080.1780.17G84.404.409.999.995.355.3594.9094.90 245.30245.30 771

21、.70771.707.807.80G92.502.506.216.212.902.9094.8094.80 282.10282.10 574.60574.601.171.17表表3 33 3 极差正规化变换处理后的数据极差正规化变换处理后的数据 工商管理学院信息管理教研室区代号区代号 指指 标标 x1x2x3x4x5x6x7G10.910.911.001.000.070.070.150.150.180.181.001.000.140.14G21.001.000.870.870.000.000.000.000.000.000.240.240.000.00G30.200.200.150.150.0

22、70.070.440.440.440.440.080.080.070.07G40.440.440.380.380.000.000.130.130.180.180.130.130.000.00G50.030.030.030.031.001.001.001.001.001.000.450.451.001.00G60.030.030.030.030.610.610.690.690.650.650.130.130.590.59G70.000.000.000.000.900.900.810.810.840.840.130.131.001.00G80.910.910.530.530.070.070.000

23、.000.100.100.430.430.090.09G90.380.380.260.260.040.040.000.000.150.150.000.000.000.006 6、极差标准化变换、极差标准化变换 即工商管理学院信息管理教研室),2,1;,2,1(minmax*njmixxxxxijiijijijij 极差标准化变换变换后的数据，每个变量的样本均值为0，极差为1，且1*ijx，在 以后的分析计算中可以减少误差的产生；同时变化后的数据也是无量纲的量。7 7、对数变换、对数变换 即即工商管理学院信息管理教研室 对数变换可将具有指数特征的数据结对数变换可将具有指数特征的数据结构化为线性数

24、据结构。构化为线性数据结构。),2,1;,2,1(0log*njmixxxijijij要求 此外，还有平方根变换，立方根变换等。此外，还有平方根变换，立方根变换等。它们的主要作用是把非线性数据结构变为线它们的主要作用是把非线性数据结构变为线性数据结构，以适应某些统计方法的需要。性数据结构，以适应某些统计方法的需要。第三节第三节 (样品间的样品间的)距离和相似系数的计算距离和相似系数的计算 距离距离是事物是事物(样品样品)之间差异性的测度，之间差异性的测度，而而相似系数相似系数则是其相似性的测度，所以距离则是其相似性的测度，所以距离和相似系数是聚类分析的依据和基础。和相似系数是聚类分析的依据和基

25、础。当聚类要素的数据处理工作完成以后，当聚类要素的数据处理工作完成以后，就要计算分类对象就要计算分类对象(样品样品)之间的距离或相似之间的距离或相似系数，并依据距离或相似系数的矩阵结构进系数，并依据距离或相似系数的矩阵结构进行聚类。行聚类。工商管理学院信息管理教研室一、距离的计算一、距离的计算设观测数据 工商管理学院信息管理教研室),2,1;,2,1(njmixij 列成表列成表31的形式。如果我们把每一个分类的形式。如果我们把每一个分类对象对象(样品，共样品，共m个个)的的n个聚类要素看成个聚类要素看成n维空维空间的间的n个坐标轴，则每一个分类对象的个坐标轴，则每一个分类对象的n个要个要素所

26、构成的素所构成的n维数据向量就是维数据向量就是n维空间中的一维空间中的一个点个点(即即m个样品看成个样品看成n维空间中的维空间中的m个点个点)。这样，各分类对象之间的差异性就可以由它这样，各分类对象之间的差异性就可以由它们所对应的们所对应的n维空间中点之间的距离度量。维空间中点之间的距离度量。关于距离的说明：关于距离的说明：用 工商管理学院信息管理教研室表示样品 和 ijd)(iX)(jX之间的距离，一般要求：(1)ijd0,对于一切i,j;当ijd=0时)(iX=)(jX；jiijdd(2),对于一切i,j；kjikijddd(3),对于一切i,j,k(三角不等式).对于定量变量，常用的距离

27、有:1 1、绝对值距离、绝对值距离 工商管理学院信息管理教研室),2,1,(1mjixxdnkjkikij2 2、欧氏距离、欧氏距离 工商管理学院信息管理教研室nkjkikijxxd12)(mji,2,1,3 3、明科夫斯基、明科夫斯基(MinkowskiMinkowski)距离距离 工商管理学院信息管理教研室pnkpjkikijxxd11mji,2,1,4 4、切比雪夫距离、切比雪夫距离 工商管理学院信息管理教研室 当明科夫斯基距离p时，有 jkiknkijxxd1maxmji,2,1,5 5、兰氏距离、兰氏距离 工商管理学院信息管理教研室 这是由Lance和Williams最早提出的，故称

28、为兰氏距离兰氏距离，定义为mji,2,1,nkjkikjkikijxxxxnLd1)(1)(这是一个无量纲的量，克服了明氏距离这是一个无量纲的量，克服了明氏距离与各指标的量纲有关的缺点，且兰氏距离对与各指标的量纲有关的缺点，且兰氏距离对在的奇异值不敏感，这样使得它特别适合高在的奇异值不敏感，这样使得它特别适合高度偏倚的数据。但兰氏距离也没有考虑变量度偏倚的数据。但兰氏距离也没有考虑变量间的相关性。间的相关性。明氏距离明氏距离和和兰氏距离兰氏距离都是假定变量之间都是假定变量之间相互独立，即在正交空间中讨论距离，但在相互独立，即在正交空间中讨论距离，但在实际问题中，变量之间往往存在着一定的相实际问

29、题中，变量之间往往存在着一定的相关性，为克服变量之间相关性的影响，可以关性，为克服变量之间相关性的影响，可以采用采用马氏距离马氏距离。工商管理学院信息管理教研室6 6、马氏距离、马氏距离 工商管理学院信息管理教研室样品样品 和 )(iX)(jX的马氏距离为的马氏距离为mji,2,1,)()()()()(1)()(jiTjiijXXSXXMd其中其中S S-1-1为样本协差阵的逆矩阵。为样本协差阵的逆矩阵。马氏距离马氏距离虽然可以排除变量之间相关性虽然可以排除变量之间相关性的干扰，并且不受量纲的影响，但是在聚类的干扰，并且不受量纲的影响，但是在聚类分析处理之前，如果用全部数据计算均值和分析处理之

30、前，如果用全部数据计算均值和协差阵来求马氏距离，效果不是很好。比较协差阵来求马氏距离，效果不是很好。比较合理的办法是用各个类的样本来计算各自的合理的办法是用各个类的样本来计算各自的协差阵，同一类样品间的马氏距离应当用这协差阵，同一类样品间的马氏距离应当用这一类的协差阵来计算，但类的形成需要依赖一类的协差阵来计算，但类的形成需要依赖于样品间的距离，而样品间合理的马氏距离于样品间的距离，而样品间合理的马氏距离又依赖于类，这就形成了一个恶性循环，因又依赖于类，这就形成了一个恶性循环，因此在实际聚类分析中，马氏距离也不是理想此在实际聚类分析中，马氏距离也不是理想的距离。的距离。为了克服变量之间相关性的

31、影响，可采为了克服变量之间相关性的影响，可采用用斜交空间距离斜交空间距离。工商管理学院信息管理教研室7 7、斜交空间距离、斜交空间距离 工商管理学院信息管理教研室 由于变量之间存在着不同程度的相关关由于变量之间存在着不同程度的相关关系，在这种情况下，用正交空间距离来计算系，在这种情况下，用正交空间距离来计算样品间的距离，易产生形变，从而使得用聚样品间的距离，易产生形变，从而使得用聚类分析进行分类时的谱系结构发生变形。类分析进行分类时的谱系结构发生变形。在在n n维空间中，为使具有相关性变量的谱维空间中，为使具有相关性变量的谱系结构不发生变形，采用斜交空间距离，即系结构不发生变形，采用斜交空间距

32、离，即令令在数据标准化处理下，工商管理学院信息管理教研室21112)(1nknlkljliljkikijrxxxxndmji,2,1,为变量和 kX之间的相关系数。lXklr举例举例 据表33中的数据，计算九个农业区之间的绝对值距离矩阵如下：工商管理学院信息管理教研室040.132.306.384.451.020.166.162.2003.596.314.529.124.288.032.1007.183.006.493.253.579.5078.199.286.146.472.4077.464.302.686.5023.147.119.2070.210.3052.10)d(D99ij二、相似系

33、数的计算二、相似系数的计算 样品间的亲疏程度除了用距离描述外，也可用相似系数来表示。常用的相似系数是夹夹角余弦角余弦和相关系数相关系数。工商管理学院信息管理教研室1 1、夹角余弦、夹角余弦 工商管理学院信息管理教研室样品样品 的的n n个观测值个观测值 )(iX)(jX看成看成n n维空间的向量，则维空间的向量，则),(21iniixxx)(iX和和 的夹角的夹角 ij的余弦称为两向量的相似系数，即的余弦称为两向量的相似系数，即 nkjknkiknkjkikijijxxxxr12121)(cosmji,2,1,工商管理学院信息管理教研室时，夹角在上式中，显然有：-1)(jX=1，说明两个样)(

34、iX和 正交时，ijijcos1。当ji=0，ijr品完全相似；当=0，说明两个样品不相似。ij=90，ijr2 2、相关系数、相关系数 工商管理学院信息管理教研室)(jX)(iX和表示，相关系数就是对数据作标准化处理后的夹角ijr余弦。样品的相关系数亦用即nkjjknkiiknkjjkiikijxxxxxxxxr12121)()()(mji,2,1,工商管理学院信息管理教研室)(jX)(iX和。在上式中，ix和jx分别为聚类对象（样品）各要素标准化数据的平均值。当 时，=1，表示两个样品线性相关，ji ijr一般情况下1ijr举例举例 据表33中的数据，用夹角余弦公式计算，可得如下的相似系数

35、矩阵：工商管理学院信息管理教研室190.019.023.021.095.055.093.077.0114.018.021.092.045.095.093.0199.098.024.071.001.020.0199.030.080.005.024.0130.076.006.030.0167.094.088.0138.049.0188.01)(99ijrR三、变量间相似系数和距离的计算三、变量间相似系数和距离的计算(略略)聚类分析方法不仅用来对样品进行分类，聚类分析方法不仅用来对样品进行分类，有时需要对变量进行分类。在对变量进行分有时需要对变量进行分类。在对变量进行分类时，通常采用相似系数来表示变

36、量之间的类时，通常采用相似系数来表示变量之间的亲疏程度。亲疏程度。这部分内容感兴趣的同学可参见指定的这部分内容感兴趣的同学可参见指定的参考书或其它相关书籍。参考书或其它相关书籍。工商管理学院信息管理教研室第四节第四节 系统聚类法系统聚类法 系统聚类法是目前在实际应用中使用最系统聚类法是目前在实际应用中使用最多的一类方法。它是将类由多变到少的一种多的一类方法。它是将类由多变到少的一种方法。方法。本节本节m个样品的聚类问题。观测数据记个样品的聚类问题。观测数据记为表为表31的形式，的形式，m个个n 维的样品记为：维的样品记为：工商管理学院信息管理教研室),2,1()(miXi一、系统聚类法的基本思

37、想和基本步骤一、系统聚类法的基本思想和基本步骤 设有设有m个样品，每个样品测得个样品，每个样品测得n项指标。系项指标。系统聚类方法的统聚类方法的基本思想是：基本思想是：首先定义样品间首先定义样品间的距离（或相似系数）和类与类之间的距离，的距离（或相似系数）和类与类之间的距离，一开始将一开始将m个样品各自自成一类，这里类间个样品各自自成一类，这里类间的距离与样品间的距离是等价的；然后将距的距离与样品间的距离是等价的；然后将距离最近的两类合并，并计算新类与其它类的离最近的两类合并，并计算新类与其它类的类间距离，再按最小距离准则并类。这样每类间距离，再按最小距离准则并类。这样每次缩小一类，直到所有的

38、样品都并成一类为次缩小一类，直到所有的样品都并成一类为止。这个并类过程可以用止。这个并类过程可以用谱系聚类图谱系聚类图形象地形象地表达出来。表达出来。工商管理学院信息管理教研室系统聚类法它的基本步骤系统聚类法它的基本步骤 数据变换：可以使用上节介绍的方法对数据变换：可以使用上节介绍的方法对数据进行变换。数据变换的目的是为了便于数据进行变换。数据变换的目的是为了便于比较、计算上的方便或改变数据的结构。比较、计算上的方便或改变数据的结构。选择度量样品间距离的定义（如欧氏距选择度量样品间距离的定义（如欧氏距离）及度量类间距离的定义（如最短距离法，离）及度量类间距离的定义（如最短距离法，参见下面参见下

39、面“系统聚类分析的方法系统聚类分析的方法”）。）。计算计算m个样品两两间的距离，得样品间个样品两两间的距离，得样品间工商管理学院信息管理教研室)0(D的距离矩阵的距离矩阵；系统聚类法它的基本步骤系统聚类法它的基本步骤(续续)一开始（第一步：）一开始（第一步：）m个样品各自构个样品各自构成一类，类的个数成一类，类的个数k=m个类：个类：工商管理学院信息管理教研室),2,1()(miXGii 此时类间的距离就是样品间的距离此时类间的距离就是样品间的距离,即即)0()1(DD然后对步骤然后对步骤 mi,3,2执行并类过程的步执行并类过程的步骤骤和和；系统聚类法它的基本步骤系统聚类法它的基本步骤(续续

40、)每次合并类间距离最小的两类为一新每次合并类间距离最小的两类为一新类。此时类的总个数类。此时类的总个数k k减少减少1 1类，即类，即工商管理学院信息管理教研室1imk 计算新类与其它类的距离，得新的距计算新类与其它类的距离，得新的距)(iD离矩阵离矩阵。若合并后类的总个数。若合并后类的总个数k仍大于仍大于1 1，重复，重复和和步；直到类的总个数为步；直到类的总个数为1 1时止。时止。画谱系聚类图；画谱系聚类图；决定分类个数及类的成员。决定分类个数及类的成员。例例 设有设有5 5个产品，每个产品测得一项指标个产品，每个产品测得一项指标X，其值如下：其值如下：1,21,2，4.54.5，6,86

41、,8。试对。试对5 5个产品按个产品按此指标进行分类。此指标进行分类。解：设样品间的距离取为欧氏距离，类解：设样品间的距离取为欧氏距离，类间的距离取为类间的最短距离，根据上面介间的距离取为类间的最短距离，根据上面介绍的步骤，计算如下：绍的步骤，计算如下：工商管理学院信息管理教研室计算5个样品:)5()4()3()2()1(,XXXXX两两间的距离，得初始的类间距离矩阵为：两两间的距离，得初始的类间距离矩阵为：)1(D 一开始m个样品各自构成一类，得5个类：工商管理学院信息管理教研室 0205.35.10645.20755.310)1(D)5,2,1()(iXGii即类的个数k=5。工商管理学院

42、信息管理教研室可知，首先合并)1(D)1(X)2(X)2()1(,4XXCL类的总个数k减少1类，变为k=4，故把此步得到和为一新类，记为；此时的新类记为CL4。由 按最短距离法计算新类按最短距离法计算新类CL4与其他类的与其他类的距距)2(D离，得新的距离矩阵：离，得新的距离矩阵：工商管理学院信息管理教研室)3(X)4(X)5(X4CL)3(X)4(X)5(X4CL01.5 3.5 2.5 0 2 4 0 6 0)2(D：因此时类的总个数因此时类的总个数k=4大于大于1类，重复并类，重复并类过程。类过程。工商管理学院信息管理教研室此时类的总个数k减少1类，变为k3，故把此步得到的新类记为CL

43、3。)2(D)3(X)4(X)4()3(,3XXCL 由可知类间距离为1.5时最小，故合并和为一新类，记为：按最短距离法计算新类CL3与其他类的)3(D距离，得新的距离矩阵：工商管理学院信息管理教研室因此时类的总个数k=3大于1，重复并类过程。：)3(D)5(X4CL3CL)5(X4CL3CL06202.50工商管理学院信息管理教研室此时类的总个数k减少1类，变为k=2，故把此步得到的新类记为CL2。)3(D)5(X3CL)4()3()5(,2XXXCL由可知，应合并和为一新类，记为；按最短距离法计算新类CL2与其他类的)4(D距离，得到的新的距离矩阵：4CL2CL4CL2CL0 02.52.

44、5 0 0因此时类的总个数k=2大于1类，重复并类过程。工商管理学院信息管理教研室)4(D4CL2CL)5()4()3()2()1(,1XXXXXCL 由可知，最后应合并和为一新类，记为；此时类的总个数k=1，故把此步得到的新类记为CL1。1CL1CL0 0)5(D此时所有样品全并成一类,得新的距离矩阵：并类过程至此结束。画谱系聚类图画谱系聚类图 工商管理学院信息管理教研室11谱系聚类图0 1 1.5 2 2.5 3)1(X)2(X)3(X)4(X)5(XCL4CL3CL2CL1确定类的个数及各类的成员工商管理学院信息管理教研室12若分为两类，则)4()3()5()2(2,XXXG；)2()1

45、()2(1,XXG，若分为三类，则)4()3()3(3,XXG；)2()1()3(1,XXG,)5()3(2XG,确定类的个数及各类的成员工商管理学院信息管理教研室12若分为四类，则若分为五类，则，)2()1()4(1,XXG；)4()4(4XG)5()4(2XG,)3()4(3XG,)5,4,3,2,1()()5(iXGii谱系聚类图的使用目的谱系聚类图的使用目的 有了谱系聚类图，用户希望分为几类，有了谱系聚类图，用户希望分为几类，都可以从谱系聚类图中得到分类结果。都可以从谱系聚类图中得到分类结果。到底分为几类最合适？到底分为几类最合适？这里并没有绝对这里并没有绝对正确的原则，一般可根据实际

46、问题的不同，正确的原则，一般可根据实际问题的不同，从谱系聚类图直观看出，通过分界值从谱系聚类图直观看出，通过分界值(阈值阈值)给出分类，也可以用近似的统计检验来验证给出分类，也可以用近似的统计检验来验证分类个数如何选取更合适分类个数如何选取更合适(后面将有较详细叙后面将有较详细叙述述)。工商管理学院信息管理教研室二、系统聚类分析的方法二、系统聚类分析的方法 系统聚类法的聚类原则决定于样品间的系统聚类法的聚类原则决定于样品间的距离距离(或相似系数或相似系数)及类间距离的定义，类间及类间距离的定义，类间距离的不同定义就产生了不同的系统聚类分距离的不同定义就产生了不同的系统聚类分析方法。下面介绍常用

47、的几种系统聚类分析析方法。下面介绍常用的几种系统聚类分析方法。方法。工商管理学院信息管理教研室间的距离。ijd)(iX)(jXijr2211ijijijijrdrd或ijDiGjG以下用表示样品和之间的距离，当样品间的亲疏关系采用相似系数时，令；用表示类和1 1、最短距离法、最短距离法(SINgleSINgle linkage)linkage)最短距离法是将类与类之间的距离定义为工商管理学院信息管理教研室两类中最近样品之间的距离，即类之间的距离定义为pGqGpqD和),X其中(min)(i,以下同表示ppijGjGipqGGidDqp工商管理学院信息管理教研室),(,minmin,minmin

48、),(min,qpkDDddGGGdDqkpkijGjGiijGjGiqprijGjGirkkqkpkrpGqGrGrGkG当某步类和合并为后，按最短距离法计算新类与其它类的类间距离，递推公式为工商管理学院信息管理教研室 以下，我们以某地区九个农业区的七项经济指标所形成的距离矩阵，用最短距离聚类法对某地区的九个农业区进行聚类分析。ijdiGjG 从原来的mm距离矩阵，得到一新类后，计算原来各类与新类之间的距离，这样就得到一个新的（m-1）阶的距离矩阵；再从新的距离矩阵中选出最小的，把和归并成新类；再计算各类与新类的距离，这样一直下去，直至各分类对象被归为一类为止。前例前例 九个农业区之间的绝对

49、值距离矩阵如下：工商管理学院信息管理教研室040.132.306.384.451.020.166.162.2003.596.314.529.124.288.032.1007.183.006.493.253.579.5078.199.286.146.472.4077.464.302.686.5023.147.119.2070.210.3052.10)d(D99ij 第一步，在99阶距离矩阵D中，非对角工商管理学院信息管理教研室9410,GGG元素中最小者是，故首先将第51.094d10G4区与第9区并为一类，记为，即1G2G3G5G6G7G8G10G分别按照最短距离法递推公式计算，与之间的距离得

50、：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工商管理学院信息管理教研室工商管理学院信息管理教研室1G2G3G5G6G7G8G10G这样就得到，上的一个新的88阶距离矩