ClusterAnalysis聚类分析实用PPT课件

1、第2讲 聚类分析2.1 2.1 聚类分析的基本思想聚类分析的基本思想2.2 2.2 相似性的度量相似性的度量2.3 2.3 类和类的特征类和类的特征2.4 2.4 系统聚类法系统聚类法2.5 2.5 非系统聚类法简介非系统聚类法简介第1页/共59页 2.1 2.1 聚类分析的基本思想 1.什么是聚类分析？什么是聚类分析？ 所谓所谓“类类”就是就是相似元素的集合。相似元素的集合。聚类就是根据研究对象某一方面的相似性将其聚类就是根据研究对象某一方面的相似性将其归类，使得同一类中的对象之间的相似性比与归类，使得同一类中的对象之间的相似性比与其他类的对象的相似性更强。或者使其他类的对象的相似性更强。或

2、者使类内类内对象对象的同质性最大化和的同质性最大化和类间类间对象的异质性最大化。对象的异质性最大化。2.基本思想基本思想根据研究对象的多个观测指标，具体地找出一根据研究对象的多个观测指标，具体地找出一些能够度量各对象之间相似程度的统计量，然些能够度量各对象之间相似程度的统计量，然后利用统计量将样品或指标进行归类。后利用统计量将样品或指标进行归类。把相似把相似的样品或指标归为一类，把不相似的归为其的样品或指标归为一类，把不相似的归为其他类。直到把所有的样品（或指标）聚合完他类。直到把所有的样品（或指标）聚合完毕毕. . 第2页/共59页2.1 2.1 聚类分析的基本思想3、聚类分析的类型：聚类分

3、析的类型： 对样品分类，称为对样品分类，称为Q Q型聚类分析型聚类分析 对变量分类，称为对变量分类，称为R R型聚类分析型聚类分析 Q Q型聚类是使具有相似性特征的样品聚集在型聚类是使具有相似性特征的样品聚集在一起，使差异性大的样品分离开来。一起，使差异性大的样品分离开来。 R R型聚类是使具有相似性的变量聚集在一起，型聚类是使具有相似性的变量聚集在一起，差异性大的变量分离开来。差异性大的变量分离开来。 R R型聚类可在相似变量中选择少数具有代表型聚类可在相似变量中选择少数具有代表性的变量参与其他分析，实现减少变量个数，性的变量参与其他分析，实现减少变量个数，达到变量降维的目的。达到变量降维的

4、目的。 第3页/共59页2.2 2.2 相似性的度量相似性的度量一、样本或变量的一、样本或变量的相似性相似性程度的数量指标：程度的数量指标： 1、相似系数相似系数 性质越接近的变量或样品，它们的相似系数越接近于1或一l，而彼此无关的变量或样品，它们的相似系数则越接近于0，相似的为一类，不相似的为不同类； 2、距离距离 它是将每一个样品看作p维空间的一个点，并用某种度量方法测量点与点之间的距离，距离较近的归为一类，距离较远的点应属于不同的类。v样品分类（Q型聚类）常以距离距离刻画相似性v变量分类(R型聚类)常以相似系数相似系数刻画相似性第4页/共59页v距离和相似系数有着各种不同的定义，而这些定

5、距离和相似系数有着各种不同的定义，而这些定义与变量类型有着非常密切的关系。义与变量类型有着非常密切的关系。v变量可分为变量可分为定性变量和定量变量。定性变量和定量变量。若按测量尺度若按测量尺度的不同可以分为的不同可以分为： （1 1）间隔尺度变量：变量用连续的量来表示，）间隔尺度变量：变量用连续的量来表示，包括定距和定比尺度，如长度、重量、速度、温包括定距和定比尺度，如长度、重量、速度、温度等。度等。 （2 2）有序尺度变量：变量度量时不用明确的）有序尺度变量：变量度量时不用明确的数量表示，而是用等级来表示，如产品分为一等数量表示，而是用等级来表示，如产品分为一等品、二等品、三等品等有次序关系

