机器学习决策树算法ID3

山东大学计算机学院实验报告 实验题目 决策树算法 ID3 学号 日期 2016 12 6 班级 2014 级 4 班 姓名 Email 实验目的 1 熟悉 matlab 环境及相关函数的熟练使用 2 学习如何构造一棵决策树 并且用 matlab 画出树形状 3 学习如何使用一棵决策树 即将测试数值代入时 如何判断属于哪一类 4 会写测试集代入的分类表达式和类别的逻辑表达式并化简 5 分析该算法准确性 硬件环境 windows10 操作系统 软件环境 matlab 环境 Azure ML 平台 实验步骤 一 背景知识及原理 决策树算法 树状结构 每一个叶子节点对应着一个分类 决策树方法在分类 预测 规则提取等领域有着广泛的应用 在 20 世纪 70 年代后期和 80 年代初期 机器学习研究者 J Ross Quinilan 提出了 ID3 算 法以后 决策树在机器学习 数据挖掘领域得到极大的发展 Quinilan 后来又 提出了 C4 5 成为新的监督学习算法 1984 年几位统计学家提出了 CART 分 类算法 ID3 和 ART 算法大约同时被提出 但都是采用类似的方法从训练样本 中学习决策树的 决策树是一树状结构 它的每一个叶子节点对应着一个分类 非叶子节点 对应着在某个属性上的划分 根据样本在该属性上的不同取值将其划分成若干 个子集 构造决策树的核心问题是在每一步如何选择适当的属性对样本进行拆 分 对一个分类问题 从已知类标记的训练样本中学习并构造出决策树是一个 自上而下分而治之的过程 ID3 算法简介及基本原理 ID3 算法基于信息熵来选择最佳的测试属性 它选择当前样本集中具有最 大信息增益值的属性作为测试属性 样本集的划分则依据测试属性的取值进行 测试属性有多少个不同的取值就将样本集划分为多少个子样本集 同时决策树 上相应于该样本集的节点长出新的叶子节点 ID3 算法根据信息论的理论 采 用划分后样本集的不确定性作为衡量划分好坏的标准 用信息增益值度量不确 定性 信息增益值越大 不确定性越小 因此 ID3 算法在每个非叶节点选择 信息增益最大的属性作为测试属性 这样可以得到当前情况下最纯的划分 从 而得到较小的决策树 设 S 是 s 个数据样本的集合 假定类别属性具有 m 个不同的值 设 是类 中的样本数 对一个给定的样本 它总的信息熵 为 其中 是任意样本属于 的概率 一般可 以用 估计 设一个属性 A 具有 k 个不同的值 利用属性 A 将集合 S 划分 为 k 个子集 其中 包含了集合 S 中属性 A 取 值的样本 若选 择属性 A 为测试属性 则这些子集就是从集合 S 的节点生长出来的新的叶节点 设 是子集 中类别为 的样本数 则根据属性 A 划分样本的信息熵为 其中 是子集 中 类别为 的样本的概率 最后 用属性 A 划分样本集 S 后所得的信息增益 Gain 为 显然 越小 Gain A 的值就越大 说明选择测试属性 A 对于分类提供 的信息越大 选择 A 之后对分类的不确定程度越小 属性 A 的 k 个不同的值对 应的样本集 S 的 k 个子集或分支 通过递归调用上述过程 不包括已经选择的 属性 生成其他属性作为节点的子节点和分支来生成整个决策树 ID3 决策 树算法作为一个典型的决策树学习算法 其核心是在决策树的各级节点上都用 信息增益作为判断标准来进行属性的选择 使得在每个非叶子节点上进行测试 时 都能获得最大的类别分类增益 使分类后的数据集的熵最小 这样的处理 方法使得树的平均深度较小 从而有效地提高了分类效率 ID3 算法的具体流程 1 对当前样本集合 计算所有属性的信息增益 2 选择信息增益最大的属性作为测试属性 把测试属性取值相同的样本划为同 一个子样本集 3 若子样本集的类别属性只含有单个属性 则分支为叶子节点 判断其属性值 并标上相应的符号 然后返回调用处 否则对子样本集递归调用本算法 二 实验步骤 1 因为以前经常使用微软的 Azure 平台 这次仍然想用这个平台实验一下 测试使用决策树算法求出的准确率和召回率等以及改变参数对结果的影响 a 两分类决策树 第一个图是数据 前 12 个数据 第二个图是平台上的流 程图 参数配置 随机种子 0 0 25 的测试集 结果 测试集共 3 个数据 分错了 2 个 准确率为 33 3 召回率 1 通过可视化平台的结果对比可以发现决策树算法的准确率很低 我感觉这 个的原因是数据太少 所以偶然性太强 数据若是多一些 可能会好一些 2 开始自己着手写 matlab 程序 刚开始看到题感觉挺简单的 不就是算 出熵 然后算信息增益得到每次要判断的属性 那树不就画出来了么 然而事 实告诉我 用笔算的简单但是写程序就不那么容易了 每次传进去的是一批数 据 得根据数据去画树 然后我就通过看清华大学那本机器学习的书 找到了 一个伪代码的算法 思路没有错 就是一个递归算法 输入的变量是数据和属 性 输出的变量是一棵树的结构 照着这个循环写完之后 运行出来又出现了 错误 然后和同学讨论发现是结构体的问题 结构体比较 BT 的地方是要求参 数数目是相同的 所以每次定义结构体的以及每个 return 的时候都需要写全所 有的参数 即使为空 第一张图片是算法伪代码 第二张是结构体的写法 3 把树构造好后 返回的是一棵树的结构 里面包含了好几层 可以用 plot 的专门画树的方法画出来 但是 如何使用这棵树呢 我是把每棵树的每 个节点也就是结构体构造了好几个属性 如上图所示 保存了节点的类别 1 或者 2 保存了节点下一个属性 最大信息增益的属性 保存了它是 否是叶子节点 这样每次使用树的时候 代入数值后 先比较第一个最大信息 增益的属性 然后找下一个 直到叶子节点就可以判断出类别了 第二个问题是第二个测试数据中的第二维是 D 并不在该有的属性集中 然后我按照老师上课讲的方法 把它设置为属性集 1 2 3 中出现次数最 多的值 3 然后去计算 4 算法的过程 a 是 ID3 算法中最后的包括了递归的循环 注意每次递归 进去的是去掉了已使用过的属性值的 数据 data 和属性 attributes 都要去掉 b 是信息增益的求法 c 是判断样本在属性上取值是否相同 a 从属性中选择最优划分属性 a 求最优属性位于第 a 行 后面递归传入 data 时记得去掉那 一行 a gain data attributes tree nextsx a ma length unique data a 首先对每一个属性循环 生成 node 的一个分支 for i 1 ma node struct value null node node null node nextsx 0 树的每个节点的下一个要选择的属性 tree node i node 得到 data 中在该属性上不同取值的样本子集 dd d1 d2 d3 d4 fkjz data a dd for t 1 l if data a t i dd dd data t end end if isempty dd fprintf data 中在属性上不同取值的样本子集为空 n if last sum l 2 l tree node i value true else tree node i value false end tree node i nextsx 0 树的每个节点的下一个要选择的属性 else dd a shux attributes shux a tree node i ID3 dd shux tree node i a end end b for i 1 m2 x1 x2 x3 x4 fkjz x i 每次都得到按照某一个属性分开的矩阵 l1 i size x1 2 12 size x2 2 12 size x3 2 12 size x4 2 12 5 行 4 列 5 种特征 每种特征中每种节点占总结点 也就是 Sv S if size x1 2 12 0 p11 i 1 p12 i 1 entro1 i 1 entropy x1 m 1 2 end if size x2 2 12 0 p11 i 2 p12 i 2 entro1 i 2 entropy x2 m 1 2 end if size x3 2 12 0 p11 i 3 p12 i 3 entro1 i 3 entropy x3 m 1 2 end if size x4 2 12 0 p11 i 4 p12 i 4 entro1 i 4 entropy x4 m 1 2 end gain2 i entro l1 i 1 entro1 i 1 l1 i 2 entro1 i 2 l1 i 3 entro1 i 3 l1 i 4 entro1 i 4 end 求最大的信息增益位于的行数 gain max find gain2 max gain2 gain max gain max 1 c m l size x a 0 for i 2 l for w 1 m 1 if x w 1 x w i return end end end a 1 三 实验结果 1 树的结构 算上根节点分成了 4 层 属性依次选的是 1 2 5 第一张 图是画的这次分出的树的结构 第二张图是调用算法后返回了的树 后面几张 图是打开树的结构体的内部参数和结构 其中 true 是指 w1 类 false 是指 w2 类 每个结构体都是包含了 3 个属性 value 是类别 nextsx 是下一个要 选择的信息增益最大的属性位于的行数 因为每次我代入递归的时候是去掉已 用过的属性 所以显示的第一次 nextsx 1 即第一行属性 第二次 nextsx 1 也就是第二行 第三次 nextsx 3 也就是第五行 tree 是根节点 按照第一 个属性往下分出了 4 个子集 其中第二个子集又按照第二个属性分出了 3 个子 集 这 3 个子集的第一个子集按照第五个属性分出 3 个节点 自此分好 2 第二题分类两个测试数据 第一个数据为 2 3 2 1 2 第二个数据为 3 3 3 2 1 分类结果为第一个数据分到 w1 类 第二个数据分到 w2 类 3 第三题写出测试数据的逻辑表达式 a1 A D B E G G a2 A D C 4 第四题写出 w1 w2 的逻辑表达式 w1 A D A A D B E G G A D B E G E M N M w2 A D B E G E M N N A D B E G F A D C A D D 结论分析与体会 刚开始感觉这个题还挺简单的 因为思路是非常清晰的 根据信息增益找 属性 然后递归 ID3 算法就能得到树的结构了 但是用笔算简单 用程序写的 健全是不容易的 特别是争取更加抽象一些 不能只根据这 12 个数据来算 最好是以后不管传入什么数据进去都是可以算出来的 所以每个算法都包装一 下 思路一定要清晰 回过头看这个题目 感觉机器学习真的不能只靠听课了 平时要多看博客 之类的 才能深刻理解 除此之外感觉 matlab 越来越熟练了