文档介绍：分类与决策树
第一页，讲稿共九十一页哦
主要内容
分类与决策树概述
ID3、
CART
第二页，讲稿共九十一页哦
分类 VS. 预测
分类和预测是两种数据分析形式，用于提取描述重要数据类或预测未来的叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。
第十二页，讲稿共九十一页哦
决策树学****采用的是自顶向下的递归方法。
决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。
从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应着一组析取的规则。
决策树学****算法的最大优点是，它可以自学****在学****的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学****如果在应用中发现不符合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中。
第十三页，讲稿共九十一页哦
树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识，分枝用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。
决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束。
根结点
个子大
可能是松鼠
可能是老鼠
可能是大象
在水里
会吱吱叫
鼻子长
脖子长
个子小
不会吱吱叫
鼻子短
脖子短
可能是长颈鹿
在陆地上
可能是犀牛
可能是河马
第十四页，讲稿共九十一页哦
可以看到，一个决策树的内部结点包含学****的实例，每层分枝代表了实例的一个属性的可能取值，叶节点是最终划分成的类。如果判定是二元的，那么构造的将是一棵二叉树，在树中每回答一个问题就降到树的下一层，这类树一般称为CART（Classification And Regression Tree）。
判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IF…THEN”规则来实现。如图6-13的决策树可以转换成下规则：
IF “个子大” THEN
IF “脖子短” THEN
IF “鼻子长” THEN 可能是大象
形式化表示成
根结点
个子大
可能是松鼠
可能是老鼠
可能是大象
在水里
会吱吱叫
鼻子长
脖子长
个子小
不会吱吱叫
鼻子短
脖子短
可能是长颈鹿
在陆地上
可能是犀牛
可能是河马
第十五页，讲稿共九十一页哦
构造一棵决策树要解决四个问题：
收集待分类的数据，这些数据的所有属性应该是完全标注的。
设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。
分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。
设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂：
该节点包含的数据太少不足以分裂，
继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献，
树的深度过大不宜再分。
通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小最大的准则，这种方案使最具有分类潜力的准则最先被提取出来
第十六页，讲稿共九十一页哦
预测变量
目标变量
记录
样本
类标号属性
类别集合：Class={“优”，“良”，“差”}
决策树的基本原理
第十七页，讲稿共九十一页哦
根节点
叶子节点
分裂属性
分裂谓词
每一个叶子节点都被确定一个类标号
第十八页，讲稿共九十一页哦
每一个节点都代表了一个数据集。
根节点1代表了初始数据集D
其它节点都是数据集D的子集。
例如，节点2代表数据集D中年龄小于40岁的那部分样本组成的数据集。
子节点是父节点的子集。
If (年龄<40) and (职业=“学生” or职业=“教师”) Then 信用等级=“优”
If (年龄<40) and (职业!=“学生”and职业!=“教师”) Then 信用等级=“良”
If (年龄≥40) and (月薪<1000) Then 信用等级=“差”
If (年龄≥40) and (月薪≥1000 and月薪≤3000) Then 信用等级=“良”
If (年龄≥40) and (月