热门标签 | HotTags
当前位置:  开发笔记 > 程序员 > 正文

决策树的原理与构建围绕一个实例展开

1.什么是决策树:决策树是一种预测模型,用来进行分类,是一种有监督学习。树中每个节点表示某个对象,而每个分叉路径则代表的某个

1. 什么是决策树:

    决策树是一种预测模型,用来进行分类,是一种有监督学习。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值


2 决策树实例(围绕一个例子)


    问题1. 基于表1中给出的训练集,给出分别使用极小熵和极大熵选择扩展属性所生成的两棵决策树。然后给出你对树的“大小”的理解,并按你的理解比较两种方法生成的决策树大小。



  问题1. 基于表1中给出的训练集,给出分别使用极小熵和极大熵选择扩展属性所生成的两棵决策树。然后给出你对树的“大小”的理解,并按你的理解比较两种方法生成的决策树大小。

(1) 极小熵生成决策树,设表1给的数据集为D,根据最大信息增益选择最优特征生成极小熵决策树,计算各特征A1、A2、A3、A4、A5对数据D的信息增益,统计结果为


 

 

 

class=1

class=2

 

D

 

 

8

7

H(D)= 0.9968

A1

D1

8

2

6

g(D,A1)=0.2880

D2

7

6

1

A2

D1

5

4

1

g(D,A2)=0.1398

D2

4

1

3

D3

6

3

3

A3

D1

3

1

2

g(D,A3)=0.0292

D2

12

7

5

A4

D1

7

6

1

g(D,A4)=0.2880

D2

8

2

6

A5

D1

6

5

1

g(D,A5)=0.4131

D2

4

0

4

D3

5

3

2


上表中的D1和D2,D3分别表示在各个特征中取值为1、2和3的样本子集,根据计算后统计在表格中的数据可得:

H(D)=-8/15*log2(8/15)—7/15*log2(7/15)=0.9968

g(D,A1)=H(D)-[8/15*H(D1)+7/15*H(D2)]=0.2880

g(D,A2)=H(D)-[5/15*H(D1)+4/15*H(D2)+6/15*H(D3)]=0.1398

g(D,A3)=H(D)-[3/15*H(D1)+12/15*H(D2)]=0.0292

g(D,A4)=H(D)-[7/15*H(D1)+8/15*H(D2)]=0.2880

g(D,A5)=H(D)-[6/15*H(D1)+4/15*H(D2)+5/15*H(D3)]=0.4131

根据上面的计算结果,特征A5的信息增益最大,所以选择A5为根节点。根据A5的取值将样本分成3个结合,S1={2,3,6,8,12,13},S2={1,5,7,14},S3={4,9,10,11,15}其中集合S2已全部属于同一个类,不需要再分,已成为叶子节点。对于集合S1,计算统计结果为:





class=1

class=2


D

 

 

5

1

H(D)=0.6500

A1

D1

1

1

0

G(D,A1)=0.0484

D2

5

4

1

A2

D1

3

2

1

G(D,A2)=0.1909

D2

1

1

0

D3

2

2

0

A3

D1

1

1

0

G(D,A3)=0.0484

D2

5

4

1

A4

D1

5

5

0

G(D,A4)=0.6500

D2

1

0

1


H(D)=0.6500 g(D,A1)= 0.0484 g(D,A2)= 0.1909 g(D,A3)= 0.0484 g(D,A4)=0.6500

     根据计算结果,集合S1选择A4为根结点。根据A4的取值,将S1集合划分为S11={3,6,8,12,13}  S12={2},集合S11和集合S12已成为叶节点。对于集合S3,计算统计结果为:


 

 

 

class 1

class 2

 

D

 

 

3

2

H(D)=0.9710

A1

D1

3

1

2

G(D,A1)=0.4200

D2

2

2

0

A2

D1

2

2

0

G(D,A2)=0.5710

D2

1

1

0

D3

2

1

1

A3

D1

0

0

0

G(D,A3)=0

D2

5

3

2

A4

D1

2

1

1

G(D,A4)=0.0200

D2

3

2

1


H(D)=0.9710 g(D,A1)=0.4200 g(D,A2)=0.5710  g(D,A3)=0 g(D,A4)=0.0200

根据计算结果,所以集合S3选择A2作为根结点,根据A2的取值将S3分成集合S31={4,11}集合S32={9}集合S33={10,15} 集合S32和集合S32已为叶子节点。对于集合S33,计算统计结果为


 

 

 

class 1

class 2

 

D

 

 

1

1

H(D)=1

A1

D1

1

0

1

G(D,A1)=1

D2

1

1

0

A3

D1

0

0

0

G(D,A3)=0

D2

2

1

1

A4

D1

2

1

1

G(D,A4)=0

D2

0

0

0


H(D)=1  g(D,A1)=1 g(D,A3)=0  g(D,A4)=0

     所以选择A1作为集合S33的根节点。根据A1的取值划分后的集合也都为叶子节点,至此极小熵决策树就建立起来了,如下图所示。

