当前位置： 首页 > news >正文

建设通招标网站营销公关名词解释

news 2026/4/26 19:02:42
建设通招标网站,营销公关名词解释,上海网页设计公司选择兴田德润,电脑网址打不开网页怎么办数学建模常见算法总结 评价决策类模型 层次分析法 层次分析法根据问题的性质和要达到的总目的#xff0c;将问题分解为不同的组成因素#xff0c;并按照因素间的相互关联影响以及隶属关系将因素按不同层次聚集组合#xff0c;形成一个多层次的分析结构模型#xff0c;从…数学建模常见算法总结 评价决策类模型 层次分析法 层次分析法根据问题的性质和要达到的总目的将问题分解为不同的组成因素并按照因素间的相互关联影响以及隶属关系将因素按不同层次聚集组合形成一个多层次的分析结构模型从而最终模型使问题归结为最低层供决策的方案、措施等相对于最高层总目标的相对重要权值的确定或相对优劣次序的排定 层次分析法建模步骤 建立递阶层次结构模型 构造出各层次中的所有判断矩阵 一致性检验 求权重后进行评价 建立层次结构模型 将决策的目标、考虑的因素决策准则和决策方案按它们之间的相互关系分为最高层中间层和最低层给出层次结构图 最高层 决策的目的、要解决的问题一个要素目标层 中间层 考虑的因素、决策的准则若干个层次、准则层 最低层 决策时的备选方案措施层、方案层 对于相邻的两层 称高层为目标层低层为因素层 构造判断矩阵 确定各层次之间的权重从层次结构模型的第2层开始对于从属于或影响上上一层每个因素的同一层诸因素构造判断矩阵直达最下层一致矩阵法 不把所有因素放在一起比较而是两两相互比较 对此时采用相对尺度以尽可能减少性质不同的诸因素相互比较的困难以提高准确度 对指标的重要性进行两两比较构造判断矩阵进而定出权重 矩阵元素 a i j a_{ij} aij​的意义是第 i i i个指标相对于第 j j j个指标的重要程度[专家经验/领域知识] 标度含义1同等重要3稍微重要5明显重要7强烈重要9极端重要 第一步 指标量化指标进行数学化 第二步 指标标准化一种方法是让总和为1 第三步 判断矩阵法确定权重 一致性检验 因为两两比较的过程中忽略了其他因素导致最后的结果可能会出现矛盾所以需要一致性检验 理想化的情况是一致性矩阵 a i j ⋅ a j i 1 a_{ij} \cdot a_{ji}1 aij​⋅aji​1 a i k ⋅ a k j a i j a_{ik} \cdot a_{kj}a_{ij} aik​⋅akj​aij​ 由于人的心理因素严格的一致矩阵几乎不可能的因此应当检验我们构造的判断矩阵和一致性矩阵是否有太大差别在使用判断矩阵求权重之前必须对其进行一致性检验只有靠谱的矩阵才能使用 一致性检验的步骤 计算一致性指标 C I λ max − n n − 1 CI \frac{\lambda_{\text{max}} - n}{n - 1} CIn−1λmax​−n​ 注 其中特征值可用数学软件计算若有虚数特征值则取模的最大值 查表获得对应的平均随机一致性指标 R I RI RI 计算一致性比例 C R C I R I CRCIRI CRCIRI ​ 若 C R 0 CR0 CR0则为一致矩阵 ​ 若 C R 0.1 CR0.1 CR0.1,判断矩阵一致能用 ​ 若 C R ≥ 0.1 CR \geq 0.1 CR≥0.1判断举止不一致用不了 n1234567891011 R I RI RI000.580.91.121.241.321.411.451.491.51 计算权重 方法一 算数平均法 按列归一化再求平均值 方法二 几何平均法 求每行的几何平均数再归一化 方法三 特征值法 求矩阵最大特征值对应的特征向量再归一化 TOPOSIS方法 图片内的内容如下 TOPSISTechnique for Order Preference by Similarity to an Ideal Solution可翻译为通过理想解排序法。国内常简称为优选评分法能充分利用原始数据的信息其结果既能客观地反映各评价方案之间的差距。 TOPSIS法引入了两个基本概念 理想解设想的最优的解它的各个属性值达到各备选方案中的最好值负理想解设想的最劣的解它的各个属性值达到各备选方案中的最坏值。 方案择优的原则是将各备选方案与理想解和负理想解做比较若其中有一个方案接近理想解而同时又远离负理想解则该方案是诸多方案中最好的方案。TOPSIS通过极大理想解和极小负理想解来完成优选排序。 建模步骤 数据正向化处理转为极大型指标体系 数据标准化处理归一化 权重确定AHP、熵权法、默认等比权重 距离计算 ​ 确定最优解和最劣解经过了正向化处理和标准化处理的评分矩阵Z里面的数据全部是极大型数据取出每一列中的最大的数构成理想最优解向量 ​ 距离计算评分 TOPSIS法是一种理想目标相似性排序法通过归一化后的数据找出多个目标中最优目标和最劣目标计算各评价目标与理想解和负理想解的距离获得各目标与理想解的贴近度作为评价目标优劣的依据。 贴近度取值在01之间该值越接近1表示相应的评价目标越接近最优水平反之数值越接近0表示评价目标越接近最劣水平。 指标类型特点转化方法极大型指标越大越好最小值为0最大值为1其余值极小型指标越小越好最小值为1最大值为0其余值中间型指标越接近某个值越好距离最优值为1差距最大为0其余值区间型指标位于某个区间内最为好区间内为1差距最大为0其余值 指标统一之后还需要归一化以消除量纲的影响就这样倒也可以但也可以用我们之前用过的方法让每列的和为1或者让每列向量的平方和为1 最后还需要再确定权重进行评价此时可以代入层次分析法继续处理。 熵权法 前面说到的指标都带有强烈的主观性有没有客观的、根据数据本身的性质得到权重的方法呢 看指标的离散程度如果某个指标都很接近则没有太多意义权重应减小 如果某个指标差距很大则更好区分权重应增大 如何表示大家在某个指标上的差距呢一个思路是用方差确定权重 按照信息论的基本原理的解释信息是系统有序程度的一个度量熵是系统无序程度的一个度量。 根据信息熵的定义对于某项指标可以用熵值来判断某个指标的离散程度若信息熵值越小指标的离散程度越大该指标对综合评价的影响就越大如果某项指标的值全部相等则该指标在综合评价中不起作用。 因此可利用信息熵这个工具计算出各个指标的权重为多指标综合评价提供依据。 熵权法是一种客观赋权方法它可以避免数据本身得出权重。 原理指标的变异程度越小所反映的信息量也越少熵对应的权值也应该越低。 步骤 数据归一化每列的和应该是1而不是平方和是1得到样本所占比重 p i j p_{ij} pij​ 利用信息熵公式求出熵值 e j − 1 ln ⁡ n ∑ p i j ⋅ ln ⁡ p i j e_j -\frac{1}{\ln n} \sum p_{ij} \cdot \ln p_{ij} ej​−lnn1​∑pij​⋅lnpij​ 信息效用值 d j 1 − e j d_j1-e_j dj​1−ej​ 对信息效用值归一化求出熵权 模糊综合评价法 模糊综合评价法是一种基于模糊数学的综合评价方法 根据模糊数学的隶属度理论它定性评价转化为定量评价用模糊数学对受到多种因素制约的事物或对象作出一个总体的评价 它具有自我解释、系统性强的特点能较好地解决模糊的、难以量化的问题适合各种非确定性问题的解决 一个元素是否属于一个模糊集是用隶属函数$ \mu_A $刻画的 $ (0 \leq \mu_A \leq 1) $ $ \mu_A 0 $ 表示确定不属于 $ \mu_A 1 $ 表示确定属于 $ \mu_A 0.5 $ 时隶属度最强 对于每个因素而言需确定各自的隶属函数 方法一 模糊统计法。找许多人调查一下竞赛中没法用 方法二 借助已有的客观尺度。如果领域知识已有相关指标就直接用。但是注意要归一化到[0,1]区间归一化可借用TOPOSIS法 方法三 指派法。凭主观意愿指派一个隶属度函数没有办法的办法需要能自圆其说 例如 假设微博粉丝数最多1.2亿则隶属度函数 μ ( x ) x 1.2 亿 \mu(x)\frac{x}{1.2亿} μ(x)1.2亿x​ 颜值直接人工打分 作品质量按10分最优为了把高分段拉开用二次函数来拟合 μ ( x ) x 2 / 100 \mu(x)x^2/100 μ(x)x2/100 作品数量达到40部就已经可以了隶属度函数 μ ( x ) m i n ( 1 , x / 40 ) \mu(x)min(1,x/40) μ(x)min(1,x/40) 得到隶属度之后确定权重就可以了 权重可以使用前面讲过的熵权法、方差法或判断矩阵法 各种方法的结果有差异需要选手对结果进行详细分析 事实上各种方法都可以进行多层次的分析 只需将每一层进一步展开逐步进行评价即可甚至可以每层采用不同的评价方法 注意不要为了内容花哨而刻意选择不同方法而要充分说明为什么选择某一种方法这种方法的权重是怎么得出来的权重的大小反映了什么实际意义如何从数据和结构得到体现的如果有educated guess有一句的猜测的话敏感度如何… 数学规划类模型 问题定义 数学规划 求目标函数在一定约束条件下的极值问题 在给定条件约束条件如何按照某一衡量指标目标函数来寻求计划、管理工作中的优方案 m i n / m a x Z f ( x ) min/max Zf(x) min/maxZf(x) g i ( x ) g_i(x) gi​(x)约束条件不等式约束、等式约束、整数约束 方法使用条件线性规划目标函数和约束条件均为是决策变量的线性表达式 f(x)axb非线性规划当目标函数或者约束条件中有一个是决策变量的非线性表达式或者不等式约束时0-1整数规划要求变量取整数值的整数规划整数变量的取值只能为0和1。动态规划基本思想是将待求问题区间分解为若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。适用场景优化问题背包问题、生产调度问题、分割问题、最短路径、最大公约子序列等 线性规划 线性规划Linear programming是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支是辅助人们进行科学管理的一种数学方法是研究线性约束条件下线性目标函数的极值问题的数学理论和方法 线性规划模型三要素 决策变量 问题中要确定的未知量用于表明规划问题中的用数量表示的方案、措施等可由决策者决定和控制 目标函数 决策变量的函数优化目标通常是求该函数的最大值或最小值 约束函数 决策变量的取值所受到的约束和限制条件通常用含决策变量的等式或不等式表示 多目标规划问题 最优解 所有目标同时达到最优任何其他解的所有目标都不好于它一般不存在 有效解 不存在另一个解所有目标都不比它差且至少一个目标好于它 满意解 对于每个目标给出阈值所有目标同时达到即可接受 多目标规划常见的目标函数设定方法 线性加权法 对各个目标线性加权得到一个综合指标权值的确定比较tricky ϵ \epsilon ϵ约束法 设定一个首要目标其他目标作为约束条件 理想点法 对每个目标设置理想值使各目标差距的平方和最小 优先级法 首先优化一个首要目标打平时再考虑次要目标 非线性规划 非线性规划的一般形式 $$ \begin{align} \min \ f(x) \ \text{s.t.} \quad \begin{cases} Ax \leq b, \quad A_{eq} \cdot x b_{eq} \text{(线性)} \ c(x) \leq 0, \quad C_{eq}(x) 0 \text{(非线性)} \ lb \leq x \leq ub \end{cases} \end{align} $$ 蒙特卡洛模拟 如果想不到什么更好的方法就直接随机大量生成向量 [ x 1 , x 2 , x 3 , x 4 ] [x_1,x_2,x_3,x_4] [x1​,x2​,x3​,x4​]然后观察解的分布 这种方法叫做蒙特卡洛模拟 0-1与整数规划 考虑这样一个问题现有 N N N种物品已知每种物品的重量 w i w_i wi​和价值 p i p_i pi​在总重量不超过 W W W的前提下选择若干物品使总价值 P P P最大。 如果每种物品只有一个如何选择如果每种物品有无穷多个如何选择 上述规划问题可写成求解 max ⁡ P ∑ p i x i \max P \sum p_i x_i maxP∑pi​xi​$s.t. ∑ w i x i ≤ W \sum w_i x_i \leq W ∑wi​xi​≤W$ x i ≥ 0 x_i \geq 0 xi​≥0 这个问题看似线性规划但要求解 x i x_i xi​的取值只能是整数甚至只能是0-1。 没有办法的方法当成线性规划求解得出的值假如是小数再进行微调。 另外的办法用0-1整数规划的方法求解。 动态规划 动态规划是运筹学的一个分支通常用来解决多阶段决策过程中最优化问题基本想法就是将原问题转换为一系列相互联系的子问题然后通过逐层地求解最终得到最优解。 动态规划理论的前提必须符合下列两个条件 最优子结构无法通过去的状态和决策如何对前面决策所形成的当前状态而言余下的诸决策必须独立成完整的最优策略子问题的最优解就是导致这个问题的全局最优。 无后效性某阶段的状态一旦确定则此后过程的演变实不会受到此前各状态及决策的影响。即未来与过去无关。 动态规划的组成部分 确定状态 通常用 f [ x , y , . . . ] f[x,y,...] f[x,y,...]表示当前最优解 状态转移方程 写出 f [ x , y , . . . ] f[x,y,...] f[x,y,...]与 f [ x − 1 , y , . . . ] f[x-1,y,...] f[x−1,y,...]之类的关系 初始或边界条件 写出 f [ 0 , 0 , . . . ] f[0,0,...] f[0,0,...]之类的取值 计算顺序 可能逆序推或顺推 对于背包问题记$ f(x) 表示只考虑前 表示只考虑前 表示只考虑前x 件物品在总重量不超过 件物品在总重量不超过 件物品在总重量不超过W$情况下的最优价值。 在0-1背包问题中若已经求出了考虑前1- x x x件物品的情况则在考虑第 x x x件物品时可以选择它或者不选择它取这两种情况下的值较大者。状态转移方程为 f ( l , x ) max ⁡ [ f ( l − 1 , x − w [ l ] ) p [ l ] , f ( l − 1 , x ) ] f(l,x) \max[f(l-1,x-w[l]) p[l], f(l-1,x)] f(l,x)max[f(l−1,x−w[l])p[l],f(l−1,x)] 边界条件为$ f(0,x) 0, f(i,0) 0, 0 \leq x \leq n $。即重量为0时价值一定为0考虑0件物品时价值也为0。 计算顺序为从1到 n n n, 从1到 W W W, 最后输出 f ( n , W ) f(n,W) f(n,W)结果即可。 在完全背包问题中只需做一个调整在考虑第 i i i件物品时可以选择它的次数为 0 − W / w [ i ] 0-W/w[i] 0−W/w[i]且所有背包的价值取这些值的最大值。状态转移方程为 f ( l , x ) max ⁡ [ f ( l − 1 , x − k ⋅ w [ i ] ) k ⋅ p [ i ] ] ( 0 ≤ k ≤ W / w [ i ] ) f(l,x) \max[f(l-1,x - k \cdot w[i]) k \cdot p[i]] \quad (0 \leq k \leq W/w[i]) f(l,x)max[f(l−1,x−k⋅w[i])k⋅p[i]](0≤k≤W/w[i]) 启发式算法 什么是启发式算法人在解决问题时所采取的一种根据经验规则进行发现的方法。 模拟退火SA 模拟退火SA的思想借鉴于固体的退火原理当固体的温度很高的时候内能比较大固体的内部粒子处于快速无序运动当温度慢慢降低的过程中固体的内能减小粒子慢慢趋于有序最终当固体处于常温时内能达到最小此时粒子最为稳定。 思想 为了不被局部最优解困住需要以一定概率跳出当前位置暂时接受一个不太好的解。在搜索最优解的过程中逐渐降温初期跳出去的概率比较大进行广泛搜索后期跳出去的概率比较小尽量收敛到较优解。 模拟退火的步骤 模拟退火算法的步骤如下 1初始化温度 T T T(充分大)、温度下限 T m i n T_{min} Tmin​(充分小)、初始解 X X X每个 T T T值迭代次数 L L L 2随机生成临域解 X n e w X_{new} Xnew​; 3设 f ( x ) f(x) f(x)函数来计算用来计算解得好坏计算出 f ( X n e w ) − f ( X ) f(X_{new})- f(X) f(Xnew​)−f(X); 4如果$f(X_{new})-f(X) 0 说明新解比原来的解好则无条件接受如果 0说明新解比原来的解好则无条件接受如果 0说明新解比原来的解好则无条件接受如果f(X_{new})-f(X ) 0 则说明旧解比新解好则以概率 )0则说明旧解比新解好则以概率 )0则说明旧解比新解好则以概率e^{((f(X_{new})-f(X))/k*T)} 接受 接受 接受X_{new}$作为解。 5如果当前温度 T m i n T_{min} Tmin​时则退出循环输出当前结果否则减少当前温度回到第2步继续循环常用的降温方法为 T a ∗ T ( 0 a 1 ) Ta*T(0a1) Ta∗T(0a1)一般取接近1的值。 解空间 解空间就是所有合理解的集合每次生成的解必须合理 旅行商问题的解空间就是1~~n的全排列 初始解 初始解可以随意选取但比较好的初始解可以帮助算法尽快收敛可先随机生成少量几个序列选一个比较小的或者采用贪心算法选择初始解 目标函数 目标函数根据我们要优化的目标确定旅行商问题的目标函数就是路径长度 降温方法 初始温度、降温方法的选择没有固定标准只能试例如初始温度为1每次降温就乘以99%降到10^-30就停止需要根据具体问题的数值能接受的迭代次数等确定 注也不需要每次迭代都降温也可以迭代几次才降一次温 温度和接受概率的关系 根据模拟退火算法如果新解更差了那就以$ e^{\frac{\Delta f(x)}{T}}$的概率接受可见如果温度较高新解变差的程度不大则接受的概率较大 如何生成新的解 新解的生成是最体现创造性的地方可以自己提出如何将当前解变换为新解而且保证新解是合理的并且和旧解的差异不要太大 例如 任意选择两个标号调换位置 任意选择两个标号颠倒它们中间的序列 任意选择三个标号将前两个标号之间的序列放到第三个标号之后 遗传算法CA 遗传算法是一种基于自然选择原理和自然遗传机制的搜索寻优算法它是模拟自然界中的生命进化机制在人工系统中实现特定目标的优化。 突变和基因重组是进化的原因遗传算法是通过群体搜索技术根据适者生存的原则逐代进化最终得到准最优解。 其基本思想是根据问题的目标函数构造一个适应度函数Fitness Function对种群中的每个个体即问题的一个解进行评估计算适应度、选择、交叉和变异通过多轮的繁殖选择逐渐形成好的个体作为问题的最终解。 操作包括初始群体的产生求每一个体的适应度根据适者生存的原则选择优良个体被选出的优良个体两两配对通过随机交叉与某些个体的基因片段随机变异某些染色体的基因生成下一代群体按此方法使群体逐代进化直到满足进化的终止条件。 步骤 产生 M M M个初始解构成初始种群 每对父母以一定概率生成一个新解交配产生后代 每个个体以一定概率发生变异即将自己的解变动变产生新解 父代和子代合在一起留下 M M M个最好的个体进入下一轮其余淘汰进行自然选择 重复以上迭代最后输出最好的个体 如何选择参数 遗传算法中要选择的参数很多种群数量 S S S、变异概率、生成子代的数量、迭代次数 但很遗憾参数的选择没有固定标准只能自己试 种群数量M越大迭代次数越多生成的子代越多当然更有希望找到最优解但相应的计算资源消耗也会增大只能在可接受范围内进行选择 如何选择初始种群 其实可以随便初始化但是较好的初始种群可以帮助更快收敛 例如随机生成若干个选最好的、贪心算法等 如何交配产生子代 交配方法应该尽量继承父代但也要进行足够的调整 例如 选择父亲的一个标号 t t t在母亲那里找到它后面的全部数字并依序取出 把父亲标号 t t t后面的部分接到母亲后面 把母亲取出来的数字接到父亲后面 如何突变产生新的解 突变就是根据自己的解生成一个新的解方法可以和模拟退火中的方法相同 蚁群算法ACO 蚁群算法来自于蚂蚁寻找食物过程中发现路径的行为。蚂蚁并没有视觉却可以寻找食物这得益于蚂蚁分泌的信息素。蚂蚁之间相互独立彼此之间通过信息素进行交流从而实现群体行为。 蚁群算法的基本原理就是蚂蚁觅食的过程。首先蚂蚁在觅食的过程中会在路径上留下信息素pheromone并在寻找食物的过程中感知这种物质的强度并指导自己的行为方向他们总会朝着浓度高的方向前进。 因此可以看得出来蚂蚁觅食的过程是一个正反馈的过程该路段经过的蚂蚁越多信息素留下的就越多浓度越高更多的蚂蚁都会选择这个路段。 步骤 蚁群算法的步骤如下 选择蚂蚁的数量。每个蚂蚁随机选择一个起点初始化所有路线上信息素的浓度相等 每一个蚂蚁从不同点出发依次选择自己的路径 ​ 在每一个节点处根据路径本身信息 η η η和信息素浓度τ选 择下一个节点 ​ 选择每个节点的概率正比于 τ α η β τ^αη^β ταηβ 选择自己的路径后在被选择路径上留下信息素 Δ τ q 路径长 Δτ \frac {q} {路径长} Δτ路径长q​ 每一轮的信息素会以一定比例挥发更新信息素浓度τ p τ 0 Δ τ pτ_0 Δτ pτ0​Δτ 重复以上迭代若干次输出找到最优的解 需要选择哪些参数 蚂蚁的数量一般蚂蚁的数量和顶点数量一样就可以 迭代的次数根据计算资源选择 $ \alpha, \beta $影响路径本身信息和信息素浓度的相对重要性 挥发系数 ( $\rho KaTeX parse error: Cant use function \) in math mode at position 1: \̲)̲、信息素总量 \( Q$ )只能根据具体问题来试 图论算法 基本概念 如果我们能用点表示某事物用点与点之间的线表示事物之间的联系就要可以把这件事物抽象地使用图表示出来。而运用抽象的方式将问题抽象为图并为之建立的数学模型就是图论 图的基本元素 顶点 用点集 V V V表示 V V V v 1 , x 2 , . . . , v n {v_1,x_2,...,v_n} v1​,x2​,...,vn​ 边 用边集 E E E表示 E E E e 1 , e 2 , . . . , e m {e_1,e_2,...,e_m} e1​,e2​,...,em​ 权重 点 i i i到点 j j j的边权记为 w i j w_{ij} wij​ 图 顶点和边的几何 G ( V , E ) G(V,E) G(V,E) 图的基本概念 边如果是单向箭头表示有方向构成有向图构成的图称为有向图 如果没有箭头只要线表示双向构成的图称为无向图比如通信电缆 权重不仅可以表示长度也可以表示时间、费用等概念 边的表示方式 边列表 邻接表 邻接矩阵 最小生成树 最小生成树问题 (Minimum spanning tree problem) 最小生成树问题也是一种常见的图论问题路线路设计、道路规划、电网布置、公交通线、网络设计都可以转化为最小生成树问题。如果要求总线路长度最短、材料最少、成本最低、耗时最少等转换为最短路径问题最小生成树是保证覆盖一个标的图所有的顶点的连通树但不能确保连通两点之间的距离最短。 连通图 在无向图中若任意两个顶点v与j之间有路径相连则称该无向图为连通图。 强连通图 在有向图中若任意两个顶点v与j之间都有路径相连则称该有向图为强连通图。 连通网 一个连通图当每条边都有一定的权值时每一条边都应有一个权称为“网络”权代表连接两点的距离、时间、成本等。 生成树 一个连通图的生成树是指包含该图的所有顶点它含有图中全部n个顶点但只有足以构成一棵树的n-1条边。对于一个n顶点的连通图其生成树有且仅有n-1条边如果生成树含有n-1条边则必定生成一个连通图。 最小生成树 在连通图的所有生成树中所有边的代价和最小的生成树称为“最小生成树”。 针对一个连通图选择n-1条边把n个顶点全部连起来且边长度综合最短 实际问题 要在n个居民点之间架设煤气管道使造价最小 在某个区域内的城市间修建公路以使任意两个城市间能够直接或间接到达 算法1prim算法 适合边多点少的情况图采用邻接矩阵存储 找到目前情况下能连上的权值最小的边的另一端加入之直到所有的顶点加入1 算法2kruskal 适合边少点多的情况图采用边目录方式存储 选目前情况下能连上的权值最小的边若与生成的树不够成环加入之直到n-1条边加入完毕 最短路径问题SPP 最短路径问题 (Shortest path problem) 最短路径问题是图论研究中的一个经典算法问题旨在寻找图由节点和路径组成的中两节点之间的最短路径。根据初始条件的不同可分为五种常见情况最短路径问题 旨在寻找图中两节点之间的最短路径 确定起点的最短路径问题 即已知起点求最短路径的问题 确定终点的最短路径问题 与确定起点的问题相反该问题是已知终点求最短路径的问题。在无向图中该问题与确定起点的问题完全等同在有向图中该问题等同于把所有路径方向反转的确定起点的问题 确定起点终点的最短路径问题 即已知起点和终点求两点之间的最短路径 多目标最短路径问题 求图中任意两点间的最短路径也可以合并为一种情况——全局最短路径问题只要某出全局最短路径那其余四种情况也已经包含在内了。 最短路径Shortest path 想要从一个顶点走到另一个顶点最短的路径是什么 单源最短路 起点是确定的求出这个起点到其他终点的最短路径 多源最短路 求出从所有起点到其他店的最短路径 Dijkstra算法单源最短路径 从起点开始采用贪心算法的策略每次遍历到始点距离最近且未访问的顶点的邻接节点直到扩展到终点为止 Floyd-Warshall多源最短路径 利用动态规划的思想时间复杂度高适合计算多源最短路 a.从任意一条单边路径开始。所有两点之间的距离是边的权如果两点之间没有边相连则权为无穷大 b.对于每一对顶点 u u u和 v v v看看是否存在一个顶点 w w w使得从 u u u到 w w w再到 v v v比已知的路径更短 如果是更新它 最短路径的常用算法 图的规模小则用Floyd。若边的权值有负数需要判断负圈 图的规模大且边的权值非负用Dijkstra 图的规模大且边的权值有负数用SPFA需要判断负圈 结点N、边M边权值适用算法数据结构n200允许有负Floyd邻接矩阵n×m10^7允许有负Bellman-Ford邻接表更大有负SPFA邻接表、前向星更大无负数Dijkstra邻接表、前向星 其他图论算法 关节点割点 如果连通图去掉某个点和与它相连的所有边整个图将变得不连通 桥 如果连通图去掉某条边整个图将变得不连通 连通分量 如果连通图去掉某条边整个图将变得不连通 团 若一些顶点两两都相连则构成一个团 社区 将顶点分成若干组组内边的数量大于组间边的数量 二分图 顶点可分为两组每组顶点内部没有变相连 二分图匹配 在一个二分图内找出一些边使得任何一个图中的点都被至多一条边连接 网络流 顶点之间的边表示最大流量有向求从一个顶点到另一个顶点的最大流量 拓扑排序 每个顶点表示一项任务边表示任务的前后关系给出顶点排序使其不违背给定的前后关系 关键路径 关键路径critical path已知一些活动的持续时间和前后关系求最短完成时间 顶点表示时间边表示活动 从起点到终点最长的一条路称为关键路径上面的活动称为关键活动 关键活动没有拖延余地一旦关键活动拖延总时间一定延后 求解方法 先要拓扑排序 从前到后写出最早时间即所有紧前工作都能完成的最早时间 从后到前写出最晚时间即所有紧后工作都要开始的最晚时间 如果最早最晚则该顶点在关键路径上 回归模型 回归模型问题概述 在统计学中回归分析指的是确定的两种或两种以上变量间相互依赖的定量关系的一种统计分析方法这是一种预测性的建模技术通常用于预测分析以及发现变量之间的因果关系 回归模型正是表示从输入变量到输出变量之间映射的函数回归问题的学习等价于函数拟合选择一条函数曲线使其很好地拟合已知数据且很好地预测未知数据 回归分析的一般步骤 1收集一组包含因变量和自变量的数据 2选定因变量与自变量之间的模型利用数据按照最小二乘准则计算模型的系数 3利用统计分析方法对不同的模型进行比较找出与数据拟合得最好的模型 4判断得到的模型是否适合于这组数据诊断有无不适合回归模型的异常数据 5利用模型对因变量作出预测或解释 按照自变量的多少分为一元回归分析和多元回归分析 按照因变量的多少分为简单回归分析和多重回归分析 按照自变量和因变量之间的相关关系不同分为线性回归分析和非线性回归分析 线性回归 研究内容 研究自变量x和因变量y之间的相关性回归分析只能研究相关性而不能研究因果性 适用数据 连续数值变量 分类 一元线性回归 如果研究的线性函数只包含一个自变量和因变量且二者的关系可以用一条直线刻画时这种回归就是一元线性回归 多元线性回归 如果涉及两个以上的自变量且是线性关系就称为多元线性回归 一元线性回归 一元线性回归模型 y β 0 β 1 x u y \beta_0 \beta_1 x u yβ0​β1​xu u u u称为误差项或随机项该方程表示当 $x x_0$ 时 E ( y ) β 0 β 1 x 0 E(y) \beta_0 \beta_1 x_0 E(y)β0​β1​x0​ β 0 \beta_0 β0​、 β 1 \beta_1 β1​是回归系数 线性回归的目标是找到最优的系数 β 0 \beta_0 β0​, β 1 \beta_1 β1​, β 2 \beta_2 β2​, … \dots …, β p \beta_p βp​,使得模型预测的值与真实值之间的误差最小。 这个误差通常用残差平方和来表示 R S S ∑ ( y i − y i ^ ) 2 RSS \sum (y_i - \hat{y_i})^2 RSS∑(yi​−yi​^​)2 许多非线性方程也可以化为线性方程的形式例如 y a x b → ln ⁡ y ln ⁡ a b ln ⁡ x y a e b x → ln ⁡ y ln ⁡ a b x y a b ln ⁡ x → 以 ln ⁡ x 做自变量 y a − b x → 以 1 x 做自变量 y a e − b x → ln ⁡ y ln ⁡ a − b x y 1 1 e a − b x → ln ⁡ ( 1 y − 1 ) a − b x \begin{aligned} y ax^b \rightarrow \ln y \ln a b \ln x \\ y ae^{bx} \rightarrow \ln y \ln a bx \\ y a b \ln x \rightarrow \text{以} \ln x \text{做自变量} \\ y a - \frac{b}{x} \rightarrow \text{以} \frac{1}{x} \text{做自变量} \\ y ae^{-\frac{b}{x}} \rightarrow \ln y \ln a - \frac{b}{x} \\ y \frac{1}{1 e^{a - bx}} \rightarrow \ln \left(\frac{1}{y} - 1\right) a - bx \end{aligned} yyyyyy​axb→lnylnablnxaebx→lnylnabxablnx→以lnx做自变量a−xb​→以x1​做自变量ae−xb​→lnylna−xb​1ea−bx1​→ln(y1​−1)a−bx​ 最小二乘法 原理 基于最小化误差的平方和来寻找数据的最佳函数匹配用于估计未知参数使得预测值与实际观测值之间的误差平方和最小 应用场景 最小二乘法是解决曲线拟合问题最常用的方法。在已知一组数据点的情况下可以利用最小二乘法求得一条最能代表这些数据的曲线 求解未知量 最小二乘法可以用于求解未知量使得误差值最小。例如在回归分析中可以利用最小二乘法求得回归直线的斜率和截距使得预测值与实际值之间的误差平方和最小 前提条件 最小二乘法成立的前提条件是假设系统中无系统误差误差均为偶然误差并且假设误差符合正态分布即整个系统最后的误差均值为零 计算过程 对于一元线性回归假设有n个数据点( x i , y i x_i,y_i xi​,yi​)其中 i i i从1到 n n n。我们的目标是找到一条直线 y y y a x b axb axb其中 a a a是斜率 b b b是截距。最小二乘法的目标是最小化以下误差平方和 S ∑ i 1 n ( y i − ( a x i b ) ) 2 S \sum_{i1}^{n} \left(y_i - (ax_i b)\right)^2 Si1∑n​(yi​−(axi​b))2 为了找到使 S S S最小的 a a a和 b b b的值我们需要对 S S S求关于 a a a和 b b b的偏导数并令它们等于零。这样可以得到一个线性方程组解这个方程组就可以找到最优的 a a a和 b b b 评判标准 相关系数 r 2 l x y 2 l x x l y y r^2 \frac{l_{xy}^2}{l_{xx} l_{yy}} r2lxx​lyy​lxy2​​越大说明自变量与因变量的关系越强。 总离差平方和 S S T ∑ ( y i − y ˉ ) 2 l y y SST \sum \left(y_i - \bar{y}\right)^2 l_{yy} SST∑(yi​−yˉ​)2lyy​ 回归平方和 S S E ∑ ( y i ^ − y ˉ ) 2 l x y 2 l x x SSE \sum \left(\hat{y_i} - \bar{y}\right)^2 \frac{l_{xy}^2}{l_{xx}} SSE∑(yi​^​−yˉ​)2lxx​lxy2​​ 残差平方和 $ SSR \sum \left(y_i - \hat{y_i}\right)^2 \sum u_i^2$ 可以证明 S S T S S E S S R SST SSE SSR SSTSSESSR 拟合优度 R 2 S S E S S T 1 − S S R S S T R^2 \frac{SSE}{SST} 1 - \frac{SSR}{SST} R2SSTSSE​1−SSTSSR​ 可以理解为 y y y 能被 x x x 解释的百分比 预测 要想估计 x 0 x_0 x0​对应的 y 0 y_0 y0​ 估计 E ( y 0 ) E(y_0) E(y0​)统计量为 T y 0 ^ − E ( y 0 ) σ ^ 1 n ( x 0 − x ˉ ) 2 l x x ∼ t ( n − 2 ) T \frac{\hat{y_0} - E(y_0)}{\hat{\sigma}\sqrt{\frac{1}{n} \frac{(x_0 - \bar{x})^2}{l_{xx}}}} \sim t(n-2) Tσ^n1​lxx​(x0​−xˉ)2​ ​y0​^​−E(y0​)​∼t(n−2) 估计 y 0 y_0 y0​统计量为 T y 0 ^ − y 0 σ ^ 1 1 n ( x 0 − x ˉ ) 2 l x x ∼ t ( n − 2 ) T \frac{\hat{y_0} - y_0}{\hat{\sigma}\sqrt{1 \frac{1}{n} \frac{(x_0 - \bar{x})^2}{l_{xx}}}} \sim t(n-2) Tσ^1n1​lxx​(x0​−xˉ)2​ ​y0​^​−y0​​∼t(n−2) 可见 x 0 x_0 x0​ 与 x ˉ \bar{x} xˉ 的偏差越大估计所得范围越宽。 若 n n n 足够大 x 0 x_0 x0​ 与 x ˉ \bar{x} xˉ 的偏差也不太大可近似取 Z y 0 ^ − y 0 σ ^ ∼ N ( 0 , 1 ) Z \frac{\hat{y_0} - y_0}{\hat{\sigma}} \sim N(0,1) Zσ^y0​^​−y0​​∼N(0,1) 多元线性回归 如果人们根据知识、经验或者观察等认为与因变量 y y y 有关联性的自变量不止一个那就应该建立多元线性回归模型。 方程形式 y β 0 β 1 x 1 β 2 x 2 ⋯ β k x k u y \beta_0 \beta_1 x_1 \beta_2 x_2 \cdots \beta_k x_k u yβ0​β1​x1​β2​x2​⋯βk​xk​u 最小二乘法 (OLS) min ⁡ Q ( β 0 , β 1 , ⋯ ) ∑ [ y i − ( β 0 β 1 x i 1 ⋯ β k x i k ) ] 2 \min Q(\beta_0, \beta_1, \cdots) \sum \left[y_i - (\beta_0 \beta_1 x_{i1} \cdots \beta_k x_{ik})\right]^2 minQ(β0​,β1​,⋯)∑[yi​−(β0​β1​xi1​⋯βk​xik​)]2 F.O.C. ∂ Q ∂ β 0 − 2 ∑ [ y i − ( β 0 β 1 x i 1 ⋯ ) ] 0 \frac{\partial Q}{\partial \beta_0} -2 \sum \left[y_i - (\beta_0 \beta_1 x_{i1} \cdots)\right] 0 ∂β0​∂Q​−2∑[yi​−(β0​β1​xi1​⋯)]0 ∂ Q ∂ β j − 2 ∑ x i j [ y i − ( β 0 β 1 x i 1 ⋯ ) ] 0 \frac{\partial Q}{\partial \beta_j} -2 \sum x_{ij} \left[y_i - (\beta_0 \beta_1 x_{i1} \cdots)\right] 0 ∂βj​∂Q​−2∑xij​[yi​−(β0​β1​xi1​⋯)]0 矩阵形式的方程 Y X β Y X \beta YXβ min ⁡ Q ( β ) ∥ Y − X β ∥ \min Q(\beta) \|Y - X \beta \| minQ(β)∥Y−Xβ∥ 系数向量可利用 X T Y X T X β X^T Y X^T X \beta XTYXTXβ 求解 拟合优度 R 2 S S E S S T 1 − S S R S S T R^2 \frac{SSE}{SST} 1 - \frac{SSR}{SST} R2SSTSSE​1−SSTSSR​ 调整后 R 2 1 − S S R / ( n − k − 1 ) S S T / ( n − 1 ) R^2 1 - \frac{SSR/(n-k-1)}{SST/(n-1)} R21−SST/(n−1)SSR/(n−k−1)​ 来源平方和自由度均方F比回归 S S E SSE SSE k k k M S E S S E k MSE\frac {SSE}{k} MSEkSSE​MSE/MSR残差 S S R SSR SSR n − k − 1 n-k-1 n−k−1 M S R S S R n − k − 1 MSR\frac {SSR}{n-k-1} MSRn−k−1SSR​合计 S S T SST SST n − 1 n-1 n−1 M S T n − 1 \frac {MST}{n-1} n−1MST​ 分类变量的处理 如果某个变量属于分类数据例如季节、学历、职务、房屋朝向等不应该用0、1、2等表示因为0与1、1与2的差不表示任何含义。 此时应当拆分成多个0-1变量进行处理以季节为例应该设3个变量 x1x2x3春天100夏天010秋天001冬天000 注意变量的数量必须比类别的数量少1否则会出现多重共线性问题。 注除此之外如果两个变量强相关也会出现多重共线性应考虑剔除其中一个 在多元线性回归中需谨慎选择回归变量使F比或调整后 ( R^2 ) 等统计量最大化留下的系数都显著。 枚举全部情况过于繁琐可采用逐步回归的方法 1每次引入一个新变量这个变量的系数应该显著而且应该使统计量增加最大 2引入一个新变量后立即检查是否有统计量可删除 3从影响最小的统计量开始删除直至删除全部可删除的变量 4重复以上过程直至没有统计量可再次引入 非线性回归 根据问题的实际背景有时已知回归方程的具体形式且无法化为线性回归的形式此时只能采用非线性回归利用最小二乘法求出待定系数 有监督和无监督分类模型 分类任务 不管是分类还是回归其本质是一样的都是对输入做出预测都是对输入做出预测并且都是监督学习。说白了就是根据特征分析输入的内容判断它的类别或者预测其值 有监督分类无监督分类定义使用标记的训练数据进行学习每个样本都有一个明确的输出或标签使用没有标记的数据算法会自动找到数据中的结构和模式样本需求需要标记数据即每个输入数据都有一个对应的标签或输出只需输入数据不需要对应的标签学习目的主要用于预测或分类任务如预测房价或分类猫和狗的图片主要用于数据的聚类或降维如客户细分或特征提取应用场景常用于分类问题、回归问题等如垃圾邮件过滤、天气预测常用于市场细分、社交网络分析、异常检测等模型复杂性因为有明确的输出可能需要复杂的模型来捕捉数据的模式模型可能更简单因为它只是试图理解数据的结构而不是预测明确的输出评估方法可以使用交叉验证、准确率、召回率等方法进行评估评估可能更为困难因为没有真实的标签来比较可能会使用轮廓系数、戴维斯-鲍尔丁指数等 有监督分类算法 有监督分类问题 训练算法的主要目标是建立具有很好泛化能力的模型即建立能准确预测未知样本类标号的模型 首先需要一个训练集training set由类标号已知的记录组成使用训练集建立分类模型然后将模型运用于检验集test由类标号未知的记录组成 训练集与检验集的划分方法 留出法 取较大比例的数据做训练集较小比例的数据做测试集只用训练集进行训练 交叉验证法k折法 将数据分成k份每次用其中k-1份做训练另外1份做测试 自助法 有放回抽样N次用作训练集没被抽到的数据用作测试集 训练误差 模型在训练集上的误差 泛化误差 模型在测试集上的误差 欠拟合 模型过于简单或迭代次数不够没学到数据的真实结构训练误差和泛化误差都很大 过拟合 数据过少模型太复杂或迭代次数过多训练误差很小但泛化误差太大 评价指标 对于二元分类问题而言可以建立混淆矩阵 准确率 预测正确的比例 a c c u r a c y T N T P T N F P F N T P accuracy\frac{TNTP}{TNFPFNTP} accuracyTNFPFNTPTNTP​ 查准率 预测类1当中有多少真的是类1 T P T P F P \frac{TP}{TPFP} TPFPTP​ 查全率 实际类1当中有多少预测出来了 T P T P F N \frac{TP}{TPFN} TPFNTP​ F1-score Precision准确率和Recall查全率的综合指标 2 × P r e c i s i o n × R e c a l l P r e c i s i o n R e c a l l \frac{2\times Precision \times Recall}{PrecisionRecall} PrecisionRecall2×Precision×Recall​ ROC-AUC 预测模型最后实际上给出的是一个属于类1的概率p 数据分析分析人员需要根据实际情况判断p大于多少的时候认为是类1 p越大则判断越严格查准率越高但查全率越低 当p取不同值的时候 Precision和Recall的图像就是P-R曲线二者相等的取值称为平衡点 TPR( T P T P F N \frac{TP}{TPFN} TPFNTP​)和FPR( F P T N F P \frac{FP}{TNFP} TNFPFP​)的图像就是ROCROC下方的面积就是AUC 对于多类问题可以先单独挑出一个类写出这个类相当于其余所有类的混淆矩阵 微平均 将混淆矩阵的各个格子相加再求出对应指标例如F1-score等 宏平均 先求出相应指标再平均 kNN算法 K邻近算法kNN是一种常用的监督学习算法其工作机制非常简单 1给定测试样本基于某种距离度量找出训练集中与其最靠近的k个训练样本 2然后基于这k个邻居的信息进行预测 3通常在分类任务中可使用“投票法”即选择这k个样本中出现最多的类别标记作为预测结果 4还可以基于距离远近进行加权投票距离越近则样本权重最大 kNN是懒惰学习lazy learning的著名代表无序训练在收到样本之后再进行处理即可 k值的选取和距离度量的选择会影响判断的结果 若k值太小则容易受到噪声扰动 若k值太大则可能受到较远样本的影响而预测错误 维数灾难 高维数据会给机器学习带来障碍不仅kNN算法面临这一问题其他机器学习方法也存在通用问题 维度太大则样本会很稀疏要想使样本布满空间所需样本数不可能实现这导致某个区域附件可能根本没有样本 位数太大时计算距离本身都存在困难 常用的位数约束算法 多维缩放MDS、主成分分析PCA等 kNN算法的特点 不需要建立模型训练开销为零但预测时需要大量运算 基于局部信息进行预测对噪声很敏感 可以生成任意姓形状的决策边界 数据预处理、选择合适的距离度量是非常重要 支持向量机SVM 给定训练样本集希望在样本空间中找到一个超平面将不同类别的样本分开 直观上看应该找位于两类训练样本正中间的超平面因为它对局部扰动的容忍度最好 这个超平面应该是样本距离最大的那个称为最大边缘超平面 支持向量机的设计是针对二类问题针对多类问题有两种思路 分解为K个二分类问题针对每个类构建分类器区分属于这个类和不属于这个类最后取属于某个类的概率最大者 分解为 K ( K − 1 ) 2 \frac{K(K-1)}{2} 2K(K−1)​个二分类问题每个问题都只针对两类最后投票选择 对于其他针对二分类问题的模型也可以采用上述思路 事实上由于样本的随机性可能无法找到一个完美的超平面将样本完全划分开 为解决这一问题可以允许支持向量机在一些样本上出错若出错则增加一个惩罚项最后的目标是使得间隔减去惩罚之后的结果最大这种模型称为“软间隔支持向量机” 在线性支持向量机当中边界必须是线性的如果实际上边界不是线性的就需要使用非线性支持向量机 找到一个非线性变换将样本映射再使用线性支持向量机 困难在于这个变换函数的寻找没什么特别的道理就是试 支持向量机的特点 数学上可转化为凸优化问题可以找到全局最优其他方法一般只能找到局部最优 需要决定的参数比较多比如惩罚项系数、变换函数 朴素贝叶斯 假设各属性是相互独立的如果各属性只能取离散值 根据训练样本可以求出各种分类的各属性取各种值的概率 即 P ( X i 0 ∣ Y 0 ) P(X_i0|Y0) P(Xi​0∣Y0)、 P ( X i 0 ∣ Y 1 ) P(X_i0|Y1) P(Xi​0∣Y1)、 P ( X i 1 ∣ Y 0 ) P(X_i1|Y0) P(Xi​1∣Y0)、 P ( X i 1 ∣ Y 1 ) P(X_i1|Y1) P(Xi​1∣Y1) 对于测试样本可以根据贝叶斯公式求出这个样本的属性下各种分类的概率 即 P ( Y 0 ∣ X ) P(Y0|X) P(Y0∣X)、 P ( Y 1 ∣ X ) P(Y1|X) P(Y1∣X) 选择较大者作为预测的分类 对于能取连续值的属性假设正态分布实际求出的是概率密度方法类似 朴素贝叶斯的特点 对于孤立的噪声点分类器是健壮的 面对无关性质分类器是健壮的 若属性之间有相关关系朴素贝叶斯的性能会降低 决策树 将整个训练样本作为根结点重复对每个节点按照某个属性的值进行逐层划分形成一棵树 理论上划分的终止条件有三种 某个节点的样本类别全部相同无需再分 某个节点的样本属性全部相同无法再分 某个节点不包含任何样本不能再分 划分标准 用所有属性进行尝试选择信息熵降低最大的那个除此之外还有增益率、Gini系数等划分标准 为了避免过拟合决策树不能太复杂可进行“剪枝”。如果划分之后在测试集上的准确度反而还下降就不应该进行这个划分 预剪枝 在生成树的过程中就进行剪枝 后剪枝 先生成一颗完整的树再判断怎么剪枝 决策树的特点 对类和属性的分布不需要任何假设 构建决策树和使用决策树进行预测的效率都很高 相对容易解释 边界理论上都和坐标轴平行不能很好适用于某些特定问题斜决策树可克服 对噪声的干扰具有很好健壮性 冗余属性不会造成不利影响 越分越细会导致样本越来越少数据碎片问题此时不应该再做分割 集成学习 构建并结合多个相对较弱的学习期来完成学习任务通常获得比单一学习器显著优越的泛化能力 Boosting 每轮提升上一轮分类错误的样本权重应用于决策树就是随机森林 Bagging 每次用一小部分数据训练许多分类器再投票应用于决策树就是GBDT 总结与归纳 评价维度选择依据特征性质分类特征:决策树随机森林朴素贝叶斯数值特征:支持向量机混合特征:决策树随机森林支持向量机缺失值情况缺失值很多:决策树随机森林。缺失值不多:支持向量机类别平衡情况不平衡类使用随机森林支持向量机数据复杂性中等复杂度:决策树随机森林朴素贝叶斯复杂度高:支持向量机速度和准确度平衡速度更重要:决策树朴素贝叶斯精度更重要:随机森林支持向量机数据噪声情况适度噪声:决策树随机森林高噪声:支持向量机离群值情况数据异常值多:svm或随机森林的健壮模型。对离群值敏感的模型:线性回归逻辑回归鲁棒性高的模型:决策树随机森林支持向量机 无监督分类算法 聚类问题Clustering概述 聚类问题试图将数据集中的样本划分为若干不想交的子集每个子集称为一个簇 训练样本的标记信息是未知的目标是揭示数据的内在性质和规律 聚类问题的评价指标 外部指标 聚成了一类没聚成一类实际上是一类ab实际上不是一类cd 与某个参考模型或实际情况进行比较 Jaccard系数JC a a b c \frac{a}{abc} abca​ FM指数FMI a a b × a a c \sqrt{\frac{a}{ab} \times \frac{a}{ac}} aba​×aca​ ​ Rand指数RI 2 ( a d ) m ( m − 1 ) \frac{2(ad)}{m(m-1)} m(m−1)2(ad)​其中 m n ( n − 1 ) 2 m\frac{n(n-1)}{2} m2n(n−1)​ 内部指标 只考察聚类结果本身没有信息可供参考好的聚合结果应该组内紧密、组间分散 凝聚度SSE 各个簇内部点的距离平方的平均值 分离度SSB 各个簇质心到整体均值的距离平方和 轮廓系数Silhouette Coefficient b − a m a x ( a , b ) \frac{b-a}{max(a,b)} max(a,b)b−a​ a a a表示点到簇内其他点的平均距离 b b b表示点到另一个簇所有点的平均值取最小者 DB指数DBI m a x a v g ( C i ) a v g ( C j ) d c e n ( i , j ) max{\frac{avg(C_i)avg(C_j)}{d_{cen}(i,j)}} maxdcen​(i,j)avg(Ci​)avg(Cj​)​ a v g ( C i ) avg(C_i) avg(Ci​)表示第 i i i个簇内所有点的平均距离 d c e n ( i , j ) d_{cen}(i,j) dcen​(i,j)表示两个簇中心的距离 Dunn指数DI d m i n ( i , j ) m a x d i a m \frac{d_{min}(i,j)}{max\ diam} max diamdmin​(i,j)​ 其中 d m i n ( i , j ) d_{min}(i,j) dmin​(i,j)表示两个簇样本之间的最小距离diam表示簇内样本的最远距离 K均值方法K-means K均值方法是一种基于原型的聚类假设聚类结构通过一组原型刻画 原型通常是质心即簇中所有点的均值也可以用最有代表性的点 每个对象到这个簇的原型比到其他簇的原型更近 这种簇会趋向于圆球状 过程 随机选择K歌点作为初始质心 重复以下步骤 ​ 将其余每个点指派到最近的质心形成K个簇 ​ 重新计算质心 直到质心不再发生变化 K-means K均值方法的初始质心如果选择不当结果会很差K-means算法改进了这一步骤 先随机选择一个点 再选择下一个点但距离越远选到的概率越大 重复上述步骤直至选出K个点 如果样本过多则运算会很慢mini-batch K均值方法每次只选取一小批样本进行运算可以加速算法收敛但效果会打折扣 K值选择 如何选择K值可采用肘部法则 用不同的k进行聚类得到SSE或其他指标找到下降幅度明显趋缓的点作为k的取值 优点 计算简单可用于各种数据类型 变种例如K-means克服了初始化问题的影响 缺点 只适用于球形的簇不能处理其他形状的簇 仅限于具有中心概念的数据 离群点影响很大 K值必须事先指定 DBSCAN DBSCAN方法是一种基于密度的聚类簇是对象的稠密区域被低密度的区域所包围 基于中心的密度 核心点 位于簇内部给定半径Eps内邻域的点数量超过阈值MinPts 边界点 不是核心点但落入某个核心点的邻域内 噪声点 既不是核心点也不是边界点 过程 判断每个点属于核心点、边界点还是噪声点 删除噪声点 连接距离小于阈值的核心彼此相连的核心点构成一个簇 将边界点指派到关联的簇当中 参数 如何确定参数 观察每个点到它最近的k个点的距离k-距离簇内的点应该较小而噪声点应该较大 给定k画出k-距离的累计值如果看到急剧变化则可以对应Eps值 二维数据集经验上取k4比较合理 优点 基于密度的定义是相对抗噪声的 能处理任意形状和大小的簇能发现K-means发现不了的簇 缺点 对于高维数据的密度定义困难 为了计算所有点对的距离计算开销很大 层次聚类 层次聚类有两种主要方法 凝聚方法 开始时每个点自己是一个簇每一步合并两个最接近的簇直至只剩下一个簇 这种方法需要定义簇的邻近性 分裂方法 开始时所有点构成一个簇每一步分裂一个簇直至每个点各成一簇 这种方法需要确定如何判断分裂哪个簇、如何分裂 注意 其中凝聚法更为常用 层次聚类常常使用树状图或嵌套族图表示簇合并或分裂的次序 若指定要分成几个簇事实上是指定了凝聚或分裂到哪个层级 基本凝聚层次聚类算法 预先计算邻近矩阵 每一步合并最接近的两个簇 更新邻近矩阵 重复以上步骤直至所有点属于一个簇 邻近度 如何定义邻近度 单链min 两个簇中任意两点距离的最小值适合处理非椭圆形状的簇但对噪声和离群点不太敏感 全链max 两个簇中任意两点距离的最大值偏好球形容易使大的簇分裂对噪声和离群点不太敏感 组平均 两个簇中所有点对距离的平均值 Ward方法 两个簇合并时导致平方误差的增量 质心方法 两个簇的质心距离 优点 能形成层次结构 有时能产生高质量的聚类 缺点 计算开销大 一旦做出决定则不可撤销容易陷入局部最优 谱聚类 谱聚类是从图论演化出来的算法后来在聚类中得到广泛的应用 主要思想是把所有的数据看做空间中的点这些点之间可以用边连接起来距离较远的两个点之间的边权重值较低而距离较近的两个点之间的边权重值较高 通过对所有数据点组成的图进行切图让切图后不同子图间边权重和尽可能的低而子图内的边权重和尽可能的高从而达到聚类的目的 优点 谱聚类只需要数据之间的相似度矩阵处理稀疏数据的聚类很有效 在处理高维数据聚类时的复杂度比传统聚类算法好 缺点 若数据降维不够谱聚类也很难得到较好结果 结果依赖于相似矩阵不同的相似矩阵得到的最终聚类效果可能很不同 总结与归纳 如何选择聚类算法 聚类算法应用场景举例筛选依据K-means文档的分类和聚类、客户分类营销、犯罪地点发现等一般场景簇大小相近球形簇数量不太多DBSCAN图像分割、地理数据聚类分析、网络流量数据中的异常行为非球形簇大小不均衡考虑离群点层次聚类生物学和金融领域物种的基因组序列进化分类或是对相似结构的蛋白质进行归类。客户分类和风险评估簇数量多层次信息有意义谱聚类社交网络分析、机器视觉领域簇数量不多大小相近非球形 时间序列模型 时序分析基础 时间序列数据规律 变化规律字母表示描述示例长期趋势TrendT持续上升或者持续下降人均收入变化出生率变化等季节变动Seasonal EffectS周、月、季的周期性变动不同季节衣服的销量循环波动Cyclical FluctuationC波浪式的周期波动年经济周期变化不规则变动Residual/errorI不可预测、无规律体重变化 时间序列数据性质 平稳性 强平稳 数据分布在实践的平移下的分布保持不变 弱平稳 均值方差自相关系数等不因时间变化而变化 校验方法 直观分析法时序图包括均值、方差等 数学校验法单位根校验ADF、KPSS 差分 将数据转换为平稳性数据对时间序列进行相邻观察值之间的减法操作 一阶差分是指当前时刻的观察值减去上一时刻的观察值 二阶差分是指一阶差分再减去上一刻的观察值依次类推 自相关性 意义 时间序列中某一个时刻的值和另一个时刻的值之间的关系发现 度量方法 相关系数、自相关函数ACF、偏自相关函数PACF 度量结果 正相关性、负相关性、零相关性 截尾 是指时间序列的自相关函数ACF或偏自相关函数PACF在某阶后接近或等于零或者急剧下降的性质。截尾表示时间序列的相关性在该阶之后逐渐减弱数据不再受之前的值的影响 拖尾 即ACF或PACF并不在某阶后均为零。在某个阶数之后仍然保持较高的值或者出现明显的周期性波动那么这个时间序列就具有拖尾的特性。拖尾表示时间序列的相关性在该阶数之后仍然存在存在长期的依赖关系 数据预处理 异常数据值处理 离群点 删除 缺失值 缺失值发生在时间序列的开头或者尾部可采用直接删除的方法 缺失值发生在序列的中间位置则采用替换缺失值的方法 替换方法 序列平均值整个序列的平均值 临近点的平均值相邻若干点的平均值 临近点的中位数相邻若干点的中位数 线性插值相邻两个点的平均值 临近点的线性趋势回归拟合 季节性分析 前提 具备年内周期性 目的 将时间序列数据拆分成具有不同特征和规律的成分 应用 理解数据的趋势、季节性和随机波动成分进行预测、分析和决策提供依据 常用模型算法 朴素预测法 朴素模型的思路假定未来的需求将完全复制过去的模式。朴素模型又称为随机漫步法有时也被称为无变化模型因为它预测未来时期的结果和过去观察到的实际结果完全一样没有变化 Naive Forecast是指预测下一期需求时下一期的预测数量等于本期的实际需求数量 y t 1 y t y_{t1}y_t yt1​yt​ 简单平均法 预测的期望值等于所有先前观察点的平均值简称简单平均法 y t 1 1 n ∑ i 1 n y i y_{t1} \frac{1}{n} \sum_{i1}^{n} y_i yt1​n1​i1∑n​yi​ 移动平均法 计算过去一段时间内的观测值的平均值来预测未来的值 简单移动平均SMA 最近的价值才重要计算移动平均值涉及到“滑动窗口”的大小值p根据之前数值的固定有限数p的平均值预测某个时序中的下一个值 y i 1 p ∑ i l − p l − 1 y i y_i\frac{1}{p} \sum_{il-p}^{l-1}y_i yi​p1​il−p∑l−1​yi​ 加权移动平均WMA 滑动窗口期内的值被赋予不同的权重通常来讲最近时间点的值越重要 y l 1 p ∑ i l − p l − 1 w i ⋅ y i y_l\frac{1}{p}\sum_{il-p}^{l-1}{wi \cdot y_i} yl​p1​il−p∑l−1​wi⋅yi​ 指数平均法 利用指数加权的方式对历史数据进行平滑处理较新的数据具有更高的权重简单平均和移动平均的集成 指数平滑法相比更早时期内的观测值越近的观测值会被赋予更大的权重而时间越久的权重越小 一次指数平滑法 适用于没有明显趋势或季节性的数据。它使用加权平均来预测未来的值其中近期的观测值具有更高的权重 二次指数平滑法 除了考虑数据的水平外还考虑数据的线性趋势。它使用两个平滑参数一个用于水平另一个用于趋势 三次指数平滑法 同时考虑数据的水平和季节性模式。它使用三个平滑参数一个用于水平一个用于趋势还有一个用于季节性 自回归移动平均模型ARMA ARMA模型将自回归AR和移动平均MA两种方法结合起来用于描述时间序列数据的动态特性 ARMA模型一般形式可以表示为ARMA(pq)其中 p p p代表自回归阶数 q q q代表移动平均阶数 移动平均 将时间序列中的每个值与前面若干个值的平均值进行比较用于平滑数据和检测趋势 自回归 将时间序列的当前值与其过去若干值进行线性组合用于预测未来值 y t α 0 ∑ i 1 p α i y t − i ϵ t ∑ i 1 q β i ϵ t − i y_t \alpha_0 \sum_{i1}^{p} \alpha_i y_{t-i} \epsilon_t \sum_{i1}^{q} \beta_i \epsilon_{t-i} yt​α0​i1∑p​αi​yt−i​ϵt​i1∑q​βi​ϵt−i​ 差分自回归移动平均模型ARIMA 建立ARIMA模型一般有三个阶段分别是模型识别和定阶、参数估计和模型检验 模型识别和定阶 确定pdq三个参数差分的阶数d一般通过观察图示1阶或2阶即可 模型 (序列)AR §MA (q)ARMA (p, q)自相关函数拖尾第q个后截尾拖尾偏自相关函数第p个后截尾拖尾拖尾 模型校验 1检验参数估计的显著性t检验 2检验残差序列的随机性即残差之间是独立的。残差序列的随机性可以通过自相关函数法来检验即做残差的自相关函数图 季节性自回归移动平均模型SARIMA SRAIMA季节性自回归移动平均模型在ARIMA模型的基础上增加了季节性的影响结构参数有七个SARIMApdqPDQs 参数概念特点p非季节自回归的阶数对于AR模型可以借助PACF确定阶数pACF拖尾PACFp阶截尾q非季节移动平均的阶数对于MA模型可以借助PACF确定阶数qPACF拖尾ACFq阶截尾d一阶差分次数做了多少次一阶差分就是多少P季节自回归的阶数通常不会大于3从PACF上判断如果季节长度为12看PACF图上落后12阶、24阶、48阶的自相关系数如果落后到24阶时就截尾了那么P等于2Q季节移动平均的阶数通常不会大于3从ACF上判断如果季节长度为12看ACF图上落后12阶、24阶、48阶的自相关系数如果落后到12阶时就截尾了那么Q等于1D季节差分次数通常不会大于1一般就差0或1做了季节差分就是1S季节周期长度该季节性序列的周期大小注意不一定是12 时序建模流程 1数据收集 2数据清洗和预处理处理缺失值、异常值、平稳性检验、去除趋势和季节性等。 3可视化和探索性数据分析EDA通过绘制时间序列图、自相关图、偏自相关图等对数据进行可视化和探索性分析以了解数据的基本特征。 4模型选择根据数据的特点选择合适的时序模型可能包括自回归模型AR、移动平均模型MA、自回归移动平均模型ARMA、自回归积分移动平均模型ARIMA等。 5参数估计对所选的模型进行参数估计可以使用最大似然估计等方法来估计模型的参数。 6模型诊断对建立的模型进行诊断包括残差分析、模型拟合优度检验等以确保模型的合理性和有效性。 7模型预测利用建立的模型对未来的数据进行预测可以使用模型的预测能力进行评价并进行预测结果的解释和分析。 8模型优化和调参根据模型的预测效果对模型进行调优和调参以提高模型的预测准确性。 9结果解释和应用 相关性分析和差异性分析 概念 相关性分析 指的是两个随机变量或随机向量之间的线性相关性衡量两个变量之间的关联程度。 差异性分析 比较不同组别之间的差异 相关定义 连续变量 对连续的指标测量所得到的数值 二分类变量 只有两个类别的二分类变量二分类变量的类别之间没有内在顺序 有序分类变量 两个或者多个已排序的类别 无序分类变量 具有三个及以上类别的分类变量。无序分类变量的类别之间没有内在顺序也不能像有序分类变量类别那样进行排序 自变量 预测变量或解释变量 因变量 应答变量或结局变量 方法选择 自变量因变量分析方法连续变量连续变量皮尔逊相关有序分类变量[非定距]有序分类变量[非定距]斯皮尔曼相关二分类数据定量数据T检验多分类数据定量数据方差分析分类变量分类变量卡方分析 使用相关性分析的情况 1只想分析两个变量之间是否存在相关关系不需要区分自变量和因变量时可用相关性分析。 2通常在进行回归分析之前都需要进行相关性分析。 相关性分析的方法 1变量特性可以通过绘制散点图判断 2通过计算显著性系数判断是否相关主要是P值 3通过计算相关性系数判断相关性大小主要是r值 显著性系数判定方法 P值是用来进行显著性检验的用来检验变量之间是否具有差异以及差异是否显著。 若P值0.05代表数据之间不存在显著性差异若P值0.05代表数据之间存在显著性差异。 相关系数判定方法 判定准则 一般可分为三级划分: ∣ r ∣ \left| r \right| ∣r∣0.4为低线性相关0.4$ \leq KaTeX parse error: Cant use function $ in math mode at position 19: …ft | r \right |$̲0.7为显著性相关0.7$…\left | r \right |$1为高度线性相关。 计算方法 Pearson系数叫皮尔逊相关系数也叫线性相关系数用于进行线性相关发内心是最常用的相关系数当数据满足正太分布时会使用该系数。 Spearman系数当数据不满足正态分布使用该系数。 相关性系数判定方法-Pearson相关系数 用于衡量两个连续变量之间的线性相关程度基于协方差的概念通过计算两个变量的协方差除以它们各自的标准层的乘积得到一个范围在-1到1之间的相关系数。 适用范围 1两个变量之间是线性关系都是连续数据。 2两个变量的总体是正态分布或接近正态的单峰分布。 3两个变量的观测值是成对的每对观测值之间相互独立。 相关性系数判定方法-Spearman秩相关系数 Spearman秩相关系数的计算需要先将原始数据转换为秩次即按大小排序后的顺序排名然后再计算秩次之间的Pearson相关系数。用于衡量两个变量之间的单调关系不要求变量服从正态分布 适用范围 1两个变量的观测值是成对的等级评定资料 2由连续变量观测资料转化得到的等级资料 选择基准 Spearman和Pearson使用选择 1连续数据正态分布线性关系用Pearson相关系数是最恰当当然用Spearman相关系数也可以就是效率没有Pearson相关系数高。 2上述任一条件不满足就用Spearman相关系数不能使用Pearson相关系数。 3两个定序测量数据之间也用Spearman相关系数不能用Pearson相关系数。 差异性分析概述 差异性分析是指两组或多组数据进行比较以确定它们之间在某些变量上的差异或相似性的统计分析方法 常用方法 原理比较均值/频数 目的检测科学实验中实验组与对照组之间是否有差异以及差异是否显著的办法。又称[差异性显著检验]是假设检验的一种判断样本间差异主要是随机误差造成的还是本质不同。 方法实用场景组别示例T检验研究分类数据和定量数据之间的关系两组样本性别对于满意度的差异程度方差分析研究分类数据和定量数据之间的关系两组或更多组不同学历样本对工作满意度的差异情况卡方分析研究分类数据和分类数据之间的关系性别和是否戴隐形眼镜之间的关系性别和是否购买理财产品之间的关系 T检验 可以用于比较两组数据之间是否来自同一分别可以用于比较两组数据的区分度 主要用途样本均数与总体均数的差异两样本均数的差异比较 分类实用场景目的示例单样本T校验正态分布总体方差未知检验单样本的均值与某一已知数已知总体的均值是否有显著性差异从某厂生产的零件中随机抽取若干件检验其某种规格的均值是否与要求的规格相等配对样本T校验总体方差相等正态分布检验在两次不同条件下来自用一组观察对象的两组样本是否具有相同的均值同一受试对象的自身前后对照如检验癌症患者术前、术后的某种指标的差异独立双样本T检验两样本独立服从正态分不分或近似正态检验两对独立的正态数据或近似正态的均值是否相等检验两工厂生产同种零件的规格是否相等 方差分析 用于比较三个或三个以上组别的均值是否存在显著差异的统计方法 基于组内变异和组间变异的比较来判断各组均值的差异情况。它将总体方法分解为组间变异和组内变异两部分然后通过比较这两部分的大小来判断各组均值是否存在显著性差异 分类适用场景目的示例单因素方差分析one-way ANOVA所有样本均来自正研究一个控制变量的不同水平是否对观测变量产生和了显著影响检验不同时间记录(早晨下午和晚上)的睁眼状态下的静息脑电信号平均功率的均值是否相同配对样本T校验two-way ANOVA态总体这些正态研究两个因素行因素row和列因素column是否对观测变量产生了显著影响分析氮、磷两种肥料的施用量对水稻产量是否有显著性影响独立双样本T检验multi-way ANOVA总体具有相同的方差研究两个因素行因素row和列因素column是否对观测变量产生显著影响 卡方分析 1用于比较观察频数与期望频数之间的拟合优度或独立性的统计方法。 2适用于分类变量的独立性检验和拟合优度检验 3原理是通过比较观察频数和期望频数之间的差异来判断两个变量之间是否存在关联或拟合程度 显著性分析比较 T校验用于比较两组数据例如两个独立样本的均值是否有显著差异 方差分析ANOVA用于比较三组或更多组数据的均值是否有显著差异。它通常用于检验一个或多个独立变量对一个因变量的影响 卡方分析用于检验两个分类变量是否独立。它属于观察频数与期望频数之间的差异来工作通常用于检验分类数据之间的关联性 每个检验都返一个p值这个p值可以用来判断观察到的差异是否可能是由随机误差引起的还是确定存在显著性差异。通常如果p值小于某个预定的显著性水平例如0.05我们就拒绝原假设即认为数据之间不存在显著性差异的假设并认为观察到的差异是不显著的。 机器学习模型 机器学习 通过算法使得机器能从大量数据中学习规律从而对新的样本做决策。数据和特征决定了机器学习结果的上限而模型算法只是尽可能逼近这个上限。 流程原始数据-数据预处理-特征提取-特征转换-预测-结果 深度学习 通过构建具有一定“深度”的模型可以让模型来自动学习好的特征表示从底层特征到中层特征再到高层特征从而最终提升预测或识别的准确性。 流程原始数据-中层特征-高层特征-预测-结果 神经网络 人工神经网络主要由大量的神经元以及它们之间的有向链接构成。因此考虑三方面 1神经元的激活规则主要是指神经元输入到输出之间的映射关系一般为非线性函数 2网络的拓扑结构不同神经元之间的连接关系 3学习算法通过训练数据来学习神经网络的参数 激活函数 激活函数对输入信息进行非线性变换。然后将变换后的输入信息作为信息传给下一层神经元 1Sigmoid函数数据被变换在0和1之间对于特别小的负数输出为0特别大的正数输出为1 2Tanh函数将元素的值变换到-1和1之间形状和Sigmoid函数的形状很像但tanh函数在坐标系的原点上对称 3ReLu函数ReLu函数只保留正数元素并将负数元素清零 Softmax函数用于多分类问题的激活函数对于长度为K的任意实向量Softmax可以将其压缩为长度为K值在0,1范围内并且向量中元素的总和为1的实向量 注意ReLu函数是一个通用的激活函数目前大多数情况下使用。但是ReLu函数只能在隐藏层中使用用于分类器时Sigmoid函数及其组合效果更好由于梯度消失问题有时要避免使用Sigmoid和Tanh函数’在神经网络层数较多时候最好使用ReLu函数ReLu函数比较简单计算量少而Sigmoid和Tanh函数计算量大很多在选择激活函数的时候可以先选用ReLu函数如果效果不理想可以尝试其他激活函数。 神经网络 人工神经网络由神经元模型构成大体上分为三种类型但是大多数网络都是复合型结构即一个神经网络中包括多种网络结构 层一组神经网络中负责处理一组输入特征或一组神经元的输出的神经元 全连接层又称密集层一种每个节点均与下一隐藏层中每个节点相连的隐藏层 输入层神经网络的第一层 输出层神经网络的最后一层 损失函数 在深度学习中损失函数loss起着至关重要的作用。它用于衡量模型预测与真实值之间的差异通过优化算法指导模型的训练过程。 1绝对损失MAE它计算的是预测值与真实值之间绝对值的平均值对损失函数在处理回归问题时较为常用 2平方损失MSE它计算的是预测值与真实值之间平方的平均值平方损失函数在处理回归问题时也常被使用 3交叉熵损失它用于解决分类问题计算的是预测概率与真实标签之间的交叉熵值适用于多分类问题 优化器 优化器是在深度学习反向传播过程中指引损失函数目标函数的各个参数往正确的方向更新合适的大小使得更新后的各个参数让损失函数目标函数值不断逼近全局最小 1首先是优化方向决定“前进的方向是否正确”在优化器中反映为梯度或动量 2其次是步长决定“每一步迈多远”在优化器中反映为学习率 分类 随机梯度下降SGD每次从训练集中随机选择一个样本来进行学习 SGDM加入一阶动量一阶动量是各个时刻梯度方向的指数移动平均值也就是说t时刻的下降方向不仅由当前点的梯度方向决定而且由此前累积的下降方向决定 AdaGrad加入二阶动量用下一个点的梯度方向与历史累计动量相结合 RMSOrop梯度平方和累加为指数加权的移动平均使得其在非凸设定下效果更好 AdamAdam结合了前面的方法的一阶动量和二阶动量 选择优化器要考虑的因素 数据集的规模和复杂性 对于大规模数据集和复杂模型应该选择具有较好收敛性的优化器如SGD和Adam 模型的稀疏性 对于稀疏模型应该选择Adagrad或其他自适应学习率的优化器 训练模型 对于需要较快训练速度的场景可以选择具有加速功能的优化器如SGD的带动量更新或Nesterov动量更新或者选择具有较高并行性的优化器如Adam或Adagrad 学习率的调整 对于需要调整学习率的场景可以选择自适应学习率的优化器如Adam或Adagrad 算法选择路径图 回归模型 回归方法是一种对数值型连续随机变量进行预测和建模的监督学习算法 使用案例一般包括房价预测、股票走势或测试成绩等连续变化的案例 特点是标注的数据集具有数值型的目标变量每个观察样本都有一个数值型的标注真值以监督算法回归模型 常见的回归模型 线性回归超平面拟合 岭回归 决策树回归 最近邻算法knn搜寻最相似的训练样本来预测观察样本的值 Lasso回归最小绝对值收敛和选择算子算法 深度学习 岭回归 岭回归是一种专用于共线性数据分析的有偏估计回归方法实质上是一种改良的最小二乘估计法。岭回归主要解决的问题是两种一是当预测变量的数量超过观测变量的数量时候预测变量相当于特征观测变量相当于标签二是数据集之间具有多重共线性即预测变量之间具有相关性 防止过拟合 自变量X至少一项或以上的定量变量或二分类定类变量 因变量Y要求为定量变量若为定类变量请使用逻辑回归 特性1特性2举例定类数字代表类别可以计算百分比性别、是否吸烟定量数字大小有对比意义可以计算平均值身高、体重 Lasso回归 Lasso回归是一种数据挖掘方法即在常用的多元线性回归中添加惩罚函数不断压缩系数从而达到精简模型的目的以避免共线性和过拟合。当系数为0时同时达到筛选变量的效果 决策树回归 在面对不同数据时决策树也可以分为两大类型分类决策树和回归决策树。前者主要用于处理离散型数据后者主要用于处理连续性数据。采用的是启发式的方法。假如我们有n个特征每个特征有 S i S_i Si​个取值那我们遍历所有特征尝试该特征的所有取值对空间进行划分直到取到特征 j j j的取值 s s s使得损失函数最小这样就得到一个划分点 分类模型 分类模型是一种对离散型随机变量建模或预测的监督学习算法 使用案例包括邮件过滤、金融欺诈和预测雇员异动等输出为类别的任务 分类算法通常适用于预测一个类别或类别的概率而不是连续的数值 分类模型 逻辑回归logistic函数即Sigmoid函数将预测映射到0到1中间 分类树决策树、随机森林 深度学习 支持向量机SVM核函数、超平面 朴素贝叶斯基于贝叶斯定理和特征条件独立假设、概率 聚类模型 聚类是一种无监督学习任务该算法基于数据内部结构寻找观察样本的自然族群即集群 使用案例包括细分客户、新闻聚类、文章推荐等 无监督学习即数据没有标注并且通过使用数据可视化评价结果 聚类模型 K-means聚类聚类的度量基于样本点之间的几何距离 层次聚类自顶向下、自底向上 谱聚类图、子图 DBSCAN基于密度的算法它将样本点的密集区域组成一个集群 降维模型 降维就是对高维度特征数据预处理方法。降维是将高维数据保留下最重要的一些特征去除噪声和不重要的特征从而实现提升数据处理速度的目的 降维模型 PCA主成分分析 自编码器AE PCA PCA的主要目的是为了得到方差最大的前N个特征通过计算数据矩阵的协方差矩阵然后得到协方差矩阵的特征值特征向量选择特征值最大即方差最大的 k k k个特征所对应的特征向量组成的矩阵。这样就可以将数据转换到新的空间当中实现数据特征的降维[线性降维] 流程图 自编码器 自编码器通过无监督学习的方式将输入数据压缩成低维表示再从低维表示中重构出原始数据。编码器将输入数据压缩成低维表示而解码器则尝试从压缩后的表示中重构出原始数据。通常比较重构数据和原始数据的差异来实现例如均方误差MSE或交叉熵等 深度学习 optimizer优化器用于控制梯度裁剪。必选项 loss损失函数或称目标函数、优化评分函数。必选项 metrics评价函数用于评估当前训练模型的性能。当模型编译后compile评价函数应该作为metrics的参数来输入。评价函数和损失函数相似只不过评价函数的结果不会用于训练过程中 批次batch模型训练的一次迭代一次梯度更新中使用的样本集 批次大小batch size一个批次中的样本数 轮次epoch在训练时整个数据集的一次完整的遍历 卷积神经网络CNN 卷积神经网络属于神经网络的一个重要分支。应用于CVNLP等的各个方面。CNN通过使用卷积层、池化层和全连接层来提取出图像中的局部特征 1卷积层通过滤波器对图像进行卷积操作提取出图像中的局部特征 2池化层不改变三维矩阵的深度可以缩小矩阵的大小进一步缩小最后全连接层中节点的个数从而到达减少整个神经网络的目的 3全连接层FC在整个卷积中起到“分类器”的作用。如果说卷积层、池化层和激活函数等操作是将原始数据映射到隐层特征空间全连接层则起到将学到的“分布式特征映射”到样本标记空间的作用 循环神经网络RNN 循环神经网络是指在全连接神经网络的基础上增加了前后时序上的关系可以更好地处理比如机器翻译等的与时序相关的问题。RNN的目的就是用来处理序列数据的。 1x是一个向量它表示输入层的值 2s是一个向量它表示隐藏层的值 3U是输入层到隐藏层的权重矩阵 4O也是一个向量它表示输出层的值 5V是隐藏层到输入层的权重矩阵 6循环神经网络的隐藏层的值S不仅仅取决于当前这次的输入x还取决于上一次隐藏层的值s。权重矩阵W就是隐藏层上一次的值作为这一次的输入的权重。 长短期记忆LSTM 长短期记忆是一种特殊的RNN主要是为了解决长序列训练过程中的梯度消失和梯度爆炸问题。简单来说就是相比普通的RNNLSTM能够在更长的序列中有更好的表现。记忆单元的关键是门。这些也是加权函数它们进一步控制单元中的信息。有3个门“ 1遗忘门。决定什么样的信息需要从单元中丢弃 2输入门。决定输入中哪些值来更新记忆状态 3输出门。根据输入和单元的内存决定输出什么 机理分析类 微分方程 马尔萨斯人口模型 1789年英国神父Malthus在分析了一百多年人口统计资料后提出Malthus模型。 模型假设 1 x ( t ) x(t) x(t)表示t时刻的人口数且 x ( t ) x(t) x(t)连续可微 2人口的增长率 r r r是常数增长率出生率-死亡率 3人口数量的变化是封闭的即人口数量的增加与减少只取决于人口中个体的生育和死亡且每一个个体都具有同样的生育能力与死亡率 阻滞增长模型 如果对增长率 r r r进行修正呢我们知道地球上的资源是有限的它只能提供一定数量的生命生存所需的条件。随着人口数量的增加自然资源环境条件等对人口再增长的限制作用将越来越显著。如果在人口较少时可以把增长率r看成常数那么当人口增加到一定数量之后就应当视 r r r为一个随着人口的增加而减小的量即将增长率 r r r表示为人口 r ( x ) r(x) r(x)且 r ( x ) r(x) r(x)为 x x x的减函数。 模型假设 1设 r ( x ) r(x) r(x)为 x x x的线性函数 r ( x ) r − s x r(x)r-sx r(x)r−sx工程师原则首先用线性 2自然资源与环境条件所能容纳的最大人口数为 x m x_m xm​。即当 x x m xx_m xxm​时增长率 r ( x m ) 0 r(x_m)0 r(xm​)0 Volterra模型沃尔泰拉模型 食饵即猎物和捕食者在时刻 t t t的数量分别记作 x 1 ( t ) x_1(t) x1​(t)和 x 2 ( t ) x_2(t) x2​(t)。因为大海中资源丰富可以假设如果出食饵独立生存则将以增长率 r 1 r_1 r1​按指数规律增长即有 d x 1 d t r 1 x 1 \frac{dx_1}{dt} r_1 x_1 dtdx1​​r1​x1​捕食者的存在使得食饵的增长率降低假设降低的程度正比于捕食者的数量于是 x 1 ( t ) x_1(t) x1​(t)满足方程 d x 1 d t x 1 ( r 1 − λ 1 x 2 ) \frac{dx_1}{dt} x_1 (r_1 - \lambda_1 x_2) dtdx1​​x1​(r1​−λ1​x2​) 其中比例系数 λ 1 \lambda_1 λ1​反应捕食者掠取食饵的能力 捕食者离开食饵无法生存若假设它独自存在时的死亡率为 r 2 r_2 r2​即食饵为它提供食物的作用相当于使其死亡率降低。假设这个作用与食饵数量成正比于是 x 2 ( t ) x_2(t) x2​(t)满足方程 d x 2 d t x 2 ( − r 2 λ 2 x 1 ) \frac{dx_2}{dt} x_2 (-r_2 \lambda_2 x_1) dtdx2​​x2​(−r2​λ2​x1​) 其中比例系数 λ 2 \lambda_2 λ2​反映食饵对捕食者的供养能力 方程1、2是在没有人工捕获情况下的自然环境中食饵与捕食者之间的制约关系是数学家Volterra提出的最简单的模型。 考虑到人工捕获时假设表示捕获能力或强度的系数为 e e e那么相当于食饵的自然增长率由 r 1 r_1 r1​降为 r 1 − e r_1-e r1​−e捕食者的死亡率由 r 2 r_2 r2​增为 r 2 e r_2e r2​e。方程变为 { d x 1 d t x 1 [ ( r 1 − e ) − λ 1 x 2 ] d x 2 d t x 2 [ − ( r 2 e ) λ 2 x 1 ] \begin{cases} \frac{dx_1}{dt} x_1 [(r_1 - e) - \lambda_1 x_2] \\ \frac{dx_2}{dt} x_2 [-(r_2 e) \lambda_2 x_1] \end{cases} {dtdx1​​x1​[(r1​−e)−λ1​x2​]dtdx2​​x2​[−(r2​e)λ2​x1​]​ 种群相互竞争模型 如果一个自然环境中存在两个或两个以上的种群它们之间的关系大致可分为以下几种相互竞争相互依存弱肉强食食饵与捕食者也可能毫无关系。弱肉强食我们已经研究过最后一种情形我们不用研究。所以还剩下两种关系这部分我们先来研究两个种群的相互竞争模型在下个部分我们再来研究两个种群的相互依存模型。 考虑单个种群在自然资源有限的环境下生存时我们常用阻滞增长模型来描述它的数量的演变即 d x ( t ) d t r x ( 1 − x N ) \frac{dx(t)}{dt} rx \left(1 - \frac{x}{N}\right) dtdx(t)​rx(1−Nx​), 其中 r r r是增长率 N N N是该环境下能容纳的最大数量。 传染病模型 历史上曾经爆发过多次大范围的传染病例如天花、流感、SARA、猪流感等。 2020年上半年爆发的新冠肺炎具有发病急、传播快、病情重等特点给人们的健康 带来极大的危害对社会的繁荣安定带来严重影响。因此搞清楚传染病的传播过 程、分析其传播特征、传播规律以便避免传染病的暴发、控制传染病的蔓延、最 终消灭传染病是一件非常重要的事。我们可以建立数学模型描述传染病的传播过程、 分析其传播规律、为预测和控制传染病提供信息和支持。要深入区分不同传染病的 不同传播特点需要很多病理学知识。这里我们仅从传染病的一般传播机理出发建 立几种最常用的传染病模型。 (1)易感者(S,Susceptible):潜在的可感染人群 (2)潜伏者(E,Exposed):已被传染但没表现出来的人群 (3)感染者(I,Infected):确诊感染的人 (4)康复者(R,Recovered):已痊愈的感染者体内含抗体。 注意以上分类的命名不唯一例如有的文献将R解释为移出状态(removed),表 示脱离系统不再受到传染病影响的人(痊愈、死亡或被有效隔离的人)。 首先考虑最基本的模型——SI 模型。这里S 是指易感染者(Susceptible) 也就是健 康人I指已感染者(Infective) 也就是患者。在该模型中我们把人群分为易感染者 和已感染者两大类(即健康人和患者)。 假设我们不考虑人口的迁移和生死设总人数为 N N N那么在任意时刻 N S 1 NS1 NS1。接下来我们需要考虑传染病的传播机理这里有两种不同的角度 1假设单位时间内易感染者与已感染者接触且被传染的强度为 β \beta β且单位时间内由易感染者 S S S转换为已感染者 I I I的人数 β S N × I N × N β S I N \beta \frac{S}{N} \times \frac{I}{N} \times N \beta \frac{SI}{N} βNS​×NI​×NβNSI​。那么有 S ( t Δ t ) − S ( t ) − β S ( t ) × I ( t ) N Δ t S(t \Delta t) - S(t) -\beta \frac{S(t) \times I(t)}{N} \Delta t S(tΔt)−S(t)−βNS(t)×I(t)​Δt I ( t Δ t ) − I ( t ) β S ( t ) × I ( t ) N Δ t I(t \Delta t) - I(t) \beta \frac{S(t) \times I(t)}{N} \Delta t I(tΔt)−I(t)βNS(t)×I(t)​Δt。这里我们可以借用高数的知识 S ( t Δ t ) − S ( t ) Δ t − β S ( t ) × I ( t ) N \frac{S(t \Delta t) - S(t)}{\Delta t} -\beta \frac{S(t) \times I(t)}{N} ΔtS(tΔt)−S(t)​−βNS(t)×I(t)​则 lim ⁡ Δ t → 0 S ( t Δ t ) − S ( t ) Δ t − β S × I N \lim_{\Delta t \to 0} \frac{S(t \Delta t) - S(t)}{\Delta t} -\beta \frac{S \times I}{N} limΔt→0​ΔtS(tΔt)−S(t)​−βNS×I​ 接下来我们即可得到对应的微分方程为 { d S d t − β S × I N d I d t β S × I N \begin{cases} \frac{dS}{dt} -\beta \frac{S \times I}{N} \\ \frac{dI}{dt} \beta \frac{S \times I}{N} \end{cases} {dtdS​−βNS×I​dtdI​βNS×I​​ 状态转移图 对于SI模型的扩展 1考虑某种使得参数 β \beta β降低的因素例如禁止大规模聚会、采取隔离措施等 2增加人口自然出生率和死亡率但不考虑疾病的死亡率。假定初始总人口数为 N ( S I ) N(SI) N(SI)疾病流行期间人口出生率和自然死亡率分别为 μ \mu μ和 v v v不考虑因病死亡新增人都是易感染者初始时单位时间内感染人数为 β S I N \beta \frac{SI}{N} βNSI​。 注意由于总人数 N N N不再固定因此我们在后期不断对总人口 N N N进行更新新的总人口 N ′ N N′的计算公式仍为 S I SI SI。其状态转移图形为 对应的微分方程组为 { d S d t − β S × I N ′ u N ′ − ν S d I d t β S × I N ′ − ν I , 且 N ′ S I d N D d t ν S ν I \begin{cases} \frac{dS}{dt} -\beta \frac{S \times I}{N} uN - \nu S \\ \frac{dI}{dt} \beta \frac{S \times I}{N} - \nu I, \quad \text{且} \; N S I \\ \frac{dND}{dt} \nu S \nu I \end{cases} ⎩ ⎨ ⎧​dtdS​−βN′S×I​uN′−νSdtdI​βN′S×I​−νI,且N′SIdtdND​νSνI​ 3不考虑人口自然出生率和死亡率只考虑疾病的死亡率假定因病的死亡率为 d d d不考虑人口自然出生率和死亡率。其状态转移图形为 对应的微分方程组为 { d S d t − β S × I N ′ d I d t β S × I N ′ − d I , 且 N ′ S I d I D d t d I 对应的微分方程组为 \begin{cases} \frac{dS}{dt} -\beta \frac{S \times I}{N} \\ \frac{dI}{dt} \beta \frac{S \times I}{N} - dI , \quad \text{且} \; N S I \\ \frac{dID}{dt} dI \end{cases} 对应的微分方程组为⎩ ⎨ ⎧​dtdS​−βN′S×I​dtdI​βN′S×I​−dI,且N′SIdtdID​dI​ 4同时考虑人口自然出生率和死亡率和疾病的死亡率疾病流行期间人口出生率和自然死亡率分别为 μ \mu μ和 v v v因病的死亡率为 d d d其状态转移图形为 对应的微分方程组为 { d S d t − β S × I N ′ u N ′ − ν S d I d t β S × I N ′ − d I − ν I , 且 N ′ S I d I D d t d I d N D d t ν S ν I 对应的微分方程组为 \begin{cases} \frac{dS}{dt} -\beta \frac{S \times I}{N} uN - \nu S \\ \frac{dI}{dt} \beta \frac{S \times I}{N} - dI - \nu I , \quad \text{且} \; N S I \\ \frac{dID}{dt} dI \\ \frac{dND}{dt} \nu S \nu I \end{cases} 对应的微分方程组为⎩ ⎨ ⎧​dtdS​−βN′S×I​uN′−νSdtdI​βN′S×I​−dI−νI,且N′SIdtdID​dIdtdND​νSνI​ 某些疾病容易被治愈但是却容易发生变异例如流感病毒。
假设从某种疾病恢复后仍不能产生抗体即未来仍可能患病即我们可能会经历感染恢复为易感者再感染不断循环下去的过程。
我们可以建立SIS模型来描述这一过程假定总人口数为 N N N,且不考虑因病死亡和自然出生死亡单位时间内感染人数为 β S I N \beta\frac{SI}{N} βNSI​,由感染状态 I I I恢复为易感者状态 S S S的恢复率为 a a a.其状态转移图形为: 对应的微分方程组为 { d S d t α I − β S × I N d I d t β S × I N − α I 对应的微分方程组为 \begin{cases} \frac{dS}{dt} \alpha I - \beta \frac{S \times I}{N} \\ \frac{dI}{dt} \beta \frac{S \times I}{N} - \alpha I \end{cases} 对应的微分方程组为{dtdS​αI−βNS×I​dtdI​βNS×I​−αI​ 数值求解类 元胞自动机 元胞自动机的定义 元胞自动机CA是一种应用比较广泛的模型理论由冯·诺依曼创始经数学家Conway、物理学家Wolfram等人的贡献后迅速发展。在物理学定义上元胞自动机指的是定义在一个由具有离散、有限状态的元胞组成的元胞空间上按照一定的局部规则在离散的时间维度上演化的动力学系统。在数学定义上从不同的角度有着基于集合论的定义和拓扑学的定义简单起见在此不做阐述。 元胞自动机CA是一种时间、空间、状态都离散空间相互作用和时间因果关系为局部的网格动力学模型具有模拟复杂系统时空烟花过程的能力。 元胞自动机的组成 元胞又称细胞、单元或者基元是元胞自动机最基本的组成部分。元胞分布在离散的欧几里得空间位置上每个时刻有着离散的状态如{0,1}等。 元胞空间元胞所分布在欧几里得空间上的网格点的集合。最常见的为二维元胞空间通常可按三角形、四边形和六边形三种网格排列。 邻居元胞自动机的演化规则是局部的对于指定元胞的状态进行更新时只需要知道其临近元胞的状态。某一元胞状态更新时要搜索的空间域叫做该元胞的邻居。 邻居的划分在四方网格划分下的二维元胞自动机的邻居通常有以下几种形式 Von Neuman型 Moore型 expend Moore型 边界条件 实际模拟元胞自动机的演化时不可能处理无限网络系统必须是有边界的。处理边界格点时可以为边界的信息进行编码由此选择不同的演化规则。另一种方法是在边界处扩展以满足边界有与内部类似的邻居。 周期型边界 周期型是指相对边界连接起来的元胞空间。这种空间与无限空间最为接近进行理论探讨时常以此类空间作为实验进行模拟。 固定边界 所有边界外元胞均取某一固定常量。 绝热边界 边界外元胞的状态始终和边界元胞的状态保持一致。 演化规则 根据元胞当前状态及其邻居状态确定下一时刻该元胞状态的动力学函数。 元胞自动机的特征 标准的元胞自动机具有以下几个特征 1同质性、齐性同质性反映在元胞空间内的每个元胞都服从相同的规则齐性指的是元胞的分布方式相同大小形状相同空间分布整齐。 2空间离散元胞分布在按一定规则划分的离散的元胞空间上。 3时间离散系统的演化是按等时间间隔分步进行的。 t t t时刻的状态只对 t 1 t1 t1时刻的状态产生影响。 4状态离散、有限元胞自动机的状态参量只能取有限个离散值。 5同步计算并行性元胞自动机的处理是同步进行的。 6时空局域性每个元胞在 t 1 t1 t1时刻的状态取决于其邻居的元胞在t时刻的状态。 7维数高动力系统中一般将变量的个数成为维数。任何完备元胞自动机的元胞空间是在空间上的无穷集每个元胞的状态是这个动力学系统的变量因此元胞自动机是一类无穷维动力系统。 应用 通过简单的规则展示了复杂系统的动态行为和模式生成能力。 常见应用领域 1.流体动力学模拟 2.交通流模拟 3.城市发展与土地利用模型 4.生物进化模拟 5.生态系统和种群动态模拟 6.火灾传播模型 7.传染病传播模拟 牛顿-拉夫逊算法NRBO 牛顿-拉夫逊优化算法(Newton-Raphson-based optimizer, NBRO)是一种新型的元启发式算法智能优化算法该成果由Sowmya等人于2024年2月发表在中科院2区Top SCI期刊《Engineering Applications of Artificial Intelligence》上。 注意如果使用该算法记得引用该论文 原理简介 所提出的NRBO通过使用几个向量集和两个算子如NRSR和TAO来探索搜索域应用NRM来发现搜索区域从而定义搜索路径。 种群初始化 与其他元启发式算法一样NRBO通过在候选解的边界内产生初始随机种群来启动对最优解的搜索。基于存在Np个种群的事实并且每个种群由模糊决策变量/向量组成。因此使用公式(7)生成随机种群 x j n l b r a n d × ( u b − l b ) , n 1 , 2 , … , N p , and j 1 , 2 , … , d i m x_{j}^{n} lb rand \times (ub - lb), \quad n 1, 2, \ldots, N_{p}, \quad \text{and} \quad j 1, 2, \ldots, dim xjn​lbrand×(ub−lb),n1,2,…,Np​,andj1,2,…,dim 其中 x i j x_{ij} xij​表示第 n n n个总体的第j个维度的位置rand表示(0,1)之间的随机数。公式(8)给出了可以描绘所有维度的种群的种群矩阵 X n [ x 1 1 x 1 2 ⋯ x 1 d i m x 2 1 x 2 2 ⋯ x 2 d i m ⋮ ⋮ ⋱ ⋮ x N p 1 x N p 2 ⋯ x N p d i m ] N p × d i m \begin{equation} X_{n} \begin{bmatrix} x_{1}^{1} x_{1}^{2} \cdots x_{1}^{dim} \\ x_{2}^{1} x_{2}^{2} \cdots x_{2}^{dim} \\ \vdots \vdots \ddots \vdots \\ x_{N_{p}}^{1} x_{N_{p}}^{2} \cdots x_{N_{p}}^{dim} \end{bmatrix}_{N_{p} \times dim} \end{equation} Xn​ ​x11​x21​⋮xNp​1​​x12​x22​⋮xNp​2​​⋯⋯⋱⋯​x1dim​x2dim​⋮xNp​dim​​ ​Np​×dim​​​ Newton-Raphson搜索规则NRSR 矢量由NRSR控制允许种群更准确地探索可行区域并获得更好的位置。NRSR是基于NRM的概念即提出NRM是为了促进勘探趋势并加快收敛。由于许多优化技术是不可微的因此在这种情况下使用数学NRM来代替函数的显式公式。NRM从一个假定的初始解开始并沿着一个确定的方向前进到下一个位置。为了从中公式(5)中获取NRSR必须使用TS来确定二阶导数。 f ( x − Δ x ) f(x− \Delta x) f(x−Δx)和 f ( x Δ x ) f(x \Delta x) f(xΔx)的TS如下所示 f ( x Δ x ) f ( x ) f ′ ( x 0 ) Δ x 1 2 ! f ′ ′ ( x 0 ) Δ x 2 1 3 ! f ′ ′ ′ ( x 0 ) Δ x 3 ⋯ f ( x − Δ x ) f ( x ) − f ′ ( x 0 ) Δ x 1 2 ! f ′ ′ ( x 0 ) Δ x 2 − 1 3 ! f ′ ′ ′ ( x 0 ) Δ x 3 ⋯ \begin{align} f(x\Delta x) f(x) f(x_0)\Delta x \frac{1}{2!}f(x_0)\Delta x^2 \frac{1}{3!}f(x_0)\Delta x^3 \cdots \\ f(x-\Delta x) f(x) - f(x_0)\Delta x \frac{1}{2!}f(x_0)\Delta x^2 - \frac{1}{3!}f(x_0)\Delta x^3 \cdots \end{align} f(xΔx)f(x−Δx)​f(x)f′(x0​)Δx2!1​f′′(x0​)Δx23!1​f′′′(x0​)Δx3⋯f(x)−f′(x0​)Δx2!1​f′′(x0​)Δx2−3!1​f′′′(x0​)Δx3⋯​​ 通过减去/加上公式(9)和公式(10)得出 f ′ ( x ) f(x) f′(x)和 f ′ ( x ) f(x) f′(x)的表达式如下 f ′ ( x ) f ( x Δ x ) − f ( x − Δ x ) 2 Δ x f ′ ′ ( x ) f ( x Δ x ) f ( x − Δ x ) − 2 f ( x ) Δ x 2 \begin{align} f(x) \frac{f(x\Delta x) - f(x-\Delta x)}{2\Delta x} \\ f(x) \frac{f(x\Delta x) f(x-\Delta x) - 2f(x)}{\Delta x^2} \end{align} f′(x)f′′(x)​2Δxf(xΔx)−f(x−Δx)​Δx2f(xΔx)f(x−Δx)−2f(x)​​​ 代入公式(5)中的公式(11)和公式(12)更新的根位置被重写如下 x n 1 x n − ( f ( x n Δ x ) − f ( x n − Δ x ) ) × Δ x 2 × ( f ( x n Δ x ) f ( x n − Δ x ) − 2 × f ( x n ) ) \begin{equation} x_{n1} x_{n} - \frac{(f(x_{n} \Delta x) - f(x_{n} - \Delta x)) \times \Delta x}{2 \times (f(x_{n} \Delta x) f(x_{n} - \Delta x) - 2 \times f(x_{n}))} \end{equation} xn1​xn​−2×(f(xn​Δx)f(xn​−Δx)−2×f(xn​))(f(xn​Δx)−f(xn​−Δx))×Δx​​​ 考虑到NRSR应该是NRBO的主要组成部分有必要进行某些调整以管理种群搜索作为公式(13)的结果。彼此相邻的x的位置分别用 x n Δ x x_n\Delta x xn​Δx和 x n − Δ x x_n− \Delta x xn​−Δx表示如图2所示。NRBO将这对相邻位置转换为种群中的另外两个向量。因为 f ( x n ) f(x_n) f(xn​)是一个最小化问题如图2所示。位置 x n Δ x x_n\Delta x xn​Δx的适应度值比位置 x x x差而位置 x n − Δ x x_n-\Delta x xn​−Δx的适合度比位置 x n x_n xn​大。因此NRBO替换位置 X b X_b Xb​的位置 x n − Δ x x_n-\Delta x xn​−Δx位置 X b X_b Xb​在其邻域中具有比位置 x n x_n xn​更好的位置而位置 x n Δ x x_n\Delta x xn​Δx被 X w X_w Xw​的位置替换位置 X w X_w Xw​在其邻域内具有比位置 x n x_n xn​更差的位置。这个方法的另一个优点是它使用位置 x n x_n xn​而不是其适应度 f ( x n ) f(x_n) f(xn​)这节省了计算时间。因此NRSR表示如下 NRSR randn × ( X w − X b ) × Δ x 2 × ( X w X b − 2 × x n ) \begin{equation} \text{NRSR} \text{randn} \times \frac{(X_w - X_b) \times \Delta x}{2 \times (X_w X_b - 2 \times x_n)} \end{equation} NRSRrandn×2×(Xw​Xb​−2×xn​)(Xw​−Xb​)×Δx​​​ 其中randn表示均值为0、方差为1的正态分布随机数 X w X_w Xw​表示最差位置 X b X_b Xb​表示最佳位置。等式14可以通过用当前解决方案来辅助更新其位置来增强当前解决方案。等式14具有随机参数以增加NRBO的搜索能力并更好地平衡开发和探索能力。 根据经验所提出的算法必须能够在多样性和聚集性之间达到平衡以便在搜索空间中发现最优解并最终收敛到全局解。可以通过应用一个称为 δ \delta δ的自适应系数来增强算法。 δ \delta δ的表达式如公式(15)所示 δ ( 1 − ( 2 × I T M a x _ I T ) ) 5 \delta \left(1 - \left(\frac{2 \times IT}{Max\_IT}\right)\right)^5 δ(1−(Max_IT2×IT​))5 其中 I T IT IT表示当前迭代而 M a x I T Max IT MaxIT表示迭代的最大次数。为了在勘探和开发阶段之间保持平衡参数 δ \delta δ在迭代过程中会自行调整。图3说明了每次迭代过程中 δ \delta δ的变化。根据公式(15) δ \delta δ的值在1到−1之间变化。 与自适应参数 δ \delta δ一起所提出的NRSR通过考虑优化过程中的随机动作、增加多样性和避免局部最优来改进NRBO同时显著减少迭代次数。公式(14)中 Δ x \Delta x Δx的表达式如公式(16)所示 Δ x r a n d ( 1 , d i m ) × ∣ X b − X n I T ∣ \Delta x rand(1, dim) \times \left| X_b - X_n^{IT} \right| Δxrand(1,dim)× ​Xb​−XnIT​ ​ 其中 X b X_b Xb​表示迄今为止获得的最佳解rand(1,dim)是具有dim维度决策变量的随机数。现在通过考虑NRSR来修改公式(13)并重写如下 x n 1 x n − N R S R x_{n1} x_n - NRSR xn1​xn​−NRSR 接着通过包括另一个称为 ρ \rho ρ的参数来改进所提出的NRBO的利用该参数将种群引导到正确的方向。ρ的表达式如下所示。 ρ a × ( X b − X n I T ) b × ( X r 1 I T − X r 2 I T ) \rho a \times \left( X_b - X_n^{IT} \right) b \times \left( X_{r_1}^{IT} - X_{r_2}^{IT} \right) ρa×(Xb​−XnIT​)b×(Xr1​IT​−Xr2​IT​) 其中 a a a和 b b b是(0,1)之间的随机数 r 1 r_1 r1​和 r 2 r_2 r2​是从总体中随机选择的不同整数。然而 r 1 r_1 r1​和 r 2 r_2 r2​的值不相等。矢量的当前位置 X n I T X_n^{IT} XnIT​已经由公式(19)更新 X n I T x n I T − ( r a n d n × ( X w − X b ) × Δ x 2 × ( X w X b − 2 × X n ) ) ( a × ( X b − X n I T ) ) b × ( X r 1 I T − X r 2 I T ) X_n^{IT} x_n^{IT} - \left( randn \times \frac{(X_w - X_b) \times \Delta x}{2 \times (X_w X_b - 2 \times X_n)} \right) \left( a \times (X_b - X_n^{IT}) \right) b \times \left( X_{r_1}^{IT} - X_{r_2}^{IT} \right) XnIT​xnIT​−(randn×2×(Xw​Xb​−2×Xn​)(Xw​−Xb​)×Δx​)(a×(Xb​−XnIT​))b×(Xr1​IT​−Xr2​IT​) 其中 X 1 n I T X1^{IT}_n X1nIT​是通过更新 x n I T x^{IT}_n xnIT​而得到的新矢量位置。NRSR是由NRM进一步改进并且公式(13)被修改和重写如下 NRSR r a n d n × ( y w − y b ) × Δ x 2 × ( y w y b − 2 × x n ) y w r 1 × ( Mean ⁡ ( Z n 1 x n ) r 1 × Δ x ) y b r 1 × ( Mean ⁡ ( Z n 1 x n ) − r 1 × Δ x ) Z n 1 x n − r a n d n × ( X w − X b ) × Δ x 2 × ( X w X b − 2 × x n ) \begin{align} \text{NRSR} randn \times \frac{(y_w - y_b) \times \Delta x}{2 \times (y_w y_b - 2 \times x_n)} \\ y_w r_1 \times \left( \operatorname{Mean}(Z_{n1} x_n) r_1 \times \Delta x \right) \\ y_b r_1 \times \left( \operatorname{Mean}(Z_{n1} x_n) - r_1 \times \Delta x \right) \\ Z_{n1} x_n - randn \times \frac{(X_w - X_b) \times \Delta x}{2 \times (X_w X_b - 2 \times x_n)} \end{align} NRSRyw​yb​Zn1​​randn×2×(yw​yb​−2×xn​)(yw​−yb​)×Δx​r1​×(Mean(Zn1​xn​)r1​×Δx)r1​×(Mean(Zn1​xn​)−r1​×Δx)xn​−randn×2×(Xw​Xb​−2×xn​)(Xw​−Xb​)×Δx​​​ 其中 y w y_w yw​和 y b y_b yb​是使用 Z n 1 Z_{n1} Zn1​和 x n x_n xn​生成的两个向量的位置 r 1 r_1 r1​表示(0,1)之间的随机数。NRSR的增强版本如公式(20)所示。使用公式(20)之后公式(19)被更新如下 X n I T x n I T − ( r a n d n × ( y w − y b ) × Δ x 2 × ( y w y b − 2 × x n ) ) ( a × ( X b − X n I T ) ) b × ( X r 1 I T − X r 2 I T ) \begin{equation} X_n^{IT} x_n^{IT} - \left( randn \times \frac{(y_w - y_b) \times \Delta x}{2 \times (y_w y_b - 2 \times x_n)} \right) \left( a \times (X_b - X_n^{IT}) \right) b \times \left( X_{r_1}^{IT} - X_{r_2}^{IT} \right) \end{equation} XnIT​xnIT​−(randn×2×(yw​yb​−2×xn​)(yw​−yb​)×Δx​)(a×(Xb​−XnIT​))b×(Xr1​IT​−Xr2​IT​)​​ 有必要通过用等公式(24)中的当前矢量 x n I T x_n^{IT} xnIT​的位置代替最佳矢量 X b X_b Xb​的位置来构造新矢量 X 2 n I T X2^{IT}_n X2nIT​ X 2 n I T X b − ( r a n d n × ( y w − y b ) × Δ x 2 × ( y w y b − 2 × x n ) ) ( a × ( X b − X n I T ) ) b × ( X r 1 I T − X r 2 I T ) \begin{equation} X2_n^{IT} X_b - \left( randn \times \frac{(y_w - y_b) \times \Delta x}{2 \times (y_w y_b - 2 \times x_n)} \right) \left( a \times (X_b - X_n^{IT}) \right) b \times \left( X_{r_1}^{IT} - X_{r_2}^{IT} \right) \end{equation} X2nIT​Xb​−(randn×2×(yw​yb​−2×xn​)(yw​−yb​)×Δx​)(a×(Xb​−XnIT​))b×(Xr1​IT​−Xr2​IT​)​​ 开发阶段是这一搜索方向策略的主要重点。当涉及到局部搜索时公式(25)提出的搜索方法是有益的但当涉及到全局搜索时它有局限性而公式(24)给出的搜索策略对于全局搜索是有益的但对于局部搜索有局限性。因此NRBO同时使用公式(24)和(25)来改善多样化和强化阶段。下一次迭代期间的新位置矢量用公式(26)、(27)表示 x n I T 1 r 2 × ( r 2 × X 1 n I T ( 1 − r 2 ) × X 2 n I T ) ( 1 − r 2 ) × X 3 n I T X 3 n I T X n I T − δ × ( X 2 n I T − X 1 n I T ) \begin{align} x_n^{IT1} r_2 \times \left( r_2 \times X1_n^{IT} (1 - r_2) \times X2_n^{IT} \right) (1 - r_2) \times X3_n^{IT} \\ X3_n^{IT} X_n^{IT} - \delta \times \left( X2_n^{IT} - X1_n^{IT} \right) \end{align} xnIT1​X3nIT​​r2​×(r2​×X1nIT​(1−r2​)×X2nIT​)(1−r2​)×X3nIT​XnIT​−δ×(X2nIT​−X1nIT​)​​ 其中 r 2 r_2 r2​表示(0,1)之间的随机数。 陷阱规避操作TAO 纳入TAO是为了提高建议的NRBO处理现实世界问题的有效性。TAO是采用Ahmadianfar等人提出的改进和增强运算公式。使用TAO可以显著改变 x n I T 1 x^{IT1}_n xnIT1​的位置。它通过组合最佳位置 X b X_b Xb​和当前矢量位置 X n I T X^{IT}_n XnIT​来产生具有增强质量XITTAO的解决方案。如果rand的值小于 D F DF DF则使用如下公式产生解XITTAO X T A O I T { X n I T 1 θ 1 × ( μ 1 × x b − μ 2 × X n I T ) θ 2 × δ × ( μ 1 × Mean ⁡ ( X I T ) − μ 2 × X n I T ) , if  μ 1 0.5 x b θ 1 × ( μ 1 × x b − μ 2 × X n I T ) θ 2 × δ × ( μ 1 × Mean ⁡ ( X I T ) − μ 2 × X n I T ) , Otherwise \begin{equation} X_{TAO}^{IT} \begin{cases} X_{n}^{IT1} \theta_1 \times \left( \mu_1 \times x_b - \mu_2 \times X_{n}^{IT} \right) \theta_2 \times \delta \times \left( \mu_1 \times \operatorname{Mean}(X^{IT}) - \mu_2 \times X_{n}^{IT} \right), \text{if } \mu_1 0.5 \\ x_b \theta_1 \times \left( \mu_1 \times x_b - \mu_2 \times X_{n}^{IT} \right) \theta_2 \times \delta \times \left( \mu_1 \times \operatorname{Mean}(X^{IT}) - \mu_2 \times X_{n}^{IT} \right), \text{Otherwise} \end{cases} \end{equation} XTAOIT​{XnIT1​θ1​×(μ1​×xb​−μ2​×XnIT​)θ2​×δ×(μ1​×Mean(XIT)−μ2​×XnIT​),xb​θ1​×(μ1​×xb​−μ2​×XnIT​)θ2​×δ×(μ1​×Mean(XIT)−μ2​×XnIT​),​if μ1​0.5Otherwise​​​ ​ X n I T 1 X T A O I T \begin{equation} X_n^{IT1} X_{TAO}^{IT} \end{equation} XnIT1​XTAOIT​​​ 其中rand表示(0,1)之间的均匀随机数 θ 1 \theta_1 θ1​和 θ 2 \theta_2 θ2​分别是(−1,1)和(−0.5,0.5)之间的一致随机数 D F DF DF表示控制NRBO性能的决定因素 μ 1 \mu_1 μ1​和 μ 2 \mu_2 μ2​是随机数分别由公式(31)和(32)生成: μ 1 β × 3 × r a n d ( 1 − β ) μ 2 β × r a n d ( 1 − β ) \begin{align} \mu_1 \beta \times 3 \times rand (1 - \beta) \\ \mu_2 \beta \times rand (1 - \beta) \end{align} μ1​μ2​​β×3×rand(1−β)β×rand(1−β)​​ 其中 β \beta β表示二进制数即1或0rand表示随机数。如果 Δ \Delta Δ的值大于或等于0.5则 β \beta β的值为0否则该值为1。由于参数 μ 1 \mu_1 μ1​和 μ 2 \mu_2 μ2​选择的随机性种群变得更加多样化并逃离局部最优解这有助于提高其多样性。与NRBO类似GBO也受到牛顿方法的启发。因此NRBO概念看起来可能与GBO相似但由于NRBO的独特特性其性能仍远优于GBO 流程图 伪代码 常见应用 工程中的非线性方程求解 在工程设计中经常需要求解非线性方程。例如在结构工程中可能需要计算梁在特定载荷下的变形这涉及到非线性材料特性和几何非线性方程的求解。 计算机图形学中的光线追踪 在光线追踪算法中需要计算光线与复杂曲面如多项式曲面之间的交点。这通常涉及求解非线性方程组牛顿-拉夫逊算法可以高效地逼近这些交点从而渲染出真实感的图像。 金融工程中的期权定价 在金融工程中Black-Scholes模型用于期权定价时有时需要反解模型中的参数如隐含波动率。牛顿-拉夫逊算法可以用来求解隐含波动率使得理论期权价格与市场价格相匹配。 优化问题 在许多优化问题中尤其是涉及到寻找函数极值点的问题牛顿-拉夫逊算法可以用来快速找到极值点。比如在机器学习中的最优化算法中用于训练神经网络的权重更新。 电力系统分析 在电力系统中电力流分析需要求解一组非线性方程以确定系统中电压和电流的分布。牛顿-拉夫逊算法被广泛应用于电力流计算帮助电力工程师分析和优化电力传输。 化学反应动力学 在化学工程中化学反应的动力学方程通常是非线性的。牛顿-拉夫逊算法可以用来求解这些方程帮助工程师设计反应器和优化反应条件。 机器人运动规划 在机器人学中运动规划问题涉及求解机器人的位置和角度通常需要求解非线性方程组。牛顿-拉夫逊算法可以用来求解这些方程从而规划机器人的路径。 本质是求解非线性方程组。它是一种迭代方法通过逐步逼近来找到方程的根。该算法不仅适用于单个非线性方程的求解也适用于多变量非线性方程组的求解。 27)表示 x n I T 1 r 2 × ( r 2 × X 1 n I T ( 1 − r 2 ) × X 2 n I T ) ( 1 − r 2 ) × X 3 n I T X 3 n I T X n I T − δ × ( X 2 n I T − X 1 n I T ) \begin{align} x_n^{IT1} r_2 \times \left( r_2 \times X1_n^{IT} (1 - r_2) \times X2_n^{IT} \right) (1 - r_2) \times X3_n^{IT} \\ X3_n^{IT} X_n^{IT} - \delta \times \left( X2_n^{IT} - X1_n^{IT} \right) \end{align} xnIT1​X3nIT​​r2​×(r2​×X1nIT​(1−r2​)×X2nIT​)(1−r2​)×X3nIT​XnIT​−δ×(X2nIT​−X1nIT​)​​ 其中 r 2 r_2 r2​表示(0,1)之间的随机数。 陷阱规避操作TAO 纳入TAO是为了提高建议的NRBO处理现实世界问题的有效性。TAO是采用Ahmadianfar等人提出的改进和增强运算公式。使用TAO可以显著改变 x n I T 1 x^{IT1}_n xnIT1​的位置。它通过组合最佳位置 X b X_b Xb​和当前矢量位置 X n I T X^{IT}_n XnIT​来产生具有增强质量XITTAO的解决方案。如果rand的值小于 D F DF DF则使用如下公式产生解XITTAO X T A O I T { X n I T 1 θ 1 × ( μ 1 × x b − μ 2 × X n I T ) θ 2 × δ × ( μ 1 × Mean ⁡ ( X I T ) − μ 2 × X n I T ) , if  μ 1 0.5 x b θ 1 × ( μ 1 × x b − μ 2 × X n I T ) θ 2 × δ × ( μ 1 × Mean ⁡ ( X I T ) − μ 2 × X n I T ) , Otherwise \begin{equation} X_{TAO}^{IT} \begin{cases} X_{n}^{IT1} \theta_1 \times \left( \mu_1 \times x_b - \mu_2 \times X_{n}^{IT} \right) \theta_2 \times \delta \times \left( \mu_1 \times \operatorname{Mean}(X^{IT}) - \mu_2 \times X_{n}^{IT} \right), \text{if } \mu_1 0.5 \\ x_b \theta_1 \times \left( \mu_1 \times x_b - \mu_2 \times X_{n}^{IT} \right) \theta_2 \times \delta \times \left( \mu_1 \times \operatorname{Mean}(X^{IT}) - \mu_2 \times X_{n}^{IT} \right), \text{Otherwise} \end{cases} \end{equation} XTAOIT​{XnIT1​θ1​×(μ1​×xb​−μ2​×XnIT​)θ2​×δ×(μ1​×Mean(XIT)−μ2​×XnIT​),xb​θ1​×(μ1​×xb​−μ2​×XnIT​)θ2​×δ×(μ1​×Mean(XIT)−μ2​×XnIT​),​if μ1​0.5Otherwise​​​ ​ X n I T 1 X T A O I T \begin{equation} X_n^{IT1} X_{TAO}^{IT} \end{equation} XnIT1​XTAOIT​​​ 其中rand表示(0,1)之间的均匀随机数 θ 1 \theta_1 θ1​和 θ 2 \theta_2 θ2​分别是(−1,1)和(−0.5,0.5)之间的一致随机数 D F DF DF表示控制NRBO性能的决定因素 μ 1 \mu_1 μ1​和 μ 2 \mu_2 μ2​是随机数分别由公式(31)和(32)生成: μ 1 β × 3 × r a n d ( 1 − β ) μ 2 β × r a n d ( 1 − β ) \begin{align} \mu_1 \beta \times 3 \times rand (1 - \beta) \\ \mu_2 \beta \times rand (1 - \beta) \end{align} μ1​μ2​​β×3×rand(1−β)β×rand(1−β)​​ 其中 β \beta β表示二进制数即1或0rand表示随机数。如果 Δ \Delta Δ的值大于或等于0.5则 β \beta β的值为0否则该值为1。由于参数 μ 1 \mu_1 μ1​和 μ 2 \mu_2 μ2​选择的随机性种群变得更加多样化并逃离局部最优解这有助于提高其多样性。与NRBO类似GBO也受到牛顿方法的启发。因此NRBO概念看起来可能与GBO相似但由于NRBO的独特特性其性能仍远优于GBO 流程图 伪代码 常见应用 工程中的非线性方程求解 在工程设计中经常需要求解非线性方程。例如在结构工程中可能需要计算梁在特定载荷下的变形这涉及到非线性材料特性和几何非线性方程的求解。 计算机图形学中的光线追踪 在光线追踪算法中需要计算光线与复杂曲面如多项式曲面之间的交点。这通常涉及求解非线性方程组牛顿-拉夫逊算法可以高效地逼近这些交点从而渲染出真实感的图像。 金融工程中的期权定价 在金融工程中Black-Scholes模型用于期权定价时有时需要反解模型中的参数如隐含波动率。牛顿-拉夫逊算法可以用来求解隐含波动率使得理论期权价格与市场价格相匹配。 优化问题 在许多优化问题中尤其是涉及到寻找函数极值点的问题牛顿-拉夫逊算法可以用来快速找到极值点。比如在机器学习中的最优化算法中用于训练神经网络的权重更新。 电力系统分析 在电力系统中电力流分析需要求解一组非线性方程以确定系统中电压和电流的分布。牛顿-拉夫逊算法被广泛应用于电力流计算帮助电力工程师分析和优化电力传输。 化学反应动力学 在化学工程中化学反应的动力学方程通常是非线性的。牛顿-拉夫逊算法可以用来求解这些方程帮助工程师设计反应器和优化反应条件。 机器人运动规划 在机器人学中运动规划问题涉及求解机器人的位置和角度通常需要求解非线性方程组。牛顿-拉夫逊算法可以用来求解这些方程从而规划机器人的路径。 本质是求解非线性方程组。它是一种迭代方法通过逐步逼近来找到方程的根。该算法不仅适用于单个非线性方程的求解也适用于多变量非线性方程组的求解。
http://www.hkea.cn/news/14425126/

相关文章：

  • 家谱网站的首页怎么做装修案例英文
  • 怎么自己创建一个网站手机合肥做网站怎么样
  • 如何做vip视频网站在线制作app平台
  • 腾讯做网站建筑施工企业专职安全生产管理员
  • dedecms可以做双语网站室内设计效果图客厅
  • 每一天做网站广西建设厅网站
  • 三亚网站建设哪家专业店名logo设计在线生成免费
  • 资料查询网站怎么做庄河做网站
  • 随州网站设计开发服务wordpress修改网站名称
  • 网站要怎么上传网站维护上海
  • 锦江区建设和交通局网站流感吃什么药更好
  • 网站建设的具体步骤做网站哪家好 青岛
  • 网站建设营销公司北京网站建设 知乎
  • 网站设计团队开网店咨询
  • 企业门户网站的设计 流程图淘宝客推广平台
  • 怎么样制作自己的网站visual composer wordpress 汉化
  • 郑州企业建站网站上海网站如何制作
  • 手机网站建站工作室网络广告公司怎么做
  • 怀化网站优化联系方式seo排名优化app
  • 做网站引流到天猫网站服务器租用一年多少钱啊
  • 兴义市网站建设网站收录量是什么意思
  • 网站自助建站系统做介绍英文网站
  • 阿里巴巴网站是用什么技术做的练手网站开发
  • 如何建设网站wap版网站建设方案
  • 网站建设主流开发语言来几个好看的网站
  • 北京网站制作网络推广公司手机html网页制作
  • 厦门创意网站建设网站开发需要注册账户吗
  • 设计素材网站0中国建设银行北京天竺支行网站
  • 龙岗公司网站网站开发主要创新点
  • 做食品企业网站的费用李勇seo的博客