建模有关算法及数据处理与分析步骤笔记.doc

建模有关算法
规划求解法
建立优化模型要确定优化的目标和寻求的决策。用x表示决策变量，f(x)表示目标函数。实际问题一般对决策变量x的取值范围有限制，不妨记作x∈Ω, Ω称为可行域。优化问题的数学模型可表示为min(或max)f(x),x∈Ω。实际中的优化问题通常有多个决策变量，用n维向量x=(x1,x2,…,xn)T表示，目标函数f(x)是多元函数，可行域比较复杂，常用一组不等式（也可以有等式）gi(x)≤0(i=1,2, …,m)来界定，称为约束条件。一般地，这类模型可表述成如下形式minZ=f(x),s.t. gi(x)≤0(i=1,2, …,m)这里的s.t.是“受约束于”的意思。
显然，上述模型属于多元函数的条件极值问题的范围，然而许多实际问题归结出的这种形式的优化模型，其决策变量个数n和约束条件个数m一般较大，并且最优解往往在可行域的边界上取得，这样就不能简单地用微分法求解数学规划是解决这类问题的有效方法。
在Excel中应用迭代法求解线性方程组
针对线性方程组的迭代解法章节中的雅可比(Jacobi)迭代法和塞德尔(Seidel)迭代法算例，通过Excel 应用软件进行试算，计算结果与算例中的计算结果完全吻合，可以省去程序设计的烦恼和对编程不熟悉所带来的尴尬。
最短路问题求解法
Dijkstra算法：求G中从顶点到其余顶点的最短路。
直接在图的带权邻接矩阵中用插入顶点的方法依次构造出个矩阵D(1)、 D(2)、… 、D()，使最后得到的矩阵D()成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
Floyd算法：求任意两点间的最短路。
D(i,j)：i到j的距离。R(i,j)：i到j之间的插入点。输入: 带权邻接矩阵w(i,j)
(1) 赋初值：
对所有i,j, d(i,j)w(i,j), r(i,j)j, k1
(2) 更新d(i,j),r(i,j)
对所有i,j，若d(i,k)+d(k,j)<d(i,j)，则d(i,j)d(i,k)+d(k,j), r(i,j)k
(3) 若k=，停止．否则kk+1，转（２）．
行遍性问题求解法
Fleury算法：求欧拉图的欧拉巡回.
Fleury算法基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止。
Fleury算法—算法步骤：
（１）任选一个顶点v0，令道路w0=v0.
（２）假定道路wi=v0e1v1e2…eivi已经选好，则从E\{e1,e2,…,ei}中选一条边ei+1，使：
a）ei+1与vi相关联
b）除非不能选择，否则一定要使ei+1不是Gi=G[E-{e1,e2,…,ei}]的割边．
（３）第（２）步不能进行时就停止．
若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次。解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．
回归分析法
一元线性回归：一般地，称由 确定的模型为一元线性回归模型，记为

固定的未知参数、称为回归系数，自变量x也称为回归变量。，称为y对x的回归直线方程.
一元线性回归分析的主要任务是：
1．用试验值（样本值）对、和作点估计；
2．对回归系数、作假设检验；
3．在x=处对y作预测，对y作区间估计.
回归系数的最小二乘估计：有n组独立观测值（x1，y1），（x2，y2），…，（xn，yn ）设
记
最小二乘法就是选择和的估计，使得
解得或
的无偏估计：记
称Qe为残差平方和或剩余平方和(SSE)。的无偏估计为 称为剩余方差（残差的方差）， 分别与、独立。称为剩余标准差。
回归方程的显著性检验：对回归方程的显著性检验，归结为对假设
进行检验. 假设被拒绝，则回归显著，认为y与x存在线性关系，所求的线性回归方程有意义；否则回归不显著，y与x的关系不能用一元线性回归模型来描述，所得的回归方程也无意义。
F检验：当成立时， ~F（1，n-2）其中 （回归平方和）(SSR)。记 称Qe为残差平方和或剩余平方和(SSE)。故F>，拒绝，否则就接受.
r检验: 记 当|r|> r时，拒绝H0；否则就接受H0。其中
回归系数的置信区间：和置信水平为1-α的置信区间分别为

