ML算法（常见机器学习算法公式）

2024-07-16 20:31| 来源: 网络整理| 查看: 265

原文链接：www.cnblogs.com/tornadomeet/p/3395593.html

前言：

　　找工作时（IT行业），除了常见的软件开发以外，机器学习岗位也可以当作是一个选择，不少计算机方向的研究生都会接触这个，如果你的研究方向是机器学习/数据挖掘之类，且又对其非常感兴趣的话，可以考虑考虑该岗位，毕竟在机器智能没达到人类水平之前，机器学习可以作为一种重要手段，而随着科技的不断发展，相信这方面的人才需求也会越来越大。

　　纵观IT行业的招聘岗位，机器学习之类的岗位还是挺少的，国内大点的公司里百度，阿里，腾讯，网易，搜狐，华为（华为的岗位基本都是随机分配，机器学习等岗位基本面向的是博士）等会有相关职位，另外一些国内的中小型企业和外企也会招一小部分。当然了，其中大部分还是百度北京要人最多，上百人。阿里的算法岗位很大一部分也是搞机器学习相关的。另外本人有幸签约了网易杭州研究院的深度学习算法岗位，打算从事机器学习领域至少5年。非常感谢小易收留了我！

　　下面是本人在找机器学习岗位工作时，总结的常见机器学习算法（主要是一些常规分类器）大概流程和主要思想，希望对大家找机器学习岗位时有点帮助。实际上在面试过程中，懂这些算法的基本思想和大概流程是远远不够的，那些面试官往往问的都是一些公司内部业务中的课题，往往要求你不仅要懂得这些算法的理论过程，而且要非常熟悉怎样使用它，什么场合用它，算法的优缺点，以及调参经验等等。说白了，就是既要会点理论，也要会点应用，既要有点深度，也要有点广度，否则运气不好的话很容易就被刷掉，因为每个面试官爱好不同。

决策是智能化的一个重要表现，类似于数据库“触发器”的概念，其意义可以表示为：我们在什么情况下该做什么？ML领域“分类”概念与其类似，智能决策也是从决策条件到决策结果的出发，与分类类似。分类可以表示为 if() then () 语句，形象表示为BOOL逻辑的组合，if (Feature >X) Then (ClassLabel =1)，决策和触发器也可以这样表示。使用数据的模式识别方法，为机器学习，机器直接从数据中获取分类函数跳过规则获取这一步，隐式地把规则用模型的方式表现出来。

规律是科学的追逐目标，发现规则是简化复杂表象的方法，就像复杂的语义是由相对较少的语法规则约束，掌握了语义的形式化规则——语法，则可以利用少量的存储应对复杂的场景，机器学习是显式或者隐式寻找复杂场景隐藏规则的过程，通过模型的方式表现出来。

专家系统第一目标是完备性，即系统规则是无矛盾的。机器学习模型的第一目标是泛化性能，模型能完成更多空间样本的决策分类。

基于规则的专家系统为硬规则系统，规则在系统内表现为知识，专家系统可以表示为机器学习模型的最终表现形式。尽管规则的推广性不可能无限制增加，总有处理不了的新目标，这也是知识获取的来源——数据受限制决定的，并不能说明规则是错误的，可以通过规则细分化——决策树分裂来完成。

专家系统的规则面对新目标失效时，可以通过反馈重构规则，完成规则系统的完备性，对应在机器学习领域表现为“在线机器学习”，其同态映射为“在线决策树”算法。

算法的扩展性是机器学习算法性能衡量标准之一，机器学习算法遵循样本->新场景中实例确定因果关联。根据已知中间模型的类型和步骤不同，划分为多种。“可扩展性”、“泛化性能” 在数学系统的同态映射为函数的值域可拓延性范围，

若样本-> 模型 ->新场景中实例确定模型为黑箱，则其代表为可能为神经网络，神经网络是使用参数描述模型的代表，甚至不用知道参数的意义也可以得到好的结果，这种使用结构来替代“决策”这种智能的描述值得追求吗？

若样本-> 模型 ->新场景中实例确定模型为先验概率和后验概率的关系，此种方法为朴素贝叶斯，朴素贝叶斯使用结果和规则来推测原因，利用数字化“可能性”来描述规则，必然有一定的错误率，这也是其他一切模型所能达到正确率的极限了。

