[决策树]西瓜书中增益、增益比率以及基尼系数的计算

决策树：分裂（Splitting）、停止（Stopping）与剪枝（Pruning）一、Splitting问题：怎样找到最好的分裂属性？希望内在的节点有更高的纯度。怎样去衡量纯度呢？信息熵（Information entropy）是来评判采样D的纯度Ent(D)Ent(D)Ent(D)的值越小表示纯度越高当概率pkp_{k}pk为111的时候，Ent(D)Ent(D)Ent(D)的值为000，也

蛋总的快乐生活

3995人浏览 · 2020-11-23 21:35:42

蛋总的快乐生活 · 2020-11-23 21:35:42 发布

决策树：分裂（Splitting）、停止（Stopping）与剪枝（Pruning）

一、Splitting

问题：

怎样找到最好的分裂属性？
希望内在的节点有更高的纯度。
怎样去衡量纯度呢？

信息熵（Information entropy）是来评判采样D的纯度

在这里插入图片描述

$E n t (D)$ 的值越小表示纯度越高
当概率 $p_{k}$ 为 $1$ 的时候， $E n t (D)$ 的值为 $0$ ，也就是说全都是这种情况，纯度很高。
当概率 $p_{k}$ 为 $12\frac{1}{2}$ 时， $E n t (D)$ 的值为 $12\frac{1}{2}$ ，由于五五开的分布，也就没那么纯了，比较混乱。

1.1、信息增益 Gain(D,a)：

对于一个离散的分布 $a$ 来说， ${a^1,a^2,…,a^V}$
$D^v$ 是 $D$ 的子集合满足 $a(x)=a^v, ∀ x∈D^v$
服从分布 $a$ 分裂 $D$ 的信息增益为:
$E n t (D)$ 表示分裂前的Entropy，而 $Ent(D^{v})$ 表示分裂后的Entropy

在这里插入图片描述

西瓜的例子：

a.分裂前

在这里插入图片描述

根据是不是好瓜，可以分为 $w_{1}$ 和 $w_{2}$ 两种，他们的先验概率(A-priori)分别为 $817\frac {8}{17}$ 和 $917\frac {9}{17}$
那么他们分裂之前的 $E n t (D)$ 计算如下：

b.开始分裂（以色泽为特征）

对于颜色属性来说，可以分成三个子集合，每个子集合的好瓜和坏瓜的概率为：
在这里插入图片描述

绿色： $D^{1}$ ={ $1, 4, 6, 10, 13, 17$ }， $P_1^1=3/6,P_2^1=3/6$
黑色： $D^2$ ={ $2, 3, 7, 8, 9, 15$ }, $P_1^2=4/6,P_2^2=2/6$
白色： $D^3$ ={ $5, 11, 12, 14, 16$ }, $P_1^3=1/5,P_2^3=4/5$
那么分裂后每一个个分支的Entropy计算如下：

在这里插入图片描述

最后计算总的色泽的信息增益

在这里插入图片描述

c.继续分裂（选择其他特征）

如计算触感特征，分为两类

硬滑 $D^{1}$ ={ $1, 2, 3, 4, 5, 8, 9, 11, 13, 14, 16, 17$ }， $P_1^1=6/12,P_2^1=6/12$
软粘 $D^2$ ={ $6, 7, 10, 12, 15$ }, $P_1^2=2/5,P_2^2=3/5$

$Ent(D^{1})=1$ , $Ent(D^{2})=0.971$

$(\frac {12}{17}*1.000+\frac {5}{17}*0.971)=0.0065$

在这里插入图片描述

和计算结果一致，因此选出最大的增益为纹理，画出分裂结果如下图所示：

1.2、信息增益比率 Gain Ratio

在这里插入图片描述

