机器学习与大数据技术第二章-机器学习的理论与方法课件.pptx

1、机器学习与大数据技术作者：牟少敏教授第二章p回归分析与最小二乘法p聚类p遗传算法p蚁群算法机器学习的理论与方法p粒子群算法p支持向量机p隐马尔科夫模型p人工神经网络创新与贡献研究意义选题背景第二章机器学习则是研究机器模仿人类的学习过程，进行知识和技能获取，是一门涉及到计算机科学与技术、概率论与统计学和认知科学等多个领域的交叉学科。学习是人类区别于低级动物，自身所具有的重要智能行为。其应用十分广泛，如：数据挖掘、计算机视觉、自然语言处理、语音和手写识别和机器人研发等各个领域。分类问题：在有监督学习任务中，预测变量为离散变量。创新与贡献研究意义选题背景第二章2.1回归分析与最小二乘法回归问题：在有

2、监督学习任务中，预测变量为连续变量。回归分析是一种用于确定两种或两种以上变量间相互依赖关系的统计分析方法。按照问题所涉及变量的多少，可将回归分析分为一元回归分析和多元回归分析。按照自变量与因变量之间是否存在线性关系，分为线性回归分析和非线性回归分析。如果在某个回归分析问题中，只有两个变量，一个自变量和一个因变量，且自变量与因变量之间的函数关系能够用一条直线来近似表示，那么称其为一元线性回归分析。创新与贡献研究意义选题背景第一章2.1回归分析与最小二乘法回归分析的基本步骤如下：创新与贡献研究意义选题背景第二章2.1回归分析与最小二乘法p 分析预测目标，确定自变量和因变量；p 建立合适的回归预测模

3、型；p 相关性分析；p 检测回归预测模型，计算预测的误差；p 计算并确定预测值。最小二乘法又称为最小平方法，是一种常用的数学优化方法。最小二乘法的原理是通过最小化误差平方和寻找与数据匹配的最佳函数。最小二乘法的应用十分广泛，既可以用于参数估计，也可以用于曲线拟合，以及一些其他的优化问题。创新与贡献研究意义选题背景第二章2.1回归分析与最小二乘法创新与贡献研究意义选题背景第二章 对于一元线性回归模型，假设从总体中获取了组观察值，其中。那么这组观察值在二维平面直角坐标系中对应的就是平面中的个点，此时有无数条曲线可以拟合这个点。通常情况下，希望回归函数能够尽可能好地拟合这组值。综合来看，当这条直线位

4、于样本数据的中心位置时似乎最合理。因此，选择最佳拟合曲线的标准可确定为：总拟合误差（即总残差）最小。对于总拟合误差，有三个标准可供选择：（1）用“残差和”表示总拟合误差，但“残差和”会出现相互抵消的问题。（2）用“残差绝对值”表示总拟合误差，但计算绝对值相对来说较为麻烦。（3）用“残差平方和”表示总拟合误差。最小二乘法采用的就是“残差平方和最小”所确定的直线。用“残差平方和”计算方便，而且对异常值会比较敏感。2.1回归分析与最小二乘法创新与贡献研究意义选题背景第二章假设回归模型（拟合函数）为：则样本的误差为：其中 为 的预测值（拟合值），为 对应的实际值。最小二乘法的损失函数 也就是残差平方和

5、，即：通过最小化来确定直线方程，即确定和，此时该问题变成了求函数的极值的问题。根据高等数学的知识可知，极值通常是通过令导数或者偏导数等于0而得到，因此，求关于未知参数和的偏导数：2.1回归分析与最小二乘法01()iif xx01()iiiiieyf xyx()ifxixiyixQ22201111()nnniiiiiiiiQeyf xyx创新与贡献研究意义选题背景第二章通过令偏导数为0，可求解函数的极值点，即：2.1回归分析与最小二乘法 0110011121020niiiniiiiQyxQyxx 2022122iiiiiiiiiiiiixyxx ynxxnx yxynxx 将样本数据 代入，即可

6、得到 和 的具体指。(,)1,2,iiXYin01创新与贡献研究意义选题背景第二章2.2.1 简介作为一种无监督机器学习方法，聚类经常用于数据挖掘和模式识别。2.2 聚类聚类（Cluster Analysis）是将数据集中的所有样本根据相似度的大小进行划分，形成两个或多个类（簇）的过程。簇是数据集中相似的样本集合。聚类没有训练过程，是一种无标准的学习，同时也是一种无监督学习。创新与贡献研究意义选题背景第二章分类的根本区别在于：分类是需要有标号的样本进行训练。2.2 聚类聚类算法可分为：基于划分方法的、基于层次方法的、基于密度方法的、基于网格方法的和基于模型方法的聚类。基于层次的聚类主要有：平衡

