机器学习常见算法总结

机器学习常见算法总结

机器学习算法分类

决策树算法 根据数据属性，采用树状结构建立决策模型。常用来解决分类和回归问题。 常见算法：CART(Classification And Regression Tree)，ID3，C4.5，随机森林等 回归算法 对连续值预测，如逻辑回归LR等 分类算法 对离散值预测，事前已经知道分类，如k-近邻算法 聚类算法 对离散值预测，事前对分类未知，如k-means算法 神经网络 模拟生物神经网络，可以用来解决分类和回归问题 感知器神经网络(Perceptron Neural Network) ，反向传递(Back Propagation)和深度学习（DL） 集成算法 集成几种学习模型进行学习，将最终预测结果进行汇总 Boosting、Bagging、AdaBoost、随机森林 (Random Forest) 等

SVM

1、SVM不太容易过拟合：松弛因子+损失函数形式

SVM的求解方法叫拉格朗日乘子法

有时候如果你非要很明确地分类，那么结果就会像右边的一样 —— 过拟合。明显左边的两个都比过拟合好多了，可是这样就要求允许一些样本不在正确的类上.

目标：找出总损失值最小并且能大概分类的超平面

2、方法选择

1、如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM
2、如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel
3、如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况

3、数据维度 如果数据特征维度高，svm要使用核函数来求解

Note：拉格朗日对偶没有改变最优解，但改变了算法复杂度：原问题—样本维度；对偶问题–样本数量。
线性分类            样本维度<样本数量：原问题求解（liblinear默认）； 
非线性–升维—一般导致 样本维度>样本数量：对偶问题求解

朴素贝叶斯

朴素贝叶斯的优点： 对小规模的数据表现很好，适合多分类任务，适合增量式训练。 缺点： 对输入数据的表达形式很敏感（离散、连续，值极大极小之类的）

线性回归

线性回归试图学得一个线性模型以尽可能准确地预测实值输出标记。均方误差是回归任务中最常用的性能度量，基于均方误差最小化来进行模型求解的方法成为最小二乘法。在线性回归中，最小二乘法就是试图找到一条直线，使得所有样本到直线上的欧式距离之和最小。这个想法和分类问题是正好相反的，分类问题是找到一个分界面离所有样本尽可能远。

优化方法

当x矩阵是列满秩的时候，可以用最小二乘法，但是求矩阵的逆比较慢

机器学习算法选择

没有最好的分类器，只有最合适的分类器。

数据维度越高，随机森林就比AdaBoost强越多，但是整体不及SVM。

数据量越大，神经网络就越强。

1、K近邻

典型KNN，它的思路就是——对于待判断的点，找到离它最近的几个数据点，根据它们的类型决定待判断点的类型。 它的特点是完全跟着数据走，没有数学模型可言。

适用情景：
需要一个特别容易解释的模型的时候。
比如需要向用户解释原因的推荐算法。

2、贝叶斯

典型的例子是Naive Bayes，核心思路是根据条件概率计算待判断点的类型。是相对容易理解的一个模型，至今依然被垃圾邮件过滤器使用。

适用情景：

需要一个比较容易解释，而且不同维度之间相关性较小的模型的时候。

可以高效处理高维数据，虽然结果可能不尽如人意。

3、决策树 (Decision tree)

决策树的特点是它总是在沿着特征做切分。随着层层递进，这个划分会越来越细。 举个简单的例子，当我们预测一个孩子的身高的时候，决策树的第一层可能是这个孩子的性别。男生走左边的树进行进一步预测，女生则走右边的树。这就说明性别对身高有很强的影响。

适用情景：
同时它也是相对容易被攻击的分类器。这里的攻击是指人为的改变一些特征，使得分类器判断错误。常见于垃圾邮件躲避检测中。因为决策树最终在底层判断是基于单个条件的，攻击者往往只需要改变很少的特征就可以逃过监测。受限于它的简单性，决策树更大的用处是作为一些更有用的算法的基石。

随机森林 (Random forest)

随机森林其实算是一种集成算法。它首先随机选取不同的特征(feature)和训练样本(training sample)，生成大量的决策树，然后综合这些决策树的结果来进行最终的分类。

它相对于决策树，在准确性上有了很大的提升，同时一定程度上改善了决策树容易被攻击的特点。

适用情景：

数据维度相对低（几十维），同时对准确性有较高要求时。

因为不需要很多参数调整就可以达到不错的效果，基本上不知道用什么方法的时候都可以先试一下随机森林。

优化问题的求解方法

大部分的机器学习算法的本质都是建立优化模型，通过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。

1、梯度下降法

优化思想

当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。

缺点 梯度下降法的最大问题就是会陷入局部最优，靠近极小值时收敛速度减慢。

2、批量梯度下降法

最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。

3、随机梯度下降法

最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。

随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

4、牛顿法

牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f (x)的泰勒级数的前面几项来寻找方程f (x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。

牛顿法比梯度下降法快

牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。

但是牛顿法要算hessian矩阵的逆，比较费时间。

5、拟牛顿法

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。

6、拉格朗日法

拉格朗日乘数法

拉格朗日乘子法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。

通过引入拉格朗日乘子建立极值条件，对n个变量分别求偏导对应了n个方程，然后加上k个约束条件（对应k个拉格朗日乘子）一起构成包含了（n+k）变量的（n+k）个方程的方程组问题，这样就能根据求方程组的方法对其进行求解

过拟合：

如果一味的去提高训练数据的预测能力，所选模型的复杂度往往会很高，这种现象称为过拟合。所表现的就是模型训练时候的误差很小，但在测试的时候误差很大。

训练模型很好用，测试时候误差较大

参考