文档章节

人工智能算法通俗讲解系列(三):决策树

StanleySun
 StanleySun
发布于 2018/03/24 14:23
字数 2378
阅读 1284
收藏 0

今天,我们介绍的机器学习算法叫决策树。

跟之前一样,介绍算法之前先举一个案例,然后看一下如何用算法去解决案例中的问题。

这里的案例跟K临近法那一讲里的案例差不多,有一点变化。我把案例简述一下:某公司开发了一款游戏,并且得到了一些用户的数据。如下所示:

 

    图上每个图形表示一个用户,横坐标是年龄,纵坐标是性别。红色表示该用户喜欢这款游戏,蓝色表示该用户不喜欢这款游戏。比如,右下角这个蓝色方框,代表的是一个五六十岁的女士。蓝色表示她不喜欢这款游戏。再比如,左上角的红色三角形,代表的是一个十来岁的男孩。红色表示他喜欢这款游戏。

    现在有个新用户,用绿色所示。这家公司想知道:这个新用户会不会喜欢这款游戏?

    仅从图上看,我们很难一眼就做出有效的判断。我们不妨先把用户的属性梳理一下,然后对用户进行归类。按照性别和年龄两个维度来分,可以制作出一个这样的表格。我们把每一个用户都按条件放到相应的格子里,如图所示:

    小于30岁且性别为男的用户都在第一个格子里,总共有3个人,且全部喜欢玩游戏;30以上的且性别为女的用户都在右下角的格子里,总共有4个人,且都不玩这款游戏。其他的人,有的喜欢玩游戏,有的不喜欢。

    我们可以再创建一颗树,用于判断这些人的偏好。比如,我们先用性别作判断条件,把人分成“男”和“女”两份。然后在每一份里面,再用年龄把他们再分成两份。

    图中用椭圆形代表判断条件,比如性别是什么,是否小于30岁。箭头是判断结果,比如男在左侧,女性在右侧。小于30岁的在左侧,大于30岁的在右侧。

    最底下是这棵树的叶子节点,每一个叶子节点就是一个判断结果。对于性别为男且小于30岁的用户,判断结果就在最左侧那片叶子上。这个叶子节点对应的是表格中第一个格子的数据。那里100%的用户都是红色,所以,这用红色的三角表示。数值为1.0,表示红色用户的占比为100%,或者红色用户的概率为100%。

    第二个叶子节点为蓝方块,它对应第二个格子中的数据。符合这些条件的用户,有80%的人是蓝色。所以,这里是蓝色,且数值为0.8。

    其它以此类推。红色0.75表示75%的用户是红色,蓝色1.0,表示100%的人蓝色。

    如果来了新的用户,就把他的属性往这棵树上套,找到他所在的叶子节点,然后根据叶子节点的颜色和数字来判断他的偏好。比如,一个15岁的小伙子,我们看一下,他应该在这棵树的哪个位置。因为是男性,所以在左半部分。有知道他是15岁,小于30岁,所以在他位于左下角的叶子。这个叶子为红色,且数值等于1.0。即喜欢这款游戏的概率为100%。于是,就判断他非常可能喜欢这款游戏。再比如,来了一个25岁的女士。因为是女性,所以在又半个树上。年龄25岁,小于30,所以会会定位在第三个叶子。这个叶子是红色,且数值等于0.75。因此,我们判断他喜欢这款游戏的概率是75%,或者说她有可能喜欢这款游戏。若是一个45岁的女士,往树上套,就会定位在第四个叶子,颜色为蓝色,数值为1.0。因此,她不喜欢这款游戏的概率为100%,或者说喜欢游戏的概率为0。

这棵树就是一颗决策树。

我们同样可以创建另一棵树,把条件的顺序颠倒一下,第一层是年龄,第二层是性别。

这两棵树的叶子都是一样的,只是顺序不一样而已。所以用这两棵树的做判断,结果是一样的。不过,这两棵树不是等价的!

它们的不同之处在于,“性别”和“年龄”这两个属性的重要性不一样!

重要性是什么意思?

可以这么想象一下:如果只让你选择一个属性,你选择哪个属性。或者说只允许选择一个属性的时候,选哪个属性会让你的决策更准确一些?我们不妨实验一下。

1. 假设我们只能用“性别”属性。

我们用性别来判断,发现男性用户里,有一半是红色,一半是蓝色。所以,我们无法判断,男性用户应该是红色好还是蓝色好。发现女性用户里,有3个红色,有5个蓝色。我们隐约可以做一个判断:“女性用户不大喜欢玩这款游戏”。但是,你做这个判断的时候,会底气不足,毕竟还有3个女性是喜欢玩的。

 

2. 假设我们只能用“年龄”这个属性。

我们会发现,小于30岁的用户总共有7个,其中有6个是红色的,占比85.7%。大于30岁的用户总共有9个,其中有8个是蓝色的,占比89%。于是,我们可以大胆的判断:“小于30岁的用户更喜欢玩游戏,大于30岁的用户不喜欢玩。”你做这个判断时,底气十足,铿锵有力!

凭直觉,你就会觉得“年龄”这个属性更重要!

