6-2 经典机器学习算法原理整理（上）
在上一章节中，我们讲到数据分析岗对于算法知识的考察不会太深，建议在面试前，从原理-优缺点-应用场景-延伸提问等角度做好准备。
在介绍算法之前，我们先回顾一下监督学习和无监督学习的概念。
监督学习是指对具有标记的训练样本进行学习，以尽可能对训练样本集外的数据进行分类预测。基础的监督学习模型包括决策树，逻辑回归，KNN，随机森林，GBDT等等。
无监督学习是指对未标记的样本进行训练学习。基础的无监督学习模型包括K-Means, PCA等等。
以下是我整理的常见算法：
【监督学习】
一 、决策树
1.原理
决策树：决策树是一种对样本进行分类的树形结构，也能够进行回归预测。决策树主要包含3种结点（根节点：初始结点；叶节点：最终分类结果结点；内结点：树内部进行判断的条件结点-即特征），在决策树中，每一个样本都只会被一条路径覆盖。
决策树常见的生成算法有三种，ID3，C4.5以及Cart。以ID3算法为例介绍一下决策树的生成原理。
第一步，计算信息增益。ID3算法是利用信息增益进行特征选择的。信息增益是指，已知某一特征xi后，使得样本整体特征不确定性减少的程度。
信息： 特征越不确定，包含的信息越大。
)
信息熵：可以衡量特征到底多不确定。信息熵越小，不确定性越低。
log_%7B2%7Dp(x_%7Bi%7D)%7D)
信息增益：使用该特征分类前的信息熵– 使用该特征分类后的信息熵
**其中，p(xi)代表随机变量X=xi时的概率。
第二步，选择特征。在每个节点上利用信息增益进行特征的选择，在选择特征时，优先选择信息增益最大的特征。直到剩余特征的信息增益小于阈值、或已经没有特征可以选择时终止。
第三步，对决策树进行剪枝优化。构建决策树的损失函数（与预测误差以及树的复杂度有关，是两者的权衡），将每一个叶节点回缩到上一层父节点，对损失函数最小的叶节点进行修剪。假设决策树有叶子节点的数量为|T|, t为某叶节点，该叶节点下有Nt个样本，其中类别为k的样本有Nik个，Ht(T)代表节点t的信息熵，并假设α>0，则损失函数为
将第一个公式的第一项记为：
则可以得到：
在这里，C(T)表示决策树在训练数据时的误差，|T|代表模型的复杂度，在误差和负责度之间需要进行权衡。α越大，代表我们希望选择简单的模型。
C4.5算法的过程与ID3类似，只是使用了信息增益比而非信息增益进行计算，而CART算法则是使用基尼指数进行选择。
2.优缺点
决策树的优势包括: ①输出树形图可解释性较强，if-then形式，逻辑性很好理解；②对输入数据的属性要求低（分类，连续）。
劣势包括：①当数据集特征维度很多时，决策树会生成许多枝干，或者树非常深，陷入过拟合；②判定过程很规则，在垃圾邮件的分类过程中，容易被攻击。③忽视了特征之间的相关性。
3.应用场景
分类（银行客户贷款分类；垃圾邮件分类等），作为复杂机器学习模型的基础模型（随机森林）
4.延伸提问
（1）如何防止过拟合？
①进行剪枝，处理由于数据中的噪声和离群点导致的过分拟合问题。包括先剪枝和后剪枝。先剪枝——在构造过程中，当某个节点满足剪枝条件，则直接停止此分支的构造。后剪枝——先构造完成完整的决策树，再通过某些条件遍历树进行剪枝。
②利用K−folds交叉验证，将训练集分为K份，然后进行K次交叉验证，每次使用K−1份作为训练样本数据集，另外一份作为测试集。
（2）决策树需要进行归一化处理吗？
不需要。一方面，决策树是一种树模型，树模型不能梯度下降，归一化没有意义。另一方面，决策树分裂跟特征的绝对大小无关。
二 、随机森林
1.原理
随机森林和决策树有很密切的联系。决策树比较容易产生过拟合的行为，而随机森林就是让很多决策树一起进行工作，采用大多数决策树的输出结果作为最终预测结果。
假如我有训练样本集D，构建随机森林的步骤为：
①抽取样本：假设随机森林中有n颗决策树，那么每棵树都需要各m个样本进行训练，并且这m个样本是通过可放回的方式从样本总体中抽取的。
②抽取特征：如果样本D共有x个特征，那么每颗树都会从x中选择k个特征，然后采用（ID3，C4.5，CART）算法来获得一棵决策树；
③重复m次，得到m颗决策树（建立树的过程是同时运行的）；
④采用多数投票法则输出最后的预测结果。
2.优缺点
优势：①有效解决决策树的过拟合问题；②能够处理特征维度很多的数据，并且不需要做特征的选择；③可以解决回归以及分类问题。
劣势：①特征维度较小的数据不适合采用②由于算法本身的复杂性，相对于决策树等需要花费更多的时间来训练。
3.应用场景
随机森林可以用来预测贷款风险，银行和证券使用较多; 调参简单，不知道用什么算法的时候都可以试试随机森林。
4.延伸提问
（
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
校招面试考点全解析——数据分析师篇 文章被收录于专栏
<p> 为什么要学习本专刊 （1）数据分析面试日益激烈，招聘门槛提高，对业务、技术的综合考察难度上升； （2）网上对数据分析面试题型的整理与解析质量参差不齐，缺少框架清晰、内容全面的学习资料； （3）直击数据分析面试热点问题； </p>
网易有道公司氛围 36人发布
