[决策树]西瓜书中增益、增益比率以及基尼系数的计算
决策树:分裂(Splitting)、停止(Stopping)与剪枝(Pruning)
一、Splitting
问题:
-
怎样找到最好的分裂属性?
-
希望内在的节点有更高的纯度。
-
怎样去衡量纯度呢?
信息熵(Information entropy)是来评判采样D的纯度
-
E n t ( D ) Ent(D) Ent(D)的值越小表示纯度越高
-
当概率 p k p_{k} pk为 1 1 1的时候, E n t ( D ) Ent(D) Ent(D)的值为 0 0 0,也就是说全都是这种情况,纯度很高。
-
当概率 p k p_{k} pk为 1 2 \frac{1}{2} 21时, E n t ( D ) Ent(D) Ent(D)的值为 1 2 \frac{1}{2} 21,由于五五开的分布,也就没那么纯了,比较混乱。
1.1、信息增益 Gain(D,a):
- 对于一个离散的分布 a a a来说, a 1 , a 2 , … , a V {a^1,a^2,…,a^V} a1,a2,…,aV
- D v D^v Dv 是 D D D的子集合 满足 a ( x ) = a v , ∀ x ∈ D v a(x)=a^v, ∀ x∈D^v a(x)=av,∀x∈Dv
- 服从分布 a a a分裂 D D D的信息增益为:
- E n t ( D ) Ent(D) Ent(D)表示分裂前的Entropy,而 E n t ( D v ) Ent(D^{v}) Ent(Dv)表示分裂后的Entropy
西瓜的例子:
a.分裂前
- 根据是不是好瓜,可以分为 w 1 w_{1} w1和 w 2 w_{2} w2两种,他们的先验概率(A-priori)分别为 8 17 \frac {8}{17} 178和 9 17 \frac {9}{17} 179
- 那么他们分裂之前的
E
n
t
(
D
)
Ent(D)
Ent(D)计算如下:
b.开始分裂(以色泽为特征)
对于颜色属性来说,可以分成三个子集合,每个子集合的好瓜和坏瓜的概率为:
-
绿色: D 1 D^{1} D1={ 1 , 4 , 6 , 10 , 13 , 17 1,4,6,10,13,17 1,4,6,10,13,17}, P 1 1 = 3 / 6 , P 2 1 = 3 / 6 P_1^1=3/6,P_2^1=3/6 P11=3/6,P21=3/6
-
黑色: D 2 D^2 D2={ 2 , 3 , 7 , 8 , 9 , 15 2,3,7,8,9,15 2,3,7,8,9,15}, P 1 2 = 4 / 6 , P 2 2 = 2 / 6 P_1^2=4/6,P_2^2=2/6 P12=4/6,P22=2/6
-
白色: D 3 D^3 D3={ 5 , 11 , 12 , 14 , 16 5,11,12,14,16 5,11,12,14,16}, P 1 3 = 1 / 5 , P 2 3 = 4 / 5 P_1^3=1/5,P_2^3=4/5 P13=1/5,P23=4/5
-
那么分裂后每一个个分支的Entropy计算如下:
- 最后计算总的色泽的信息增益
c.继续分裂(选择其他特征)
如计算触感特征,分为两类
-
硬滑 D 1 D^{1} D1={ 1 , 2 , 3 , 4 , 5 , 8 , 9 , 11 , 13 , 14 , 16 , 17 1,2,3,4,5,8,9,11,13,14,16,17 1,2,3,4,5,8,9,11,13,14,16,17}, P 1 1 = 6 / 12 , P 2 1 = 6 / 12 P_1^1=6/12,P_2^1=6/12 P11=6/12,P21=6/12
-
软粘 D 2 D^2 D2={ 6 , 7 , 10 , 12 , 15 6,7,10,12,15 6,7,10,12,15}, P 1 2 = 2 / 5 , P 2 2 = 3 / 5 P_1^2=2/5,P_2^2=3/5 P12=2/5,P22=3/5
E n t ( D 1 ) = 1 Ent(D^{1})=1 Ent(D1)=1, E n t ( D 2 ) = 0.971 Ent(D^{2})=0.971 Ent(D2)=0.971
G a i n ( D , 触 感 ) = E n t ( D ) − ( 12 17 ∗ 1.000 + 5 17 ∗ 0.971 ) = 0.0065 Gain(D,触感)=Ent(D) - (\frac {12}{17}*1.000+\frac {5}{17}*0.971)=0.0065 Gain(D,触感)=Ent(D)−(1712∗1.000+175∗0.971)=0.0065
- 和计算结果一致,因此选出最大的增益为纹理,画出分裂结果如下图所示:
1.2、信息增益比率 Gain Ratio
-
I V ( a ) IV(a) IV(a) 是分布 a a a的固有属性
-
分布a的值越离散,纯度越小, I V ( a ) IV(a) IV(a) 的值就越大
-
如果针对触感(touch)计算一下 I V ( a ) IV(a) IV(a)
- I V ( a ) = − ( 12 17 l o g 2 ( 12 17 ) + 5 17 l o g 2 ( 5 17 ) ) = 0.874 IV(a)=-(\frac {12}{17} log_{2}(\frac {12}{17})+\frac {5}{17} log_{2}(\frac {5}{17}))=0.874 IV(a)=−(1712log2(1712)+175log2(175))=0.874
- G a i n r a t i o n ( D , t o u c h ) = G a i n ( D , t o u c h I V ( a ) = 0.006 0.874 = 0.74 Gain_ration(D,touch)=\frac {Gain(D,touch}{IV(a)}=\frac{0.006}{0.874}=0.74 Gainration(D,touch)=IV(a)Gain(D,touch=0.8740.006=0.74%
- 触感的离散程度很小,大部分都是硬滑的,可以认为比较离散,因此它的信息增益比率很小。
-
如果针对色泽计算一下 I V ( a ) IV(a) IV(a)
-
I V ( a ) = − ( 6 17 l o g 2 ( 6 17 ) + 6 17 l o g 2 ( 6 17 ) + 5 17 l o g 2 ( 5 17 ) ) = 1.580 IV(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 IV(a)=−(176log2(176)+176log2(176)+175log2(175))=1.580
-
G a i n r a t i o n ( D , c o l o r ) = G a i n ( D , c o l o r I V ( a ) = 0.109 0.580 = 6.9 Gain_ration(D,color)=\frac {Gain(D,color}{IV(a)}=\frac{0.109}{0.580}=6.9 Gainration(D,color)=IV(a)Gain(D,color=0.5800.109=6.9%
-
色泽的离散程度较大,基本上不连续,因此它的信息增益比率较大
-
1.3、基尼系数 Gini index
-
从集合D中随机的选取两个样本的可能有不同的标签,比如绿色色泽中随便抽取两个样本,计算好瓜和坏瓜的概率
-
小的Gini index表明更高的纯度
-
然后选择具有最小的Gini index
-
计算触感的Gini index, D 1 D^{1} D1是硬滑, D 2 D^{2} D2是软粘, D 1 D = 12 17 \frac {D^{1}}{D}=\frac {12}{17} DD1=1712
- G i n i ( D 1 , t o u c h ) = 1 − ( 6 12 ) 2 − ( 6 12 ) 2 = 0.500 Gini(D^{1},touch)=1-(\frac {6}{12})^2-(\frac {6}{12})^2=0.500 Gini(D1,touch)=1−(126)2−(126)2=0.500
- G i n i ( D 2 , t o u c h ) = 1 − ( 2 5 ) 2 − ( 3 5 ) 2 = 0.480 Gini(D^{2},touch)=1-(\frac {2}{5})^2-(\frac {3}{5})^2=0.480 Gini(D2,touch)=1−(52)2−(53)2=0.480
- G i n i i n d e x ( D , t o u c h ) = 12 17 ∗ 0.500 + 5 17 ∗ 0.480 = 0.494 Gini_index(D,touch)=\frac {12}{17} * 0.500 + \frac {5}{17} * 0.480=0.494 Giniindex(D,touch)=1712∗0.500+175∗0.480=0.494
-
计算色泽的Gini index
-
G i n i ( D 1 , c o l o r ) = 1 − ( 3 6 ) 2 − ( 3 6 ) 2 = 0.500 Gini(D^{1},color)=1-(\frac {3}{6})^2-(\frac {3}{6})^2=0.500 Gini(D1,color)=1−(63)2−(63)2=0.500
-
G i n i ( D 2 , c o l o r ) = 1 − ( 4 6 ) 2 − ( 2 6 ) 2 = 0.444 Gini(D^{2},color)=1-(\frac {4}{6})^2-(\frac {2}{6})^2=0.444 Gini(D2,color)=1−(64)2−(62)2=0.444
-
G i n i ( D 3 , c o l o r ) = 1 − ( 1 5 ) 2 − ( 4 5 ) 2 = 0.320 Gini(D^{3},color)=1-(\frac {1}{5})^2-(\frac {4}{5})^2=0.320 Gini(D3,color)=1−(51)2−(54)2=0.320
-
G i n i i n d e x ( D , c o l o r ) = 6 17 ∗ 0.500 + 6 17 ∗ 0.444 + 5 17 ∗ 0.320 = 0.427 Gini_index(D,color)=\frac {6}{17} * 0.500 + \frac {6}{17} * 0.444+ \frac {5}{17}*0.320=0.427 Giniindex(D,color)=176∗0.500+176∗0.444+175∗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,3,1|+), (2,1,1|+), (3,2,2|+), (1,3,3|+) Dj=(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=(1,2,1|+), (1,2,1|+), (1,2,1|-) Dj=(1,2,1∣+),(1,2,1∣+),(1,2,1∣−)
-
没数据分裂:当前节点是空的或者由父节点直接分配了主标签
D j = ∅ D_j=∅ Dj=∅
三、Pruning
-
过拟合
-
太多的分支会让数据集在训练集上表现的过好
-
过拟合的风险可以通过剪枝来解决
-
-
策略
- 前减枝(Pre-pruning),提前停止分支的增长
- 后减枝(Post-pruning),从一个完整的决策树中移除一些分支
-
如何决定要不要剪枝呢?
应当遵循留出法(hold-out)
- 把数据集分成两部分训练集和测试集(交集为空,并集为数据集)
- 分层采样(Stratified sampling),让训练集和测试集有相似的分布
- 多次随机采样,用平均分数来评价训练集的泛化指标