聚类分析-动态聚类讲解课件.ppt

1、1第六章第六章 聚类分析聚类分析2n系统聚类分析 直观，易懂。n动态聚类 快速，动态。n有序聚类 保序(时间顺序或大小顺序)。3 一、变量测量尺度的类型一、变量测量尺度的类型 为了将样本进行分类，就需要研究样品之间为了将样本进行分类，就需要研究样品之间的关系；而为了将变量进行分类，就需要研究的关系；而为了将变量进行分类，就需要研究变量之间的关系。但无论是样品之间的关系，变量之间的关系。但无论是样品之间的关系，还是变量之间的关系，都是用变量来描述的，还是变量之间的关系，都是用变量来描述的，变量的类型不同，描述方法也就不同。通常，变量的类型不同，描述方法也就不同。通常，变量按照测量它们的尺度不同，

2、可以分为三类。变量按照测量它们的尺度不同，可以分为三类。2 距离和相似系数距离和相似系数4 (1)(1)间隔尺度间隔尺度。指标度量时用数量来表示，。指标度量时用数量来表示，其数值由测量或计数、统计得到，如长其数值由测量或计数、统计得到，如长度、重量、收入、支出等。一般来说，度、重量、收入、支出等。一般来说，计数得到的数量是离散数量，测量得到计数得到的数量是离散数量，测量得到的数量是连续数量。在间隔尺度中如果的数量是连续数量。在间隔尺度中如果存在绝对零点，又称比例尺度。存在绝对零点，又称比例尺度。5 (2)(2)顺序尺度顺序尺度。指标度量时没有明确的数量。指标度量时没有明确的数量表示，只有次序关

3、系，或虽用数量表示，但相表示，只有次序关系，或虽用数量表示，但相邻两数值之间的差距并不相等，它只表示一个邻两数值之间的差距并不相等，它只表示一个有序状态序列。如评价酒的味道，分成好、中、有序状态序列。如评价酒的味道，分成好、中、次三等，三等有次序关系，但没有数量表示。次三等，三等有次序关系，但没有数量表示。又如评价产品的质量，虽可用一、二、三等来又如评价产品的质量，虽可用一、二、三等来表示，但一等与二等之间、二等与三等之间的表示，但一等与二等之间、二等与三等之间的差距并不一定相等。差距并不一定相等。6 (3)(3)名义尺度名义尺度。指标度量时既没有数量表示。指标度量时既没有数量表示也没有次序关

4、系，只有一些特性状态，如眼也没有次序关系，只有一些特性状态，如眼睛的颜色，化学中催化剂的种类等。在名义睛的颜色，化学中催化剂的种类等。在名义尺度中只取两种特性状态的变量是很重要的，尺度中只取两种特性状态的变量是很重要的，如电路的开和关，天气的有雨和无雨，人口如电路的开和关，天气的有雨和无雨，人口性别的男和女，医疗诊断中的性别的男和女，医疗诊断中的“+”+”和和“-”-”，市场交易中的买和卖等都是此类变量。市场交易中的买和卖等都是此类变量。显然，显然，对于具有多个特性状态的变量，可通过并类对于具有多个特性状态的变量，可通过并类的方法将其转化为二性状态变量。的方法将其转化为二性状态变量。7 二、数

