一、常用的决策树节点枝剪的衡量指标：
熵：
如果一件事有k种可的结果，每种结果的概率为 pi（i＝1…k）
该事情的信息量：
熵越大，随机变量的不确定性越大。
信息增益：
特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下的经验条件熵H(D|A)之差
换句话说，就是原信息集下的信息量－在A特征条件下的信息集的信息量
信息增益越大，信息增多，不确定性减小
信息增益率：
信息增益率定义:特征A对训练数据集D的信息增益比定义为其信息增益与训练数据D关于特征A的值的熵HA(D)之比
注：p：每个唯独上，每个变量的个数／总变量个数
二、常用的决策树介绍：
ID3算法：
ID3算法的核心是在决策树各个子节点上应用信息增益准则选择特征，递归的构建决策树，具体方法是:从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归调用以上方法，构建决策树。
解释：在做每次选择差分枝的时候，以不确定性最小点作为loss fuction，直到无法细分
缺点：
1.ID3算法只有树的生成，所以该算法生成的树容易产生过拟合，分得太细，考虑条件太多。
2.不能处理连续属性
3.选择具有较多分枝的属性，而分枝多的属性不一定是最优的选择。
4.局部最优化，整体熵值最小，贪心算法算子节点的分支
C4.5算法：
基于ID3算法，用信息增益比来选择属性，对非离散数据也能处理，能够对不完整数据进行处理。
采用增益率（GainRate）来选择分裂属性。计算方式如下：
CART算法：
CART算法选择分裂属性的方式是比较有意思的，首先计算不纯度，然后利用不纯度计算Gini指标。
计算每个子集最小的Gini指标作为分裂指标。
不纯度的计算方式为：
pi表示按某个变量划分中，目标变量不同类别的概率。
某个自变量的Gini指标的计算方式如下：
计算出每个每个子集的Gini指标，选取其中最小的Gini指标作为树的分支（Gini（D）越小，则数据集D的纯度越高）。连续型变量的离散方式与信息增益中的离散方式相同。
三、基于决策树的一些集成算法：
随机森林：
随机生成n颗树，树之间不存在关联，取结果的时候，以众数衡量分类结果；除了分类，变量分析，无监督学习，离群点分析也可以。
生成过程：
1.n个样本，随机选择n个样本（有放回），训练一颗树
从原始训练数据集中,应用bootstrap方法有放回地随机抽取 K个新的自助样本集,并由此构建 K棵分类回归树,每次未被抽到的样本组成了 K个袋外数据(Out-of-bag,OOB)
2.每个样本有M个属性，随机选m个，采取校验函数（比如信息增益、熵啊之类的），选择最佳分类点
3.注意，每个树不存在枝剪
4.将生成的多棵树组成随机森林,用随机森林对新的数据进行分类,分类结果按树分类器的投票多少而定
树的个数随机选取，一般500，看三个误差函数是否收敛；变量的个数一般取均方作为mtry
GBDT：
DT步骤：
GBDT里面的树是回归树！
GBDT做每个节点上的分支的时候，都会以最小均方误差作为衡量（真实值－预测值）的平方和／N，换句话说，就是存在真实线l1，预测线l2，两条线之间的间距越小越好。
BT步骤：
GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。
换句话说，就是第一次预测的差值记为下一次预测的初始值，一直到某一次计算出的差值为0，把前n次的结果相加，就是一个真实预测。
Adaboost：
步骤：
1.初始化所有训练样例的权重为1 / N,其中N是样本数
2.对其中第1~m个样本:
a.训练m个弱分类器，使其最小化bias：
b.接下来计算该弱分类器的权重α，降低错判的分类器的权重，：
c.更新权重：
3.最后得到组合分类器：
核心的思想如下图：
全量数据集在若干次训练后，降低训练正确的样本的权重，提高训练错误样本的权重，得到若干个Y对应的分类器，在组合投票得到最终的分类器
四、惠普实验室-集成并行化的随机森林：
