决策树分类
王成（副教授）
计算机科学与技术学院
主要内容
什么是决策树
ID3算法
算法改进算法
CART算法
Decision Tree ModelingDecision Tree Modeling
决策树是一种简单且应用广泛的决策树是一种简单且应用广泛的预测预测方法方法
决策树
图 常见的决策树形式
·决策树主要有二元分支（binary split）树和多分支（multiway split）树。
一般时候采用二元分裂，因为二元分裂在穷举搜索中更加灵活。
决策树形式
决策树
决策树（Decision Tree）又称为判定树，是运用于分类的
一种树结构。其中的每个内部结点（internal node）代表
对某个属性的一次测试，每条边代表一个测试结果，叶结
点（leaf）代表某个类（class）或者类的分布（class
distribution），最上面的结点是根结点
决策树提供了一种展示在什么条件下会得到什么类别这类
规则的方法。
下例是为了解决这个问题而建立的一棵决策树，从中可以
看到决策树的基本组成部分：决策结点、分支和叶结点
决策树
下图给出了一个商业上使用的决策树的例子。它表示了一
个关心电子产品的用户是否会购买PC（buys_computer）的
知识，用它可以预测某条记录（某个人）的购买意向
决策树
这棵决策树对销售记录进行分类，指出一个电子产品消费
者是否会购买一台计算机“buys_computer”。每个内部结
点(方形框)代表对某个属性的一次检测。每个叶结点(椭圆
框)代表一个类:
buys_computers=yes 或者 buys_computers=no
在这个例子中，特征向量为：
(age, student, credit_rating, buys_computers)
被决策数据的格式为:
(age, student, credit_rating)
输入新的被决策的记录，可以预测该记录隶属于哪个类。
使用决策树进行分类
第1步：利用训练集建立并精化一棵决策树，建立决策树模
型。这个过程实际上是一个从数据中获取知识，进行机器
学习的过程
第2步：利用生成完毕的决策树对输入数据进行分类。对输
入的记录，从根结点依次测试记录的属性值，直到到达某
个叶结点，从而找到该记录所在的类
主要内容
什么是决策树
ID3算法
算法改进算法
CART算法
如何从训练数据中学习决策树?
ID Age Has-job Own_house Credit_rating Class
1 Young False False Fair No
2 Young False False Good No
3 Young True False Good Yes
4 Young True True Fair Yes
5 Young False False Fair No
6 Middle False False Fair No
7 Middle False False Good No
8 Middle True True Good Yes
9 Middle False True Excellent Yes
10 Middle False True Excellent Yes
11 Old False True Excellent Yes
12 Old False True Good Yes
13 Old True False Good Yes
14 Old True False Excellent Yes
15 Old False False fair no
贷款申请数据集
如何从训练数据中学习决策树?
Age？
young
middle
old
No:3
Yes:2
No:2
Yes:3
No:4
Yes:1
Own_house？
true false
No:0
Yes:6
No:6
Yes:3
(a) (b)
两种可能的根节点选取方式
哪种更好？
ID3算法
ID3算法主要针对属性选择问题
使用信息增益度选择测试属性
ID3决策树建立算法
1 决定分类属性集合；
2 对目前的数据表，建立一个节点N
3 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上
标出所属的类(纯的类别)
4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少
数服从多数的原则在树叶上标出所属类别(不纯的类别)
5 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作
为节点N的测试属性
6 节点属性选定后，对于该属性中的每个值：
从N生成一个分支，并将数据表中与该分支有关的数据收集形
成分支节点的数据表，在表中删除节点属性那一栏
7如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树
信息熵 (Entropy)
我们常说信息很多，或信息很少，但却很难说清楚信息到
底有多少
比如一本50多万字的《史记》有多少信息量？或一套莎士
比亚全集有多少信息量？
这个问题几千年来都没有人给出很好的解答，直到1948年，
香农(Claude Shannon)在他著名的论文“通信的数学原理
”中提出了信息熵的概念，才解决了信息的度量问题，并
且量化出信息的作用
信息熵 (Entropy)
一条信息的信息量和它的不确定性有着直接的关系
比如，要搞清楚一件非常不确定的事，或是我们一无所知
的事情，就需要了解大量信息。相反，如果我们对某件事
已经有了较多了解，那么不需要太多信息就能把它搞清楚
从这个角度看，信息量就等于不确定性的多少
如何量化信息的度量呢？
信息熵 (Entropy)
假如我错过了一个有32支球队参加的足球赛，赛后我问一
个知道比赛结果的观众“哪支球队是冠军”？他不愿意直
接告诉我，而让我猜，每猜一次，他要收一元钱才肯告诉
我是否猜对，那我需要付多少钱才能知道谁是冠军呢？
我可以把球队编号，从1到32，然后问“冠军球队在1-16号
中吗？”，假如他告诉我猜对了，我就接着问“冠军在1-8
号中吗？”，假如他说猜错了，那我就知道冠军在9-16号
中。这样只要5次，我就能知道哪支球队是冠军
当然，香农不是用钱，而是用比特(bit)来度量信息量，在
上例中，这条消息的信息量是5比特
信息量的比特数和所有可能
情况的对数有关，例如本例
中，信息量 = log (球队数)，
即 5 = log (32)
信息熵 (Entropy)
实际上可能不需要5次就能猜出谁是冠军，因为一些强队得
冠的可能性更高，因此第一次猜测时可以把少数几支强队
分成一组，其它球队分成另一组，然后猜冠军球队是否在
那几支强队中
这样，也许三次或四次就能猜出结果。因此，当每支球队
夺冠的可能性(概率)不等时，这条信息的信息量比5比特少
香农指出，它的准确信息量应该是
p1,p2,...,p32分别是这32支球队夺冠概率，香农把它称作信息熵，单位为比特；
可以算出，当32支球队夺冠概率相同时，对应的信息熵为5比特。
信息熵 (Entropy)
对于任意一个随机变量X(比如夺冠球队)，它的熵定义为
变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大
数据集的信息熵
设数据集D中有m个不同的类C1, C2, C3, ..., Cm
设 Ci,D是数据集D中Ci类的样本的集合, |D|和 |Ci,D|分别是D和 Ci,D中的样本个数
其中pi是数据集D中任意样本属于类Ci的概率，用 估计
数据集D的信息熵:
例: 计算对下列数据集分类所需的信息熵
年龄 收入 学生 信用 买了电脑
<30 高 否 一般 否
<30 高 否 好 否
30-40 高 否 一般 是
>40 中等 否 一般 是
>40 低 是 一般 是
>40 低 是 好 否
30-40 低 是 好 是
<30 中 否 一般 否
<30 低 是 一般 是
>40 中 是 一般 是
<30 中 是 好 是
30-40 中 否 好 是
30-40 高 是 一般 是
>40 中 否 好 否
|D|=14
|C1,D|=5
|C2,D|=9
使用熵衡量数据纯度
假设有一个数据集合D，其中只有两个类，一个是正例类，一个是负例类
计算D中正例类和负例类在三种不同的组分下熵的变化情况。
（1）D中包含有50%的正例和50%的负例。
H(D) = * - * = 1
（2）D中包含有20%的正例和80%的负例。
H(D) = * - * =
（3）D中包含有100%的正例和0%的负例。
H(D) = -1 * log21 - 0 * log20 =0
可以看到一个趋势，当数据变得越来越“纯”时，熵的值变得越来越小。
当D中正反例所占比例相同时，熵取最大值。
当D 中所有数据都只属于一个类时，熵得到最小值。
因此熵可以作为数据纯净度或混乱度的衡量指标。这正是决策树学习中
需要的。
数据集的信息熵
假设按属性 A 划分 D 中的样本，且属性 A 根据训练数据的观测具有 v
个不同取值{ a1, a2, ..., aj , ..., av }。
如果 A 是离散值，可依属性 A 将 D 划分为 v 个子集 { D1, D2, ..., Dj
, ..., Dv }
其中，Dj为D中的样本子集，它们在A上具有属性值aj
这些划分将对应于从该节点A出来的分支。
按属性A对D划分后，数据集的信息熵:
其中， 充当第 j 个划分的权重。
InfoA(D)越小，
表示划分的纯度越高
信息增益
选择具有最高信息增益Gain(A)
的属性A作为分裂属性
按照能做“最佳分类”的属性A划分，
使完成样本分类需要的信息量最小
确定第一次分裂的属性：按年龄划分
年龄 收入 学生 信用 买了电脑
<30 高 否 一般 否
<30 高 否 好 否
30-40 高 否 一般 是
>40 中等 否 一般 是
>40 低 是 一般 是
>40 低 是 好 否
30-40 低 是 好 是
<30 中 否 一般 否
<30 低 是 一般 是
>40 中 是 一般 是
<30 中 是 好 是
30-40 中 否 好 是
30-40 高 是 一般 是
>40 中 否 好 否
年龄<30的有5个, 其中3个为“否”
年龄30-40的有4个, 其中0个为“否”
年龄>40的有5个, 其中2个为“否”
Info年龄(D)
Gain(年龄)
= Info(D) - Info年龄(D)
= - =
确定第一次分裂的属性：按收入划分
年龄 收入 学生 信用 买了电脑
<30 高 否 一般 否
<30 高 否 好 否
30-40 高 否 一般 是
>40 中 否 一般 是
>40 低 是 一般 是
>40 低 是 好 否
30-40 低 是 好 是
<30 中 否 一般 否
<30 低 是 一般 是
>40 中 是 一般 是
<30 中 是 好 是
30-40 中 否 好 是
30-40 高 是 一般 是
>40 中 否 好 否
收入=高的有4个, 其中2个为“否”
收入=中的有6个, 其中2个为“否”
收入=低的有4个, 其中1个为“否”
Info收入(D)
Gain(收入)
= Info(D) - Info收入(D)
= - =
确定第一次分裂的属性：按学生划分
年龄 收入 学生 信用 买了电脑
<30 高 否 一般 否
<30 高 否 好 否
30-40 高 否 一般 是
>40 中 否 一般 是
>40 低 是 一般 是
>40 低 是 好 否
30-40 低 是 好 是
<30 中 否 一般 否
<30 低 是 一般 是
>40 中 是 一般 是
<30 中 是 好 是
30-40 中 否 好 是
30-40 高 是 一般 是
>40 中 否 好 否
是学生的有7个, 其中1个为“否”
不是学生的有7个, 其中4个为“否”
Info学生(D)
Gain(学生)
= Info(D) - Info学生(D)
= - =
确定第一次分裂的属性：按信用划分
年龄 收入 学生 信用 买了电脑
<30 高 否 一般 否
<30 高 否 好 否
30-40 高 否 一般 是
>40 中 否 一般 是
>40 低 是 一般 是
>40 低 是 好 否
30-40 低 是 好 是
<30 中 否 一般 否
<30 低 是 一般 是
>40 中 是 一般 是
<30 中 是 好 是
30-40 中 否 好 是
30-40 高 是 一般 是
>40 中 否 好 否
信用好的有6个, 其中3个为“否”
信用一般的有8个, 其中2个为“否”
Info信用(D)
Gain(信用)
= Info(D) - Info信用(D)
= - =
收入 学生 信用 买了电脑
高 否 一般 否
高 否 好 否
中 否 一般 否
低 是 一般 是
中 是 好 是 收入 学生 信用 买了电脑
高 否 一般 是
低 是 好 是
中 否 好 是
高 是 一般 是
确定第一次分裂的属性
收入 学生 信用 买了电脑
中 否 一般 是
低 是 一般 是
低 是 好 否
中 是 一般 是
中 否 好 否
年龄
<30
30-40
>40
“年龄”属性具体最高
信息增益，成为分裂属性
收入 学生 信用 买了电脑
高 否 一般 否
高 否 好 否
中 否 一般 否
低 是 一般 是
中 是 好 是
Info收入(D)
= 2/5 * (-2/2 * log2/2 - 0/2 * log0/2)
+ 2/5 * (-1/2 * log1/2 - 1/2 * log1/2)
+ 1/5 * (-1/1 * log1/1 - 0/1 * log0/1)
=
Info学生(D)
= 3/5 * (-3/3 * log3/3 - 0/3 * log0/3)
+ 2/5 * (-2/2 * log2/2 - 0/2 * log0/2)
= 0
Info信用(D)
= 3/5 * (-2/3 * log2/3 - 1/3 * log1/3)
+ 2/5 * (-1/2 * log1/2 - 1/2 * log1/2)
=
“学生”属性具体最高
信息增益，成为分裂属性
确定第二次分裂的属性
年龄
<30
30-40
>40
学生
不买 买
不是学生 是学生
...
买
ID3决策树建立算法
1 决定分类属性；
2 对目前的数据表，建立一个节点N
3 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上
标出所属的类
4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少
数服从多数的原则在树叶上标出所属类别
5 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作
为节点N的测试属性
6 节点属性选定后，对于该属性中的每个值：
从N生成一个分支，并将数据表中与该分支有关的数据收集形
成分支节点的数据表，在表中删除节点属性那一栏
7如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树
它首先对数据进行处理，利用归纳法生成可读的规则和决
策树，然后使用决策对新数据进行分析。本质上决策树是
通过一系列规则对数据进行分类的过程。决策树技术发现
数据模式和规则的核心是采用递归分割的贪婪算法。
决策树的基本原理
分类决策树
A decision tree is so called because the predictive model can be
represented in a tree-like structure.
the target is categorical, the model is a called a classification tree.
分类树采用的标准：
◆ 分类错误率:
◆ Gini 指数:
◆ 信息熵:
主要内容
什么是决策树
ID3算法
算法改进算法
CART算法
算法对ID3的改进
改进1：用信息增益率代替信息增益来选择属性
改进2：能够完成对连续值属性的离散化处理
改进3：能处理属性值缺失的情况
改进4：在决策树构造完成之后进行剪枝
十大数据挖掘算法
k-Means SVM Apriori
EM
PageRank
AdaBoost
kNN
Naïve Bayes
CART
改进1：信息增益的问题
假设按属性 A 划分 D 中的样本，且属性 A 根据训练数据的观测具有 v 个不同取值
{ a1, a2, ..., aj , ..., av }。
如果 A 是离散值，可依属性 A 将 D 划分为 v 个子集 { D1, D2, ..., Dj , ...,
Dv }
其中，Dj为D中的样本子集，它们在A上具有属性值aj
这些划分将对应于从该节点A出来的分支。
信息增益度量偏向于对取值较多的属性进行测试，即它倾向于选择v较大的属性A
举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分
（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。
对属性PID划分得到的信息增
益最大，显然，这种划分对分
类没有用处。
改进1：信息增益率
使用分裂信息(split information)将信息增益规范化
该值表示数据集D按属性A分裂的v个划分产生的信息
选择具有最大信息增益率的属性作为分裂属性
改进1：信息增益率
年龄 收入 学生 信用 买了电脑
<30 高 否 一般 否
<30 高 否 好 否
30-40 高 否 一般 是
>40 中 否 一般 是
>40 低 是 一般 是
>40 低 是 好 否
30-40 低 是 好 是
<30 中 否 一般 否
<30 低 是 一般 是
>40 中 是 一般 是
<30 中 是 好 是
30-40 中 否 好 是
30-40 高 是 一般 是
>40 中 否 好 否
Info(D) =
Info收入(D) =
Gain(收入) =
高收入的有4个
中等收入的有6个
低收入的有4个
SplitInfo收入(D)
= - 4/14 * log4/14
- 6/14 * log6/14
- 4/14 * log4/14
=
GainRatio(收入)
= Gain(收入) / SplitInfo收入(D)
= / =
改进2：连续值属性与分裂点
对于连续值属性，按属性值大小从小到大排序，取每对相邻值的中点作为可能的
分裂点split_point。
假设一连续值属性共有N个不同的属性值，则可找到N-1个可能的分裂点。
检查每个可能分裂点，取能使得信息增益最大的分裂点，将D分裂成
D1: A <= split_point 和 D2: A > split_point(一个分裂点，二分法，二叉树)
5 6 10
8
<=8 >8
不使用中点，而是直接使用一对值中较小的值作为可能的分裂点，如本例中
将使用5, 6作为可能分裂点
多个分裂点？多分法，多叉决策树
改进3：缺失值的处理
在某些情况下，可供使用的数据可能缺少某些属性的值，例如
一种简单的办法是赋予它该
属性最常见的值，例如将“
晴”或“雨”赋予第6个实例
的天气属性
一种更复杂的策略是为A的每
个可能值赋予一个概率
改进3：缺失值的处理
建树过程（学习过程）
选定训练样本实例有缺失值，如何知道要将其分配到哪个
分支？
分类过程（测试过程或者工作过程）
待分类实例有缺失值，如何测试该实例属于哪个分支？
天气
晴
多云
雨
(天气=缺失，温度=72，湿度=90...)
改进3： 中缺失值的处理 - 建树过程（学习过程）
Gain(A) = F ( Info(D) – InfoA(D))
其中 F 为属性值未缺失的实例所占比例；
计算 Info(D) 和 InfoA(D) 时忽略属性值缺失的实例
Info(D)
= -8/13×log(8/13) - 5/13×log(5/13)
= bits
Info天气(D)
= 5/13×(-2/5log(2/5) - 3/5×log(3/5))
+ 3/13×(-3/3log(3/3) - 0/3×log(0/3))
+ 5/13×(-3/5log(3/5) - 2/5×log(2/5))
= bits
Gain(天气)
= 13/14 × ( - )
= bits
改进3： 中缺失值的处理 - 建树过程（学习过程）
计算 SplitInfo 时，将缺失的属性值当作一个正常值进行计算，
本例中，当作天气有四个值，分别是晴, 多云, 雨, ?，再计算其 SplitInfo
SplitInfo天气(D)
= - 5/14×log(5/14)
- 3/14×log(3/14)
- 5/14×log(5/14)
- 1/14×log(1/14)
= bits
晴
多云
雨
缺失
GainRatio(天气)
= Gain(天气) / SplitInfo天气(D)
= /
改进3： 中缺失值的处理 - 建树过程（学习过程）
分裂时，将属性值缺失的实例分配给所有分支，但是带一个权重
湿度 有风 玩？ 权重
70
90
85
95
70
90
有
有
无
无
无
有
玩
不玩
不玩
不玩
玩
玩
1
1
1
1
1
5/13
湿度 有风 玩？ 权重
90
78
65
75
有
无
有
无
玩
玩
玩
玩
3/13
1
1
1
T1: (天气=晴) T1: (天气=多云)
湿度 有风 玩？ 权重
80
70
80
80
96
90
有
有
无
无
无
有
不玩
不玩
玩
玩
玩
玩
1
1
1
1
1
5/13
T1: (天气=雨)
本例14个实例中共13个实例天气属性值未缺失：
其中5个实例的天气属性为“晴”，3个实例的天气属性为“多云”， 5个实例的
天气属性为“雨”
本例14个实例中共1个实例天气属性值缺失，因此估算出天气属性值缺失的第6
个实例：
天气是晴的概率是5/13，天气是多云的概率是3/13，天气是雨的概率是5/13
改进3： 中缺失值的处理 - 建树过程（学习过程）
湿度 有风 玩？ 权重
70
90
85
95
70
90
有
有
无
无
无
有
玩
不玩
不玩
不玩
玩
玩
1
1
1
1
1
5/13=
T1: (天气=晴)
湿度<=75 2玩， 0不玩
湿度 > 75 5/13玩，3不玩
湿度
玩 () 不玩 (
<=75 >75
叶节点以 (N/E) 的形式定义，
其中 N 为到达该叶节点的实例数，
E 为其中属于其它分类的实例数。
例如，不玩( 表示个实例
到达“不玩”节点，其中个实例
不属于“不玩”
改进3： 中缺失值的处理 - 分类过程
湿度
玩 () 不玩 (
<=75 >75
天气
晴
(天气=晴，温度=90，湿度=缺失 ...)
对于任一实例，
湿度 <=75 的可能性是 + )，
湿度 >75 的可能性是 + )
当湿度 <=75 时，
分类为玩的可能性 = 100%
分类为不玩的可能性 = 0
当湿度 >75 时，
分类为玩的可能性 =
分类为不玩的可能性 = 3/=88%
最终分类的概率分布为：
玩 = + = 44%
不玩 = = 56%
改进4：学习过程中的过度拟合
上述的决策树算法增长树的每一个分支的深度，直到恰好
能对训练样例比较完美地分类。
实际应用中，当训练样本中有噪声或训练样例的数量太少
以至于不能产生目标函数的有代表性的采样时，该策略可
能会遇到困难
在以上情况发生时，这个简单的算法产生的树会过度拟合
训练样例 (过度拟合: Over fitting)
过度拟合产生的原因：训练样本中有噪声，训练样例太小
等
改进4：欠拟合、合适拟合、过拟合
欠拟合 合适拟合 过拟合
改进4：过度拟合
训练样本中噪声导致的过度拟合
错误的类别值/类标签，属性值等
训练样本中缺乏代表性样本所导致的过度拟合
根据少量训练记录作出的分类决策模型容易受过度拟合的
影响。由于训练样本缺乏代表性的样本，在没有多少训练
记录的情况下，学习算法仍然继续细化模型就会导致过度
拟合
改进4：缺乏代表性样本所导致的过度拟合
名称 体温 胎生 4条腿 冬眠 哺乳动物
蝾螈 冷血 N Y Y N
虹鳉 冷血 Y N N N
鹰 恒温 N N N N
弱夜鹰 恒温 N N Y N
鸭嘴兽 恒温 Y Y Y Y
哺乳动物分类的训练样例
名称 体温 胎生 4条腿 冬眠 哺乳动物
人 恒温 Y N N Y
大象 恒温 Y Y N Y
鸽子 恒温 N N N N
体温
恒温 冷血
冬眠 N
Y N
N4条腿
Y N
NY
按照训练模型。人和大象都不是
哺乳动物。决策树作出这样的判
断是因为只有一个训练样例具有
这些特点（鹰，恒温，不冬眠）
被划分为非哺乳动物。
该例清楚表明，当决策树的叶节
点没有足够的代表性时，可能会
预测错误。
哺乳动物分类的测试样例
改进4：决策树剪枝
How
?
预剪枝
(prepruning)
后剪枝
(postpruning
)
在完全正确分类训练集之
前就停止树的生长。
由“完全生长”的树剪去
子树。
改进4：预剪枝
yes
yes
no 剪枝处理
yes no
4
5
3
1 1
no
否
否
否
否
是
是
是
是
最直接的方法：
事先限定树的最大生长高度
如果设为3，
则如图剪枝
改进4：后剪枝
训练过程中允许对数据
的过度拟合，然后再利
用测试集对树进行修剪
树叶用被替换的子
树最频繁的类标号
yes
yes
no
yes no
4
1
3
1 1
no
2
yes/no
2
NO
是
是
是
是
是
是
否
否
否
否
否
否
改进4：后剪枝
在测试集上定义损失函数C，我们的目标是通过剪枝使得在测试
集上C的值下降。
例如通过剪枝使在测试集上误差率降低。
1. 自底向上的遍历每一个非叶节点(除了根节点)，将当前的非叶节点从树
中减去，其下所有的叶节点合并成一个节点，代替原来被剪掉的节点。
2. 计算剪去节点前后的损失函数，如果剪去节点之后损失函数变小了，则
说明该节点是可以剪去的，并将其剪去；如果发现损失函数并没有减少，
说明该节点不可剪去，则将树还原成未剪去之前的状态。
3. 重复上述过程，直到所有的非叶节点(除了根节点)都被尝试了。
从决策树导出产生式规则
大型决策树可读性较低，可通过从决策树导出产生式规则
以提高可读性
把从根结点到叶子结点的路径中遇到的所有测试条件联合
起来，便可建立相对应的规则集
从决策树导出产生式规则
但这样的规则会导致某些不必要的复杂性
可用类似的方法对规则集进行剪枝
对于某一规则，将它的单个条件暂时去除，在测试集上估
计误差率，并与原规则的误差率进行比较，若新规则的结
果较好，则删除这个条件
IF 天气=晴 AND 湿度 <= 75
THEN 玩
IF 天气=晴
THEN 玩
主要内容
什么是决策树
ID3算法
算法改进算法
CART算法
CART算法
分类回归树（CART:Classification and Regression
Tree）
其特点是在计算过程中充分利用二分支树的结构（Bianry
Tree-structured），即根节点包含所有样本，在一定的分
裂规则下根节点被分裂为两个子节点，这个过程又在子节
点上重复进行，直至不可再分，成为叶节点为止。
回归树（Regression Tree）
因变量-continuous ，叶子为因变量的预测值。
Boston Housing Data
Leaves = Boolean Rules（布尔规则）
Leaf
1
2
3
4
5
6
7
8
RM
<
<
<
[, )
<
[, )
NOX
<.51
[.51, .63)
[.63, .67)
<.67
.67
<.66
<.66
.66
Predicted MEDV
22
19
27
27
14
33
46
16
If RM {values} & NOX {values}, then MEDV=value
CART算法
CART: Classification And Regression Trees
可用于分类和回归(数值预测)
使用GINI指标来选择分裂属性
使用二元切分(将生成二叉树)
基于代价-复杂度剪枝
Gini指标
指标用来度量数据划分或者数据集的不纯度。
其中， 是 中样本属于 类的概率，并用 估计。
电脑销售数据集中，
9个样本属于“购买电脑”，
5个样本属于“未购买电脑”
Gini指标
如果按照 的二元分裂，将 划分成 和 ，则给定该划分的
指标为：
Gini指标最小，划分越纯。
选择具有最小Gini指标
(或最大∆Gini)的属性作为
分裂属性
处理离散值属性
以收入为例，对收入属性的所有可能子集：
{低，中，高}，{低，中}，{低，高}，{中，高}，{低}，{中}，{高}
考虑所有可能的二元划分，并计算划分前后的Gini指标，
选择能产生最小Gini指标的子集作为分裂子集
收入∈{中，高}
... ...
是 否
回归树的生成
◇ 数据：N个观测，p个自变量，1个因变量(连续型)
◇ 目标：自动地选择分裂变量及其分裂点
假设有一个分裂把自变量空间分成M个区域:
在每个区域，我们用一个常数来拟合因变量：
优化目标：误差平方和最小
上最优的拟合解为
从根节点开始，考虑一个分裂变量j和分裂点s，得到2个
区域：
最优的变量j和分裂点s，要满足
对于给定的j和s，最里层的优化问题的解为
而对于给定的j,分裂点s很快能找到.
这样，遍历所有的自变量，就能找到最佳的一对j和s.
递归分割-greedy algorithm
剪枝
最大的决策树能对训练集的准确率达到100%，最大的分类
树的结果会导致过拟合（对信号和噪声都适应）。因此建
立的树模型不能很好的推广到总体中的其他样本数据。同
样，太小的决策树仅含有很少的分支，会导致欠拟合。一
个好的树模型有低的偏倚和低的方差，模型的复杂性往往
在偏倚和方差之间做一个折中，因此要对树进行剪枝。这
里介绍cost-complexity pruning。
最大树
决策树能长到每个叶子都是纯的。最大的分类
可以达到100%的准确，最大的回归树残差为0。
恰当的树
先生成一个大的树 考虑一个子树 子树就是由大树进
行删减内部节点而得到.
用|T|表示树T 的叶节点（最终节点）的个数.
定义cost complexity criterion:
对于每个 ，寻找子树 使得 达到最小.
而 则起到了平衡树的大小和数据拟合好坏的作用.
较大会得到较小的树， 较小则会得到较大的树.
对于每个 ，可以证明存在唯一的最小的子树 使得
达到最小.
To find we use weakest link pruning: we successively
collapse the internal node that produces the smallest
per-node increase in , and continue until
we produce the single-node (root) tree.
This gives a sequence of subtrees, and this sequence must
contains
Estimation of is achieved by cross-validation: we
choose the value to minimize the cross-validation
sum of squares.
用于回归
要预测的属性是数值属性，非离散值属性
不纯度度量：计算所有数据的均值，再计算每条数据的值
到均值的差值的平方和
叶子结点用均值表示
k-Means SVM Apriori
EM
PageRank
AdaBoost
kNN
Naïve Bayes
CART
高伸缩性决策树算法
SLIQ、SPRINT、BOAT
决策树基本概念
决策树的优点
1、推理过程容易理解，决策推理过程可以表示成If Then形式；
2、推理过程完全依赖于属性变量的取值特点；
3、可自动忽略目标变量没有贡献的属性变量，也为判断属性
变量的重要性，减少变量的数目提供参考。
决策树基本概念
关于归纳学习(1)
决策树技术发现数据模式和规则的核心是归纳算法。
归纳是从特殊到一般的过程。归纳推理从若干个事实中表
征出的特征、特性和属性中，通过比较、总结、概括而得出一
个规律性的结论。
归纳推理试图从对象的一部分或整体的特定的观察中获得
一个完备且正确的描述。即从特殊事实到普遍性规律的结论。
归纳对于认识的发展和完善具有重要的意义。人类知识的增长
主要来源于归纳学习。
决策树基本概念
关于归纳学习(2)
归纳学习的过程就是寻找一般化描述的过程。这种一般性
描述能够解释给定的输入数据，并可以用来预测新的数据。
锐角三角形内角和等于180度；
钝角三角形内角和等于180度； 三角形内角和
直角三角形内角和等于180度； 等于180度
已知三角形ABC，A角等于76度，
B角等于89度，则其C角等于15度
归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个
基本的假设：
任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也
能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。
决策树基本概念
关于归纳学习(3)
决策树基本概念
关于归纳学习(4)
归纳过程就是在描述空间中进行搜索的过程。归纳可分为自
顶向下，自底向上和双向搜索三种方式。
自底向上法一次处理一个输入对象。将描述逐步一般化。直
到最终的一般化描述。
自顶向下法对可能的一般性描述集进行搜索，试图找到一些
满足一定要求的最优的描述。
决策树基本概念
从机器学习看分类及归纳推理等问题（1）
从特殊的训练样例中归纳出一般函数是机器学习的中心问题；
从训练样例中进行学习通常被视为归纳推理。每个例子都是一个
对偶（序偶）（x, f(x)），对每个输入的x，都有确定的输出f(x)。
学习过程将产生对目标函数f的不同逼近。F的每一个逼近都
叫做一个假设。假设需要以某种形式表示。例如，y=ax+b。通过
调整假设的表示，学习过程将产生出假设的不同变形。在表示中
通常需要修改参数（如a, b）。
决策树基本概念
从机器学习看分类及归纳推理等问题（2）
从这些不同的变形中选择最佳的假设（或者说权值集合）。
一般方法如定义为使训练值与假设值 预测出的值之间的误差平方
和E最小为最佳。
学习是在假设空间上的一个搜索。概念学习也可以看作是一
个搜索问题的过程。它在预定义的假设空间中搜索假设，使其与
训练样例有最佳的拟合度。多数情况下，为了高效地搜索，可以
利用假设空间中一种自然形成的结构，即一般到特殊的偏序关系。
决策树基本概念
从机器学习看分类及归纳推理等问题（3）
分类模型的性能根据模型正确和错误预测也可以根据的检验记录计数
进行评估。这些计数存储在混同矩阵（Confusion Matrix）的表格中，二元
分类问题混淆矩阵如下：
实际
的类
类1 f11
类0 f01
f10
f00
类1 类0
预测的类
准确率=正确的预测数/预测总数=（f11+f00）/(f11+f01+f10+f00)
差错率=错误的预测数/预测总数=（f10+f01）/(f11+f01+f10+f00)
归纳学习假设
机器学习的任务是在整个实例集合X上确定与目标概念c相同
的假设 。一般H表示所有可能假设。H中每个假设h表
示X上定义的布尔函数。由于对c仅有的信息只是它在训练样例上
的值，因此归纳学习最多只能保证输出的假设能与训练样例相拟
合。若没有更多的信息，只能假定对于未见实例最好的假设就是
训练数据最佳拟合的假设。
定义 归纳学习假设：任一假设如果在足够大的训练样例中很
好地逼近目标函数，则它也能在未见实例中很好地逼近目标函数。
（Function Approximation）。
决策树基本概念
从机器学习看分类及归纳推理等问题（4）
决策树学习是以实例为基础的归纳学习。
从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。
概念分类学习算法：来源于
Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概
念。
1979年, . Quinlan 给出ID3算法，并在1983年和1986年对ID3
进行了总结和简化，使其成为决策树学习算法的典型。
Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策
树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。
1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效
率。
1993年，Quinlan 进一步发展了ID3算法，改进成算法。
另一类决策树算法为CART，与不同的是，CART的决策树由二元
逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正
例与反例。
其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节
点处的熵值为零，此时每个叶节点中的实例都属于同一类。
决策树的基本原理
决策树学习采用的是自顶向下的递归方法。
决策树的每一层节点依照某一属性值向下分为子节点，待分
类的实例在每一节点处与该节点相关的属性值进行比较，根
据不同的比较结果向相应的子节点扩展，这一过程在到达决
策树的叶节点时结束，此时得到结论。
从根节点到叶节点的每一条路经都对应着一条合理的规则，
规则间各个部分（各个层的条件）的关系是合取关系。整个
决策树就对应着一组析取的规则。
决策树学习算法的最大优点是，它可以自学习。在学习的过
程中，不需要使用者了解过多背景知识，只需要对训练例子
进行较好的标注，就能够进行学习。如果在应用中发现不符
合规则的实例，程序会询问用户该实例的正确分类，从而生
成新的分枝和叶子，并添加到树中。
决策树的基本原理
树是由节点和分枝组成的层
次数据结构。节点用于存贮
信息或知识，分枝用于连接
各个节点。树是图的一个特
例，图是更一般的数学结构，
如贝叶斯网络。
决策树是描述分类过程的一
种数据结构，从上端的根节
点开始，各种分类原则被引
用进来，并依这些分类原则
将根节点的数据集划分为子
集，这一划分过程直到某种
约束条件满足而结束。
根结点
个子大
可能是松鼠 可能是老鼠
可能是大象
在水里
会吱吱叫
鼻子长
脖子长
个子小
不会吱吱叫
鼻子短
脖子短
可能是长颈鹿
在陆地上
可能是犀牛 可能是河马
可以看到，一个决策树的内部结点包含学习的实例，每层分枝代
表了实例的一个属性的可能取值，叶节点是最终划分成的类。如
果判定是二元的，那么构造的将是一棵二叉树，在树中每回答一
个 问 题 就 降 到 树 的 下 一 层 ， 这 类 树 一 般 称 为
CART（Classification And Regression Tree）。
判定结构可以机械的转变成产生式规则。可以通过对结构进行广
度优先搜索，并在每个节点生成“IF…THEN”规则来实现。如图
6-13的决策树可以转换成下规则：
IF “个子大” THEN
IF “脖子短” THEN
IF “鼻子长” THEN 可能是大象
形式化表示成
根结点
个 子
大
可能是松
鼠
可能是老
鼠
可能是大
象在 水
里
会 吱 吱
叫
鼻 子
长
脖 子
长
个子小
不会吱吱
叫
鼻 子
短
脖 子
短
可能是长颈
鹿
在 陆 地
上
可能是犀
牛
可能是河
马
构造一棵决策树要解决四个问题：
收集待分类的数据，这些数据的所有属性应该是完全标注的。
设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。
分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令
人满意。
设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往
是有限几个，因此在必要的时候应该停止数据集分裂：
• 该节点包含的数据太少不足以分裂，
• 继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献，
• 树的深度过大不宜再分。
通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小
最大的准则，这种方案使最具有分类潜力的准则最先被提取出来
它首先对数据进行处理，利用归纳法生成可读的规则和决
策树，然后使用决策对新数据进行分析。本质上决策树是
通过一系列规则对数据进行分类的过程。决策树技术发现
数据模式和规则的核心是采用递归分割的贪婪算法。
决策树的基本原理
决策树应用
· 决策树有很多的优点，可解释性、计算快捷、缺
失值的处理、对于多值名义变量不需要建立哑变
量、对输入变量异常值稳健。
· 一些树模型作为最后模型并不合适。它经常作为
很多熟悉模型（如回归模型）的辅助工具。标准
的回归模型具有线性和可加性。他们需要更多的
数据准备阶段：如缺失值的处理、哑变量编码。
他们统计计算的有效性严重的被许多不相关和冗
余的输入变量影响。
对数据的要求
进行分析时，决策树对变量的量纲的差异、离群
值的存在以及有偏分布不太敏感，也就是说对数
据准备要求不高。
当每一类的训练样本数较小时，决策树是容易出
错的，有好多分支的树或者每个节点有太多枝的
树最有可能这样，决策树对输出结果的密度很敏
感；
有的研究表明， regression模型样本量选择中，
最好各组样本含量大于解释变量数的20倍。
决策树方法之所以经常被选用是因为它能理顺一些
可以理解的规则。然而这些能力有时有些夸大，确
实对于某一个已经分过类的记录来说，为了产生这
种分类，很简单只要沿着从根到叶的路径走就可以
了，然而一个较复杂的决策树可能包含成千上万的
叶，这么一棵树从整体上很难提供有关问题可以理
解的信息。
而回归模型的回归系数具有可解释性，在流行病学
研究中，对致病因素的效应，常用一些危险度指标
来衡量因素与发病（或死亡）的联系程度或对人群
发病的致病作用的大小均可通过拟合该模型得出。
决策树所建立的算法把最胜任的拆分字段变量放在
树的根节点（并且同一个字段在树的其他层也可以出
现）。在用于预测时，重要的变量会漂浮到树的顶端，
这种方式产生的一个有用的结果是使得我们很容易就
能发现哪些解释变量最胜任预测工作。也可为
regression模型变量的筛选和决策提供指导。
谢谢！
