作者:張張張張
github地址:https://github.com/zhanghekai
【转载请注明出处,谢谢!】

【机器学习系列】之“西瓜数据集”决策树构建数学公式计算过程
【机器学习系列】之决策树剪枝和连续值、缺失值处理数学公式计算
【机器学习系列】之ID3、C4.5、CART决策树构建代码

一、决策树概述

决策树(Decision Tree)算法是一种基本的分类与回归方法,是最经常使用的数据挖掘算法之一。决策树是一种非线性有监督分类模型必须将已有的数据进行离散化,即:从字符串变成数值。构造决策树的基本思想是随着树深度的增加,节点的“熵”迅速降低,熵降低的速度越快越好,这样我们有望得到一棵高度最矮的决策树。

决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。

决策树的定义:分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型:内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性(features),叶结点表示一个类(labels)。

用决策树对需要测试的实例进行分类:从根节点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点;这时,每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点。最后将实例分配到叶结点的类中。

决策树学习通常包括 3 个步骤:特征选择、决策树的生成和决策树的修剪。

二、决策树场景

  • 一个叫做 “二十个问题” 的游戏,游戏的规则很简单:参与游戏的一方在脑海中想某个事物,其他参与者向他提问,只允许提 20 个问题,问题的答案也只能用对或错回答。问问题的人通过推断分解,逐步缩小待猜测事物的范围,最后得到游戏的答案。

  • 一个邮件分类系统,大致工作流程如下:

在这里插入图片描述

首先检测发送邮件域名地址。如果地址为 myEmployer.com, 则将其放在分类 "无聊时需要阅读的邮件"中。
如果邮件不是来自这个域名,则检测邮件内容里是否包含单词 “曲棍球” , 如果包含则将邮件归类到 “需要及时处理的朋友邮件”, 如果不包含则将邮件归类到 “无需阅读的垃圾邮件” 。

三、决策树概念须知

1.名词定义

熵(entropy):指体系的混乱的程度,在不同的学科中也有引申出的更为具体的定义,是各领域十分重要的参量。

信息熵(information theory):使度量样本集合纯度最常用的一种指标。信息熵度量了事物的不确定性,越不确定的事物,它的熵就越大。

信息增益(information gain):在划分数据集前后信息熵发生的变化称为信息增益。信息增益越大,表明数据“纯度”提升越大。

信息增益率(infor gain ratio):正信息增益的基础上,解决过拟合问题的方法。

基尼系数(Gini index):CART决策树划分属性的指标,数据集的纯度可以用基尼值来度量,基尼值越小,数据集的纯度越高。

纯度(purity):叶子节点中正确分类的标签所占该叶子节点中包含数据的比例。

2.构建“树”时的基本要求

  • 决策树的生成是一个递归过程,即决策树以深度优先遍历进行构建。
  • 每个节点可选择的特征为:除该节点的父节点和祖父节点之外的所有特征。
  • 若当前节点为空集,对应的处理措施为:将其设置为叶节点,类别设置为其父节点,所含样本最多的类别。

四、三种决策树对比

支持模型树结构特征选择连续值处理
ID3分类多叉树信息增益不支持
C4.5分类多叉树信息增益率支持
CART分类、多回归二叉树基尼系数、均方差支持

五、 划分选择

我们希望决策树的分支节点所包含的样本尽可能属于同一类别,即节点的“纯度”越来越高。

我们使用周志华一书《机器学习》中的“西瓜数据集”进行计算:
在这里插入图片描述

1.ID3信息增益

信 息 熵 : E n t ( D ) = − ∑ k = 1 ∣ Y ∣ p k l o g 2 p k 信息熵:Ent(D) = - \sum_{k = 1}^{|Y|}p_k log_2 p_k Ent(D)=k=1Ypklog2pk

信 息 增 益 : G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) 信息增益:Gain(D,a) = Ent(D) - \sum_{v = 1}^{V}\frac{|D^v|}{|D|}Ent(D^v) Gain(D,a)=Ent(D)v=1VDDvEnt(Dv)

  • |Y|:代表分类标签的数量,“好瓜”、“坏瓜”,所以|Y|=2
  • a:代表数据集所包含的特征,a={色泽,根蒂,敲声,纹理,脐部,触感}
  • v:代表每一个特征下所包含的属性,例如特征“色泽“下v={青绿,乌黑,浅白}
  • 正例:”是“好瓜
  • 反例:”否“好瓜
  • ∣ D v ∣ ∣ D ∣ \frac{|D^v|}{|D|} DDv:代表该节点所包含的数据数量占其父节点数据数量的比例

  1. 根节点包含D中所有数据,数据总数:17,正例占p1=8/17,反例占p2=9/17。

    根节点的信息熵为:
    E n t ( D ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 8 17 l o g 2 8 17 + 9 17 l o g 2 9 17 ) = 0.998 Ent(D)=-\sum_{k=1}^{2}p_k log_2 p_k=-(\frac{8}{17}log_2 \frac{8}{17}+\frac{9}{17}log_2 \frac{9}{17})=0.998 Ent(D)=k=12pklog2pk=(178log2178+179log2179)=0.998

​ 然后,我们要计算出当前特征集合{色泽,根蒂,敲声,纹理,脐部,触感}中每个特征的信息熵和信息增益。

