《聚类分析》课件.ppt

1,第06章 聚类分析,2,聚类分析的基本思想及意义,聚类分析是研究分类问题的多元数据分析方法聚类分析是数值分类学的一分支 在经济学中有广泛的应用背景 城镇居民收入分析 产品质量指标 等等,3,聚类分析的基本思想及意义,聚类分析的基本思想是在样品之间定义距离，在变量之间定义相似系数，距离或相似系数代表样品或变量之间的相似程度。按相似程度的大小，将样品（或变量）逐一归类，关系密切的类聚集到一个小的分类单位，然后逐步扩大，使得关系疏远的聚合到一个大的分类单位，直到所有的样品（或变量）都聚集完毕，形成一个表示亲疏关系的谱系图，依次按照某些要求对样品（或变量）进行分类。,4,聚类分析的基本思想及意义,多元数据形成数据矩阵，在这个数据矩阵中，共有n个样品（列向），p个指标（行向）。聚类分析有两种类型：按样品聚类或按变量（指标）聚类。,5,聚类分析与判别分析的区别和联系,聚类分析一般寻求客观的分类方法。在进行聚类之前，对总体到底有几类类型并不知道（究竟分几类较为合适需从计算中探索调整）。判别分析则是在总体类型划分已知，在各总体分布或来自总体训练样本基础上，对当前的新样本判定它们属于哪个总体。联系：例如当我们对研究的多元数据的特征不熟悉，就要先进行聚类分析，才能考虑判别分析问题。,6,聚类分析的方法,重点介绍 谱系聚类法 快速聚类法,7,样品间的相似性度量距离,设有n个样品的多元观测数据：每个样品可看成p元空间的一个点，n个样品组成p元空间的n个点。我们用各点之间的距离来衡量各种样品之间的相似程度（或靠近程度）。,8,样品间的相似性度量距离,设 是样品 之间的距离，一般要求它满足下列条件：在聚类分析中，有些距离不满足3），我们在广义的角度上仍称它为距离。,9,聚类分析中的常用距离,欧式距离 令，形成一个距离矩阵 其中。,10,例 6.1,为研究辽宁、浙江、河南、甘肃、青海5省份1991年城镇居民生活消费规律，需要利用调查资料对这5个省分类。指标变量共8个，含义如下：x1：人均粮食支出，x2：人均副食支出，x3：人均烟酒茶支出，x4：人均其他副食支出，x5：人均衣着商品支出，x5：人均日用品支出，x7：人均燃料支出，x8：人均非商品支出。数据资料示于表6.2。将每个省份的数据看成一个样 品，计算样品之间的欧式距离矩阵。,11,例 6.1,表6.2 1991年5省城镇居民月均消费（单位：元/人）,12,例 6.1,解 以1，2，3，4，5分别表示辽宁、浙江、河南、甘肃、青海5个省（样品）。计算每两个样品之间的欧式距离 如,13,例 6.1,从而得到距离矩阵如下：（因是对称矩阵，故只用下三角部分表示）。D中各元素数值的大小，反映了5个省消费水平的接近程度。,14,聚类分析中的常用距离,绝对距离Minkowski距离 其中。当 时分别是欧式距离、绝对距离。Minkowski距离又称 距离，距离即欧式距离，距离即绝对距离。,15,聚类分析中的常用距离,Chebyshev距离 Chebyshev距离是Minkowski距离当 时的极限。,16,聚类分析中的常用距离,以上距离与各变量指标的量纲有关，为消除量纲的影响，有时应先对数据进行标准化，然后用标准化数据计算距离。标准化数据 其中,17,聚类分析中的常用距离,方差加权距离 对标准化数据 计算欧式距离时，即是方差加权距离。,18,聚类分析中的常用距离,马氏距离 其中 是由样品 算得的协方差矩阵：其中,19,样品间的相似性度量距离,Q型聚类：样品聚类在SAS系统中，采用欧式距离聚类或先将数据标准化，再计算欧式距离进行聚类。（实际上就是采用了方差加权距离）,20,变量间的相似性度量相似系数,当对p个指标变量进行聚类时，用相似系数来衡量变量之间的相似性程度（或关联性程度）。一般的，若 表示变量 之间的相似系数，应满足：,21,变量间的相似性度量相似系数,相关系数 设由样品 算得协方差矩阵S与相关矩阵R。设 则变量 的相关系数为,22,变量间的相似性度量相似系数,是变量 的观测值 与 的观测值 间的相关系数。,23,变量间的相似性度量相似系数,夹角余弦 设变量 的观测值各为 与 其夹角余弦为,24,例 6.2,设 为两个二态变量（设只取0，1两个值），其观测值向量 和（注意分量只由0，1构成）可总结为下列联表形式：求（1）的相关系数；（2）的夹角余弦。,25,例 6.2,解（1）注意：,26,27,例 6.2,又,28,例 6.2,同理因此,29,例 6.2,（2）因为所以,30,变量间的相似性度量相似系数,变量聚类通常称为R型聚类。在R型聚类中，相似矩阵 是出发点。相似系数矩阵可以是相关矩阵，也可以是夹角余弦矩阵，Spearman相关矩阵。,31,变量间的相似性度量相似系数,有时变量之间也可以用距离来描述它们的接近程度。距离和相似系数之间可以相互转化。设 是一个距离，则 是相似系数，若 是相似系数，则可令 或 或,32,谱系聚类法,谱系聚类法是目前应用很广泛的一种聚类方法。谱系聚类法的思想重点讨论：Q型聚类问题。关键：定义类与类的距离,33,类间距离,以 分别表示样品，以 简记 与 的距离 分别表示两个类，设它们分别含有 个样品。若类 中有样品，则其均值 称为类 的重心。,34,类间距离,由于类的形式和形状多种多样，所以类与类之间的距离有多种定义与计算方法。下面我们介绍类间距离的定义。类 与 之间的距离记为。（1）最短距离 即用两类中样品之间的距离最短者作为两类距离。,35,类间距离,（2）最长距离即用两类中样品之间的距离最长者作为两类距离。（3）类平均距离即用两类中所有两两样品之间的距离平均作为两类之间的距离。类平均距离还可用下列方式定义：,36,类间距离,（4）重心距离 其中 分别是 的重心。这是用两类的重心之间的距离作为两类距离。（5）离差平方和距离对重心法而言，。,37,类间距离的递推公式,按照谱系聚类法的思想，先将样品聚合成小类，再逐步扩大为大类。设类 由类 合并所得，则 包含 个样品。问题：由 与其他类 的距离计算 与 的距离 建立类间距离的递推公式,38,类间距离的递推公式,类间距离的递推方式（1）最短距离事实上,39,类间距离的递推公式,类间距离的递推方式（2）最长距离事实上,40,类间距离的递推公式,类间距离的递推方式（3）类平均距离事实上,41,类间距离的递推公式,类间距离的递推方式（3）类平均距离对于类平均距离的下列定义方式：可得递推公式,42,类间距离的递推公式,类间距离的递推方式（4）重心距离事实上，由 的合并集 的重心是而,43,类间距离的递推公式,类间距离的递推方式（4）重心距离由有,44,类间距离的递推公式,类间距离的递推方式（5）离差平方和距离若记 是离差平方和距离，是重心平方距离，则有,45,类间距离的递推公式,在一定条件下，以上介绍的5种类间距离的递推公式可以构成统一的形式。假定样品之间的距离皆采用欧式平方距离，即 则类间距离递推公式有统一的形式：,46,类间距离的递推公式,表6.3 类间距离的参数,47,类间距离的递推公式,注,48,谱系聚类法的步骤,以Q型聚类为例说明谱系聚类法的步骤1）n个样品开始时作为n个类，计算两两之间的距 离，构成一个对称距离矩阵此时，。,49,谱系聚类法的步骤,2）选择 中的非对角线上的最小元素，设这个最小元素是。这时。将 合并成一个新类。在 中消去 所对应的行与列，并加入由新类 与剩下的其他未聚合的类间的距离组成的一行和一列，得到一个新的距离矩阵，它是n-1阶方阵。,50,谱系聚类法的步骤,3）从 出发重复步骤2的作法得。再由 出发重复上述步骤，直到n个样品聚为1个大类为止。4）在合并过程中要记下合并样品的编号及两类合并时的水平（即距离）并绘制聚类谱系图。,51,谱系聚类PROCCLUSTER过程,Proc cluster过程提供了最短距离法（Single Linkage）、最长距离法（Complete linkage）、类平均法（Average linkage）、重心法（Centroid method）等11种谱系聚类方法。,52,谱系聚类PROCCLUSTER过程,基本语句 PROCCLUSTER options；VAR variables;ID variable;,53,谱系聚类PROCCLUSTER过程,PROCCLUSTER options；1）DATASAS data set：该语句指出要进行聚类分析的SAS数据集名称，它可以是含各观测向量的原始数据集，也可以是“距离”矩阵（TYPE DISTANCE），其中“距离”可以是通常的欧氏距离，也可以是其他的距离或变换后的相似度量。若是原始观测数据，则每个数据向量被当作欧氏空间中的坐标点以计算欧氏距离矩阵。,54,谱系聚类PROCCLUSTER过程,注意 本过程总是按照距离矩阵中的元素取值由小到大聚类，因此当使用相似度量矩阵对变量聚类时，要首先对相似度量矩阵中的元素作变换，使得值小的元素对应两个更相似的变量，通常采用的变换为、或 等，这里 为原相似度量矩阵中的元素。,55,谱系聚类PROCCLUSTER过程,PROCCLUSTER options；2）OUTTREESAS data set：生成一个用于画聚类谱系图的输出数据集。若省略此句，则SAS系统自动用DATA1，DATA2，规则命名这种数据集。3）METHODname：此语句是本过程必需的，它指出具体使用的聚类方法。它可以是SAS系统中包含的11种方法的任何一种。主要有：,56,谱系聚类PROCCLUSTER过程,SINGLE（或SIN）：要求使用最短距离法。COMPLETE（或COM）：要求使用最长距离法。AVERAGE（或AVE）：要求使用类平均法。在此过程中类平均法使用欧氏距离的平方，若不需要再平方，可在“options”部分写上“NOSQUARE”。CENTROID（或CEN）：要求使用重心法。如果 不规定“NOSQUARE”，则距离数据被平方。,57,谱系聚类PROCCLUSTER过程,MEDIAN（或MED）：要求使用中间距离法。若不规定“NOSQUARE”选项，则使用平方距离。WARD（或WAR）：要求使用WARD最小方差法。若不规定“NOSQUARE”选项，则使用平方距离。,58,谱系聚类PROCCLUSTER过程,PROCCLUSTER options；4）NOSQUARE：阻止过程在METHODAVERAGE、CENTROID、MEDIAN或WARD方法中将输入的距离平方。5）NONORM：阻止将距离规范化。6）PSEUDO：要求打印伪F统计量及伪 统计量的值。只有当输入数据是原始观测数据（但“METHOD”选项不能是SIN）或“METHOD”选项是AVE、CEN或WAR时，才可选此项。,59,谱系聚类PROCCLUSTER过程,PROCCLUSTER options；7）RSQUARE（或RSQ）：要求打印出 统计量和半偏相关统计量SPRSQ的值。当输入数据是原始观测数据且“METHOD”选项是AVE或CEN时，才可选此项。,60,谱系聚类PROCCLUSTER过程,VAR variables；此语句的“variables”部分列出参与聚类分析的数值变量名称。若省略此句，则未列在其他语句（如其后的ID语句）中的数值变量均参与分析。,61,谱系聚类PROCCLUSTER过程,ID variables；ID变量的值用以表述各样品的名称，它通常时定性变量。若该语句被省略，该过程自动将各样品（或变量）命名为“OBn”，其中n表示第n个样品（或变量）。,62,谱系聚类PROCTREE过程,用于画出谱系图基本语句：PROC TREE options；ID variable；,63,谱系聚类PROCTREE过程,PROC TREE options；1）HORIZONTAL：表示谱系图水平放置。2）VERTICAL：表示谱系图垂直放置。3）SPACESm：表示各ID变量值的间隔单位，这里m是正整数。4）GRAPHICS：要求画高分辨率的聚类谱系图。5）NCLUSTERSm：指定在输出分类结果数据集中所分成的类的个数。6）OUTSAS data set：输出分类结果。,64,例 6.3,从例6.1算得的样品间的欧氏距离矩阵出发用下列方法进行谱系聚类。（1）最短距离法；（2）最长距离法；（3）类平均距离法。,65,例 6.3,解 分别用1，2，3，4，5表示辽宁、浙江、河南、甘肃、青海5个省。将距离矩阵记为，,66,例 6.3,（1）最短距离法。先将5个省各看成一类，即，。有 从 看出，最小，故将 在水平2.20上合并成一个新类。计算 与 之间的最短距离，得,67,例 6.3,在 中划去 所对应的行和列，并加上新类 到其他类的距离作为新的一行一列，得到：,68,例 6.3,从 看到，到 的距离最小，为2.21。在水平2.21上将 合并得，计算 与 的距离：在 中划去 和 所对应的行和列，加上 的相应行列，得到：,69,例 6.3,中最短距离是，故在水平11.67上合并得新类。至此仅有两类 和，其距离为从而得到最后在水平12.80上将 合为1个包含所有省份的大类。,70,71,72,73,74,75,76,77,例 6.4,欧洲各国语言有许多相似之处，有的甚至十分相近。以E，N，Da，Du，G，Fr，S，I，P，H，Fi分别表示英语、挪威语、丹麦语、荷兰语、德语、法语、西班牙语、意大利语、波兰语、匈牙利语和芬兰语这11种语言。人们以任两种语言对110这十个数字拼写中第一个字母不相同的个数定义两种语言间的“距离”。这种“距离”是广义距离。例如，英语和挪威语只有数字1和8的第一个字母不同，故这两种语言间的距离定义为2。这样得到11种语言间的距离矩阵如下：,78,例 6.4,用下列方法对这11种语言进行谱系聚类：（1）最短距离法，并画谱系图；（2）最长距离法，并画谱系图；（3）类平均距离法，并画谱系图；（4）重心距离法；（5）离差平方和距离法（Ward法）,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,分为3类,97,98,99,100,101,谱系聚类法的统计量,一个较好的聚类应该在类内各样品尽可能相似的前提下，使得类的个数尽可能少。主要用到以下几种统计量 统计量 半偏相关统计量 伪F统计量 伪 统计量,102,统计量,设某谱系水平上类的个数是G。类 中样品的类内离差平方和为 其中 是类 的重心。越小，说明 中各样品越相似。,103,统计量,在谱系的第G层共有G个类。定义 又以T记所有样品的总离差平方和，其中,104,统计量,定义 统计量为 统计量可用于评价每次合并时的聚类效果。显然 1）n个样品各为一类时，；2）n个样品合并成一类时，。3）的值总是随着分类数目的减少而减小，取快速 下降的上一类。,105,半偏相关统计量,这一统计量与离差平方和距离有关。设类 的离差平方和分别是 将 合并成 后，离差平方和,106,半偏相关统计量,其中 合并后离差平方和的增加量为,107,半偏相关统计量,由类 合并成类 时的半偏相关统计量SPRSQ为 SPRSQ是上一步 值与该步 值的差值。当SPRSQ值越大时，说明上一次合并效果越好。,108,伪F统计量,伪F统计量PSF是 PSF值越大表示这些观测可显著地分为G个类。,109,伪 统计量,伪 统计量PST2是 PST2大，说明合并 为 后，使得离差平方和的增量 相对于原 的类内离差平方和大。这表明合并的两个类是很分开的。也就是上一次聚类效果较好。,110,例 6.5,对例5.2提供的数据进行聚类分析。考察第127号省市区，指标变量的含义如例5.2所述，省市区的编号如下：1.山西 2.内蒙古 3.吉林 4.黑龙江 5.河南 6.甘肃 7.青海 8.河北 9.陕西 10.宁夏 11.新疆 12.湖北 13.云南 14.湖南 15.安徽 16.贵州 17.辽宁 18.四川 19.山东 20.江西 21.福建 22.广西 23.海南 24.天津 25.江苏 26.浙江 27.北京,111,例 6.5,利用下列聚类法将上述样品进行分类，分析分几类为合适，并写出各种聚类方法得到的分类结果。（1）最长距离法；（2）类平均距离法；（3）重心距离法；（4）离差平方和距离法；,112,113,114,115,116,117,变量聚类,变量聚类称为R型聚类。变量聚类一般从数据的相关矩阵R出发，设变量 的数据的相关矩阵是,118,变量聚类,从R矩阵的元素，经变换 得到距离矩阵,119,例6.6,对某地超基性岩的一批样品，测试6个与矿化有关的元素:x1(镍),x2(钴),x3(铜),x4(铬),x5(硫),x6(砷),计算得到他们的相关矩阵是,120,例6.6,解 计算距离矩阵，,121,122,123,124,125,126,快速聚类法,在谱系聚类法中，因为样品一旦被归到某个类后就不变了，所以要求分类方法比较准确。而样品容量较大时，谱系聚类法的计算量过大。因此，为了弥补谱系聚类法的不足，产生了快速聚类法，又称动态聚类法。快速聚类法先将样品粗糙地分一下类，然后再按照某种原则进行修正，直至分类比较合理为止。,127,快速聚类法,128,快速聚类法的步骤,1 选择聚点 聚点（种子）是一批有代表性的样品，它的选择决定了初始分类，对最终分类有较大影响。在进行快速聚类法前，要根据研究问题的要求及了解程度先定下分类数k，这样就可以在每一类中选择一个有代表性的样品作为聚点（初始聚点）。,129,快速聚类法的步骤,1 选择聚点 选择聚点有下列方法：1）经验选择。如果对研究对象比较了解，根据以往的经验定下k个样品作为聚点。2）将n个样品人为地（或随机地）分成k类，以每类的重心作为聚点。,130,快速聚类法的步骤,1 选择聚点 3）最小最大原则。设要将n个样品分成k类，先选择所有样品中距离最远的两个样品 为前两个聚点，即选择 和，使 然后，选择第3个聚点，使得 与前两个聚点的距离最小者等于所有其余的与 的较小距离中最大的，用公式表示为,131,快速聚类法的步骤,然后按相同的原则选取，依次下去，直至选定k个聚点。若已选了l个聚点（lk）,则第l+1个聚点选取的原则为,132,快速聚类法的步骤,注：在SAS系统proc fastclus过程中，分类数k是事先给定的。在给定k以后，proc fastclus过程会按上述方法算出初始聚点的。,133,快速聚类法的计算步骤,先假设聚类中采用的距离是欧式距离，即1）设k个初始聚点的集合是用下列原则实现初始分类。记这样，将样品分成不相交的k类。以上初始分类的原则是每个样品以最靠近的初始聚点归类。,134,快速聚类法的计算步骤,依照以上计算，得到一个初始分类2）从 出发，计算新的聚点集合。以 的重心作为新的聚点：其中 是类 中的样品数。这样，得到新的聚点集合：,135,快速聚类法的计算步骤,从 出发，将样品作新的分类。记得到分类这样，依次重复计算下去。,136,快速聚类法的计算步骤,3）设在第m步得到分类在以上递推计算过程中，是类 的重心。不一定是样品，又一般不是 的重心。当m逐渐增大时，分类趋于稳定。此时，就会近似为 的重心，从而算法即可结束。实际计算时，从某一步m开始，分类,137,快速聚类法的计算步骤,与完全相同，计算即告结束。记理论上可以证明：当m增加时，为单调减下有界序列，故 存在，即 会逐步趋于稳定。因此，分类结果也将逐步稳定，即上述快速聚类法具有收敛性。,138,快速聚类法的计算步骤,设给定，若则递推计算过程结束。注：在proc fastclus过程中，的默认值是0.02。,139,快速聚类proc fastclus过程,该过程适合于观测数目较大的数据集的不相交聚类（即各类之间互不相交）。但对于小数据集，此过程对于观测的次序较为敏感。此过程在聚类之前要求指定类的个数，因为要对不同的类的个数作分析，需要多次运行该过程。主要语句形式为 proc fastclus options；var variables；ID variable；,140,快速聚类proc fastclus过程,proc fastclus options；1）maxcluster（或maxc）n：指定所允许的最大分类个数，若省略，则默认n100。2）radiust：为选择新的“聚点”指定的最小距离准则。t的默认值为0。用户必须规定以上两个选项之一。,141,快速聚类proc fastclus过程,proc fastclus options；3）dataSAS data set：指出用以分析的SAS数据集名称。此过程中，数据性质是原始观测数据，而不能是距离或相似矩阵。4）mean SAS data set：生成一个输出数据集，其中包括每个类的均值和其他统计量的值。5）out SAS data set：生成一个输出数据集，其中包括原始数据及两个新变量cluster（用以指示观测属于哪个类的变量）和距离distance。,142,快速聚类proc fastclus过程,proc fastclus options；6）clustername：规定在4）和5）的输出数据集中用以指示观测数据属于哪一类的变量名称。缺省时系统自动命名为cluster。7）distance：要求打印类均值之间的距离。8）list：要求列出所有观测的ID变量值，观测所归入类的类号及观测与最终“聚点”之间的距离。9）leastm：表明用Lm准则进行聚类，L1是绝对距离，leastmax是Chebyshev距离。,143,例 6.7,从12个不同地区测得了某树种的平均发芽率x1与发芽势x2，数据见表。采用欧氏距离，将这12个地区以树种发芽情况按快速聚类法聚为2类。,144,表6.22 12个地区某树种发芽情况,145,146,147,148,149,例6.8,1976年74个国家和地区的人口出生率x1和死亡率x2的数据见表6.25（国家与地区名从略）。表中列出的数据是每10万人的出生数与死亡数。试对这74个国家与地区按人口出生率与死亡率进行快速聚类分析。,150,151,假定分3类,data shengsi;input x1 x2;cards;proc fastclus data=shengsi out=a1 maxc=3 cluster=c distance list;proc plot;plot x2*x1=c;run;,152,153,154,155,156,分为4类,data shengsi;input x1 x2;cards;proc fastclus data=shengsi out=a1 maxc=4 cluster=c distance list;proc plot;plot x2*x1=c;run;,157,158,159,160,161,例 6.9（续例 5.2）,对例5.2的数据进行快速聚类分析（27个省市区的编号如例6.5所示），按下列情况分析：（1）分为2类；（2）分为4类。,162,分为2类,data pjxf;input x1-x8;cards;proc fastclus data=pjxf out=a1 maxc=2 distance list;run;,163,164,165,166,分为4类,167,168,169,170,用Lm距离进行快速聚类,上面我们介绍的聚类方法都是用欧氏距离。下面我们介绍用Lm距离进行快速聚类的方法。设，则其Lm距离为 当 时，即是欧氏距离，当 时，为绝对距 离：,171,用Lm距离进行快速聚类,我们先讨论L1的情况。对于一元数据，要求一个数c，使得可知，使上式达到最小的c是 的中位数,172,用Lm距离进行快速聚类,对于p元样品。其中 的第k个分量的数据集是，设它的中位数是，则 称为 的中位向量，其中 满足,173,用Lm距离进行快速聚类,从而,174,用Lm距离进行快速聚类,讨论Lm最优化准则。对于一元数据，要求有一个数c，使得 称c为 的m中心。对于p元样品，其中,175,用Lm距离进行快速聚类,的第k个分量的数据集是，设它的m中心是，则 称为 的m中心向量，其中 满足 从而,176,用Lm距离进行快速聚类,2中心向量即均值向量，1中心向量即中位向量在采用Lm距离进行快速聚类分析时，最终聚点应是每一类的m中心向量。在采用L1距离进行聚类分析时，最终聚点应是每一类的中位向量用L1距离进行聚类分析时，有较强的稳健性，当有异常数据时，分类结果经常会更好些采用不同的Lm距离，聚类分析的结果经常会是不同的,177,例 6.10（续例6.7）,利用绝对距离对例6.7的数据进行快速聚类。,178,179,180,181,例 6.11（续例6.8）,利用绝对距离对例6.8的数据进行快速聚类。（1）分为3类；（2）分为4类。,182,例 6.11（续例6.8）,利用绝对距离对例6.8的数据进行快速聚类。（1）分为3类；（2）分为4类。,183,184,185,186,187,188,189,190,例 6.12（续例6.8）,利用Lm距离对例6.8的数据进行快速聚类，取m1.5；（1）分为3类；（2）分为4类。,191,192,193,194,195,196,