机器学习实战之决策树

一、简介

决策树是一类常见的机器学习方法,以二分类任务为例,我们希望从给定训练数据集学得一个模型用以对新数据进行分类,比如通过一组数据通过模型训练得到以下的决策树:

二、理论

决策树学习的关键是如何选择最优划分属性,一般而言,随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”越来越高。

1、信息熵

熵定义为信息的期望值,在明晰这个概念之前,我们必须知道信息的定义。如果待分类的事

务可能划分在多个分类之中,则符号的信息定义为

其中是当前样本集合D中第i类样本所占的比例。

为了计算熵,我们需要计算所有类别所有可能值包含的信息期望值,通过下面的公式得到:

其中n是分类的数目,H的值越小,则数据纯度越高。

2、信息增益

假定当前样本集D按照属性a来分类,a的属性取值有共V种情形,则会产生V个分支结点,其中第v个分支结点包含了D中所有在属性a上取值为的样本,该样本记为.并计算出的信息熵,再考虑到不同的分支结点所包含的样本数不同,给分支结点赋予权重,即样本数越多的分支结点对信息熵的影响越大,于是可计算出用属性a对样本集D进行划分所获得的“信息增益”。

信息增益越大,意味着使用属性a来划分所获得的“纯度提升”越大,决策树中的ID3学习算法就是使用信息增益来选择划分属性的。

3、信息增益率

实际上,信息增益准则对可取值数目较多(V较大)的属性有所偏好,为减少这种偏好可能带来的不利影响,C4.5决策树算法使用增益率来选择划分属性,增益率定义为:

其中

称为属性a的固有值。属性a的可能取值数目越多,则IV(a)值通常会越大。但是增益率准则对可取值数目较少的属性有所偏好,因此C4.5不是直接选择增益率最大的候选划分属性,而是使用启发式:先从候选划分属性中找到信息增益高于平均水平的属性,再从中选择增益率最高的。

4、基尼指数

CART决策树使用“基尼指数”来选择划分属性,数据集D的纯度可用基尼值来度量:

Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率,因此,Gini(D)越小,则数据集D的纯度越高。

属性a的基尼指数定义为

我们选择属性集合A中,选择那个使得划分后基尼指数最小的属性作为最优划分属性。

三、Python实践

这里我们采用信息增益ID3学习算法来选择划分属性,首先是计算给定数据集的信息熵,首先,计算数据集中实例的总数。然后,创建一个数据字典,它的键值是最后一列的数值 。如果当前键值不存在,则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。最后,使用所有类标签的发生频率计算类别出现的概率。我们将用这个概率计算香农熵 ,统计所有类标签发生的次数。

以上我们知道怎么计算信息熵,接下来是划分数据集,度量划分数据集的熵,以便判断当前是否正确地划分了数据集。我们将对每个特征划分数据集的结果计算一次信息熵,然后判断按照哪个特征划分数据集是最好的划分方式。

接下来我们将遍历整个数据集,循环计算信息熵和sub_data()函数,根据信息增益最大的值找到对应最好的特征划分方式。

最后递归构建决策树,得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分。第一次划分之后,数据将被向下传递到树分支的下一个节点,在这个节点上,我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

递归结束的条件是:情况一是程序遍历完所有划分数据集的属性,通过少数服从多数的原则,确定该分支的类别,构建函数maj_cnt()来找到该分支出现次数最多的类别。情况二是每个分支下的所有实例都具有相同的分类。

最后采用《机器学习实战》第三章的案例数据来测试。

构建的决策树为:

{‘no surfacing’:}}}

参考:《机器学习实战》

本文来自企鹅号 - 全球大搜罗媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闪电gogogo的专栏

《统计学习方法》笔记二 感知机

感知机(perceptron)是二分类的线性分类模型,输入为实例的特征向量,输出为实例的类别,取±1。感知机对应与输入空间中将实例划分为正负两类的分离超平面,属...

8720
来自专栏null的专栏

机器学习算法实现解析——libFM之libFM的训练过程之Adaptive Regularization

本节主要介绍的是libFM源码分析的第五部分之二——libFM的训练过程之Adaptive Regularization的方法。 5.3、Adaptive Re...

71170
来自专栏机器学习算法与Python学习

梯度提升树GBDT原理

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 作者:雪伦_ 链接:http://b...

43060
来自专栏机器学习、深度学习

物体计数--Learning To Count Objects in Images

Learning To Count Objects in Images NIPS 2010 http://www.robots.ox.ac.uk/~v...

29790
来自专栏文武兼修ing——机器学习与IC设计

深入理解感知机

1.模型 感知机的模型如下图所示: ? linear_classifier_structure.png 公式表示如下所示: $$ f(x) = sign(...

382100
来自专栏拂晓风起

验证码去噪 分离背景 分离文字 最大类间方差

13120
来自专栏iOSDevLog

决策树

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

决策树算法原理(下)

    在决策树算法原理(上)这篇里,我们讲到了决策树里ID3算法,和ID3算法的改进版C4.5算法。对于C4.5算法,我们也提到了它的不足,比如模型是用较为复...

11210
来自专栏AI研习社

一文详解 Word2vec 之 Skip-Gram 模型(结构篇)

这次的分享主要是对Word2Vec模型的两篇英文文档的翻译、理解和整合,这两篇英文文档都是介绍Word2Vec中的Skip-Gram模型。下一篇专栏文章将会用T...

70040
来自专栏null的专栏

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

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

38280

扫码关注云+社区

领取腾讯云代金券