首页 > 其他分享 >机器学习系列——2、决策树

机器学习系列——2、决策树

时间:2022-11-02 10:31:48浏览次数:53  
标签:系列 样本 增益 划分 机器 决策树 节点 属性


决策树(decision tree)是一种基本的分类与回归方法。

决策树模型呈树形结构,在分类过程中,表示基于特诊对实例进行分类的过程。它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。

其主要优点是模型具有可读性,分类速度快。学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型。

预测时,对新的数据,利用决策树模型进行分类。

决策树学习通常包括三个步骤:

  • 特征选择
  • 决策树的生成
  • 决策树的修剪

决策树与if-then规则

可以将决策树看成一个if-then规则的集合,将决策树转换成if-then规则的过程如下:由决策树的根结点到叶节点的每一条路径构建一条规则;路径上内部结点的特征对应着规则的条件,而叶节点的类对应着规则的结论,决策树的路径或其对应的if-then规则集合具有一个重要的性质:互斥并且完备。这就是说,每一个实例都被一条路径或一个规则所覆盖,而且只被一条路径或一条规则所覆盖。这里所谓覆盖指的是实例的特征与路径上的特征一致或实例满足规则的条件。

决策树与条件概率分布

决策树还可以表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域,并在每个单元定义一个类的概率分布,就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X表示为特征的随机变量,Y表示类的随机变量,那么这个条件概率分布表示为P(Y|X)。各叶节点上的条件概率往往偏向某一个类,即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。

机器学习系列——2、决策树_决策树

决策树模型

输入:训练集机器学习系列——2、决策树_概率分布_02, 属性集机器学习系列——2、决策树_概率分布_03

机器学习系列——2、决策树_概率分布_04

决策树是一个递归过程,有三种情况会导致递归返回:

  • 当前节点包含的样本属于同一类别,无需划分
  • 当前属性集为空或所有样本在所有属性上取值相同,无法划分
  • 当前节点包含的样本集合为空,无法划分

由上述算法的伪代码可以看出,决策树构造最重要的环节就是如何选择划分的属性

  • 信息增益(ID3)
  • 信息增益率(C4.5)
  • 基尼系数(CART)

ID3

信息熵

样本集合D中第i类样本所占比率为机器学习系列——2、决策树_信息增益_05,则该样本的信息熵机器学习系列——2、决策树_决策树_06

属性A对样本D进行划分后的信息熵

假设属性A有V个可选值,则a将D切成V个子样本D1,D2,…,DV。则划分后的信息熵机器学习系列——2、决策树_概率分布_07
其中机器学习系列——2、决策树_概率分布_08表示子样本机器学习系列——2、决策树_决策树_09的个数

对样本D划分属性A的信息增益
机器学习系列——2、决策树_信息增益_10
每次划分我们都选择信息增益最大的那个属性

C4.5

实际上,信息增益准则对可取值数目较多的属性有所偏好,为减少这种偏好带来的不利影响,C4.5算法使用增益率来进行属性划分

属性a的固有值:机器学习系列——2、决策树_信息增益_11

属性a的可能取值数目越多,则固有值越大。

增益率:机器学习系列——2、决策树_概率分布_12

需要注意的是,增益率准则对可取值数目较少的属性有所偏好,所以C4.5算法不是直接取增益率最大的候选划分属性,而是:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的

CART

数据集D的基尼系数:
机器学习系列——2、决策树_决策树_13

直观来说,基尼系数反映了从数据集中抽取两个样本,其类别不一致的概率。因此,基尼系数越小,则数据集纯度越高

机器学习系列——2、决策树_决策树_14

我们在选属性时,选择那个使得划分后基尼指数最小的属性作为最优属性划分
数据集D的基尼系数:
机器学习系列——2、决策树_决策树_13

直观来说,基尼系数反映了从数据集中抽取两个样本,其类别不一致的概率。因此,基尼系数越小,则数据集纯度越高

机器学习系列——2、决策树_决策树_14

我们在选属性时,选择那个使得划分后基尼指数最小的属性作为最优属性划分

剪枝处理 TODO

剪枝是决策树学习算法对付过拟合的主要手段。

