题型划分、常用算法及其适用场景

常见赛题类型

• 优化类
• 机理分析类
• 评价类
• 预测类

算法体系分类

• 数据处理模型
• 优化模型
• 预测模型
• 评价模型
• 聚类分析模型

常用算法分类

数据预处理模型及应用场景

1.插值拟合
主要用于对数据的补全处理;
其中样本点较少时（泛指样本点小于30个）采用插值方法，主要有拉格朗日插值算法、牛顿插值、双线性内插和双三次插值
当样本点较多时（泛指样本点大于30个）则采用拟合函数

2.小波分析，聚类分析（高斯混合聚类，K-均值聚类等等)

主要用于分析诊断数据异常值并进行剔除;
小波分析:适用于时域范围的大样本异常值监测
聚类分析:适用于空间分布的大样本/小样本异常值监测

3.主成分分析、线性判别分析、局部保留投影等
主要用于多维数据的降维处理，减少数据冗余等

4.均值、方差分析、协方差分析等统计方法

主要用于数据的截取或者特征选择等

优化类模型及应用场景

优化问题的三要素：

1. 决策变量
2. 目标函数
3. 约束

优化类模型：

1.单目标优化:

所评测目标只有一个，只需要根据具体的满足函数条件求得最值

适用场景:针对问题所建立的优化目标函数有且仅有一个。

2.多目标优化:

多个评测函数的存在，而且使用不同的评测函数的解，也是不同的。也即是说:多目标优化问题中，同时存在多个最大化或是最小化的目标函数，并且，这些目标函数并不是相互独立的，也不是相互和谐融洽的，他们之间会存在或多或少的冲突，使得不能同时满足所有的目标函数。

适用场景:基于问题所构建的优化目标函数不唯一，常出现在金融投资领域，往往要求风险更小，收益更大;

3.线性规划

该问题是要最小化或最大化一个受限于一组有限的线性约束的线性函数
适用场景:所建立的目标函数和约束条件均为线性函数

4.非线性规划

如果目标函数或者约束条件中至少有一个是非线性函数时，最 优化问题叫做非线性规划问题
适用场景:所建立的目标函数或约束条件存在非线性函数

5.整数规划

6.二次规划

7.动态规划

基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这 些子问题的解得到原问题的解。
（1）背包问题：对于背包的类型，这边就做个简单的描述：n个物品要放 到一个背包里，背包有个总容量m，每个物品都有一个体积w[i]和价值v[i]， 问如何装这些物品,使得背包里放的物品价值最大。
（2）运输问题：给定m个资源，分配给n个部门，第i个部门获得j个资源 有个盈利值，问如何分配这m个资源能使获得的盈利最大，求最大盈利。
（3）分割问题：给定一个具有n（n<50）个顶点（从1到n编号）的凸多边 形，每个顶点的权均已知。问如何把这个凸多边形划分成n-2个互不相交
的三角形，使得这些三角形顶点 的权的乘积之和最小？

即：有限的资源进行分配达到最优效果

8.图论模型

(1)最短路模型：主要包括Dijkstra算法和Floyd算法两种，用于求解 两点间的最短距离
适用场景：路径规划问题，如修建道路、设定救援路线等

顶端数量多采用Dijkstra

(2)最大流模型：通常可以把这些边想象成道路，流量就是这条道 路的车流量，容量就是道路可承受的最大的车流量
适用场景：企业生产运输问题、交通拥堵优化问题等

(3)最小生成树：图的生成树是它的一颗含有其所有顶点的无环连通子图,一 幅加权图的最小生成树(MST)是它的一颗权值(树中的所有边的权值之和) 最小的生成树
适用场景：道路规划、通讯网络规划、管道铺设、电线布设等

(4)排队论模型：排队论也称随机服务系统理论。它涉及的是建立一些数学模 型，以对随机发生的需求提供服务的系统预测其行为；排队论主要是对服 务系统建立数学模型，研究诸如单位时间内服务系统能够服务的顾客的平 均数、顾客平均的排队时间、排队顾客的平均数等数量规律。
适用场景：商店购货、轮船进港、病人就诊、机器等待修理等等

聚类模型及应用场景

(1)K-means聚类：针对每个点，计算这个点距离所有中心点最近的那个中心点， 然后将这个点归为这个中心点代表的簇。一次迭代结束之后，针对每个簇类， 重新计算中心点，然后针对每个点，重新寻找距离自己最近的中心点。如此循 环，直到前后两次迭代的簇类没有变化。
适用场景：与地理位置有关的分类情形，如地物类别划分、村落划区、语言分 布位置划分等
(2)层次（系统）聚类：层次聚类也称系统聚类法，是根据个体间距离将个体 向上两两聚合，再将聚合的小群体两两聚合一直到聚为一个整体。计算所有个 体之间的距离，最相近距离的个体合体，不断合体。
适用场景：通常用于行政区域的划分或分级处理等，如根据城市经济指标划分
城市发展等级、根据各类综合指标进行文明城市建设评选等

(3)模糊聚类