6、。品、二等品、三等品等有次序关系。 （3 3）名义尺度变量：变量用）名义尺度变量：变量用既没有既没有数量关系数量关系也没有次序关系，只有一些特性状态，也没有次序关系，只有一些特性状态，如性别、如性别、职业、产品的型号等。职业、产品的型号等。 对于间隔尺度变量，聚类时数据单位往往不同，为为使不同量纲、不同数量级的数据能在一起比较，通常需要先进数据变换处理 第5页/共59页3.常用的数据变换方法), 1;, 2 , 1(*mjnixxxjijij (1) 中心化变换中心化变换 变换后数据的均值为变换后数据的均值为0，而协差阵不变，而协差阵不变. (2) 标准化变换标准化变换 变换后的数据变换后的数

7、据,每个变量的样本均值为每个变量的样本均值为0,标准差为标准差为1, 且标准化变换后的数据且标准化变换后的数据x*ij与变量的量纲无关与变量的量纲无关. (3) 极差标准化变换极差标准化变换 变换后的数据变换后的数据,每个变量的样本均值为每个变量的样本均值为0,极差为极差为1,变变换后的数据也是无量纲的量换后的数据也是无量纲的量.*(1,2, ;1, )ijjijjxxxin jpR*(1,2, ;1, )ijjijjxxxin jps第6页/共59页 (4) 极差正规化变换极差正规化变换(规格化变换规格化变换)变换后的数据变换后的数据0 x*ij 1;极差为极差为1,也是无量纲的量也是无量纲

8、的量. (5) 对数变换对数变换 可将具有指数特征的数据结构化为线性数据结构可将具有指数特征的数据结构化为线性数据结构.*1(1,2, ;1, )miniji nijjxijxin jpRx *log()(0)(1,2, ;1, )ijijijxxxin jp第7页/共59页二、样品间相似性的度量：距离二、样品间相似性的度量：距离 设有n个样品，每个样品测有p个指标（变量），原始资料阵为： 每个样品都可以看成p维空间中的一点，n个样品就是p维空间中的n个点 第i个样品与第j个样品之间的距离记为npnnppxxxxxxxxxX212222111211ijd第8页/共59页1 1、距离公理：、距离

9、公理：v第i个和第j个样品之间的距离 满足如下四个四个性质性质：0;ijdij 对一切的和 成立0;ijdij当且仅当成立;ijjiddij对一切的 和 成立.ijikkjdddij对于一切的和 成立ijd第9页/共59页2 2、常用距离、常用距离：（1 1）明考夫斯基距离）明考夫斯基距离( (Minkowski distance)Minkowski distance) 明氏距离有三种特殊形式：明氏距离有三种特殊形式： （1 1a a）绝对距离（绝对距离（BlockBlock距离）距离）: :当当q=1q=1时时 pkjkikijxxd1111( )(| )pqqijikjkkdqxx （1b

10、)欧氏距离(Euclidean distance):当q=2时（1c)切比雪夫距离:当 时 2112)(2pkjkikijxxdjkikpkijxxd1max)(q第10页/共59页 缺点缺点:(1) 与各变量的量纲有关与各变量的量纲有关; (2) 没有考虑指标间的相关性没有考虑指标间的相关性; (3) 没有考虑各变量方差的不同没有考虑各变量方差的不同.如欧氏距如欧氏距离离,变差大的变量在距离中的作用变差大的变量在距离中的作用(贡献贡献)就会大就会大,这是不合适的这是不合适的. 合理的方法就是对各变量加权合理的方法就是对各变量加权,如用如用1/s2 作为作为权数可得出权数可得出“统计距离统计距

11、离”:*21() ( ,1,2., )pitjtijttxxdi jns第11页/共59页v当各变量的单位不同或测量值范围相差很大时，当各变量的单位不同或测量值范围相差很大时，不应直接采用明氏距离，而应先对各变量的数据不应直接采用明氏距离，而应先对各变量的数据作标准化处理，然后用标准化后的数据计算距离。作标准化处理，然后用标准化后的数据计算距离。常用的标准化处理：常用的标准化处理： 其中 为第j个变量的样本均值； 为第j个变量的样本方差。*1,2, ,1,2, ,ijjijjjxxxinjps11njijixxn211()1njjijjisxxn第12页/共59页（2 2）兰氏距离兰氏距离 当

12、当 时：时： 11pikjkijkikjkxxdLpxx克服量纲的影响克服量纲的影响 未考虑指标间未考虑指标间相关性的影响相关性的影响0;1,2, ;1,2,ijxin jp适用于变量之间互不相关的情形适用于变量之间互不相关的情形第13页/共59页(3) 斜交空间距离斜交空间距离 在在m维空间中维空间中,为使具有相关性变量的谱系结为使具有相关性变量的谱系结构不发生变形构不发生变形,采用斜交空间距离采用斜交空间距离,即即在数据标准化处理下在数据标准化处理下, ,rkl为变量为变量Xk和和Xl之间的相关系数之间的相关系数 第14页/共59页v （4 4）马氏距离）马氏距离克服量纲的影响克服量纲的影

13、响 克服指标间相克服指标间相关性的影响关性的影响)()(2ji1jixxxxijd1/2()()ijd1ijijxxxx缺点：缺点：协方差矩协方差矩阵难以确定阵难以确定第15页/共59页三、变量间相似性的度量：相似系数三、变量间相似性的度量：相似系数v 相似系数（或其绝对值）越大，变量之间的相似性程度越高；反之，越低。聚类时，相似的变量归为一类，不太相似的变量归为不同的类。 变量 与 的相似系数用 表示，满足以下三个条件： ixjxijc1, (0)ijijcxaxb ab 当且仅当和 是常数；1,ijc对一切i,j；,ijjicc对一切i,j。第16页/共59页1 1、夹角余弦、夹角余弦 从

14、向量集合的角度所定义的一种测度变量之间亲疏程度的相似系数。设在从向量集合的角度所定义的一种测度变量之间亲疏程度的相似系数。设在n n维维空间的向量空间的向量niiiixxx,21xnjjjjxxx,21xnknkkjkinkkjkiijijxxxxc11221cos221ijijCd第17页/共59页2 2、相关系数、相关系数设 和是第 和 个变量的观测值，则二者之间的相似测度为:12,iinixxxix12(,)jjnjxxxjxij12211()()() () nkiikjjkijnnkiikjjkkxxxxxxxx相关系数就是对数据作相关系数就是对数据作中心化或标准化处理中心化或标准化处

15、理后的夹角余弦后的夹角余弦.第18页/共59页 至此，我们可以根据所选择的距离构成样本至此，我们可以根据所选择的距离构成样本点间的距离表：点间的距离表：00 0pGqG1G2GnG1G2GnG12dnd121d1nd2ndnd2第19页/共59页2.3 2.3 类和类的特征类和类的特征一、类的定义： 用G表示类，设G中有n个元素，dij表示元素i与j之间的距离类的定义： T为一个给定的阈值，若对于任意的i，jG，有dij T，则称G为一个类。第20页/共59页二、类的特征：二、类的特征： 设类G中有样品 。n为G内的样品数。 （1）类均值（或称为重心） （2）离差、协方差矩阵1,nXX11nG

16、iiXXn1()()nGiGiGisXXXX11GGsn (3)类G的直径 ,m axGijijGDd第21页/共59页 (4)类的离差平方和 对于聚类前的n个样品，可以证明：n个样品总离差平方和聚成k类后各类内离差平方 之和类间离差平方和 令T为总离差平方和，Pk为分为K类的类内离差平方之和。kktiktnitiBPXXXXTt )()()()(11)()(其中其中 kttkSP1)()(XXXXSinii第22页/共59页2.4 2.4 系统聚类法系统聚类法一、系统聚类法的基本思想和步骤 1.是一种其聚类过程可以用所谓的谱系结构或树形结构来描绘的方法。事先不用确定分多少类事先不用确定分多少

17、类 2.基本思想： 先所有的研究对象各自算作一类，将最先所有的研究对象各自算作一类，将最“靠靠近近” 的两个类首先聚类，再将这个新类和其余类的两个类首先聚类，再将这个新类和其余类中最中最“靠近靠近”的类合并，每次缩小一类，直至所的类合并，每次缩小一类，直至所有的对象都合并为一类为止。有的对象都合并为一类为止。 第23页/共59页 系统聚类法的聚类原则决定于样品间的距离系统聚类法的聚类原则决定于样品间的距离( (或相似系数或相似系数) )及类间距离的定义及类间距离的定义, ,类间距离的类间距离的不同定义就产生了不同的系统聚类分析方法不同定义就产生了不同的系统聚类分析方法. .几个记号几个记号:

18、: 用用dij表示样品表示样品X(i)和和X(j)之间的距离之间的距离, 当样品间的亲疏关系采用相似系数当样品间的亲疏关系采用相似系数C Cij ij 时时, , 令令 dij=1-|Cij| (或或 d2ij=1-C2ij);); 用用Dij表示类表示类Gi和和Gj间的距离间的距离. .第24页/共59页3.3.系统聚类法的基本步骤（以系统聚类法的基本步骤（以Q Q型聚类为例）型聚类为例）第25页/共59页二、最短距离（二、最短距离（Nearest Neighbor)Nearest Neighbor) 1.含义： 类间距离定义为两类中距离最近样品之间的距离。x21x12x22x1113d类G

