机器学习 3.2 决策树模型 学习笔记(待补)

3.2.1 模型结构

决策树模型将思维过程抽象为一系列对已知数据属性的判别和决策过程,使用树结构表示和判别的逻辑和关系和一系列的判别过程,并通过叶节点表示判别或决策结果。

请添加图片描述

如上图所示,一颗树上的叶节点全部表示最终结果,而非叶节点表示每个决策的点,也就是对样本某一属性的判别。不难发现决策树是一个外向树模型,每个内部节点都将直接或间接的影响决策的最终结果。从根节点到某一叶节点的的路径称为测试序列。

我们可以将决策树模型的构造过程描述为如下的过程:

  1. 根据某种分类规则得到最优的划分特征,计算最优特征子函数,并创建特征的划分节点,按照划分节点将数据集划分为若干部分子数据集;
  2. 在子数据集重复使用判别规则,构造出新的节点,作为树的新分支;
  3. 在生成子数据集时,注意检查数据是否均属于同一类别或者再也没有用于数据划分的属性;如果仍能继续分类,则递归执行上述过程;否则将当前节点作为叶节点,结束该分支的构造过程。

3.2.2 判别标准

构造决策树的关键在于合理选择其颞部节点所对应的样本属性,使得节点所对应样本子集中的样本尽可能多属于同一类别,即具有尽可能高的纯度。

决策树模型的判别标准需要满足以下两点:

  1. 如果节点对应数据子集中的样本基本属于同一个类别,则不用再对节点的数据子集做进一步划分,否则就要对该节点的数据子集做进一步划分,生成新的判别标准;
  2. 如果新的判别标准能够基本上把节点上不同类别的数据分离开,使得每个子节点都是类别比较单一的数据,那么该判别标准就是一个好规则,否则需要重新选取判别标准。

如何量化决策树的判别属性选择标准?

我们一般使用信息熵(熵)对样本集合的纯度进行定量分析。信息熵时信息论中定量描述随机变量不确定度的的一类度量指标,主要用于衡量数据取值的无序程度,熵值越大则表明数据取值越杂乱无序。

假设机器学习 3.2 决策树模型 学习笔记(待补)为具有机器学习 3.2 决策树模型 学习笔记(待补)个可能取值机器学习 3.2 决策树模型 学习笔记(待补)的离散型随机变量,概率分布为机器学习 3.2 决策树模型 学习笔记(待补),则其信息熵定义为:
机器学习 3.2 决策树模型 学习笔记(待补)
机器学习 3.2 决策树模型 学习笔记(待补)的值越大时,表明随机变量机器学习 3.2 决策树模型 学习笔记(待补)的不确定性就越大。

对于任意给定的两个离散型随机变量机器学习 3.2 决策树模型 学习笔记(待补),其联合概率分布为:
机器学习 3.2 决策树模型 学习笔记(待补)
机器学习 3.2 决策树模型 学习笔记(待补)关于机器学习 3.2 决策树模型 学习笔记(待补)的信息熵机器学习 3.2 决策树模型 学习笔记(待补)定量表示在已知随机变量机器学习 3.2 决策树模型 学习笔记(待补)取值的条件下随机变量机器学习 3.2 决策树模型 学习笔记(待补)取值的不确定性,计算公式为随机便变量机器学习 3.2 决策树模型 学习笔记(待补)基于条件概率分布的熵对随机变量机器学习 3.2 决策树模型 学习笔记(待补)的数学期望,即有:
机器学习 3.2 决策树模型 学习笔记(待补)
其中,机器学习 3.2 决策树模型 学习笔记(待补)