★特征”色泽“:
D 1 D^1 D1(色泽=青绿):{1,4,6,10,13,17},正例p1=3/6,反例p2=3/6
E n t ( D 1 ) = − ( 3 6 l o g 2 3 6 + 3 6 l o g 2 3 6 ) = 1.000 Ent(D^1)=-(\frac{3}{6}log_2 \frac{3}{6} + \frac{3}{6}log_2 \frac{3}{6}) = 1.000 Ent(D1)=(63log263+63log263)=1.000

D 2 D^2 D2(色泽=乌黑):{2,3,7,8,9,15},正例p1=4/6,反例p2=2/6
E n t ( D 2 ) = − ( 4 6 l o g 2 4 6 + 2 6 l o g 2 2 6 ) = 0.918 Ent(D^2)=-(\frac{4}{6}log_2 \frac{4}{6} + \frac{2}{6}log_2 \frac{2}{6}) = 0.918 Ent(D2)=(64log264+62log262)=0.918

D 3 D^3 D3(色泽=浅白):{5,11,12,14,16},正例p1=1/5,反例p2=4/5
E n t ( D 3 ) = − ( 1 5 l o g 2 1 5 + 4 5 l o g 2 4 5 ) = 0.722 Ent(D^3)=-(\frac{1}{5}log_2 \frac{1}{5} + \frac{4}{5}log_2 \frac{4}{5}) = 0.722 Ent(D3)=(51log251+54log254)=0.722

"色泽"特征的信息增益:

G a i n ( D , 色 泽 ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) = 0.998 − ( 6 17 × 1 + 6 17 × 0.918 + 5 17 × 0.722 ) = 0.109 Gain(D,色泽)=Ent(D) - \sum_{v = 1}^{V}\frac{|D^v|}{|D|}Ent(D^v)\\ =0.998-(\frac{6}{17}\times 1 +\frac{6}{17}\times 0.918 + \frac{5}{17}\times 0.722)=0.109 Gain(D,)=Ent(D)v=1VDDvEnt(Dv)=0.998(176×1+176×0.918+175×0.722)=0.109

类似的,计算出其他特征的信息增益:
Gain(D,根蒂)=0.143 \quad Gain(D,敲声)=0.141 \quad Gain(D,纹理)=0.381
Gain(D,脐部)=0.289 \quad Gain(D,触感)=0.006

特征”纹理”的信息增益最大,选他作为划分属性。
在这里插入图片描述

其中节点上方红色字体表示:创建该node节点时可选择的特征。

  1. D 1 D^1 D1中有编号为{1,2,3,4,5,6,8,10,15},可用特征集合为{色泽,根蒂,敲声,脐部,触感},其中正例p1=7/9,反例p2=2/9。

D 1 D^1 D1节点的信息熵为:
E n t ( D 1 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 7 9 l o g 2 7 9 + 2 9 l o g 2 2 9 ) = 0.763 Ent(D^1)=-\sum_{k=1}^{2}p_k log_2 p_k=-(\frac{7}{9}log_2 \frac{7}{9}+\frac{2}{9}log_2 \frac{2}{9})=0.763 Ent(D1)=k=12pklog2pk=(97log297+92log292)=0.763
★特征”色泽“:
D 11 D^{11} D11(色泽=青绿):{1,4,6,10},正例p1=3/4,反例p2=1/4
E n t ( D 11 ) = − ( 3 4 l o g 2 3 4 + 1 4 l o g 2 1 4 ) = 0.811 Ent(D^{11})=-(\frac{3}{4}log_2 \frac{3}{4} + \frac{1}{4}log_2 \frac{1}{4}) = 0.811 Ent(D11)=(43log243+41log241)=0.811

D 12 D^{12} D12(色泽=乌黑):{2,3,8,15},正例p1=3/4,反例p2=1/4
E n t ( D 12 ) = − ( 3 4 l o g 2 3 4 + 1 4 l o g 2 1 4 ) = 0.811 Ent(D^{12})=-(\frac{3}{4}log_2 \frac{3}{4} + \frac{1}{4}log_2 \frac{1}{4}) = 0.811 Ent(D12)=(43log243+41log241)=0.811

D 13 D^{13} D13(色泽=浅白):{5},正例p1=1,反例p2=0
E n t ( D 13 ) = − ( 1 l o g 2 1 + 0 l o g 2 0 ) = 0 Ent(D^{13})=-(1log_2 1 + 0log_2 0) =0 Ent(D13)=(1log21+0log20)=0

"色泽"特征的信息增益:

G a i n ( D 1 , 色 泽 ) = E n t ( D 1 ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) = 0.763 − ( 4 9 × 0.811 + 4 9 × 0.811 + 1 9 × 0 ) = 0.043 Gain(D^1,色泽)=Ent(D^1) - \sum_{v = 1}^{V}\frac{|D^v|}{|D|}Ent(D^v)\\ =0.763-(\frac{4}{9}\times 0.811 +\frac{4}{9}\times 0.811 + \frac{1}{9}\times 0)=0.043 Gain(D1,)=Ent(D1)v=1VDDvEnt(Dv)=0.763(94×0.811+94×0.811+91×0)=0.043