和
的置信水平为1-的置信区间为
多项式回归：设变量x、Y的回归模型为

其中p是已知的，是未知参数，服从正态分布。
称为回归多项式。上面的回归模型称为多项式回归。
令，i=1，2，…，k多项式回归模型变为多元线性回归模型.
插值求解法
一维插值定义：给出一些点，构造一个曲线，使这个曲线严格过这些点。
一维插值函数：yi=interp1(x，y，xi，'method')
一维插值方法：‘nearest’最邻近插值；‘linear’线性插值；‘spline’ 三次样条插值；‘cubic’立方插值；缺省时分段线性插值．
（所有的插值方法都要求x是单调的，并且xi不能够超过x的范围。）
二维插值定义：给出空间的一些点，构成一个曲面，使这个曲面过这些点。二维插值分为网络节点插值和散乱节点插值。
用MATLAB作网格节点数据的插值函数：z=interp2(x0,y0,z0,x,y,’method’)
（要求x0,y0单调；x，y可取为矩阵，或x取行向量，y取为列向量，x,y的值分别不能超出x0,y0的范围．）
二维插值方法：‘nearest’最邻近插值；‘linear’双线性插值；‘cubic’双三次插值；缺省时双线性插值。
用MATLAB作散点数据的插值函数：cz =griddata（x，y，z，cx，cy，‘method’） （要求cx取行向量，cy取为列向量．）
插值方法：‘nearest’最邻近插值；‘linear’ 双线性插值；‘cubic’ 双三次插值；'v4'- MATLAB提供的插值方法；缺省时,双线性插值。
拟合求解法
拟合定义：已知一组（二维）数据，即平面上 n个点（xi,yi) i=1,…,n, 寻求一个函数（曲线）y=f(x), 使 f(x) 在某种准则下与所有数据点最为接近，即曲线拟合得最好．
拟合与插值的关系：若要求所求曲线（面）通过所给所有数据点，就是插值问题若不要求曲线（面）通过所有数据点，而是要求它反映对象整体的变化趋势，这就是数据拟合，又称曲线拟合或曲面拟合。函数插值与曲线拟合都是要根据一组数据构造一个函数作为近似，由于近似的要求不同，二者在数学方法上是完全不同的．
曲线拟合问题最常用的解法——线性最小二乘法的基本思路：
第一步:先选定一组函数 r1(x), r2(x), …,rm(x), m<n, 令
f(x)=a1r1(x)+a2r2(x)+…+amrm(x) （1）
其中 a1,a2, …,am 为待定系数．
第二步: 确定a1,a2, …,am 的准则（最小二乘准则）：
使n个点（xi,yi) 与曲线 y=f(x) 的距离di 的平方和最小 ．
记
问题则归结为，求 a1,a2, …,am 使 J (a1,a2, …,am) 最小．
系统聚类分析法
聚类分析主要是研究在事先没有分类的情况下，如何将样本归类的方法。
聚类分析又称群分析，它是研究（样品或指标）分类问题的一种多元统计方法，所谓类，通俗地说，就是指相似元素的集合。严格的数学定义是较麻烦的，在不同问题中类的定义是不同的。值得提出的是将聚类分析和其它方法联合起来使用，如判别分析、主成分分析、回归分析等往往效果更好。
聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。我们主要介绍常用的系统聚类法。
系统聚类法的基本原理：首先将一定数量的样品（或指标）各自看成一类，然后根据样品（或指标）的亲疏程度，将亲疏程度最高的两类合并，如此重复进行，直到所有的样品都合成一类（即，将一个样品看作P维空间的一个点，并在空间定义距离，距离越近的点归为一类，距离较远的点归为不同的类）。衡量亲疏程度的指标有两类：距离、相似系数。
设有n个样品，每个样品测得p项指标（变量），原始资料阵为

