电子科技大学：《数据分析与数据挖掘 Data Analysis and Data Mining》课程教学资源（课件讲稿）决策树

数据分析与数据挖掘 四、决策树





决策树模型 决策树基于“树”结构进行决策 口每个“内部结点”对应于某个属性上的“测试”(test) 口每个分支对应于该测试的一种可能结果（即该属性的某个取值） 每个“叶结点”对应于一个“预测结果” 色泽=？ 青绿 学习过程：通过对训练样本的分析来 根蒂=？ 确定“划分属性”（即内部结点所对 蜷缩 应的属性) 敲声=？ 预测过程：将测试示例从根结点开始， 浊响 沿着划分属性所构成的“判定测试序 好瓜 列”下行，直到叶结点 主要工作：如何生成决策树！！！ 图4.1西瓜问题的一棵决策树

@14 @1
1B-ID@ p 5
KB8!%0#' :
7F(test) p 5*!%G7F:?CB/G#':0 p 5
B8!%
L7B/ ⹇⅁抨䳬JH!EA2+:., =
#'KB8)! %:#' 步䀬抨䳬"7F> 3B8& 6<#')-(:
 7F$  D;B8 ℜ屢テ∽9(@1

决策树简史 ·第一个决策树算法：CLS(Concept Learning System) [E.B.Hunt,J.Marin,and P T.Stone's book "Experiments in Induction"published by Academic Press in 1966] ·使决策树受到关注、成为机器学习主流技术的算法：D3 [J.R.Quinlan's paper in a book "Expert Systems in the Micro Electronic Age"edited by D.Michie,published by Edinburgh University Press in 1979] ·最常用的决策树算法：C4.5 [J.R.Quinlan's book "C4.5:Programs for Machine Learning"published by Morgan Kaufmann in 1993]

 •  CLS (Concept Learning System) [E. B. Hunt, J. Marin, and P. T. Stone’s book “Experiments in Induction” published by Academic Press in 1966] •   
ID3 [J. R. Quinlan’s paper in a book “Expert Systems in the Micro Electronic Age” edited by D. Michie, published by Edinburgh University Press in 1979] •  C4.5 [J. R. Quinlan’s book “C4.5: Programs for Machine Learning” published by Morgan Kaufmann in 1993]

决策树简史(cont) 可以用于回归任务的决策树算法：CART(Classification and Regression Tree) [L.Breiman,J.H.Friedman,R.A.Olshen,and C.J.Stone's book "Classification and Regression Trees"published by Wadsworth in1984] ·基于决策树的最强大算法(？？)：RF (Random Forest) [L.Breiman's MLJ'01 paper "Random Forest"] 这是一种“集成学习”方法→第8章

)!?(con’t) •   ( )!#CART (Classification and Regression Tree) [L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone’s book “Classification and Regression Trees” published by Wadsworth in 1984] •  )!#
RF (Random Forest) [L. Breiman’s MLJ’01 paper “Random Forest”] $% à 8 

基本流程 ▣ 决策过程中提出的每个判定问题都是对某个属 色泽=？ 青绿 性的“测试” 000年 口决策过程的最终结论对应了希望的判定结果 根蒂=？ 蜷缩 ▣ 每个测试的结果或是导出最终结论，或者导出 敲声=？ 进一步的判定问题，其考虑范围是在上次决策 浊响 结果的限定范围之内 好瓜 ▣从根结点到每个叶结点的路径对应了一个判定 测试序列 图4.1西瓜问题的一裸决策树 决策树学习的目的是为了产生一棵泛化能力强 即处理未见示例能力强的决策树

 p =I<(93LNK). &9
5G p =I<9*>?F# !+9?- p 35G9?-')*>?F'A JO29LN@DC)1= ?-9MC p 0?63?69H%# O 5G" =/ 9:9) 8OP4B$ 7,E; B$9=/