对于任意给定的训练样本集合机器学习 3.2 决策树模型 学习笔记(待补),可将集合机器学习 3.2 决策树模型 学习笔记(待补)看作时一个关于样本标签取值状态的随机变量,由此可根据熵的本质内涵来定义一个量化指标机器学习 3.2 决策树模型 学习笔记(待补)进而度量机器学习 3.2 决策树模型 学习笔记(待补)中样本类型的纯度,通常称机器学习 3.2 决策树模型 学习笔记(待补)为经验熵。机器学习 3.2 决策树模型 学习笔记(待补)的值越大,则表明机器学习 3.2 决策树模型 学习笔记(待补)中所包含的样本标签取值越杂乱;反之越小则表明越样本标签取值越纯净。机器学习 3.2 决策树模型 学习笔记(待补)的具体计算公式如下:
机器学习 3.2 决策树模型 学习笔记(待补)
其中,机器学习 3.2 决策树模型 学习笔记(待补)表示样本标签值的取值状态数;机器学习 3.2 决策树模型 学习笔记(待补)表示训练样本集机器学习 3.2 决策树模型 学习笔记(待补)中所有标注值为第机器学习 3.2 决策树模型 学习笔记(待补)个取值的训练样本组成的集合,机器学习 3.2 决策树模型 学习笔记(待补)机器学习 3.2 决策树模型 学习笔记(待补)分别表示集合机器学习 3.2 决策树模型 学习笔记(待补)机器学习 3.2 决策树模型 学习笔记(待补)的基数。

对于训练样本集机器学习 3.2 决策树模型 学习笔记(待补)上的任意属性机器学习 3.2 决策树模型 学习笔记(待补),可在经验熵机器学习 3.2 决策树模型 学习笔记(待补)的基础上进一步定义一个量化指标机器学习 3.2 决策树模型 学习笔记(待补)来度量集合机器学习 3.2 决策树模型 学习笔记(待补)中样本在以属性机器学习 3.2 决策树模型 学习笔记(待补)为标准划分后的纯度,通常乘机器学习 3.2 决策树模型 学习笔记(待补)为集合机器学习 3.2 决策树模型 学习笔记(待补)关于属性机器学习 3.2 决策树模型 学习笔记(待补)的经验条件熵。机器学习 3.2 决策树模型 学习笔记(待补)的计算公式如下:
机器学习 3.2 决策树模型 学习笔记(待补)
其中,机器学习 3.2 决策树模型 学习笔记(待补)表示属性机器学习 3.2 决策树模型 学习笔记(待补)的取值状态数;机器学习 3.2 决策树模型 学习笔记(待补)表示集合机器学习 3.2 决策树模型 学习笔记(待补)在以属性机器学习 3.2 决策树模型 学习笔记(待补)为标准划分后产生的子集,即为机器学习 3.2 决策树模型 学习笔记(待补)中所有属性机器学习 3.2 决策树模型 学习笔记(待补)取第机器学习 3.2 决策树模型 学习笔记(待补)个状态的样本组成的样本集合。

由经验熵机器学习 3.2 决策树模型 学习笔记(待补)的定义可知,其值越小则样本集合机器学习 3.2 决策树模型 学习笔记(待补)的纯度越高,可在经验熵的基础上进一步计算每个属性作为划分指标后对数据集合经验熵变化的影响,即信息增益。信息增益度量的是已知随机变量机器学习 3.2 决策树模型 学习笔记(待补)的信息使得随机变量机器学习 3.2 决策树模型 学习笔记(待补)的信息不确定性减少的程度。

对于任意给定的训练样本数据集机器学习 3.2 决策树模型 学习笔记(待补)及上的某个属性机器学习 3.2 决策树模型 学习笔记(待补),属性机器学习 3.2 决策树模型 学习笔记(待补)关于集合机器学习 3.2 决策树模型 学习笔记(待补)的信息增益机器学习 3.2 决策树模型 学习笔记(待补)定义为经验熵机器学习 3.2 决策树模型 学习笔记(待补)与条件经验熵机器学习 3.2 决策树模型 学习笔记(待补)之差,即有:
机器学习 3.2 决策树模型 学习笔记(待补)
显然,对于属性机器学习 3.2 决策树模型 学习笔记(待补)关于集合机器学习 3.2 决策树模型 学习笔记(待补)的信息增益机器学习 3.2 决策树模型 学习笔记(待补)如果其值越大则表示使用属性机器学习 3.2 决策树模型 学习笔记(待补)划分后的样本集合纯度越高,使得决策树模型具有更强的分类能力,故可将机器学习 3.2 决策树模型 学习笔记(待补)作为标准选择合适的判别属性,通过递归计算样本属性的信息增益以实现对决策树的构造。