类似的,计算出其他特征的信息增益:
Gain(D1,根蒂)=0.458 \quad Gain(D1,敲声)=0.331
Gain(D1,脐部)=0.458 \quad Gain(D1,触感)=0.458
其中“根蒂”,“脐部”,“触感”均获得最大信息增益,可任选其一作为特征划分。此处我们选择“根蒂”特征。
在这里插入图片描述

  1. D 11 D^{11} D11中有编号为{1,2,3,4,5},可用特征集合为{色泽,敲声,脐部,触感},其中正例p1=1,反例p2=0。
    D 11 D^{11} D11节点的信息熵为:
    E n t ( D 11 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 1 l o g 2 1 + 0 l o g 2 0 ) = 0 Ent(D^{11})=-\sum_{k=1}^{2}p_k log_2 p_k=-(1log_2 1 +0log_2 0)=0 Ent(D11)=k=12pklog2pk=(1log21+0log20)=0

由于Ent(D11)的值已达最小,说明D11中数据纯度已达到最高,数据分类已完全分类,则无需再往下进行划分,将该节点设置为叶子节点。

  1. D 12 D^{12} D12中编号为{6,8,15},可用特征集合为{色泽,敲声,脐部,触感},其中正例p1=2/3,反例p2=1/3。
    D 12 D^{12} D12节点的信息熵为:
    E n t ( D 12 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 2 3 l o g 2 2 3 + 1 3 l o g 2 1 3 ) = 0.918 Ent(D^{12})=-\sum_{k=1}^{2}p_k log_2 p_k=-(\frac{2}{3}log_2 \frac{2}{3} +\frac{1}{3}log_2 \frac{1}{3})=0.918 Ent(D12)=k=12pklog2pk=(32log232+31log231)=0.918
    ★特征“色泽”:
    D 121 D^{121} D121(色泽=青绿):{6},正例p1=1,反例p2=0
    E n t ( D 121 ) = − ( 1 l o g 2 1 + 0 l o g 2 0 ) = 0 Ent(D^{121})=-(1log_2 1 + 0log_2 0) = 0 Ent(D121)=(1log21+0log20)=0


    D 122 D^{122} D122(色泽=乌黑):{8,15},正例p1=1/2,反例p2=1/2
    E n t ( D 122 ) = − ( 1 2 l o g 2 1 2 + 1 2 l o g 2 1 2 ) = 1 Ent(D^{122})=-(\frac{1}{2}log_2 \frac{1}{2} + \frac{1}{2}log_2 \frac{1}{2}) = 1 Ent(D122)=(21log221+21log221)=1


    D 123 D^{123} D123(色泽=浅白):{ },正例p1=0,反例p2=0
    E n t ( D 123 ) = − ( 0 l o g 2 0 + 0 l o g 2 0 ) = 0 Ent(D^{123})=-(0log_2 0 + 0log_2 0) =0 Ent(D123)=(0log20+0log20)=0

"色泽"特征的信息增益:

G a i n ( D 12 , 色 泽 ) = E n t ( D 12 ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) = 0.918 − ( 1 3 × 0 + 2 3 × 1 + 0 × 0 ) = 0.251 Gain(D^{12},色泽)=Ent(D^{12}) - \sum_{v = 1}^{V}\frac{|D^v|}{|D|}Ent(D^v)\\ =0.918-(\frac{1}{3}\times 0 +\frac{2}{3}\times 1 + 0\times 0)=0.251 Gain(D12,)=Ent(D12)v=1VDDvEnt(Dv)=0.918(31×0+32×1+0×0)=0.251

类似的,计算出其他特征的信息增益:
Gain(D12,敲声)=0 \quad Gain(D12,脐部)=0 \quad Gain(D12,触感)=0.251

其中“色泽”和“触感”均获得最大信息增益,可任选其一作为特征划分。此处我们选择“色泽”特征。
在这里插入图片描述

  1. D 121 D^{121} D121中编号为{6},可用特征集合为{敲声,脐部,触感},其中p1=1,p2=0。
    D 121 D^{121} D121节点的信息熵为:
    E n t ( D 121 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 1 l o g 2 1 + 0 l o g 2 0 ) = 0 Ent(D^{121})=-\sum_{k=1}^{2}p_k log_2 p_k=-(1log_2 1 +0 log_2 0)=0 Ent(D121)=k=12pklog2pk=(1log21+0log20)=0
    将该节点划分为叶子节点。

  2. D 122 D{122} D122中编号为{8,15},可用特征集合为{敲声,脐部,触感},p1=1/2,p2=1/2。
    D 122 D^{122} D122节点的信息熵为:
    E n t ( D 122 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 1 2 l o g 2 1 2 + 1 2 l o g 2 1 2 ) = 1 Ent(D^{122})=-\sum_{k=1}^{2}p_k log_2 p_k=-(\frac{1}{2}log_2 \frac{1}{2} +\frac{1}{2} log_2 \frac{1}{2})=1 Ent(D122)=k=12pklog2pk=(21log221+21log221)=1
    ★特征“触感”:
    D 1221 D^{1221} D1221(触感=硬滑):{8},正例p1=1,反例p2=0
    E n t ( D 1221 ) = − ( 1 l o g 2 1 + 0 l o g 2 0 ) = 0 Ent(D^{1221})=-(1log_2 1 + 0log_2 0) = 0 Ent(D1221)=(1log21+0log20)=0


    D 1222 D^{1222} D1222(触感=软粘):{15},正例p1=0,反例p2=1
    E n t ( D 1221 ) = − ( 0 l o g 2 0 + 1 l o g 2 1 ) = 0 Ent(D^{1221})=-(0log_2 0 + 1log_2 1) = 0 Ent(D1221)=(0log20+1log21)=0

    "触感"特征的信息增益:

G a i n ( D 122 , 色 泽 ) = E n t ( D 122 ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) = 1 − ( 1 2 × 0 + 1 2 × 0 ) = 1 Gain(D^{122},色泽)=Ent(D^{122}) - \sum_{v = 1}^{V}\frac{|D^v|}{|D|}Ent(D^v)\\ =1-(\frac{1}{2}\times 0 +\frac{1}{2}\times 0)=1 Gain(D122,)=Ent(D122)v=1VDDvEnt(Dv)=1(21×0+21×0)=1
类似的,计算出其他特征的信息增益:
Gain(D122,敲声)=0 \quad Gain(D122,脐部)=0

所以选择“触感”特征作为划分节点。
在这里插入图片描述

  1. D 1221 D^{1221} D1221中编号为{8},可用特征集合为{敲声,脐部},p1=1,p2=0。
    D 1221 D^{1221} D1221节点的信息熵为:
    E n t ( D 1221 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 1 l o g 2 1 + 0 l o g 2 0 ) = 0 Ent(D^{1221})=-\sum_{k=1}^{2}p_k log_2 p_k=-(1log_2 1 +0 log_2 0)=0 Ent(D1221)=k=12pklog2pk=(1log21+0log20)=0
    所以将该节点设置为叶子节点。

  2. D 1222 D^{1222} D1222中编号为{15},可用特征集合为{敲声,脐部},p1=0,p2=1。
    D 1222 D^{1222} D1222节点的信息熵为:
    E n t ( D 1222 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 0 l o g 2 0 + 1 l o g 2 1 ) = 0 Ent(D^{1222})=-\sum_{k=1}^{2}p_k log_2 p_k=-(0log_2 0 +1 log_2 1)=0 Ent(D1222)=k=12pklog2pk=(0log20+1log21)=0

此时需要往回遍历,找到第三层“色泽”特征下的D123属性集合。

  1. D 123 D^{123} D123中为空集{ },将其设置为叶节点,且类别设置为其父节点所含样本最多的类别即{6,8,15}
    中,p1=2/3,p2=1/3,所以该叶子节点类别为“好瓜”。

继续往回遍历,找到第二层“根蒂”特征下的D13属性集合。

  1. D 13 D^{13} D13中编号为{10},可用特征集合为{色泽,敲声,脐部,触感},p1=0,p2=1。
    D 13 D^{13} D13节点的信息熵为:
    E n t ( D 13 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 0 l o g 2 0 + 1 l o g 2 1 ) = 0 Ent(D^{13})=-\sum_{k=1}^{2}p_k log_2 p_k=-(0log_2 0 +1 log_2 1)=0 Ent(D13)=k=12pklog2pk=(0log20+1log21)=0
    所以将该节点设置为叶子节点。

继续往回遍历,找到第一层“纹理”特征下的D2属性集合。

  1. D 2 D^{2} D2中编号为{7,9,13,14,17},可用特征集合为{色泽,根蒂,敲声,脐部,触感},p1=1/5,p2=4/5。
    D 2 D^{2} D2节点的信息熵为:
    E n t ( D 2 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 1 5 l o g 2 1 5 + 4 5 l o g 2 4 5 ) = 0.722 Ent(D^{2})=-\sum_{k=1}^{2}p_k log_2 p_k=-(\frac{1}{5}log_2 \frac{1}{5} +\frac{4}{5} log_2 \frac{4}{5})=0.722 Ent(D2)=k=12pklog2pk=(51log251+54log254)=0.722
    ★特征“色泽”:
    D 21 D^{21} D21(色泽=青绿):{13,17},正例p1=0,反例p2=1
    E n t ( D 21 ) = − ( 0 l o g 2 1 + 1 l o g 2 0 ) = 0 Ent(D^{21})=-(0log_2 1 + 1log_2 0) = 0 Ent(D21)=(0log21+1log20)=0


    D 22 D^{22} D22(色泽=乌黑):{7,9},正例p1=1/2,反例p2=1/2
    E n t ( D 22 ) = − ( 1 2 l o g 2 1 2 + 1 2 l o g 2 1 2 ) = 1 Ent(D^{22})=-(\frac{1}{2}log_2 \frac{1}{2} + \frac{1}{2}log_2 \frac{1}{2}) = 1 Ent(D22)=(21log221+21log221)=1


    D 23 D^{23} D23(色泽=浅白):{14},正例p1=0,反例p2=1
    E n t ( D 23 ) = − ( 0 l o g 2 0 + 1 l o g 2 1 ) = 0 Ent(D^{23})=-(0log_2 0 + 1log_2 1) =0 Ent(D23)=(0log20+1log21)=0

    "色泽"特征的信息增益:

G a i n ( D 2 , 色 泽 ) = E n t ( D 2 ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) = 0.722 − ( 2 5 × 0 + 2 5 × 1 + 1 5 × 0 ) = 0.322 Gain(D^{2},色泽)=Ent(D^{2}) - \sum_{v = 1}^{V}\frac{|D^v|}{|D|}Ent(D^v)\\ =0.722-(\frac{2}{5}\times 0 +\frac{2}{5}\times 1 + \frac{1}{5}\times 0)=0.322 Gain(D2,)=Ent(D2)v=1VDDvEnt(Dv)=0.722(52×0+52×1+51×0)=0.322
类似的,计算出其他特征的信息增益:
Gain(D2,敲声)=0.322 \quad Gain(D2,脐部)= 0.172
Gain(D2,触感)= 0.722 \quad Gain(D2,根蒂)= 0.073