剪枝可分为预剪枝和后剪枝两种基本策略。

  • 预剪枝:预剪枝是指在决策树的生成过程中,对每个节点在划分前后进行估计,若当前节点的划分不能带来决策树泛化性能的提升,则停止划分并将当前节点标记为叶节点。
  • 后剪枝:先从训练集生成一颗完整的决策树,然后自底而上地对非叶节点进行考察,若将该节点对应的子树替换为叶节点能带来决策树的泛化性能提升,则将该子树替换为叶节点。

连续值与缺失值

连续值处理

对于连续的属性,可取值不可数,因此不能直接用连续属性的取值来对节点进行划分。此时就需要将连续属性离散化。最简单的策略就是二分法(C4.5采取的就是这种机制):

  • 将连续属性a的所有n个取值升序排列
  • 相邻两个取值的均值可作为候选划分点,则有n-1个候选划分点
  • 从这n-1个候选划分点选一个最好的:计算这n-1个候选划分点划分后的信息增益,选择信息增益最大的那个候选划分点作为属性a的划分点

缺失值处理

现实任务中,经常会遇到数据不完整的情况,尤其是属性较多的时候,会有大量样本出现缺失值。

我们需要解决两个问题:

  • 如何在属性缺失的情况下进行划分属性选择
  • 给定划分属性,如何对带缺失属性的样本进行划分

机器学习系列——2、决策树_信息增益_17

多变量决策树

OC1等 TODO

增量学习 TODO

  • ID4
  • ID5R
  • ITI

决策树的回归问题


标签:系列,样本,增益,划分,机器,决策树,节点,属性
From: https://blog.51cto.com/u_15856104/5816017

相关文章

  • Jenkins发版通知企业微信机器人
    1)开始通知在Jenkins发版过程的第一步添加下面内容,调用下面脚本实现机器人发版通知(注意脚本路径和传参)${BUILD_USER}是Jenkins内置变量,执行发布的用户名,需要安装插件-Buil......
  • 决策树Decision Tree
    1.决策树概念:是一种非参数的有监督学习方法,他能从一系列有特征和标签的数据中总结出决策规则,并用树状图来呈现这些规则,以解决分类和回归问题。思想:决策树基于特征对数据......
  • 梯度提升决策树GBDT
    GBDT简述梯度提升树:使用损失函数的负梯度在当前模型的值求解更为一般的提升树模型,这种基于负梯度求解提升树前向分布迭代过程叫做梯度提升树GBDT可以适用于回归问题(线......
  • 第12章 决策树
     12-1什么是决策树        ......
  • 机器学习
    机器学习机器学习,是人工智能一个基本条件,是建立大数据基础之上。从数据中提取出模型,并可以利用模型对未知的数据做出预测历史往往不一样,但历史总是惊人的相似  有监......
  • R机器学习:特征工程与特征选择的介绍
    两个月没更新了,没有其它理由,就是懒惰,间接持续性的懒惰,一直持续了2个月,简直懒惰!!!大家的好多的私信也没回就过期回不了了。请大家批评我!!!。看了很多高深的算法之后,实在是看不......
  • tensorflow2从入门到精通——自编码器系列原理以及实现
    自编码器无监督学习,常用于数据去噪,数据降维、图像重构无监督学习监督学习样本数据对应着标签,称之为有监督学习难点绝大部分标签为人工标注有些数据对于标注者的先验......
  • 深度学习从入门到精通——人工智能、机器学习与深度学习绪论
    人工智能、机器学习与深度学习​​人工智能​​​​定义​​​​人工智能​​​​历史​​​​机器学习​​​​分类,按照监督方式​​​​深度学习​​​​主要应用​​​​......
  • 深度学习从入门到实战——机器学习常用算法总结
    机器学习笔记​​一级目录​​​​机器学习​​​​定义​​​​分类​​​​学派分类​​​​按照学习方式分类​​​​业务领域分类​​​​学习步骤​​​​学习技巧​​......
  • 李宏毅机器学习笔记——机器学习相关技术介绍
    机器学习技术介绍让机器具有学习的能力,人工智能是人类想要达到的目的,能够像人一样的聪明,机器通过学习方式来达到跟人一样甚至超越人的能力。机器学习技术是达成人工智能的手......