7、迭代削减聚类法（BIRCH算法）、基于密度的聚类方法（DBSCAN算法）和使用代表点的聚类方法（CURE算法）等；基于划分的聚类方法主要有：K均值聚类算法（K-means聚类算法）、K中心点算法（K-mediods聚类算法）和随机搜索聚类算法（CLARANS聚类算法）等。创新与贡献研究意义选题背景第一章2.2聚类2.2.2 基本原理 聚类的结果是类内样本的相似度高，类间样本的相似度低。相似性的度量通常采用样本间的距离来表示，距离函数值的大小反应相似的程度，相似度越大两个样本间的距离函数的值越小，相似度越小两个样本间的距离函数值越大。聚类是按照相似性大小，将无标号的数据集划分为若干类或簇的过程。

8、常用的距离计算方法有：创新与贡献研究意义选题背景第二章p 欧氏距离2.2 聚类p 曼哈顿距离p 明氏距离p 欧氏距离创新与贡献研究意义选题背景第二章欧氏距离又叫欧几里得距离，是最常见的距离表示法。假设 ，则它们之间的距离为：即两项间的差是每个变量值差的平方和再取平方根，目的是计算其间的整体距离，即不相似性。欧氏距离的优点是计算公式比较简单，缺点是不能将样本的不同属性（即各指标或各变量）之间的差别等同看待，在某些特定的应用背景中不能满足要求。一般的聚类大都采用欧氏距离。1.欧式距离（Euclidean Distance）12,.,nxx xx12,.,nyy yy222211221(,)()()

9、.()()nnniiid x yxyxyxyxy 2.2 聚类创新与贡献研究意义选题背景第二章曼哈顿距离也称为城市街区距离(CityBlock Distance)，是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。二维平面两点 与 间的曼哈顿距离定义为：两个n维向量 与 间的曼哈顿距离：要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。2.曼哈顿距离（Manhattan Distance）12a(x,x)12(,)b yy121212dxxyy11121a(,.,)nxxx21222(,.,)nb xxx12121nkkkdxx2.2 聚类创新

10、与贡献研究意义选题背景第二章明式距离也被称作闵氏距离，可以理解为N维空间的距离，是欧式距离的扩展，两个n维变量 与 间的明氏距离定义为：其中p是一个变参数。根据变参数的不同，明氏距离可以表示一类的距离：（1）当时，明氏距离即为曼哈顿距离。（2）当时，明氏距离即为欧式距离。（3）当时，明式距离即为切比雪夫距离。3.明氏距离（Minkowski Distance）11121a(,.,)nxxx21222(,.,)nb xxx12121pnpkkkdxx2.2 聚类创新与贡献研究意义选题背景第二章余弦距离，也称为余弦相似度，是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量。对于二

11、维空间，其定义为：假设向量a、b的坐标分别为 、。则：设向量 ，推广到多维：余弦距离通过测量两个向量内积空间夹角的余弦值来度量它们的相似性。余弦值的范围在-1，1之间，值越趋近于1，代表两个向量的方向越接近，越相似；越趋近于-1，他们的方向越相反，越不相似；越趋近于0，表示两个向量近乎于正交。余弦距离可以用在任何维度的向量比较中，在高维正空间中的采用较多。4.余弦距离（Cosine Similarity）cosa ba b11(,)xy22(,)xy1 21 222221122cosxxy yxyxy2.2 聚类12(,.,)nAA AA12(,.,)nBB BB12211()cosniinn

12、iiABAB创新与贡献研究意义选题背景第一章2.2聚类2.2.3 常用聚类算法 常用的几种聚类算法：p K近邻算法（KNN）p K均值聚类（K-means）p K中心点聚类（K-mediods）K近邻算法是一种常见的有监督的聚类算法，也是非参数分类的重要方法之一。K近邻的优点在于算法原理比较简单，容易理解和实现，不需要先验知识等。缺点在于计算量较大，在处理孤立点或噪声方面精度较低。K中心点聚类算法是对K均值聚类的改进，属于基于划分方法的聚类。与K均值聚类算法相比，优点是减轻了对孤立点的敏感性，提高了聚类结果的准确率。缺点是算法的复杂性比K均值聚类算法高。K中心聚类算法与K均值聚类算法最大的区别

13、在于选择将簇内离平均值最近的对象作为该簇的中心，而不是将簇内各对象的平均值作为簇的中心。K均值聚类是划分方法中经典的聚类算法之一。优点是算法简单，聚类效果较好，效率较高，对于处理大数据集有较好的可伸缩性。缺点是K值需要事先指定，受孤立点或噪声的影响较大，而且由于算法本身是迭代的，最终得到的结果有可能是局部最优而不是全局最优。创新与贡献研究意义选题背景第二章1.K近邻算法基本思想2.2 聚类 K近邻算法的基本思想是针对测试集中的一个样本点，在已经学习并且完成分类的样本空间中找到k个距离最近的样本点，距离的计算通常采用欧氏距离或明式距离。如果找到的k个样本点大多属于某一个类别，则可以判定该样本也属

