python决策树-1

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/78755544

本文主要内容:

  1. 通过简单的示例说明决策树,以及决策树的定义
  2. 信息熵概念,以及决策树,树生成节点划分的依据。三种计算方法方法:
    • 1.信息增益(由ID3算法作为特征选取标准)
    • 2.信息增益比/率(由C4.5算法作为特征选取标准)
    • 3.基尼指数(由CART作为特征选取标准)
  3. 树的生成ID3算法,C4.5算法
  4. 算法python实现以及示例

决策树示例,以及决策树的定义

下图决策树预测贷款用户是否具有偿还贷款的能力,其中贷款用户主要具备三个属性:是否拥有房产,是否结婚,平均月收入。

每一个内部节点都表示一个属性条件判断,叶子节点表示贷款用户是否具有偿还能力(即类别)。 例如:用户甲没有房产,没有结婚,月收入5K。通过决策树的根节点判断,用户甲符合右边分支 (拥有房产为“否”);再判断是否结婚,用户甲符合左边分支(是否结婚为否);然后判断月收入是否大于 4k,用户甲符合左边分支 (月收入大于4K),该用户落在“可以偿还”的叶子节点上。所以预测用户甲具备偿还贷款能力。

定义(决策树)

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

分类过程

使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。


信息熵,决策树,树生成节点划分的依据

在信息论里面,熵(entropy)是信息不确定性的一个测度,熵越大则表示信息的不确定程度越高。这么说好像的确有点抽象,还是用公式解释吧:

这里H是熵,U可以理解为所有可能事件的集合,P(x)则是某一具体事件x发生的概率,对数的底一般取2。举个例子,预测明天的天气,如果能100%确定明天一定是晴天,那么熵就是-1*log1=0,也就是说不确定性为零。如果说明天有50%概率晴天,50%概率下雨,那么熵就是2*(-0.5)log0.5=2*(-0.5)(-1)=1,可以说不确定性为1。而如果明天有25%概率晴天,25%概率下雨,25%概率阴天,25%概率下雪,那么熵就是4*(-0.25)(log0.25)=2, 也就是说随着不确定程度的增加,熵也在不断地增大。 多少信息用信息量来衡量,我们接受到的信息量跟具体发生的事件有关。信息的大小跟随机事件的概率有关。越小概率的事情发生了产生的信息量越大,如四川发生地震了;越大概率的事情发生了产生的信息量越小,如太阳从东边升起来了(肯定发生嘛,没什么信息量)。这很好理解!

当随机变量只能取两个值,例如1,0即X的分布为:

P(X=1)=p, P(X=0)=1-p, 0<=p<=1

当p=0.5时,熵取值最大,随机变量不确定性最大(这个概率对我们”分类基本没什么用”)

计算增益,有三种方法:

  1. 信息增益(由ID3算法作为特征选取标准)
  2. 信息增益比/率(由C4.5算法作为特征选取标准)
  3. 基尼指数(由CART作为特征选取标准)

信息增益

首先说明下条件熵:

定义(信息增益(information gain))

信息增益表示的是:得知特征X的信息而使得类Y的信息的不确定性减少的程度。 具体定义如下: 特征A对训练数据集D的信息增益g(D,A)定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即g(D,A)=H(D)-H(D|A) 根据信息增益准则进行特征选择的方法是:对训练数据集D,计算其每个特征的信息增益,选择信息增益最大的特征。

信息增益算法:

输入:训练数据集D和特征A;

输出:特征A对训练数据集D的信息增益g(D,A)

(1)计算数据集D的经验熵H(D).

(2)计算特征A对数据集D的经验条件熵H(D|A).

(3)计算信息增益: g(D, A) = H(D) - H(D|A)

下面给出李航书中贷款申请判断的数据,以及计算示例。四个属性:

年龄: 0 -> 青年, 1 -> 中年, 2 -> 老年

有工作: 0 -> 否, 1 -> 是

有房子: 0 -> 否, 1 -> 是

信贷情况: 0 -> 一般, 1 -> 好, 2 -> 非常好

对应的Y类别0 -> 不能提供贷款, 1 -> 能提供贷款,