(2) 极大熵生成决策树,同上面的极小熵建立决策树类似,设表1中数据集为D。根据信息增益最小选择特征建立决策树。计算各特征A1、A2、A3、A4、A5对数据D的信息增益,统计结果为


 

 

 

class=1

class=2

 

D

 

 

8

7

H(D)= 0.9968

A1

D1

8

2

6

G(D,A1)= 0.2880

D2

7

6

1

A2

D1

5

4

1

G(D,A2)=0.1398

D2

4

1

3

D3

6

3

3

A3

D1

3

1

2

G(D,A3)= 0.0292

D2

12

7

5

A4

D1

7

6

1

G(D,A4)= 0.2880

D2

8

2

6

A5

D1

6

5

1

G(D,A5)=0.4131

D2

4

0

4

D3

5

3

2


  H(D)=0.9968g(D,A1)=0.2880 g(D,A2)=0.1398 g(D,A3)=0.0292 g(D,A4)=0.2880  g(D,A5)=0.4131

  根据上面计算结果,选择最小增益A3作为根结果。根据A3的取值,将集合划分S1={5,8,14},S2={1,2,3,4,6,7,9,10,11,12,13,15}.对于集合S1,计算统计结果为


 

 

 

class=1

class=2

 

D

 

 

1

2

H(D)=0.9183

A1

D1

2

0

2

G(D,A1)=0.9183

D2

1

1

0

A2

D1

1

1

0

G(D,A2)=0.9183

D2

1

0

1

D3

1

0

1

A4

D1

1

1

0

G(D,A4)= 0.9183

D2

2

0

2

A5

D1

1

1

0

G(D,A5)=0.9183

D2

2

0

2

D3

0

0

0


H(D)=0.9183 g(D,A1)=0.9183 g(D,A2)=0.9183 g(D,A4)=0.9183 g(D,A5)=0.9183

根据计算结果,选择A1或A2或A4或A5都可以作为集合S1的根节点,这里不妨选择A1作为根节点,根据A1的取值将S1划分成S11={5,14} ,S12={8},此时S11和S12已经为叶节点不需要在划分。

对于集合S2,计算统计结果为


 

 

 

class=1

class=2

 

D

 

 

7

5

H(D)=0.9799

A1

D1

6

2

4

G(D,A1)= 0.1957

D2

6

5

1

A2

D1

4

3

1

G(D,A2)=0.0753

D2

3

1

2

D3

5

3

2

A4

D1

6

5

1

G(D,A4)=0.1957

D2

6

2

4

A5

D1

5

4

1

G(D,A5)= 0.2745

D2

2

0

2

D3

5

3

2


H(D)=0.9799 g(D,A1)=0.1957 g(D,A2)=0.0753 g(D,A4)=0.1957 g(D,A5)=0.2745

根据计算结果,选择A2作为集合S2的根节点,根据A2的取值将集合S2划分为S21={2,4,6,11},S22={7,9,12},S23={1,3,10,13,15},对于集合S21,计算统计结果为


 

 

 

class=1

class=2

 

D

 

 

3

1

H(D)=0.8113

A1

D1

1

1

0

G(D,A1)=0.1226

D2

3

2

1

A4

D1

1

1

0

G(D,A4)=0.1226

D2

3

2

1

A5

D1

2

1

1

G(D,A5)=0.3113

D2

0

0

0

D3

2

2

0


H(D)=0.8113  g(D,A1)=0.1226  g(D,A4)=0.1226  g(D,A5)=0.3113

根据计算结果,选择A1和A4作为S21的根节点都可以,这里不妨选A1为S21的根节点。根据A1的取值将S21划分为S211={11},S212={2,4,6},其中S211已为叶节点。对于集合S212,计算统计结果为


 

 

 

class=1

class=2

 

D

 

 

2

1

H(D)=0.9183

A4

D1

1

1

0

G(D,A4)=0.2516

D2

2

1

1

A5

D1

2

1

1

G(D,A5)=0.2516

D2

0

0

0

D3

1

1

0


H(D)=0.9183  g(D,A4)=0.2516  g(D,A5)=0.2516

根据计算结果,选择A4和A5作为S212的根节点都可以,这里不妨选A4作为根节点。根据A4的取值将集合S212划分为S2121={6}  S2122={2,4};对于集合S2122选择A5作为根节点,根据A5的取值将集合S2122划分为S21221={2}  S21223={4};此时集合S2121和集合S21221,S21223都为叶节点,对于集合S22,计算统计结果为


 

 

 

class=1

class=2

 

D

 

 

1

2

H(D)= 0.9183

A1

D1

2

0

2

G(D,A1)=0.9183

D2

1

1

0

A4

D1

1

1

0

G(D,A4)=0.9183

D2

2

0

2

A5

D1

1

1

0

G(D,A5)=0.9183

D2

1

0

1