• 基于模糊关系的分类法：其中包括谱系聚类算法(又称系统聚类法)、基于等价 关系的聚类算法、基于相似关系的聚类算法和图论聚类算法等等。它是研究比较早 的一种方法，它不能适用于大数据量的情况，所以在实际中的应用并不广泛。
• 基于目标函数的模糊聚类算法：该方法把聚类分析归结成一个带约束的非线性 规划问题，通过优化求解获得数据集的最优模糊划分和聚类。该方法设计简单、解 决问题的范围广，还可以转化为优化问题而借助经典数学的非线性规划理论求解， 并易于计算机实现。
• 基于神经网络的模糊聚类算法：它是兴起比较晚的一种算法，主要是采用竞争
学习算法来指导网络的聚类过程。

(4)神经网络分类：常用的分类模型为BP神经网络模型，指通过多层神经元系统建立 输入与输出间的非线性映射关系
适用场景：适合样本数量较多时的分类问题，常被用于图像地物类别划分。

评价模型及应用场景

① 模糊综合评判：是一种基于模糊数学的综合评价方法。该综合评价法 根据模糊数学的隶属度理论把定性评价转化为定量评价，即用模糊数学 对受到多种因素制约的事物或对象做出一个总体的评价。它具有结果清 晰，系统性强的特点，能较好地解决模糊的、难以量化的问题，适合各 种非确定性问题的解决
适用场景：无具体的评价标准，通过统计问卷等形式进行的评价问题

② 层次分析法：是指将与决策总是有关的元素分解成目标、准则、方案 等层次，在此基础之上进行定性和定量分析的决策方法
适用场景：比较适合于具有分层交错评价指标的目标系统，而且目标值
又难于定量描述的决策问题，但常用于计算指标的权重

④ 数据包络(DEA)分析法：它是根据多项投入指标和多项产出指标，利用线性规划的方法，对具有可比性的同类型单位进行相对有效性评价的一种数量分析方法
适用场景：该方法一般用于评价生产效率或者综合竞争力水平等

⑤ Topsis综合评价法：TOPSIS法根据有限个评价对象与理想化目标的接近程度进 行排序的方法，是在现有的对象中进行相对优劣的评价。TOPSIS法是一种逼近 于理想解的排序法，该方法只要求各效用函数具有单调递增（或递减）性就行。 TOPSIS法是多目标决策分析中一种常用的有效方法，又称为优劣解距离法。
适用场景：尝试用于大体系的综合评价，要求有理想化指标数据，如环境质量评价、医疗质量综合评价、国家综合实力评价等

⑥ 神经网络评价：与前面介绍的分类较为类似，事先将各项输入样本数据与其对 应的输出评价结果建立非线性映射关系，然后对未知样本进行类别划分即可。
适用场景：同样适用于大样本的综合评价，不要求指标具有理想化情形

预测类模型及应用场景

1.灰色预测模型：是通过少量的、不完全的信息，建立数学模型并做出预 测的一种预测方法。是处理小样本（4个就可以，十到二十以内）预测问题的有效工具， 而对于小样本预测问题回归和神经网络的效果都不太理想
适用条件：适用于小样本情况下的发展预测问题

2.微分方程预测：无法直接找到原始数据之间的关系，但可以找到原始数据 变化速度之间的关系，通过公式推导转化为原始数据之间的关系。微分方 程建模是数学建模的重要方法，因为许多实际问题的数学描述将导致求解 微分方程的定解问题。把形形色色的实际问题化成微分方程的定解问题

常用到的模型有：传染病模型、理想火箭模型、人口模型（Malthus模型 和Logistic模型）
适用场景：常用于疾病的传播预测、人口数量或城市发展水平预测等

3.回归分析预测：是在分析自变量和因变量之间相关关系的基础上，建立 变量之间的回归方程，并将回归方程作为预测模型
适用场景：样本数量较少，自变量与因变量间的变化具有明显的逻辑关系

4.马尔科夫预测：对事件的全面预测，不仅要能够指出事件发生的各种可 能结果，而且还必须给出每一种结果出现的概率，说明被预测的事件在预 测期内出现每一种结果的可能性程度。这就是关于事件发生的概率预测。 马尔可夫（Markov)预测法，就是一种关于事件发生的概率预测方法。它 是根据事件的目前状况来预测其将来各个时刻（或时期)变动状况的一种 预测方法。马尔可夫预测法是地理预测研究中重要的预测方法之一。
适用场景：主要用于市场占有率的预测和销售期望利润的预测以及其他商
业领域的预测等

5.时间序列预测（必须掌握）

• 时间序列是按时间顺序排列的、随时间变化且相互关联的数据序列。分析时间序 列的方法构 成数据分析的一个重要领域，即时间序列分析。
• 时间序列预测法是一种定量分析方法，它是在时间序列变量分析的基础上，运用一定的数学 方法建立预测模型，使时间趋势向外延伸，从而预测未来市场的发展变化趋势，确定变量预 测值
常用到的模型：移动平均法、指数平滑法、差分指数平滑法、平稳时间序列模型 ：自回归 AR 、移动平均 MA 、ARMA 模型等
适用场景：常用在国民经济市场潜量预测、气象预报、水文预报、地震前兆预报、农作物病 虫灾害预报、环境污染控制、生态平衡、天文学和海洋学等方面。
6.神经网络预测：大部分时间序列预测方法均假设各变量之间是一种线性关系，这种局限性 使其在实际应用过程中很难准确地进行分析和预测，而神经网络作为一种非线性模型被用来 研究预测问题效果会更好。
常使用的方法：利用前i年的数据预测第i+1年的数据
适用场景：同样适用于大样本的预测问题