《数据挖掘计算》PPT课件

《《数据挖掘计算》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、决策树的学习如果学习的任务是对一个大的例子集作分类概念的归纳定义，而这些例子又都是用一些无结构的属性值对来表示，则可以采用示例学习方法的一个变种──决策树学习，其代表性的算法是昆兰（J.R.Quinlan，1986）提出的ID3。决策树(DecisionTree)一种描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。决策树学习是以实例为基础的归纳学习。从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。概念分类学习算法：来源于Hunt,Mari

2、n和Stone于1966年研制的CLS学习系统，用于学习单个概念。1979年,J.R.Quinlan给出ID3算法，并在1983年和1986年对ID3进行了总结和简化，使其成为决策树学习算法的典型。Schlimmer和Fisher于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。1988年，Utgoff在ID4基础上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan进一步发展了ID3算法，改进成C4.5算法。另一类决策树算法为CART，与C4.5不同的是，CART

3、的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。决策树学习采用的是自顶向下的递归方法。决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应

4、着一组析取的规则。决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。如果在应用中发现不符合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中。树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识，分枝用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种

5、约束条件满足而结束。根结点个子大可能是松鼠可能是老鼠可能是大象在水里会吱吱叫鼻子长脖子长个子小不会吱吱叫鼻子短脖子短可能是长颈鹿在陆地上可能是犀牛可能是河马可以看到，一个决策树的内部结点包含学习的实例，每层分枝代表了实例的一个属性的可能取值，叶节点是最终划分成的类。如果判定是二元的，那么构造的将是一棵二叉树，在树中每回答一个问题就降到树的下一层，这类树一般称为CART（ClassificationAndRegressionTree）。判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IF…THEN

6、”规则来实现。如图6-13的决策树可以转换成下规则：IF“个子大”THENIF“脖子短”THENIF“鼻子长”THEN可能是大象形式化表示成构造一棵决策树要解决四个问题：收集待分类的数据，这些数据的所有属性应该是完全标注的。设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂：该节点包含的数据太少不足以分裂，继续分裂数据集对树生成

7、的目标(例如ID3中的熵下降准则)没有贡献，树的深度过大不宜再分。通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小最大的准则，这种方案使最具有分类潜力的准则最先被提取出来证据由属性值对表示证据由固定的的属性和其值表示，如属性（温度），值（热）最简单的学习情况时每个属性拥有少量的不相关的值。目标函数有离散输出值决策树分配一个二值的树，很容易扩展成为多于两个的输出值。需要不相关的描述决策树原则上是表述不相关的表示容忍训练数据的错误对训练样本和表述样本的属性值的错误都有较强的鲁棒性。训练数据可以缺少值可以采用缺少属性值

8、的样本学习。（不是所有样本都有）基于决策树的概念表示决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类别。如，白化体动物的8个样本集合：事例动物种类身体颜色眼睛颜色白化体1兔棕