机器学习与知识发现实验—酒分类

UsingUsing chemicalchemical analysisanalysis determinedetermine thethe originorigin ofof wineswines 赵启杰 SC11011063 摘要摘要 采用较简单的决策树归纳算法根据红酒的成分对其进行分类 划分度量采用的是 Gini 指标 所有数据都看做是连续属性 进行二元划分 最后得到的是一棵二叉决策树 最后 采用二折交叉验证的方式 进行评估 得到的分类准确度在 85 左右 为了简单 没有考虑噪声的干扰 没有考虑模型的过分拟合问题 没有考虑泛化误差 相关工作相关工作 算法的实现参考 数据挖掘导论 算法 4 1 的决策树归纳算法的框架 TreeGrowth E F if Stopping cond E F true then leaf creatNode leaf label Classify E return leaf else root creatNode root test cond find best split E F 令 V v v 是 root test cond 的一个可能的输出 for 每个 v in V do Ev e root test cond e v 并且 e in E child TreeGrowth Ev F 将 child 作为 root 的派生节点添加到树中 并将边 root child 标记为 v end for end if ruturn root 其中 E 是训练记录集 F 是属性集 涉及到的主要类 涉及到的主要类 Tuple 数据集的一条记录 这里把记录的所有属性都当成浮点型数据处理 TupleTable 整个数据集 其中 iClassNum 代表总共的类数 iTableLen 代表记录数 iTupleSize 代表记录的属性数 rgStrClasses 保存所有的类 rgStrAttribute 保存所有的属性 rgTuples 保存所有的记录 DecisionNode 决策树中的一个节点 TestCond 决策树非叶子节点中保存的测试条件 涉及到的主要方法 涉及到的主要方法 TupleTable InitTableFromFile 从数据文件获取数据 初始化数据集 数据文件格式需要做适当修改 TupleTable TupleIndexs 从数据集导出一个数据集的索引 即一个由 Tuple 指针组成的数组 该数组中的每一 个元素指向 TupleTable 中的一个 Tuple 可以通过比较 Tuple 的值对索引中的指针进行排序 Stopping cond 通过检查是否所有的记录都属于同一个类 或者都具有相同的属性值 决定是否终止 决策树的增长 或者检查记录数是否小于某一个最小阈值 BOUNDARY RECORD 通过调整阈值可以在一定范围内改变分类器的准确率 CreateNode 为决策树建立新节点 决策树的节点或者是一个测试条件 即一个 testcond 对象 或 者是一个类标号 Find best split 确定应当选择哪个属性作为划分训练记录的测试条件 使用的不纯性度量是 Gini 指标 首先对索引按第 j 个属性进行排序 如果索引中第 i 个记录和第 i 1 个记录不是同一个类 则将第 i 个记录和第 i 1 个记录的属性 j 的中间值作为划分点 计算 Gini 指标 循环计算 所有可能的 Gini 指标 找出其中的最小值 保存属性名和属性值 作为当前最优测试条件 GetGini 获取某个训练数据子集的 Gini 指标 1 0 2 1 c i tiptGini 其中 p i t 表示节点 t 中属于类 i 的记录所占比例 Classify 为节点确定类标号 对于节点 t 统计分配到该节点的所有记录中类 i 的记录数 0 i iClassNum 则节点的类标号为 max i Sort record 对记录子集的索引按照某个属性从小到大进行排序 为了简单 使用了冒泡 TreeGrowth 递归创建决策树 创建决策时之前需要对作为输入的数据集文件做适当修改创建决策时之前需要对作为输入的数据集文件做适当修改 属性个数 n 属性名 1 属性名 n 类个数 m 类名 1 类名 m 记录数 k 类名 属性 1 属性 n 类名 属性 1 属性 n 由于分类器的性能评估并不是实验的主要内容 因此这里只是简单的做了一下二折交 叉验证 将数据集随机分成两个子集 其中一个作为训练集 另一个作为检验集 然后互 换集合再做一次 最后得到的准确率在 85 左右 优劣分析 优劣分析 1 决策树归纳是一种构建分类模型的非参数方法 换言之 它不要求任何先验假设 不假定类和其他属性服从一定的概率分布 如 Logistic 回归 2 找到最优决策树是 NP 完全问题 许多决策树算法都采取启发式方法指导对假设空 间的搜索 如采用贪心的 自顶向下的递归划分策略建立决策树 3 不需要昂贵的计算代价 即使训练集非常大 也可以快速建立模型 此外 决策树 一旦建立 未知样本分类也非常快 最坏情况下的时间复杂度为 O w 其中 w 是树的最 大深度 4 决策树相对容易解释 特别是小型决策树 在很多简单的数据集上 决策树的准确 率也可以与其他分类算法想媲美 5 决策树算法对于噪声的干扰具有相当好的鲁棒性 采用避免过分拟合的方法之后尤 其如此 6 冗余属性不会对决策树的准确率造成不利影响 如果一个属性在数据集中与另一个 属性是强相关的 则该属性是冗余的 在两个冗余属性中 如果已经选择其中一个作为用 于划分的属性 则另一个属性将被忽略 另一方面 如果数据集中含有很多与目标变量不 相关的属性 则某些属性可能在树的构造过程中偶然被选中 导致决策树过于庞大 在预 处理阶段 特征选择技术能够帮助找出并删除不相关属性 以帮助提高决策树的准确率 7 数据碎片 data fragmentation 问题 由于大多数的决策树算法采用自顶向下的递 归划分方法 因此沿着树向下 记录会越来越少 在叶子结点记录数量可能太少 以致对 于叶子结点代表的类的判决不具有统计显著性 解决这一问题的方法是当样本数小于某个 特定阀值时停止分裂 8 由于大多数决策树算法采用分治划分策略 因此属性空间的不同部分可能使用相同 的测试条件 从而导致子树在决策书中重复出现多次 这使得决策树过于复杂 并且可能 更难于解释 9 决策树是学习离散值函数的典型代表 然而 它不能很好的推广到某些特定的布尔 问题 如对于奇偶函数来说 当奇数 偶数个布尔属性为真时其值为 0 1 对这样的函数准 确建模需要一棵具有 2 的 d 次方个节点的满决策树 d 为布尔属性的个数 10 对于测试条件只涉及一个属性的决策树 可以将决策树的成长过程看成划分属性 空间为不相交的区域的过程 直到每个区域都只包含同一记录 两个不同类的相邻区域之 间的边界称作决策边界 Decision Boundary 由于测试属性只涉及单个属性 因此决策边 界是平行于坐标轴的直线 这就限制了决策树对连续属性之间复杂关系建模的表达能力 斜决策树 Oblique Decision Tree 是克服以上局限的方法之一 它允许测试条件涉及多个 属性 如 x y 1 当然 这一技术在赋予决策树更强表达能力的同时 为给定结点找出最 佳的测试条件的计算复杂度也是昂贵的 另一种将属性空间划分为非矩形区域的方法是构 造归纳 Constructive Induction 即创建复合属性用于代表已有属性的算术 逻辑组合 该 方法不需要昂贵的计算花费 11 研究表明大部分不纯性度量方法的结果是指一致的 因此不纯性度量方法的选择 对决策树算法的