基本流程 策略：“分而治之”(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