其中为第i个样品的第j个指标的观测数据。第i个样品Xi为矩阵X的第i行所描述，所以任何两个样品XK与XL之间的相似性，可以通过矩阵X中的第K行与第L行的相似程度来刻划；任何两个变量与之间的相似性，可以通过第K列与第L列的相似程度来刻划。
如果把n个样品（X中的n个行）看成p维空间中n个点，则两个样品间相似程度可用p维空间中两点的距离来度量。令dij表示样品Xi与Xj的距离。常用的距离有：欧氏距离、标准化欧氏距离、布洛克距离（绝对距离）、闵可夫斯基（Minkowski）距离、马氏（Mahalanobis）距离、余弦距离、相似距离等。而常用的聚类方法有最短距离法、最长距离法、中间距离法、重心法、平方和递增法等等。在此我们就不再一一叙述了。
判别分析法
判别分析与聚类分析不同。判别分析是在已知研究对象分成若干类型（或组别）并已取得各种类型的一批已知样品的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分类。对于聚类分析来说，一批给定样品要划分的类型事先并不知道，正需要通过聚类分析来给以确定类型的。
正因为如此，判别分析和聚类分析往往联合起来使用，例如判别分析是要求先知道各类总体情况才能判断新样品的归类，当总体分类不清楚时，可先用聚类分析对原来的一批样品进行分类，然后再用判别分析建立判别式以对新样品进行判别。
判别分析可以从不同角度提出的问题，因此有不同的判别准则，如马氏距离最小准则、Fisher准则、平均损失最小准则、最小平方准则、最大似然准则、最大概率准则等等，按判别准则的不同又提出多种判别方法。我们常用的四种判别方法是距离判别法、Fisher判别法、Bayes判别法和逐步判别法。下面我们简单介绍这四种方法（具体函数导出略）：
1、距离判别法 基本思想：首先根据已知分类的数据，分别计算各类的重心即分组（类）的均值，判别准则是对任给的一次观测，若它与第i类的重心距离最近，就认为它来自第i类。距离判别法，对各类（或总体）的分布，并无特定的要求。
2、Fisher判别法 Fisher判别法是1936年提出来的，该法对总体的分布并未提出什么特定的要求。Fisher判别法又分为不等协差阵的两总体Fisher判别法和多总体Fisher判别法。
基本思想：从两个总体中抽取具有p个指标的样品观测数据，借助方差分析的思想造一个判别函数或称判别式：，其中系数、…、确定的原则是使两组间的区别最大，而使每个组内部的离差最小。有了判别式后，对于一个新的样品，将它的p个指标值代入判别式中求出y值，然后与判别临界值（或称分界点后面给出）进行比较，就可以判别它应属于哪一个总体。
3、Bayes判别法 Fisher判别法是随着总体个数的增加，建立的判别式也增加，因而计算起来还是比较麻烦的。如果对多个总体的判别考虑的不是建立判别式，而是计算新给样品属于各总体的条件概率。比较这k个概率的大小，然后将新样品判归为来自概率最大的总体，这种判别法称为Bayes判别法。
基本思想：Bayes判别法的基本思想总是假定对所研究的对象已有一定的认识，常用先验概率来描述这种认识。
4、逐步判别法
基本思想：逐步判别法与逐步回归法的基本思想类似，都是采用“有进有出”的算法，即逐步引入变量，每引入一个“最重要”的变量进入判别式，同时也考虑较早引入判别式的某些变量，如果其判别能力随新引入变量而变为不显著了（例如其作用被后引入的某几个变量的组合所代替），应及时从判别式中把它剔除去，直到判别式中没有不重要的变量需要剔除，而剩下来的变量也没有重要的变量可引入判别式时，逐步筛选结束。这个筛选过程实质就是作假设检验，通过检验找出显著性变量，剔除不显著变量。
模糊聚类分析方法
在科学技术、经济管理中常常要按一定的标准（相似程度或亲疏关系）进行分类。例如，根据生物的某些性状可对生物分类，根据土壤的性质可对土壤分类等。对所研究的事物按一定标准进行分类的数学方法称为聚类分析，它是多元统计“物以类聚”的一种分类方法。由于科学技术、经济管理中的分类界限往往不分明，因此采用模糊聚类方法通常比较符合实际。
模糊聚类分析的一般步骤：
第一步：数据标准化[9]
（1） 数据矩阵
设论域为被分类对象，每个对象又有个指标表示其性状，即
，
于是，得到原始数据矩阵为
。
其中表示第个分类对象的第个指标的原始数据。
（2） 数据标准化
在实际问题中，不同的数据一般有不同的量纲，为了使不同的量纲也能进行比较，通常需要对数据做适当的变换。但是，即使这样，得到的数据也不一定在区间上。因此，这里说的数据标准化，就是要根据模糊矩阵的要求，将数据压缩到区间上。通常有以下几种变换：① 平移·标准差变换

