当前课程知识点:互联网大规模数据分析技术 >  第三章 分类算法 >  第6讲 决策树 >  第6讲 决策树

返回《互联网大规模数据分析技术》慕课在线视频课程列表

第6讲 决策树在线视频

下一节:第7讲 简单贝叶斯分类

返回《互联网大规模数据分析技术》慕课在线视频列表

第6讲 决策树课程教案、知识点、字幕

同学们好

欢迎来到

互联网大规模数据分析技术课堂

我是这节课的主讲教师张蕊

来自武汉理工大学

这节课我们一起来了解一下

分类的经典算法之决策树

那什么是决策树呢

决策树是一种类似树结构的分类器

由内部的决策结点

和终端的叶结点组成

决策结点表示在一个属性上的测试

叶结点存放一个类标签

弧或边表示由测试结果的输出

而形成的分支

路径表示一系列测试

从根结点开始沿着分支追踪到叶子结点

就可以做出最终的决策

下面我们来看一个决策树的例子

我们有一些顾客购买计算机的数据集

这个训练数据集的类标签

就是是否购买计算机buys_computer

最终形成的决策树是这样

根结点是对年龄进行判断

根结点下有3个分支

第一个分子是小于等于30

第二个分支是年龄在31和40间

第三个分支是年龄大于40

沿年龄小于等于30的分支走

将遇到判断是否为学生的决策结点

这个结点将产生两个分支

分别是yes和no

沿着student=no的分支将走到叶结点no

表示类标签buys_computer=no

也就是不购买电脑

沿着student=yes的分支将走到叶结点yes

表示类标签buys_computer=yes

也就是购买电脑

类似的

沿着年龄在31和40间的分支

将直接走到叶结点yes

而沿着年龄大于40的分支

将走到决策结点判断信用等级

如果信用等级是优秀将走到叶结点no

如果信用等级是一般

将走到叶结点yes

我们可以看到决策树类似流程图

很容易被理解

所以广受欢迎

那怎样得到这样的一棵决策树呢

决策树算法采用贪婪的思想

一般用自顶向下的、递归的

分而治之的方式来构造

开始所有的训练样本都在根结点

我们假定所有属性都是分类属性

这时构造的是分类树

然后

根据所选择的属性递归地进行划分

怎样去选择测试属性呢

可以根据直觉方法

或者是统计度量来进行选择

什么时候决策树就停止生长呢

有几种情况

1、如果某个结点的所有样本都属于同一类

2、不存在还可以继续划分的属性值了

3、没有剩余的样本数据了

这3种情况都没有办法继续往下划分了

决策树就停止生长了

实际上

决策树每个结点分裂时的度量

应该是来衡量数据的不纯度的

信息熵就是决策树构造中

常用的一个度量

它是由香农提出的

衡量信息不确定性的一个概念

有条件熵、相对熵等形式

在决策树构建中如何利用信息熵呢

简单来说就是先要计算

对整个数据集进行划分的

期望信息Expected info

也就是熵

然后计算某个属性

来划分当前这些样本数据的话

需要的期望信息是多少

原来对整个数据集

进行划分的所需的期望信息

减去

按这个属性对样本数据

进行划分的期望信息

得到的差是是信息增益info gain

我们希望选择划分后纯度最高

或者说不纯度最低的那个属性

也就是info gain最大的属性

这是对顾客是否购买计算机的数据集

采用信息增益的办法

来构造决策树的一个例子

开始我们对整个数据集计算期望信息

然后对属性age计算期望信息

I(9,5)表示所有14个样本数据中

有9个buys_computer=yes

有5个buys_computer=no

然后用熵的公式来计算

结果是0.940

对属性age来计算期望信息的时候

因为age的取值有3个

小于等于30、31和40间、大于40

而取值小于等于30的5个样本中

有2个buys_computer=yes

3个buys_computer=no

所以是I(2,3)

而取值小于等于30有5个样本

占14个样本的14分之5

所以是5/14* I(3,2)

类似的

可以计算取值为

31和40间、大于40的情况

然后得到关于age的期望信息是0.694

