决策树.ppt

决策树 决策树简介决策树算法 A1 A2两方案投资分别为450万和240万 经营年限为5年 销路好的概率为0 7 销路差的概率为0 3 A1方案销路好年 差年的损益值分别为300万和负60万 A2方案分别为120万和30万 决策树简介 决策树简介 A1 A2 0 7 0 3 0 7 0 3 300 60 120 30 决策树简介 最后选择的最佳方案 代表备选方案的经济效果 将每个方案在各种自然状态下取得的损益值标注于结果节点的右端 决策树的一般流程 1 收集数据 2 准备数据 3 分析数据 4 训练算法 5 测试算法 6 使用算法 决策树简介 划分数据集的大原则就是将无序的数据变得更加有序 划分数据集前后信息发生的变化成为信息增益 决策树简介 集合信息的度量方式称为香农熵 熵 条件熵 决策树简介 计算给定数据集的香农熵frommathimportlogdefcalcShannonEnt dataSet numEntries len dataSet labelCounts forfeatVecindataSet currentLabel featVec 1 ifcurrentLabelnotinlabelCounts keys labelCounts currentLabel 0labelCounts currentLabel 1shannonEnt 0 0forkeyinlabelCounts prob float labelCount key numEntriesshannonEnt prob log prob 2 returnshannonEnt 决策树简介 1 2 计算给定数据集的香农熵首先 计算数据集中实例的总数 为了提高代码效率 我们显式的声明一个变量保存实例总数 然后 创建一个数据字典 它的键值是最后一列的数值 1 如果当前键值不存在 则扩展字典并将当前键值加入字典 每个键值都记录了当前类别出现的次数 最后 使用所有类标签的发生频率计算类别出现的频率 2 我们将用这个概率计算香农熵 决策树简介 选择最好的数据集划分方式要求 1数据必须是一种列表元素组成的列表 而且所有的列表元素都要具有相同的数据长度 2数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签 决策树简介 递归构建决策树defcreateTree dataSet labels classList example 1 forexampleindataSet ifclassList count classList 0 len classList returnclassList 0 stopsplittingwhenalloftheclassesareequaliflen dataSet 0 1 stopsplittingwhentherearenomorefeaturesindataSetreturnmajorityCnt classList bestFeat chooseBestFeatureToSplit dataSet bestFeatLabel labels bestFeat myTree bestFeatLabel del labels bestFeat featValues example bestFeat forexampleindataSet uniqueVals set featValues forvalueinuniqueVals subLabels labels copyalloflabels sotreesdon tmessupexistinglabelsmyTree bestFeatLabel value createTree splitDataSet dataSet bestFeat value subLabels returnmyTree 决策树简介 1 2 3 递归构建决策树首先创建了名为classList列变量 其中包含了数据集的所有类标签 递归函数的第一个停止条件是所有的类标签完全相同 则直接返回该类标签 1 递归函数的第二个停止条件是使用完了所有特征 仍然不能将数据集划分成仅包含唯一类别的分组 2 决策树简介 递归构建决策树第二步 开始创建树 这里使用python语言的字典类型存储树的信息 3 决策树简介 递归构建决策树第三步 代码遍历当前选择特征包含的所有属性值 在每个数据集划分上递归调用函数createTree 得到的返回值将被插入到字典变量MyTree中 决策树简介 3种算法比较ID3较小数据算法清晰C4增加信息增益率可以处理连续数值型属性规则后修剪C5Unix 决策树算法 一ID3基本思想二ID3算法三实例四ID3缺点 决策树算法 在决策树各个结点上应用信息增益准则选择特征递归地构建决策树 天气 取值为 晴 多云 雨 气温 取值为 冷 适中 热 湿度 取值为 高 正常 风 取值为 有风 无风 决策树算法 ID3基本思想 某天早晨气候描述为 天气 多云 气温 冷 湿度 正常 风 无风 它属于哪类气候呢 要解决这个问题 需要用某个原则来判定 这个原则来自于大量的实际例子 从例子中总结出原则 有了原则就可以判定任何一天的气候了 每个实体在世界中属于不同的类别 为简单起见 假定仅有两个类别 分别为P N 在这种两个类别的归纳任务中 P类和N类的实体分别称为概念的正例和反例 将一些已知正例和反例放在一起便得到训练集 决策树算法 ID3基本思想 决策树算法 ID3基本思想 决策树算法 晴 多云 雨 P 正常 P N N P 有风 无风 湿度 风 天气 高 ID3基本思想 决策树算法 风 ID3算法 从根结点 rootnode 开始 对结点计算所有可能的特征的信息增益 选择信息增益最大的特征作为结点的特征 由该特征的不同取值建立子结点 再对子结点递归的调用以上方法 构建决策树 直到所有特征的信息增益均很小或者没有特征可以选择为止 最后 得到一个决策树 决策树算法 ID3算法 决策树算法 三实例 对于气候分类问题进行以下具体计算 1 信息熵计算 类别ui出现概率 S 表示例子集S的总数 ui 表示类别ui的例子数 对9个正例u1和5个反例u2有 2 条件熵计算条件熵 属性A1取值vj时 类别ui的条件概率 A1 天气的取值 v1 晴 v2 多云 v3 雨在A1处取值 晴 的例子5个 取值 多云 的例子4个 取值 雨 的例子5个 故 决策树算法 三实例 取值为晴的5个例子中有两个正例 3个反例 故 同理有 决策树算法 三实例 3 互信息计算对A1 天气 有 类似可得 气温 0 029bit 湿度 0 151bit 风 0 048bit 决策树算法 三实例 决策树算法 三实例 4 建决策树的树根和分支ID3算法将选择互信息最大的属性 天气 作为树根 在14个例子中对 天气 的3个取值进行分支 3个分支对应3个子集 分别是 F1晴 1 2 8 9 11 F2多云 3 7 12 13 F3雨 4 5 6 10 14 其中 F2中的例子全属于P类 因此对应分支标记为P 其余两个子集既含有正例P又含有反例 将递归调用建树算法 决策树算法 三实例 5 递归建树分别对F1和F3子集利用ID3算法 在每个子集中对各属性 仍为4个属性 求互信息 1 F1中的天气全取 晴 值 则H U H U V 有I U V 0 在余下3个属性中求出 湿度 互信息最大 以它为该分支的根结点 再向下分支 湿度 取 高 的例子全为N类 该分支标记N 取值 正常 的例子全为P类 该分支标记P 决策树算法 三实例 2 在F3中 对4个属性求互信息 得到 风 属性互信息最大 则以它为该分支的根结点 再向下分支 风 取 有风 时全为N类 该分支标记N 取 无风 时全为P类 该分支标记P 这样就得到如图所示的决策树 决策树算法 三实例 ID3算法的缺点 1 只适合属性值为离散的 2 决策树层次较多时 决策质量低 3 倾向于选择取值较多的属性 决策树算法 四ID3缺点 决策树 优点 决策树易于理解和实现 人们在在学习过程中不需要使用者了解很多的背景知识这同时是它的能够直接体现数据的特点 只要通过解释后都有能力去理解决策树所表达的意义 对于决策树 数据的准备往往是简单