聚类分析部分课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,多元统计课程设计 之 聚类分析,长春工业大学,多元统计课程设计 之 聚类分析,1,聚类分析概述,聚类分析又称群分析，它是研究（样品或指标）分类问题的一种多元统计方法。所谓类，通俗的说，就是指相似元素的集合。,聚类分析概述,2,在社会经济领域中存在着大量,分类问题。比如，在经济学中，根据人均国民收入、人均工农业产值和人均消费水平等多项指标对世界上所有国家的经济发展状况进行分类。,世界上， 按经济发展水平可以将各个国家和地区划分为发达国家、发展中国家和贫困落后国家等。,在社会经济领域中存在着大量,3,聚类分析的目的是把分类对象按一定规则分成若干类，这些类不是事先给定的，而是根据数据的特征确定的，对类的数目和类的结构不必作任何假定。,聚类分析也能用来概括数据而不只是为了寻找“自然的”或“实在的”分类。,聚类分析部分课件,4,判别分析与聚类分析的关系,判别分析是在已知研究对象分成若干类型（或组别）并已取得各种类型的一批已知样品的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分类。对于聚类分析来说，一批给定样品要划分的类型事先并不知道，正需要通过聚类分析来给以确定类型。,判别分析与聚类分析的关系 判别分析是在已知,5,正因为如此，判别分析和聚类分析往往联合起来使用，例如判别分析是要求先知道各类总体情况才能判断新样品的归类，当总体分类不清楚时，可先用聚类分析对原来的一批样品进行分类，然后再用判别分析建立判别式以对新样品进行判别。,聚类分析部分课件,6,聚类分析与判别分析、主成分,分析、回归分析等方法联合起来使用，往往效果更好。,聚类分析部分课件,7,聚类分析根据分类对象不同分,为,Q型聚类分析,和,R型聚类分析,。,Q型聚类,是指对,样品,进行聚类，,R型聚类,是指对,变量,进行聚类。,教材中主要介绍Q型聚类。,聚类分析根据分类对象不同分,8,聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。我们主要介绍系统聚类法。,9,在对样品（或变量）进行分类时，很直观地，我们认为在同一类里的的这些对象在某种意义上倾向于彼此相似，而在不同类里的对象倾向于不相似。,多元统计分析中，样品（或变量）之间的这种相似性用距离和相似系数来度量。,10,距离和相似系数,距离常用来度量样品之间的相似性,相似系数常用来度量变量之间的相似性,样品之间的距离和相似系数有着各,种不同的定义，而这些定义与变量的类,型有着非常密切的关系。,距离和相似系数距离常用来度量样品之间的相似性,11,变量的类型,通常变量按测量尺度的不同可以分为以下,三类：,（1）,间隔尺度变量,：变量用连续的量来表示，,如长度、重量、速度、温度等；,（2）,有序尺度变量,：变量度量时不用明确的数,量表示，而是用等级来表示，如某产品分为一,等品、二等品、三等品等有次序的关系。,（3）,名义尺度变量,：变量用一些类表示，这些,类之间既无等级关系，也无数量关系，如性别,职业、产品的型号等。,变量的类型 通常变量按测量尺度的不同可以分为以下,12,距离,设 为第i个样品的第j个指标，数据矩阵表如下：,距离 设 为第i个样品的第j个指标，数据矩,13,在上表中，每个样品有p个变量，故,每个样品都可以看成是 中的一个点，n,个样品就是 中的n个点。在 中需定义,某种距离，将第i个样品与第j个样品之间,的距离记为 ,在聚类过程冲，相距较近的,点倾向于归为一类，相距较远的点应归属,不同的类。,在上表中，每个样品有p个变量，故,14,距离的性质,距离 一般应满足如下四个条件：,（1） ，对一切i，j；,（2） ，当且仅当第i个样品与第j个样品的,各变量值都相同；,（3） ，对一切i，j；,（4） ，对一切i，j，k。,距离的性质 距离 一般应满足如下四个条件：,15,常用距离定义,Minkowski（明考夫斯基）距离（明氏距离）,第i个样品与第j个样品间的,明氏距离,定义为：,明氏距离有以下三种特殊形式：,（1）当q=1时， ，成为,绝对值距离,也常被称为“城市街区”距离；,（2）当q=2时， ，称为,欧氏距,离,，这是聚类分析中最常用的一个距离；,（3）当q=,时， ，称为,契比雪夫距离。,常用距离定义Minkowski（明考夫斯基）距离（明氏距离）,16,当各变量的单位不同或测量值范围相差很大时，不应直接采用明氏距离，而应先对各变量的数据作标准化处理，然后用标准化后的数据计算距离。最常用的标准化处理是,其中 为第j个变量的样板均值， 为第j个变量的样本,方差。,当各变量的单位不同或测量值范围相差很大时,17,明氏距离特别是其中的欧氏距离是人们比较熟悉的也是使用最多的距离。但明氏距离存在不足之处，主要表现在两个方面：第一,它与各指标的量纲有关；第二，它没有考虑指标之间的相关性。,明氏距离特别是其中的欧氏距离是人们比较熟悉的也是,18,除此以外，从统计的角度上看，使用欧氏距离要求一个向量的n个分量是不相关的且具有相同的方差，或者说各坐标对欧氏距离的贡献是同等的且变差大小也是相同的，这时使用欧氏距离才合适，效果也较好，否则就有可能不能如实反映情况，甚至导致错误的结论。故一个合理的做法，就是对坐标加权，这就产生了“统计距离”。,除此以外，从统计的角度上看，使用欧氏距离要求,19,比如设 ，,且Q的坐标是固定的，点P的坐标相互独立地变化。用,表示p个变量 的n次观测的,样本方差，则可定义P到Q的统计距离为：,所加的权是 ，即用样本方差,除相应坐标。当取 时，就是点P,到原点O的距离。若 时，为欧氏距,离。,比如设,20,兰氏（Lance和Williams）距离,当 时，可以定义第i个,样品与第j个样品间的,兰氏距离,为,这个距离与各变量的单位无关。由于它对大的异常值,不敏感，故适用于高度偏斜的数据。兰氏距离有助于,克服各指标之间量纲的影响，但与明氏距离一样，也,没有考虑指标建的相关性。,兰氏（Lance和Williams）距离,21,马氏（Mahalanobis）距离,第i个样品与第j个样品间的马氏距离为,， ，S为样本,协方差矩阵。,马氏距离的优点是考虑到了变量间的相关性，且,与各变量的单位无关。除此之外，他还有一些优点，,如可以证明，将原数据作线性变换，马氏距离仍不变,等。,但马氏距离有一个很大的缺陷，就是马氏距离公式,中的S难以确定。因此，在实际聚类分析中，马氏距离,不理想。,马氏（Mahalanobis）距离,22,斜交空间距离,第i个样品与第j个样品间的,斜交空间距离,定义为,其中 是变量 与 间的相关系数。当p个变量互不,相关时， ，即斜交空间距离退化为欧氏距,离（除相差一个常数倍）。,斜交空间距离,23,以上几种距离的定义均要求变量是间隔尺度的，如果使用的变量是有序尺度或名义尺度的，则又吸纳供应的一些定义距离的方法。,聚类分析部分课件,24,某培训学院资料如下（名义尺度变量）：,这两名学员的第二个变量都取值“英”，称为,配合的,，第,一个变量取值不同，称为,不配合的,。一般地，记配合,的变量数为 ，不配合的变量数为 ，则它们之间的,距离可定义为,故上述两个样本之间的距离为2/3。,某培训学院资料如下（名义尺度变量）：,25,相似系数,聚类分析方法不仅用来对样品进,行分类，而且可用来对变量进行分,类，在对变量进行分类时，常常采用,相似系数来度量变量之间的相似性。,相似系数,26,变量之间的这种相似性度量，在,一些应用中要看相似系数的大小，而,在另一些应用中要看相似系数绝对值,的大小。相似系数（或其绝对值）越,大，认为变量之间的相似性程度就越,高；反之，则越低。,变量之间的这种相似性度量，在,27,聚类时，比较相似的变量倾向于,归为一类，不太相似的变量归属不同,的类。,聚类时，比较相似的变量倾向于,28,相似系数性质,变量 与 的相似系数用 来表示，它一般应满,足如下三个条件：,（1） ，当且仅当 和b为常数；,（2） ，对一切i，j；,（3） ，对一切i，j。,相似系数性质 变量 与 的相似系数,29,最常用的相似系数有两种：,1.,夹角余弦,变量 与 的,夹角余弦,定义为,它是 中变量 的观测向量 与变,量 的观测向量 之间的夹角 的,余弦函数，即 。,最常用的相似系数有两种：,30,2.,相关系数,变量 与 的,相关系数,定义为,样本相关系数我们曾用 来表示，这里表示为,是为了与其他相似系数符号一致。若变量与变量 是已标准化了的，则它们间的夹角,余弦就是相关系数。,2.相关系数,31,变量之间常借助于相似系数来定,义距离，如令 ，同样，样品,之间的相似系数也由类似的定义。,距离度量的是样品（或变量）间的差,异程度，相似系数度量的是样品（或变量）,间的相似程度。,变量之间常借助于相似系数来定,32,一般来说，同一批数据采用不同的相似性,度量，会得到不同的分类结果。在进行聚类分,析的过程中，应根据实际情况选取合适的相似,性度量。如在经济变量分析中，常用相关系数,来描述变量间的相似性程度。一般情况下，相,关系数比其他的相似系数有更强的可变性，但,分辨力要弱一点。,一般来说，同一批数据采用不同的相似性,33,系统聚类法,系统聚类法是聚类分析诸方法中用得最多,的一种，其基本思想是：开始将n个样品各自作,为一类，并规定样品之间的距离和类与类之间,的距离，然后将距离最近的两类合并成一个新,类，计算新类于其他类的距离；重复进行两个,最近类的合并，每次减少一类，直至所有的样,品和为一类。,常用的系统聚类法有八种，这些聚类方法,的区别在于类与类之间距离的计算方法不同。,系统聚类法 系统聚类法是聚类分析诸方法中用得最多,34,这里我们用 表示第i个样品与第j个样品的,距离， 表示类 表示 与 的距离。,所有的系统聚类法一开始每个样品自成一类，,类与类之间的距离与样品之间的距离相同（除,离差平方和法之外），即 ，所以起初,的距离矩阵全部相同，记为 。,这里我们用 表示第i个样品与第j个样品的,35,最短距离法,定义类与类之间的距离为两类最近样,品间的距离，即,称这种系统聚类法为,最短距离法（single,linkage method）,最短距离法,36,最短距离法聚类步骤：,（1）规定样品之间的距离，计算n个样品的距,离矩阵 ，它是一个对称矩阵；,（2）选择 中的最小元素，设为 ，则将,和 合并成一个新类 ，即,最短距离法聚类步骤：,37,（3）计算新类 与任一类 之间的距离的递推公,式为,在 中， 和 所在的行和列合并成一个新行新列,对应 ，该行列上的新距离值由上式计算，其余行列,上的距离值不变，即得新的距离矩阵，记作 。,（4）对 重复上述步骤得 ，如此下去直至所有元,素合并成一类为止。,（3）计算新类 与任一类 之间的距离的递推公,38,如果某一步的距离矩阵中最小的元素,不止一个，则称此现象为,结,，对应这些最,小元素的类可以任选一堆合并或同时合并。,最短距离法最容易产生结。,聚类分析部分课件,39,最长距离法,类与类之间的距离定义为两类最远样品间的距离,即,称这种系统聚类法为,最长距离法,（complete linkage,method）,。,最长距离法与最短距离法的并类步骤完全,相同，只是类间距离的递推公式有所不同。设某步将,类 和 合并成新类 ，则 与任一类 的距离,为,最长距离法,40,最长距离法容易被异常值严重地,扭曲，这是值得我们在应用中注意的,问题。一个有效的方法是删去这些异,常值后再进行聚类。,聚类分析部分课件,41,中间距离法,类与类之间的距离既不取两类最近样,品间的距离，也不取两类最远样品间的距,离，而是取介于两者中间的距离，称为,中,间距离法（median method）。,中间距离法,42,设某一步将 与 合并为 ，对于任一类,，考虑由 、 和 为边长组成的三角,形，取 边的中线作为 ，则 的计算公式,为,这就是中间距离法的递推公式。,中间距离法可推广为更一般的情形，将上,式三项的系数依赖于某个参数 ，即,这里 ，这种方法称为,可变法,。,设某一步将 与 合并为 ，对,43,类平均法,类平均法,（average linkage method）有,两种定义，一种定义方法是把类与类之间按的,距离定义为所有样品对之间的平均距离，即定,义 和 之间的距离为,其中 和 分别为类 和 的样品个数， 为,中的样品i与 中的样品j之间的距离。其递推,公式：,类平均法,44,另一种定义方法是定义类与类之间的平方,距离为样品对之间的平方距离的平均值，即,它的递推公式类似于前面的递推式，即,类平均法较好地利用了所有样品之间的信息，,在很多情况下它被认为是一种比较好的系统聚,类法。,另一种定义方法是定义类与类之间的平方,45,在上面的递推式中， 的影响没有被反映,出来，为此可将递推公式进一步推广为,其中 ，称这种系统聚类法为,可变类平均法,。,若采用第二种距离定义的类平均法进行聚,类，我们可以一开始就将 的每个元素都平方,则使用递推公式会比较方便。,在上面的递推式中， 的影响没有被反映,46,重心法,类与类之间的距离定义为它们的重心（均,值）之间的欧氏距离。设 和 的重心分别为,和 ，则 和 之间的平方距离为,这种系统聚类法称为,重心法,（centroid,hierarchical method）。它的递推公式为,重心法,47,重心法在处理异常值方面比其他,系统聚类法更稳健，但在别的方面一,般不如类平均法和离差平方和法的效,果好。,重心法在处理异常值方面比其他,48,离差平方和法（ward方法）,类中各样品到类重心（均值）的平方欧氏,距离之和称为（类内）,离差平方和,。设类 和,合并成新类 ，则 、 和 的离差平方和,分别是,离差平方和法（ward方法）,49,它们反映了各自类内样品的分散程度。如,果 和 这两类相距较近，则合并后所增加的,离差平方和 应较小；否则，应较,大。于是我们定义 和 之间的平方距离为,这种系统聚类法称为,离差平方和法,或,ward方,法,（wards minimum variance method）。,它们反映了各自类内样品的分散程度。如,50,也可表达为,可见这个距离与重心法的距离只相差一个常数,倍。重心法的类间距离与两类的样品数无关，,而离差平方和法的类间距离与两类的样品数有,较大的关系，两个大的类倾向于有较大的距,离，因而不易合并，这往往符合我们对聚类的,实际要求。,也可表达为,51,离差平方和法在许多场合下优于重心,法，是比较好的一种系统聚类法，但它对,异常值很敏感。,离差平方和法的平均距离递推公式,为,离差平方和法在许多场合下优于重心,52,一般来说，只要聚类的样品数目,不是太少，各种聚类方法所产生的聚,类结果一般是不同的，甚至会有大的,差异。,各种系统聚类法都有其适用的场,合，选用哪种方法需视实际情况和对,聚类结果的要求而定。,一般来说，只要聚类的样品数目,53,系统聚类法性质,1. 单调性,令 是系统聚类法中第i次并类时的距离。若一,种统聚类法能满足 ，则称它具有,单,调性,。这种单调性符合系统聚类法的思想，先合并较,相似的类，后合并较疏远的类。,可以证明，最短距离法、最长距离法、可变法、,类平均法、可变类平均法和离差平方和法都具有单调,性，但中间距离法和重心法不具有单调性。,系统聚类法性质1. 单调性,54,2. 空间的浓缩与扩张,设有两种系统聚类法，它们在第i步的距离矩阵分,别为 和 ，若,，则称第一种方法比第二种方法更,使空间扩张,，或第二种方法比第一种方法更,使空间浓,缩,。,我们以类平均法为基准，其他方法都与它作比较，有：,（1）最短距离法和重心法比类平均法更使空间浓缩；,（2）最长距离法比类平均法更使空间扩张；,（3）当 ，可变类平均法比类平均法更使空间浓缩；当 ，可变类平均法比类平均法更使空间扩张。,2. 空间的浓缩与扩张,55,比较以上这些方法可见，太浓缩,的方法不够灵敏，太扩张的方法可能,因灵敏度过高而容易失真。类平均法,比较适中，它既不太浓缩也不太扩,张，因此它被认为是一种比较理想的,方法。,聚类分析部分课件,56,类的个数,确定类个数的几种常用的方法：,给定一个阙值T,通过观测树形图，给出一个你认为合适的,阙值T，要求类与类之间的距离要大于T，有些,样品可能会因此而归不了类或只能自成一类。,这种方法有较强的主观性，这是它的不足之处。,类的个数确定类个数的几种常用的方法：,57,观测样品的散点图,如果样品只有两个或三个变量，则可通过观测数,据的散点图来确定类的个数。对于三个变量，可使用,SAS软件通过旋转三位坐标轴从各个角度来观测散点,图。若变量超过三个，则可将原始变量综合成两个或,三个综合变量，然后再观测这些综合变量的散点图。,观测散点图还有一个重要的用途，即从直觉上来,判断所采用的聚类方法是否合理，甚至有时直接从散,点图中进行主观的分类，效果也许会好于正规的聚类,方法。,观测样品的散点图,58,使用统计量,（1） 统计量,越大，表明k个类分得越开。因此， 统,计量可用于评价合并成k个类时的聚类效果，,值越大，聚类效果越好。,的取值范围在0与1之间，它总是随着分类个,数的减少而变小。聚类刚开始时，n个样品各自为一,类，这时 ；当n个样品最后合并成一类时,一般来说，我们希望类的个数尽可能地少，同时 又,保持较大。因此，类个数的进一步减少一般不应以,的大为减少作为代价。,使用统计量,59,（2）半偏 统计量,半偏 值是上一步 值与该步 值之差，因此半偏 值越大，说明上一次聚类的效果越好。,（2）半偏 统计量,60,（3）伪F统计量,伪F值越大，表明此时的分类效,果越好。,（4）伪 统计量,伪 值达，表明上一次的聚类的,效果是好的。,（3）伪F统计量,61,动态聚类法,Q型系统聚类法一般是在样品间距离矩阵,的基础上进行的，故当样品的个数n很大（如n,100)时，系统聚类法的计算量是非常大的，将,占据大量的计算机内存空间和较多的计算时,间，甚至会因计算机内存或计算时间的限制而,无法进行。因此，当n很大时，我们需要一种相,比系统聚类法而言计算量少得多，以致计算机,运行时只需占用较少内存空间和较短计算时间,的聚类方法。,动态聚类法 Q型系统聚类法一般是在样品间距离矩阵,62,动态聚类法,（或称,逐步聚类法,）正是基于,这种考虑而产生的一种方法。由于该方法不必,确定距离矩阵，在计算机运行中也不必存储基,本数据，因此同系统聚类法相比，这种方法更,适用于大的数据集，而且n越大，它的优越性就,越突出。,动态聚类法（或称逐步聚类法）正是基于,63,动态聚类法的基本思想是，选择一批凝聚,点或给出一个初始的分类，让样品按某种原则、,向凝聚点凝聚，对凝聚点进行不断的修改或迭,代，直至分类比较合理或迭代稳定为止。类的,个数k可以事先指定，也可以在聚类过程中确定。,选择初始凝聚点（或给出初始分类）的一种简,单方法是采用随机抽选（或随机分割）样品的,方法。,动态聚类法的基本思想是，选择一批凝聚,64,动态聚类法有许多种方法，主要介绍k均值,法。,k均值法基本步骤为：,（1）选择k个样品作为初始凝聚点，或者将所,有样品分成k个初始类，然后将这k个类的重心,（均值）作为初始凝聚点；,（2）对除凝聚点之外的所有样品逐个归类，将,每个样品归入凝聚点离它最近的那个类（通常,采用欧氏距离），该类的凝聚点更新为这一类,目前的均值，直至所有样品都归了类。,（3）重复步骤（2），直至所有样品都不能再分配。,动态聚类法有许多种方法，主要介绍k均值,65,最终的聚类结果在一定程度上依,赖于初始凝聚点或初始分类的选择。,经验表明，聚类过程中的绝大多数重,要变化均发生在第一次再分配中。,聚类分析部分课件,66,有序样品分类法,有序样品的分类实质上是找一些分点，将,有序样品划分为几个分段，每个分段看作一个,类，所以分类也称为分割。显然分点取在不同,的位置就可以得到不同的分割。通常寻找最好,分割的一个依据就是使各段内部样品之间的差,异最小，而各段样品之间的差异较大。有序样,品聚类法就是研究这种最优分割法。,系统聚类法，被分类的样品是相互独立,的，分类时彼此是平等的。而有序样品分类法,要求样品按一定的顺序排列，分类时不能打乱,次序。,有序样品分类法 有序样品的分类实质上是找一些分点,67,模糊聚类法,模糊聚类法是将模糊集的概念用到聚,类分析中所产生的一种聚类方法，它是根,据研究对象本身的属性而构造一个模糊矩,阵，在此基础上根据一定的隶属度来确定,其分类关系。,模糊聚类法,68,SAS实现,proc cluster data= method=name;,var variables;,copy varibles;,rmsstd variable;,id variable;,by variables;,freq variable;,run;,除第一语句为必需语句外，其余均为可选择语句,。,Rmsstd语句出现时，freq语句必需出现，其余,情况下可选。,SAS实现proc cluster data= me,69,不能省略的说明项：,1. method=name或M=name=用来确定聚类方法,name：,（1）average/ave=类平均法；,（2）centroid/cen=重心法；,（3）complete/com=最长距离法；,（4）density/den=密度估计法；,（5）eml=最大似然谱系聚类；,（6）flexible/fle=可变类平均法；,不能省略的说明项：,70,（7）mcquitty/mcq=mcquitty相似分析方法;,（8）median/med=中间距离法；,（9）single/sin=最短距离法；,（10）two stage/two=两阶段密度估计法；,（11）ward/war=离差平方和法,聚类分析部分课件,71,2. Cluster过程选项：,（1）指定输入与输出数据集,（,）data=；命名包含进行聚类的观测的输入SAS数据集，若数据集类型为type=,distance，则数据被认为是距离矩阵，若数据不是type=distance，数据被认为是坐标数据,并计算欧氏距离；,2. Cluster过程选项：,72,（,）outtree=；生成记录并类过程的输出SAS数据集，画树状图的tree过程使用该数据集作为输入数据集。若缺省，数据集采用data n规则命名，且该数据集为临时数据集。若不想生成此输出数据集，使用outtree=_null_;,（2）指定聚类方法细节,beta=n=对method=flexible等规定beta，n应小于1，通常介于0与-1之间，缺省值为,-0.25，Milligan建议对有较多异常值的数据集采用更小的beta值，如beta=-0.5；,（）outtree=；生成记录并类过程的输出SAS数据,73,（3）控制聚类之前的数据处理,（,）nonorm=防止将距离规范化为单位均值或单位均方，若与m=ward一起使用，阻止过程用总平方和去除类间平方和来得到平方半偏相关；,（,）nosquare=阻止过程在m=ave，cen，med或war方法中输入的距离被平方；,（3）控制聚类之前的数据处理,74,（4）控制聚类历史过程的输出,（,）noid=在聚类历史过程中每次产生的合并时不输出id值；,（,）print=n/p=n=指定输出的聚类历史过程的层数。p=n表只输出最后n层，p=的值须为非负整数。缺省时，输出全部聚类过程；p=0不输出聚类历史过程；,（,）pseudo=输出伪F和伪t方统计量，此时数据为坐标数据，或m=ave，cen，war时才有效；,（4）控制聚类历史过程的输出,75,（,）rmsstd=输出每一类均方根标准差，此时数据为坐标数据，或m=ave，cen，war时有效；,（,）rsquare/rsq=输出R方和半偏R方，此时数据为坐标数据，或m=ave，cen时有效，m=war时， R方和半偏R方总会输出；,copy语句=将其列出的变量（一般是var等语句没有列出的）从输入数据集复制到outtree=数据集中，以备后用。,（）rmsstd=输出每一类均方根标准差，此时数据为坐,76,