建模培训讲座第四讲优秀PPT.ppt
《建模培训讲座第四讲优秀PPT.ppt》由会员分享,可在线阅读,更多相关《建模培训讲座第四讲优秀PPT.ppt(117页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第一节第一节 引言引言n“物以类聚,人以群分物以类聚,人以群分”。对事物进行分类,是人们相识事。对事物进行分类,是人们相识事物的动身点,也是人们相识世界的一种重要方法。因此,分物的动身点,也是人们相识世界的一种重要方法。因此,分类学已成为人们相识世界的一门基础科学。类学已成为人们相识世界的一门基础科学。n在生物、经济、社会、人口等领域的探讨中,存在着大量量在生物、经济、社会、人口等领域的探讨中,存在着大量量化分类探讨。例如:在生物学中,为了探讨生物的演化,生化分类探讨。例如:在生物学中,为了探讨生物的演化,生物学家须要依据各种生物不同的特征对生物进行分类。在经物学家须要依据各种生物不同的特征对
2、生物进行分类。在经济探讨中,为了探讨不同地区城镇居民生活中的收入和消费济探讨中,为了探讨不同地区城镇居民生活中的收入和消费状况,往往须要划分不同的类型去探讨。在地质学中,为了状况,往往须要划分不同的类型去探讨。在地质学中,为了探讨矿物勘探,须要依据各种矿石的化学和物理性质和所含探讨矿物勘探,须要依据各种矿石的化学和物理性质和所含化学成分把它们归于不同的矿石类。在人口学探讨中,须要化学成分把它们归于不同的矿石类。在人口学探讨中,须要构造人口生育分类模式、人口死亡分类状况,以此来探讨人构造人口生育分类模式、人口死亡分类状况,以此来探讨人口的生育和死亡规律。口的生育和死亡规律。n但历史上这些分类方法
3、多半是人们主要依靠阅历作定性分类,但历史上这些分类方法多半是人们主要依靠阅历作定性分类,致使很多分类带有主观性和随意性,不能很好地揭示客观事致使很多分类带有主观性和随意性,不能很好地揭示客观事物内在的本质差别与联系;特殊是对于多因素、多指标的分物内在的本质差别与联系;特殊是对于多因素、多指标的分类问题,定性分类的精确性不好把握。为了克服定性分类存类问题,定性分类的精确性不好把握。为了克服定性分类存在的不足,人们把数学方法引入分类中,形成了数值分类学。在的不足,人们把数学方法引入分类中,形成了数值分类学。后来随着多元统计分析的发展,从数值分类学中渐渐分别出后来随着多元统计分析的发展,从数值分类学
4、中渐渐分别出了聚类分析方法。随着计算机技术的不断发展,利用数学方了聚类分析方法。随着计算机技术的不断发展,利用数学方法探讨分类不仅特别必要而且完全可能,因此近年来,聚类法探讨分类不仅特别必要而且完全可能,因此近年来,聚类分析的理论和应用得到了快速的发展。分析的理论和应用得到了快速的发展。n聚类分析就是分析如何对样品(或变量)进行量化分类的问聚类分析就是分析如何对样品(或变量)进行量化分类的问题。通常聚类分析分为题。通常聚类分析分为Q型聚类和型聚类和R型聚类。型聚类。Q型聚类是对样型聚类是对样品进行分类处理,品进行分类处理,R型聚类是对变量进行分类处理。型聚类是对变量进行分类处理。其次节其次节
5、相像性的量度相像性的量度 一一 样品相似性的度量样品相似性的度量 二二 变量相似性的度量变量相似性的度量 一、样品相像性的度量一、样品相像性的度量n在聚类之前,要首先分析样品间的相像性。在聚类之前,要首先分析样品间的相像性。Q型聚类分析,型聚类分析,常用距离来测度样品之间的相像程度。每个样品有常用距离来测度样品之间的相像程度。每个样品有p个指标个指标(变量)从不同方面描述其性质,形成一个(变量)从不同方面描述其性质,形成一个p维的向量。假维的向量。假如把如把n个样品看成个样品看成p维空间中的维空间中的n个点,则两个样品间相像程个点,则两个样品间相像程度就可用度就可用p维空间中的两点距离公式来度
6、量。两点距离公式维空间中的两点距离公式来度量。两点距离公式可以从不同角度进行定义,令可以从不同角度进行定义,令dij 表示样品表示样品Xi与与Xj的距离,的距离,存在以下的距离公式:存在以下的距离公式:n1明考夫斯基距离明考夫斯基距离n (5.1)n明考夫斯基距离简称明氏距离,按的取值不同又可分成:明考夫斯基距离简称明氏距离,按的取值不同又可分成:n欧氏距离是常用的距离,大家都比较熟悉,但是前面已经提欧氏距离是常用的距离,大家都比较熟悉,但是前面已经提到,在解决多元数据的分析问题时,欧氏距离就显示出了它到,在解决多元数据的分析问题时,欧氏距离就显示出了它的不足之处。一是它没有考虑到总体的变异对
7、的不足之处。一是它没有考虑到总体的变异对“距离距离”远近远近的影响,明显一个变异程度大的总体可能与更多样品近些,的影响,明显一个变异程度大的总体可能与更多样品近些,既使它们的欧氏距离不确定最近;另外,欧氏距离受变量的既使它们的欧氏距离不确定最近;另外,欧氏距离受变量的量纲影响,这对多元数据的处理是不利的。为了克服这方面量纲影响,这对多元数据的处理是不利的。为了克服这方面的不足,可用的不足,可用“马氏距离马氏距离”的概念。的概念。2马氏距离马氏距离 设设Xi与与Xj是来自均值向量为是来自均值向量为,协方差为,协方差为=(0)的总)的总体体G中的中的p维样品,则两个样品间的马氏距离为维样品,则两个
8、样品间的马氏距离为 (5.5)马氏距离又称为广义欧氏距离。明显,马氏距离与上述各种马氏距离又称为广义欧氏距离。明显,马氏距离与上述各种距离的主要不同就是它考虑了观测变量之间的相关性。假如距离的主要不同就是它考虑了观测变量之间的相关性。假如各变量之间相互独立,即观测变量的协方差矩阵是对角矩阵,各变量之间相互独立,即观测变量的协方差矩阵是对角矩阵,则马氏距离就退化为用各个观测指标的标准差的倒数作为权则马氏距离就退化为用各个观测指标的标准差的倒数作为权数的加权欧氏距离。马氏距离还考虑了观测变量之间的变异数的加权欧氏距离。马氏距离还考虑了观测变量之间的变异性,不再受各指标量纲的影响。将原始数据作线性变
9、换后,性,不再受各指标量纲的影响。将原始数据作线性变换后,马氏距离不变。马氏距离不变。3兰氏距离兰氏距离 (5.6)它仅适用于一切它仅适用于一切Xij0的状况,这个距离也可以克服各个指的状况,这个距离也可以克服各个指标之间量纲的影响。这是一个自身标准化的量,由于它对大标之间量纲的影响。这是一个自身标准化的量,由于它对大的奇异值不敏感,它特殊适合于高度偏倚的数据。虽然这个的奇异值不敏感,它特殊适合于高度偏倚的数据。虽然这个距离有助于克服明氏距离的第一个缺点,但它也没有考虑指距离有助于克服明氏距离的第一个缺点,但它也没有考虑指标之间的相关性。标之间的相关性。4距离选择的原则距离选择的原则 一般说来
10、,同一批数据接受不同的距离公式,会得到不同的分一般说来,同一批数据接受不同的距离公式,会得到不同的分类结果。产生不同结果的缘由,主要是由于不同的距离公式类结果。产生不同结果的缘由,主要是由于不同的距离公式的侧重点和实际意义都有不同。因此我们在进行聚类分析时,的侧重点和实际意义都有不同。因此我们在进行聚类分析时,应留意距离公式的选择。通常选择距离公式应留意遵循以下应留意距离公式的选择。通常选择距离公式应留意遵循以下的基本原则:的基本原则:(1)要考虑所选择的距离公式在实际应用中有明确的意义。)要考虑所选择的距离公式在实际应用中有明确的意义。如欧氏距离就有特别明确的空间距离概念。马氏距离有消退如欧
11、氏距离就有特别明确的空间距离概念。马氏距离有消退量纲影响的作用。量纲影响的作用。(2)要综合考虑对样本观测数据的预处理和将要接受的聚类)要综合考虑对样本观测数据的预处理和将要接受的聚类分析方法。如在进行聚类分析之前已经对变量作了标准化处分析方法。如在进行聚类分析之前已经对变量作了标准化处理,则通常就可接受欧氏距离。理,则通常就可接受欧氏距离。(3)要考虑探讨对象的特点和计算量的大小。样品间距离公)要考虑探讨对象的特点和计算量的大小。样品间距离公式的选择是一个比较困难且带有确定主观性的问题,我们应式的选择是一个比较困难且带有确定主观性的问题,我们应依据探讨对象的特点不同做出具体分折。实际中,聚类
12、分析依据探讨对象的特点不同做出具体分折。实际中,聚类分析前不妨摸爽性地多选择几个距离公式分别进行聚类,然后对前不妨摸爽性地多选择几个距离公式分别进行聚类,然后对聚类分析的结果进行对比分析,以确定最合适的距离测度方聚类分析的结果进行对比分析,以确定最合适的距离测度方法。法。二、变量相像性的度量二、变量相像性的度量n 多元数据中的变量表现为向量形式,在几何上可用多维空间多元数据中的变量表现为向量形式,在几何上可用多维空间中的一个有向线段表示。在对多元数据进行分析时,相对于中的一个有向线段表示。在对多元数据进行分析时,相对于数据的大小,我们更多地对变量的变更趋势或方向感爱好。数据的大小,我们更多地对
13、变量的变更趋势或方向感爱好。因此,变量间的相像性,我们可以从它们的方向趋同性或因此,变量间的相像性,我们可以从它们的方向趋同性或“相关性相关性”进行考察,从而得到进行考察,从而得到“夹角余弦法夹角余弦法”和和“相关系数相关系数”两种度量方法。两种度量方法。n1、夹角余弦、夹角余弦n两变量两变量Xi与与Xj看作看作p维空间的两个向量,这两个向量间维空间的两个向量,这两个向量间的夹角余弦可用下式进行计算的夹角余弦可用下式进行计算n (5.7)n明显,明显,cos ij 1。2相关系数相关系数相关系数常常用来度量变量间的相像性。变量相关系数常常用来度量变量间的相像性。变量Xi与与Xj的相关的相关系数
14、定义为系数定义为 (5.8)明显也有,明显也有,rij 1。n无论是夹角余弦还是相关系数,它们的确定值都小于无论是夹角余弦还是相关系数,它们的确定值都小于1,作,作为变量近似性的度量工具,我们把它们统记为为变量近似性的度量工具,我们把它们统记为cij。当。当 cij n=1时,说明变量时,说明变量Xi与与Xj完全相像;当完全相像;当 cij 近似于近似于1时,时,说说n明变量明变量Xi与与Xj特别亲密;当特别亲密;当 cij =0时,说明变量时,说明变量Xi与与Xj完完n全不一样;当全不一样;当 cij 近似于近似于0时,说明变量时,说明变量Xi与与Xj差别很差别很大。大。n据此,我们把比较相
15、像的变量聚为一类,把不太相像的据此,我们把比较相像的变量聚为一类,把不太相像的变量归到不同的类内。变量归到不同的类内。n在实际聚类过程中,为了计算便利,我们把变量间相像性的在实际聚类过程中,为了计算便利,我们把变量间相像性的度量公式作一个变换为度量公式作一个变换为n dij=1 cij (5.9)n或者或者 n dij2=1 cij2 (5.10)n 用表示变量间的距离远近,小则与先聚成一类,这比较符用表示变量间的距离远近,小则与先聚成一类,这比较符合人们的一般思维习惯。合人们的一般思维习惯。第三节第三节 系统聚类分析法系统聚类分析法 一一 系统聚类的基本思想系统聚类的基本思想 二二 类间距离
16、与系统聚类法类间距离与系统聚类法 三三 类间距离的统一性类间距离的统一性 一、系统聚类的基本思想一、系统聚类的基本思想n系统聚类的基本思想是:距离相近的样品(或变量)先聚成系统聚类的基本思想是:距离相近的样品(或变量)先聚成类,距离相远的后聚成类,过程始终进行下去,每个样品类,距离相远的后聚成类,过程始终进行下去,每个样品(或变量)总能聚到合适的类中。系统聚类过程是:假设总(或变量)总能聚到合适的类中。系统聚类过程是:假设总共有共有n个样品(或变量),第一步将每个样品(或变量)独个样品(或变量),第一步将每个样品(或变量)独自聚成一类,共有自聚成一类,共有n类;其次步依据所确定的样品(或变量)
17、类;其次步依据所确定的样品(或变量)“距离距离”公式,把距离较近的两个样品(或变量)聚合为一公式,把距离较近的两个样品(或变量)聚合为一类,其它的样品(或变量)仍各自聚为一类,共聚成类,其它的样品(或变量)仍各自聚为一类,共聚成n 1类;类;第三步将第三步将“距离距离”最近的两个类进一步聚成一类,共聚成最近的两个类进一步聚成一类,共聚成n 2类;类;,以上步骤始终进行下去,最终将全部的样品,以上步骤始终进行下去,最终将全部的样品(或变量)全聚成一类。为了直观地反映以上的系统聚类过(或变量)全聚成一类。为了直观地反映以上的系统聚类过程,可以把整个分类系统画成一张谱系图。所以有时系统聚程,可以把整
18、个分类系统画成一张谱系图。所以有时系统聚类也称为谱系分析。除系统聚类法外,还有有序聚类法、动类也称为谱系分析。除系统聚类法外,还有有序聚类法、动态聚类法、图论聚类法、模糊聚类法等,限于篇幅,我们只态聚类法、图论聚类法、模糊聚类法等,限于篇幅,我们只介绍系统聚类方法。介绍系统聚类方法。二、类间距离与系统聚类法二、类间距离与系统聚类法n在进行系统聚类之前,我们首先要定义类与类之间的距离,在进行系统聚类之前,我们首先要定义类与类之间的距离,由类间距离定义的不同产生了不同的系统聚类法。常用的类由类间距离定义的不同产生了不同的系统聚类法。常用的类间距离定义有间距离定义有8种之多,与之相应的系统聚类法也有
19、种之多,与之相应的系统聚类法也有8种,分种,分别为最短距离法、最长距离法、中间距离法、重心法、类平别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和法。它们的归类均法、可变类平均法、可变法和离差平方和法。它们的归类步骤基本上是一样的,主要差异是类间距离的计算方法不同。步骤基本上是一样的,主要差异是类间距离的计算方法不同。以下用以下用dij表示样品表示样品Xi与与Xj之间距离,用之间距离,用Dij表示类表示类Gi与与Gjn之间的距离。之间的距离。1.最短距离法最短距离法定义类与之间的距离为两类最近样品的距离,即为定义类与之间的距离为两类最近样品的距离,即为
20、 (5.11)设类与合并成一个新类记为,则任一类与的距离为设类与合并成一个新类记为,则任一类与的距离为 (5.12)n最短距离法进行聚类分析的步骤如下:最短距离法进行聚类分析的步骤如下:n(1)定义样品之间距离,计算样品的两两距离,得一)定义样品之间距离,计算样品的两两距离,得一距离距离 n 阵记为阵记为D(0),起先每个样品自成一类,明显这时,起先每个样品自成一类,明显这时Dij=n dij。n(2)找出距离最小元素,设为)找出距离最小元素,设为Dpq,则将,则将Gp和和Gq合并合并成一个成一个n 新类,记为新类,记为Gr,即,即Gr=Gp,Gq。n(3)按()按(5.12)计算新类与其它类
21、的距离。)计算新类与其它类的距离。n (4)重复()重复(2)、()、(3)两步,直到全部元素。并成一类)两步,直到全部元素。并成一类为为n 止。假如某一步距离最小的元素不止一个,则对应这些止。假如某一步距离最小的元素不止一个,则对应这些n 最小元素的类可以同时合并。最小元素的类可以同时合并。n【例【例5.1】设有六个样品,每个只测量一个指标,分别是】设有六个样品,每个只测量一个指标,分别是1,2,5,7,9,10,试用最短距离法将它们分类。,试用最短距离法将它们分类。n(1)样品接受确定值距离,计算样品间的距离阵)样品接受确定值距离,计算样品间的距离阵D(0),见表,见表5.1表表5.1(2
22、)D(0)中最小的元素是中最小的元素是D12D561,于是将,于是将G1和和G2合合并成并成G7,G5和和G6合并成合并成G8,并利用(,并利用(5.12)式计算新类与其)式计算新类与其它类的距离它类的距离D(1),见表,见表5.2表表5.2 (3)在)在D(1)中最小值是中最小值是D34D482,由于,由于G4与与G3合并,合并,又与又与G8合并,因此合并,因此G3、G4、G8合并成一个新类合并成一个新类G9,其与其,其与其它类的距离它类的距离D(2),见表,见表5.3表表5.3(4)最终将)最终将G7和和G9合并成合并成G10,这时全部的六个样品聚为,这时全部的六个样品聚为一类,其过程终止
23、。一类,其过程终止。上述聚类的可视化过程见图上述聚类的可视化过程见图5.1所示,横坐标的刻度表示并类所示,横坐标的刻度表示并类的距离。这里我们应当留意,聚类的个数要以实际状况所定,的距离。这里我们应当留意,聚类的个数要以实际状况所定,其具体内容将在后面探讨。其具体内容将在后面探讨。图图5.1 最短距离聚类法的过程最短距离聚类法的过程n再找距离最小两类并类,直至全部的样品全归为一类为止。再找距离最小两类并类,直至全部的样品全归为一类为止。可以看出最长距离法与最短距离法只有两点不同:可以看出最长距离法与最短距离法只有两点不同:n一是类与类之间的距离定义不同;一是类与类之间的距离定义不同;n另一是计
24、算新类与其它类的距离所用的公式不同。另一是计算新类与其它类的距离所用的公式不同。3.中间距离法中间距离法最短、最长距离定义表示都是极端状况,我们定义类间距离最短、最长距离定义表示都是极端状况,我们定义类间距离可以既不接受两类之间最近的距离也不接受两类之间最远的可以既不接受两类之间最近的距离也不接受两类之间最远的距离,而是接受介于两者之间的距离,称为中间距离法。距离,而是接受介于两者之间的距离,称为中间距离法。中间距离将类中间距离将类Gp与与Gq类合并为类类合并为类Gr,则随意的类,则随意的类Gk和和Gr的距离公式为的距离公式为 (14 0)(5.15)设设DkqDkp,假如接受最短距离法,则,
25、假如接受最短距离法,则Dkr=Dkp,假如,假如接受接受最长距离法,则最长距离法,则Dkr=Dkq。如图。如图5.2所示,所示,(5.15)式就是取式就是取它们(最长距离与最短距离)的中间一点作为计算它们(最长距离与最短距离)的中间一点作为计算Dkr的依的依据。据。n特殊当特殊当=14,它表示取中间点算距离,公式为,它表示取中间点算距离,公式为n (5.16)图图5.2 中间距离法中间距离法n n n n【例【例5.2】针对例】针对例5.1的数据,试用重心法将它们聚类。的数据,试用重心法将它们聚类。n(1)样品接受欧氏距离,计算样品间的平方距离阵)样品接受欧氏距离,计算样品间的平方距离阵D2(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 建模 培训 讲座 第四 优秀 PPT
限制150内