大纲 口基本流程 口划分选择 口剪枝处理 口连续与缺失值 多变量决策树
大纲 基本流程 划分选择 剪枝处理 连续与缺失值 多变量决策树
划分选择 口决策树学习的关键在于如何选择最优划分属性。一般而言,随着 划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可 能属于同一类别,即结点的“纯度”( purity)越来越高 口经典的属性划分方法: ●信息增益 增益率 基尼指数
划分选择 决策树学习的关键在于如何选择最优划分属性。一般而言，随着 划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可 能属于同一类别，即结点的“纯度”(purity)越来越高 经典的属性划分方法： ⚫ 信息增益 ⚫ 增益率 ⚫ 基尼指数
划分选择-信息增益 口“信息熵”是度量样本集合纯度最常用的一种指标,假定当前样 本集合D中第k类样本所占的比例为Pk(K=1,2,…,y),则的信 息熵定义为 Ent(D ∑ pk 10g2 pk Ent(D)的值越小,则D的纯度越高 口计算信息熵时约定:若p=0,则plog2p=0 口En(D)的最小值为0,最大值为og2
划分选择-信息增益 “信息熵”是度量样本集合纯度最常用的一种指标，假定当前样 本集合 中第 类样本所占的比例为 ，则 的信 息熵定义为 的值越小，则 的纯度越高 计算信息熵时约定：若 ，则 的最小值为 ，最大值为
划分选择-信息增益 口离散属性Q有V个可能的取值{al,a2,…,aY},用来进行划分,则 会产生V个分支结点,其中第0个分支结点包含了D中所有在属性a 上取值为α的样本,记为D°。则可计算出用属性对样本集进行 划分所获得的“信息增益” Gain(D,a)=Et(D)-∑ D Ent(d 为分支结点权重,样本数越 多的分支结点的影响越大 口一般而言,信息增益越大,则意味着使用属性α来进行划分所获 得的“纯度提升”越大 口ID3决策树学习算法[ Quinlan,1986]以信息增益为准则来选择划分 属性
划分选择-信息增益 离散属性 有 个可能的取值 ，用 来进行划分，则 会产生 个分支结点，其中第 个分支结点包含了 中所有在属性 上取值为 的样本，记为 。则可计算出用属性 对样本集 进行 划分所获得的“信息增益”： 一般而言，信息增益越大，则意味着使用属性 来进行划分所获 得的“纯度提升”越大 ID3决策树学习算法[Quinlan, 1986]以信息增益为准则来选择划分 属性 为分支结点权重，样本数越 多的分支结点的影响越大
划分选择-信息增益 信息增益实例 编号色泽根蒂敲声纹理脐部触感好瓜 青 缩浊响清晰凹陷硬滑 12345 黑蜷缩沉闷清晰凹陷硬滑 乌黑蜷缩浊响清晰凹陷硬滑 青绿蜷缩沉闷清晰凹陷硬滑 是是是 浅白蜷缩浊响清晰凹陷硬滑是 6青绿稍蜷浊响清晰稍凹软粘是 乌黑稍蜷浊响稍糊稍凹软粘是 8乌黑稍蜷浊响清晰稍凹硬滑 是—该数据集包含17 乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑 青绿使提清脆清断平坦软训练样本,y=2, 12浅白蜷缩浊响模糊平坦软粘其中正例占p1=n 13青绿稍蜷浊响稍糊凹陷硬滑 14浅白稍蜷沉闷稍糊凹陷硬滑 反例占P2=,计 164蜡浊i断魏精算得到根结点的信 17利滑怠熵为 2 Ent(D)=∑ Pr 10g2 Pk 1710g215+21og21)=0.998
划分选择-信息增益 信息增益实例 …... … …... … 该数据集包含 个 训练样本， ， 其中正例占 ， 反例占 ，计 算得到根结点的信 息熵为