3.算法流程
3.1、ID3算法
3.1.1、思想
从信息论的知识中可以知道，期望信息越小，信息熵越大，从而样本纯度越低。ID3算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。
3.1.2、划分标准
ID3 使用的分类标准是信息增益，它表示得知特征 A 的信息而使得样本集合不确定性减少的程度。
3.1.3、算法步骤
3.1.4、缺点
1、ID3 没有剪枝策略，容易过拟合；
2、信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
3、只能用于处理离散分布的特征；
4、没有考虑缺失值。
3.2、C4.5算法
3.2.1、思想
C4.5算法相对于ID3算法的缺点对应有以下改进方式：
1、引入悲观剪枝策略进行后剪枝；
2、引入信息增益率作为划分标准；
3、将连续特征离散化，假设n个样本的连续特征A有m个取值，C4.5将其排序并取相邻两样本值的平均数共m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
4、对于缺失值的处理可以分为两个子问题：
4.1. 在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
4.2. 选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
针对问题4.1，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
针对问题4.2，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。
3.2.2、划分标准
利用信息增益率可以克服信息增益的缺点，这里需要注意，信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。
3.2.3、剪枝策略
为什么要剪枝：过拟合的树在泛化能力的表现非常差。
3.2.4、预剪枝
在节点划分前来确定是否继续增长，及早停止增长的主要方法有：
1、节点内数据样本低于某一阈值；
2、所有节点特征都已分裂；
3、节点划分前准确率比划分后准确率高。
预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。
3.2.5、后剪枝
在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。
C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。
后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。
3.2.6、算法步骤
3.2.7、缺点
1、剪枝策略可以再优化；
2、C4.5 用的是多叉树，用二叉树效率更高；
3、C4.5 只能用于分类；
4、C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
5、C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。
3.3、CART算法
3.3.1、思想
CART 包含的基本过程有分裂，剪枝和树选择。
分裂：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
剪枝：采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
树选择：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。
CART 在 C4.5 的基础上进行了很多提升。
C4.5为多叉树，运算速度慢，CART 为二叉树，运算速度快；
C4.5只能分类，CART 既可以分类也可以回归；
CART使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
CART采用代理测试来估计缺失值，而C4.5以不同概率划分到不同节点中；
CART采用“基于代价复杂度剪枝”方法进行剪枝，而C4.5采用悲观剪枝方法。
3.3.2、划分标准
熵模型拥有大量耗时的对数运算，基尼指数在简化模型的同时还保留了熵模型的优点。基尼指数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（率）正好相反。其中k代表类别。
基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越小，则数据集纯度越高。基尼指数偏向于特征值较多的特征，类似信息增益。基尼指数可以用来度量任何不均匀分布，是介于0~1之间的数0是完全相等1是完全不相等。
3.3.3、算法步骤
3.3.4、CART剪枝算法
4.集成学习之随机森林
集成学习（ensemble learning）通过构建并结合多个学习器来完成学习任务。根据个体学习器的生成方式，目前集成学习的方法大致分为两类，即个体学习器之间存在强依赖关系，必须串行生成的序列化方法；另一类就是个体学习器之间不存在强依赖关系、可同时生成的并行化方法。前者的代表是Boosting，后者的代表室Bagging和随机森林。
集成学习中的几个概念：
1、个体学习器：集成学习的一般结构都是先产生一组个体学习器（individual learner），在用某种策略将他们结合起来，个体学习器通常由一个现有的学习算法从训练数据中产生。
2、基学习器：如果集成中只包含同种类型的个体学习器，例如决策树集成中全都是决策树，这样的集成是‘同质’（homogeneous）的，同质集成中的个体学习器又称‘基学习器’，相应的学习算法又称基学习算法。
3、组件学习器：集成也可以是包含不同类型的个体学习器，例如决策树和神经网络，这样的集成是‘异质’（heterogenous）的，异质集成中的个体学习器称为组件学习器或者直接称为个体学习器。
4.1、Bagging
Bagging，Bootstrapped Aggregation的简称。Bootstrap是一种有放回的重复抽样方法，抽样策略就是简单的随机抽样。
另外，Bagging 各个学习器之间没有依赖关系，可以并行生成，在如今大数据大样本的的时代很有诱惑力。
bootstrap自助法重采样技术，从训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。
随机森林是bagging的一个“特化进阶"版。所谓的“特化“是因为随机森林的弱学习器都是决策树。所谓的“进阶“是随机森林在bagging的样本随机采样基础上，又加上了特征的随机选择，其基本思想没有脱离bagging的范畴。
4.2、Boosting
Boosting 各个学习器之间是串连的关系，每一轮的训练集不变，改变的是样本的权重。
（1）首先从训练集用初始权重训练出一个弱学习器1；
（2）根据学习误差率来更新训练样本的权重，误差率高的训练样本赋予更高的权重，这样误差率高的点在后面的弱学习器2中就会得到更多的重视；
（3）然后基于调整权重后的训练集来训练弱学习器2；
……
如此重复进行迭代训练
4.3、随机森林（Random Forest）
决策树和集合学习颇有渊源，将决策树与上面提到的集成学习算法框架进行结合所得到的新的算法：
Bagging + 决策树 = 随机森林
AdaBoost + 决策树 = 提升树
Gradient Boosting + 决策树 = GBDT
此文主要学习的内容，就是“随机森林”。
4.4、模型融合
不论采用Boosting还是 Bagging，我们都得到了若干个弱学习器，如何将预测结果融合是一下步重点解决的问题。
（1）数值预测问题，可以采用平均值法，包括简单平均，加权平均等；
（2）分类预测问题，一般采用投票法，简单的方法就是“少数服从多数”。复杂一点要求“超过半数”，否则拒绝预测。更加复杂的，要求“加权投票”；
（3）Stacking——将弱学习器（初级学习器）的预测结果作为输入，再套上一个模型（次级学习器）预测一次，最终得到输出。
集成学习的核心内容：
（1）如何构建具有差异性的分类器；
（2）如何对这些分类器的结果进行整合。
4.5、随机森林核心
随机森林，Random Forest是Bagging的一种特化进阶版。
首先，在Random Forest【森林】里，弱学习器全部由CART决策树构成。各个决策树之间没有依赖关系，并列运行。
其次，Random Forest的【随机】体现在两个方面：
（1）随机特征
每棵树训练用的特征不是全部特征，而是随机从M个总特征中选出的m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；
选变量个数（m）是决策树的重要参数，对系统的调优非常关键。
如果m=M，M表示全部特征数量，则此时RF的CART决策树和普通的CART决策树没有区别。
m取值越小，则模型约健壮，当然此时对于训练集的拟合程度会变差。也就是说m越小，模型的方差会减小，但是偏倚会增大。
在实际案例中，一般会通过交叉验证调参获取一个合适的m值。
（2）随机数据
如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本，作为该树的训练集。
放回采样，必然导致一部分数据被选中，另外一部分数据没有选中，选中了就放到bag中，没有选中的就是out of bag（oob）。
按照Random Forest的采用方式，每个样本每次被采集到的概率为1/N，不被采集到的概率为1-1/N，m次采样都没有被采集中的概率是(1-1/N)N。
当m→∞时，(1-1/N)N~1/e≈0.368.
即，在bagging的每轮随机采样中，训练集中大约有36.8%的数据没有被采样到。也就是说，对于每棵树而言（假设对于第k棵树），大约36.8%的训练实例没有参与第k棵树的生成，它们称为第k棵树的 oob 样本（袋外样本）。
由于袋外样本的存在，这些没有选中的数据不参与建模，所以可以作为验证数据，评估模型效果。因此，随机森林没有必要再进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计，可以用 oob error 替代。
oob error 计算步骤：
1）对每个样本，计算它作为oob样本的树对它的分类情况（约1/3的树）；
2）然后以简单多数投票作为该样本的分类结果；
3）最后用误分个数占样本总数的比率作为随机森林的oob误分率。
【随机特征】和【随机数据】这两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。
也正因为如此，随机森林相比CART决策树还有另外一个特点，那就是：通常情况下，随机森林不需要剪枝。
回想一下，我们在学习决策树时剪枝的目的，是为了防止过度拟合。随机森林里面每棵树的产生通过选特征、选数据的随机性，已经考虑了避免过拟合。剩下的每棵树需要做的，就是尽可能的在自己所对应的数据(特征)集情况下做到最好的预测结果。
因此，随机森林中的每棵树都尽最大程度的生长，并没有剪枝过程。
4.6、影响性能因素
随机森林模型特别让人稀罕的一点，就是基本不需要调参。但我们仍需要了解影响模型性能的因素，方便我们应对实际情况中难以预测的问题。
影响随机森林性能的因素包括：
（1）森林面积越越大，分类效果越好；
（2）森林中的每棵树越茂盛，分类效果就越好；
（3）森林中任意两棵树的相关性越大，错误率越大；
对应需要调整的参数有：
（1） 决策树的个数 n_estimators
（2） 递归次数（即决策树的深度）max_depth
（3） 特征属性的个数 max_features
n_estimators：因为有随机因素，n_estimators越多结果越稳定，所以只要允许内，决策树的数目越大越好。通常随着树的数量的增加，test error 会逐渐减小，当达到足够大的时候，test error的变化变得很小，这时候就可以确定较为合理的树的数量。
max_depth：一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。深度越小，计算量越小，速度越快。常用的可以取值10-100之间。
max_features：减小max_features不仅会提升算法速度，也有可能降低测试误差；通常使用的值可以是全部特征值M的开方，或者取对数；或者，逐一尝试max_features的值，直到找到比较理想的数。
4.7、随机森林优缺点
优点：
（1）可以高度并行化运算，大样本运算有速度优势
（2）由于采用了随机采样，泛化能力强，对缺失值不敏感
（3）训练后可以输出特征重要性
（4）调参较为简单
缺点：
（1）在某些噪音比较大的样本集上，RF模型容易陷入过拟合。
（2）取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。