特征“触感”的信息增益最大,选他作为划分属性。
在这里插入图片描述
12. D 21 D^{21} D21中编号为{9,13,14,17},可用特征集合为{色泽,根蒂,敲声,脐部},其中正例p1=0,反例p2=1.

D 21 D{21} D21节点的信息熵为:
E n t ( D 21 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 0 l o g 2 0 + 1 l o g 2 1 ) = 0 Ent(D^{21})=-\sum_{k=1}^{2}p_k log_2 p_k=-(0log_2 0 +1 log_2 1)=0 Ent(D21)=k=12pklog2pk=(0log20+1log21)=0
所以将该节点划分为叶子节点。

  1. D 22 D^{22} D22中编号为{7},可用特征集合为{色泽,根蒂,敲声,脐部},其中正例p1=1,反例p2=0.

D 22 D{22} D22节点的信息熵为:
E n t ( D 22 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 1 l o g 2 1 + 0 l o g 2 0 ) = 0 Ent(D^{22})=-\sum_{k=1}^{2}p_k log_2 p_k=-(1log_2 1 +0 log_2 0)=0 Ent(D22)=k=12pklog2pk=(1log21+0log20)=0
所以将该节点划分为叶子节点。

往回遍历,找到第一层“纹理”特征下的D3属性集合。

  1. D 3 D^3 D3中有编号为{11,12,16},可用特征集合为{色泽,根蒂,敲声,脐部,触感},其中正例p1=0,反例p2=1。

D 3 D{3} D3节点的信息熵为:
E n t ( D 3 ) = − ∑ k = 1 2 p k l o g 2 p k = − ( 0 l o g 2 0 + 1 l o g 2 1 ) = 0 Ent(D^{3})=-\sum_{k=1}^{2}p_k log_2 p_k=-(0log_2 0 +1 log_2 1)=0 Ent(D3)=k=12pklog2pk=(0log20+1log21)=0

所以将其设置为叶子节点。
在这里插入图片描述

至此,使用信息增益构建的ID3决策树已经建立好了,如上图所示。

2.C4.5信息增益率

信息增益缺点:是对可取属性多的特征有偏好,比如如果把“编号”这一列当作特征也考虑在内,那么可以计算处它的信息增益大于其他的候选特征,因为“编号”有17个可取的数值,产生17个分支,每个分支节点仅包含一个样本,显然这些分支节点的纯度最大。但是,这样的决策树显然不具有泛化能力,无法对新样本进行有效预测。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)} Gainratio(D,a)=IV(a)Gain(D,a)
其中:
I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ I V ( a ) IV(a)=-\sum_{v=1}^{V} \frac{|D^v|}{|D|}log_2 \frac{|D^v|}{|D|}IV(a) IV(a)=v=1VDDvlog2DDvIV(a)
IV(a)称为特征a的“固有值”,特征a的可能取值数目越多(即V越大),则 IV(a)的值通常会越大。但增益率也可能产生一个问题就是对属性较少的特征有所偏好。注意:C4.5算法并不是直接选择增益率最大的候选划分特征,而是先从候选划分特征中找出信息增益高于平均水平的特征,再从中选择增益率最高的。