19、p与类Gq之间的距离Dpq (d(xi,xj)表示点xi Gp和xj Gq之间的距离)min ( ,)pqijDd x x第26页/共59页2.应用 对5个样品测量了两个指标，数据如下表： 定义样品间距离为绝对距离，用最短距离法聚类1X2X样品1148样品2159样品3104样品481样品562第27页/共59页根据并类过程绘制的谱系聚类图 第28页/共59页三、最长距离（三、最长距离（Furthest Furthest NeighborNeighbor）1.含义： 定义类间距离为两类中距离最远的样品的距离x11x2112dmax ( ,)pqijDd x x例题：例题：数据如前数据如前第29

20、页/共59页四、中间距离法四、中间距离法PGqGLGrG最长距离最短距离中间距离第30页/共59页2222111224lrlplqpqDDDD递推公式：04121212222，递推公式：pqkqkpkrDDDD中间距离法的递推公式 若在某步聚类中将类p与q合并为类r，则任一类k与新类r的距离： 当=-0.25时，为三角形中线：第31页/共59页五、重心法（五、重心法（Centroid clustering):Centroid clustering):含义： 两类间的距离定义为两类重心(均值点)之间的的距离11,x y22,xy例题：例题：数据如前数据如前第32页/共59页v 样品间距离为欧氏距