若样本-> 模型 ->新场景中实例确定模型为bool逻辑规则的附加，此种方法为决策树方法。决策树运用 “And”运算，对特征进行优先级分层建立树状结构，利用“And”运算完成从根部开始到叶子的递推，完成决策过程。决策树方法必然会出现过拟合现象，其泛化性能受样本拓扑分布特征约束明显，由于其分裂特性，决策空间划分为块状，其不同父类叶子间的分类面不相关。

　　若样本-> 模型 ->新场景中实例确定模型表现为连续函数，则需要拟合，方法有线性回归等。

下面的分类不是很规则，如有疑问，请自行排疑.

一.朴素贝叶斯：

　　有以下几个地方需要注意：

　　1. 如果给出的特征向量长度可能不同，这是需要归一化为通长度的向量（这里以文本分类为例），比如说是句子单词的话，则长度为整个词汇量的长度，对应位置是该单词出现的次数。

　　2. 计算公式如下：

　　其中一项条件概率可以通过朴素贝叶斯条件独立展开。要注意一点就是的计算方法，而由朴素贝叶斯的前提假设可知，

= ，

因此一般有两种，一种是在类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本的总和；第二种方法是类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本中所有特征出现次数的总和。

　　3. 如果中的某一项为0，则其联合概率的乘积也可能为0，即2中公式的分子为0，为了避免这种现象出现，一般情况下会将这一项初始化为1，当然为了保证概率相等，分母应对应初始化为2（这里因为是2类，所以加2，如果是k类就需要加k，术语上叫做laplace光滑, 分母加k的原因是使之满足全概率公式）。

　　朴素贝叶斯的优点：

　　对小规模的数据表现很好，适合多分类任务，适合增量式训练。

　　缺点：

　　对输入数据的表达形式很敏感。

后记：

二.决策树：

　　决策树中很重要的一点就是选择一个属性进行分枝，因此要注意一下信息增益的计算公式，并深入理解它。

　　信息熵的计算公式如下:

　　其中的n代表有n个分类类别（比如假设是2类问题，那么n=2）。分别计算这2类样本在总样本中出现的概率p1和p2，这样就可以计算出未选中属性分枝前的信息熵。

　　现在选中一个属性xi用来进行分枝，此时分枝规则是：如果xi=vx的话，将样本分到树的一个分支；如果不相等则进入另一个分支。很显然，分支中的样本很有可能包括2个类别，分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’=p1*H1+p2*H2.，则此时的信息增益ΔH=H-H’。以信息增益为原则，把所有的属性都测试一边，选择一个使增益最大的属性作为本次分枝属性。

　　决策树的优点：

　　计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征；

　　缺点：

　　容易过拟合（后续出现了随机森林，减小了过拟合现象）；

三.Logistic回归：

　　Logistic是用来分类的，是一种线性分类器，需要注意的地方有：

　　1. logistic函数表达式为：

　　其导数形式为：

　　2. logsitc回归方法主要是用最大似然估计来学习的，所以单个样本的后验概率为：

　　到整个样本的后验概率：

　　其中：

　　通过对数进一步化简为：

　　3. 其实它的loss function为-l(θ)，因此我们需使loss function最小，可采用梯度下降法得到。梯度下降法公式为:

　　Logistic回归优点：

　　1、实现简单；

　　2、分类时计算量非常小，速度很快，存储资源低；

　　缺点：

　　1、容易欠拟合，一般准确度不太高

　　2、只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；

四.线性回归：

　　线性回归才是真正用于回归的，而不像logistic回归是用于分类，其基本思想是用梯度下降法对最小二乘法形式的误差函数进行优化，当然也可以用normal equation直接求得参数的解，结果为：

　　而在LWLR（局部加权线性回归）中，参数的计算表达式为:

　　因为此时优化的是：

　　由此可见LWLR与LR不同，LWLR是一个非参数模型，因为每次进行回归计算都要遍历训练样本至少一次。

　　线性回归优点：

　　实现简单，计算简单；

　　缺点：

　　不能拟合非线性数据；

五.KNN算法：

　　KNN即最近邻算法，其主要过程为：

　　1. 计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；

