快速数据挖掘数据分析实战RapidMiner工具应用第11章-决策树与神经网络V1.1.pdfVIP

《RapidMiner数据分析与挖掘实战》第11章

第11章决策树与神经网络

11.1理解决策树

决策树方法在分类、预测、规则提取等领域有着广泛应用。在20世纪70年代后期和

80年代初期，机器学习研究者J.RossQuinilan提出了ID3[5-2]算法以后，决策树在机器学习、

数据挖掘邻域得到极大的发展。Quinilan后来又提出了C4.5，成为新的监督学习算法。1984

年几位统计学家提出了CART分类算法。ID3和ART算法大约同时被提出，但都是采用类

似的方法从训练样本中学习决策树。

决策树是一树状结构，它的每一个叶节点对应着一个分类，非叶节点对应着在某个属性

上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。对于非纯的叶节点，多

数类的标号给出到达这个节点的样本所属的类。构造决策树的核心问题是在每一步如何选择

适当的属性对样本做拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策

树是一个自上而下，分而治之的过程。

常用的决策树算法见表11-1。

表11-1决策树算法分类

决策树算法算法描述

其核心是在决策树的各级节点上，使用信息增益方法作为属性的选

ID3算法

择标准，来帮助确定生成每个节点时所应采用的合适属性。

C4.5决策树生成算法相对于ID3算法的重要改进是使用信息增益率

来选择节点属性。C4.5算法可以克服ID3算法存在的不足：ID3算

C4.5算法

法只适用于离散的描述属性，而C4.5算法既能够处理离散的描述属

性，也可以处理连续的描述属性。

CART决策树是一种十分有效的非参数分类和回归方法，通过构建

CART算法树、修剪树、评估树来构建一个二叉树。当终结点是连续变量时，

该树为回归树；当终结点是分类变量，该树为分类树。

本节将详细介绍ID3算法，也是最经典的决策树分类算法。

1.ID3算法简介及基本原理

ID3算法基于信息熵来选择最佳测试属性。它选择当前样本集中具有最大信息增益值的

231

《RapidMiner数据分析与挖掘实战》第11章

属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值就

将样本集划分为多少子样本集，同时决策树上相应于该样本集的节点长出新的叶子节点。

ID3算法根据信息论理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息

增益值度量不确定性：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶节点选

择信息增益最大的属性作为测试属性，这样可以得到当前情况下最纯的拆分，从而得到较小

的决策树。

m

设S是个数据样本的集合。假定类别属性具有个不同的值：C(i=1,2,...,m)。

s

i

设是类中的样本数。对一个给定的样本，它总的信息熵为

sC

ii

m

I(s,s,...,s)=-Plog(P)11-1

12måi2i（）