其中 ， 。
经过变换后，每个变量的均值为0，标准差为1，且消除了量纲的影响。但是，再用得到的还不一定在区间上。
② 平移·极差变换
，
显然有，而且也消除了量纲的影响。
③ 对数变换

取对数以缩小变量间的数量级。
第二步：标定（建立模糊相似矩阵）
设论域，，依照传统聚类方法确定相似系数，建立模糊相似矩阵，与的相似程度。确定的方法主要借用传统聚类的相似系数法、距离法以及其他方法。具体用什么方法，可根据问题的性质，选取下列公式之一计算。
（1） 相似系数法
① 夹角余弦法 。
② 最大最小法 。
③ 算术平均最小法 。
④ 几何平均最小法 。
以上3种方法中要求，否则也要做适当变换。
⑤ 数量积法 ，
其中 。
⑥ 相关系数法 ，
其中 ，。
⑦ 指数相似系数法 ，
其中 ，
而 。
（2） 距离法
① 直接距离法 ，
其中为适当选取的参数，使得，表示他们之间的距离。经常用的距离有
● 海明距离 。
● 欧几里得距离 。
● 切比雪夫距离 。
② 倒数距离法 。
其中为适当选取的参数，使得。
③ 指数距离法 。
3、第三步：聚类（求动态聚类图）
（1）基于模糊等价矩阵聚类方法
① 传递闭包法
根据标定所得的模糊矩阵还要将其改造称模糊等价矩阵。用二次方法求的传递闭包，即=。再让由大变小，就可形成动态聚类图。
② 布尔矩阵法[10]
布尔矩阵法的理论依据是下面的定理：
定理2.2.1 设是上的一个相似的布尔矩阵，则具有传递性（当是等价布尔矩阵时）矩阵在任一排列下的矩阵都没有形如的特殊子矩阵。
布尔矩阵法的具体步骤如下：
① 求模糊相似矩阵的截矩阵.
② 若按定理2.2.1判定为等价的，则由可得在水平上的分类，若判定为不等价，则在某一排列下有上述形式的特殊子矩阵，此时只要将其中特殊子矩阵的0一律改成1直到不再产生上述形式的子矩阵即可。如此得到的为等价矩阵。因此，由可得水平上的分类
（2） 直接聚类法
所谓直接聚类法，是指在建立模糊相似矩阵之后，不去求传递闭包，也不用布尔矩阵法，而是直接从模糊相似矩阵出发求得聚类图。其步骤如下：
① 取（最大值），对每个作相似类，且
=，
即将满足的与放在一类，构成相似类。相似类与等价类的不同之处是，不同的相似类可能有公共元素，即可出现
,,.
此时只要将有公共元素的相似类合并，即可得水平上的等价分类。
② 取为次大值，从中直接找出相似度为的元素对（即），将对应于的等价分类中所在的类与所在的类合并，将所有的这些情况合并后，即得到对应于的等价分类。
③ 取为第三大值，从中直接找出相似度为的元素对（即），将对应于的等价分类中所在的类与所在的类合并，将所有的这些情况合并后，即得到对应于的等价分类。
④ 以此类推，直到合并到成为一类为止。
最佳阈值的确定
在模糊聚类分析中对于各个不同的，可得到不同的分类，许多实际问题需要选择某个阈值，确定样本的一个具体分类，这就提出了如何确定阈值的问题。一般有以下两个方法：
① 按实际需要，在动态聚类图中，调整的值以得到适当的分类，而不需要事先准确地估计好样本应分成几类。当然，也可由具有丰富经验的专家结合专业知识确定阈值，从而得出在水平上的等价分类
② 用F统计量确定最佳值。[11]
设论域为样本空间（样本总数为），而每个样本有个特征：，。于是得到原始数据矩阵，如下表所示，其中，称为总体样本的中心向量。
样
本
指 标
1 2 k m