5、据的变换处理二、数据的变换处理 所谓数据变换，就是将原始数据矩阵中的每个元素，按照某种特定的运算把它变成为一个新值，而且数值的变化不依赖于原始数据集合中其它数据的新值。81 1、中心化变换、中心化变换 中心化变换是一种坐标轴平移处理方法，它是先求出每个变量的样本平均值，再从原始数据中减去该变量的均值，就得到中心化变换后的数据。设原始观测数据矩阵为：npnnppxxxxxxxxx212222111211Xjijijxxx*令),3,2,1;,3,2,1(pjni9中心化变换的结果是1.使每列之和均为0，即每个变量的均值为0；2.协方差阵不变；3.每列数据的平方和是该列变量样本方差的(n-1)倍；

6、4.任何不同两列数据之交叉乘积是这两列变量样本协方差的(n-1)倍，所以这是一种很方便地计算方差与协方差的变换。10 2 2、极差正规化变换、极差正规化变换 正规化变换是从数据矩阵的每一个变量中找出其最大值和最小值，这两者之差称为极差，然后从每个变量的每个原始数据中减去该变量中的最小值，再除以极差，就得到正规化数据。即有：jniijijijRxxx,2,1*)min(),3,2,1;,3,2,1(pjniniijijnijxxR,2,1,2,1)min()(max10*ijx11 经过正规化变换后，数据矩阵中每列即每个变量的最大数值为1，最小数值为0，其余数据取值均在01之间；并且变换后的数据

7、都不再具有量纲，便于不同的变量之间的比较。123 3、标准化变换、标准化变换 标准化变换也是对变量的数值和量纲进行类似于规格化变换的一种数据处理方法。首先对每个变量进行中心化变换，然后用该变量的标准差进行标准化。即有：jjijijSxxx*),3,2,1;,3,2,1(pjninijijjxxnS12)(1113 经过标准化变换处理后，每个变量即数据矩阵中每列数据的平均值为0，方差为1，且也不再具有量纲，同样也便于不同变量之间的比较。变换后，数据短阵中任何两列数据乘积之和是两个变量相关系数的（n-1）倍，所以这是一种很方便地计算相关矩阵的变换。14 4 4对数变换对数变换 对数变换是将各个原始

8、数据取对数，将原始数据的对数值作为变换后的新值。即：)log(*ijijxx 15 三、样品间亲疏程度的测度三、样品间亲疏程度的测度 研究样品或变量的亲疏程度的数量指标有两种，一种叫相似系数相似系数，性质越接近的变量或样品，它们的相似系数越接近于1或-1，而彼此无关的变量或样品它们的相似系数则越接近于0，相似的为一类，不相似的为不同类；另一种叫距离距离，它是将每一个样品看作p维空间的一个点，并用某种度量测量点与点之间的距离，距离较近的归为一类，距离较远的点应属于不同的类。16 变量之间的聚类即R型聚类分析，常用相似系数来测度变量之间的亲疏程度。而样品之间的聚类即Q型聚类分析，则常用距离来测度样

9、品之间的亲疏程度。注:变量聚类放到因子分析后面17 1、定义距离的准则、定义距离的准则 定义距离要求满足第i个和第j个样品之间的距离如下四个条件（距离可以自己定义，只要满足距离的条件）距离可以自己定义，只要满足距离的条件）;0成立和对一切的jidij;0成立当且仅当jidij;0成立和对一切的jiddjiij.成立和对于一切的jidddkjikij182 2、常用距离的算法、常用距离的算法设 和是第i和 j 个样品的观测值，则二者之间的距离为：gpkgjkikijxxd11)|(pkjkikijxxd12)(ipiixxx,21ix),(21jpjjxxxjx特别，欧氏距离(1)(1)闵科夫斯

10、基距离闵科夫斯基距离19 闵科夫斯基距离主要有以下两个缺点：闵氏距离的值与各指标的量纲有关，而各指标计量单位的选择有一定的人为性和随意性，各变量计量单位的不同不仅使此距离的实际意义难以说清，而且，任何一个变量计量单位的改变都会使此距离的数值改变从而使该距离的数值依赖于各变量计量单位的选择。闵氏距离的定义没有考虑各个变量之间的相关性和重要性。实际上，闵氏距离是把各个变量都同等看待，将两个样品在各个变量上的离差简单地进行了综合。20(2)杰氏距离这是杰斐瑞和马突斯塔(Jffreys&Matusita)所定义的一种距离，其计算公式为：2112)()(pkjkikijxxJd21(3)(3)兰氏距离兰

11、氏距离 这是兰思和维廉姆斯(Lance&Williams)所给定的一种距离，其计算公式为：mkjkikjkikijxxxxmLd11)(这是一个自身标准化的量，由于它对大的奇异值不敏感，这样使得它特别适合于高度偏倚的数据。虽然这个距离有助于克服明氏距离的第一个缺点，但它也没有考虑指标之间的相关性。22 (4)马氏距离马氏距离 这 是 印 度 著 名 统 计 学 家 马 哈 拉 诺 比 斯(PCMahalanobis)所定义的一种距离，其计算公式为：)()(2ji1jixxxxijd 分别表示第i个样品和第j样品的p指标观测值所组成的列向量，即样本数据矩阵中第i个和第j个行向量的转置，表示观测变

12、量之间的协方差短阵。在实践应用中，若总体协方差矩阵未知，则可用样本协方差矩阵作为估计代替计算。23 马氏距离又称为广义欧氏距离。显然，马氏距离与上述各种距离的主要不同就是马氏距离考虑了观测变量之间的相关性。如果假定各变量之间相互独立，即观测变量的协方差矩阵是对角矩阵，则马氏距离就退化为用各个观测指标的标准差的倒数作为权数进行加权的欧氏距离。因此，马氏距离不仅考虑了观测变量之间的相关性，而且也考虑到了各个观测指标取值的差异程度，为了对马氏距离和欧氏距离进行一下比较，以便更清楚地看清二者的区别和联系，现考虑一个例子。2419.09.01,002N19.09.0119.011两点。和设)1,1()1

