Cluster-Analysis(聚类分析).ppt

1、经济管理类研究生专业学位课,Multivariate Statistics Analysis 多元统计分析,第2讲 聚类分析,2.1 聚类分析的基本思想,2.2 相似性的度量,2.3 类和类的特征,2.4 系统聚类法,2.5 非系统聚类法简介,2.1 聚类分析的基本思想,1.什么是聚类分析？ 所谓“类”就是相似元素的集合。 聚类就是根据研究对象某一方面的相似性将其归类，使得同一类中的对象之间的相似性比与其他类的对象的相似性更强。或者使类内对象的同质性最大化和类间对象的异质性最大化。 2.基本思想 根据研究对象的多个观测指标，具体地找出一些能够度量各对象之间相似程度的统计量，然后利用统计量将样品

2、或指标进行归类。把相似的样品或指标归为一类，把不相似的归为其他类。直到把所有的样品（或指标）聚合完毕.,2.1 聚类分析的基本思想,3、聚类分析的类型： 对样品分类，称为Q型聚类分析 对变量分类，称为R型聚类分析 Q型聚类是使具有相似性特征的样品聚集在一起，使差异性大的样品分离开来。 R型聚类是使具有相似性的变量聚集在一起，差异性大的变量分离开来。 R型聚类可在相似变量中选择少数具有代表性的变量参与其他分析，实现减少变量个数，达到变量降维的目的。,2.2 相似性的度量,一、样本或变量的相似性程度的数量指标： 1、相似系数 性质越接近的变量或样品，它们的相似系数越接近于1或一l，而彼此无关的变量

3、或样品，它们的相似系数则越接近于0，相似的为一类，不相似的为不同类； 2、距离 它是将每一个样品看作p维空间的一个点，并用某种度量方法测量点与点之间的距离，距离较近的归为一类，距离较远的点应属于不同的类。 样品分类（Q型聚类）常以距离刻画相似性 变量分类(R型聚类)常以相似系数刻画相似性,距离和相似系数有着各种不同的定义，而这些定义与变量类型有着非常密切的关系。 变量可分为定性变量和定量变量。若按测量尺度的不同可以分为： （1）间隔尺度变量：变量用连续的量来表示，包括定距和定比尺度，如长度、重量、速度、温度等。 （2）有序尺度变量：变量度量时不用明确的数量表示，而是用等级来表示，如产品分为一等

4、品、二等品、三等品等有次序关系。 （3）名义尺度变量：变量用既没有数量关系也没有次序关系，只有一些特性状态，如性别、职业、产品的型号等。 对于间隔尺度变量，聚类时数据单位往往不同，为为使不同量纲、不同数量级的数据能在一起比较，通常需要先进数据变换处理,3.常用的数据变换方法,(1) 中心化变换 变换后数据的均值为0，而协差阵不变. (2) 标准化变换 变换后的数据,每个变量的样本均值为0,标准差为1, 且标准化变换后的数据x*ij与变量的量纲无关. (3) 极差标准化变换 变换后的数据,每个变量的样本均值为0,极差为1,变换后的数据也是无量纲的量.,(4) 极差正规化变换(规格化变换) 变换后

5、的数据0 x*ij 1;极差为1,也是无量纲的量. (5) 对数变换 可将具有指数特征的数据结构化为线性数据结构.,二、样品间相似性的度量：距离,设有n个样品，每个样品测有p个指标（变量），原始资料阵为： 每个样品都可以看成p维空间中的一点，n个样品就是p维空间中的n个点 第i个样品与第j个样品之间的距离记为,1、距离公理：,第i个和第j个样品之间的距离 满足如下四个性质：,2、常用距离：,（1）明考夫斯基距离(Minkowski distance) 明氏距离有三种特殊形式： （1a）绝对距离（Block距离）:当q=1时,（1b)欧氏距离(Euclidean distance):当q=2时

6、（1c)切比雪夫距离:当 时,缺点:(1) 与各变量的量纲有关; (2) 没有考虑指标间的相关性; (3) 没有考虑各变量方差的不同.如欧氏距离,变差大的变量在距离中的作用(贡献)就会大,这是不合适的. 合理的方法就是对各变量加权,如用1/s2 作为权数可得出“统计距离”:,当各变量的单位不同或测量值范围相差很大时，不应直接采用明氏距离，而应先对各变量的数据作标准化处理，然后用标准化后的数据计算距离。常用的标准化处理： 其中 为第j个变量的样本均值； 为第j个变量的样本方差。,（2）兰氏距离 当 时：,克服量纲的影响,未考虑指标间相关性的影响,适用于变量之间互不相关的情形,(3) 斜交空间距离

