聚类分析数学建模精选文档.ppt

《聚类分析数学建模精选文档.ppt》由会员分享，可在线阅读，更多相关《聚类分析数学建模精选文档.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、聚类分析数学建模聚类分析数学建模本讲稿第一页，共七十七页分类l俗语说，物以类聚、人以群分。l但什么是分类的根据呢？l比如，要想把中国的县分成若干类，就有很多种分类法；l可以按照自然条件来分，l比如考虑降水、土地、日照、湿度等各方面；l也可以考虑收入、教育水准、医疗条件、基础设施等指标；l既可以用某一项来分类，也可以同时考虑多项指标来分类。本讲稿第二页，共七十七页一、聚类分析的基本概念一、聚类分析的基本概念l研究对样品或指标进行分类的一种多元统计方法,是依据研究对象的个体的特征进行分类的方法。l聚类分析把分类对象按一定规则分成若干类，这些类非事先给定的，而是根据数据特征确定的。在同一类中这些对象

2、在某种意义上趋向于彼此相似，而在不同类中趋向于不相似。l职能是建立一种能按照样品或变量的相似程度进行分类的方法。本讲稿第三页，共七十七页聚类分析l对于一个数据，人们既可以对变量（指标）进行分类(相当于对数据中的列分类)，也可以对观测值（事件，样品）来分类（相当于对数据中的行分类）。l比如学生成绩数据就可以对学生按照理科或文科成绩（或者综合考虑各科成绩）分类，l当然，并不一定事先假定有多少类，完全可以按照数据本身的规律来分类。l本章要介绍的分类的方法称为聚类分析（cluster analysis）。对变量的聚类称为R型聚类，而对观测值聚类称为Q型聚类。这两种聚类在数学上是对称的，没有什么不同。本

3、讲稿第四页，共七十七页 聚类分析的聚类分析的基本思想基本思想是认为我们所研究的样本或指标（变量）之间是认为我们所研究的样本或指标（变量）之间存在着程度不同的相似性（亲疏关系）。于是根据一批样本的多个观测存在着程度不同的相似性（亲疏关系）。于是根据一批样本的多个观测指标，具体找出一些彼此之间相似程度较大的样本（或指标）聚合为一指标，具体找出一些彼此之间相似程度较大的样本（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样本（或指标）又聚合为另一类，把另外一些彼此之间相似程度较大的样本（或指标）又聚合为另一类，关系密切的聚合到一个小的分类单位，关系疏远的聚合到一个大的类，关系密切的聚合到一个小

4、的分类单位，关系疏远的聚合到一个大的分类单位，直到把所有样本（或指标）都聚合完毕，把不同的类型一一分类单位，直到把所有样本（或指标）都聚合完毕，把不同的类型一一划分出来，形成一个由小到大的分类系统。最后把整个分类系统画成一划分出来，形成一个由小到大的分类系统。最后把整个分类系统画成一张谱系图，用它把所有样本（或指标）间的亲疏关系表示出来。这种方张谱系图，用它把所有样本（或指标）间的亲疏关系表示出来。这种方法是最常用的、最基本的一种，称为系统聚类分析。法是最常用的、最基本的一种，称为系统聚类分析。本讲稿第五页，共七十七页饮料数据（drink.sav）l16种饮料的热量、咖啡因、钠及价格四种变量种

5、饮料的热量、咖啡因、钠及价格四种变量 本讲稿第六页，共七十七页如何度量远近？l如如果果想想要要对对100个个学学生生进进行行分分类类，如如果果仅仅仅仅知知道道他他们们的的数数学学成成绩绩，则则只只好好按按照照数数学学成成绩绩来来分分类类；这这些些成成绩绩在在直直线线上上形成形成100个点。这样就可以把接近的点放到一类。个点。这样就可以把接近的点放到一类。l如如果果还还知知道道他他们们的的物物理理成成绩绩，这这样样数数学学和和物物理理成成绩绩就就形形成成二维平面上的二维平面上的100个点，也可以按照距离远近来分类。个点，也可以按照距离远近来分类。l三三维维或或者者更更高高维维的的情情况况也也是是

