资源描述：
《数据挖掘与知识发现(讲稿4---决策树学习技术)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据挖掘与知识发现（讲稿4---决策树学习技术）i数据挖掘与知识发现讲稿主讲：刘以安第四章决策树（decisiontree）决策树也是归纳学习中常用的一种知识表示形式，常用于分类。同时，也是发现概念描述空间的一种有效方法。决策树的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。教学目的：掌握决策树学习的概念重点掌握TD3学习算法以及决策树的构造TMR前常用的决策树改进方法4.1概念描述空间的归纳学习归纳学习旨在从人量的经验数据中归纳抽取出一般的规则和模式，因而成为知识秋取的主要手段，在专家系统、模式识别、图像处理、语音识别等领域都有重要应用。归纳学习是机器学习最核心、最成熟的
2、分支。［示例］数字识别应用：假设有三类数字，即0,1,2。每类有两个例子，每个例子有四个属性扌山述，即孔数（#hole）、端点数（#end）、交叉点数（#cross）、右上弧数（#right-arc）。如表所示。町归纳产生三类数字的如下规则：0类：[#hole二1][#ctoss=0]1类:[#hole=0][#right-arc=O]2类：[#end=2][#right-arc=l]归纳学习是符号学习屮研究得最为广泛的一种方法。思想是：给定关于某个概念的一•系列已知的正例和反例，从中归纳出一个通用的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。它的一般操作1
3、i数据
4、挖掘与知识发现讲稿主讲：刘以安是泛化和特化.泛化川来扩展某一假设的语义信息，使其能包含更多的正例，应用于更多的情况；特化是泛化的相反操作，用于限制概念描述的应用范围。［示例］假设我们被要求从一副扑克牌中选择一张牌，如果选到好牌就可以获奖。已知前面被抽出的牌冇：梅花4、梅花7、黑桃2、红桃5和黑桃J,其中前三张都获奖，后两张没有获奖。试用归纳学习帮助选择能获奖的好牌。解：取纸牌的一组属性：VI—-花色(Suit)和阶V2一-(Rank),如:梅花4显然,纸牌的示例空间VIV2就是所有牌的集合。它是由属性Suit和Rank所定义的，其屮，属性V1,V2的观察值集合为：VI｛clubs,sp
5、ade,d梅花、黑桃、方块、红桃siamon,dhsear｝tsV2｛1,2,3,4,5,6,7,8,9,10,J,Q,K｝每个示例就是单张牌。设X是一组确定属性决定的示例空间(如，VIV2)；II是处义在X上的假设空间(如，11二｛梅花4、梅花7、黑桃2、红桃5和黑桃J｝),也就是用X的属性按一定的逻辑形式定义的-•组概念。Q是定义在X上的目标概念c的示例有限集，我们定义Q的描述空间是由H中适合Q的全部示例的假设构成的集合。如果示例空间是冇限的，且口标概念c是H的成员。当新的示例添加到Q中时，Q描述空间将收缩，最终直到仅包含FI标概念c,这时称描述空间被穷尽。对描述空间可以用描述图來
6、表示，它是一个无冋路的有向图，其屮各节点是描述空间的元索。如果从节点pfOq有一条弧，当目-仅当下而两条性质成立：P比q特殊；不存在节点「它比p普遍，比q特殊。取PE=｛梅花4、梅花7、黑桃2｝为止例；NE=｛红桃5和黑桃J｝为反例。这样对，梅花4是肯定示例，其描述图为梅花4构战的樹述田梅花丁添加后的福述田a这里，c一clubs;bblack;nnum;aany-suit或any-rank。图中从左到右表示suit从特殊到普遍，垂直方向从卜•到上表示Rank从特殊到普遍；ba表示的概念为(suitblack)(Rankanyrank),即所有黑色的牌。i数据挖掘与知识发现讲稿主讲：刘以
7、安这时增加新的示例，如梅花7,能修剪描述空间。删除三个涉及阶是4的概念，因为它们不能覆盖该肯定示例，得到新的描述图。同理，由否定示例红桃5可修剪掉aa和购，因为这两个概念覆盖该否定示例；肯定示例黑桃2剪掉梅花，最后由否定示例黑桃J将描述空间缩小到单个概念bn,即黑色数字牌。4.2决策树学习决策树是川样木的属性作为结点，川属性的取值作为分支的树结构。它是利川信息论原理对大量样本的属性进行分析和归纳而产生的。决策树的根结点是所有样本信息小信息量最人的属性。屮间结点是以该结点为根的子树所包含的样本子集屮信息量最人的属性。决策树的叶结点是样木的类别值。决策树学习是以实例为基础的归纳学习算法。它
8、着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递推方式，在决策树的内部结点进彳亍属性值的比较并根据不同的属性值判断从该结点向下的分枝，在决策树的叶结点得到结论。所以，从根结点到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。决策树的内部结点是属性或属性集，称为测试属性；叶结点是所要学习划分的类。先用训练实例集产生决策树，然后用其对未知实例集进行分类。对实例进行分类时，由树根开始对该
