机器学习面试题精讲（一）
环境说明：
Python 2.7；
Sklearn 0.19.0；
graphviz 0.8.1 决策树可视化。
1. 决策树
1.1 原理
顾名思义，决策树就是用一棵树来表示我们的整个决策过程。这棵树可以是二叉树（比如 CART 只能是二叉树），也可以是多叉树（比如 ID3、C4.5 可以是多叉树或二叉树）。
根节点包含整个样本集，每个叶节都对应一个决策结果（注意，不同的叶节点可能对应同一个决策结果），每一个内部节点都对应一次决策过程或者说是一次属性测试。从根节点到每个叶节点的路径对应一个判定测试序列。
举个例子：
就像上面这个例子，训练集由三个特征：outlook(天气)，humidity（湿度），windy（是否有风）。
那么我们该如何选择特征对训练集进行划分那？连续型特征（比如湿度）划分的阈值又是如何确定的？
决策树的生成就是不断的选择最优的特征对训练集进行划分，是一个递归的过程。递归返回的条件有三种：
（1）当前节点包含的样本属于同一类别，无需划分；
（2）当前属性集为空，或所有样本在属性集上取值相同，无法划分；
（3）当前节点包含样本集合为空，无法划分。
1.2 ID3、C4.5、CART
这三个是非常著名的决策树算法。简单粗暴来说，ID3 使用信息增益作为选择特征的准则；C4.5 使用信息增益比作为选择特征的准则；CART 使用 Gini 指数作为选择特征的准则。
ID3：熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。
信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。
ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。
C4.5：克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。
C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。
CART：与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。
CART 的全称是分类与回归树。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。
回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。
要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。
分类树种，使用 Gini 指数最小化准则来选择特征并进行划分；
Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。
1.3 信息增益 vs 信息增益比
之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。
1.4 Gini 指数 vs 熵
既然这两个都可以表示数据的不确定性，不纯度。那么这两个有什么区别那？
Gini 指数的计算不需要对数运算，更加高效；
Gini 指数更偏向于连续属性，熵更偏向于离散属性。
1.5 剪枝
决策树算法很容易过拟合（overfitting），剪枝算法就是用来防止决策树过拟合，提高泛华性能的方法。
剪枝分为预剪枝与后剪枝。
预剪枝是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。
后剪枝是指先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。
那么怎么来判断是否带来泛化性能的提升那？最简单的就是留出法，即预留一部分数据作为验证集来进行性能评估。
1.6 总结
决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。
特征选择。特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则：信息增益、信息增益比、Gini 指数；
决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始，递归的生成决策树。相当于是不断选取局部最优特征，或将训练集分割为基本能够正确分类的子集；
决策树的剪枝。决策树的剪枝是为了防止树的过拟合，增强其泛化能力。包括预剪枝和后剪枝。
2. 随机森林（Random Forest）
要说随机森林就要先说 Bagging，要说 Bagging 就要先说集成学习。
2.1 集成学习方法
集成学习（ensemble learning）通过构建并组合多个学习器来完成学习任务。集成学习通过将多个学习器进行结合，常获得比单一学习器显著优越的泛化性能。
根据个体学习器是否是同类型的学习器（由同一个算法生成，比如 C4.5,BP 等），分为同质和异质。同质的个体学习器又叫做基学习器，而异质的个体学习器则直接成为个体学习器。
原则：要获得比单一学习器更好的性能，个体学习器应该好而不同。即个体学习器应该具有一定的准确性，不能差于弱学习器，并且具有多样性，即学习器之间有差异。
根据个体学习器的生成方式，目前集成学习分为两大类：
个体学习器之间存在强依赖关系、必须串行生成的序列化方法。代表是 Boosting；
个体学习器之间不存在强依赖关系、可同时生成的并行化方法。代表是 Bagging 和随机森林（Random Forest）。
2.2 Bagging
前面提到，想要集成算法获得性能的提升，个体学习器应该具有独立性。虽然 “独立” 在现实生活中往往无法做到，但是可以设法让基学习器尽可能的有较大的差异。
Bagging 给出的做法就是对训练集进行采样，产生出若干个不同的子集，再从每个训练子集中训练一个基学习器。由于训练数据不同，我们的基学习器可望具有较大的差异。
Bagging 是并行式集成学习方法的代表，采样方法是自助采样法，用的是有放回的采样。初始训练集中大约有 63.2% 的数据出现在采样集中。
Bagging 在预测输出进行结合时，对于分类问题，采用简单投票法；对于回归问题，采用简单平均法。
Bagging 优点：
高效。Bagging 集成与直接训练基学习器的复杂度同阶；
Bagging 能不经修改的适用于多分类、回归任务；
包外估计。使用剩下的样本作为验证集进行包外估计（out-of-bag estimate）。
Bagging 主要关注降低方差。（low variance）
2.3 随机森林（Random Forest）
2.3.1 原理
随机森林（Random Forest）是 Bagging 的一个变体。Ramdon Forest 在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入随机属性选择。
原来决策树从所有属性中，选择最优属性。Ramdom Forest 的每一颗决策树中的每一个节点，先从该节点的属性集中随机选择 K 个属性的子集，然后从这个属性子集中选择最优属性进行划分。
K 控制了随机性的引入程度，是一个重要的超参数。
预测 ：
分类：简单投票法；
回归：简单平均法。
2.3.2 优缺点
优点：
由于每次不再考虑全部的属性，而是一个属性子集，所以相比于 Bagging 计算开销更小，训练效率更高；
由于增加了属性的扰动，随机森林中基学习器的性能降低，使得在随机森林在起始时候性能较差，但是随着基学习器的增多，随机森林通常会收敛于更低的泛化误差，相比于 Bagging；
两个随机性的引入，使得随机森林不容易陷入过拟合，具有很好的抗噪声能力；
对数据的适应能力强，可以处理离散和连续的，无需要规范化；
可以得到变量的重要性， 基于 oob 误分类率和基于 Gini 系数的变化。
缺点：在噪声较大的时候容易过拟合。
3. AdaBoost
AdaBoost 是 Boosting 的代表，前面我们提到 Boosting 是集成学习中非常重要的一类串行化学习方法。
3.1 Boosting
Boosting 是指个体学习器之间存在强依赖关系，必须串行序列化生成的集成学习方法。他的思想来源是三个臭皮匠顶个诸葛亮。Boosting 意为提升，意思是希望将每个弱学习器提升为强学习器。
工作机制如下：
先从初始训练集中学习一个基学习器；
根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续收到更多关注；
基于调整后的样本分布来训练下一个基学习器；
如此反复，直到基学习器数目达到 T，最终将这 T 个基学习器进行加权结合。
对训练样本分布调整，主要是通过增加误分类样本的权重，降低正确分类样本的权重。
Boosting 关注的主要是降低偏差。（low bias）
3.2 AdaBoost 原理
面临两个问题：
（1）在每一轮，如何改变训练数据的概率分布或者权值分布。（也可以重采样，但是 AdaBoost 没这么做）；
（2）如何将弱分类器组合成强分类器。
AdaBoost 的做法：
（1）提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类的样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮弱分类器的关注；
（2）采用加权多数表决。具体的，加大分类错误率低的分类器的权值，使其在表决中起较大作用，减少分类误差率大的弱分类器的权值，使其在表决中起较小作用。
弱分类器被线性组合成为一个强分类器。
训练目标：最小化指数损失函数。
三部分组成：
（1）分类器权重更新公式；
（2）样本分布（也就是样本权重）更新公式；
（3）加性模型。 最小化指数损失函数。
3.3 AdaBoost 优缺点
优点：
不改变所给的训练数据，而不断改变训练数据的权值分布，使得训练数据在基本分类器的学习中起不同的作用。这是 AdaBoost 的一个特点；
利用基本分类器的加权线性组合构建最终分类器，是 AdaBoost 的另一个特点；
AdaBoost 被实践证明是一种很好的防止过拟合的方法，但至今为什么至今没从理论上证明。
缺点：AdaBoost 只适用于二分类问题。
BAT机器学习面试题：
相关内容
微信扫码咨询专知VIP会员