6、类类似似；只只不不过过三三维维以以上上的的图图形形无无法法直直观观地地画画出出来来而而已已。在在饮饮料料数数据据中中，每每种种饮饮料料都都有有四四个个变变量量值值。这这就就是是四四维维空空间间点点的的问问题题了。了。本讲稿第七页，共七十七页两个距离概念l按照远近程度来聚类需要明确两个概念：一个是点和点之间的距离，一个是类和类之间的距离。l点间距离有很多定义方式。最简单的是歐氏距离，还有其他的距离。l当然还有一些和距离相反但起同样作用的概念，比如相似性等，两点越相似度越大，就相当于距离越短。l由一个点组成的类是最基本的类；如果每一类都由一个点组成，那么点间的距离就是类间距离。但是如果某一类包含不

7、止一个点，那么就要确定类间距离，l类间距离是基于点间距离定义的：比如两类之间最近点之间的距离可以作为这两类之间的距离，也可以用两类中最远点之间的距离作为这两类之间的距离；当然也可以用各类的中心之间的距离来作为类间距离。在计算时，各种点间距离和类间距离的选择是通过统计软件的选项实现的。不同的选择的结果会不同，但一般不会差太多。本讲稿第八页，共七十七页二、距离二、距离用 表示第i个样本与第j个样本之间的距离。一切距离应满足以下条件：每个样本有p个指标，因此每个样本可以看成p维空间中的一个点，n个样本就组成p维空间中的n个点，这时很自然想到用距离来度量n个样本间的接近程度。本讲稿第九页，共七十七页常

8、见的距离有：常见的距离有：minkowski distance（明氏距离）：（明氏距离）：当当 q=1 block distance 绝对值距离绝对值距离:当当 q=2 squared euclidean distance 平方欧式距离平方欧式距离-=ptqjtitxxdq11当当q=chebychev distance 切比雪夫距离切比雪夫距离本讲稿第十页，共七十七页明氏距离在实际中应用的很多，明氏距离在实际中应用的很多，但也存在一些缺点：但也存在一些缺点：处理办法：标准化2 2、指标间的相关问题；、指标间的相关问题；1、量纲的问题；、量纲的问题；本讲稿第十一页，共七十七页Mahalanob

9、is 马氏距离改进的办法，采用马氏距离本讲稿第十二页，共七十七页相似系数相似系数l夹角余弦l相关系数本讲稿第十三页，共七十七页l 夹角余弦 两变量的夹角余弦定义为：本讲稿第十四页，共七十七页l 相关系数 两变量的相关系数定义为：本讲稿第十五页，共七十七页16 系统聚类方法系统聚类方法1、最短距离（Nearest Neighbor)x21x12x22x11本讲稿第十六页，共七十七页三、系统聚类法基本步骤1.选择样本间距离的定义及类间距离的定义；2.计算n个样本两两之间的距离，得到距离矩阵 3.构造个类，每类只含有一个样本；4.合并符合类间距离定义要求的两类为一个新类；5.计算新类与当前各类的距离

10、。若类的个数为1，则转到步骤6，否则回到步骤4;6.画出聚类图；7.决定类的个数和类。本讲稿第十七页，共七十七页系统聚类分析的方法系统聚类分析的方法l系统聚类法的聚类原则决定于样品间的距离以及类间距离的定义，类间距离的不同定义就产生了不同的系统聚类分析方法。l以下用dij表示样品X(i)和X(j)之间的距离，当样品间的亲疏关系采用相似系数Cij时，令 ；l以下用D(p,q)表示类Gp和Gq之间的距离。本讲稿第十八页，共七十七页3.重心法重心法(CENtroid method)本讲稿第十九页，共七十七页4.类平均法类平均法(AVErage method)本讲稿第二十页，共七十七页例例为了研究辽宁

11、等5省1991年城镇居民生活消费情况的分布规律，根据调查资料做类型分类，用最短距离做类间分类。数据如下：x1x2x3x4x5x6x7x8辽宁17.9039.778.4912.9419.2711.052.0413.29浙江27.6850.3711.3513.3019.2514.592.7514.87河南39.4227.938.208.1416.179.421.559.76甘肃49.1627.989.019.3215.999.101.8211.35青海510.0628.6410.5210.0516.188.391.9610.81本讲稿第二十一页，共七十七页l将每一个省区视为一个样本，先计算5个省区

12、之间的欧式距离，用D0表示距离矩阵（对称阵，故给出下三角阵）因此将3.4合并为一类，为类6，替代了3、4两类l类6与剩余的1、2、5之间的距离分别为：d(3,4)1=min(d31,d41)=min(13.80,13.12)=13.12 d(3,4)2=min(d32,d42)=min(24.63,24.06)=24.06 d(3,4)5=min(d35,d45)=min(3.51,2.21)=2.21本讲稿第二十二页，共七十七页l得到新矩阵合并类6和类5，得到新类7l类7与剩余的1、2之间的距离分别为：d(5,6)1=min(d51,d61)=min(12.80,13.12)=12.80 d