14、于这个类别。p K近邻算法（KNN）创新与贡献研究意义选题背景第二章K近邻算法的实现主要有以下3个要素：2.2 聚类1）数据特征的量化。如果数据特征中存在非数值类型，则需要运用一定的手段量化成数值。若样本中存在颜色这一特征属性，可将颜色转化成灰度值来计算距离；或为了保证参数取值较大时的影响力覆盖参数取值较小时的影响力，通常需要对样本的特征数值进行归一化处理。2）样本间距离计算公式的选择。常见的距离计算公式有欧氏距离、曼哈顿距离、明式距离、余弦距离等。不同情况下对公式的选择不同，如：样本变量为连续型时，通常采用欧氏距离；样本变量为非连续型时，通常采用明式距离。3）K值的选择。K为自定义的常数，K

15、值的选择对聚类的结果有很大的影响。通常采用交叉验证法确定K的取值，且K的取值一般小于训练样本数的平方根。p K近邻算法（KNN）创新与贡献研究意义选题背景第二章2.K近邻算法过程2.2 聚类K近邻具体描述如下：1）构建训练集和测试集，使训练集按照已有的标准分成离散型数值类或连续型数值类。2）根据样本集为离散型或连续型选择适当的距离计算公式，计算测试集中的数据与各个训练集数据之间的距离，并排序。3）利用交叉验证法确定K的取值，并选择距离最小的K个点。4）确定K个点所在类别的出现频率，选择出现频率最高的类别作为测试集的预测类。p K近邻算法（KNN）创新与贡献研究意义选题背景第二章1.K均值算法基

16、本思想2.2 聚类K均值算法的基本思想是将n个样本点划分或聚类成K个簇，使得簇内具有较高的相似度，而簇间的相似度较低。首先确定所要聚类的最终数目K，并从样本中随机选择K个样本作为中心；其次将集合中每个数据点被划分到与其距离最近的簇中心所在的类簇之中，形成K个聚类的初始分布；然后对分配完的每一个类簇内对象计算平均值，重新确定新的簇中心，继续进行数据分配过程；迭代执行若干次，若簇中心不再发生变化，则完成了将数据对象完全分配至所属的类簇中，且聚类准则函数收敛；否则继续执行迭代过程，直至聚类准则函数收敛。p K均值聚类（K-means）创新与贡献研究意义选题背景第二章2.K均值算法过程2.2 聚类K均

17、值算法具体描述如下：假设给定的n个样本是 ，每个 ，其中样本间的距离选择欧氏距离。输入：n个样本和簇的数目K；输出：K个簇，且平方误差准则最小。具体步骤：（1）确定所要聚类的最终数目K，并从样本中随机选择K个样本作为中心，即 。12,.mDxxx，inxR12,.,nkR p K均值聚类（K-means）创新与贡献研究意义选题背景第二章（2）重复以下过程，直至误差平方和准则函数E收敛至某个固定值。2.2 聚类对每个样本i，计算并确定其应属类别：对于每一个类j，重新计算类的簇中心：计算E，并判断其是否收敛于某个固定的值。其中K为确定的值，代表样本i与K个类中距离最近的类，取值为 ，簇中心 代表对

18、属于同一个类的样本中心点的预测。聚类准则函数用于判断聚类质量的高低，一般采用误差平方和准则函数E的值变化情况判断是否继续进行迭代过程，E的值在每次迭代过程中逐渐减小，最终收敛至一个固定的值，则迭代过程结束，否则继续执行迭代过程，直至E收敛。误差平方和准则函数E定义如下：其中，E是所有样本点的平方误差的总和，p是某一样本点，mi是簇Ci的平均值。2arg miniijjCx 11miiijmiii Cj xi Cj iC1,Kj21ikiip cEpm p K均值聚类（K-means）创新与贡献研究意义选题背景第二章1.K中心点算法基本思想2.2 聚类K中心算法的基本思想是首先确定所要聚类的最终

19、数目K，并从样本中随机选择K个样本作为中心；其次将集合中每个数据点被划分到与其距离最近的簇中心所在的类簇之中，形成K个聚类的初始分布；反复地利用各簇中的非中心点样本来替代中心点样本，并计算各簇中各中心点样本与非中心点样本的距离之和；迭代执行若干次，寻找最小距离之和，通过不断更新各距离值来不断调整聚类的结果。p K中心点聚类（K-mediods）创新与贡献研究意义选题背景第二章2.K中心点算法过程2.2 聚类K中心点算法具体描述如下：假设给定的n个样本是，每个，其中样本间的距离选择欧氏距离。输入：n个样本和簇的数目K；输出：K个簇。p K中心点聚类（K-mediods）创新与贡献研究意义选题背景