$I V (a)$ 是分布 $a$ 的固有属性
分布a的值越离散，纯度越小， $I V (a)$ 的值就越大
如果针对触感（touch）计算一下 $I V (a)$
1. $IV(a)=−(1217log2(1217)+517log2(517))=0.874IV(a)=-(\frac {12}{17} log_{2}(\frac {12}{17})+\frac {5}{17} log_{2}(\frac {5}{17}))=0.874$
2. $Gainration(D,touch)=Gain(D,touchIV(a)=0.0060.874=0.74Gain_ration(D,touch)=\frac {Gain(D,touch}{IV(a)}=\frac{0.006}{0.874}=0.74$ %
3. 触感的离散程度很小，大部分都是硬滑的，可以认为比较离散，因此它的信息增益比率很小。
如果针对色泽计算一下 $I V (a)$
1. $IV(a)=−(617log2(617)+617log2(617)+517log2(517))=1.580IV(a)=-(\frac {6}{17} log_{2}(\frac {6}{17})+\frac {6}{17} log_{2}(\frac {6}{17})+\frac {5}{17} log_{2}(\frac {5}{17}))=1.580$
2. $Gainration(D,color)=Gain(D,colorIV(a)=0.1090.580=6.9Gain_ration(D,color)=\frac {Gain(D,color}{IV(a)}=\frac{0.109}{0.580}=6.9$ %
3. 色泽的离散程度较大，基本上不连续，因此它的信息增益比率较大

1.3、基尼系数 Gini index

在这里插入图片描述

从集合D中随机的选取两个样本的可能有不同的标签，比如绿色色泽中随便抽取两个样本，计算好瓜和坏瓜的概率
小的Gini index表明更高的纯度
然后选择具有最小的Gini index
计算触感的Gini index, $D^{1}$ 是硬滑， $D^{2}$ 是软粘， $D1D=1217\frac {D^{1}}{D}=\frac {12}{17}$
1. $Gini(D1,touch)=1−(612)2−(612)2=0.500Gini(D^{1},touch)=1-(\frac {6}{12})^2-(\frac {6}{12})^2=0.500$
2. $Gini(D2,touch)=1−(25)2−(35)2=0.480Gini(D^{2},touch)=1-(\frac {2}{5})^2-(\frac {3}{5})^2=0.480$
3. $Giniindex(D,touch)=1217∗0.500+517∗0.480=0.494Gini_index(D,touch)=\frac {12}{17} * 0.500 + \frac {5}{17} * 0.480=0.494$
计算色泽的Gini index
1. $Gini(D1,color)=1−(36)2−(36)2=0.500Gini(D^{1},color)=1-(\frac {3}{6})^2-(\frac {3}{6})^2=0.500$
2. $Gini(D2,color)=1−(46)2−(26)2=0.444Gini(D^{2},color)=1-(\frac {4}{6})^2-(\frac {2}{6})^2=0.444$
3. $Gini(D3,color)=1−(15)2−(45)2=0.320Gini(D^{3},color)=1-(\frac {1}{5})^2-(\frac {4}{5})^2=0.320$
4. $Giniindex(D,color)=617∗0.500+617∗0.444+517∗0.320=0.427Gini_index(D,color)=\frac {6}{17} * 0.500 + \frac {6}{17} * 0.444+ \frac {5}{17}*0.320=0.427$

1.4 总结

	纯度小（离散程度大）	分裂点
Gain	大的增益	选择大的增益
Gain ratio	大的增益比率	选择大的增益比率
Gini index	小的基尼系数	选择小的基尼系数

二、Stopping and labeling

停止分裂的三种情况

没必要分裂：所有样本在当前节点有相同的标签

$D_j=(1,3,1|+), (2,1,1|+), (3,2,2|+), (1,3,3|+)$
没办法分裂：当前分布集合是空的或者所有样本在所有的分布都相同

$D_j=(1,2,1|+), (1,2,1|+), (1,2,1|-)$
没数据分裂：当前节点是空的或者由父节点直接分配了主标签

$D_j=∅$

三、Pruning

过拟合
1. 太多的分支会让数据集在训练集上表现的过好
2. 过拟合的风险可以通过剪枝来解决
策略
1. 前减枝(Pre-pruning)，提前停止分支的增长
2. 后减枝(Post-pruning)，从一个完整的决策树中移除一些分支
如何决定要不要剪枝呢？

应当遵循留出法(hold-out)
1. 把数据集分成两部分训练集和测试集（交集为空，并集为数据集）
2. 分层采样(Stratified sampling)，让训练集和测试集有相似的分布
3. 多次随机采样，用平均分数来评价训练集的泛化指标