D3

1

0

1


H(D)=0.9183  g(D,A1)=0.9183  g(D,A4)=0.9183  g(D,A5)=0.9183

根据计算结果,选择A1或A4或A5作为根节点都可以,这里选择A1作为根节点。根据A1的取值将集合S22划分为S221={12},S222={7,9} 此时,S221和S222已为叶节点。对于集合S23,计算统计结果为


 

 

 

class=1

class=2

 

D

 

 

3

2

H(D)=0.9710

A1

D1

3

1

2

G(D,A1)=0.4200

D2

2

2

0

A4

D1

4

3

1

G(D,A4)=0.3220

D2

1

0

1

A5

D1

2

2

0

G(D,A5)=0.5710

D2

1

0

1

D3

2

1

1


H(D)=0.9710  g(D,A1)=0.4200  g(D,A4)=0.3220  g(D,A5)=0.5710

根据计算结果,选择A4作为根节点。根据A4的取值将S23划分为S231={3,10,13,15},S232={1}.对集合S231,计算统计结果为


 

 

 

class=1

class=2

 

D

 

 

3

1

H(D)=0.8113

A1

D1

2

1

1

G(D,A1)= 0.3113

D2

2

2

0

A5

D1

2

2

0

G(D,A5)= 0.3113

D2

0

0

0

D3

2

1

1


H(D)=0.8113  g(D,A1)=0.3113  g(D,A5)=0.3113

根据计算结果,选择A1或A5作为S231的根节点都可以,这里选择A1作为其根节点,根据A1的取值将集合S231划分为S2311={3,10},S2312={13,15}。集合S2311选择A5作为根节点,将集合S2311划分为S23111={3} , S23113={10}。至此极大熵决策树就可以建立起来了,如下图所示



3.  拓展

     利用极小熵生成的决策树不一定是“最小决策树”。因为用极小熵生成的决策树可能存在过拟合,对训练数据分类很好,但对测试数据不一定好。一般需要对生成的决策树做剪枝处理,减掉过于细分的叶节点。使其退回到父节点,然后将父节点改为新的叶节点。







推荐阅读
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 本文介绍如何解决在 IIS 环境下 PHP 页面无法找到的问题。主要步骤包括配置 Internet 信息服务管理器中的 ISAPI 扩展和 Active Server Pages 设置,确保 PHP 脚本能够正常运行。 ... [详细]
  • PHP 5.2.5 安装与配置指南
    本文详细介绍了 PHP 5.2.5 的安装和配置步骤,帮助开发者解决常见的环境配置问题,特别是上传图片时遇到的错误。通过本教程,您可以顺利搭建并优化 PHP 运行环境。 ... [详细]
  • 本文将详细介绍如何使用剪映应用中的镜像功能,帮助用户轻松实现视频的镜像效果。通过简单的步骤,您可以快速掌握这一实用技巧。 ... [详细]
  • 1.如何在运行状态查看源代码?查看函数的源代码,我们通常会使用IDE来完成。比如在PyCharm中,你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢?当我们想使用一个函 ... [详细]
  • 数据管理权威指南:《DAMA-DMBOK2 数据管理知识体系》
    本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释,构建了数据管理的总体框架,为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]
  • 本文详细介绍了Java中org.eclipse.ui.forms.widgets.ExpandableComposite类的addExpansionListener()方法,并提供了多个实际代码示例,帮助开发者更好地理解和使用该方法。这些示例来源于多个知名开源项目,具有很高的参考价值。 ... [详细]
  • 解决PHP与MySQL连接时出现500错误的方法
    本文详细探讨了当使用PHP连接MySQL数据库时遇到500内部服务器错误的多种解决方案,提供了详尽的操作步骤和专业建议。无论是初学者还是有经验的开发者,都能从中受益。 ... [详细]
  • Java内存管理与优化:自动与手动释放策略
    本文深入探讨了Java中的内存管理机制,包括自动垃圾回收和手动释放内存的方法。通过理解这些机制,开发者可以更好地优化程序性能并避免内存泄漏。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • DNN Community 和 Professional 版本的主要差异
    本文详细解析了 DotNetNuke (DNN) 的两种主要版本:Community 和 Professional。通过对比两者的功能和附加组件,帮助用户选择最适合其需求的版本。 ... [详细]
  • Python自动化处理:从Word文档提取内容并生成带水印的PDF
    本文介绍如何利用Python实现从特定网站下载Word文档,去除水印并添加自定义水印,最终将文档转换为PDF格式。该方法适用于批量处理和自动化需求。 ... [详细]
  • 尽管某些细分市场如WAN优化表现不佳,但全球运营商路由器和交换机市场持续增长。根据最新研究,该市场预计在2023年达到202亿美元的规模。 ... [详细]
  • 本文深入探讨了Linux系统中网卡绑定(bonding)的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡,实现网络冗余、带宽聚合和负载均衡,在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
author-avatar
小TMM_
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有