机器学习算法选择
来自： http://www.csuldw.com/2016/02/26/2016-02-26-choosing-a-machine-learning-classifier/
本文主要回顾下几个常用算法的适应场景和优缺点！
对于你的分类问题，你知道应该如何选择哪一个机器学习算法么？当然，如果你真的在乎精度（accuracy），最好的方法就是通过交叉验证（cross-validation）对各个算法一个个地进行测试，进行比较，然后调整参数确保每个算法达到最优解，最后选择最好的一个。但是如果你只是在寻找一个“good enough”的算法来解决你的问题，或者这里有些技巧可以参考，因为其中会有一些基本准则。
数据集大小
首先来普及一下偏差和方差
-
偏差：描述的是预测值（估计值）的期望E’与真实值T之间的差距。偏差越大，越偏离真实数据。
-
方差：描述的是预测值P的变化范围，离散程度，也就是离其期望值E的距离。方差越大，数据的分布越分散。
如果是小训练集，高偏差/低方差的分类器（例如，朴素贝叶斯NB）要比低偏差/高方差大分类的优势（例如，KNN），因为后者会过度拟合。但是，随着你训练集的增长，低偏差/高方差分类器就会渐渐的表现其优势（因为它们有较低的渐近误差），因为高偏差分类器此时已经不足以提供准确的模型。
当然，你也可以认为这是生成模型与判别模型的一个区别。
为什么说朴素贝叶斯是高偏差低方差?
以下内容引自知乎：
首先，假设你知道训练集和测试集的关系。简单来讲是我们要在训练集上学习一个模型，然后拿到测试集去用，效果好不好要根据测试集的错误率来衡量。但很多时候，我们只能假设测试集和训练集的是符合同一个数据分布的，但却拿不到真正的测试数据。这时候怎么在只看到训练错误率的情况下，去衡量测试错误率呢？
由于训练样本很少（至少不足够多），所以通过训练集得到的模型，总不是真正正确的。（就算在训练集上正确率100%，也不能说明它刻画了真实的数据分布，要知道刻画真实的数据分布才是我们的目的，而不是只刻画训练集的有限的数据点）。而且，实际中，训练样本往往还有一定的噪音误差，所以如果太追求在训练集上的完美而采用一个很复杂的模型，会使得模型把训练集里面的误差都当成了真实的数据分布特征，从而得到错误的数据分布估计。这样的话，到了真正的测试集上就错的一塌糊涂了（这种现象叫过拟合）。但是也不能用太简单的模型，否则在数据分布比较复杂的时候，模型就不足以刻画数据分布了（体现为连在训练集上的错误率都很高，这种现象较欠拟合）。过拟合表明采用的模型比真实的数据分布更复杂，而欠拟合表示采用的模型比真实的数据分布要简单。
在统计学习框架下，大家刻画模型复杂度的时候，有这么个观点，认为Error = Bias + Variance。这里的Error大概可以理解为模型的预测错误率，是有两部分组成的，一部分是由于模型太简单而带来的估计不准确的部分（Bias），另一部分是由于模型太复杂而带来的更大的变化空间和不确定性（Variance）。
所以，这样就容易分析朴素贝叶斯了。它简单的假设了各个数据之间是无关的，是一个被严重简化了的模型。所以，对于这样一个简单模型，大部分场合都会Bias部分大于Variance部分，也就是说高偏差而低方差。
在实际中，为了让Error尽量小，我们在选择模型的时候需要平衡Bias和Variance所占的比例，也就是平衡over-fitting和under-fitting。
一些常见算法的优势
1.朴素贝叶斯
属于生成式模型，非常简单，你只是做了一堆计数。如果注有条件独立性假设，朴素贝叶斯分类器的收敛速度将快于判别模型，如逻辑回归，所以你只需要较少的训练数据即可。即使NB条件独立假设不成立，NB分类器在实践中仍然表现的很出色。它的主要缺点是它不能学习特征件的相互作用（例如，它不能学习出虽然你喜欢Brad Pitt和Tom Cruise的电影，但是你不喜欢他们在一起演的电影）。
优点：对小规模的数据表现很好，适合多分类任务，适合增量式训练。
缺点：对输入数据的表达形式很敏感。
2.Logistic Regression（逻辑回归）
属于判别式模型，有很多正则化模型的方法（L0， L1， L2, etc），而且你不必像在用朴素贝叶斯那样担心你的特征是否相关。与决策树与SVM机相比，你还会得到一个不错的概率解释，你甚至可以轻松地利用新数据来更新模型（使用在线梯度下降算法）。如果你需要一个概率架构（比如，简单地调节分类阈值，指明不确定性，或者是要获得置信区间），或者你希望以后将更多的训练数据快速整合到模型中去，那么使用它吧。
Sigmoid函数：
$$f(x) = \frac{1}{1+e^{-x}}$$
优点：
- 实现简单，广泛的应用于工业问题上；
- 分类时计算量非常小，速度很快，存储资源低；
- 便利的观测样本概率分数；
- 对逻辑回归而言，多重共线性并不是问题，它可以结合L2正则化来解决该问题；
缺点：
- 当特征空间很大时，逻辑回归的性能不是很好；
- 容易 欠拟合 ，一般准确度不太高
- 不能很好地处理大量多类特征或变量；
- 只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须 线性可分 ；
- 对于非线性特征，需要进行转换；
3.线性回归
线性回归是用于回归的，而不像Logistic回归是用于分类，其基本思想是用 梯度下降法 对最小二乘法形式的误差函数进行优化，当然也可以用normal equation直接求得参数的解，结果为：
$$ \hat{w}=(X^{T}X)^{-1}X^Ty$$
而在LWLR（局部加权线性回归）中，参数的计算表达式为:
$$ \hat{w}=(X^{T}WX)^{-1}X^TWy$$
由此可见LWLR与LR不同，LWLR是一个非参数模型，因为每次进行回归计算都要遍历训练样本至少一次。
优点： 实现简单，计算简单；
缺点： 不能拟合非线性数据.
4.最近领算法——KNN
KNN即最近邻算法，其主要过程为：
1. 计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）； 2. 对上面所有的距离值进行排序； 3. 选前k个最小距离的样本； 4. 根据这k个样本的标签进行投票，得到最后的分类类别；
如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值可通过各种启发式技术来获取，比如，交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。
近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。
KNN算法的优点
- 思想简单，理论成熟，既可以用来做分类也可以用来做回归；
- 可用于非线性分类；
- 训练时间复杂度为O(n)；
- 准确度高，对数据没有假设，对outlier不敏感；
缺点
- 计算量大；
- 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
- 需要大量的内存；
5.决策树
易于解释。它可以毫无压力地处理特征间的交互关系并且是非参数化的，因此你不必担心异常值或者数据是否线性可分（举个例子，决策树能轻松处理好类别A在某个特征维度x的末端，类别B在中间，然后类别A又出现在特征维度x前端的情况）。它的缺点之一就是不支持在线学习，于是在新样本到来后，决策树需要全部重建。另一个缺点就是容易出现过拟合，但这也就是诸如随机森林RF（或提升树boosted tree）之类的集成方法的切入点。另外，随机森林经常是很多分类问题的赢家（通常比支持向量机好上那么一丁点），它训练快速并且可调，同时你无须担心要像支持向量机那样调一大堆参数，所以在以前都一直很受欢迎。
决策树中很重要的一点就是选择一个属性进行分枝，因此要注意一下信息增益的计算公式，并深入理解它。
信息熵的计算公式如下:
$$H=-\sum^{n}_{i=1}p(x_i)log_2p(x_i)$$
其中的n代表有n个分类类别（比如假设是2类问题，那么n=2）。分别计算这2类样本在总样本中出现的概率p1和p2，这样就可以计算出未选中属性分枝前的信息熵。
现在选中一个属性$x_i$用来进行分枝，此时分枝规则是：如果$x_i=v$的话，将样本分到树的一个分支；如果不相等则进入另一个分支。很显然，分支中的样本很有可能包括2个类别，分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’ =p1 H1+p2 H2,则此时的信息增益ΔH = H - H’。以信息增益为原则，把所有的属性都测试一边，选择一个使增益最大的属性作为本次分枝属性。
决策树自身的优点
- 计算简单，易于理解，可解释性强；
- 比较适合处理有缺失属性的样本；
- 能够处理不相关的特征。
缺点
- 容易发生过拟合（随机森林可以很大程度上减少过拟合）。
6.支持向量机
高准确率，为避免过拟合提供了很好的理论保证，而且就算数据在原特征空间线性不可分，只要给个合适的核函数，它就能运行得很好。在动辄超高维的文本分类问题中特别受欢迎。可惜内存消耗大，难以解释，运行和调参也有些烦人，而随机森林却刚好避开了这些缺点，比较实用。
优点
- 能够处理大型特征空间
- 能够处理非线性特征的相互作用
- 无需依赖整个数据
缺点
- 当观测样本很多时，效率并不是很高
- 有时候很难找到一个合适的核函数
算法选择参考
- 首当其冲应该选择的就是逻辑回归，如果它的效果不怎么样，那么可以将它的结果作为基准来参考；
- 然后试试决策树（随机森林）是否可以大幅度提升模型性能。即使你并没有把它当做最终模型，你也可以使用随机森林来移除噪声变量；
- 如果特征的数量和观测样本特别多，那么当资源和时间充足时，使用SVM不失为一种选择。
尽管如此，回想一下， 好的数据却要优于好的算法 ，设计优良特征是大有裨益的。假如你有一个超大数据集，那么无论你使用哪种算法可能对分类性能都没太大影响（此时就可以根据速度和易用性来进行抉择）。
参考文献
[1] http://blog.echen.me/2011/04/27/choosing-a-machine-learning-classifier/
</div>