决策树

作者: 初七123 | 来源:发表于2017-10-09 17:14 被阅读41次

一图胜千言

一个女孩找相亲对象的决策逻辑

EricZhang 的博客

这便是决策树的核心思想:基于训练数据学习出一个含有决策逻辑的树
然后用这个决策树进行分类预测
其中常见的学习算法有 ID3、C4.5、CART

下面内容需要一定的概率与数理统计基础

信息论

设定X是一个取有限个值的随机变量


则随机变量X的熵定义

熵越大,随机变量的不确定性就越大。事件的确定性越高,熵就越小,比如必然事件的熵为0。

条件熵表示已知X的条件下Y的不确定性
定义为X给定条件下Y的条件概率分布的熵对X的数学期望

当对X的概率密度是由极大似然估计(基于频率估计)得到时,熵被成为经验熵。

设训练数据集D,特征A
信息增益定义为经验熵与经验条件熵之差

信息增益比定义为信息增益和的经验熵的比值

ID3 & C4.5

ID3的核心思想为选择信息增益最大的特征进行递归分类
输入训练数据集D,特征集A,阈值 ε
输出决策树T

(1) 若 D 中所有实例属于同一类C(k),则返回单节点树,并标记类别为C(k)
(2) 若A为空集,则返回单节点树,并将D中实例数最多的类别C(k)作为分类标记
(3) 否则,使用极大似然估计计算特征集A的信息增益,选择增益最大的特征A*
(4) 如果信息增益 g(A*, D) < ε ,则返回单节点树,并将D中实例数最多的类别C(k)作为分类标记
(5) 否则,对A*的每一种取值将D划分为若干个子集D(i),并将D(i)中实例数最多的类别C(k)作为分类标记,构建子节点。
(6) 对于第i个子节点,以D(i)为训练集,A - {A*}特征集,递归调用(1) ~ (5),得到子树T(i)

为什么选择信息增益大的特征作为划分?
对于待划分的数据集D,其 H(D) 是一定的,但是划分之后的熵 H(D|A) 是不定的,H(D|A) 越小说明使用此特征划分得到的子集的不确定性越小(也就是纯度越高),因此 H(D)-H(D|A) 差异越大,说明使用当前特征划分数据集D的话,其纯度上升的更快。

C4.5

C4.5和ID3的区别为——使用信息增益比而不是信息增益选择特征

这是因为ID3算法存在一个问题,就是偏向于多值属性。例如,如果存在唯一标识属性ID,则ID3会选择它作为分裂属性,这样虽然使得划分充分纯净,但这种划分对分类几乎毫无用处。C4.5使用信息增益比试图克服这个偏倚。

信息增益比的本质: 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时,惩罚参数较小;特征个数较少时,惩罚参数较大。

惩罚参数:数据集D以特征A作为随机变量的熵的倒数,即将特征A取值相同的样本划分到同一个子集中(而同通常所说数据集的熵是依据类别进行划分的)

惩罚参数

C4.5 剪枝
C4.5决策树生成算法递归的产生决策树,直到不能继续下去。这样产生的决策树往往对训练数据的分类很准确,却容易出现过拟合现象,所以有时候我们需要简化决策树,减少模型的拟合程度。通常方法是减去一些不必要的枝叶。

此处不介绍具体算法

CART(分类与回归树)

分类和回归树的意思是CART分为回归树算法和分类树算法

首先我们要知道的是CART假设决策树视为一颗二叉树(C4.5 是多叉树)
其次CART算法分为两个组成部分:
(1) 基于训练数据集生成决策树,要尽可能大
(2) 使用CART剪枝算法简化决策树

CART分类树

和C4.5不同的是,CART分类树使用基尼指数作为划分特征选择的标准

基尼指数定义

基尼指数越大表示不确定性越大,这点和熵是类似的。

因为CART假设决策树唯一一颗二叉树,所以生成算法和C4.5也有些不同
主要区别是对于每一个特征计算A,对其每个可能取值a,用“是”、“否” A = a 划分为两个子集计算基尼指数(C4.5是计算特征A的条件熵)

CART 生成算法

CART剪枝 —— CCP方法

CCP方法选择节点误差率增益值最小的非叶子节点,删除该非叶子节点的左右子节点。

子树的损失函数

误差率增益值

α 就是误差率增益值,因为 α 越大意味着剪枝前后预测误差 C(T)变化越大!

步骤

注意:若有多个非叶子节点的表面误差率增益值相同小,则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。

CART回归树

回归树把输入空间划分为多个单元,并且给出对应的输出值。与之类似的算法是线性回归

举个例子
给出一个人的健康指标X。先做多次二分类,最后每个叶结点对应的不再是类别,而是该结点下所有样本的健康系数均值,作为对这些样本健康系数的预测y。

推导
给定训练数据集

假设回归树将输入空间划分为M个单元[R1,R2...Rm],每个单元对应的输出值为Cm,于是回归树模型可表示为

Cm的取值

对于单元Rm,设其预测误差为

使 Cm* = Rm单元中所有样本的 y 值的平均值,即可使这个误差最小化

选择划分特征
和C4.5算法一样,CART回归树也需要选择一个特征进行子树划分

CART回归树生成算法

参考

《统计学习方法》
http://www.cnblogs.com/muzixi/p/6566803.html
http://www.cnblogs.com/fionacai/p/5894142.html
http://www.jianshu.com/p/b90a9ce05b28

相关文章

  • 机器学习6-决策树

    一. 决策树概述 1.1 什么是决策树 决策树输入: 测试集决策树输出: 分类规则(决策树) 1.2 决策树算法概...

  • 决策树

    1、决策树 决策树学习通常包括3个步骤: 特征选择。 决策树生成。 决策树剪枝。 决策树的学习目标是:根据给定的训...

  • 决策树

    决策树 决策树模型与学习 特征选择 决策树的生成 决策树的剪枝 CART 算法 决策树模型呈树形结构,在分类问题中...

  • 决策树算法总结

    目录 一、决策树算法思想 二、决策树学习本质 三、总结 一、决策树(decision tree)算法思想: 决策树...

  • 机器学习 - 决策树算法[一]

    1 决策树模型与学习 1.1 决策树模型 决策树定义: 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由...

  • 机器学习系列(三十六)——回归决策树与决策树总结

    本篇主要内容:回归决策树原理、回归树学习曲线、决策树总结 回归决策树原理 回归决策树树是用于回归的决策树模型,回归...

  • [机器学习]决策树

    决策树 @(技术博客)[机器学习, 决策树, python] 学习决策树首先要搞清楚决策树是什么(what),在弄...

  • 经典机器学习系列之【决策树详解】

      这节我们来讲说一下决策树。介绍一下决策树的基础知识、决策树的基本算法、决策树中的问题以及决策树的理解和解释。 ...

  • 第5章 决策树

    内容 一、决策树内容简介 二、决策树的模型与学习 三、特征选择 四、决策树生成 五、决策树剪枝 六、CART算法 ...

  • 决策树与随机森林

    PART I 决策树 (Decision Tree) 决策树基本知识 决策树何时停止生长:(I) all leaf...

网友评论

    本文标题:决策树

    本文链接:https://www.haomeiwen.com/subject/bhejyxtx.html