文档介绍：决策树
决策树模型与学****br/> 特征选择
决策树的生成
决策树的剪枝
CART算法
第一页，共65页。
决策树模型与学****br/> 决策树模型
决策树与if-then规则
决策树与条件概率分布
决策树学****br/>第二页，共65页。
决策树模型
什么是决策树？
（决策树） 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。
第三页，共65页。
决策树学****算法的特点
决策树学****算法的最大优点是，它可以自学****在学****的过程中，不需要使用者了解过多背景知识，只需要对训练实例进行较好的标注，就能够进行学****br/>显然，它属于有监督学****br/>从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。
第四页，共65页。
决策树学****的主要算法
建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有一下三种算法。
ID3 （J. Ross Quinlan-1975）核心：信息熵
—ID3的改进，核心：信息增益比
CART（Breiman-1984），核心：基尼指数
第五页，共65页。
例1. 找对象
决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
  女儿：多大年纪了？ (年龄)       母亲：26。       女儿：长的帅不帅？ (长相)       母亲：挺帅的。       女儿：收入高不？ (收入情况)       母亲：不算很高，中等情况。       女儿：是公务员不？ (是否公务员)       母亲：是，在税务局上班呢。       女儿：那好，我去见见。
第六页，共65页。
决策树与if-then规则
由决策树的根结点到叶结点的每一条路径构建一条规则；
路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
If-then规则集合的一重要性质：互斥并且完备
第七页，共65页。
决策树与条件概率分布
将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。
各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较大，决策树分类时将该结点的实例强行分到条件概率大的那一类去。
第八页，共65页。
决策树学****br/>第九页，共65页。
决策树学****br/>目标：我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。
决策树学****的损失函数：（通常是）正则化的极大似然函数。但是基于损失函数找到全局最优决策树是NP-完全问题。
现实中决策树学****通常采用启发式方法，即局部最优。
具体做法：每次选择feature时，都挑选择当前条件下最优的那个feature作为划分规则，即局部最优的feature。
第十页，共65页。