过度拟合（overfitting）：如果决策树对训练样本的特征 描述得“过于精确”，无法实现对新样本的合理分析，所以此时它 不是一棵分析新数据的最佳决策树。一棵完全决策树能非常准确地 反映训练集中数据的特征，但因失去了一般代表性而无法用于对新 数据的分类或预测，这种现象一般称为“过拟合”。
母亲：26。
女儿：长的帅不帅？ (长相)
母亲：挺帅的。
女儿：收入高不？ (收入情况)
母亲：不算很高，中等情况。
女儿：是公务员不？ (是否公务员)
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
1.1.2 决策树与if-then规则
由决策树的根结点到叶结点的每一条路径 构建一条规则；
路径上内部结点的特征对应着规则的条件 ，而叶结点的类对应着规则的结论。
信贷情 况 一般 好 好 一般 一般 好 好
14 老年 是 非常好
15 老年 否 表2 一般
类别
否 否 是 否 否 否 是 是 否

有自己的
是
否房子
是
ID 3 13
年龄 青年 老年
是
信贷情况 好 好
类别 是 是
有工作
否
ID 年龄 信贷情况 类别
1 青年 一般 否
2 青年
好
否
14 老年 非常好 是
决策树学习算法的特点
决策树学习算法的最大优点是，它可以自学习 。在学习的过程中，不需要使用者了解过多背景知识 ，只需要对训练实例进行较好的标注，就能够进行学 习。
显然，它属于有监督学习。 从一类无序、无规则的事物(概念)中推理出决策树 表示的分类规则。
决策树学习的主要算法
建立决策树的关键，即在当前状态下选择哪 个属性作为分类依据。根据不同的目标函数，建 立决策树主要有一下三种算法。
决策树
根据李峰等人的PPT改编 课件主要依据李航编写的《统计学 习方法》编制，清华大学出版社 另一本参考书：《数据挖掘与数学
建模》国防工业出版社 2010
决策树
1.1 决策树模型与学习 1.2 特征选择 1.3 决策树的生成 1.4 决策树的剪枝 1.5 CART算法
1.1 决策树模型与学习
If-then规则集合的一重要性质：互斥并且 完备
1.1.3 决策树与条件概率分布
将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的 概率分布就构成了一个条件概率分布。
各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较 大，决策树分类时将该结点的实例强行分到条件概率大的那一类去。
ID3 （J. Ross Quinlan-1975）核心：信息熵 C4.5—ID3的改进，核心：信息增益比 CART（Breiman-1984），核心：基尼指数
例1. 找对象
决策树分类的思想类似于找对象。现想 象一个女孩的母亲要给这个女孩介绍男朋 友，于是有了下面的对话：

女儿：多大年纪了？ (年龄)
非常好
是
10
中年
否
是
非常好
是
11
老年
否
是
非常好
是
12
老年
否
是
好
是
13
老年
是
否
好
是
14
老年
是
否
非常好
是
15
老年
否
否
一般
否
1.2.2 信息增益

熵-就分类而言，所有成员都属于一类，熵为零；不同类别
数目相等，则熵等于1，类别数目不等，则熵介于0,1之间。

条件

信息增益算法
1.2 特征选择
1.2.1 特征选择问题
特征选择在于选取对训练数据具有分类能 力的特征。
如何判断一个特征对于当前数据集的分类 效果？ 也即确定选择特征的准则。
例1.2 右表是一个由15个样 本组成的贷款申请训练数据 。数据包括贷款申请人的四 个特征。表的最后一列是类 别，是否同意贷款，取2个值 ：是、否。
希望通过所给的训练数据学 习一个贷款申请的决策树， 用以对未来的贷款申请进行 分类。
特征选择是决定用哪个特征 来划分特征空间。
ID
年龄
有工作 有自己的 信贷情况 类别
房子
1
青年
否
否
一般
否
2
青年
否
否
好
否
3
青年
是
否
好
是
4
青年
是
是
一般
是
5
青年
否
否
一般
否
6
中年
否
否
一般
否
7
中年
否
否
好
否
8
中年
是
是
好
是
9
中年
否
是
1.1.4 决策树学习

1.1.4 决策树学习
目标：我们需要的是一个与训练数据矛盾 较小的决策树，同时具有很好的泛化能力 。
决策树学习的损失函数：（通常是）正则 化的极大似然函数。但是基于损失函数找 到全局最优决策树是NP-完全问题。
现实中决策树学习通常采用启发式方法， 即局部最优。
有自己的房 子(A3)
是
否
ID 年龄 有工作 信贷情况 类 别
4 青年 是
一般 是
8 中年 是
好是
9 中年 否 非常好 是
10 中年 否 非常好 是
11 老年 否 非常好 是
12 老年 都
好是
表1
ID 年龄 有工作
1 青年 否 2 青年 否 3 青年 是 5 青年 否 6 中年 否 7 中年 否 13 老年 是
5 青年 一般 否
表3
6 中年 一般 否
7 中年
好
否
这里生成的决策树只用到两个特征 （两个内节点），ID3算法容易存在过
15 老年 一般 否
表4
拟合问题。
补充：如何解决决策树的过拟合问题
概念
什么是过度拟合数据
原因
过度拟合数据是怎么产生的
解决
怎么去解决这个问题
补充：如何解决决策树的过拟合问题——概念

例1.3 对表1.1所给的训练数据集IDD, 根据信息增益准则选择最优特征。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
年龄
青年 青年 青年 青年 青年 中年 中年 中年 中年 中年 老年 老年 老年 老年 老年
有工作
否 否 是 是 否 否 否 是 否 否 否 否 是 是 否
有自己 的房子
否 否 否 是 否 否 否 是 是 是 是 是 否 否 否
信贷情 况 一般 好 好 一般 一般 一般 好 好
非常好 非常好 非常好
好 好 非常好 一般
类别
否 否 是 是 否 否 否 是 是 是 是 是 是 是 否
1.2.3 信息增益比

1.3 决策树的生成
1.3.1 ID3算法

例1.4 对表1.1的训练数据集，利用ID3算法建立决策树
1.1.1 决策树模型 1.1.2 决策树与if-then规则 1.1.3 决策树与条件概率分布 1.1.4 决策树学习
1.1.1 决策树模型
什么是决策树？
定义1.1（决策树） 分类决策树模型是一种描述 对实例进行分类的树形结构。决策树由结点和有 向边组成。结点有两种类型：内部结点和叶节点 。内部结点表示一个特征或属性，叶节点表示一 个类。