决策树的不同划分方法

ID3决策树算法

        学习算法的重点在于如何选择最优划分属性。显然我们希望分支节点尽可能的属于同一个类--即希望节点的纯度越高越好。关键在于我们如何定义节点的纯度。

        一般我们采用的是信息熵的指标。其定义如下

信息熵

        信息熵的值越小,则节点的纯度越高。(熵用于表示事物的混乱程度)

        为了选择最佳划分属性,则我们需要对每个属性都进行信息熵的计算。对每个属性(即特征)而言,利用每个属性的多个分类(比如高矮这一属性就可以分为:<160,160-180,>180等等),分别计算划分后的样本空间的信息熵,并利用样本空间的样本数量为权重相加。为了表达纯度的提升,我们用最初的信息熵减去分类之后的信息熵,就可以得到熵减,也就是纯度的提升(称为信息增益),具体计算公式如下(绝对值符号代表该空间的样本数量):

信息增益

        我们可以通过计算每个属性的信息增益,选择信息增益最大的那项属性来进行划分,这就是ID3决策树学习算法。

C4.5决策树算法

        在ID3决策树学习算法中,我们采用信息增益准则来决定最佳划分属性,然而信息增益准则会偏好可取值数目较多的属性,为了减少这种偏好所带来的不利影响,著名的C4.5决策树算法不直接使用信息增益,而是利用增益率来选择最佳划分属性。增益率的定义如下:


增益率

        分子仍采用之前的信息增益,而分母被称为属性a的固有值。属性a的可能取值越多,其固有值也会越大。增益率准则通过添加分母的方式抑制了对可取值较多属性的抑制,但不幸的是,这种抑制是过量的,增益率准则会偏好可取值较少的属性。

CART决策树算法

        cart决策树采用“基尼指数”来划分属性。基尼系数的定义如下

基尼系数

        基尼系数可以直观理解为从数据集D中随机选取两个样本,其属性不一致的概率。因此基尼系数越小,数据集的纯度越高。同样,属性a的基尼指数定义为分类后的样本空间乘以权重的和。

基尼指数
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 决策树理论在决策树理论中,有这样一句话,“用较少的东西,照样可以做很好的事情。越是小的决策树,越优于大的决策树”。...
    制杖灶灶阅读 5,961评论 0 25
  •   决策树(Decision Tree)是一种基本的分类与回归方法,其模型呈树状结构,在分类问题中,表示基于特征对...
    殉道者之花火阅读 4,621评论 2 2
  • 一、决策树应用体验 分类   从上面可以看出,决策树对分类具有线性回归无可比拟的优势, 如果对未参与训练的数据集是...
    杨强AT南京阅读 1,276评论 1 3
  • 依据不同的决策树算法,在划分子节点时进行特征选择的依据有信息增益、信息增益比(又称信息增益率)、基尼系数三种。依次...
    迪丽娜扎阅读 6,198评论 2 4
  • 1 前言 在了解树模型之前,自然想到树模型和线性模型,他们有什么区别呢? 树形模型是一个一个特征进行处理,之前线性...
    高永峰_GYF阅读 1,440评论 0 1