7、 在m维空间中,为使具有相关性变量的谱系结构不发生变形,采用斜交空间距离,即,在数据标准化处理下,rkl为变量Xk和Xl之间的相关系数,（4）马氏距离,克服量纲的影响,克服指标间相关性的影响,缺点：协方差矩阵难以确定,三、变量间相似性的度量：相似系数,相似系数（或其绝对值）越大，变量之间的相似性程度越高；反之，越低。聚类时，相似的变量归为一类，不太相似的变量归为不同的类。 变量 与 的相似系数用 表示，满足以下三个条件：,1、夹角余弦,从向量集合的角度所定义的一种测度变量之间亲疏程度的相似系数。设在n维空间的向量,2、相关系数,设 和 是第 和 个变量的观测值，则二者之间的相似 测度为:,相关

8、系数就是对数据作中心化或标准化处理后的夹角余弦.,至此，我们可以根据所选择的距离构成样本点间的距离表：,2.3 类和类的特征,一、类的定义： 用G表示类，设G中有n个元素，dij表示元素i与j之间的距离 类的定义： T为一个给定的阈值，若对于任意的i，jG，有dij T，则称G为一个类。,二、类的特征： 设类G中有样品 。n为G内的样品数。 （1）类均值（或称为重心） （2）离差、协方差矩阵,(3)类G的直径,(4)类的离差平方和 对于聚类前的n个样品，可以证明： n个样品总离差平方和聚成k类后各类内离差平方 之和类间离差平方和 令T为总离差平方和，Pk为分为K类的类内离差平方之和。,其中,2

9、.4 系统聚类法,一、系统聚类法的基本思想和步骤 1.是一种其聚类过程可以用所谓的谱系结构或树形结构来描绘的方法。事先不用确定分多少类 2.基本思想： 先所有的研究对象各自算作一类，将最“靠近” 的两个类首先聚类，再将这个新类和其余类中最“靠近”的类合并，每次缩小一类，直至所有的对象都合并为一类为止。,系统聚类法的聚类原则决定于样品间的距离(或相似系数)及类间距离的定义,类间距离的不同定义就产生了不同的系统聚类分析方法.,几个记号: 用dij表示样品X(i)和X(j)之间的距离, 当样品间的亲疏关系采用相似系数Cij 时, 令 dij=1-|Cij| (或 d2ij=1-C2ij); 用Dij

10、表示类Gi和Gj间的距离.,3.系统聚类法的基本步骤（以Q型聚类为例）,二、最短距离（Nearest Neighbor),1.含义： 类间距离定义为两类中距离最近样品之间的距离。,类Gp与类Gq之间的距离Dpq (d(xi,xj)表示点xi Gp和xj Gq之间的距离),2.应用,对5个样品测量了两个指标，数据如下表： 定义样品间距离为绝对距离，用最短距离法聚类,根据并类过程绘制的谱系聚类图,三、最长距离（Furthest Neighbor）,1.含义： 定义类间距离为两类中距离最远的样品的距离,例题：数据如前,四、中间距离法,最长距离,最短距离,中间距离,中间距离法的递推公式,若在某步聚类中

11、将类p与q合并为类r，则任一类k与新类r的距离： 当=-0.25时，为三角形中线：,五、重心法（Centroid clustering):,含义： 两类间的距离定义为两类重心(均值点)之间的的距离,例题：数据如前,样品间距离为欧氏距离时的递推公式,Gr,Gt,重心法虽有较好的代表性,但并未充分利用各个样品的信息.比如下面两组类按重心法类间距离相等,这是不合理的.,六、类平均法(Between-group Linkage),含义：类间距离为所有样品对间的平均距离。,利用了所有样品对距离的信息,类与类之间的距离平方为两类样品两两之间的距离平方的平均,即,类平均法的类间距离：,合并新类的距离递推公式