使用信息增益指标作为划分属性选择标准的时候,选择结果通常会偏向取值状态数目加多的属性。为了解决这个问题,最简单的思路是对信息增益进行归一化,信息增益率便可以看作对信息增益进行归一化的一个度量标准。信息增益率在信息增益的基础上引入一个增益因子,消除属性取值数目变化对计算结果的干扰。具体来说,对于给任意给定的训练样本的数据集合机器学习 3.2 决策树模型 学习笔记(待补)及其上的某个属性机器学习 3.2 决策树模型 学习笔记(待补),属性机器学习 3.2 决策树模型 学习笔记(待补)关于集合机器学习 3.2 决策树模型 学习笔记(待补)的信息增益率机器学习 3.2 决策树模型 学习笔记(待补)定义为:
机器学习 3.2 决策树模型 学习笔记(待补)
其中机器学习 3.2 决策树模型 学习笔记(待补)为校正因子,由下式计算:
机器学习 3.2 决策树模型 学习笔记(待补)
显然,属性机器学习 3.2 决策树模型 学习笔记(待补)的取值状态数机器学习 3.2 决策树模型 学习笔记(待补)值越大,则机器学习 3.2 决策树模型 学习笔记(待补)值也越大,由此可以减少信息增益的不良偏好对决策树某型结构所带来的影响。

对于决策树模型,还可以用基尼指数作为划分标准来选择最优属性。与上的概念类似,基尼指数可以用来度量数据集的纯度。对于任意给定的一个机器学习 3.2 决策树模型 学习笔记(待补)分类,假设样本点属于第机器学习 3.2 决策树模型 学习笔记(待补)类的概率为机器学习 3.2 决策树模型 学习笔记(待补),则关于这个概率分布机器学习 3.2 决策树模型 学习笔记(待补)的基尼指数可以定义为
机器学习 3.2 决策树模型 学习笔记(待补)
即有:
机器学习 3.2 决策树模型 学习笔记(待补)
相应的,对于任意给定的样本集合机器学习 3.2 决策树模型 学习笔记(待补),可将其基尼指数定义为:
机器学习 3.2 决策树模型 学习笔记(待补)
其中,机器学习 3.2 决策树模型 学习笔记(待补)机器学习 3.2 决策树模型 学习笔记(待补)中属于第机器学习 3.2 决策树模型 学习笔记(待补)类的样本子集;机器学习 3.2 决策树模型 学习笔记(待补)是类别方案数。

样本集合机器学习 3.2 决策树模型 学习笔记(待补)的基尼指数表示在机器学习 3.2 决策树模型 学习笔记(待补)中随机选中一个样本被错误分类的概率。显然,机器学习 3.2 决策树模型 学习笔记(待补)的值越小,数据集机器学习 3.2 决策树模型 学习笔记(待补)中样本的纯度越高,或者说机器学习 3.2 决策树模型 学习笔记(待补)中样本种类一致性越高。

若样本集合机器学习 3.2 决策树模型 学习笔记(待补)根据属性机器学习 3.2 决策树模型 学习笔记(待补)是否取某一可能值机器学习 3.2 决策树模型 学习笔记(待补)而被分割为机器学习 3.2 决策树模型 学习笔记(待补)机器学习 3.2 决策树模型 学习笔记(待补)两部分,即
机器学习 3.2 决策树模型 学习笔记(待补)
则在属性机器学习 3.2 决策树模型 学习笔记(待补)为划分属性的条件下,集合机器学习 3.2 决策树模型 学习笔记(待补)的基尼指数可以定义为:
机器学习 3.2 决策树模型 学习笔记(待补)

3.2.3 模型构造(占坑)

基于上述判断标准,主要有三种相应的决策树生成算法

  • 基于信息增益:ID3算法
  • 基于信息增益率:C4.5算法
  • 基于基尼指数:CART算法

待补

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
xiaoxingxing的头像xiaoxingxing管理团队
上一篇 2022年5月22日
下一篇 2022年5月22日

相关推荐