21、离时的递推公式2222pqrqrpkqrqkprpkrDnnnnDnnDnnDrqpnnnGrGt第33页/共59页重心法虽有较好的代表性重心法虽有较好的代表性, ,但并未充分利用各但并未充分利用各个样品的信息个样品的信息. .比如下面两组类按重心法类间比如下面两组类按重心法类间距离相等距离相等, ,这是不合理的这是不合理的. .第34页/共59页六、类平均法(Between-group Linkage)含义：类间距离为所有含义：类间距离为所有样品对样品对间的平均距离。间的平均距离。991ddv利用了所有样品对距离的信息第35页/共59页 类与类之间的距离平方为两类样品两两之间类与类之间的距离

22、平方为两类样品两两之间的距离平方的平均的距离平方的平均, ,即即2,21ijGjGiqppqdnnDqp类平均法的类间距离：合并新类的距离递推公式：合并新类的距离递推公式： 设某一步将设某一步将Gp和和Gq合并成合并成Gr, ,它们所包含的样它们所包含的样品个数分别为品个数分别为np , ,nq和和nr( (nr= =np+ +nq).).Gr与其他类与其他类Gk的类间距离的递推公式为的类间距离的递推公式为),(222qpkDnnDnnDqkrqpkrprk第36页/共59页七七. .离差平方和法离差平方和法 ( (Wards method ) )v 类似于方差分析的想法，如果类分得恰当，同类

23、内的样品之间的离差平方和应较小，而类间的离差平方和应当较大。 2222pqkrkkqkrqkkpkrpkkrDnnnDnnnnDnnnnD2222qprpqSSSD的增量：定义距离为离差平方和其中 是由Gp和Gq合并成的Gr类的类内离差平方和。可以证明离差平方和法的类间递推公式为2rS)()(2qPqPqpqppqXXXXnnnnD例题：例题：数据如前数据如前第37页/共59页八、系统聚类法的软件实现SPSSSPSS以教材以教材8888页例题页例题1 1为例，为例，SPSSSPSS处理：处理： 1 1、AnalyzeAnalyzeClassifyClassifyHierarchical Clu

24、sterHierarchical Cluster 2 2、把、把dxbzdxbz、czbzczbz、wmbzwmbz选入选入VariablesVariables 3 3、若对样品聚类（、若对样品聚类（Q Q型聚类）：在型聚类）：在ClusterCluster选选CasesCases； 若对变量聚类（若对变量聚类（R R型聚类）则在型聚类）则在ClusterCluster选选VariablesVariables 4 4、选、选PlotsPlots，再点，再点DendrogramDendrogram，则则画出树状图；画出树状图； 若若点点Icicle，则则画出冰挂图画出冰挂图，其中，其中Orien

25、tation中中（Vertical为纵为纵向冰挂图；向冰挂图；Horizontal为横向冰挂图）。为横向冰挂图）。 .第38页/共59页九、 系统聚类法的基本性质 （一） 单调性 在聚类分析过程中，并类距离分别为l k（k=1，2，3，）若满足 ，则称该聚类方法具有单调性。可以证明除了重心法和中间距离法之外，其他的系统聚类法均满足单调性的条件。121kkllll（二）空间的浓缩和扩张 1、定义矩阵的大小 设同阶矩阵D（A）和D（B），如果D（A）的每一个元素 小于D（B）的每一个元素，则记为 。)()(BDAD第39页/共59页 2、空间的浓缩和扩张 设有两种系统聚类法A和B，他们在第i步的距

26、离矩阵分别为Ai和Bi（I=1，2，3），若AiBi ，则称第一种方法A比第二种方法B使空间扩张，或第二种方法比第一种方法浓缩。 3、方法的比较 D（短） D（平），D（重） D（平）； D（长） D（平）； 当 ，D（变平） D（平）； 当 ，D（变平） D（平）。10 0 第40页/共59页 1.1.由适当的阈值确定由适当的阈值确定 介绍系统聚类法的基本步骤时介绍系统聚类法的基本步骤时,由由谱系聚类图谱系聚类图及临界值及临界值,即可给出分类结果即可给出分类结果. 2.2.根据数据点的散布图直观地确定类的个数根据数据点的散布图直观地确定类的个数 3.3.根据谱系图确定分类个数的根据谱系图确定

27、分类个数的准则准则 4.4.根据根据统计量统计量确定分类个数确定分类个数十、确定类个数的几种常见方法：第41页/共59页黛米尔曼（黛米尔曼（Demirmen,1972)Demirmen,1972)提出依据树状结构图分类的准则：提出依据树状结构图分类的准则：第42页/共59页 由由 Rk2的定义的定义 可知可知 , Rk2值越大值越大，也就是，也就是Pk/ /T越小，越小，表示表示k个类内离差平方和之和个类内离差平方和之和Pk在总离差平方和在总离差平方和T中占中占的比例越小的比例越小, ,这这说明说明k个类区分得越开个类区分得越开. . Rk2的值总是的值总是在在0 0和和1 1之间，而且之间，

