数据分析与数据挖掘 四、决策树
决策树模型 决策树基于“树”结构进行决策 口每个“内部结点”对应于某个属性上的“测试”(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?F # !+9 ?- p 35G9?-') *>?F'A JO29 LN@DC)1= ?-9M C p 0?63?69H% # O 5G" =/ 9:9) 8OP4B$ 7,E; B$9=/
基本流程 策略：“分而治之”(divide-and-conquer))。从根节点开始自 至叶节点的递归过程。在每个中间结点寻找一个“划分” (splitter test)属性。 三种停止条件： (1)当前结点包含的样本全属于同一类别，无需划分； (2)当前属性集为空，或是所有样本在所有属性上取值相同， 无法划分； (③)当前结点包含的样本集合为空，不能划分
%* ) #! (1) -&'" , 0 ; (2) /+, " ( $ ; (3) -&'" /+. . (divide-and-conquer) ! !#" $ (splitter test)
(1) 当前结点包含的样本全属于同一类别，无需划分； 基本算法 (2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分； (3)当前结点包含的样本集合为空，不能划分. 输入：训练集D= {(c1,1),(x2,2),,(cm,ym)}; 属性集A={a1,a2,,ad 过程：函数TreeGenerate(D,A) 1:生成结点node 递归返回， 2: ifD中样本全属于同一类别C then 情形(1) 3: 将node标记为C类叶结点；return 4:end if 递归返回， 5:fA=⑦ORD中样本在A上取值相同then 将node标记为叶结点，其类别标记为D中样本数最多的类； 情形(2) 6: return 7:end if 8:从A中选择最优划分属性a*; 利用当前结点的后验分布 9: fora*的每一个值agdo 10: 为node生成一个分支；士D,表示D中在a*上取值为a的样本子集； ifD,为空then 递归返回， 11: 12: 将分支结点标记为叶结 其类别标记为D中样本最多的类；return 情形(3) 13: else 将父结点的样本分布作为 14: 以TreeGenerate(Du,A\)为分支结点 当前结点的先验分布 15: end if 16: end for 决策树算法的 输出：以node为根结点的一棵决策树 核心
(4, 9 8 " (1) 9 8 " (2) / 6-0< 9 8 " (3) .6-0*( 6-0 < 3)4,0 + (1) 6-0*( 5%; ; (2) !:2, #&$'*($'!1%, ; (3) 6-0*(:27 .
划分选择 决策树学习的关键在于如何选择最优划分属性。 般而言，随着划分过程不断进行，我们希望决策树 的分支结点所包含的样本尽可能属于同一类别，即 结点的"纯度”(purity)越来越高 ▣经典的属性划分方法： 。信息增益-ID3算法中使用 ●增益率-C4.5算法中使用 基尼指数-CART算法中使用
p 90 5 G F&, "KJ @>BH7D8*EA$ -90 5(=3%51. ? J: =35;!(purity)C/CI p<5 "+2 l #6 - ID3 l 64 - C4.5 l ') - CART
信息增益(information gain) 信息熵 (entropy)是度量样本集合“纯度”最常用的一种指标 假定当前样本集合D中第k类样本所占的比例为Pk,则D的 信息熵定义为 计算信息熵时约定：若 p=0,则plog2p=0. Ent(D)=-∑pr log2pk k=1 Ent(D)的最小值为0， 最大值为log2门儿. Et(D)的值越小，则D的纯度越高 信息增益直接以信息熵为基础，计算当前划分对信息熵所造成的变化
+ (information gain) ( (entropy) "6&$72#)*. % &$7 D / k 1&$ *' D * ( * 4 *248 +,! (-30 ( 5 *
表4.1西瓜数据集2.0 一个例子 编号 色泽 根蒂 敲声 纹理 脐部 触感 好瓜 青绿 蜷缩 浊响 清晰 凹陷 硬滑 是 2 乌黑 蜷缩 沉闷 清晰 凹陷 硬滑 是 3 乌黑 蜷缩 浊响 清晰 凹陷 硬滑 是 使用哪个属性划分？ 青绿 蜷缩 沉闷 清晰 凹陷 硬滑 是 5 浅白 蜷缩 浊响 清晰 凹陷 硬滑 是 6 青绿 稍蜷 浊响 清晰 稍凹 软粘 是 7 乌黑 稍蜷 浊响 稍糊 稍凹 软粘 是 8 乌黑 稍蜷 浊响 清晰 稍凹 硬滑 是 9 乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑 10 青绿 硬挺 清脆 清晰 平坦 软粘 否 该数据集包含17个 11 浅白 硬挺 清脆 模糊 平坦 硬滑 否 12 浅白 蜷缩 浊响 模糊 平坦 软粘 否 训练样例，川=2 13 青绿 稍蜷 浊响 稍糊 凹陷 硬滑 否 其中正例占P1=7 14 浅白 稍蜷 沉闷 稍糊 凹陷 硬滑 否 9 反例占p2= 15 乌黑 稍蜷 浊响 清晰 稍凹 软粘 否 16 浅白 蜷缩 浊响 模糊 平坦 硬滑 否 17 青绿 蜷缩 沉闷 稍糊 稍凹 硬滑 否 根结点的信息熵为 BmtD)=-2 n oga4=-(8+}1g2）=090s k=1