20、第二章2.2 聚类具体步骤：（1）确定所要聚类的最终数目K，并从样本中随机选择K个样本作为中心，即 。（2）对每个样本p，计算并确定其应属类别，使得其欧氏距离M最小。（3）调整聚类中心，随机选取一个非簇中心样本 代替 ，重新分配所有剩余样本p，使得 （4）若 ，则 =，否则本次迭代中 不发生变化。（5）重复执行以上步骤，直到步骤（3）中不再成立，否则继续迭代执行（2）。12,()kko oo oD21()ikkip CMporandomomo(1)mk221()()imkkrandomip Cp Ci mMpopo 0MMrandomomomop K中心点聚类（K-mediods）创新与贡献研

21、究意义选题背景第二章2.3.1 简介遗传算法（Genetic Algorithm）也称为进化算法，是Michigan大学的Holland教授受达尔文的进化论的启发，借鉴生物进化过程，于1975年提出的一种随机启发式搜索算法。2.3 遗传算法创新与贡献研究意义选题背景第二章2.3.2基本原理遗传算法的基本思想是将问题域中的万能解作为个体，反复对群体进行交叉、变异和选择操作，通过比较每个个体的适应度值，淘汰差的个体，最终求得最优解或满意解。遗传算法具体步骤如下：（1）初始化群体；（2）计算群体上每个个体的适应度值；（3）按由个体适应度值所决定的某个规则选择将进入下一代的个体；（4）按概率参数PXO

22、VER进行交叉操作；（5）按概率参数PMUTATION进行突变操作；（6）没有满足某种停止条件，则转第(2)步，否则进入(7)；（7）输出种群中适应度值最优的个体作为问题的满意解或最优解。程序的停止条件最简单的有如下两种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。2.3 遗传算法创新与贡献研究意义选题背景第二章图2-1遗传算法流程图2.3 遗传算法创新与贡献研究意义选题背景第二章遗传算法的实现有6个主要因素：参数的编码、初始种群的设定、适应度函数的设计、遗传操作、算法控制参数的设定和约束条件的处理。（1）编码与解码编码是将一

23、个问题的可行解从其解空间转换到遗传算法的搜索空间的转化方法。主要的编码方法有：二进制编码、浮点数编码、格雷编码及多参数编码等。估计编码的三个准则是完备性、健全性和非冗余性。解码又称为译码，是由遗传算法解空间向问题空间的转换。（2）选择选择是在群体中选择出生命力较强的个体产生新的群体的过程，目的是使得群体中个体的适应度接近最优解。常见的选择算子有随机竞争选择、轮盘赌选择、最佳保留选择、确定式选择、期望值选择、均匀排序等。（3）交叉交叉是按某种方式对两个相互配对的染色体进行相互交换部分基因的操作，从而形成两个新的个体。常见的适用于二进制编码与浮点数编码的交叉算子有：两点交叉、多点交叉、算子交叉以及

24、均匀交叉。2.3 遗传算法创新与贡献研究意义选题背景第二章（4）变异变异是指将个体染色体编码串中的某些基因位上的基因值用该基因位上的其它等位基因来替换，从而形成新的个体。常见的适用于二进制编码与浮点数编码的变异算子有基本位变异、均匀变异、边界变异、非均匀变异以及高斯近似变异。（5）适应度函数适应度函数又称为评价函数，是根据目标函数确定的、用于区分群体中个体好坏的标准。目标函数可正可负，而适应度函数是非负的，因此需要在目标函数与适应度函数之间进行适当的变换。设计适应度函数时主要遵照以下四条标准：1）函数满足连续、非负、单值及最大化；2）合理性、一致性；3）计算量小；4）通用性强。评价个体适应度的

25、一般过程是：1）对个体编码串进行解码处理，得到个体的表现型；2）通过个体的表现型计算对应的个体目标函数值；3）根据最优化问题的类型，将目标函数值按照一定的转换规则计算出个体的适应度。2.3 遗传算法创新与贡献研究意义选题背景第二章（6）约束条件处理约束条件处理主要有搜索空间限定法和可行解变换法。搜索空间限定法是通过对遗传算法的搜索空间大小加以限制，在搜索空间中表示一个个体的点与解空间中表示一个可行解的点间建立一一对应的关系。可行解变换法是在个体基因型向表现型变换的过程中，增加使其满足约束条件的处理过程，也就是说，寻找个体基因型与表现型多对一的变换关系，扩大搜索空间，使得进化过程中所产生的个体可