由于信息增益的计算方法在ID3中已经详细介绍并给出计算例子,在这里不再赘述,重点计算信息增益率的求解。

  1. 计算数据集D中所有特征的信息增益和信息增益率:

    Gain(D,色泽 ) = 0.109 \quad Gain(D,根蒂) = 0.143 \quad Gain(D,敲声) = 0.141

    Gain(D,纹理) = 0.381 \quad Gain(D,脐部) = 0.289 \quad Gain(D,触感) = 0.006
    a v e _ G a i n ( D ) = 0.109 + 0.143 + 0.141 + 0.381 + 0.289 + 0.006 6 = 0.178 ave\_Gain(D)=\frac{0.109+0.143+0.141+0.381+0.289+0.006}{6}=0.178 ave_Gain(D)=60.109+0.143+0.141+0.381+0.289+0.006=0.178
    选择信息增益高于平均水平的特征,即选择“纹理”和“脐部”计算信息增益率:

    ★特征“纹理”:清晰:9;稍糊:5;模糊:3
    I V ( 纹 理 ) = − ( 9 17 l o g 2 9 17 + 5 17 l o g 2 5 17 + 3 17 l o g 2 3 17 ) = 1.446 IV(纹理)=-(\frac{9}{17}log_2 \frac{9}{17} + \frac{5}{17}log_2 \frac{5}{17} + \frac{3}{17}log_2 \frac{3}{17})=1.446 IV()=(179log2179+175log2175+173log2173)=1.446
    信息增益率为:
    G a i n _ r a t i o ( D , 纹 理 ) = 0.381 1.446 = 0.263 Gain\_ratio(D,纹理)=\frac{0.381}{1.446}=0.263 Gain_ratio(D,)=1.4460.381=0.263
    ★特征“脐部”:凹陷:7;稍凹:6;平坦:4
    I V ( 脐 部 ) = − ( 7 17 l o g 2 7 17 + 6 17 l o g 2 6 17 + 4 17 l o g 2 4 17 ) = 1.548 IV(脐部)=-(\frac{7}{17}log_2 \frac{7}{17} + \frac{6}{17}log_2 \frac{6}{17} + \frac{4}{17}log_2 \frac{4}{17})=1.548 IV()=(177log2177+176log2176+174log2174)=1.548
    信息增益率为:
    G a i n _ r a t i o ( D , 脐 部 ) = 0.289 1.548 = 0.187 Gain\_ratio(D,脐部)=\frac{0.289}{1.548}=0.187 Gain_ratio(D,)=1.5480.289=0.187
    “纹理”的信息增益率大于“脐部”的信息增益率,所以选择特征“纹理”当作节点,划分数据集。
    在这里插入图片描述

  2. 计算数据集D1中可用特征的信息增益和信息增益率:

    Gain(D1,色泽 ) = 0.043 \quad Gain(D1,根蒂) = 0.458 \quad Gain(D1,敲声) = 0.331

    Gain(D1,脐部) = 0.458 \quad Gain(D1,触感) = 0.458
    a v e _ G a i n ( D 1 ) = 0.043 + 0.458 + 0.331 + 0.458 + 0.458 5 = 0.3496 ave\_Gain(D1)=\frac{0.043+0.458+0.331+0.458+0.458}{5}=0.3496 ave_Gain(D1)=50.043+0.458+0.331+0.458+0.458=0.3496
    选择信息增益高于平均水平的特征,即选择“根蒂”、“触感”和“脐部”计算信息增益率:

    ★特征“根蒂”:蜷缩:5;稍蜷:3;硬挺:1
    I V ( 根 蒂 ) = − ( 5 9 l o g 2 5 9 + 3 9 l o g 2 3 9 + 1 9 l o g 2 1 9 ) = 1.351 IV(根蒂)=-(\frac{5}{9}log_2 \frac{5}{9} + \frac{3}{9}log_2 \frac{3}{9} + \frac{1}{9}log_2 \frac{1}{9})=1.351 IV()=(95log295+93log293+91log291)=1.351
    信息增益率为:
    G a i n _ r a t i o ( D 1 , 根 蒂 ) = 0.458 1.351 = 0.339 Gain\_ratio(D1,根蒂)=\frac{0.458}{1.351}=0.339 Gain_ratio(D1,)=1.3510.458=0.339
    ★特征“脐部”:凹陷:5;稍凹:3;平坦:1
    I V ( 脐 部 ) = − ( 5 9 l o g 2 5 9 + 3 9 l o g 2 3 9 + 1 9 l o g 2 1 9 ) = 1.351 IV(脐部)=-(\frac{5}{9}log_2 \frac{5}{9} + \frac{3}{9}log_2 \frac{3}{9} + \frac{1}{9}log_2 \frac{1}{9})=1.351 IV()=(95log295+93log293+91log291)=1.351
    信息增益率为:
    G a i n _ r a t i o ( D 1 , 脐 部 ) = 0.458 1.351 = 0.339 Gain\_ratio(D1,脐部)=\frac{0.458}{1.351}=0.339 Gain_ratio(D1,)=1.3510.458=0.339
    ★特征“触感”:硬滑:6;软粘:3
    I V ( 触 感 ) = − ( 6 9 l o g 2 6 9 + 3 9 l o g 2 3 9 ) = 0.918 IV(触感)=-(\frac{6}{9}log_2 \frac{6}{9} + \frac{3}{9}log_2 \frac{3}{9} )=0.918 IV()=(96log296+93log293)=0.918
    信息增益率为:
    G a i n _ r a t i o ( D 1 , 触 感 ) = 0.458 0.918 = 0.499 Gain\_ratio(D1,触感)=\frac{0.458}{0.918}=0.499 Gain_ratio(D1,)=0.9180.458=0.499
    “触感”的信息增益率最大,所以选择特征“触感”当作节点,划分数据集。

    在这里插入图片描述

  3. 计算数据集D11中的信息:

    由于数据集D11的信息熵为0,所以此节点以完全分类,将其设置为叶子节点。

  4. 计算数据集D12中的信息:

    Gain(D12,色泽)=0.251 \quad Gain(D12,根蒂)=0.251

    Gain(D12,敲声)=0.251 \quad Gain(D12,脐部)=0.251

    ★特征“脐部”:凹陷:0;稍凹:2;平坦:1
    I V ( 脐 部 ) = − ( 0 l o g 2 0 + 2 3 l o g 2 2 3 + 1 3 l o g 2 1 3 ) = 0.251 IV(脐部)=-(0 log_2 0 + \frac{2}{3}log_2 \frac{2}{3} + \frac{1}{3}log_2 \frac{1}{3})=0.251 IV()=(0log20+32log232+31log231)=0.251
    ​ 不难发现,这四个特征均是一个属性包含数据为0,一个属性包含数据为2,另一个属性包含数据为1,所以他们的信息增益率均相同,这种情况我们可以任选其一划分数据,类别为其中包含最多的类别;也可以将其设置为叶子节点,牺牲正确率换取更低的决策树层数。在这里我采取的方法为后者。

    在这里插入图片描述

  5. 计算数据集D2中的信息

    类似于数据集D12的情况,由于D2中只包含一个正例,所以依然可以采取牺牲正确率换取更低的决策树层数,或是进行计算选出一个特征来划分。此处采取设置为叶节点,有兴趣的同学可以自行计算。

  6. 计算数据集D3中的信息

    由于数据集D11的信息熵为0,所以此节点以完全分类,将其设置为叶子节点。

    在这里插入图片描述

