作者:張張張張
github地址:/zhanghekai
【转载请注明出处,谢谢!】
【机器学习系列】之“西瓜数据集”决策树构建数学公式计算过程
【机器学习系列】之决策树剪枝和连续值、缺失值处理数学公式计算
【机器学习系列】之ID3、C4.5、CART决策树构建代码
文章目录
一、决策树概述二、决策树场景三、决策树概念须知1.名词定义2.构建“树”时的基本要求四、三种决策树对比五、 划分选择1.ID3信息增益2.C4.5信息增益率3.CART基尼系数一、决策树概述
决策树(Decision Tree)算法是一种基本的分类与回归方法,是最经常使用的数据挖掘算法之一。决策树是一种非线性有监督分类模型必须将已有的数据进行离散化,即:从字符串变成数值。构造决策树的基本思想是随着树深度的增加,节点的“熵”迅速降低,熵降低的速度越快越好,这样我们有望得到一棵高度最矮的决策树。
决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树的定义:分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型:内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性(features),叶结点表示一个类(labels)。
用决策树对需要测试的实例进行分类:从根节点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点;这时,每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点。最后将实例分配到叶结点的类中。
决策树学习通常包括 3 个步骤:特征选择、决策树的生成和决策树的修剪。
二、决策树场景
一个叫做 “二十个问题” 的游戏,游戏的规则很简单:参与游戏的一方在脑海中想某个事物,其他参与者向他提问,只允许提 20 个问题,问题的答案也只能用对或错回答。问问题的人通过推断分解,逐步缩小待猜测事物的范围,最后得到游戏的答案。
一个邮件分类系统,大致工作流程如下:
首先检测发送邮件域名地址。如果地址为 , 则将其放在分类 "无聊时需要阅读的邮件"中。
如果邮件不是来自这个域名,则检测邮件内容里是否包含单词 “曲棍球” , 如果包含则将邮件归类到 “需要及时处理的朋友邮件”, 如果不包含则将邮件归类到 “无需阅读的垃圾邮件” 。
三、决策树概念须知
1.名词定义
熵(entropy):指体系的混乱的程度,在不同的学科中也有引申出的更为具体的定义,是各领域十分重要的参量。
信息熵(information theory):使度量样本集合纯度最常用的一种指标。信息熵度量了事物的不确定性,越不确定的事物,它的熵就越大。
信息增益(information gain):在划分数据集前后信息熵发生的变化称为信息增益。信息增益越大,表明数据“纯度”提升越大。
信息增益率(infor gain ratio):正信息增益的基础上,解决过拟合问题的方法。
基尼系数(Gini index):CART决策树划分属性的指标,数据集的纯度可以用基尼值来度量,基尼值越小,数据集的纯度越高。
纯度(purity):叶子节点中正确分类的标签所占该叶子节点中包含数据的比例。
2.构建“树”时的基本要求
决策树的生成是一个递归过程,即决策树以深度优先遍历进行构建。每个节点可选择的特征为:除该节点的父节点和祖父节点之外的所有特征。若当前节点为空集,对应的处理措施为:将其设置为叶节点,类别设置为其父节点,所含样本最多的类别。四、三种决策树对比
五、 划分选择
我们希望决策树的分支节点所包含的样本尽可能属于同一类别,即节点的“纯度”越来越高。
我们使用周志华一书《机器学习》中的“西瓜数据集”进行计算:
1.ID3信息增益
信息熵:Ent(D)=−∑k=1∣Y∣pklog2pk信息熵:Ent(D) = - \sum_{k = 1}^{|Y|}p_k log_2 p_k 信息熵:Ent(D)=−k=1∑∣Y∣pklog2pk
信息增益:Gain(D,a)=Ent(D)−∑v=1V∣Dv∣∣D∣Ent(Dv)信息增益:Gain(D,a) = Ent(D) - \sum_{v = 1}^{V}\frac{|D^v|}{|D|}Ent(D^v) 信息增益:Gain(D,a)=Ent(D)−v=1∑V∣D∣∣Dv∣Ent(Dv)
|Y|:代表分类标签的数量,“好瓜”、“坏瓜”,所以|Y|=2a:代表数据集所包含的特征,a={色泽,根蒂,敲声,纹理,脐部,触感}v:代表每一个特征下所包含的属性,例如特征“色泽“下v={青绿,乌黑,浅白}正例:”是“好瓜反例:”否“好瓜∣Dv∣∣D∣\frac{|D^v|}{|D|}∣D∣∣Dv∣:代表该节点所包含的数据数量占其父节点数据数量的比例
根节点包含D中所有数据,数据总数:17,正例占p1=8/17,反例占p2=9/17。
根节点的信息熵为:
Ent(D)=−∑k=12pklog2pk=−(817log2817+917log2917)=0.998Ent(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=1∑2pklog2pk=−(178log2178+179log2179)=0.998
然后,我们要计算出当前特征集合{色泽,根蒂,敲声,纹理,脐部,触感}中每个特征的信息熵和信息增益。
★特征”色泽“:
D1D^1D1(色泽=青绿):{1,4,6,10,13,17},正例p1=3/6,反例p2=3/6
Ent(D1)=−(36log236+36log236)=1.000Ent(D^1)=-(\frac{3}{6}log_2 \frac{3}{6} + \frac{3}{6}log_2 \frac{3}{6}) = 1.000Ent(D1)=−(63log263+63log263)=1.000
D2D^2D2(色泽=乌黑):{2,3,7,8,9,15},正例p1=4/6,反例p2=2/6
Ent(D2)=−(46log246+26log226)=0.918Ent(D^2)=-(\frac{4}{6}log_2 \frac{4}{6} + \frac{2}{6}log_2 \frac{2}{6}) = 0.918Ent(D2)=−(64log264+62log262)=0.918
D3D^3D3(色泽=浅白):{5,11,12,14,16},正例p1=1/5,反例p2=4/5
Ent(D3)=−(15log215+45log245)=0.722Ent(D^3)=-(\frac{1}{5}log_2 \frac{1}{5} + \frac{4}{5}log_2 \frac{4}{5}) = 0.722Ent(D3)=−(51log251+54log254)=0.722
"色泽"特征的信息增益:
Gain(D,色泽)=Ent(D)−∑v=1V∣Dv∣∣D∣Ent(Dv)=0.998−(617×1+617×0.918+517×0.722)=0.109Gain(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=1∑V∣D∣∣Dv∣Ent(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
特征”纹理”的信息增益最大,选他作为划分属性。
D1D^1D1中有编号为{1,2,3,4,5,6,8,10,15},可用特征集合为{色泽,根蒂,敲声,脐部,触感},其中正例p1=7/9,反例p2=2/9。其中节点上方红色字体表示:创建该node节点时可选择的特征。
D1D^1D1节点的信息熵为:
Ent(D1)=−∑k=12pklog2pk=−(79log279+29log229)=0.763Ent(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=1∑2pklog2pk=−(97log297+92log292)=0.763
★特征”色泽“:
D11D^{11}D11(色泽=青绿):{1,4,6,10},正例p1=3/4,反例p2=1/4
Ent(D11)=−(34log234+14log214)=0.811Ent(D^{11})=-(\frac{3}{4}log_2 \frac{3}{4} + \frac{1}{4}log_2 \frac{1}{4}) = 0.811Ent(D11)=−(43log243+41log241)=0.811
D12D^{12}D12(色泽=乌黑):{2,3,8,15},正例p1=3/4,反例p2=1/4
Ent(D12)=−(34log234+14log214)=0.811Ent(D^{12})=-(\frac{3}{4}log_2 \frac{3}{4} + \frac{1}{4}log_2 \frac{1}{4}) = 0.811Ent(D12)=−(43log243+41log241)=0.811
D13D^{13}D13(色泽=浅白):{5},正例p1=1,反例p2=0
Ent(D13)=−(1log21+0log20)=0Ent(D^{13})=-(1log_2 1 + 0log_2 0) =0Ent(D13)=−(1log21+0log20)=0
"色泽"特征的信息增益:
Gain(D1,色泽)=Ent(D1)−∑v=1V∣Dv∣∣D∣Ent(Dv)=0.763−(49×0.811+49×0.811+19×0)=0.043Gain(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=1∑V∣D∣∣Dv∣Ent(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
其中“根蒂”,“脐部”,“触感”均获得最大信息增益,可任选其一作为特征划分。此处我们选择“根蒂”特征。
D11D^{11}D11中有编号为{1,2,3,4,5},可用特征集合为{色泽,敲声,脐部,触感},其中正例p1=1,反例p2=0。
D11D^{11}D11节点的信息熵为:
Ent(D11)=−∑k=12pklog2pk=−(1log21+0log20)=0Ent(D^{11})=-\sum_{k=1}^{2}p_k log_2 p_k=-(1log_2 1 +0log_2 0)=0 Ent(D11)=−k=1∑2pklog2pk=−(1log21+0log20)=0
由于Ent(D11)的值已达最小,说明D11中数据纯度已达到最高,数据分类已完全分类,则无需再往下进行划分,将该节点设置为叶子节点。
D12D^{12}D12中编号为{6,8,15},可用特征集合为{色泽,敲声,脐部,触感},其中正例p1=2/3,反例p2=1/3。
D12D^{12}D12节点的信息熵为:
Ent(D12)=−∑k=12pklog2pk=−(23log223+13log213)=0.918Ent(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=1∑2pklog2pk=−(32log232+31log231)=0.918
★特征“色泽”:
D121D^{121}D121(色泽=青绿):{6},正例p1=1,反例p2=0
Ent(D121)=−(1log21+0log20)=0Ent(D^{121})=-(1log_2 1 + 0log_2 0) = 0Ent(D121)=−(1log21+0log20)=0
D122D^{122}D122(色泽=乌黑):{8,15},正例p1=1/2,反例p2=1/2
Ent(D122)=−(12log212+12log212)=1Ent(D^{122})=-(\frac{1}{2}log_2 \frac{1}{2} + \frac{1}{2}log_2 \frac{1}{2}) = 1Ent(D122)=−(21log221+21log221)=1
D123D^{123}D123(色泽=浅白):{ },正例p1=0,反例p2=0
Ent(D123)=−(0log20+0log20)=0Ent(D^{123})=-(0log_2 0 + 0log_2 0) =0Ent(D123)=−(0log20+0log20)=0
"色泽"特征的信息增益:
Gain(D12,色泽)=Ent(D12)−∑v=1V∣Dv∣∣D∣Ent(Dv)=0.918−(13×0+23×1+0×0)=0.251Gain(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=1∑V∣D∣∣Dv∣Ent(Dv)=0.918−(31×0+32×1+0×0)=0.251
类似的,计算出其他特征的信息增益:
Gain(D12,敲声)=0 \quad Gain(D12,脐部)=0\quad Gain(D12,触感)=0.251
其中“色泽”和“触感”均获得最大信息增益,可任选其一作为特征划分。此处我们选择“色泽”特征。
D121D^{121}D121中编号为{6},可用特征集合为{敲声,脐部,触感},其中p1=1,p2=0。
D121D^{121}D121节点的信息熵为:
Ent(D121)=−∑k=12pklog2pk=−(1log21+0log20)=0Ent(D^{121})=-\sum_{k=1}^{2}p_k log_2 p_k=-(1log_2 1 +0 log_2 0)=0 Ent(D121)=−k=1∑2pklog2pk=−(1log21+0log20)=0
将该节点划分为叶子节点。
D122D{122}D122中编号为{8,15},可用特征集合为{敲声,脐部,触感},p1=1/2,p2=1/2。
D122D^{122}D122节点的信息熵为:
Ent(D122)=−∑k=12pklog2pk=−(12log212+12log212)=1Ent(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=1∑2pklog2pk=−(21log221+21log221)=1
★特征“触感”:
D1221D^{1221}D1221(触感=硬滑):{8},正例p1=1,反例p2=0
Ent(D1221)=−(1log21+0log20)=0Ent(D^{1221})=-(1log_2 1 + 0log_2 0) = 0Ent(D1221)=−(1log21+0log20)=0
D1222D^{1222}D1222(触感=软粘):{15},正例p1=0,反例p2=1
Ent(D1221)=−(0log20+1log21)=0Ent(D^{1221})=-(0log_2 0 + 1log_2 1) = 0Ent(D1221)=−(0log20+1log21)=0
"触感"特征的信息增益:
Gain(D122,色泽)=Ent(D122)−∑v=1V∣Dv∣∣D∣Ent(Dv)=1−(12×0+12×0)=1Gain(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=1∑V∣D∣∣Dv∣Ent(Dv)=1−(21×0+21×0)=1
类似的,计算出其他特征的信息增益:
Gain(D122,敲声)=0 \quad Gain(D122,脐部)=0
所以选择“触感”特征作为划分节点。
D1221D^{1221}D1221中编号为{8},可用特征集合为{敲声,脐部},p1=1,p2=0。
D1221D^{1221}D1221节点的信息熵为:
Ent(D1221)=−∑k=12pklog2pk=−(1log21+0log20)=0Ent(D^{1221})=-\sum_{k=1}^{2}p_k log_2 p_k=-(1log_2 1 +0 log_2 0)=0 Ent(D1221)=−k=1∑2pklog2pk=−(1log21+0log20)=0
所以将该节点设置为叶子节点。
D1222D^{1222}D1222中编号为{15},可用特征集合为{敲声,脐部},p1=0,p2=1。
D1222D^{1222}D1222节点的信息熵为:
Ent(D1222)=−∑k=12pklog2pk=−(0log20+1log21)=0Ent(D^{1222})=-\sum_{k=1}^{2}p_k log_2 p_k=-(0log_2 0 +1 log_2 1)=0 Ent(D1222)=−k=1∑2pklog2pk=−(0log20+1log21)=0
D123D^{123}D123中为空集{ },将其设置为叶节点,且类别设置为其父节点所含样本最多的类别即{6,8,15}此时需要往回遍历,找到第三层“色泽”特征下的D123属性集合。
中,p1=2/3,p2=1/3,所以该叶子节点类别为“好瓜”。
D13D^{13}D13中编号为{10},可用特征集合为{色泽,敲声,脐部,触感},p1=0,p2=1。继续往回遍历,找到第二层“根蒂”特征下的D13属性集合。
D13D^{13}D13节点的信息熵为:
Ent(D13)=−∑k=12pklog2pk=−(0log20+1log21)=0Ent(D^{13})=-\sum_{k=1}^{2}p_k log_2 p_k=-(0log_2 0 +1 log_2 1)=0 Ent(D13)=−k=1∑2pklog2pk=−(0log20+1log21)=0
所以将该节点设置为叶子节点。
继续往回遍历,找到第一层“纹理”特征下的D2属性集合。
D2D^{2}D2中编号为{7,9,13,14,17},可用特征集合为{色泽,根蒂,敲声,脐部,触感},p1=1/5,p2=4/5。
D2D^{2}D2节点的信息熵为:
Ent(D2)=−∑k=12pklog2pk=−(15log215+45log245)=0.722Ent(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=1∑2pklog2pk=−(51log251+54log254)=0.722
★特征“色泽”:
D21D^{21}D21(色泽=青绿):{13,17},正例p1=0,反例p2=1
Ent(D21)=−(0log21+1log20)=0Ent(D^{21})=-(0log_2 1 + 1log_2 0) = 0Ent(D21)=−(0log21+1log20)=0
D22D^{22}D22(色泽=乌黑):{7,9},正例p1=1/2,反例p2=1/2
Ent(D22)=−(12log212+12log212)=1Ent(D^{22})=-(\frac{1}{2}log_2 \frac{1}{2} + \frac{1}{2}log_2 \frac{1}{2}) = 1Ent(D22)=−(21log221+21log221)=1
D23D^{23}D23(色泽=浅白):{14},正例p1=0,反例p2=1
Ent(D23)=−(0log20+1log21)=0Ent(D^{23})=-(0log_2 0 + 1log_2 1) =0Ent(D23)=−(0log20+1log21)=0
"色泽"特征的信息增益:
Gain(D2,色泽)=Ent(D2)−∑v=1V∣Dv∣∣D∣Ent(Dv)=0.722−(25×0+25×1+15×0)=0.322Gain(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=1∑V∣D∣∣Dv∣Ent(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. D21D^{21}D21中编号为{9,13,14,17},可用特征集合为{色泽,根蒂,敲声,脐部},其中正例p1=0,反例p2=1.
D21D{21}D21节点的信息熵为:
Ent(D21)=−∑k=12pklog2pk=−(0log20+1log21)=0Ent(D^{21})=-\sum_{k=1}^{2}p_k log_2 p_k=-(0log_2 0 +1 log_2 1)=0 Ent(D21)=−k=1∑2pklog2pk=−(0log20+1log21)=0
所以将该节点划分为叶子节点。
D22D^{22}D22中编号为{7},可用特征集合为{色泽,根蒂,敲声,脐部},其中正例p1=1,反例p2=0.
D22D{22}D22节点的信息熵为:
Ent(D22)=−∑k=12pklog2pk=−(1log21+0log20)=0Ent(D^{22})=-\sum_{k=1}^{2}p_k log_2 p_k=-(1log_2 1 +0 log_2 0)=0 Ent(D22)=−k=1∑2pklog2pk=−(1log21+0log20)=0
所以将该节点划分为叶子节点。
D3D^3D3中有编号为{11,12,16},可用特征集合为{色泽,根蒂,敲声,脐部,触感},其中正例p1=0,反例p2=1。往回遍历,找到第一层“纹理”特征下的D3属性集合。
D3D{3}D3节点的信息熵为:
Ent(D3)=−∑k=12pklog2pk=−(0log20+1log21)=0Ent(D^{3})=-\sum_{k=1}^{2}p_k log_2 p_k=-(0log_2 0 +1 log_2 1)=0 Ent(D3)=−k=1∑2pklog2pk=−(0log20+1log21)=0
所以将其设置为叶子节点。
至此,使用信息增益构建的ID3决策树已经建立好了,如上图所示。
2.C4.5信息增益率
信息增益缺点:是对可取属性多的特征有偏好,比如如果把“编号”这一列当作特征也考虑在内,那么可以计算处它的信息增益大于其他的候选特征,因为“编号”有17个可取的数值,产生17个分支,每个分支节点仅包含一个样本,显然这些分支节点的纯度最大。但是,这样的决策树显然不具有泛化能力,无法对新样本进行有效预测。C4.5决策树算法:使用“信息增益率”来选择最优划分属性,可以很好的克服上述缺点。
信息增益率定义为:
Gainratio(D,a)=Gain(D,a)IV(a)Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)} Gainratio(D,a)=IV(a)Gain(D,a)
其中:
IV(a)=−∑v=1V∣Dv∣∣D∣log2∣Dv∣∣D∣IV(a)IV(a)=-\sum_{v=1}^{V} \frac{|D^v|}{|D|}log_2 \frac{|D^v|}{|D|}IV(a) IV(a)=−v=1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣IV(a)
IV(a)称为特征a的“固有值”,特征a的可能取值数目越多(即V越大),则 IV(a)的值通常会越大。但增益率也可能产生一个问题就是对属性较少的特征有所偏好。注意:C4.5算法并不是直接选择增益率最大的候选划分特征,而是先从候选划分特征中找出信息增益高于平均水平的特征,再从中选择增益率最高的。
由于信息增益的计算方法在ID3中已经详细介绍并给出计算例子,在这里不再赘述,重点计算信息增益率的求解。
计算数据集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
ave_Gain(D)=0.109+0.143+0.141+0.381+0.289+0.0066=0.178ave\_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
IV(纹理)=−(917log2917+517log2517+317log2317)=1.446IV(纹理)=-(\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
信息增益率为:
Gain_ratio(D,纹理)=0.3811.446=0.263Gain\_ratio(D,纹理)=\frac{0.381}{1.446}=0.263 Gain_ratio(D,纹理)=1.4460.381=0.263
★特征“脐部”:凹陷:7;稍凹:6;平坦:4
IV(脐部)=−(717log2717+617log2617+417log2417)=1.548IV(脐部)=-(\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
信息增益率为:
Gain_ratio(D,脐部)=0.2891.548=0.187Gain\_ratio(D,脐部)=\frac{0.289}{1.548}=0.187 Gain_ratio(D,脐部)=1.5480.289=0.187
“纹理”的信息增益率大于“脐部”的信息增益率,所以选择特征“纹理”当作节点,划分数据集。
计算数据集D1中可用特征的信息增益和信息增益率:
Gain(D1,色泽 ) = 0.043 \quad Gain(D1,根蒂) = 0.458 \quad Gain(D1,敲声) = 0.331
Gain(D1,脐部) = 0.458 \quad Gain(D1,触感) = 0.458
ave_Gain(D1)=0.043+0.458+0.331+0.458+0.4585=0.3496ave\_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
IV(根蒂)=−(59log259+39log239+19log219)=1.351IV(根蒂)=-(\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
信息增益率为:
Gain_ratio(D1,根蒂)=0.4581.351=0.339Gain\_ratio(D1,根蒂)=\frac{0.458}{1.351}=0.339 Gain_ratio(D1,根蒂)=1.3510.458=0.339
★特征“脐部”:凹陷:5;稍凹:3;平坦:1
IV(脐部)=−(59log259+39log239+19log219)=1.351IV(脐部)=-(\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
信息增益率为:
Gain_ratio(D1,脐部)=0.4581.351=0.339Gain\_ratio(D1,脐部)=\frac{0.458}{1.351}=0.339 Gain_ratio(D1,脐部)=1.3510.458=0.339
★特征“触感”:硬滑:6;软粘:3
IV(触感)=−(69log269+39log239)=0.918IV(触感)=-(\frac{6}{9}log_2 \frac{6}{9} + \frac{3}{9}log_2 \frac{3}{9} )=0.918 IV(触感)=−(96log296+93log293)=0.918
信息增益率为:
Gain_ratio(D1,触感)=0.4580.918=0.499Gain\_ratio(D1,触感)=\frac{0.458}{0.918}=0.499 Gain_ratio(D1,触感)=0.9180.458=0.499
“触感”的信息增益率最大,所以选择特征“触感”当作节点,划分数据集。
计算数据集D11中的信息:
由于数据集D11的信息熵为0,所以此节点以完全分类,将其设置为叶子节点。
计算数据集D12中的信息:
Gain(D12,色泽)=0.251 \quad Gain(D12,根蒂)=0.251
Gain(D12,敲声)=0.251 \quad Gain(D12,脐部)=0.251
★特征“脐部”:凹陷:0;稍凹:2;平坦:1
IV(脐部)=−(0log20+23log223+13log213)=0.251IV(脐部)=-(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,所以他们的信息增益率均相同,这种情况我们可以任选其一划分数据,类别为其中包含最多的类别;也可以将其设置为叶子节点,牺牲正确率换取更低的决策树层数。在这里我采取的方法为后者。
计算数据集D2中的信息
类似于数据集D12的情况,由于D2中只包含一个正例,所以依然可以采取牺牲正确率换取更低的决策树层数,或是进行计算选出一个特征来划分。此处采取设置为叶节点,有兴趣的同学可以自行计算。
计算数据集D3中的信息
由于数据集D11的信息熵为0,所以此节点以完全分类,将其设置为叶子节点。
3.CART基尼系数
CART决策树:使用”基尼指数“来选择划分特征。数据集的纯度可用基尼值(Gini)来度量。Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率,Gini值越小,则数据集的纯度越高。
Gini(D)=1−∑k=1∣Y∣pk2Gini(D)=1-\sum_{k=1}^{|Y|}p_{k}^{2} Gini(D)=1−k=1∑∣Y∣pk2
特征的“基尼指数”(Gini index)定义如下,选择使得划分后基尼指数最小的特征作为最优划分特征。
Gini_index(D,a)=∑v=1V∣Dv∣∣D∣Gini(Dv)Gini\_index(D,a)=\sum_{v=1}^{V} \frac{|D^v|}{|D|}Gini(D^v) Gini_index(D,a)=v=1∑V∣D∣∣Dv∣Gini(Dv)
计算每个特征的基尼指数前,先计算下该节点的基尼值,若基尼值为0,则表示该节点下的数据集已完全分类。
根节点包含D中所有数据,数据总数为17,可用特征{色泽,根蒂,敲声,纹理,脐部,触感}:
★特征“色泽”:
青绿:{1,4,6,10,13,17},数据总计:6,正例p1= 3/6,反例p2= 3/6
Gini(青绿)=1−∑k=1∣Y∣pk2=1−(36×36+36×36)=0.5Gini(青绿)=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(青绿)=1−k=1∑∣Y∣pk2=1−(63×63+63×63)=0.5
乌黑:{2,3,7,8,9,15},数据总计:6,正例p1= 4/6,反例p2= 2/6
Gini(乌黑)=1−∑k=1∣Y∣pk2=1−(46×46+26×26)=0.444Gini(乌黑)=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(乌黑)=1−k=1∑∣Y∣pk2=1−(64×64+62×62)=0.444
浅白:{5,11,12,14,16},数据总计:5,正例p1= 1/5,反例p2= 4/5
Gini(浅白)=1−∑k=1∣Y∣pk2=1−(15×15+45×45)=0.32Gini(浅白)=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(浅白)=1−k=1∑∣Y∣pk2=1−(51×51+54×54)=0.32
“色泽”特征的基尼指数为:
Gini_index(D,色泽)=617×0.5+617×0.444+517×0.32=0.427Gini\_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
选择基尼指数最小的特征进行划分,所以此次划分使用“纹理”特征。
D1中包含数据总数为9,可用特征{色泽,根蒂,敲声,脐部,触感}:
★特征“色泽”
青绿:{1,4,6,10},数据总计:4,正例p1= 3/4,反例p2= 1/4
Gini(青绿)=1−∑k=1∣Y∣pk2=1−(34×34+14×14)=0.375Gini(青绿)=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(青绿)=1−k=1∑∣Y∣pk2=1−(43×43+41×41)=0.375
乌黑:{2,3,8,15},数据总计:4,正例p1= 3/4,反例p2= 1/4
Gini(乌黑)=1−∑k=1∣Y∣pk2=1−(34×34+14×14)=0.375Gini(乌黑)=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(乌黑)=1−k=1∑∣Y∣pk2=1−(43×43+41×41)=0.375
浅白:{5},数据总计:1,正例p1= 1,反例p2= 0
Gini(浅白)=1−∑k=1∣Y∣pk2=1−(1×1+0×0)=0Gini(浅白)=1-\sum_{k=1}^{|Y|}p_k^2=1-(1\times 1 + 0\times 0)=0 Gini(浅白)=1−k=1∑∣Y∣pk2=1−(1×1+0×0)=0
“色泽”特征的基尼指数为:
Gini_index(D1,色泽)=49×0.375+49×0.375+19×0=0.333Gini\_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
由于“根蒂”、“脐部”和“触感”的基尼指数相同,任选其一作为特征进行划分数据集,这里我们选择“根蒂”特征:
D11中包含数据总数为5,其中正例p1=1,反例p2=0。
该节点基尼值为:
Gini(D11)=1−∑k=1∣Y∣pk2=1−(1×1+0×0)=0Gini(D^11)=1-\sum_{k=1}^{|Y|}p_k^2=1-(1\times 1 +0 \times 0) = 0 Gini(D11)=1−k=1∑∣Y∣pk2=1−(1×1+0×0)=0
该节点基尼值已达最小,将其设置为叶子节点。
D12中包含数据总数位3,可用特征为{色泽,敲声,脐部,触感}
★特征“色泽”:
青绿:{6},数据总计:1,正例p1= 1,反例p2= 1/40
Gini(青绿)=1−∑k=1∣Y∣pk2=1−(1×1+0×0)=0Gini(青绿)=1-\sum_{k=1}^{|Y|}p_k^2=1-(1\times 1 + 0\times 0)=0 Gini(青绿)=1−k=1∑∣Y∣pk2=1−(1×1+0×0)=0
乌黑:{8,15},数据总计:2,正例p1= 1/2,反例p2= 1/2
Gini(乌黑)=1−∑k=1∣Y∣pk2=1−(12×12+12×12)=0.5Gini(乌黑)=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(乌黑)=1−k=1∑∣Y∣pk2=1−(21×21+21×21)=0.5
浅白:{ },数据总计:0,正例p1= 0,反例p2= 0
Gini(浅白)=1−∑k=1∣Y∣pk2=1−(0×0+0×0)=0Gini(浅白)=1-\sum_{k=1}^{|Y|}p_k^2=1-(0\times 0 + 0\times 0)=0 Gini(浅白)=1−k=1∑∣Y∣pk2=1−(0×0+0×0)=0
“色泽”特征的基尼指数为:
Gini_index(D12,色泽)=13×0+23×0.5+0×0=0.333Gini\_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
由于“色泽”和“触感”的基尼指数相同,任选其一作为特征进行划分数据集,这里我们选择“色泽”特征:
D121中已完全分类,设置为叶节点。
D122中包含数据总数为2,可用特征为{敲声,脐部,触感}
Gini_index(D122,敲声) = 0.5 \quad Gini_index(D122,脐部) = 0.5 \quad Gini_index(D122,触感) = 0
所以选择“触感”特征划分数据集。
D1221中已完全分类,设置为叶节点。
D1222中已完全分类,设置为叶节点。
该节点集合为空,设置为其父节点数据中类别最多的类。往回遍历,找到第三层“色泽”特征下的D123属性集合。
往回遍历,找到第二层“根蒂”特征下的D13属性集合
D13中已完全分类,设置为叶节点。
往回遍历,找到第一层“纹理”特征下的D2属性集合
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
所以选择“触感”作为特征划分数据集。
D21中已完全分类,设置为叶节点。
D22中已完全分类,设置为叶节点。
D3中已完全分类,设置为叶节点。
建立好的决策树如下图所示:
至此,三种决策树构建时的计算过程已经整理完了,在下一篇文章中我们来看看预剪枝与缺失值处理是怎么操作的。
【参考文献】
apache github主页:/apachecn/AiLearning天泽28 CSDN博客:/u012328159/article/details/70184415刘建平 博客园:/pinard/周志华 《机器学习》