earth_houge 阅读(62) 评论(0)

   在生成决策树的过程中,如果是离散属性,而且每个样例属性值都存在,那么我们很容易进行划分,但是在现实生活中,我们常常会遇到连续属性,而且有可能某些样例的属性值不存在,此时我们就不得不针对属性数据进行一些处理,常见的有连续值处理和缺失值处理。

连续值处理

  由于连续属性的可取值数目不再有限,因此,不能直接根据连续属性的可取值来对节点进行划分,此时,连续属性离散化技术可派上用场,最简单的策略是采用二分法对连续属性进行处理,这正是C4.5决策树算法中采用的机制。

  给定样本集D和连续属性a,假定a在D上出现了n个不同的取值,将这些值从小到大进行排序,记为{a1,a2,......,an},基于划分点t可将D分为子集Dt-和Dt+,其中Dt-包含那些在属性a上取值不大于t的样本,显然,对相邻的属性取值ai和ai+1来说,t在区间[ai,ai+1)中取任意值所产生的划分结果相同,因此,对连续属性a,我们可考察包含n-1个元素的候选划分集合

即把区间[ai,ai+1)的中位点(ai+ai+1)/2作为候选划分点,然后我们就可像离散属性值一样来考察这些划分点,选取最优的划分点进行样本集合的划分,例如,我们可对信息增益的公式稍加改造:

      

其中Gain(D,a,t)是样本集D基于划分点t二分后的信息增益,于是,我们就可选择使Gain(D,a,t)最大化的划分点。

  我们用下表一所示的数据集生成一棵决策树

表一:

  对属性“密度”,在决策树学习开始时,根节点包含的17个训练样本在该属性上取值均不同,根据公式,该属性的候选划分点集合包含16个候选值:T密度={0.244,0.294,0.351,0.381,0.420,0.459,0.518,0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746},则由计算可得属性“密度”的信息增益为0.262,对应划分点0.381。

  对属性“含糖率”,其候选划分点集合也包含16个候选值:T含糖率={0.049,0.074,0.095,0.101,0.126,0.155,0.179,0.204,0.213,0.226,0.250,0.265,0.292,0.344,0.373,0.418},类似的,可计算出其信息增益为0.349,对应于划分点0.126。

  再计算出其他离散属性的信息增益,然后根据信息增益准则递归进行节点划分过程,最终生成如下图所示的决策树。

  需要注意的是,与离散属性不同,若当前节点划分属性为连续属性,该属性还可作为其后代节点的划分属性。

缺失值处理

  现在任务中往往会遇到某些属性值缺失,尤其是在属性数目较多的情况下,往往会有大量样本出现缺失值,如果简单的放弃不完整样本,仅仅使用无缺失值的样本进行学习,显然是对信息的极大浪费,如下表二所示,数据集中只有编号为{4,7,14,16}的4个样本能被使用,显然,有必要考虑利用有缺失值的训练样例来进行学习。

表二:

  我们需要解决两个问题:(1),如何在属性值缺失的情况下进行划分属性选择?(2),给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分?

  给定训练集D和属性a,令表示D中在属性a上没有缺失值的样本子集,对问题(1),我们仅可根据来判断属性a的优劣,假定属性a有V个可取值{a1,a2,......,av},令v表示中在属性a上取值为av的样本子集,k表示中属于第k类(k=1,2......)的样本子集,则显然有 。假定我们为每个样本x赋予一个权重wx,并定义

直观来看,对属性a,ρ表示无缺失值样本所占的比例,表示无缺失值样本中第k类所占的比例,则表示无缺失值样本中在属性a上取值av的样本所占的比例,显然,

  基于上述定义,我们可将信息增益的计算公式推广为:

Gain(D,a)=ρ*Gain(,a)=ρ*(Ent()-∑Vv=1Ent(v))

其中

  对问题(2),若样本x在划分属性a上的取值已知,则将x划入与其值对应的子节点,且样本权值在子节点中保持为wx,若样本x在划分属性a上的取值未知,则将x同时划入所有子节点,且样本权值在与属性av对应的子节点中调整为,直观地看,这就是让同一个样本以不同的概率划入到不同的子节点中去。

  下面我们以上表中的数据生成一课决策树,在学习开始时,根节点包含样本集D中全部17个样例,各样例的权值均为1,以属性“色泽“为例,该属性上无缺失值的样例子集包含编号为{2,3,4,6,7,8,9,10,11,12,14,15,16,17}的14个样例,显然,的信息熵为

Ent()=-∑2k=1*log2=-(6/14*log2(6/14)+8/14*log2(8/14))=0.985

  令123分别表示在属性“色泽”上取值为“青绿“,“乌黑”以及“浅白”的样本子集,有:

Ent(1)=-(2/4*log2(2/4)+2/4*log2(2/4))=1.000

Ent(2)=-(4/6*log2(4/6)+2/6*log2(2/6))=0.918

Ent(3)=-(0/4*log2(0/4)+4/4*log2(4/4))=0.000

因此,样本子集上属性“色泽”的信息增益为:

 Gain(,色泽)=Ent()-∑3v=1Ent(v)=0.985-(4/14*1.000+6/14*0.918+4/14*0.000)=0.306

  于是,样本集D上属性“色泽”的信息增益为:

 Gain(D,色泽)=*Gain(,色泽)=14/17*0.306=0.252

  类似可计算出所有属性在D上的信息增益,“纹理”在所有属性中取得了最大的信息增益,被用于对根节点进行划分,划分结果是使编号为{1,2,3,4,5,6,15}的样本进入“纹理=清晰”分支,编号为{7,9,1,3,14,17}的样本进入“纹理=稍糊”分支,而编号为{11,12,16}的样本进入“纹理=模糊”分支,且样本在各子节点中的权重保持为1,需注意的是,编号为{8}的样本在属性“纹理”上出现了确实值,因此它将同时进入三个分支中,但权重在三个子节点中分别调整为7/15,5/15,3/15,编号为{10}的样本有类似划分结果,划分过程递归进行,最终生成如图所示决策树。