决策树（理论部分1）

教材：周志华 机器学习 参考视频资料：【一起啃书】机器学习西瓜书白话解读（来自bilibili）

视频地址：https://www.bilibili.com/video/BV17J411C7zZ?

知识整理如下

决策树（理论部分1）

• 决策树（理论部分1）
• • 4.1 基本流程
  • 4.2 划分选择
  • • 4.2.1 信息增益
    • 4.2.2 增益率
    • 4.2.3 基尼指数

4.1 基本流程

一棵决策树包含：一个根结点、若干个内部结点、若干个叶结点

• 根结点：包含样本全集
• 叶结点：对应决策结果
• 其他结点：对应一个属性测试

4.2 划分选择

4.2.1 信息增益

1. 信息熵是什么

   参考：知乎YJango 信息熵是什么？

   https://www.zhihu.com/question/22178202

• 熵：一种事物的不确定性
• 信息：消除不确定性的事物，可调整概率、排除干扰、确定情况
• 数据=信息+噪音

1. 熵的度量：

• 若为均匀分布，且只有两种可能， n = log ⁡ 2 m n=\log_2m n=log2​m其中 n n n为熵，有 m m m种不确定的情况

• 若为一般分布，假设样本集合 D D D的第 k k k类样本为 p k ( k = 1 , 2 , . . . , ∣ y ∣ ) p_k (k=1,2,...,|y|) pk​(k=1,2,...,∣y∣)（最终分为了 y y y类）， D D D的信息熵为 E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k l o g 2 p k Ent(D)=-\sum^{|y|}_{k=1} p_k log_2 p_k Ent(D)=−k=1∑∣y∣​pk​log2​pk​我理解为 ∑ p k l o g 2 1 p k \sum p_k log_2 \frac{1}{p_k} ∑pk​log2​pk​1​比如说若 p k = 1 3 p_k=\frac1 3 pk​=31​，以均匀分布方式来看，不确定事件数为3件，故 n 1 = l o g 2 3 n_1=log_2 3 n1​=log2​3，再进行加权，得到 ∑ p k l o g 2 1 p k \sum p_klog_2 \frac{1}{p_k} ∑pk​log2​pk​1​，数学上等效于 E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k l o g 2 p k Ent(D)=-\sum^{|y|}_{k=1} p_k log_2 p_k Ent(D)=−k=1∑∣y∣​pk​log2​pk​

  E n t ( D ) Ent(D) Ent(D)的值越小，则 D D D的纯度越高（即分支结点包含的样本尽可能属于同一类别）

1. 信息增益：假设属性集合 a a a有 V V V个可能的属性，按照属性 a a a对样本 D D D进行划分会有 V V V个分支结点，不同分支结点的样本数不同，权重分别为 D v D ( v = 1 , 2 , . . . , V ) \frac{D_v} D(v=1,2,...,V) DDv​​(v=1,2,...,V)，信息增益定义为： G r a n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gran(D,a)=Ent(D)-\sum^{V}_{v=1}\frac{|D_v|} {|D|} Ent(D^v) Gran(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv​∣​Ent(Dv)可理解成 E n t ( D ) Ent(D) Ent(D)为初始不确定度（即熵），得到信息后求出属性集合中各属性的熵，再进行加权，得到 ∑ ∣ D v ∣ ∣ D ∣ E n t ( D v ) \sum \frac{|D_v|} {|D|} Ent(D^v) ∑∣D∣∣Dv​∣​Ent(Dv)。初始熵与得知信息后求得的熵的差值即为信息增益。

• 一般而言，利用属性 a a a来划分后（得知信息后）求得的熵越小，信息增益越大，意味着使用属性 a a a来进行划分所获得的“纯度提升”越大。因此可以以信息增益为准则来划分属性，如ID3决策树学习算法（ID为Iterative Dichotomiser 即迭代二分器） 。

4.2.2 增益率

仅根据信息增益来决定选择怎样的分类属性带来的问题：按照属性 a a a划分时，若分支结点仅包含一个样本，这些分支结点的纯度已达最大，此时 a a a的信息增益远大于其他划分属性的，这样的决策数不具有泛化能力。

• 信息增益准则对可取值数目较多（有较多分支）的属性有所偏好
• 为减少信息增益准则的偏好带来的不利影响，C4.5决策树算法使用“增益率”来选择最优划分属性

增益率定义

G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)} Gain_ratio(D,a)=IV(a)Gain(D,a)​其中

I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ IV(a)=-\sum^{V}_{v=1}\frac{|D_v|} {|D|} log_2\frac{|D_v|} {|D|} IV(a)=−v=1∑V​∣D∣∣Dv​∣​log2​∣D∣∣Dv​∣​称为属性 a a a的固有值，属性 a a a的分支越多（ V V V越大）， I V ( a ) IV(a) IV(a)的值通常越大。

