机器学习主流算法

一：机器学习的概念

监督学习：

在监督式学习下，输入数据被称为“训练数据”，每组训练数据有一个明确的标识或结果，如对防垃圾邮件系统中“垃圾邮件”“非垃圾邮件”，对手写数字识别中的“1“，”2“，”3“，”4“等。在建立预测模型的时候，监督式学习建立一个学习过程，将预测结果与“训练数据”的实际结果进行比较，不断的调整预测模型，直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归（Logistic Regression）和反向传递神经网络（Back Propagation Neural Network）

非监督学习：

在非监督式学习中，数据并不被特别标识，学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means算法。

半监督式学习：

在此学习方式下，输入数据部分被标识，部分没有被标识，这种学习模型可以用来进行预测，但是模型首先需要学习数据的内在结构以便合理的组织数据来进行预测。应用场景包括分类和回归，算法包括一些对常用监督式学习算法的延伸，这些算法首先试图对未标识数据进行建模，在此基础上再对标识的数据进行预测。如图论推理算法（Graph Inference）或者拉普拉斯支持向量机（Laplacian SVM.）等。

强化学习：

在这种学习模式下，输入数据作为对模型的反馈，不像监督模型那样，输入数据仅仅是作为一个检查模型对错的方式，在强化学习下，输入数据直接反馈到模型，模型必须对此立刻作出调整。常见的应用场景包括动态系统以及机器人控制等。常见算法包括Q-Learning以及时间差学习（Temporal difference learning）

在企业数据应用的场景下，人们最常用的可能就是监督式学习和非监督式学习的模型。在图像识别等领域，由于存在大量的非标识的数据和少量的可标识数据，目前半监督式学习是一个很热的话题。而强化学习更多的应用在机器人控制及其他需要进行系统控制的领域。

二：机器学习的主流算法

2.1算法的大致类型

根据算法的功能和形式的类似性，我们可以把算法分类，比如说基于树的算法，基于神经网络的算法等等。当然，机器学习的范围非常庞大，有些算法很难明确归类到某一类。而对于有些分类来说，同一分类的算法可以针对不同类型的问题。这里，我们尽量把常用的算法按照最容易理解的方式进行分类。

回归算法：

回归算法是试图采用对误差的衡量来探索变量之间的关系的一类算法。回归算法是统计机器学习的利器。在机器学习领域，人们说起回归，有时候是指一类问题，有时候是指一类算法，这一点常常会使初学者有所困惑。常见的回归算法包括：最小二乘法（Ordinary Least Square），逻辑回归（Logistic Regression），逐步式回归（Stepwise Regression），多元自适应回归样条（Multivariate Adaptive Regression Splines）以及本地散点平滑估计（Locally Estimated Scatterplot Smoothing）

基于实例的算法

基于实例的算法常常用来对决策问题建立模型，这样的模型常常先选取一批样本数据，然后根据某些近似性把新数据与样本数据进行比较。通过这种方式来寻找最佳的匹配。因此，基于实例的算法常常也被称为“赢家通吃”学习或者“基于记忆的学习”。常见的算法包括 k-Nearest Neighbor（KNN）， 学习矢量量化（Learning Vector Quantization， LVQ），以及自组织映射算法（Self-Organizing Map ， SOM）

决策树学习

 决策树算法根据数据的属性采用树状结构建立决策模型，决策树模型常常用来解决分类和回归问题。常见的算法包括：分类及回归树（Classification And Regression Tree， CART）， ID3（Iterative Dichotomiser 3）， C4.5， Chi-squared Automatic Interaction Detection（CHAID）， Decision Stump， 随机森林（Random Forest）， 多元自适应回归样条（MARS）以及梯度推进机（Gradient Boosting Machine， GBM）

 聚类算法

聚类，就像回归一样，有时候人们描述的是一类问题，有时候描述的是一类算法。聚类算法通常按照中心点或者分层的方式对输入数据进行归并。所以的聚类算法都试图找到数据的内在结构，以便按照最大的共同点将数据进行归类。常见的聚类算法包括k-Means算法以及期望最大化算法（Expectation Maximization， EM）。

集成算法：

集成算法用一些相对较弱的学习模型独立地就同样的样本进行训练，然后把结果整合起来进行整体预测。集成算法的主要难点在于究竟集成哪些独立的较弱的学习模型以及如何把学习结果整合起来。这是一类非常强大的算法，同时也非常流行。常见的算法包括：Boosting， Bootstrapped Aggregation（Bagging）， AdaBoost，堆叠泛化（Stacked Generalization， Blending），梯度推进机（Gradient Boosting Machine， GBM），随机森林（Random Forest）。

2.2 常见的部分算法

决策树

使用某些属性将一组数据分类为不同的组中，在每个节点上执行测试，通过brach判断，进一步将数据拆分两个不同的组，此次等等。测试是基于现有的数据进行的，当添加新数据时，可以将其分类为相应的组。