26、以通过这种变换转化成解空间中满足约束条件的一个可行解。2.3 遗传算法创新与贡献研究意义选题背景第二章2.3.3 特点与应用遗传算法的特点（1）以决策变量的编码作为运算对象。借鉴染色体和基因的概念，模仿自然界生物的遗传和进化机理。（2）使用概率搜索技术，而不是确定性规则。（3）直接以适应度作为搜索信息，无需借助导数等其它辅助信息。（4）使用多个点的搜索信息，具有隐含并行性。2.3 遗传算法创新与贡献研究意义选题背景第二章遗传算法的应用2.3 遗传算法遗传算法不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于函数优化、组合优化，例如：遗传算法已经在求解旅行商问题、背包问题、装箱问

27、题、图形划分问题等方面得到成功的应用。此外，遗传算法在生产调度问题、自动控制、机器人学、图像处理等方面获得了广泛的运用。创新与贡献研究意义选题背景第二章2.4.1 简介 2.4 蚁群算法 蚁群算法(Ant Colony Optimization，ACO)，最早是由Marco Dorigo等人于1991年提出的，是在图中寻找优化路径的概率型算法。基本思想来自蚂蚁在寻找食物过程中发现最短路径的行为。蚁群在寻找食物时，通过分泌信息素交流觅食信息，从而能在没有任何提示的情况下找到从食物源到巢穴的最短路径，并在周围环境发生变化后，自适应地搜索新的最佳路径。蚁群算法的优点是算法简单，实现容易。创新与贡献研

28、究意义选题背景第二章2.4.2 基本原理 2.4 蚁群算法 首先介绍蚁群算法中的参数：设蚁群中所有蚂蚁的数量为m，所有城市之间的信息素为矩阵pheromon，最短路径为bestLength，最佳路径为bestTour。每只蚂蚁都有自己的内存，内存中用一个禁忌表（Tabu）来存储该蚂蚁已经访问过的城市，表示其在以后的搜索中将不能访问这些城市，用一个允许访问的城市表（Allowed）来存储该蚂蚁还可以访问的城市，用一个矩阵（Delta）来存储它在一个循环（或者迭代）中给所经过的路径释放的信息素；此外还有一些数据，运行次数MAX_GEN次，运行时间t，控制参数，蚂蚁行走完全程的总成本或距离（tour

29、Length）等。创新与贡献研究意义选题背景第二章蚁群算法计算过程如下：图2-2蚁群算法流程图2.4 蚁群算法（1）初始化（2）选择节点（3）更新信息素矩阵（4）检查终止条件（5）输出最优值创新与贡献研究意义选题背景第二章（1）初始化t=0时，对所有参数进行初始化。设置bestLength为正无穷，bestTour为空，将所有蚂蚁的Delt矩阵所有元素初始化为0，Tabu表清空，向Allowed表中加入所有的城市节点，用随机选择或人工指定的方法它们的起始位置，在Tabu表中加入起始节点，Allowed表中去掉该起始节点。2.4 蚁群算法创新与贡献研究意义选题背景第二章（2）选择节点为每只蚂蚁选

30、择下一个节点，该节点只能从Allowed表中以通过公式（2-1）计算得到的概率搜索到，每搜到一个节点，就将该节点加入到Tabu表中，并且从Allowed表中删除该节点。重复n-1次该过程，直到所有的城市都遍历过一次。遍历完所有节点后，将起始节点加入到Tabu表中。此时Tabu表元素数量为n+1（n为城市数量），Allowed表元素数量为0。接下来按照公式（2-2）计算每个蚂蚁的Delta矩阵值。最后计算最佳路径，比较每个蚂蚁的路径成本，然后与bestLength比较，若它的路径成本比bestLength小，则将该值赋予bestLength，并且将其Tabu赋予BestTour并将该城市节点加到

31、bestTour中。2.4 蚁群算法创新与贡献研究意义选题背景第二章（2）选择节点其中k表示第k个蚂蚁，表示选择城市j的概率，表示城市i，j在第t时刻的信息素浓度，表示从城市i到城市j的可见度，表示城市i，j之间的成本。表示蚂蚁k在城市i与j之间留下的信息素。表示蚂蚁k完成一个循环所经过路径的总成本，即tourLength，Q均为控制参数。()()()0kijijkkikikk allowedijtjallowedttp（2-1）0kkijQL（2-2）()ijtp()ijtij1ijijdijdkijkL2.4 蚁群算法创新与贡献研究意义选题背景第二章（3）更新信息素矩阵令t=t+n，按照公

