模式识别——决策树算法

《模式识别——决策树算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数学与计算机学院课程名称:模式识别题目:决策树任课老师:王类年级专业:2014级应用数学姓名:闫辉时间:2014年12月10日模式识别——决策树算法目录一决策树算法介绍3二ID3算法描述3三ID3算法java实现51实例52算法的JAVA实现7四ID3算法性能分析141优势142弊端14五ID3算法改进14六、附录——核心算法的主要源代码15161617参考文献18第16页共14页模式识别——决策树算法决策树算法一决策树算法介绍决策树是数据挖掘分类算法的一个重要方法。在各种分类算法中，决策树是最直观的一种。决策树(Decis

2、ionTree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。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，一个确定“最好”地划分数据元组为个体类的分裂准则的过程。这个准则由分裂属性和分裂点或分裂子集组成。输出：一棵决策树第16页共14

6、页模式识别——决策树算法方法：创建一个节点N；ifD中的元组都是同一类C，then返回N作为叶节点，以类C标记；ifattribute_list为空then返回N作为叶节点，标记为D中的多数类；//多数表决使用Attribute_selection_method（D，attribute_list），找出“最好”的splitting_criterion；7用splitting_criterion标记节点N；ifsplitting_attribute是离散值的并且允许多路划分then//不限于二叉树attribute_listß

7、attribute_list-splitting_attribute；//删除划分属性forsplitting_criterion的每个输出j//划分元组并对每个划分产生子树设Dj是D中满足输出j的数据元组的集合；//一个划分ifDj为空then加一个树叶到节点N，标记为D中的多数类；else加一个由Generate_decision_tree（Dj，attribute_list）返回的节点到节点N；endfor返回N；上述算法基本策略中，用到三个参数D、attribute_list和Attribute_selection_

8、method调用该算法。其中，D为数据划分；attribute_list是描述元组的属性列表；Attribute_selection_method指定选择属性的启发式过程，所选择的属性按类“最好”地区分元组。该过程使用一种属性选择度量，如信息增益和Gini指标。属性选择度量是一种选择分裂准