第四章：决策树.pdf

第四章：决策树 大纲  基本流程  划分选择  剪枝处理  连续与缺失值  多变量决策树 基本流程 决策树基于树结构来进行预测 色泽=? 青绿 … 根蒂=? …... 蜷缩 … 敲声=? …... 浊响 … 好瓜 …... 基本流程  决策过程中提出的每个判定问题都是对某个属性的“测试”  决策过程的最终结论对应了我们所希望的判定结果  每个测试的结果或是导出最终结论，或者导出进一步的判定问题， 其考虑范围是在上次决策结果的限定范围之内  从根结点到每个叶结点的路径对应了一个判定测试序列 决策树学习的目的是为了产生一棵泛化能力强， 即处理未见示例能力强的决策树 基本流程 （1）当前结点包含的 样本全部属于同一类 别 （2 ）当前属性集为空， 或所有样本在所有属 性上取值相同 （3 ）当前结点包含的 样本集合为空 大纲  基本流程  划分选择  剪枝处理  连续与缺失值  多变量决策树 划分选择  决策树学习的关键在于如何选择最优划分属性。一般而言，随着 划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可 能属于同一类别，即结点的“纯度”(purity)越来越高  经典的属性划分方法：  信息增益  增益率  基尼指数 划分选择-信息增益  “信息熵”是度量样本集合纯度最常用的一种指标，假定当前样 本集合 中第 类样本所占的比例为 ，则 的信 息熵定义为 的值越小，则 的纯度越高  计算信息熵时约定：若 ，则  的最小值为 ，最大值为 划分选择-信息增益  离散属性 有 个可能的取值 ，用 来进行划分，则 会产生 个分支结点，其中第 个分支结点包含了 中所有在属性 上取值为 的样本，记为 。则可计算出用属性 对样本集 进行 划分所获得的 “信息增益”： 为分支结点权重，样本数越 多的分支结点的影响越大  一般而言，信息增益越大，则意味着使用属性 来进行划分所获 得的“纯度提升”越大 