3.CART基尼系数

CART决策树:使用”基尼指数“来选择划分特征。数据集的纯度可用基尼值(Gini)来度量。Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率,Gini值越小,则数据集的纯度越高。
G i n i ( D ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 Gini(D)=1-\sum_{k=1}^{|Y|}p_{k}^{2} Gini(D)=1k=1Ypk2
特征的“基尼指数”(Gini index)定义如下,选择使得划分后基尼指数最小的特征作为最优划分特征。
G i n i _ i n d e x ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ G i n i ( D v ) Gini\_index(D,a)=\sum_{v=1}^{V} \frac{|D^v|}{|D|}Gini(D^v) Gini_index(D,a)=v=1VDDvGini(Dv)

计算每个特征的基尼指数前,先计算下该节点的基尼值,若基尼值为0,则表示该节点下的数据集已完全分类。


  1. 根节点包含D中所有数据,数据总数为17,可用特征{色泽,根蒂,敲声,纹理,脐部,触感}:

    ★特征“色泽”:

    青绿:{1,4,6,10,13,17},数据总计:6,正例p1= 3/6,反例p2= 3/6
    G i n i ( 青 绿 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 3 6 × 3 6 + 3 6 × 3 6 ) = 0.5 Gini(青绿)=1-\sum_{k=1}^{|Y|}p_k^2=1-(\frac{3}{6}\times \frac{3}{6} + \frac{3}{6}\times \frac{3}{6})=0.5 Gini(绿)=1k=1Ypk2=1(63×63+63×63)=0.5
    乌黑:{2,3,7,8,9,15},数据总计:6,正例p1= 4/6,反例p2= 2/6
    G i n i ( 乌 黑 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 4 6 × 4 6 + 2 6 × 2 6 ) = 0.444 Gini(乌黑)=1-\sum_{k=1}^{|Y|}p_k^2=1-(\frac{4}{6}\times \frac{4}{6} + \frac{2}{6}\times \frac{2}{6})=0.444 Gini()=1k=1Ypk2=1(64×64+62×62)=0.444
    浅白:{5,11,12,14,16},数据总计:5,正例p1= 1/5,反例p2= 4/5
    G i n i ( 浅 白 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 1 5 × 1 5 + 4 5 × 4 5 ) = 0.32 Gini(浅白)=1-\sum_{k=1}^{|Y|}p_k^2=1-(\frac{1}{5}\times \frac{1}{5} + \frac{4}{5}\times \frac{4}{5})=0.32 Gini()=1k=1Ypk2=1(51×51+54×54)=0.32

    “色泽”特征的基尼指数为:
    G i n i _ i n d e x ( D , 色 泽 ) = 6 17 × 0.5 + 6 17 × 0.444 + 5 17 × 0.32 = 0.427 Gini\_index(D,色泽)=\frac{6}{17}\times 0.5 +\frac{6}{17}\times 0.444 + \frac{5}{17} \times 0.32=0.427 Gini_index(D,)=176×0.5+176×0.444+175×0.32=0.427
    同理可以计算出其他特征的基尼指数为:

    Gini_index(D,根蒂) = 0.422 \quad Gini_index(D,敲声) = 0.424 \quad Gini_index(D,纹理) = 0.277

    Gini_index(D,脐部) = 0.345 \quad Gini_index(D,触感) = 0.494

    选择基尼指数最小的特征进行划分,所以此次划分使用“纹理”特征。

    在这里插入图片描述

  2. D1中包含数据总数为9,可用特征{色泽,根蒂,敲声,脐部,触感}:

    ★特征“色泽”

    青绿:{1,4,6,10},数据总计:4,正例p1= 3/4,反例p2= 1/4
    G i n i ( 青 绿 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 3 4 × 3 4 + 1 4 × 1 4 ) = 0.375 Gini(青绿)=1-\sum_{k=1}^{|Y|}p_k^2=1-(\frac{3}{4}\times \frac{3}{4} + \frac{1}{4}\times \frac{1}{4})=0.375 Gini(绿)=1k=1Ypk2=1(43×43+41×41)=0.375
    乌黑:{2,3,8,15},数据总计:4,正例p1= 3/4,反例p2= 1/4
    G i n i ( 乌 黑 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 3 4 × 3 4 + 1 4 × 1 4 ) = 0.375 Gini(乌黑)=1-\sum_{k=1}^{|Y|}p_k^2=1-(\frac{3}{4}\times \frac{3}{4} + \frac{1}{4}\times \frac{1}{4})=0.375 Gini()=1k=1Ypk2=1(43×43+41×41)=0.375
    浅白:{5},数据总计:1,正例p1= 1,反例p2= 0
    G i n i ( 浅 白 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 1 × 1 + 0 × 0 ) = 0 Gini(浅白)=1-\sum_{k=1}^{|Y|}p_k^2=1-(1\times 1 + 0\times 0)=0 Gini()=1k=1Ypk2=1(1×1+0×0)=0
    “色泽”特征的基尼指数为:
    G i n i _ i n d e x ( D 1 , 色 泽 ) = 4 9 × 0.375 + 4 9 × 0.375 + 1 9 × 0 = 0.333 Gini\_index(D^1,色泽)=\frac{4}{9}\times 0.375 +\frac{4}{9}\times 0.375 + \frac{1}{9} \times 0=0.333 Gini_index(D1,)=94×0.375+94×0.375+91×0=0.333
    同理可以计算出其他特征的基尼指数为:

    Gini_index(D1,根蒂) = 0.148 \quad Gini_index(D1,敲声) = 0.185

    Gini_index(D1,脐部) = 0.148 \quad Gini_index(D1,触感) = 0.148

    由于“根蒂”、“脐部”和“触感”的基尼指数相同,任选其一作为特征进行划分数据集,这里我们选择“根蒂”特征:

    在这里插入图片描述

  3. D11中包含数据总数为5,其中正例p1=1,反例p2=0。

    该节点基尼值为:
    G i n i ( D 1 1 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 1 × 1 + 0 × 0 ) = 0 Gini(D^11)=1-\sum_{k=1}^{|Y|}p_k^2=1-(1\times 1 +0 \times 0) = 0 Gini(D11)=1k=1Ypk2=1(1×1+0×0)=0
    该节点基尼值已达最小,将其设置为叶子节点。

  4. D12中包含数据总数位3,可用特征为{色泽,敲声,脐部,触感}

    ★特征“色泽”:

    青绿:{6},数据总计:1,正例p1= 1,反例p2= 1/40
    G i n i ( 青 绿 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 1 × 1 + 0 × 0 ) = 0 Gini(青绿)=1-\sum_{k=1}^{|Y|}p_k^2=1-(1\times 1 + 0\times 0)=0 Gini(绿)=1k=1Ypk2=1(1×1+0×0)=0
    乌黑:{8,15},数据总计:2,正例p1= 1/2,反例p2= 1/2
    G i n i ( 乌 黑 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 1 2 × 1 2 + 1 2 × 1 2 ) = 0.5 Gini(乌黑)=1-\sum_{k=1}^{|Y|}p_k^2=1-(\frac{1}{2}\times \frac{1}{2} + \frac{1}{2}\times \frac{1}{2})=0.5 Gini()=1k=1Ypk2=1(21×21+21×21)=0.5
    浅白:{ },数据总计:0,正例p1= 0,反例p2= 0
    G i n i ( 浅 白 ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 = 1 − ( 0 × 0 + 0 × 0 ) = 0 Gini(浅白)=1-\sum_{k=1}^{|Y|}p_k^2=1-(0\times 0 + 0\times 0)=0 Gini()=1k=1Ypk2=1(0×0+0×0)=0
    “色泽”特征的基尼指数为:
    G i n i _ i n d e x ( D 12 , 色 泽 ) = 1 3 × 0 + 2 3 × 0.5 + 0 × 0 = 0.333 Gini\_index(D^{12},色泽)=\frac{1}{3}\times 0 +\frac{2}{3}\times 0.5 + 0 \times 0=0.333 Gini_index(D12,)=31×0+32×0.5+0×0=0.333
    同理可以计算出其他特征的基尼指数为:

    Gini_index(D12,敲声) = 0.444 \quad Gini_index(D12,脐部) = 0.444 \quad Gini_index(D12,触感) = 0.333

    由于“色泽”和“触感”的基尼指数相同,任选其一作为特征进行划分数据集,这里我们选择“色泽”特征:
    在这里插入图片描述

  5. D121中已完全分类,设置为叶节点。

  6. D122中包含数据总数为2,可用特征为{敲声,脐部,触感}

    Gini_index(D122,敲声) = 0.5 \quad Gini_index(D122,脐部) = 0.5 \quad Gini_index(D122,触感) = 0

    所以选择“触感”特征划分数据集。

在这里插入图片描述

  1. D1221中已完全分类,设置为叶节点。

  2. D1222中已完全分类,设置为叶节点。

往回遍历,找到第三层“色泽”特征下的D123属性集合。

  1. 该节点集合为空,设置为其父节点数据中类别最多的类。

往回遍历,找到第二层“根蒂”特征下的D13属性集合

  1. D13中已完全分类,设置为叶节点。

    在这里插入图片描述

往回遍历,找到第一层“纹理”特征下的D2属性集合

  1. D2中包含数据总数为5,可用特征为{色泽,根蒂,敲声,脐部,触感}

    Gini_index(D2,敲声) = 0.467 \quad Gini_index(D2,脐部) = 0.267 \quad Gini_index(D2,触感) = 0

    Gini_index(D2,色泽) = 0.2 \quad Gini_index(D1,根蒂) = 0.3

    所以选择“触感”作为特征划分数据集。

    在这里插入图片描述

  2. D21中已完全分类,设置为叶节点。

  3. D22中已完全分类,设置为叶节点。

  4. D3中已完全分类,设置为叶节点。

建立好的决策树如下图所示:

在这里插入图片描述

至此,三种决策树构建时的计算过程已经整理完了,在下一篇文章中我们来看看预剪枝与缺失值处理是怎么操作的。

【参考文献】

Logo

CSDN联合极客时间,共同打造面向开发者的精品内容学习社区,助力成长!

更多推荐