决策树及衍射指标

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

熵:

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

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

打赏的大佬可以联系我,赠送超赞的算法资料