根据某些特征对数据进行分类，每当过程进入下一步时，就会有一个判断分支，并且判断将数据分为两部分，然后过程继续。当对现有数据进行测试时，新数据可以通过现有数据了解这些问题，当有新的数据出现时，计算机可以将数据归类到正确的分支中。

决策树的构建是数据逐步分裂的过程，构建的步骤如下:

步骤1：将所有的数据看成是一个节点，进入步骤2；

步骤2：从所有的数据特征中挑选一个数据特征对节点进行分割，进入步骤3；

步骤3：生成若干孩子节点，对每一个孩子节点进行判断，如果满足停止分裂的条件，进入步骤4；否则，进入步骤2；

步骤4：设置该节点是子节点，其输出的结果为该节点数量占比最大的类别。

 从上述步骤可以看出，决策生成过程中有两个重要的问题：

（1）数据如何分割

（2）如何选择分裂的属性

（3）什么时候停止分裂

决策树的构建算法主要有ID3、C4.5、CART三种，其中ID3和C4.5是分类树，CART是分类回归树，其中ID3是决策树最基本的构建算法，而C4.5和CART是在ID3的基础上进行优化的算法。

对分类结果好坏的度量标准：基尼值、信息熵、信息增益

信息增益（information gain)

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少程度

                              g(D,A)=H(D)-H(D|A)

H（D)数据D的经验熵， H(D|A) 特征A给定条件下D的经验条件熵， 也称为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息

2 逻辑回归

什么是逻辑回归？

逻辑回归其实是一个分类算法而不是回归算法。通常是利用已知的自变量来预测一个离散型因变量的值（像二进制值0/1，是/否，真/假）。简单来说，它就是通过拟合一个逻辑函数（logit fuction）来预测一个事件发生的概率。所以它预测的是一个概率值，自然，它的输出值应该在0到1之间。　　假设你的一个朋友让你回答一道题。可能的结果只有两种：你答对了或没有答对。为了研究你最擅长的题目领域，你做了各种领域的题目。那么这个研究的结果可能是这样的：如果是一道十年级的三角函数题，你有70%的可能性能解出它。但如果是一道五年级的历史题，你会的概率可能只有30%。逻辑回归就是给你这样的概率结果。

逻辑回归用途

寻找危险因素：寻找某一疾病的危险因素等；

预测：根据模型，预测在不同的自变量情况下，发生某病或某种情况的概率有多大；

判别：实际上跟预测有些类似，也是根据模型，判断某人属于某病或属于某种情况的概率有多大，也就是看一下这个人有多大的可能性是属于某病。

Regression 常规步骤

1 寻找h函数（即预测函数）

2 构造J函数（损失函数）

3 想办法使得J函数最小并求得回归参数（θ）

 3 神经网络

眼下最热门的技术，绝对是人工智能。人工智能的底层模型是"神经网络"（neural network）。许多复杂的应用（比如模式识别、自动控制）和高级模型（比如深度学习）都基于它。学习人工智能，一定是从它开始。

历史上，科学家一直希望模拟人的大脑，造出可以思考的机器。人为什么能够思考？科学家发现，原因在于人体的神经网络。既然思考的基础是神经元，如果能够"人造神经元"（artificial neuron），就能组成人工神经网络，模拟思考。上个世纪六十年代，提出了最早的"人造神经元"模型，叫做"感知器"（perceptron），直到今天还在用。

上图的圆圈就代表一个感知器。它接受多个输入（x1，x2，x3...），产生一个输出（output），好比神经末梢感受各种外部环境的变化，最后产生电信号。

为了简化模型，我们约定每种输入只有两种可能：1 或 0。如果所有输入都是1，表示各种条件都成立，输出就是1；如果所有输入都是0，表示条件都不成立，输出就是0。

下面来看一个例子。城里正在举办一年一度的游戏动漫展览，小明拿不定主意，周末要不要去参观。

他决定考虑三个因素：

天气：周末是否晴天？

同伴：能否找到人一起去？

价格：门票是否可承受？

这就构成一个感知器。上面三个因素就是外部输入，最后的决定就是感知器的输出。如果三个因素都是Yes（使用1表示），输出就是1（去参观）；如果都是 No（使用0表示），输出就是0（不去参观）。

看到这里，你肯定会问：如果某些因素成立，另一些因素不成立，输出是什么？比如，周末是好天气，门票也不贵，但是小明找不到同伴，他还要不要去参观呢？

现实中，各种因素很少具有同等重要性：某些因素是决定性因素，另一些因素是次要因素。因此，可以给这些因素指定权重（weight），代表它们不同的重要性。

天气：权重为8

同伴：权重为4

价格：权重为4

上面的权重表示，天气是决定性因素，同伴和价格都是次要因素。

如果三个因素都为1，它们乘以权重的总和就是 8 + 4 + 4 = 16。如果天气和价格因素为1，同伴因素为0，总和就变为 8 + 0 + 4 = 12。

