数学建模方法详解--16种常用算法.doc
《数学建模方法详解--16种常用算法.doc》由会员分享,可在线阅读,更多相关《数学建模方法详解--16种常用算法.doc(74页珍藏版)》请在冰点文库上搜索。
数学建模方法详解--三十四种常用算法
目录
一、主成分分析法 2
二、因子分析法 5
三、聚类分析 9
四、最小二乘法与多项式拟合 16
五、方差分析法 22
六、逼近理想点排序法 27
七、动态加权法 28
八、灰色关联分析法 30
九、灰色预测法 32
十、模糊综合评价 34
十一、时间序列分析法 36
十二、蒙特卡罗(MC)仿真模型 41
十三、BP神经网络方法 43
十四、数据包络分析法(DEA) 50
十五、多因素方差分析法(基于SPSS) 53
十六、拉格朗日插值 69
一、主成分分析法
一)、主成分分析法介绍:
主成分分析(principalcomponentsanalysis,PCA)又称:
主分量分析,主成分回归分析法。
旨在利用降维的思想,把多指标转化为少数几个综合指标。
它是一个线性变换。
这个变换把数据变换到一个新的坐标系统中,使得任何数据投影的第一大方差在第一个坐标(称为第一主成分)上,第二大方差在第二个坐标(第二主成分)上,依次类推。
主成分分析经常用减少数据集的维数,同时保持数据集的对方差贡献最大的特征。
这是通过保留低阶主成分,忽略高阶主成分做到的。
这样低阶成分往往能够保留住数据的最重要方面。
但是,这也不是一定的,要视具体应用而定。
二)、主成分分析法的基本思想:
在实证问题研究中,为了全面、系统地分析问题,我们必须考虑众多影响因素。
这些涉及的因素一般称为指标,在多元统计分析中也称为变量。
因为每个变量都在不同程度上反映了所研究问题的某些信息,并且指标之间彼此有一定的相关性,因而所得的统计数据反映的信息在一定程度上有重叠。
在用统计方法研究多变量问题时,变量太多会增加计算量和增加分析问题的复杂性,人们希望在进行定量分析的过程中,涉及的变量较少,得到的信息量较多。
主成分分析正是适应这一要求产生的,是解决这类题的理想工具。
同样,在科普效果评估的过程中也存在着这样的问题。
科普效果是很难具体量化的。
在实际评估工作中,我们常常会选用几个有代表性的综合指标,采用打分的方法来进行评估,故综合指标的选取是个重点和难点。
如上所述,主成分分析法正是解决这一问题的理想工具。
因为评估所涉及的众多变量之间既然有一定的相关性,就必然存在着起支配作用的因素。
根据这一点,通过对原始变量相关矩阵内部结构的关系研究,找出影响科普效果某一要素的几个综合指标,使综合指标为原来变量的线性拟合。
这样,综合指标不仅保留了原始变量的主要信息,且彼此间不相关,又比原始变量具有某些更优越的性质,就使我们在研究复杂的科普效果评估问题时,容易抓住主要矛盾。
上述想法可进一步概述为:
设某科普效果评估要素涉及个指标,这指标构成的维随机向量为。
对作正交变换,令,其中为正交阵,的各分量是不相关的,使得的各分量在某个评估要素中的作用容易解释,这就使得我们有可能从主分量中选择主要成分,削除对这一要素影响微弱的部分,通过对主分量的重点分析,达到对原始变量进行分析的目的。
的各分量是原始变量线性组合,不同的分量表示原始变量之间不同的影响关系。
由于这些基本关系很可能与特定的作用过程相联系,主成分分析使我们能从错综复杂的科普评估要素的众多指标中,找出一些主要成分,以便有效地利用大量统计数据,进行科普效果评估分析,使我们在研究科普效果评估问题中,可能得到深层次的一些启发,把科普效果评估研究引向深入。
例如,在对科普产品开发和利用这一要素的评估中,涉及科普创作人数百万人、科普作品发行量百万人、科普产业化(科普示范基地数百万人)等多项指标。
经过主成分分析计算,最后确定个或个主成分作为综合评价科普产品利用和开发的综合指标,变量数减少,并达到一定的可信度,就容易进行科普效果的评估。
三)、主成分分析法的数学模型:
其中:
为第j个指标对应于第个主成分的初始因子载荷,
为第l个主成分对应的特征值
根据主成分表达式得出综合得分模型:
四)、主成分分析法的基本原理:
主成分分析法是一种降维的统计方法,它借助于一个正交变换,将其分量相关的原随机向量转化成其分量不相关的新随机向量,这在代数上表现为将原随机向量的协方差阵变换成对角形阵,在几何上表现为将原坐标系变换成新的正交坐标系,使之指向样本点散布最开的p个正交方向,然后对多维变量系统进行降维处理,使之能以一个较高的精度转换成低维变量系统,再通过构造适当的价值函数,进一步把低维系统转化成一维系统。
五)、主成分分析法的作用:
概括起来说,主成分分析主要由以下几个方面的作用。
1.主成分分析能降低所研究的数据空间的维数。
即用研究m维的Y空间代替p维的X空间(m<p),而低维的Y空间代替高维的x空间所损失的信息很少。
即:
使只有一个主成分Yl(即m=1)时,这个Yl仍是使用全部X变量(p个)得到的。
例如要计算Yl的均值也得使用全部x的均值。
在所选的前m个主成分中,如果某个Xi的系数全部近似于零的话,就可以把这个Xi删除,这也是一种删除多余变量的方法。
2.有时可通过因子负荷aij的结论,弄清X变量间的某些关系。
3.多维数据的一种图形表示方法。
我们知道当维数大于3时便不能画出几何图形,多元统计研究的问题大都多于3个变量。
要把研究的问题用图形表示出来是不可能的。
然而,经过主成分分析后,我们可以选取前两个主成分或其中某两个主成分,根据主成分的得分,画出n个样品在二维平面上的分布况,由图形可直观地看出各样品在主分量中的地位,进而还可以对样本进行分类处理,可以由图形发现远离大多数样本点的离群点。
4.由主成分分析法构造回归模型。
即把各主成分作为新自变量代替原来自变量x做回归分析。
5.用主成分分析筛选回归变量。
回归变量的选择有着重的实际意义,为了使模型本身易于做结构分析、控制和预报,好从原始变量所构成的子集合中选择最佳变量,构成最佳变量集合。
用主成分分析筛选变量,可以用较少的计算量来选择量,获得选择最佳变量子集合的效果。
六)、主成分分析法的计算步骤:
1、原始指标数据的标准化采集p维随机向量x=(x1,X2,...,Up)T)n个样品xi=(xi1,xi2,...,dip)T,I=1,2,…,n,
n>p,构造样本阵,对样本阵元进行如下标准化变换:
其中,得标准化阵Z。
2、对标准化阵Z求相关系数矩阵
其中,。
3、解样本相关矩阵R的特征方程得p个特征根,确定主成分
按确定m值,使信息的利用率达85%以上,对每个job,j=1,2,...,m,解方程组Rib=job得单位特征向量。
4、将标准化后的指标变量转换为主成分
U1称为第一主成分,U2称为第二主成分,…,Up称为第p主成分。
5、对m个主成分进行综合评价
对m个主成分进行加权求和,即得最终评价值,权数为每个主成分的方差贡献率。
PS另一种易于理解的步骤:
1、数据标准化;
2、求相关系数矩阵;
3、一系列正交变换,使非对角线上的数置0,加到主对角上;
得特征根xi(即相应那个主成分引起变异的方差),并按照从大到小的顺序把特征根排列;
4、求各个特征根对应的特征向量;
用下式计算每个特征根的贡献率Vi;
VI=xi/(x1+x2+........)
5、根据特征根及其特征向量解释主成分物理意义
七)、主成分分析法的案例:
参见:
基于主成分分析的力量结构指标的权重的计算、基于主成分析的江苏省地方高校创新力研究
二、因子分析法
一)因子分析法介绍:
主成分分析通过线性组合将原变量综合成几个主成分,用较少的综合指标来代替原来较多的指标(变量)。
在多变量分析中,某些变量间往往存在相关性。
是什么原因使变量间有关联呢?
是否存在不能直接观测到的、但影响可观测变量变化的公共因子?
因子分析法(FactorAnalysis)就是寻找这些公共因子的模型分析方法,它是在主成分的基础上构筑若干意义较为明确的公因子,以它们为框架分解原变量,以此考察原变量间的联系与区别。
例:
随着年龄的增长,儿童的身高、体重会随着变化,具有一定的相关性,身高和体重之间为何会有相关性呢?
因为存在着一个同时支配或影响着身高与体重的生长因子。
那么,我们能否通过对多个变量的相关系数矩阵的研究,找出同时影响或支配所有变量的共性因子呢?
因子分析就是从大量的数据中“由表及里”、“去粗取精”,寻找影响或支配变量的多变量统计方法。
因此,可以说因子分析是主成分分析的推广,也是一种把多个变量化为少数几个综合变量的多变量分析方法,其目的是用有限个不可观测的隐变量来解释原始变量之间的相关关系。
因子分析主要用于:
1、减少分析变量个数;2、通过对变量间相关关系探测,将
原始变量进行分类。
即将相关性高的变量分为一组,用共性因子代替该组变量。
二)、因子分析法的基本模型:
因子分析法是从研究变量内部相关的依赖关系出发,把一些具有错综复杂关系的变量归结为少数几个综合因子的一种多变量统计分析方法。
它的基本思想是将观测变量进行分类,将相关性较高,即联系比较紧密的分在同一类中,而不同类变量之间的相关性则较低,那么每一类变量实际上就代表了一个基本结构,即公共因子。
对于所研究的问题就是试图用最少个数的不可测的所谓公共因子的线性函数与特殊因子之和来描述原来观测的每一分量。
因子分析模型描述如下:
1、X=(x1,x2,…,xp)是可观测随机向量,均值向量E(X)=0,协方差阵Cov(X)=∑,且协方差阵∑与相关矩阵R相等(只要将变量标准化即可实现)。
2、F=(F1,F2,…,Fm)(m
3、e=(e1,e2,…,ep)与F相互独立,且E(e)=0,e的协方差阵∑是对角阵,即各分量e之间是相互独立的,则模型:
x1=a11F1+a12F2+…+a1mFm+e1
x2=a21F1+a22F2+…+a2mFm+e2
xp=ap1F1+ap2F2+…+apmFm+ep
称为因子分析模型,由于该模型是针对变量进行的,各因子又是正交的,所以也称为R型正交因子模型。
其矩阵形式为:
x=AF+e
其中:
x=,A=,F=,e=
这里
(1)m£p;
(2)Cov(F,e)=0,即F和e是不相关的;
(3)D(F)=Im,即F1,F2,…,Fm不相关且方差均为1;
(4)D(e)=,即e1,e2,…,ep不相关,且方差不同。
我们把F称为X的公共因子或潜因子,矩阵A称为因子载荷矩阵,e称为X的特殊因子。
A=(aij),aij为因子载荷。
数学上可以证明,因子载荷aij就是第i变量与第j因子的相关系数,反映了第i变量在第j因子上的重要性。
三)、模型的统计意义:
模型中F1,F2,…,Fm叫做主因子或公共因子,它们是在各个原观测变量的表达式中都共同出现的因子,是相互独立的不可观测的理论变量。
公共因子的含义,必须结合具体问题的实际意义而定。
e1,e2,…,ep叫做特殊因子,是向量x的分量xi(i=1,2,…,p)所特有的因子,各特殊因子之间以及特殊因子与所有公共因子之间都是相互独立的。
模型中载荷矩阵A中的元素(aij)是为因子载荷。
因子载荷aij是xi与Fj的协方差,也是xi与Fj的相关系数,它表示xi依赖Fj的程度。
可将aij看作第i个变量在第j公共因子上的权,aij的绝对值越大(|aij|£1),表明xi与Fj的相依程度越大,或称公共因子Fj对于xi的载荷量越大。
为了得到因子分析结果的经济解释,因子载荷矩阵A中有两个统计量十分重要,即变量共同度和公共因子的方差贡献。
因子载荷矩阵A中第i行元素之平方和记为hi2,称为变量xi的共同度。
它是全部公共因子对xi的方差所做出的贡献,反映了全部公共因子对变量xi的影响。
hi2大表明x的第i个分量xi对于F的每一分量F1,F2,…,Fm的共同依赖程度大。
将因子载荷矩阵A的第j列(j=1,2,…,m)的各元素的平方和记为gj2,称为公共因子Fj对x的方差贡献。
gj2就表示第j个公共因子Fj对于x的每一分量xi(i=1,2,…,p)所提供方差的总和,它是衡量公共因子相对重要性的指标。
gj2越大,表明公共因子Fj对x的贡献越大,或者说对x的影响和作用就越大。
如果将因子载荷矩阵A的所有gj2(j=1,2,…,m)都计算出来,使其按照大小排序,就可以依此提炼出最有影响力的公共因子。
四)、因子旋转:
建立因子分析模型的目的不仅是找出主因子,更重要的是知道每个主因子的意义,以便对实际问题进行分析。
如果求出主因子解后,各个主因子的典型代表变量不很突出,还需要进行因子旋转,通过适当的旋转得到比较满意的主因子。
旋转的方法有很多,正交旋转(orthogonalrotation)和斜交旋转(obliquerotation)是因子旋转的两类方法。
最常用的方法是最大方差正交旋转法(Varimax)。
进行因子旋转,就是要使因子载荷矩阵中因子载荷的平方值向0和1两个方向分化,使大的载荷更大,小的载荷更小。
因子旋转过程中,如果因子对应轴相互正交,则称为正交旋转;如果因子对应轴相互间不是正交的,则称为斜交旋转。
常用的斜交旋转方法有Promax法等。
五)、因子得分:
因子分析模型建立后,还有一个重要的作用是应用因子分析模型去评价每个样品在整个模型中的地位,即进行综合评价。
例如地区经济发展的因子分析模型建立后,我们希望知道每个地区经济发展的情况,把区域经济划分归类,哪些地区发展较快,哪些中等发达,哪些较慢等。
这时需要将公共因子用变量的线性组合来表示,也即由地区经济的各项指标值来估计它的因子得分。
设公共因子F由变量x表示的线性组合为:
Fj=uj1xj1+uj2xj2+…+ujpxjpj=1,2,…,m
该式称为因子得分函数,由它来计算每个样品的公共因子得分。
若取m=2,则将每个样品的p个变量代入上式即可算出每个样品的因子得分F1和F2,并将其在平面上做因子得分散点图,进而对样品进行分类或对原始数据进行更深入的研究。
但因子得分函数中方程的个数m小于变量的个数p,所以并不能精确计算出因子得分,只能对因子得分进行估计。
估计因子得分的方法较多,常用的有回归估计法,Bartlett估计法,Thomson估计法。
具体方法为:
(1)回归估计法
F=Xb=X(X¢X)-1A¢=XR-1A¢(这里R为相关阵,且R=X¢X)。
(2)Bartlett估计法
Bartlett估计因子得分可由最小二乘法或极大似然法导出。
F=(W-1/2A)¢W-1/2A]-1(W-1/2A)¢W-1/2X=(A¢W-1A)-1A¢W-1X
(3)Thomson估计法
在回归估计法中,实际上是忽略特殊因子的作用,取R=X¢X,若考虑特殊因子的作用,此时R=X¢X+W,于是有:
F=XR-1A¢=X(X¢X+W)-1A¢
这就是Thomson估计的因子得分,使用矩阵求逆算法(参考线性代数文献)可以将其转换为:
F=XR-1A¢=X(I+A¢W-1A)-1W-1A¢
六)、因子分析的步骤:
因子分析的核心问题有两个:
一是如何构造因子变量;二是如何对因子变量进行命名解释。
因此,因子分析的基本步骤和解决思路就是围绕这两个核心问题展开的。
因子分析常常有以下四个基本步骤:
1、确认待分析的原变量是否适合作因子分析。
2、构造因子变量。
3、利用旋转方法使因子变量更具有可解释性。
4、计算因子变量得分。
因子分析的计算过程:
1、将原始数据标准化,以消除变量间在数量级和量纲上的不同。
2、求标准化数据的相关矩阵;
3、求相关矩阵的特征值和特征向量;
4、计算方差贡献率与累积方差贡献率;
5、确定因子:
设F1,F2,…,Fp为p个因子,其中前m个因子包含的数据信息总量(即其累积贡献率)不低于80%时,可取前m个因子来反映原评价指标;
6、因子旋转:
若所得的m个因子无法确定或其实际意义不是很明显,这时需将因子进行旋转以获得较为明显的实际含义。
7、用原指标的线性组合来求各因子得分:
采用回归估计法,Bartlett估计法或Thomson估计法计算因子得分。
8、综合得分:
以各因子的方差贡献率为权,由各因子的线性组合得到综合评价指标函数。
F=(w1F1+w2F2+…+wmFm)/(w1+w2+…+wm)
此处wi为旋转前或旋转后因子的方差贡献率。
9、得分排序:
利用综合得分可以得到得分名次。
七)、主成分分析法的使用范围:
1、简化系统结构,探讨系统内核。
可采用主成分分析、因子分析、对应分析等方法,在众多因素中找出各个变量最佳的子集合,从子集合所包含的信息描述多变量的系统结果及各个因子对系统的影响。
“从树木看森林”,抓住主要矛盾,把握主要矛盾的主要方面,舍弃次要因素,以简化系统的结构,认识系统的内核。
2、构造预测模型,进行预报控制。
在自然和社会科学领域的科研与生产中,探索多变量系统运动的客观规律及其与外部环境的关系,进行预测预报,以实现对系统的最优控制,是应用多元统计分析技术的主要目的。
在多元分析中,用于预报控制的模型有两大类。
一类是预测预报模型,通常采用多元线性回归或逐步回归分析、判别分析、双重筛选逐步回归分析等建模技术。
另一类是描述性模型,通常采用聚类分析的建模技术。
3、进行数值分类,构造分类模式。
在多变量系统的分析中,往往需要将系统性质相似的事物或现象归为一类。
以便找出它们之间的联系和内在规律性。
过去许多研究多是按单因素进行定性处理,以致处理结果反映不出系统的总的特征。
进行数值分类,构造分类模式一般采用聚类分析和判别分析技术。
如何选择适当的方法来解决实际问题,需要对问题进行综合考虑。
对一个问题可以综合运用多种统计方法进行分析。
例如一个预报模型的建立,可先根据有关生物学、生态学原理,确定理论模型和试验设计;根据试验结果,收集试验资料;对资料进行初步提炼;然后应用统计分析方法(如相关分析、逐步回归分析、主成分分析等)研究各个变量之间的相关性,选择最佳的变量子集合;在此基础上构造预报模型,最后对模型进行诊断和优化处理,并应用于生产实际。
三、聚类分析
一)聚类分析的概念:
聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。
它是一种重要的人类行为。
聚类与分类的不同在于,聚类所要求划分的类是未知的。
聚类是将数据分类到不同的类或者簇这样的一个过程,所以同一个簇中的对象有很大的相似性,而不同簇间的对象有很大的相异性。
从统计学的观点看,聚类分析是通过数据建模简化数据的一种方法。
传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。
采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中,如SPSS、SAS等。
二)、聚类分析的主要应用:
在商业上
聚类分析被用来发现不同的客户群,并且通过购买模式刻画不同的客户群的特征;
在生物上
聚类分析被用来动植物分类和对基因进行分类,获取对种群固有结构的认识
在地理上
聚类能够帮助在地球中被观察的数据库商趋于的相似性
在保险行业上
聚类分析通过一个高的平均消费来鉴定汽车保险单持有者的分组,同时根据住宅类型,价值,地理位置来鉴定一个城市的房产分组
在因特网应用上
聚类分析被用来在网上进行文档归类来修复信息
在电子商务上
聚类分析在电子商务中网站建设数据挖掘中也是很重要的一个方面,通过分组聚类出具有相似浏览行为的客户,并分析客户的共同特征,可以更好的帮助电子商务的用户了解自己的客户,向客户提供更合适的服务。
三)聚类分析的主要步骤:
1、数据预处理,
2、为衡量数据点间的相似度定义一个距离函数,
3、聚类或分组,
4、评估输出。
数据预处理包括选择数量,类型和特征的标度,它依靠特征选择和特征抽取,特征选择选择重要的特征,特征抽取把输入的特征转化为一个新的显著特征,它们经常被用来获取一个合适的特征集来为避免“维数灾”进行聚类,数据预处理还包括将孤立点移出数据,孤立点是不依附于一般数据行为或模型的数据,因此孤立点经常会导致有偏差的聚类结果,因此为了得到正确的聚类,我们必须将它们剔除。
既然相类似性是定义一个类的基础,那么不同数据之间在同一个特征空间相似度的衡量对于聚类步骤是很重要的,由于特征类型和特征标度的多样性,距离度量必须谨慎,它经常依赖于应用,例如,通常通过定义在特征空间的距离度量来评估不同对象的相异性,很多距离度都应用在一些不同的领域,一个简单的距离度量,如Euclidean距离,经常被用作反映不同数据间的相异性,一些有关相似性的度量,例如PMC和SMC,能够被用来特征化不同数据的概念相似性,在图像聚类上,子图图像的误差更正能够被用来衡量两个图形的相似性。
将数据对象分到不同的类中是一个很重要的步骤,数据基于不同的方法被分到不同的类中,划分方法和层次方法是聚类分析的两个主要方法,划分方法一般从初始划分和最优化一个聚类标准开始。
CrispClustering,它的每一个数据都属于单独的类;FuzzyClustering,它的每个数据可能在任何一个类中,CrispClustering和FuzzyClusterin是划分方法的两个主要技术,划分方法聚类是基于某个标准产生一个嵌套的划分系列,它可以度量不同类之间的相似性或一个类的可分离性用来合并和分裂类,其他的聚类方法还包括基于密度的聚类,基于模型的聚类,基于网格的聚类。
评估聚类结果的质量是另一个重要的阶段,聚类是一个无管理的程序,也没有客观的标准来评价聚类结果,它是通过一个类有效索引来评价,一般来说,几何性质,包括类间的分离和类内部的耦合,一般都用来评价聚类结果的质量,类有效索引在决定类的数目时经常扮演了一个重要角色,类有效索引的最佳值被期望从真实的类数目中获取,一个通常的决定类数目的方法是选择一个特定的类有效索引的最佳值,这个索引能否真实的得出类的数目是判断该索引是否有效的标准,很多已经存在的标准对于相互分离的类数据集合都能得出很好的结果,但是对于复杂的数据集,却通常行不通,例如,对于交叠类的集合。
四)聚类分析的计算方法:
1、划分法(partitioningmethods):
给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,K而且这K个分组满足下列条件:
(1)每一个分组至少包含一个数据纪录;
(2)每一个数据纪录属于且仅属于一个分组(注意:
这个要求在某些模糊聚类算法中可以放宽);对于给定的K,算法首先给出一个初始的分组方法,以后通过反复迭代的方法改变分组,使得每一次改进之后的分组方案都较前一次好,而所谓好的标准就是:
同一分组中的记录越近越好,而不同分组中的纪录越远越好。
使用这个基本思想的算法有:
K-MEANS算法、K-MEDOIDS算法、CLARANS算法;
2、层次法(hierarchicalmethods):
这种方法对给定的数据集进行层次似的分解,直到某种条件满足为止。
具体又可分为“自底向上”和“自顶向下”两种方案。
例如在“自底向上”方案中,初始时每一个数据纪录都组成一个单独的组,在接下来的迭代中,它把那些相互邻近的组合并成一个组,直到所有的记录组成一个分组或者某个条件满足为止。
代表算法有:
BIRCH算法、CURE算法、CHAMELEON算法等;
3、基于密度的方法(density-basedmethods):
基于密度的方法与其它方法的一个根本区别是:
它不是基于各种各样的距离的,而是基于密度的。
这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
这个方法的指导思想就是,只要一个区域中的点的密度大过某个阀值,就把它加到与之相近的聚类中去。
代表算法有:
DBSCAN算法