28、而且Rk2的值总是随着分类个数的值总是随着分类个数k的减少的减少而变小而变小,12TBTPRkkk十一、聚类效果评价统计量所以我们只能取合适的K，使得R2足够大，而K本身较小，且随着K的增加， R2的增幅不大。1、Rk2统计量第43页/共59页 用于评价聚为K个类的效果。如果聚类的效果好，类间的离差平方和相对于类内的离差平方和应比较大，所以应该取伪F F统计量较大而类数较小的聚类水平。 () (1)()kkTPkFPnk2.伪F统计量第44页/共59页 其中WK和WL分别是类K、L的类内离差平方和，BKL是将K和L合并为第M类所增加离差平方和 BKL = WM - WK - WL 为合并导致的

29、类内离差平方和的增量。用它评价合并第K K和L L类的效果，伪 统计量大说明不应该合并这两类，应该取合并前的水平。2t)2()(2LKLKKLNNWWBt2t3.伪 统计量第45页/共59页2.5 2.5 非系统聚类法简介非系统聚类法简介v动态聚类法动态聚类法: :也叫做逐步聚类法、也叫做逐步聚类法、k-k-均值聚类法、或快速聚类均值聚类法、或快速聚类法。法。事先要确定分多少类事先要确定分多少类第46页/共59页选择凝聚点分 类修改分类分类是否合理分类结束YesNo第47页/共59页 用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。快速聚类的步骤： 1、随机选取两个点

30、 和 作为聚核。 2、对于任何点 ，分别计算 3、若 ，则将 划为第一类，否则划给第二类。于是得图（c）的两个类。 )1 (1x)1 (2xkx),(),()1(2)1(1xxdxxdkk和),(),()1(2)1(1xxdxxdkkkx 4、分别计算两个类的重心，则得 和 ，以其为新的聚核，对空间中的点进行重新分类，得到新分类。)2(1x)2(2x第48页/共59页 （a）空间的群点 (b) 任取两个聚核 (c) 第一次分类 (d) 求各类中心第49页/共59页 (e) 第二次分类第50页/共59页 如此叠代下去，直到达到停止叠代的要求（比如，各类最后变化不大了，或者叠代次数太多了）。如此叠代下去，直到达到停止叠代的要求（比如，各类最后变化不大了，或者叠代次数太多了）。 下面用一个例子来做下面用一个例子来做k-k-均值聚类。均值聚类。第51页/共59页 【例】假定我们对A、B、C、D四个样品分别测量两个变量和得到结果见下表试将以上的样品聚成两类。 第52页/共59页第一步：按要求取K=2，为了实施K均值法聚类，我们将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标，见下表所示。