13、,1(BA05.1)(MdA20)(MdB2)(UdA2)(UdB例如，假设有一个二维正态总体，它的分布为：25 (5)斜交空间距离 由于各变量之间往往存在着不同的相关关系，用正交空间的距离来计算样本间的距离易变形，所以可以采用斜交空间距离。21112)(1 phpkhkjkikjhihijxxxxpd当各变量之间不相关时，斜交空间退化为欧氏距离。26 2、相似系数的算法（1）相关系数设 和是第 和 个样品的观测值，则二者之间的相关系数为:ipiixxx,21ix),(21jpjjxxxjxijpkpkjjkiikpkjjkiikijxxxxxxxx11221)()()(其中27 （2）夹角余

14、弦 夹角余弦是从向量集合的角度所定义的一种测度变量之间亲疏程度的相似系数。设在n维空间的向量niiiixxx,21xnjjjjxxx,21xnknkkjkinkkjkiijijxxxxc11221cos221ijijCd28 五、距离和相似系数选择的原则 一般说来，同一批数据采用不同的亲疏测度指标，会得到不同的分类结果。产生不同结果的原因，主要是由于不同的亲疏测度指标所衡量的亲疏程度的实际意义不同，也就是说，不同的亲疏测度指标代表了不同意义上的亲疏程度。因此我们在进行聚类分析时，应注意亲疏测度指标的选择。通常，选择亲疏测度指标时，应注意遵循的基本原则主要有：29 (1)所选择的亲疏测度指标在实

15、际应用中应有明确的意义。如在经济变量分析中，常用相关系数表示经济变量之间的亲疏程度。30 (2)亲疏测度指标的选择要综合考虑已对样本观测数据实施了的变换方法和将要采用的聚类分析方法。如在标准化变换之下，夹角余弦实际上就是相关系数；又如若在进行聚类分析之前已经对变量的相关性作了处理，则通常就可采用欧氏距离，而不必选用斜交空间距离。此外，所选择的亲疏测度指标，还须和所选用的聚类分析方法一致。如聚类方法若选用离差平方和法，则距离只能选用欧氏距离。31 (3)适当地考虑计算工作量的大小。如对大样本的聚类问题，不适宜选择斜交空间距离，因采用该距离处理时，计算工作量太大。样品间或变量间亲疏测度指标的选择是

16、一个比较复杂且带主规性的问题，我们应根据研究对象的特点作具体分折，以选择出合适的亲疏测度指标。实践中，在开始进行聚类分析时，不妨试探性地多选择几个亲疏测度指标，分别进行聚类，然后对聚类分析的结果进行对比分析，以确定出合适的亲疏测度指标。32000pGqG1G2GnG1G2GnG12dnd121d1nd2ndnd2 至此，我们已经可以根据所选择的距离构成至此，我们已经可以根据所选择的距离构成样本点间的距离表样本点间的距离表,样本点之间被连接起来。样本点之间被连接起来。33 四、样本数据与小类、小类与小类之间的度量四、样本数据与小类、小类与小类之间的度量1、最短距离（Nearest Neighbo

17、r)x21x12x22x1113d34最长距离（Furthest Neighbor）x11x2112d35991dd 组间平均连接（Between-group Linkage)36 1、组内平均连接法（Within-group Linkage)1234566ddddddx21x12x22x1137重心法（Centroid clustering):均值点的距离11,x y22,xy38离差平方和法连接2，41，56，522(23)(43)222(65.5)(55.5)0.522(1 3)(53)839红绿（2，4，6，5）8.75 离差平方和增加8.752.56.25 黄绿（6，5，1，5）14