13、(5,6)2=min(d52,d62)=min(23.54,24.06)=23.54本讲稿第二十三页，共七十七页 得到新矩阵合并类1和类2，得到新类8l此时，我们有两个不同的类：类7和类8。它们的最近距离d(7,8)=min(d71,d72)=min(12.80,23.54)=12.80本讲稿第二十四页，共七十七页l得到矩阵最后合并为一个大类。这就是按最短距离定义类间距离的系统聚类方法。最长距离法类似！本讲稿第二十五页，共七十七页26最长距离（Furthest Neighbor）x11x21本讲稿第二十六页，共七十七页27组间平均连接（Between-group Linkage)本讲稿第二十七

14、页，共七十七页28组内平均连接法（Within-group Linkage)x21x12x22x11本讲稿第二十八页，共七十七页29重心法（Centroid clustering):均值点的距离本讲稿第二十九页，共七十七页类的个数的确定类的个数的确定l由适当的阈值确定；l根据数据点的散布直观地确定类的个数；l根据统计量确定分类个数；本讲稿第三十页，共七十七页类的个数的确定类的个数的确定l根据谱系图确定分类个数的准则：l各类重心间的距离必须很大；l类中保包含的元素不要太多；l类的个数必须符合实际应用；l如果采用几种不同的聚类方法处理，则在各种聚类图中应该发现相同的类。本讲稿第三十一页，共七十七页

15、聚类分析聚类分析1、系统聚类法、系统聚类法-（分层聚类）系统聚类法是应（分层聚类）系统聚类法是应用最广泛的一种（用最广泛的一种（Hierarchical Cluster过程）过程）1）、）、聚类原则：都是相近的聚为一类，即距离最聚类原则：都是相近的聚为一类，即距离最近或最相似的聚为近或最相似的聚为 一类。一类。2）、）、分层聚类的方法可以用于样本聚类（分层聚类的方法可以用于样本聚类（Q）型，也）型，也可以用于变量聚类（可以用于变量聚类（R型）。型）。2、非系统聚类法、非系统聚类法-（快速聚类法（快速聚类法-K-均值聚类法）均值聚类法）（K-means Cluster)3、两步聚类法、两步聚类法

16、-一种探索性的聚类方法一种探索性的聚类方法（TwoStep Cluster）本讲稿第三十二页，共七十七页四、系统聚类的参数选择四、系统聚类的参数选择聚类类别：聚类类别：统计统计图：树型谱系图图：树型谱系图 冰柱谱系图冰柱谱系图聚类方法聚类方法1.Between-groups linkage 类间平均法类间平均法 两类距离为两类元素两两之间平均平方距离两类距离为两类元素两两之间平均平方距离2.Within-groups linkage 类内平均法类内平均法两类距离为合并后类中可能元素两两之间平均平方距离两类距离为合并后类中可能元素两两之间平均平方距离3.Nearest neighbor 最短距离

17、法最短距离法 4.Furthest neighbor 最长距离法最长距离法5.Centroid clustering 重心法重心法 (欧式距离欧式距离)6.Median clustering 中间距离法中间距离法 (欧式距离欧式距离)7.Ward Method 离差平方法离差平方法 (欧式距离欧式距离)本讲稿第三十三页，共七十七页本讲稿第三十四页，共七十七页数据标准化处理：数据标准化处理：本讲稿第三十五页，共七十七页存储中间过程数据存储中间过程数据本讲稿第三十六页，共七十七页数据标准化处理，并存储。本讲稿第三十七页，共七十七页本讲稿第三十八页，共七十七页指定5类本讲稿第三十九页，共七十七页收敛

18、标准值本讲稿第四十页，共七十七页存储最终结果输出情况，在数据文件中（存储最终结果输出情况，在数据文件中（QCL-1、QCL-2）本讲稿第四十一页，共七十七页初始聚心选项，输出方差分析表本讲稿第四十二页，共七十七页初始聚类中心表本讲稿第四十三页，共七十七页具体城市看后表最终聚类中心表最终聚类中心表本讲稿第四十四页，共七十七页聚类结果：聚类结果：QCL-1说明聚类结果，说明聚类结果，QCL-2说明聚类的长度情况说明聚类的长度情况本讲稿第四十五页，共七十七页主要城市日照时数本讲稿第四十六页，共七十七页注：连续变量注：连续变量本讲稿第四十七页，共七十七页本讲稿第四十八页，共七十七页SPSS提供不同类间

