第7章 决策树与贝叶斯网络

第七章 决策树与贝叶斯网络

研究生特色精品课程-机器学习

1

决策树的形成与发展

研究生特色精品课程-机器学习

1.1 简介

决策树方法的起源是概念学习系统CLS，然后发展到ID3方 法而为高潮，最后又演化为能处理连续属性的C4.5。有名 的决策树方法还有CART 是应用最广的归纳推理算法之一 语义可表示性 对噪声数据有很好的健壮性

研究生特色精品课程-机器学习

1.2 决策树的表示法

决策树通过把实例从根节点排列到某个叶子节点来分类实 例，叶子节点即为实例所属的分类。树上的每一个节点说 明了对实例的某个属性的测试，并且该节点的每一个后继 分支对应于该属性的一个可能值。

研究生特色精品课程-机器学习

图

研究生特色精品课程-机器学习

1.3 构造决策树

决策树分类过程 从根节点开始，首先对某一属性的取值提问 Color? 与根节点相连的不同分支，对应这个属性的不同取值 green; yellow; red; 根据不同的回答，转向相应的分支 green 在新到达的节点处做同样的分支判断 Size? – big. 这一过程持续，直到到达某个叶节点，输出该叶节点的类别标记 Watermelon

研究生特色精品课程-机器学习

2

决策树的基本原理： 统计学角度

研究生特色精品课程-机器学习

2.1 决策树的判决面

研究生特色精品课程-机器学习

2.2 构造决策树 基本过程

从上到下，分而治之（divide-and-conquer），递归生长 最初，所有的样本都在根节点 所有属性都是标称型的（如果是连续数值型的，则需要先离散化ID3) 所有样本根据每次选择出的属性递归的逐渐划分开来 满足如下条件之一时，划分操作停止

所有落入某一节点的样本均属于同一类别 没有特征能够进一步用于划分样本集 没有任何样本落入某一节点

研究生特色精品课程-机器学习

属性选择

构造好的决策树的关键在于如何选择好的逻辑判断或属性。 对于同样一组例子，可以有很多决策树能符合这组例子。 人们研究出，一般情况下或具有较大概率地说，树越小则 树的预测能力越强。要构造尽可能小的决策树，关键在于 选择恰当的逻辑判断或属性。由于构造最小的树是NP-难 问题，因此只能采取用启发式策略选择好的逻辑判断或属 性。

研究生特色精品课程-机器学习

度量标准——熵

熵(Entropy)

– 信息论中广泛使用的一个度量标准 – 刻画任意样例集的纯度（purity） – 一般计算公式为：

Entropy ( S ) pi log2 pi

i 1

c

– 对于二元分类：给定包含关于某个目标概念的正反样例的样例集S， 那么S相对这个布尔型分类的熵为： – Entropy(S)