没错,你的直觉是对的!

    原因是,用了“性别”后,数据仍然混乱不清;而用了“年龄”这个属性后,数据变得确定起来。

    关于确定性或不确定性的程度,信息论里用一个叫做“熵”的词来表示。“熵”这个词原本是热力学里的一个概念,用于表示热力学系统的无序程度。熵越大表示越无序,熵越小表示越有序。1948年,香浓把它引入到信息论里,并给出了信息熵的计算公式。信息熵越大,不确定性越大;熵越小,不确定性越小。这个被认为是20世纪最重要的贡献之一!

    上图中,若数据中增加了“性别”属性进行分类,用户是那种颜色仍然不是很确定,所以熵值比较大。若数据中增加了“年龄”属性进行分类,用户的颜色基本就确定了,所以熵值就小。

    因此:一个属性的重要性,可以用它所产生的熵值大小来判断。使得熵值变的更小的属性,重要性更高!

    熵是有一个精确的公式,具体就不在这里写了。有机会的话,我会在以后的高级课程里讲。

    既然熵可以计算,那属性的重要性就可以计算。我们把所有属性产生熵计算一遍,从小到大排序,最小熵值对应的属性就是最重要的。我们把最重要的属性放到决策树最上面的节点。

    然后在每个分支上,计算剩余属性中最重要的属性,放到二级节点。以此类推。

    当我们有很多属性的时候,放在最底下的属性,其影响力可能微小到忽略不计,我们就可以不要它们,这样决策树的结构也就很精简,只包含重要属性。在有些情况下,这样对枝叶的裁剪可以有效的避免过拟合。关于什么叫“过拟合”,以后有机会再讲,有兴趣的同学也可以自己查一查。

    对于上面的两个树,我们可以尝试裁剪一下。如下图所示。以年龄为根的树,通过裁剪,仍然可以有很好的预测准确率,因为右侧被裁剪后,仍然有89%的预测准确率,这个概率已经足够高。而对以性别为根对树进行裁剪,就会有些问题。因为右侧叶子仅有62%的预测准概率。可以看出来“年龄”做根更好一些。

 

下面是一段伪代码,createBranch方法用于创建决策树的分支,它是一个递归的结构。

createBranch(){

    检测数据集中的每个子项是否属于同一分类

    if  是同一分类{

       return 分类标签

    }else{

        寻找划分数据集的最好特征  

        划分数据集    

        创建分支节点        

        for 每个划分的子集{            

            调用函数createBranch并增加返回结果到分支节点中  

        } 

        return 分支节点

    } 

}

 

相关文章:

人工智能算法通俗讲解系列(一):K临近法

人工智能算法通俗讲解系列(二):逻辑回归

人工智能算法通俗讲解系列(三):决策树

© 著作权归作者所有

StanleySun
粉丝 24
博文 46
码字总数 44524
作品 0
技术主管
私信 提问
零基础自学人工智能,看这些资料就够了(300G资料免费送)

为什么有今天这篇? 首先,标题不要太相信,哈哈哈。 本公众号之前已经就人工智能学习的路径、学习方法、经典学习视频等做过完整说明。但是鉴于每个人的基础不同,可能需要额外的学习资料进行...

经济与编程
2018/08/17
0
0
算法|决策树算法究竟说的是什么?

作者简介 浩彬老撕,R语言中文社区特邀作者。 个人公众号:探数寻理 决策树算法概述

kmd8d5r
2018/05/10
0
0
“我爱智能”原创性博客索引

不知不觉,博客也写出了一点小体系,新的阶段已经开始,未来希望再接再厉继续补充这一体系,在成长中写博客,在博客中成长,在此先做一个小的梳理,谢谢大家的支持。 一)关于深度学习系列 ...

on2way
2015/08/29
0
0
ApacheCN 人工智能知识树 v1.0

Special Sponsors 贡献者:飞龙 版本:v1.0 最近总是有人问我,把 ApacheCN 这些资料看完一遍要用多长时间,如果你一本书一本书看的话,的确要用很长时间。但我觉得这是非常麻烦的,因为每本...

ApacheCN_飞龙
05/18
0
0
大白话5分钟带你走进人工智能 - 第二十二节决策树系列之概念介绍(1)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/LHWorldBlog/article/details/89854819 第二十二节决策树系列之概念介绍(1) 本系列我们讲一个新算法及其衍生出...

LHWorldBlog
05/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

centos7上部署dubbo管理控制台dubbo-admin

centos7上部署dubbo管理控制台dubbo-admin 1 准备工作 服务器:系统centos7, 内存4G, 存储60G, ip 192.168.159.128 软件环境: 安装有jdk1.8, 具体安装方式参见《centos7上安装jdk1.8》博...

flygrk
26分钟前
5
0
工作中一些原则体会

尽可能让一切变得简单,用最简单的方式完成工作 能用最少的概念,最精简易懂的概念模型来抽象系统,多一个概念就多一份别人了解系统以及维护系统的复杂度,别人也会质疑多一个概念的意义所在...

小强的进阶之路
30分钟前
5
0
Android -------- kotlin插件神器Json直接生成javaBean

这是一个data class从JSON字符串生成Kotlin 的插件,换句话说,是一个将JSON字符串转换为Kotlin data class(Json到Kotlin)的插件 在使用Kotlin进行开发的时候,我们需要经常对Json数据做解析...

切切歆语
55分钟前
31
0
1、Spring注解开发,第一天

第一天:Spring annotation开发 目录:1、@Configuration与@Bean给容器注册组件 2、@ConponentScan自动扫描注解 一、@Configuration与@Bean给容器注册组件 1、旧版本中创建配置文件和Bean //...

有一个小阿飞
今天
24
0
斯坦福博弈论笔记整理活动的任务已重新划分,望周知

参与方式:https://github.com/apachecn/stanford-game-theory-notes-zh/blob/master/CONTRIBUTING.md 整体进度:https://github.com/apachecn/stanford-game-theory-notes-zh/issues/1 项目......

ApacheCN_飞龙
今天
23
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部