决策树
本质是一颗由多个判断节点组成的树。决策树算法的核心是通过对数据的学习，选定判断节点，构造一颗合适的决策树。
树模型不需要做归一化：
- 归一化的目的是为了加快梯度下降法的收敛速度，但是决策树模型不需要计算梯度
- 树模型只考虑特征的划分界限，而不需要考虑特征的值范围
决策树的关键是选择最优划分属性。
一个属性会有多个取值，根据这个属性的不同取值将输入的数据划分为多个样本集合，一个取值对应一个分支集合，
(注意，CART树只选取一个取值，因此是划分为二叉树）
使得每个取值分支集合中的样本尽可能属于同一类别，即分支集合的纯度越高。
三种选择方式：
信息增益 ID3
信息熵：度量样本集合纯度的常用指标。令$p_k, k=1,2,…,m$代表第k类样本在输入样本集合D中所占的比例，假设一共有m个类别，则该集合D的信息熵为：
信息熵Ent(D)的值越小，则代表D的纯度越高。
假定属性a有V种取值，因此输入数据集合D, 根据属性a可以将D划分为V个分支集合，那么根据属性a划分得到的信息增益为：
其中，$D^v$代表根据属性a的某个取值$a^v$得到的分支集合。
信息增益越大，则意味着使用属性a进行划分带来的纯度提升越大，因此可以根据信息增益选择属性。
(因为划分后的纯度越高, 那么信息熵越小, 即第二项越小, 因此增益越大)
增益率 C4.5
为了避免ID3算法偏向于选择可取值数目较多的属性。
定义每个属性的增益率，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性。
相当于对信息增益进行了标准化。
定义属性a的固有值为, 属性a的可能取值越多，则固有值通常会越大，因此
增益率对可取值较少的属性有所偏好。
基尼指数 CART树
ID3和C4.5都使用了大量的对数运算，计算量大。
CART树是二叉树，因此每次选择最优属性后，再选择该属性的一个取值进行划分。
对回归树用最小化平方误差：
即先选择一个属性，再选择一个取值将节点集合分为两个子集,
对每个子集选择一个输出值使得划分后的两个集合与该输出值的的平方差最小。
然后根据最小平方差, 选择最优属性的最优切分点.
最后得到多个叶节点，每个叶节点包含多个样本，叶节点的输出值取所有样本输出值的均值或使平方差最小的值。
对于分类树采用基尼指数最小化准则：
用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
基尼值：数据集D的纯度用基尼值表示，
Gini(D)越小，代表数据纯度越高。
基尼指数：属性a的基尼指数表示为：
根据使基尼指数最小的属性进行选择。
最后根据叶节点中样本的标签数量, 取多数类别作为该叶子节点的类别.
Xgboost是根据split gain计算得到增益, 得到最优划分. 与CART树存在区别。
决策树剪枝
训练出得决策树存在过度拟合现象——决策树过于针对训练的数据，专门针对训练集创建出来的分支，其熵值可能会比真实情况有所降低。
如何剪枝
预剪枝：
在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶节点。
泛化性能判断：
关键是要预留一部分数据作为验证集。
假设要划分属性a，划分在a属性下的样本集合为D。
若不划分属性a，则取D中样本类别数最多的类别作为a的标记，然后在验证集中计算出此时的验证集精度；
若划分属性a, 则将样本D划分为多个子集，对每个子集，将样本类别最多的类别作为该子集的标记，然后计算验证集中样例的精度，如果大于不划分的情况，则可以用属性a进行划分。
预剪枝可能会带来欠拟合的风险。
后剪枝：
先从训练集中生成一颗完整的决策树，然后自底向上对每个非叶节点进行观察，若将该节点替换为叶结点能带来泛化性能的提升，则将该子树替换为叶结点。
后剪枝训练开销大。
随机森林
鉴于决策树容易过拟合的缺点，随机森林采用多个决策树的投票机制来改善决策树，我们假设随机森林使用了m棵决策树，那么就需要产生m个一定数量的样本集来训练每一棵树，如果用全样本去训练m棵决策树显然是不可取的，全样本训练忽视了局部样本的规律，对于模型的泛化能力是有害的。
随机采样Bootstrap：
假设原始训练集的样本数为n, 则每个采样集的样本数量也是n, 但是样本内容不同，所以某一个样本可能被多次采样到，某一些样本没有机会被采样到。
产生n个样本的方法采用Bootstraping法，这是一种有放回的抽样方法，产生n个样本, 然后去重。
实际上，在bagging的每轮采样中，训练集中大约有36.8%的数据没有被采样集采集。
而最终结果采用Bagging的策略来获得，即多数投票机制。
Bagging的生成方法：
1.从样本集中通过重采样的方式产生n个样本
2.假设样本特征数目为a，对n个样本选择a中的k个特征，用建立决策树的方式获得最佳分割点
3.重复m次，产生m棵决策树
4.多数投票机制来进行预测
（需要注意的一点是，这里m是指循环的次数，n是指样本的数目，n个样本构成训练的样本集，而m次循环中又会产生m个这样的样本集）
原理 （随机森林与bagging的关系）
Bagging可以简单的理解为：放回抽样，多数表决（分类）或简单平均（回归）,同时Bagging的基学习器之间属于并列生成，不存在强依赖关系。
Random Forest（随机森林）是Bagging的扩展变体，它在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括RF包括四个部分：
1、随机选择样本（放回抽样, 行抽样）；
2、构建决策树（CART树）；
3、随机选择特征(列抽样)；
4、随机森林投票（平均）。
随机选择样本和Bagging相同，随机选择特征是指在树的构建中，会从样本集的特征集合中随机选择部分特征，然后再从这个子集中选择最优的属性用于划分，这种随机性导致随机森林的偏差会有稍微的增加（相比于单棵不随机树），但是由于随机森林的‘平均’特性，会使得它的方差减小，而且方差的减小补偿了偏差的增大，因此总体而言是更好的模型。
在构建决策树的时候，RF的每棵决策树都最大可能的进行生长而不进行剪枝；在对预测输出进行结合时，RF通常对分类问题使用简单投票法，回归任务使用简单平均法。
RF的重要特性是不用对其进行交叉验证或者使用一个独立的测试集获得无偏估计，它可以在内部进行评估，也就是说在生成的过程中可以对误差进行无偏估计，由于每个基学习器只使用了训练集中约63.2%的样本，剩下约36.8%的样本可用做验证集来对其泛化性能进行“包外估计”。
RF和Bagging对比：Bagging使用的是‘确定性’决策树，在选择特征划分结点时，要对所有的特征进行考虑，而随机森林使用的是‘随机性’特征数，只需考虑特征的子集。
优缺点：
随机森林的优点较多，简单总结：
- 训练可以高度并行化，对于大数据时代的大样本训练速度有优势
- 由于随机选择特征时只考虑特征子集，因此样本特征维度很高时仍然高效
- 训练后，可以给出各个特征的重要性
- 由于采用了随机采样，方差小，泛化能力强
- 相比Boosting，实现简单
RF的缺点：在噪声较大的分类或者回归问题上会过拟合。
随机森林特征选择
- 基于选择频率， 即特征在构建随机森林时被选为最优特征划分的次数
- 基于基尼不纯度，根据特征选择后降低的gini不纯度来确定
存在问题：偏向于选择具有较多类别的特征；
当存在相关特征时，一个特征被选择后，与其相关的其他特征的重要度则会变得很低 - 准确率， 每次选择一列特征，将该特征的所有数值打乱后训练模型，查看模型下降的准确度
参考：
周志华，机器学习；
CART回归树, 李航，第五章决策树；
随机森林，面试：https://blog.csdn.net/qq_28031525/article/details/70207918
特征选择：https://blog.csdn.net/banbuduoyujian/article/details/60328474