19、距离提供不同类间距离的测量方法的测量方法1、组间连接法、组间连接法2、组内连接法、组内连接法3、最近距离法、最近距离法4、最远距离法、最远距离法5、重心法、重心法6、中位数法、中位数法7、Ward最小偏差平方和法最小偏差平方和法本讲稿第四十九页，共七十七页观测量概述表本讲稿第五十页，共七十七页聚类步骤，与图结合看！本讲稿第五十一页，共七十七页本讲稿第五十二页，共七十七页研究各种饮料在市场消费的分配规律，试确定各种饮料消费类型研究各种饮料在市场消费的分配规律，试确定各种饮料消费类型本讲稿第五十三页，共七十七页本讲稿第五十四页，共七十七页本讲稿第五十五页，共七十七页本讲稿第五十六页，共七十七页本讲

20、稿第五十七页，共七十七页本讲稿第五十八页，共七十七页本讲稿第五十九页，共七十七页聚类分析的第几步聚类分析的第几步哪两个样本或小哪两个样本或小类聚成一类类聚成一类相应的样本距离或相应的样本距离或小类距离小类距离指明是样本指明是样本(0)还是小还是小类类(n)下面第几步下面第几步用到用到本讲稿第六十页，共七十七页垂直冰柱图垂直冰柱图显示层次聚显示层次聚类分析类分析从冰柱图最后从冰柱图最后一行开始观察，一行开始观察，第一列表示类第一列表示类数数本讲稿第六十一页，共七十七页两步聚类法两步聚类法TwoStep Cluster 一种探索性的聚类方法，是随着人工智能的发展起来的智能聚类方法中的一种。一种探索

21、性的聚类方法，是随着人工智能的发展起来的智能聚类方法中的一种。用于解决海量数据或具有复杂类别结构的聚类分析问题。用于解决海量数据或具有复杂类别结构的聚类分析问题。两步聚类法特点：两步聚类法特点：1、同时处理离散变量和连续变量的能力、同时处理离散变量和连续变量的能力2、自动选择聚类数、自动选择聚类数3、通过预先选取样本中的部分数据构建聚类模型、通过预先选取样本中的部分数据构建聚类模型4、可以处理超大样本量的数据、可以处理超大样本量的数据本讲稿第六十二页，共七十七页简单介绍基本原理简单介绍基本原理分两步进行分两步进行第一步：预聚类。对记录进行初始的归类，用户自定义最大类别第一步：预聚类。对记录进行

22、初始的归类，用户自定义最大类别数。通过构建和修改特征树（数。通过构建和修改特征树（CT Free）完成。）完成。第二步：正式聚类。对第一步完成的初步聚类进行再聚类并确定第二步：正式聚类。对第一步完成的初步聚类进行再聚类并确定最终的聚类方案，系统根据一定的统计标准确定聚类的类别数目。最终的聚类方案，系统根据一定的统计标准确定聚类的类别数目。以后，可以通过传统的聚类方法进行聚类（以后，可以通过传统的聚类方法进行聚类（SPSS中采用合并型分层聚类法）。中采用合并型分层聚类法）。本讲稿第六十三页，共七十七页本讲稿第六十四页，共七十七页本讲稿第六十五页，共七十七页本讲稿第六十六页，共七十七页输出各变量在

23、聚类中比重图输出出聚类饼分图每个变量做一张条图每一各类别做两张,分别为连续与离散聚类重要性测度本讲稿第六十七页，共七十七页1、质心表和频数表2、聚类分析表3、自动聚类结果表本讲稿第六十八页，共七十七页聚类数目数值越小效果越好BIC相邻两项差值看数据的峰值，看聚类效果。4、8、10、14类。BIC准则-Schwartz Bayesian Criterion本讲稿第六十九页，共七十七页本讲稿第七十页，共七十七页本讲稿第七十一页，共七十七页本讲稿第七十二页，共七十七页本讲稿第七十三页，共七十七页本讲稿第七十四页，共七十七页离散变量频数表的图形表示本讲稿第七十五页，共七十七页本讲稿第七十六页，共七十七页连续变量在各个类别中的误差图本讲稿第七十七页，共七十七页