这时，还需要指定一个阈值（threshold）。如果总和大于阈值，感知器输出1，否则输出0。假定阈值为8，那么 12 > 8，小明决定去参观。阈值的高低代表了意愿的强烈，阈值越低就表示越想去，越高就越不想去。

上面的决策过程，使用数学表达如下。

单个的感知器构成了一个简单的决策模型，已经可以拿来用了。真实世界中，实际的决策模型则要复杂得多，是由多个感知器组成的多层网络。

一个神经网络的搭建，需要满足三个条件：输入和输出、权重（w）和阈值（b）、多层感知器的结构。

其中，最困难的部分就是确定权重（w）和阈值（b）。目前为止，这两个值都是主观给出的，但现实中很难估计它们的值，必需有一种方法，可以找出答案。

这种方法就是试错法。其他参数都不变，w（或b）的微小变动，记作Δw（或Δb），然后观察输出有什么变化。不断重复这个过程，直至得到对应最精确输出的那组w和b，就是我们要的值。这个过程称为模型的训练。

因此，神经网络的运作过程如下。

1 确定输入和输出

2 找到一种或多种算法，可以从输入得到输出

3 找到一组已知答案的数据集，用来训练模型，估算w和b

4 一旦新的数据产生，输入模型，就可以得到结果，同时对w和b进行校正

三：算法的应用场景

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

14年的时候有人做过一个实验[1]，比较在不同数据集上（121个），不同的分类器（179个）的实际效果。

随机森林平均来说最强，但也只在9.9%的数据集上拿到了第一，优点是鲜有短板。

SVM的平均水平紧随其后，在10.7%的数据集上拿到第一。

神经网络（13.2%）和boosting（9%）表现不错。

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

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

近邻(Nearest Neighbor)

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

适用情景：

需要一个特别容易解释的模型的时候。

比如需要向用户解释原因的推荐算法。

贝叶斯(Bayesian)

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

适用情景：

需要一个比较容易解释，而且不同维度之间相关性较小的模型的时候。可以高效处理高维数据，虽然结果可能不尽如人意。

决策树(Decision tree)

决策树的特点是它总是在沿着特征做切分。随着层层递进，这个划分会越来越细。虽然生成的树不容易给用户看，但是数据分析的时候，通过观察树的上层结构，能够对分类器的核心思路有一个直观的感受。

举个简单的例子，当我们预测一个孩子的身高的时候，决策树的第一层可能是这个孩子的性别。男生走左边的树进行进一步预测，女生则走右边的树。这就说明性别对身高有很强的影响。

适用情景：

因为它能够生成清晰的基于特征(feature)选择不同预测结果的树状结构，数据分析师希望更好的理解手上的数据的时候往往可以使用决策树。同时它也是相对容易被攻击的分类器。这里的攻击是指人为的改变一些特征，使得分类器判断错误。常见于垃圾邮件躲避检测中。因为决策树最终在底层判断是基于单个条件的，攻击者往往只需要改变很少的特征就可以逃过监测。受限于它的简单性，决策树更大的用处是作为一些更有用的算法的基石。

随机森林(Random forest)

提到决策树就不得不提随机森林。顾名思义，森林就是很多树。严格来说，随机森林其实算是一种集成算法。它首先随机选取不同的特征(feature)和训练样本(training sample)，生成大量的决策树，然后综合这些决策树的结果来进行最终的分类。随机森林在现实分析中被大量使用，它相对于决策树，在准确性上有了很大的提升，同时一定程度上改善了决策树容易被攻击的特点。

适用情景：

数据维度相对低（几十维），同时对准确性有较高要求时。因为不需要很多参数调整就可以达到不错的效果，基本上不知道用什么方法的时候都可以先试一下随机森林。

神经网络(Neural network)

它的核心思路是利用训练样本(training sample)来逐渐地完善参数。还是举个例子预测身高的例子，如果输入的特征中有一个是性别（1:男；0:女），而输出的特征是身高（1:高；0:矮）。那么当训练样本是一个个子高的男生的时候，在神经网络中，从“男”到“高”的路线就会被强化。同理，如果来了一个个子高的女生，那从“女”到“高”的路线就会被强化。最终神经网络的哪些路线比较强，就由我们的样本所决定。

神经网络的优势在于，它可以有很多很多层。如果输入输出是直接连接的，那它和LR就没有什么区别。但是通过大量中间层的引入，它就能够捕捉很多输入特征之间的关系。卷积神经网络有很经典的不同层的可视化展示(visulization)，我这里就不赘述了。

神经网络的提出其实很早了，但是它的准确率依赖于庞大的训练集，原本受限于计算机的速度，分类效果一直不如随机森林和SVM这种经典算法。

使用情景：

数据量庞大，参数之间存在内在联系的时候。

当然现在神经网络不只是一个分类器，它还可以用来生成数据，用来做降维，这些就不在这里讨论了。