第二章-机器学习的理论与方法

机器学习与大数据技术作者：牟少敏教授第二章回归分析与最小二乘法聚类遗传算法蚁群算法机器学习的理论与方法粒子群算法支持向量机隐马尔科夫模型人工神经网络创新与贡献研究意义选题背景第二章机器学习则是研究机器模仿人类的学习过程，进行知识和技能获取，是一门涉及到计算机科学与技术、概率论与统计学和认知科学等多个领域的交叉学科。学习是人类区别于低级动物，自身所具有的重要智能行为。其应用十分广泛，如：数据挖掘、计算机视觉、自然语言处理、语音和手写识别和机器人研发等各个领域。分类问题：在有监督学习任务中，预测变量为离散变量。创新与贡献研究意义选题背景第二章2.1回归分析与最小二乘法回归问题：在有监督学习任务中，预测变量为连续变量。回归分析是一种用于确定两种或两种以上变量间相互依赖关系的统计分析方法。按照问题所涉及变量的多少，可将回归分析分为一元回归分析和多元回归分析。按照自变量与因变量之间是否存在线性关系，分为线性回归分析和非线性回归分析。如果在某个回归分析问题中，只有两个变量，一个自变量和一个因变量，且自变量与因变量之间的函数关系能够用一条直线来近似表示，那么称其为一元线性回归分析。创新与贡献研究意义选题背景第一章2.1回归分析与最小二乘法回归分析的基本步骤如下：创新与贡献研究意义选题背景第二章2.1回归分析与最小二乘法分析预测目标，确定自变量和因变量；建立合适的回归预测模型；相关性分析；检测回归预测模型，计算预测的误差；计算并确定预测值。最小二乘法又称为最小平方法，是一种常用的数学优化方法。最小二乘法的原理是通过最小化误差平方和寻找与数据匹配的最佳函数。最小二乘法的应用十分广泛，既可以用于参数估计，也可以用于曲线拟合，以及一些其他的优化问题。创新与贡献研究意义选题背景第二章2.1回归分析与最小二乘法创新与贡献研究意义选题背景第二章对于一元线性回归模型，假设从总体中获取了组观察值，其中。那么这组观察值在二维平面直角坐标系中对应的就是平面中的个点，此时有无数条曲线可以拟合这个点。通常情况下，希望回归函数能够尽可能好地拟合这组值。综合来看，当这条直线位于样本数据的中心位置时似乎最合理。因此，选择最佳拟合曲线的标准可确定为：总拟合误差（即总残差）最小。对于总拟合误差，有三个标准可供选择：（1）用“残差和”表示总拟合误差，但“残差和”会出现相互抵消的问题。（2）用“残差绝对值”表示总拟合误差，但计算绝对值相对来说较为麻烦。（3）用“残差平方和”表示总拟合误差。最小二乘法采用的就是“残差平方和最小”所确定的直线。用“残差平方和”计算方便，而且对异常值会比较敏感。2.1回归分析与最小二乘法创新与贡献研究意义选题背景第二章假设回归模型（拟合函数）为：则样本的误差为：其中为的预测值（拟合值），为对应的实际值。最小二乘法的损失函数也就是残差平方和，即：通过最小化来确定直线方程，即确定和，此时该问题变成了求函数的极值的问题。根据高等数学的知识可知，极值通常是通过令导数或者偏导数等于0而得到，因此，求关于未知参数和的偏导数：2.1回归分析与最小二乘法01()iifxx01()iiiiieyfxyx()ifxixiyixQ22201111()nnniiiiiiiiQeyfxyx创新与贡献研究意义选题背景第二章通过令偏导数为0，可求解函数的极值点，即：2.1回归分析与最小二乘法0110011121020niiiniiiiQyxQyxx2022122iiiiiiiiiiiiixyxxynxxnxyxynxx将样本数据代入，即可得到和的具体指。(,)1,2,iiXYin0ˆ1ˆ创新与贡献研究意义选题背景第二章2.2.1简介作为一种无监督机器学习方法，聚类经常用于数据挖掘和模式识别。2.2聚类聚类（ClusterAnalysis）是将数据集中的所有样本根据相似度的大小进行划分，形成两个或多个类（簇）的过程。簇是数据集中相似的样本集合。聚类没有训练过程，是一种无标准的学习，同时也是一种无监督学习。创新与贡献研究意义选题背景第二章分类的根本区别在于：分类是需要有标号的样本进行训练。2.2聚类聚类算法可分为：基于划分方法的、基于层次方法的、基于密度方法的、基于网格方法的和基于模型方法的聚类。基于层次的聚类主要有：平衡迭代削减聚类法（BIRCH算法）、基于密度的聚类方法（DBSCAN算法）和使用代表点的聚类方法（CURE算法）等；基于划分的聚类方法主要有：K均值聚类算法（K-means聚类算法）、K中心点算法（K-mediods聚类算法）和随机搜索聚类算法（CLARANS聚类算法）等。创新与贡献研究意义选题背景第一章2.2聚类2.2.2基本原理聚类的结果是类内样本的相似度高，类间样本的相似度低。相似性的度量通常采用样本间的距离来表示，距离函数值的大小反应相似的程度，相似度越大两个样本间的距离函数的值越小，相似度越小两个样本间的距离函数值越大。聚类是按照相似性大小，将无标号的数据集划分为若干类或簇的过程。常用的距离计算方法有：创新与贡献研究意义选题背景第二章欧氏距离2.2聚类曼哈顿距离明氏距离欧氏距离创新与贡献研究意义选题背景第二章欧氏距离又叫欧几里得距离，是最常见的距离表示法。假设，，则它们之间的距离为：即两项间的差是每个变量值差的平方和再取平方根，目的是计算其间的整体距离，即不相似性。欧氏距离的优点是计算公式比较简单，缺点是不能将样本的不同属性（即各指标或各变量）之间的差别等同看待，在某些特定的应用背景中不能满足要求。一般的聚类大都采用欧氏距离。1.欧式距离（EuclideanDistance）12{,,....,}nxxxx12{,,....,}nyyyy222211221(,)()()...()()nnniiidxyxyxyxyxy2.2聚类创新与贡献研究意义选题背景第二章曼哈顿距离也称为城市街区距离(CityBlockDistance)，是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。二维平面两点与间的曼哈顿距离定义为：两个n维向量与间的曼哈顿距离：要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。2.曼哈顿距离（ManhattanDistance）12a(x,x)12(,)byy121212dxxyy11121a(,,...,)nxxx21222(,,...,)nbxxx12121nkkkdxx2.2聚类创新与贡献研究意义选题背景第二章明式距离也被称作闵氏距离，可以理解为N维空间的距离，是欧式距离的扩展，两个n维变量与间的明氏距离定义为：其中p是一个变参数。根据变参数的不同，明氏距离可以表示一类的距离：（1）当时，明氏距离即为曼哈顿距离。（2）当时，明氏距离即为欧式距离。（3）当时，明式距离即为切比雪夫距离。3.明氏距离（MinkowskiDistance）11121a(,,...,)nxxx21222(,,...,)nbxxx12121pnpkkkdxx2.2聚类创新与贡献研究意义选题背景第二章余弦距离，也称为余弦相似度，是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量。对于二维空间，其定义为：假设向量a、b的坐标分别为、。则：设向量，，推广到多维：余弦距离通过测量两个向量内积空间夹角的余弦值来度量它们的相似性。余弦值的范围在[-1，1]之间，值越趋近于1，代表两个向量的方向越接近，越相似；越趋近于-1，他们的方向越相反，越不相似；越趋近于0，表示两个向量近乎于正交。余弦距离可以用在任何维度的向量比较中，在高维正空间中的采用较多。4.余弦距离（CosineSimilarity）cosabab11(,)xy22(,)xy121222221122cosxxyyxyxy2.2聚类12(,,...,)nAAAA12(,,...,)nBBBB12211()cosniinniiABAB创新与贡献研究意义选题背景第一章2.2聚类2.2.3常用聚类算法常用的几种聚类算法：K近邻算法（KNN）K均值聚类（K-means）K中心点聚类（K-mediods）K近邻算法是一种常见的有监督的聚类算法，也是非参数分类的重要方法之一。K近邻的优点在于算法原理比较简单，容易理解和实现，不需要先验知识等。缺点在于计算量较大，在处理孤立点或噪声方面精度较低。K中心点聚类算法是对K均值聚类的改进，属于基于划分方法的聚类。与K均值聚类算法相比，优点是减轻了对孤立点的敏感性，提高了聚类结果的准确率。缺点是算法的复杂性比K均值聚类算法高。K中心聚类算法与K均值聚类算法最大的区别在于选择将簇内离平均值最近的对象作为该簇的中心，而不是将簇内各对象的平均值作为簇的中心。K均值聚类是划分方法中经典的聚类算法之一。优点是算法简单，聚类效果较好，效率较高，对于处理大数据集有较好的可伸缩性。缺点是K值需要事先指定，受孤立点或噪声的影响较大，而且由于算法本身是迭代的，最终得到的结果有可能是局部最优而不是全局最优。创新与贡献研究意义选题背景第二章1.K近邻算法基本思想2.2聚类K近邻算法的基本思想是针对测试集中的一个样本点，在已经学习并且完成分类的样本空间中找到k个距离最近的样本点，距离的计算通常采用欧氏距离或明式距离。如果找到的k个样本点大多属于某一个类别，则可以判定该样本也属于这个类别。K近邻算法（KNN）创新与贡献研究意义选题背景第二章K近邻算法的实现主要有以下3个要素：2.2聚类1）数据特征的量化。如果数据特征中存在非数值类型，则需要运用一定的手段量化成数值。若样本中存在颜色这一特征属性，可将颜色转化成灰度值来计算距离；或为了保证参数取值较大时的影响力覆盖参数取值较小时的影响力，通常需要对样本的特征数值进行归一化处理。2）样本间距离计算公式的选择。常见的距离计算公式有欧氏距离、曼哈顿距离、明式距离、余弦距离等。不同情况下对公式的选择不同，如：样本变量为连续型时，通常采用欧氏距离；样本变量为非连续型时，通常采用明式距离。3）K值的选择。K为自定义的常数，K值的选择对聚类的结果有很大的影响。通常采用交叉验证法确定K的取值，且K的取值一般小于训练样本数的平方根。K近邻算法（KNN）创新与贡献研究意义选题背景第二章2.K近邻算法过程2.2聚类K近邻具体描述如下：1）构建训练集和测试集，使训练集按照已有的标准分成离散型数值类或连续型数值类。2）根据样本集为离散型或连续型选择适当的距离计算公式，计算测试集中的数据与各个训练集数据之间的距离，并排序。3）利用交叉验证法确定K的取值，并选择距离最小的K个点。4）确定K个点所在类别的出现频率，选择出现频率最高的类别作为测试集的预测类。K近邻算法（KNN）创新与贡献研究意义选题背景第二章1.K均值算法基本思想2.2聚类K均值算法的基本思想是将n个样本点划分或聚类成K个簇，使得簇内具有较高的相似度，而簇间的相似度较低。首先确定所要聚类的最终数目K，并从样本中随机选择K个样本作为中心；其次将集合中每个数据点被划分到与其距离最近的簇中心所在的类簇之中，形成K个聚类的初始分布；然后对分配完的每一个类簇内对象计算平均值，重新确定新的簇中心，继续进行数据分配过程；迭代执行若干次，若簇中心不再发生变化，则完成了将数据对象完全分配至所属的类簇中，且聚类准则函数收敛；否则继续执行迭代过程，直至聚类准则函数收敛。K均值聚类（K-means）创新与贡献研究意义选题背景第二章2.K均值算法过程2.2聚类K均值算法具体描述如下：假设给定的n个样本是，每个，其中样本间的距离选择欧氏距离。输入：n个样本和簇的数目K；输出：K个簇，且平方误差准则最小。具体步骤：（1）确定所要聚类的最终数目K，并从样本中随机选择K个样本作