X>x2
<=52,000
>52,000
图9-2 按照分裂点划分而成的决策树图与相关的具体例子图
第9章 决策树算法
10
9.1 决策树算法原理

X
颜色
x1 x2 …… xi
红绿蓝 橙
收入
低 中等 高
图9-3 按照分裂子集划分而成的决策树图与相关的两个具体例子图
第9章 决策树算法
11
9.1 决策树算法原理
注意：分裂准则与分裂属性、分裂点、分裂 子集并不等同，它们是四个不同的概念， 并且分裂子集分裂点分裂属性分裂准则
第9章 决策树算法
9
9.1 决策树算法原理
将上面的定义结合实际的决策树例子可得 决策树图如下图9-1，图9-2，图9-3所示， 图中设X为分裂属性，是属性X的已知值。
X
收入
X<=x1
第9章 决策树算法
18
9.2.1 ID3算法
假设训练数据集D中的正例集PD和反例 集ND的大小分别为p和n，则ID3基于下面 两个假设给出该决策树算法中信息增益的 定义，因为信息是用二进制编码的，所以 在下面的公式定义中都用以2为底的对数。 （1）在训练数据集D上的一棵正确决策树 对任意例子的分类概率同D中正反例的概率 一致；（2）一棵决策树能对一个例子做出 正确类别判断所需的信息量如下公式所示：
第9章 决策树算法
13
9.2 常用决策树算法
ID3算法
ID3是Quinlan于1986年提出的，是机器学习中一种 广为人知的一个算法，它的提出开创了决策树算法的先河， 而且是国际上最早最有影响的决策树方法，在该算法中， 引入了信息论中熵的概念，利用分割前后的熵来计算信息 增益，作为判别能力的度量。
定义9.3 分裂属性Xi定义为决策树中每个内 部节点都对应的一个用于分裂数据集的属 性。Xi A= {A1, A2 ,, Ah }
第9章 决策树算法
8
9.1 决策树算法原理
定义9.4 如果Xi是连续属性，那么分裂准则 的形式为Xi，其中，就称为节点n的分裂点。
定义9.5 如果Xi是离散属性，那么的形式为， 其中，就称为节点n的分裂子集。
第9章 决策树算法
14
9.2.1 ID3算法
定义9.6 信息熵
自信息量只能反映符号的不确定性，而信息熵可以用
来度量整个信源X整体的不确定性。设某事物具有n种相互
独的立概的率可分能别结为果(P或(x1称), P状(x2态),)：P(xx1n,)x, 2 ,,且xn有，：每一种结果出现

n
p(xi ) 1
每个内部节点都被标记一个属性Ai。
每个弧都被标记一个值，这个值对应于相 应父结点的属性。
每个叶节点都被标记一个类Cj。
第9章 决策树算法
7
9.1 决策树算法原理
定义9.2 分裂准则 定义为在决策树算法中 将训练数据集D中的元组划分为个体类的最 好的方法与策略，它告诉我们在节点N上测 试哪个属性合适，如何选择测试与测试的 方法，从节点N上应该生长出哪些分支。
X Y i
yes
noBiblioteka 颜色 {红 , 绿 }是
否
图9-4 按照分裂子集划分而成的决策树（只能是二叉树）图与相关的具体例子图
第9章 决策树算法
12
9.1 决策树算法原理
目前主要使用如下几个量化评估标准 (1)预测准确性 (2)模型强健性 (3)描述的简洁性 (4)计算复杂性 (5)处理规模性
（9.1）
i 1
那么，该事物所具有的不确定量为：
n

H (X ) p(x1)I (x1) p(x2 )I (x2 ) p(xn )I (xn ) p(xi ) log 2 P(xi )
i1

（9.2）
第9章 决策树算法
15
9.2.1 ID3算法
上式即为著名的香农信息量公式。注意到 式中的对数以2为底，当n=2时且时，熵=1 比特。由此可见，一个等概率的二选一事 件具有1比特的不确定性。所以，可以把一 个等概率的二选一事件所具有信息量定为 信息量的单位。任何一个事件能够分解成n 个可能的二选一事件，它的信息量就是n比 特。
优点：
使用者不需要了解很多背景知识，只要训练事例 能用属性→结论的方式表达出来，就能用该算法 学习；
决策树模型效率高，对训练集数据量较大的情况 较为适合；
分类模型是树状结构，简单直观，可将到达每个 叶结点的路径转换为IF→THEN形式的规则，易于 理解；
决策树方法具有较高的分类精确度。
工作过程：
训练数 据集
决策树 分类算
法
评估模 式
测试集
预测
预测结 果
类别未 知的数
据集
1、创建决策树过程
2、使用决策树模型预测过程
决策树分类模型的工作过程图
第9章 决策树算法
6
9.1 决策树算法原理
定义 9.1 给定一个训练数据集D＝，其中每 个实例，称为例子，训练数据集中包含以 下属性A=。同时给定类别集合C。对于训 练数据集D，决策树是指具有以下性质的树：
第9章 决策树算法
4
9.1 决策树算法原理
传统的数据分类操作通常有以下两个步骤: 模型训练阶段：根据给定的训练集，找到
合适的映射函数H:→C的表示模型。 使用上一步训练完成的函数模型预测数据
的类别，或利用该函数模型，对数据集中 的每一类数据进行描述，形成分类规则。
第9章 决策树算法
5
9.1 决策树算法原理
下面给出的是ID3算法中将香农的信息熵定 义应用到决策树构造中，进而给出的信息 增益的定义。
设训练数据集D= D1 D2 D, n 是n维有穷向量空间，其中
Dj
是有穷离散符号集，D中的每个元素
d t1,t2 ,,tn ，叫做例子，其中
t j D j , j 1,2,, n 设PD和ND是D的两个子集，分别叫做正例集和反例集。
数据挖掘原理与SPSS Clementine应用宝典
元昌安 主编 邓 松 李文敬 刘海涛 编著
电子工业出版社
第9章 决策树算法
1
第9章 决策树算法
第9章 决策树算法
2
本章大纲：
决策树算法原理 常用决策树算法 决策树剪枝 由决策树提取分类规则 应用实例分析
第9章 决策树算法
3
9.1 决策树算法原理
第9章 决策树算法
16
9.2.1 ID3算法
Quinlan的首创性工作主要是在决策树的学 习算法中第一次引入了信息论中的互信息 （称之为信息增益），以之作为属性选择 的标准，并且将建树的方法嵌入在其中， 其核心是在决策树的各级节点上选择属性， 用信息增益作为属性选择标准
第9章 决策树算法
17
9.2.1 ID3算法