理论：决策树及衍射指标

一、常用的决策树节点枝剪的衡量指标：

熵：

如果一件事有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对应的分类器，在组合投票得到最终的分类器

四、惠普实验室-集成并行化的随机森林：