　　2. 对上面所有的距离值进行排序；

　　3. 选前k个最小距离的样本；

　　4. 根据这k个样本的标签进行投票，得到最后的分类类别；

　　如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值可通过各种启发式技术来获取，比如，交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。

　　近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。

　　注：马氏距离一定要先给出样本集的统计性质，比如均值向量，协方差矩阵等。关于马氏距离的介绍如下：

　　KNN算法的优点：

　　1. 思想简单，理论成熟，既可以用来做分类也可以用来做回归；

　　2. 可用于非线性分类；

　　3. 训练时间复杂度为O(n)；

　　4. 准确度高，对数据没有假设，对outlier不敏感；

　　缺点：

　　1. 计算量大；

　　2. 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；

　　3. 需要大量的内存；

六.SVM：

　　要学会如何使用libsvm以及一些参数的调节经验，另外需要理清楚svm算法的一些思路：

　　1. svm中的最优分类面是对所有样本的几何裕量最大（为什么要选择最大间隔分类器，请从数学角度上说明？网易深度学习岗位面试过程中有被问到。答案就是几何间隔与样本的误分次数间存在关系：，其中的分母就是样本到分类间隔距离，分子中的R是所有样本中的最长向量值），即：

　　经过一系列推导可得为优化下面原始目标：

　　2. 下面来看看拉格朗日理论：

　　可以将1中的优化目标转换为拉格朗日的形式（通过各种对偶优化，KKD条件），最后目标函数为：

　　我们只需要最小化上述目标函数，其中的α为原始优化问题中的不等式约束拉格朗日系数。

　　3. 对2中最后的式子分别w和b求导可得：

　　由上面第1式子可以知道，如果我们优化出了α，则直接可以求出w了，即模型的参数搞定。而上面第2个式子可以作为后续优化的一个约束条件。

　　4. 对2中最后一个目标函数用对偶优化理论可以转换为优化下面的目标函数：

　　而这个函数可以用常用的优化方法求得α，进而求得w和b。

　　5. 按照道理，svm简单理论应该到此结束。不过还是要补充一点，即在预测时有：

　　那个尖括号我们可以用核函数代替，这也是svm经常和核函数扯在一起的原因。

　　6. 最后是关于松弛变量的引入，因此原始的目标优化公式为：

　　此时对应的对偶优化公式为：

　　与前面的相比只是α多了个上界。

　　SVM算法优点：

　　可用于线性/非线性分类，也可以用于回归；

　　低泛化误差；

　　容易解释；

　　计算复杂度较低；

　　缺点：

　　对参数和核函数的选择比较敏感；

　　原始的SVM只比较擅长处理二分类问题；

七.Boosting：

　　主要以Adaboost为例，首先来看看Adaboost的流程图，如下：

　　从图中可以看到，在训练过程中我们需要训练出多个弱分类器（图中为3个），每个弱分类器是由不同权重的样本（图中为5个训练样本）训练得到（其中第一个弱分类器对应输入样本的权值是一样的），而每个弱分类器对最终分类结果的作用也不同，是通过加权平均输出的，权值见上图中三角形里面的数值。那么这些弱分类器和其对应的权值是怎样训练出来的呢？

　　下面通过一个例子来简单说明。

　　书中（machinelearning in action）假设的是5个训练样本，每个训练样本的维度为2，在训练第一个分类器时5个样本的权重各为0.2.注意这里样本的权值和最终训练的弱分类器组对应的权值α是不同的，样本的权重只在训练过程中用到，而α在训练过程和测试过程都有用到。

　　现在假设弱分类器是带一个节点的简单决策树，该决策树会选择2个属性（假设只有2个属性）的一个，然后计算出这个属性中的最佳值用来分类。

　　Adaboost的简单版本训练过程如下：

　　1. 训练第一个分类器，样本的权值D为相同的均值。通过一个弱分类器，得到这5个样本（请对应书中的例子来看，依旧是machine learning in action）的分类预测标签。与给出的样本真实标签对比，就可能出现误差(即错误)。如果某个样本预测错误，则它对应的错误值为该样本的权重，如果分类正确，则错误值为0. 最后累加5个样本的错误率之和，记为ε。

　　2. 通过ε来计算该弱分类器的权重α，公式如下：