设对应于值的分类数为，第类的样本数为，第类的样本记为：
，第类的聚类中心为向量，其中为第个特征的平均值，即
，，
作统计量
，
其中
为与间的距离，为第类中第个样本与其中心间的距离。称为统计量，它是遵从自由度为，的分布。它的分子表征类与类之间的距离，分母表征类内样本间的距离。因此，值越大，说明类与类之间的距离越大;类与类间的差异越大，分类就越好。
主成分分析
主成分分析的原理：主成分分析是设法将原来众多具有一定相关性（比如P个指标），重新组合成一组新的互相无关的综合指标来代替原来的指标。 通常数学上的处理就是将原来P个指标作线性组合，作为新的综合指标。最经典的做法就是用F1 （选取的第一个线性组合，即第一个综合指标）的方差来表达，即Var(F1)越大，表示F1 包含的信息越多。因此在所有的线性组合中选取的 F1 应该是方差最大的，故称 F1为第一主成分。如果第一主成分不足以代表原来 P 个指标的信息，再考虑选取F2 即选第二个线性组合，为了有效地反映原来信息，F1 已有的信息就不需要再出现在 F2 中，用数学语言表达就是要求 Cov(F1, F2)=0，则称 F2 为第二主成分，依此类推可以构造出第三、第四，……，第P个主成分。
主成分模型：

