第二章决策树(ID3分类算法).ppt

研究生学院 性别年龄种族家庭人口家庭收入申请该校原因家庭住址 例2 Wal Mart的销售与供应商关心哪一种产品畅销 第二章决策树DecisionTree ID3分类算法 产品名称产品型号产品价格生产厂家生产国家出售地点出售日期 例1 学校录取部门的困扰 新生录取以后会不会来报到 一 分类问题的提出 为解决上述问题必须进行分类分类是数据挖掘中的一种主要分析手段分类的任务是对数据集进行学习并构造一个拥有预测功能的分类模型 用于预测未知样本的类标号 如 根据瓦斯状态 开采技术条件 煤层赋存状况等对危险进行分类评估根据核磁共振的结果区分肿瘤是恶性还是良性的根据星系的形状对它们进行分类划分出交易是合法或欺诈将新闻分类金融 天气 娱乐体育等 主要分类方法决策树分类方法贝叶斯分类方法K 最近邻分类方法神经网络分类方法支持向量机组合学习方法不平衡数据分类问题分类模型的评价回归方法 研究生学院 举例说明分类任务 归纳 推论 模型 学习算法 研究生学院 有房 婚姻状况 年收入 是 否 否 否 是 没有 已婚 单身 离婚 80K 80K 极快的属性 训练数据 模型 决策树 研究生学院 婚姻状况 有房 年收入 是 否 否 是 没有 已婚 单身 离异 80K 80K 测试数据 申请模型到测试数据 研究生学院 开始从树 的根 测试数据 研究生学院 测试数据 开始从树 的根 研究生学院 测试数据 开始从树 的根 研究生学院 测试数据 开始从树 的根 研究生学院 测试数据 开始从树 的根 研究生学院 测试数据 开始从树 的根 研究生学院 归纳 推论 模型 学习算法 研究生学院 有房 婚姻状况 年收入 是 否 否 否 是 没有 已婚 单身 离婚 80K 80K 极快的属性 训练数据 模型 决策树 决策树的例子 研究生学院 婚姻状况 有房 年收入 是 否 否 是 没有 已婚 单身 离异 80K 80K 决策树的例子 研究生学院 归纳 推论 模型 学习算法 研究生学院 测试数据 开始从树 的根 申请模型到测试数据 研究生学院 测试数据 开始从树 的根 研究生学院 测试数据 开始从树 的根 研究生学院 测试数据 开始从树 的根 研究生学院 测试数据 开始从树 的根 研究生学院 测试数据 开始从树 的根 举例说明分类任务 研究生学院 归纳 推论 模型 学习算法 决策树在构建过程中需重点解决2个问题 1 如何选择合适的属性作为决策树的节点去划分训练样本 2 如何在适当位置停止划分过程 从而得到大小合适的决策树 虽然可以采用任何一个属性对数据集进行划分 但最后形成的决策树会差异很大 需要寻找合适的属性选择方法 属性选择是决策树算法中重要的步骤 常见的属性选择标准包括信息增益 informationgain 和Gini系数 信息增益是决策树常用的分枝准则 在树的每个结点上选择具有最高信息增益的属性作为当前结点的划分属性 Gini系数是一种不纯度函数 用来度量数据集的数据关于类的纯度 二 DI3分类算法 1 ID3分类算法提出 由Quinlan于1986年提出 它使用信息增益 informationgain 作为属性的选择标准 首先检测所有的属性 选择信息增益最大的属性产生决策树结点 由该属性的不同取值建立分支 再对各分支的子集递归调用该方法建立决策树结点的分支 直到所有子集仅包含同一个类别的数据为止 最后得到一棵决策树 它可以用来对新的样本进行分类 2 ID3分类算法相关的基本概念 1 信息熵2 信息增益 熵 entropy 也称信息熵 用来度量一个属性的信息量 假定S为训练集 S的目标属性C具有m个可能的类标号值 C C1 C2 Cm 假定训练集S中 Ci在所有样本中出现的频率为 i 1 2 3 m 则该训练集S所包含的信息熵定义为 熵越小表示样本对目标属性的分布越纯 反之熵越大表示样本对目标属性分布越混乱 信息熵例题演示考虑数据集weather如下 求weather数据集关于目标属性playball的熵 目标属性 解答 令weather数据集为S 其中有14个样本 目标属性playball有2个值 C1 yes C2 no 14个样本的分布为 9个样本的类标号取值为yes 5个样本的类标号取值为No C1 yes在所有样本S中出现的概率为9 14 C2 no在所有样本S中出现的概率为5 14 因此数据集S的熵为 信息增益 是划分前样本数据集的不纯程度 熵 和划分后样本数据集的不纯程度 熵 的差值 假设划分前样本数据集为S 并用属性A来划分样本集S 则按属性A划分S的信息增益Gain S A 为样本集S的熵减去按属性A划分S后的样本子集的熵 按属性A划分S后的样本子集的熵定义如下 假定属性A有k个不同的取值 从而将S划分为k个样本子集 S1 S2 Sk 则按属性A划分S后的样本子集的信息熵为 其中 Si i 1 2 k 为样本子集Si中包含的样本数 S 为样本集S中包含的样本数 信息增益越大 说明使用属性A划分后的样本子集越纯 越有利于分类 以数据集weather为例 设该数据集为S 假定用属性wind来划分S 求S对属性wind的信息增益 解 1 首先由前例计算得到数据集S的熵值为0 94 2 属性wind有2个可能的取值 weak strong 它将S划分为2个子集 S1 S2 S1为wind属性取值为weak的样本子集 共有8个样本 S2为wind属性取值为strong的样本子集 共有6个样本 下面分别计算样本子集S1和S2的熵 对样本子集S1 playball yes的有6个样本 playball no的有2个样本 则 对样本子集S2 playball yes的有3个样本 playball no的有3个样本 则 利用属性wind划分S后的熵为 按属性wind划分数据集S所得的信息增益值为 以weather数据集为例 讲解ID3的建立过程 数据集具有属性 outlook temperature humidity wind outlook sunny overcast rain temperature hot mild cool humidity high normal wind weak strong 首先计算总数据集S对所有属性的信息增益 寻找根节点的最佳分裂属性 Gain S outlook 0 246Gain S temperature 0 029Gain S humidity 0 152Gain S wind 0 049显然 这里outlook属性具有最高信息增益值 因此将它选为根结点 以outlook做为根结点 继续往下 思想是 以outlook的可能取值建立分支 对每个分支递归建立子树 因为outlook有3个可能值 因此对根结点建立3个分支 sunny overcast rain 那么 哪个属性用来最佳划分根结点的Sunny分支 overcast分支 Rain分支 首先对outlook的sunny分支建立子树 找出数据集中outlook sunny的样本子集Soutlook sunny 然后依次计算剩下三个属性对该样本子集Ssunny划分后的信息增益 Gain Ssunny humidity 0 971Gain Ssunny temperature 0 571Gain Ssunny wind 0 371 显然humidity具有最高信息增益值 因此它被选为outlook结点下sunny分支下的决策结点 采用同样的方法 依次对outlook的overcast分支 rain分支建立子树 最后得到一棵可以预测类标号未知的样本的决策树 ID3决策树对未知样本进行预测下面利用决策树对类标号未知的样本X进行预测 X rain hot normal weak ID3算法总结ID3算法是所有可能的决策树空间中一种自顶向下 贪婪的搜索方法 ID3搜索的假设空间是可能的决策树的集合 搜索目的是构造与训练数据一致的一棵决策树 搜索策略是爬山法 在构造决策树时从简单到复杂 用信息熵作为爬山法的评价函数 ID3算法的核心是在决策树各级结点上选择属性 用信息增益作为属性选择的标准 使得在每个非叶节点进行测试时能获得关于被测数据最大的类别信息 使得该属性将数据集分成子集后 系统的熵值最小 优点 理论清晰 方法简单 学习能力较强 缺点 1 算法只能处理分类属性数据 无法处理连续型数据 2 算法对测试属性的每个取值相应产生一个分支 且划分相应的数据样本集 这样的划分会导致产生许多小的子集 随着子集被划分得越来越小 划分过程将会由于子集规模过小所造成的统计特征不充分而停止 3 ID3算法中使用信息增益作为决策树节点属性选择的标准 由于信息增益在类别值多的属性上计算结果大于类别值少的属性上计算结果 这将导致决策树算法偏向选择具有较多分枝的属性 因而可能导致过度拟合 在极端的情况下 如果某个属性对于训练集中的每个元组都有唯一的一个值 则认为该属性是最好的 这是因为对于每个划分都只有一个元组 因此也是一类 优点 理论清晰 方法简单 学习能力较强 缺点 1 算法只能处理分类属性数据 无法处理连续型数据 2 算法对测试属性的每个取值相应产生一个分支 且划分相应的数据样本集 这样的划分会导致产生许多小的子集 随着子集被划分得越来越小 划分过程将会由于子集规模过小所造成的统计特征不充分而停止 3 ID3算法中使用信息增益作为决策树节点属性选择的标准 由于信息增益在类别值多的属性上计算结果大于类别值少的属性上计算结果 这将导致决策树算法偏向选择具有较多分枝的属性 因而可能导致过度拟合 在极端的情况下 如果某个属性对于训练集中的每个元组都有唯一的一个值 则认为该属性是最好的 这是因为对于每个划分都只有一个元组 因此也是一类 C4 5基于ID3算法中存在的不足 Quinlan于1993年对其做出改进 提出了改进的决策树分类算法C4 5