def get_loan_data_lh():
    x = np.array([
        [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2],
        [0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0],
        [0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
        [0, 1, 1, 0, 0, 0, 1, 1, 2, 2, 2, 1, 1, 2, 0]
    ])

    x = x.T
    y = np.array([0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0])
    return x, y

首先计算类别的经验熵:

对应的代码如下:

def _cal_class_entropy(self, y):
    num = len(y)
    print num  # 15
    unique_class, counter = np.unique(y, return_counts=True)
    print unique_class, counter
    # [0 1] [6 9]
    # calculate each class probability
    class_prob = [c * 1.0 / num for c in counter]
    print class_prob
    # [0.40000000000000002, 0.59999999999999998]
    print self._cal_entropy(class_prob)
    # 0.970950594455

def _cal_entropy(self, arr_prob):
    """
    for example  arr_prob like [0.5, 0.5]
    return -1 * 0.5 *log0.5 + -1 * 0.5 * log0.5 = 1
    """
    # -1 * sum(Pi * logPi)
    return np.sum(-1 * np.log2(arr_prob) * arr_prob)

def test_cal_class_entropy():
    from create_data import get_loan_data_lh
    X, Y = get_loan_data_lh()
    dt = DTree()
    dt._cal_class_entropy(Y)

树的生成ID3算法,C4.5算法


算法python实现以及示例

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

谷歌开源神经网络模型,压缩图片比传统方法提升25%(附论文)

【新智元导读】 谷歌官方博客今天发布了一篇文章,介绍如何使用神经网络压缩图片。在论文中,谷歌证明了神经网络可以获得比现在普遍使用的压缩方法质量更好、大小更小的图...

45040
来自专栏AI科技大本营的专栏

谷歌大脑深度学习从入门到精通视频课程[1.2]:前馈神经网络——激活函数

课程主要内容 回顾上一节课的内容。(P2) 神经网络中的四种激活函数的性质。(P3-P6) PPT 解释如下: P1. 首页 P2. 回顾上一节课的内容,主要...

27730
来自专栏量子位

自然语言处理中的注意力机制是干什么的?

王小新 编译自Quora 量子位 出品 | 公众号 QbitAI 谈神经网络中注意力机制的论文和博客都不少,但很多人还是不知道从哪看起。于是,在国外问答网站Qu...

29730
来自专栏BestSDK

无论人工智能发展到什么地步,都离不开这6段代码

从代码中追溯深度学习的历史 深度学习发展到如今的地位,离不开下面这 6 段代码。本文介绍了这些代码的创作者及其完成这些突破性成就的故事背景。每个故事都有简单的代...

382140
来自专栏杂七杂八

Doc2vec预测IMDB评论情感

本文内容源自于国外2015年的一篇博客,中文翻译可以在伯乐在线看到。可以整体了解一些word2vec和doc2vec的使用方法,但是由于时间过去很久了,gens...

1.1K90
来自专栏AI科技评论

学界 | Yann LeCun新作,中日韩文本分类到底要用哪种编码?

AI科技评论按:前几天,Yann LeCun与其学生 张翔在arXiv上发表了一篇新作「Which Encoding is the Best for Text ...

37140
来自专栏云时之间

NLP入门之N元语法模型

在上边我们知道其实当今的自然语言处理的主流趋势是统计自然语言处理,而统计自然语言处理的基本目的就是结合语料库中的一些数据对于某些未知的数据进行处理,从而根据这些...

73950
来自专栏人工智能

基于神经网络的图像压缩技术

(本文由软件工程师 Nick Johnston 和 David Minnen 发布)

1K120
来自专栏AI研习社

如何对非结构化文本数据进行特征工程操作?这里有妙招!

文本数据通常是由表示单词、句子,或者段落的文本流组成。由于文本数据非结构化(并不是整齐的格式化的数据表格)的特征和充满噪声的本质,很难直接将机器学习方法应用在原...

61560
来自专栏大数据文摘

算法可视化:把难懂的代码画进梵高的星空

31440

扫码关注云+社区

领取腾讯云代金券