18、.75离差平方和增加14.758.56.25黄红（2，4，1，5）10100故按该方法的连接和黄红首先连接。403 系统聚类方法系统聚类方法 1、计算n个样品两两间的距离 ，有 个。将所有列表，记为D(0)表，该表是一张对称表。所有的样本点各自为一类。2、选择D(0)表中最小的非零数，不妨假设 ，于是将 和 合并为一类，记为 。pqdpGqGqprGGG，2nCijd（一）方法开始各样本自成一类。41 3、利用递推公式计算新类与其它类之间的距离。分别删除D(0)表的第p，q行和第p，q列，并新增一行和一列添上的结果，产生D(1)表。42 4、在D(1)表再选择最小的非零数，其对应的两类有构成新

19、类，再利用递推公式计算新类与其它类之间的距离。分别删除D(1)表的相应的行和列，并新增一行和一列添上的新类和旧类之间的距离。结果，产生D(2)表。类推直至所有的样本点归为一类为止。432 动态聚类 一、思想一、思想 系统聚类法是一种比较成功的聚类方法。然而当样本点数量十分庞大时，则是一件非常繁重的工作，且聚类的计算速度也比较慢。比如在市场抽样调查中，有4万人就其对衣着的偏好作了回答，希望能迅速将他们分为几类。这时，采用系统聚类法就很困难，而动态聚类法就会显得方便，适用。动态聚类解决的问题是：假如有个样本点，要把它们分为类，使得每一类内的元素都是聚合的，并且类与类之间还能很好地区别开。动态聚类使