12、： 设某一步将Gp和Gq合并成Gr,它们所包含的样品个数分别为np ,nq和nr(nr=np+nq).Gr与其他类Gk的类间距离的递推公式为,七.离差平方和法 (Wards method ),类似于方差分析的想法，如果类分得恰当，同类内的样品之间的离差平方和应较小，而类间的离差平方和应当较大。,其中 是由Gp和Gq合并成的Gr类的类内离差平方和。可以证明离差平方和法的类间递推公式为,例题：数据如前,八、系统聚类法的软件实现SPSS,以教材88页例题1为例，SPSS处理： 1、AnalyzeClassifyHierarchical Cluster 2、把dxbz、czbz、wmbz选入Varia

13、bles 3、若对样品聚类（Q型聚类）：在Cluster选Cases； 若对变量聚类（R型聚类）则在Cluster选Variables 4、选Plots，再点Dendrogram，则画出树状图； 若点Icicle，则画出冰挂图，其中Orientation中（Vertical为纵向冰挂图；Horizontal为横向冰挂图）。 .,九、 系统聚类法的基本性质,（一） 单调性 在聚类分析过程中，并类距离分别为l k（k=1，2，3，）若满足 ，则称该聚类方法具有单调性。可以证明除了重心法和中间距离法之外，其他的系统聚类法均满足单调性的条件。,（二）空间的浓缩和扩张,1、定义矩阵的大小 设同阶矩阵D（

14、A）和D（B），如果D（A）的每一个元素 小于D（B）的每一个元素，则记为 。,2、空间的浓缩和扩张 设有两种系统聚类法A和B，他们在第i步的距离矩阵分别为Ai和Bi（I=1，2，3），若AiBi ，则称第一种方法A比第二种方法B使空间扩张，或第二种方法比第一种方法浓缩。,3、方法的比较,D（短） D（平），D（重） D（平）； D（长） D（平）； 当 ，D（变平） D（平）； 当 ，D（变平） D（平）。,1.由适当的阈值确定 介绍系统聚类法的基本步骤时,由谱系聚类图及临界值,即可给出分类结果. 2.根据数据点的散布图直观地确定类的个数 3.根据谱系图确定分类个数的准则 4.根据统计量确定

15、分类个数,十、确定类个数的几种常见方法：,黛米尔曼（Demirmen,1972)提出依据树状结构图分类的准则：,由 Rk2的定义 可知 , Rk2值越大，也就是Pk/T越小，表示k个类内离差平方和之和Pk在总离差平方和T中占的比例越小,这说明k个类区分得越开. Rk2的值总是在0和1之间，而且Rk2的值总是随着分类个数k的减少而变小,十一、聚类效果评价统计量,所以我们只能取合适的K，使得R2足够大，而K本身较小，且随着K的增加， R2的增幅不大。,1、Rk2统计量,用于评价聚为K个类的效果。如果聚类的效果好，类间的离差平方和相对于类内的离差平方和应比较大，所以应该取伪F统计量较大而类数较小的聚

16、类水平。,2.伪F统计量,其中WK和WL分别是类K、L的类内离差平方和，BKL是将K和L合并为第M类所增加离差平方和 BKL = WM - WK - WL 为合并导致的类内离差平方和的增量。用它评价合并第K和L类的效果，伪 统计量大说明不应该合并这两类，应该取合并前的水平。,3.伪 统计量,2.5 非系统聚类法简介,动态聚类法:也叫做逐步聚类法、k-均值聚类法、或快速聚类法。事先要确定分多少类,选择凝聚点,分 类,修改分类,分类是否合理,分类结束,Yes,No,用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。快速聚类的步骤： 1、随机选取两个点 和 作为聚核。 2、对

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

18、、D），然后计算这两个聚类的中心坐标，见下表所示。 表中的中心坐标是通过原始数据计算得来的，比如（A、 B）类的， 等等。,第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类的平方距离： 由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配。计算B到两类的平方距离：,由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类，得到新的聚类是（A）和（B、C、D）。更新中心坐标如下表所示。,第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，得结果见下表。 到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得到K=2的聚类结果是A独自成一类，B、C、D聚成一类。,表 样品聚类结果,K-均值聚类SPSS处理： 1、AnalyzeClassifyK-Menas Cluster 2、Variables： 3、Number of Clusters处选择3（想要分的类数） 4、如果想要知道每个样品分到哪类，则选Save