32、式（2-3）更新信息素矩阵phermone。其中 为t+n时刻城市i与j之间的信息素浓度，为控制参数，为城市i与j之间信息素经过一个迭代后的增量。并且有 其中 由公式计算得到。()()ijijijt nt()ijtnij1mki ji jkkij（2-3）2.4 蚁群算法创新与贡献研究意义选题背景第二章（4）检查终止条件如果达到最大迭代次数MAX_GEN，则算法终止，转到第（5）步；否则，重新初始化所有蚂蚁的Delt矩阵中所有元素为0，Tabu表清空，Allowed表中加入所有的城市节点，随机选择或人工指定它们的起始位置，在Tabu表中加入起始节点，Allowed表中去掉该起始节点，重复执行（

33、2）（3）（4）步。（5）输出最优值2.4 蚁群算法创新与贡献研究意义选题背景第二章2.4.3 特点与应用 2.4 蚁群算法1.特点（1）自组织：蚁群算法的组织指令来自于系统内部的，在获得空间、时间或者功能结构过程中，没有受到外界的影响，即蚁群算法能够在没有外界环境的影响下使系统的熵增加，具有良好的自组织能力。（2）并行化：每只蚂蚁个体搜索最优解的过程彼此独立，仅通过信息激素进行通信，所以蚁群算法可以看作一个分布式的多agent系统，在问题空间中多个不同的点位同时进行解的搜索，不仅降低了算法的时间复杂性，还可以使算法具有一定的全局搜索能力。（3）正反馈：蚂蚁能够找到最短路径的过程依赖于路径上堆

34、积的信息激素，信息激素堆积是一个正反馈的过程，其反馈方式是在较优解的路径上留下更多的信息激素，而信息激素越多又会吸引更多的蚂蚁，正反馈的过程又引导整个系统向最优解的方向进化。（4）鲁棒性：蚁群算法对初始路线要求不高，即最终结果不依赖初始路线的选择，在搜索过程中也不需要人为调整。创新与贡献研究意义选题背景第二章2.4.3 特点与应用 2.4 蚁群算法1.应用近年来随着对蚁群算法理论与实际应用研究的不断深入，蚁群算法被应用于求解经典的旅行商问题及其他领域的优化问题和边界条件优化问题，如生产调度问题、图像处理、车辆路径问题及机器人路径规划问题等。创新与贡献研究意义选题背景第二章2.5.1 简介2.5

35、 粒子群算法粒子群算法（Particle Swarm Optimization，PSO）是一种由Kennedy等学者从鸟类寻找食物的过程中得到启发，于1995年提出的新型群体智能优化算法。粒子群算法同遗传算法以及蚁群算法等群体智能算法类似，都是受生物群体启发的优化算法。其基本思想来自鸟群在觅食过程中发现最优位置的行为。鸟群在寻找食源的过程中，通过不断进行最优位置信息的交流，每只鸟根据最优位置调整自己的飞行速度和飞行方向，最终找到食源。创新与贡献研究意义选题背景第二章2.5.2 基本原理 2.5 粒子群算法假设一个n维的目标搜索空间中含有m个粒子，每个粒子的位置对应一个n维向量 ，第i个粒子的局

36、部最优值为 ，当前种群的最优位置为 ，每个粒子所对应的运动速度也是一个n维的向量 。在粒子的运动过程中，粒子群中的每一个粒子会根据公式（2-4）和（2-5）来更新自己的运动速度，根据公式（2-6）更新自己的位置。12(,.)iiiinxxxx12(,.,)iiiinpppp12(,.,)ggggnpppp12(,.,)iiiinvvvv112()()()()kkkkkkididididgdgdvvcrandpxcrandpxmaxmaxminmin,ididididvvvvvvvv11kkkidididxxv（2-4）（2-5）（2-6）创新与贡献研究意义选题背景第二章2.5.2 基本原理2.

37、5 粒子群算法其中 ，k为粒子群迭代的次数（），为随机数函数，在0，1之间随机选取。为非负数，表示粒子自身的认知系数，表示粒子的社会认知系数。为最大的运动速度，为最小的运动速度，两者的值通常由用户根据经验来定义，用来对运动速度进行调整。对于公式（2-7）来说 代表前次运动的速度，它使得粒子在全部的搜素空间中有向各个方向伸张的趋势，表示自身的认知过程，它通过粒子自身的运动来获得认知能力。表示学习其他粒子经验的过程，该过程是粒子群中每个粒子相互分享学习经验的过程。1im 1dn1k()rand12,c c1c2cmaxvmaxvkidv1()()kkididcrandpx2()()kkgdgdcr

