《模式识别——决策树算法》由会员分享，可在线阅读，更多相关《模式识别——决策树算法（18页珍藏版）》请在金锄头文库上搜索。
1、数学与计算机学院课程名称: 模式识别 题 目: 决策树 任课老师: 王类 年级专业: 2014 级应用数学 姓 名: 闫辉 时 间: 2014 年 12 月 10 日模式识别决策树算法第 0 页 共 14 页目 录一 决策树算法介绍 .3二 ID3 算法描述 .3三 ID3 算法 java 实现 .51 实例 .52 算法的 JAVA 实现 .7四 ID3 算法性能分析 .141 优势 .142 弊端 .14五 ID3 算法改进 .14六、 附录 核心算法的主要源代码 .15.16.16.17参考文献 .18模式识别决策树算法第 1 页 共 14 页决策树算法一 决策树算法介绍决策树是数据挖掘
2、分类算法的一个重要方法。在各种分类算法中，决策树是最直观的一种。决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法 ID3, C4.5 和 C5.0 生成树算法使用熵。这一度量是基于信息学理论中熵的概念。决策树是由一系列节点组成的，每一个节点代表一个特征和相应的决策规则。最
3、上部的节点是根节点(这里的“树 ”通常是倒置过来画的，即根在顶端) ，此时所有的样本都在一起，经过该节点后被划分到各个子节点中。每个子节点再用新的特征来进一步决策，直到最后的叶节点。在叶节点上，每一个节点只包含纯一类的样本，不需要再划分。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数扼集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性
4、的分枝剪除。二 ID3 算法描述ID3算法是由 Quinlan 首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。 ID3算法主要针对属性选择问题，是决策树学习方法中最具影响和最为典型的算法。ID3采用贪心方法，其中决策树以自顶向下递归的分治方式构造。大 多 数 决 策 树 归 纳 算 法 都 沿 用 这种自顶向下的方法，从训练元组集和它们的相关联的类标号开始构造决策树。随着树的构建 ， 训 练 集 递 归 地 划 分 成 较 小 的 子 集 。ID3算 法 中 关 键 的 一 步 是 属 性 选 择 度 量 ， 即 选 择 分 裂 准 则 。 其
5、中 的 三 种 度 量 方 法 分 别 是信 息 增 益 、增 益 率 和 Gini 指 标 。 (示 例 算 法 选 择 了 第 一 种 方 法 )。 当 获 取 信 息 时 ， 将 不 确 定 的内容转为确定的内容，因此信息伴着不确定性。算法的基本策略如下：算法：Generate_decision_tree。由数据划分 D 的训练元组产生决策树。输入：1.数据划分 D 是 训 练 元 组 和 对 应 类 标 号 的 集 合2.attribute_list，候选属性的集合3.Attribute_selection_method， 一 个 确 定 “最 好 ”地 划 分 数 据 元 组 为 个
6、 体 类 的 分 裂准则的过程。这个准则由分裂属性和分裂点或分裂子集组成。输出：一棵决策树模式识别决策树算法第 2 页 共 14 页方法：创建一个节点 N；if D 中的元组都是同一类 C，then返回 N 作为叶节点，以类 C 标记；if attribute_list 为空 then返回 N 作为叶节点，标记为 D 中的多数类； /多数表决使用 Attribute_selection_method（D，attribute_list），找出“最好”的splitting_criterion；7用 splitting_criterion 标记节点 N；if splitting_ attribute
7、 是离散值的并且允许多路划分 then /不限于二叉树attribute_list attribute_list - splitting_ attribute ； /删除划分属性for splitting_criterion 的每个输出 j / 划分元组并对每个划分产生子树设 Dj 是 D 中满足输出 j 的数据元组的集合；/一个划分if Dj 为空 then加一个树叶到节点 N，标记为 D 中的多数类；else 加一个由 Generate_decision_tree（Dj，attribute_list）返回的节点到节点 N；end for返回 N；上述算法基本策略中，用到三个参数D、attr
8、ibute_list和Attribute_selection_method调用该算法。其中， D为数据划分；attribute_list是描述元组的属性列表；Attribute_selection_method 指定选择属性的启发式过程，所选择的属性按类“最好”地区分元组。该过程使用一种属性选择度量，如信息增益和Gini指标。属性选择度量是一种选择分裂准则，将给定的类标记的训练元组的数据划分D“最好”地分成个体类的启发式方法。如果我们要根据分裂准则的输出将D划分成较小的划分，理想地，每个划分是“纯”的，即，落在给定划分的所有元组都属于相同的类。从概念上讲，最好的划分准则是导致最接近这种情况的划
9、分。本文主要介绍一种流行的属性选择度量信息增益。信息增益度量基于Claude Shannon在研究消息的值或“信息内容”的信息论方面的先驱工作。设节点N代表或存放划分 D的元组。选择具有最高信息增益的属性作为节点N的分裂属性。该属性使结果划分中的元组分类所需的信息量最小，并反映这些划分中的最小随机性或“不纯性”。这种方法使对给定元组分类所需的期望测试数目最小，并确保找到一棵简单的树。对于D中的元组分类所需的期望信息由下式给出：（1）21()log()miiInfoDp其中，p i是D中任意元组属于类C i的概率，并用|C i,D|/|D|估计。使用以2为底的对数函数，因为信息用二进位编码。In
10、fo(D)是识别 D中的元组的类标号所需的平均信息量。这里，我们所具有的信息只是每个类的元组所占的百分比。Info(D)又称 D的熵。模式识别决策树算法第 3 页 共 14 页假设按属性A划分D中的元组，其中属性A根据训练数据的观测具有v个不同值a1,a2,av。可以用属性 A将 D划分为v个子集D 1D2,Dv ，其中D j包含D 中的元组，它们在A上具有值A j。这些划分将对应于从节点N 生长出来的分枝。理想地，我们希望该划分产生元组的准确分类，即，每个划分都是纯的。为了得到准确的分类我们还需要多少信息？这个量由下式度量：（2）1|()()vjAjjInfoInfoD项 充当第j个划分的权重。 是基于按A划分对D的元组分类所需要的期|D()If望信息。所需要的信息越小，划分的纯度越高。信息增益定义为原来的信息