所以关于age的info gain是

关于整个数据集的期望信息减去

用age进行划分的期望信息

得出的结果是0.246

类似的,可以计算

income、student

credit_rating的info gain

是0.029 ,0.151,0.048

由于age的info gain最大

所以选择age来进行分裂

分裂属性还可以选择

Gain ratio、Gini index等

来评估不纯度

对于具体细节

感兴趣的同学可以查阅相关资料

在构建分类器时

常常会出现过拟合现象

指的是分类器过于拟合训练数据集

包括其中的特殊情况或异常

而这些异常

在通常的数据集当中并不出现

在决策树的构建过程中

也会出现过拟合

这时候决策树可能会

分支过多、层次过深

而且对未知数据准确率不高

对于过拟合的决策树

可以采取两种策略来进行剪枝

一种是前剪枝

前剪枝就是

当某些度量低于给定阈值时

认为这个划分或者分裂是不好的

从而提前停止树的构建

后剪枝就是

从生长完全的树剪去一些分支

通常用不同于训练集的数据集

来评估剪枝效果。

虽然看起来

前剪枝似乎比较省时间和空间

但实际上很难选择合适的阈值

因此,实际当中

后剪枝的效果更好、用得更多

对大规模数据集

构建决策树是一个很挑战的问题

因为仅仅训练数据

可能内存就无法放下

而如果频繁地在内存和磁盘间

进行数据交换

决策树的构建将会变得效率低下

那这时需要一种可伸缩的方法

来构造决策树

典型代表有RainForest和BOAT等

本节课的内容到此结束

谢谢大家的观看

互联网大规模数据分析技术课程列表:

第一章 大数据与数据挖掘概述

-第1讲 大数据与数据挖掘概述

--第1讲 大数据与数据挖掘概述

第二章 关联规则

-第2讲 频繁项集和关联规则的基本概念

--第2讲 频繁项集和关联规则的基本概念

-第3讲 Apriori算法

--第3讲 Apriori算法

-第4讲 Apriori算法的改进与兴趣度度量

--第4讲 Apriori算法的改进与兴趣度度量

第三章 分类算法

-第5讲 分类的基本概念

--第5讲 分类的基本概念

-第6讲 决策树

--第6讲 决策树

-第7讲 简单贝叶斯分类

--第7讲 简单贝叶斯分类

第四章 聚类算法

-第8讲 聚类的基本概念

--第8讲 聚类的基本概念

-第9讲 K-Means & K-Medoids Clustering

--第9讲 K-Means & K-Medoids Clustering

-第四章 聚类算法--习题

第五章 大数据平台与技术

-第10讲 大数据处理平台Hadoop

--第10讲 大数据处理平台Hadoop

-第11讲 MapReduce编程

--第11讲 MapReduce编程

-第12讲 大数据处理平台Spark

--第12讲 大数据处理平台Spark

-第13讲 NoSQL数据库

--第13讲 NoSQL数据库

第六章 信息检索

-第14讲 Web信息检索简介

--第14讲 Web信息检索简介

-第15讲 信息检索之倒排索引

--第15讲 信息检索之倒排索引

-第16讲 信息检索之TFIDF

--Video

-第17讲 信息检索之相似度排序

--第16讲 信息检索之TFIDF

第七章 Web链接分析

-第18讲 Web搜索之链接分析

--第18讲 Web搜索之链接分析

-第19讲 Web搜索之PageRank

--第19讲 Web搜索之PageRank

-第20讲 Lucene信息检索平台

--第20讲 Lucene信息检索平台

-第七章 Web链接分析--习题

第八章 推荐系统

-第21讲 推荐系统简介

--第21讲 推荐系统简介

-第22讲 推荐系统之协同过滤

--第22讲 推荐系统之协同过滤

-第23讲 Mahout数据挖掘平台

--第23讲 Mahout数据挖掘平台

-第24讲 信息过滤评价体系

--第24讲 信息过滤评价体系

-第八章 推荐系统--习题一

-第八章 推荐系统--习题二

自我提升练习

-综合编程题

第6讲 决策树笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。