《统计学习方法》笔记五 决策树

知识概要

决策树模型

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点。内部结点表示一个特征或属性,叶结点表示一个类。

决策树与if-then规则

可以把决策树看成一个if-then规则的集合,则应满足互斥并且完备,即每一条实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖。

决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布,定义在特征空间的一个划分上,将特征空间划分为互不相交的单元或区域,并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。设X为表示特征的随机变量,Y为表示类的随机变量,则条件概率分布表示为P(Y|X)。X取值于给定划分下单元的集合,Y取值于类的集合。

特征选择

包括以下

  • 信息增益
  • 信息增益比
  • 基尼指数

特征选择在于选取对训练数据具有分类能力的特征,如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。通常特征选择的准则是信息增益信息增益比

信息增益

1 熵

熵表示随机变量不确定性的度量,熵越大,随机变量的不确定性越大。设X是一个取有限个值的离散随机变量,概率分布为

P(X = xi) = pi,  i = 1,2,...n

则随机变量X的熵定义为

以2或e为底,此时熵的单位分别称作比特(bit)或纳特(nat),熵只依赖X的分布,与X的取值无关,所以也可记为H(p)

2 条件熵

H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性 

定义为X给定条件下Y的条件概率分布的熵对X的数学期望:

当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵和经验条件熵。

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

信息增益比

当训练数据集的经验熵大的时候,信息增益值偏大,反之偏小,使用信息增益比校正。

基尼指数

CART中生成分类树中使用,用基尼指数选择最优特征,同时决定该特征的最优二值且分点。

决策树的生成

ID3算法

ID3算法只有树的生成,所以该算法生成的树容易产生过拟合。

C4.5

与ID3相似,在生成过程中,用信息增益比来选择特征

决策树的剪枝

决策树生成往往对训练数据分类很准确,但对未知的测试数据的分类却没有那么准确,即过拟合。过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,解决方法是考虑决策树的复杂度,对已生成的树进行简化,成为剪枝(pruning),具体指从生成的树上裁掉一些子树或叶结点,并将其根结点或父结点作为新的叶结点。

设树T的叶结点个数为| T | , t 是树T的叶结点有 Nt 个样本点,其中k类的样本点有 Ntk 个,k = 1, 2, · · · , K,Ht(T) 为叶结点 t 上的经验熵,a ≥ 0为参数,则决策树学习的损失函数可以定义为

CART算法

可用于分类也可用于回归,给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树,内部结点特征的取值是“是”和“否”,左分支取值为是,右取值为否,等价于递归的二分每个特征,将输入空间即特征空间划分为有限个单元,并在这些单元上确定预测的概率分布,也就是在输入给定的条件下输出的条件概率分布。

由决策树生成和剪枝两个步骤组成。

回归树生成

一个回归树对应输入空间(即特征空间)的一个划分以及在划分的单元上的输出值,假设已将输入空间划分为M个单元,R1,...RM,并在每个单元RM上有一个固定的输出值Cm,则回归树模型可表示为

如何划分,选择第j个变量和它的取值s,作为切分变量和且分点,并定义两个区域

然后寻找足有切分变量j和最优切分点s

对固定输入变量j可找到最优切分点s

遍历所有输入变量,找到最优的切分变量j,构成一个对(j,s),依次将输入空间划分成两个区域,对每个区域重复上述步骤,直到满足停止条件为止。这样的回归树称为最小二乘回归树。

分类树生成

输入:训练数据集D,停止计算条件

输出:CART决策树

1)设结点的训练数据集为D,计算现有特征对该数据集的基尼指数。此时,对每一个特征A,对其可能取的每个值a,根据样本点对A = a的测试为"是"或者“否”将D分割为D1和D2两部分,计算其基尼系数。

2)在所有可能的特征A以及他们所有可能的切分点a中,选择基尼系数最⼩小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点,从现结点⽣生成两个⼦子结点,将训练数据集依特征分配到两个⼦子结点中去。

3)对两个⼦子结点递归地调⽤用上述两个步骤,直⾄至满⾜足停⽌止条件。

4)⽣生成CART决策树

CART剪枝

CART剪枝算法从“完全⽣生⻓长”的决策树的底端减去⼀一些⼦子树,使决策树变⼩小(模型变简单),从⽽而能够对未知数据有更更准确的预测

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

感知机(Perceptron)是怎么实现“知错能改”的?

感知机(perceptron)是二类分类的线性分类模型,其输入为实例的特征向量,输出为实例的类别,取+1和-1二值。感知机对应于输入空间中将实例划分为正负两类的...

39780
来自专栏机器学习算法与理论

核技巧

关于映射到更高维平面的方法。 对数据进行某种形式的转换,从而得到新的变量来表示数据。从一个特征空间转换到另一个特征空间(特征空间映射)。 其实也就是另外一种距离...

35360
来自专栏机器之心

教程 | 基础入门:深度学习矩阵运算的概念和代码实现

选自Medium 机器之心编译 参与:蒋思源 本文从向量的概念与运算扩展到矩阵运算的概念与代码实现,对机器学习或者是深度学习的入门者提供最基础,也是最实用的教...

458130
来自专栏机器学习算法原理与实践

感知机原理小结

    感知机可以说是最古老的分类方法之一了,在1957年就已经提出。今天看来它的分类模型在大多数时候泛化能力不强,但是它的原理却值得好好研究。因为研究透了感知...

9320
来自专栏机器学习算法工程师

RNN入门与实践

作者:叶虎 编辑:黄俊嘉 引言 递归神经网络(Recurrent Neural Network, RNN)是神经网络家族的重要成员,而且也是深度学习领域中的得...

39670
来自专栏智能算法

分类回归树算法---CART

一、算法介绍 分类回归树算法:CART(Classification And Regression Tree)算法也属于一种决策树,和之前介绍了C4.5算法相...

52290
来自专栏杨熹的专栏

用 Doc2Vec 得到文档/段落/句子的向量表达

本文结构: Doc2Vec 有什么用 两种实现方法 用 Gensim 训练 Doc2Vec ---- Doc2Vec 或者叫做 paragraph2vec, s...

2K100
来自专栏desperate633

小白也能看懂的BP反向传播算法之Surpass Backpropagation

上篇文章小白也能看懂的BP反向传播算法之Further into Backpropagation中,我们小试牛刀,将反向传播算法运用到了一个两层的神经网络结构中...

20920
来自专栏null的专栏

利用Theano理解深度学习——Auto Encoder

注:本系列是基于参考文献中的内容,并对其进行整理,注释形成的一系列关于深度学习的基本理论与实践的材料,基本内容与参考文献保持一致,并对这个专题起名为“利用The...

38280
来自专栏算法channel

全面总结机器学习项目和面试中几乎绕不开的决策树

决策树是一种常见的机器学习算法,它的思想十分朴素,类似于我们平时利用选择做决策的过程。

12300

扫码关注云+社区

领取腾讯云代金券