满足以下条件：
（1）每个主成分系数平方和为1即：
（2）主成分之间互不相关 即：
主成分方差依次递减，即
主成分分析计算步骤
① 计算相关系数矩阵 （1）
在（1）式中，rij（i，j=1，2，…，p）为原变量的xi与xj之间的相关系数，其计算公式为
（2）
因为R是实对称矩阵（即rij=rji），所以只需计算上三角元素或下三角元素即可。
② 计算特征值与特征向量
首先解特征方程，通常用雅可比法（Jacobi）求出特征值，并使其按大小顺序排列，即；然后分别求出对应于特征值的特征向量。这里要求=1，即，其中表示向量的第j个分量。
③ 计算主成分贡献率及累计贡献率
主成分的贡献率为： 累计贡献率为：
一般取累计贡献率达85—95%的特征值所对应的第一、第二，…，第m（m≤p）个主成分。
④ 计算主成分载荷
其计算公式为 （3）
得到各主成分的载荷以后，还可以按照（1）式进一步计算，得到各主成分的得分
（4）
数学建模中的数据处理
数学建模是利用数学方法解决实际问题的一种实践。 即通过抽象、简化、假设、引进变量等处理过程后，将实际问题用数学方式表达，建立起数学模型，进而对其进行求解、模 拟、分析检验的过程。它大致可以分为模型准备、模型假设、模型构成、模型求解、模型分析、模型检验及应用等步骤。在这一系列过程中需要对大量的数据进行分析、处理和加工。 在这个过程中不仅要有正确的方法，还要掌握一定的计算工具，才能更有效的处理好。
在数学建模中如何更高效的处理数据是提高数学建模效率的一个非常重要的手段。本文针对数学建模中所需要处理的数据的特点，给出在数学建模过程中数据处理的方法及其所采用的工具。 如果要览已有的分析工具，可以单击“工具”菜单中的“数据分析”命令。如果“数据分析”命令没有出现在“工具”菜 单上，则必须运行“安装”程序来加载“分析工具库”。安装完毕之后，必须通过“工具”菜单中的“加载宏”命令，在“加载宏”对话框中选择并启动它。统计工具可生成以下统计指标，按从上到下的顺序其中包括样本的平均值，标准误差，组中值，众数,样本标准差，样本方差,峰度值，偏度值，极差,最小值，最大值，样本总和，样本个数，和一定显著水平下总体均值的置信区间。从以上可以得知：采用Excel的数据分析功能，可以非常方便的得到数据的数字特征，建模者不需要掌握复杂的编程工具就能解决。
在数学建模过程中，经常需要得到一条光滑的数据曲线或直线，实际上只给出一些分散的数据点，因而在许多情况下，需要利用这些不连续的点，运用最小二乘法等算法，利用 多项式或其它的已知函数生成一个新的多项式或已知函数来对已知的数据点进行逼近，这种方法就是曲线的拟合。最常用曲线拟合是多项式曲线拟合。在数学建模中经常遇到在已知区间（a,b）上求已知函数的积分时，理论上可以用Newton - Lipnize公式求解。但在实际应用中，经常接触到的许多函数都找不到其积分函数，或者函数形式非常复杂，在Newton-Lipnize 求解时也非常复杂，有时甚至根本计算不出来。 这时就需要用数值积分进行求解。同样的有时我们也无法求出函数的微分的表达式，这时要求函数在某一点处的微分只能求数值微分。数值插值可以分为：一维插值、二维插值与三维插值。 数学建模中数值插值是一种常见的数据的处理方法。 采用工具：Matlab 中的函数：interp1（一维插值）、interp2（二维插值）、interp3（三维插值），在数学建模过程中，模型检验是建模的一个非常重要的步骤，模型检验时常常需要对模型的解进行模拟，与实际的数据进行对比。数据模拟是实现模型检验的一个非常重要的方法手段。
数学建模中的分析步骤
—般说来数学建模中的分析大体上可分为两大类、一类是机理分析方法，一类是测试分析方法．
机理分析是根据对现实对象特性的认识、 分析其因果关系， 找出反映内部机理的规律,建立的模型常有明确的物理或现实意义.测试分折将研究对象视为一个“黑箱”系统，内部机理无法直接寻求，可以测量系统的输人输出数据、并以此为基础运用统计分析方法，按照事先确定的准则在某一类模型中选出一个与数据拟合得最好的模型。这种方法称为系统辨识(System Identification)．将这两种方法结合起来也是常用的建模方法。即用机理分析建立模型的结构，用系统辨识确定模型的参数．可以看出，用上面的哪一类方法建模主要是根据我们对研究对象的了解程度和建模目的决定的．如果掌握了机理方面的一定知识，模型也要求具有反映内部特性的物理意义。那么应该以机理分析方法为主．当然,若需要模型参数的具体数值，还可以用系统辨识或其他统计方法得到．如果对象的内部机理基本上没掌握，模型也不用于分析内部特性,譬如仅用来做输出预报，则可以系统辩识方法为主． 系统辨识是一门专门学科，需要一定的控制理论和随机过程方面的知识．
建模要经过哪些步骤并没有一定的模式，通常与实际问题的性质、建模的目的等有关。
对模型解答进行数学上的分析，有时要根据问题的性质分析变量间的依赖关系或稳定状况，有时是根据所得结果给出数学上的预报，有时则可能要给出数学上的最优决策或控制，不论哪种情况还常常需要进行误差分析、模型对数据的稳定性或灵敏性分析等．