C4.5详解(附带信息论介绍)
C4.5详解
第六次写博客,本人数学基础不是太好,如果有幸能得到读者指正,感激不尽,希望能借此机会向大家学习。这一篇内容来自于各种书籍、网上的资料,以及自己的一些见解。关于决策树的一些基本概念在这篇博客《Decision Tree简介(决策树算法族的开篇)》中有相关介绍。
预备知识:
这一部分主要是谈一谈几种基于信息论的结点划分方法,包括信息熵(InformaticaEntropy)、信息增益(InformaticaGain)与增益率(GainRatio)的简要介绍。
信息熵(InformaticaEntropy)
“信息熵”是度量样本集合纯度最常用的一种指标,假设当前样本集中第类样本所占比例为,其中为样本集的总类别数量,则的信息熵定义为
信息熵越小,则的纯度越高,需要注意的是由于,因此。
信息增益(InformaticaGain)
假定某一离散属性有个可能的取值,分别为,若使用来对样本集进行划分,则会产生个分支结点。其中第个分支结点包含了中所有在属性上取值为的样本,这些样本的集合记为。可以根据式(1)对的信息熵进行计算,再考虑到不同的分支结点所包含的样本数不同,因此给每个分支结点的信息熵赋予权重,即样本数越多的分支结点的影响越大,于是可以计算出使用属性作为划分属性,对样本集进行划分后所得的“信息增益”(InformaticaGain)
信息增益越大,即划分后的子集合的加权信息熵越小,则使用属性来进行划分所得到的“纯度提升”越大。
增益率(GainRatio)
实际上,将信息增益作为准则存在重要的问题,即他对可能的取值数量较大的属性(e.g. 样本编号)有所偏好,为了解决这一问题,某些算法不直接采用信息增益做为准则,而是使用“增益率”(GainRatio)来选择最优划分属性,他的定义为
上式中,
称为属性的固有值(Intrinsic Value)。与信息熵的定义类似,属性的可能的取值数量越大,其固有值越大。
推导过程
主要分为三部分:如何处理连续值、如何处理缺失值以及划分属性的选择标准。
处理连续值
当某一属性的可取值数目不可数(连续值)或数目很多(离散值)时,可以采用离散化对这种情况进行处理。对于连续属性,最简单的离散化方法就是“二分法”(bi-partition),对于离散属性还可以采用“n分法”(n-partition),即将可取值分成n类。
1. 连续属性的“二分法”
给定数据集和连续属性,假定在上出现了个不同的取值,将这些值从小到大进行排列,排列后的可取值集合记为,之后基于划分点可将数据集分为两个子集和,他们分别包含那些在属性 上取值大于的样本和不大于的样本。对于连续属性,可以选取可取值集合中相临近两点的均值作为候选划分点,使用这种方法产生的候选划分点集的大小为,候选集合为
之后对候选划分点集中的每个候选点进行考察,选择使数据集纯度提升最高的那个作为划分点,具体方式如下所示
易知,是数据集基于划分点二分后的信息增益。
需要注意的是,与离散属性不同的是,如果当前结点的划分属性为连续属性,该属性还可以作为其后代结点的划分属性。
缺失值的处理
现实任务中经常会遇到稀疏数据集,即数据集中的某些样本的某些属性值缺失,当遇到这种情况时,在决策树的训练过程中要考虑以下两个问题:
(1) 如何在属性值缺失的情况下,选择最优划分属性?
(2) 给定划分属性,若样本在该属性上的值缺失,如何对该样本进行划分?
同样,给定数据集和属性令表示数据集在属性上没有缺失值的样本集合,那么对于第一个问题,显然我们只能根据来决定属性的好坏。假设属性的可取值集合记为,令表示中在属性上取值为的样本子集,表示中属于第 类的样本子集,显然有和。假设为每个样本赋予一个权重 ,并定义
由上式定义可知,对于属性,表示无缺失值样本在整个数据集中所占的比例,表示无缺失值数据集中属于第类样本所占的比例,表示无缺失值数据集中在属性上取值为的样本所占的比例,显然有和。
基于上述定义,我们可将信息增益的定义调整为
令表示在数据集中,并且在属性上取值为的样本子集中,属于第类的样本集合,则这个样本集合在数据集中所占的比例可以表示为
那么式(1)中的和可以分别表示为
对于第二个问题,若样本在划分属性上的取值已知,则将 中去,并保持原始权值 。若样本在划分属性上的取值未知,则将同时划分到所有的子结点中去,并且在每个子结点中该样本的权值变更为,直观的看,就是让同一个结点以不同的概率划分到不同的子结点中去。C4.5在处理缺失值(离散的)就采用了上述的方法。
划分属性的选择标准
C4.5中所使用的选择标准是增益率,需要注意的是,增益率对可取值数目 较少的属性有所偏好,因此在C4.5算法中并不是直接将具有最大增益率的属性作为划分属性,而是使用了一个“启发式”的方法,即先从候选划分属性中找出信息增益高于平均水平的属性,再从这些属性中选择增益率最高的作为最优划分属性。