38、andpx创新与贡献研究意义选题背景第二章2.5.2 基本原理2.5 粒子群算法粒子群算法的实现步骤如下：(1)对粒子群的每个粒子的位置和速度进行随机的初始化；(2)根据定义的适应度函数，计算每个粒子的适应度值；(3)将粒子的适应度值与该粒子局部最优位置的适应度值相比较，求粒子的局部最优解；(4)将全局最优位置的适应度值与每个粒子的局部位置的适应度值相比较，求粒子群的全局最优解；(5)根据公式（2-4）和（2-5）计算每个粒子的运动速度，根据公式（2-6）计算每个粒子的位置；(6)判断终止条件是否满足，如果不满足，返回第（2）步，否则算法结束。创新与贡献研究意义选题背景第二章2.5.3 特点与

39、应用2.5 粒子群算法1.特点（1）速度快：粒子群算法没有交叉和变异运算，依靠粒子速度完成搜索，并且在迭代进程中只有最优的粒子把信息传递给其他粒子，搜索速度快。（2）记忆性：粒子群体获得的历史最好位置可以被记录并传递给其它粒子的。（3）易于实现：粒子群算法需要调整的参数较少，易于实现，结构简单，它采用实数编码，直接由问题的解决定，问题解的变量数直接作为粒子的维度数。2.应用由于粒子群算法实现简单，易于理解，且能够优化一些复杂的问题，常被用于神经网络的优化、函数参数的优化、电力系统的优化等领域，并且有着较好的效果。创新与贡献研究意义选题背景第二章2.6.1 简介2.6 人工神经网络人工神经网络（

40、Artificial Neural Network，ANN）简称为神经网络(NN)或连接模型（Connectionist Model）。智库百科中人工神经网络的定义是：“人工神经网络是由人工建立的以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作状态相应而进行信息处理”。因此，人工神经网络是基于神经网络的基本原理，在理解和抽象人脑和外界刺激响应机制的基础上，以网络拓扑知识为理论基础，模拟人脑神经系统实现复杂信息处理机制的数学模型，具有自学能力、联想存储能力以及高速寻优能力。创新与贡献研究意义选题背景第二章2.6.1 简介2.6 人工神经网络1.人工神经网络发展（1）初始阶段启蒙时期（2）

41、第二阶段低潮时期（3）第三阶段复兴时期（发展期）（4）第四阶段深度学习创新与贡献研究意义选题背景第二章2.6.1 简介2.6 人工神经网络（1）初始阶段启蒙时期启蒙时期也称为形成时期，早在20世纪50年代国外的学者就开始了对人工神经网络的研究工作。1943年，美国生理学家Mcculloch和数学家Pitts发表文章，提出了第一个神经元模型（M-P模型），开启了对人工神经网络研究的大门。1951年，心理学家Donala O.Hebb提出了连接权值强化的Hebb法则，为构造有学习功能的的神经网络模型奠定了基础。1960年，Widrow和Hoff提出了一种连续取值的自适应线性神经元网络模型Adali

42、ne，提高了分段线性网络的训练速度及精度。创新与贡献研究意义选题背景第二章2.6.1 简介2.6 人工神经网络（2）第二阶段低潮时期1969年，Minsky和Papert在Perceptrons一书，从数学的角度证明了简单的线性感知器的功能是有限的，不能有效地应用于多层网络，由此对神经网络的研究进入10年左右的低潮期。尽管在低谷时期，也产生了许多重要的研究成果，如1972年芬兰的Kohonen教授提出的自组织映射（SOM）理论，1980年福岛邦彦提出的“新认知机”模型等，为日后神经网络的理论研究奠定了重要的基础。创新与贡献研究意义选题背景第二章2.6.1 简介2.6 人工神经网络（3）第三阶段

43、复兴时期（发展期）1982年，美国物理学家Hopfield提出了离散Hopfield神经网络，并证明了在一定条件下，网络可以达到稳定的状态，再次掀起了神经网络研究的一个热潮。1983年Kirkpatrick等人认识到可将模拟退火算法运用到NP完全组合优化问题的求解过程中。Hinton与年轻学者Sejnowski等于1984年合作提出了大规模并行网络学习机（后来被称为Boltzmann机），同时提出了隐单元的概念。1986年，D.E.Ru melhart在多层神经网络模型的基础上，提出了多层神经网络权值修正的反向传播学习算法BP算法（Back-Propagation），解决了多层前向神经网络的学

44、习问题，证明了多层神经网络具有很强的学习能力，可以完成许多学习任务，解决许多实际问题。1988年，Broomhead和Lowe将径向基函数(Radial Basis Function，RBF)运用到人工神经网络（ANN）的设计中，将人工神经网络的设计与数值分析以及线性适应滤波联系起来。创新与贡献研究意义选题背景第二章2.6.1 简介2.6 人工神经网络（4）第四阶段深度学习2006年，Hinton提出的深度学习，是机器学习的一个新方法，也是神经网络的最新发展。深度学习算法打破了传统神经网络对层数的限制，可根据设计者需要选择网络层数，构建含多隐层的机器学习框架模型，对大规模数据进行训练，从而得到