20、用于大型数据。44选择凝聚点分 类修改分类分类是否合理分类结束YesNo45 用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。快速聚类的步骤：1、随机选取两个点 和 作为聚核。2、对于任何点 ，分别计算 3、若 ，则将 划为第一类，否则划给第二类。于是得图（b）的两个类。)1(1x)1(2xkx),(),()1(2)1(1xxdxxdkk和),(),()1(2)1(1xxdxxdkkkx 4、分别计算两个类的重心，则得 和 ，以其为新的聚核，对空间中的点进行重新分类，得到新分类。)2(1x)2(2x46 （a）空间的群点 (b)任取两个聚核 (c)第一次分类 (d)求

21、各类中心47 (e)第二次分类48二、选择凝聚点和确定初始分类二、选择凝聚点和确定初始分类 凝聚点就是一批有代表性的点，是欲形成类的中心。凝聚点的 选择直接决定初始分类，对分类结果也有很大的影响，由于凝聚点 的不同选择，其最终分类结果也将出现不同。故选择时要慎重通 常选择凝聚点的方法有：(1)人为选择，当人们对所欲分类的问题有一定了解时，根据经验，预先确定分类个数和初始分类，并从每一类中选择一个有代表性的样品作为凝聚点。(2)将数据人为地分为A类，计算每一类的重心，就将这些重心作为凝聚点。49 (3)用密度法选择凝聚点。以某个正数d为半径，以每个样品为球心，落在这个球内的样品数(不包括作为球心

22、的样品)就叫做这个样品的密度。计算所有样品点的密度后，首先选择密度最大的样品作为第一凝聚点，并且人为地确定一个正数D(一般D d，常取D2d)。然后选出次大密度的样品点，若它与第一个凝 聚点的距离大于D，则将其作为第二个凝聚点；否则舍去这点，再 选密度次于它的样品。这样，按密度大小依次考查，直至全部样品考查完毕为止此方法中，d要给的合适，太大了使凝聚点个数太 少，太小了使凝聚点个数太多。50 (5)随机地选择，如果对样品的性质毫无所知，可采用随机数表来选择，打算分几类就选几个凝聚点。或者就用前A个样品作为凝聚点(假设分A类)。这方法一般不提倡使用。(4)人为地选择一正数d，首先以所有样品的均值

23、作为第一凝聚点。然后依次考察每个样品，若某样品与已选定的凝聚点的距 离均大于d，该样品作为新的凝聚点，否则考察下一个样品。51 三、衡量聚类结果的合理性指标和算法终止的标准三、衡量聚类结果的合理性指标和算法终止的标准 定义定义 设 表示在第n次聚类后得到的第i类集合，为第n次聚类所得到的聚核。定义定义 若分类不合理时，会很大，随着分类的过程，逐渐下降，并趋于稳定。niPki,3,2,1)(niAkiPxninniAxdu1)(2),(kiPxninniAxdu1)(2),(11,2,jlijilxPiAxjn1j第 步的新聚核。52定义定义 第i类中所有元素与其重心的距离的平方和:nilPxn

24、ilniniAxdPAD),(),(2kiPxnilnnilAxdu1)(2),(kininiPAD1),(11|nnnuuu是事前给定的一个充分小量 。为所有K个类中所有元素与其重心的距离的平方和。定义算法终止的标准是53五、动态聚类步骤为：五、动态聚类步骤为：第一，选择若干个观测值点为“凝聚点”；第二，可选择地，通过分配每个“凝聚点”最近的类里来形成临时分类。每一次对一个观测值点进行归类，“凝聚点”更新为这一类目前的均值；54n第三，可选择地，通过分配每个“凝聚点”最近的类里来形成临时分类。所有的观测值点分配完后，这些类的“凝聚点”用临时类的均值代替。该步骤可以一直进行直到“凝聚点”的改变

25、很小或为零时止；n第四，最终的分类有分配每一个观测到最近的“凝聚点”而形成。55例 我国经济发展的总目标是到2000年人民生活达到小康标准，因此，了解各地区目前对小康生活质量的实现程度。对各地区实现小康生活质量的状况进行综合评价，对各级政府部门具有重要意义。数据是1990年全国30个省在经济（jj）、教育（jy）、健康（jk）和居住环境（jz）四个方面对小康标准已经实现的程度，1表示已经达到或超过小康水平，0表示低于或多或少刚达到温饱水平。希望利用该数据对15个地区进行分类研究。56 jjjyjkjz类别类别 距离距离beijngsh0.72580.94131.00000.500010.295

26、50anghai0.53460.98481.00000.500010.14909 ianjin0.32460.97331.00000.500010.16173 henna0.23010.46211.00001.000020.22252 ejiang0.50250.23741.00000.888220.34448 jilin0.34460.77550.82800.500010.18212elongji0.28910.78350.80800.500010.22322 fujian0.14060.35241.00000.710220.27468 uangxi0.09390.64980.44351.0

27、00020.51560 anhui0.11040.08021.00000.954520.34050 ingxia0.27080.31270.54250.905320.29445 hunan0.06180.56870.43850.500030.41704jiangxi0.05490.30420.35200.615530.15540 inghai0.07510.01180.00000.825830.37720 uizhou0.02860.06000.05900.500030.2596857 四、有序样本聚类法四、有序样本聚类法 （一）功能范畴与数据类型（一）功能范畴与数据类型 有序样本聚类法又称为

28、最优分段法。该方法是由费歇在1958年提出的。它主要适用于样本由一个变量描述的情况。或者将多变量综合成为一个变量来分析。设 是样本点构成的集合，样本点 在函数 上的取值为 。若 ，则将视为一类。不妨假设 。要将 分为 类；即 ，分类时不能打乱样本点的顺序，即每一类必须呈的 形式，即有序样本聚类。n,21 i)(Vi)()(jiVVmv21mv,21K),(21kPPPPj,2158 系统聚类开始n个样品各自自成一类，然后逐步并类，直至所有的样品被聚为一类为止。而有序聚类则相反，开始所有的样品为一类，然后分为二类、三类等，直到分成n类。每次分类都要求产生的离差平方和的增量最小。59例 421,1

29、.1)(11V3.1)()(322VV1.3)(43V这里n=4，m=3。若将其分为两类，其结果应该是 对应中的点是 。321),(vvvP 4221),(wwww60 有序样本聚类法常常被用于系统的评估问题，被用来对样本点进行分类划级。例如，十二个地区的经济发展指数，排列出来以后，需要划分他们的等级。一种方法是按照行政命令。规定三个经济发达地区，四个中等发达的地区，三个一般地区，两个发展较差地区。这种行政上的规定往往是不客观、不合理的。合理的分类应该把发展情况最近似的地区划入同一类。这就是有序样本聚类的工作思路。61（二）有序聚类的步骤1、定义类的直径 设某类G中包含的样品有)(ij(j)1

30、)(i(i)x,x,x 该类的均值向量为jitij(t)GxX11 设有序样品x(1),x(2),x(n)。他们可以是从小到达排列，也可以是按时间的先后排列。62 用D(i,j)表示这一类的直径，常用的直径有，欧氏距离：jitjiD)X(x)XxG(t)G(t)(),(当是单变量的时，也可以定义直径为：是中位数GjitG(t)XXxjiD|),(632、定义分类的损失函数 用b(n,k)表示将n个有序的样品分为k类的某种分法：1112,1,1Gj jj2223,1,1Gjjj,1,kkkGjjn 定义这种分类法的损失函数为：各类的直径之和。ktttiiDknbL11)1,(),(64 由损失函

31、数的构造可以看出，损失函数是各类的直径之和。如果分类不好，则各类的直径之和大，否则比较小。当n和k固定时，Lb(n,k)越小表示各类的离差平方和越小，分类是合理的。因此要寻找一种分法b(n,k)，使分类损失函数Lb(n,k)达到最小。记该分法为Pn,k。65 若分类数k是已知的，求分类法b(n,k)，使它在损失函数意义下达到最小，其求法如下：首先，找出分点jk，使2(,2)min(1,1)(,)kkj nL P nDjD j n 且 于是得第k类njjGkkk,1,3、最优解的求法(,2):1,2,1,1,kkkP njjjn66 然后，找出jk1，使它满足 于是得第k-1类 1,1,111k

32、kkkjjjG 111(1,2):1,2,1,1,1kkkkkP jjjjj1121(1,2)min(1,1)(,1)kkkkkjjL P jDjD jj 且67 再然后，找出jk2，使它满足 于是得第k-2类 2221,1,1kkkkGjjj 类推。一直可以得到所有类G1，G2，Gk，这就是所求得最优解。12221(1,2):1,2,1,1,1kkkkkP jjjjj1122121(1,2)min(1,1)(,1)kkkkkjjL P jDjD jj 且68 4、Lb(n,k)的递推公式),()1,1(min),(),()1,1(min)2,(2njDkjDknpLnjDjDnpLnjknj

33、 以上的两个公式的含义是，如果要找到n个样品分为k个类的最优分割，应建立在将j-1（j2,3,n)个样品分为k-1类的最优分割的基础上。69 分析儿童的生长期。有如下的资料是1-11岁的男孩平均每年的增重：问男孩的发育可分为几个阶段。年龄年龄1234567891011增加重增加重量（公量（公斤）斤）9.31.81.91.71.51.31.42.01.92.32.170(,)D i j7122(1,2)(9.35.55)(1.85.55)28.125D222(1,3)(9.34.333)(1.84.333)(1.94.333)37.007D72 nk234567891030.005/240.02

34、/20.005/450.088/20.020/50.005/560.232/20.040/50.02/60.005/670.280/20.040/50.025/60.010/60.005/680.417/20.280/80.040/80.025/80.010/80.005/890.469/20.285/80.045/80.030/80.015/80.010/80.005/8100.802/20.367/80.127/80.045/100.030/100.015/100.010/100.005/10110.909/20.368/80.128/80.065/100.045/110.030/110.

35、015/110.010/110.005/11最小损失函数最小损失函数Lp(n,k)73损失函数Lp(n,k)随k变化趋势图00.20.40.60.81123456789类数损失函数74分类数分类数误差函数误差函数最优分割结果最优分割结果20.83921,2-1130.210691,2-6,7-1140.091991,2-4,5-7,8-1150.051021,2-4,5-7,8-9,10-1160.025861,2-3,4-5,6-7,8-9,10-1170.020551,2-3,4-5,6-7,8-9,10,1180.015231,2-3,4,5,6-7,8-9,10,1190.010161,2-3,4,5,6,7,8-9,10,11100.005081,2-3,4,5,6,7,8,9,10,11