• 增益率准则对可取值数目较少（有较少分支）的属性有所偏好
• 启发：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率高的

4.2.3 基尼指数

（此处参考百科“Decision tree learning”中对Gini impurity （基尼不纯度）的解释）

CART (classification and regression tree) 算法中的分类树中，基尼不纯度是衡量如果从集合中随机选择一个元素（这个元素是根据子集中标签的分布情况，随机被贴上标签的），这个元素被错误标注的概率。换一种说法，基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。

基尼不纯度可以这样计算：一个样本被选中的概率 p i p_i pi​（标签为 i i i）乘以它被分错的概率 ∑ k ≠ i p k = 1 − p i \sum_{k\neq i}p_k=1-p_i ∑k​=i​pk​=1−pi​，再进行加和（因为一个样本可以落在 p 1 , p 2 , . . . p J p_1,p_2,...p_J p1​,p2​,...pJ​）。设分为 J J J类，其中 i ∈ { 1 , 2 , . . . , J } i \in \{1,2,...,J\} i∈{1,2,...,J} ，令 p i p_i pi​为集合中标为第 i i i类的类别所占的份额。

I G ( p ) = ∑ i = 1 J ( p i ∑ k ≠ i p k ) = ∑ i = 1 J p i ( 1 − p i ) = ∑ i = 1 J ( p i − p i 2 ) = ∑ i = 1 J p i − ∑ i = 1 J p i 2 = 1 − ∑ i = 1 J p i 2 \mathrm{I}_{G}(p)=\sum_{i=1}^{J}\left(p_{i} \sum_{k \neq i} p_{k}\right)=\sum_{i=1}^{J} p_{i}\left(1-p_{i}\right)=\sum_{i=1}^{J}\left(p_{i}-p_{i}^{2}\right)=\sum_{i=1}^{J} p_{i}-\sum_{i=1}^{J} p_{i}^{2}=1-\sum_{i=1}^{J} p_{i}^{2} IG​(p)=i=1∑J​⎝⎛​pi​k​=i∑​pk​⎠⎞​=i=1∑J​pi​(1−pi​)=i=1∑J​(pi​−pi2​)=i=1∑J​pi​−i=1∑J​pi2​=1−i=1∑J​pi2​基尼不纯度越小，数据集的纯度越高。

最后加权平均求基尼指数（Gini index），因为属性 a a a有 V V V个子集（分类），基尼指数计算为 G i n i _ i n d e x ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ I G v ( p ) Gini\_index(D,a)=\sum_{v=1}^{V}\frac{|D_v|} {|D|} \mathrm{I}_{G_v}(p) Gini_index(D,a)=v=1∑V​∣D∣∣Dv​∣​IGv​​(p)

在候选属性集合 A A A中选择使划分后基尼指数最小的属性 a a a作为最优划分属性。

以西瓜书中西瓜数据集2.0为例

计算基尼指数代码实现如下：

# 计算基尼不纯度Gini impurity，此处决策结果只有好瓜g和坏瓜b之分
def gini_impurity(g,b):
    gini_impurity = 1 - (((g/(g+b))**2) + ((b/(g+b))**2))
    return round(gini_impurity,3)
# 求基尼指数Gini index
# 对分成三类的属性求基尼指数
def gini_index(a,b,c,d,e,f):
    class1 = gini_impurity(a,b)  #a，b分别代表正例，反例
    class2 = gini_impurity(c,d)
    class3 = gini_impurity(e,f)
    sum = a+b+c+d+e+f
    gini_index = (a+b)/sum*class1 + (c+d)/sum*class2 + (e+f)/sum*class3
    return round(gini_index,3)
# 对只分成两类的属性求基尼指数
def gini_index2(a,b,c,d):
    class1 = gini_impurity(a,b)
    class2 = gini_impurity(c,d)
    sum = a+b+c+d
    gini_index2 = (a+b)/sum*class1 + (c+d)/sum*class2 
    return round(gini_index2,3)
# 对“色泽”属性（青绿，乌黑，浅白）求基尼指数
feature1 = gini_index(3,3,4,2,1,4)
# 对“根蒂”属性（蜷缩，稍蜷，硬挺）求基尼指数
feature2 = gini_index(5,3,3,4,0,2)
# 对“敲声”属性（沉闷，浊响，清脆）求基尼指数
feature3 = gini_index(2,3,6,4,0,2)
# 对“纹理”属性（清晰，稍糊，模糊）求基尼指数
feature4 = gini_index(7,2,1,4,0,3)
# 对“脐部”属性（凹陷，稍凹，平坦）求基尼指数
feature5 = gini_index(5,2,3,3,0,4)
# 对“触感”属性（硬滑，软粘）求基尼指数
feature6 = gini_index2(6,6,2,3)
print(feature1,feature2,feature3,feature4,feature5,feature6)
           

运行结果如下：

可见使用“纹理”划分的基尼指数最小，故“纹理”为最优划分属性。