45、更有代表性的特征信息。创新与贡献研究意义选题背景第二章2.6.1 简介2.6 人工神经网络1.人工神经网络研究内容神经网络的研究可分为理论研究和应用研究两个方面。理论研究主要包括：（1）以神经生理与认知科学为基础，对人类思维以及智能机理进行研究。（2）借鉴神经基础理论的研究成果，运用数理方法，深入研究网络算法，提高稳定性、收敛性、容错性、鲁棒性等方面的性能，发展如神经网络动力学、非线性神经场等新的网络数理理论，并且尝试构建功能上更加完善、性能上更具优越性的神经网络模型。应用研究主要包括：（1）对神经网络的硬件实现和软件模拟的研究。（2）神经网络在模式识别、信号处理、专家系统、优化组合、知识工程

46、和机器人控制等领域的应用研究。创新与贡献研究意义选题背景第二章2.6.2 神经网络基础2.6 人工神经网络1.生物神经元 在介绍人工神经元之前，首先以人脑神经元为例介绍生物神经元的结构及特点。人脑中大约有1000亿个神经元。神经元主要由树突、细胞体、轴突和突触组成，基本结构如图所示。树突的作用是接受信息，细胞体的作用是对接受的信息进行处理，轴突的作用是发出信息。一个神经元的轴突末端与另外一个神经元的树突紧密接触形成的部分构成突触，用于保证信息的单向传递。创新与贡献研究意义选题背景第二章2.6.2 神经网络基础2.6 人工神经网络1.生物神经元 创新与贡献研究意义选题背景第二章2.6.2 神经网

47、络基础2.6 人工神经网络2.人工神经网络结构 人工神经元是受人脑神经元结构的启发而提出的，结构如下图所示，一个神经元结构由输入向量、激活函数及输出向量三部分组成。输入向量 与对应的权值向量 分别相乘再取和作为输入值 ，在激活函数的作用下输出对应 ，其中b为激活函数的阈值。01,.nXxxx01,.nWwww0niiixw()iifx wb创新与贡献研究意义选题背景第二章2.6.2 神经网络基础2.6 人工神经网络2.人工神经网络结构 创新与贡献研究意义选题背景第二章2.6.2 神经网络基础2.6 人工神经网络3.常见激活函数（Activation Function）神经网络由大量的神经元连接

48、组成，每个神经元代表一种特定的输出函数，称为激活函数。激活函数不是要在神经网络中发挥某种激活作用，而是通过某种函数的形式把生物神经元中“激活的神经元特征”保留并映射出来。激活函数具有可微性、单调性和输出范围有限等特点。常用的激活函数主要有线性函数、斜面函数、阈值函数、Sigmoid函数，双曲正切函数以及ReLU函数。下面重点介绍三种常用的函数：创新与贡献研究意义选题背景第二章2.6.2 神经网络基础2.6 人工神经网络3.常见激活函数（Activation Function）（1）Sigmoid函数Sigmoid函数又称为S型曲线，是一种常用的非线性激活函数，数学表达式为：由图可知，Sigmo

49、id函数是一个连续、光滑且严格单调的阈值函数，可将输入的实值映射到01的范围内，当输入值趋向于负无穷时映射结果为0，当输入值趋向于正无穷时映射结果为1。但Sigmoid函数也存在缺点，具体表现为Sigmoid函数有易饱和性，当输入值非常大或非常小时，神经元梯度几乎接近0。1()1xf xe创新与贡献研究意义选题背景第二章2.6.2 神经网络基础2.6 人工神经网络3.常见激活函数（Activation Function）（2）Tanh函数Tanh函数是双曲正切函数，是一种常用的非线性激活函数，数学表达式为：由图可知，Tanh函数和Sigmoid函数类似，是Sigmoid函数的变形，不同的是Ta

50、nh函数把实值的输入映射到的范围，基本是0均值。Tanh函数解决了上述Sigmoid函数的第二个缺点，因此实际中Tanh函数比Sigmoid函数更常用。Tanh函数的缺点是存在梯度饱和的问题。()xxxxeef xee创新与贡献研究意义选题背景第二章2.6.2 神经网络基础2.6 人工神经网络3.常见激活函数（Activation Function）（3）ReLU函数近年来，ReLU函数越来越受欢迎，数学表达式为：由图可知，当输入信号小于0时，输出为0，当输入信号大于0时，输入与输出相等。ReLU函数的优点是：1）相比于Sigmoid函数和Tanh函数，收敛速度较快，且梯度不会饱和；2）计算复