模式识别报告.docVIP

数学与计算机学院

课程名称:模式识别

题目:决策树-基于手写数据实现

任课老师:王晓明

年级专业:2011级计算机科学与技术

姓名:游在雨城

学号:312011080605300

时间:2013年11月20日

模式识别——决策树-基于手写数据实现

第PAGE1页共14页

目录

TOC\o1-3\h\z\u一决策树介绍 2

1决策树算法的历史与发展： 2

2决策树算法的主要思想： 2

二决策树ID3算法描述 4

?1ID3属性选择： 4

2ID3实例 4

三ID3算法C++实现-基于手写数据实现 9

1数据读入 9

1手写数据的产生: 9

2手写数据的识别过程： 9

2算法运行结果 10

四总结和心得 15

五附录——核心算法的主要源代码 16

参考文献 23

决策树

一决策树介绍

1决策树算法的历史与发展：

决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。

决策树方法最早产生于上世纪60年代，到70年代末。由JRossQuinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。

1960’s：Hunt的完全有哪些信誉好的足球投注网站决策树方法（CLS）对概念学习建模。

1970后期：Quinlan发明用信息增益作为启发策略的ID3方法，从样本中学

习构造专家系统同时，Breiman和Friedman开发的CART（分类与回归树）

方法类似于ID3。

1980’s：对噪声、连续属性、数据缺失、改善分割条件等进行研究。

1993：Quinlan的改进决策树归纳包（C4.5），目前被普遍采用。

2决策树算法的主要思想：

决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。决策树的基本组成部分：决策节点、分支和叶子。

决策节点，是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案。

分支节点，代表备选方案的经济效果（期望值），通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。

结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。

决策树中最上面的节点称为根节点，是整个决策树的开始。决策树的每个节点子节点的个数与决策树在用的算法有关。如CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。决策树的内部节点（非树叶节点）表示在一个属性上的测试。每个分支要么是一个新的决策节点，要么是树的结尾，称为叶子。在沿着决策树从上到下遍历的过程中，在每个节点都会遇到一个问题，对每个节点上问题的不同回答导致不同的分支，最后会到达一个叶子节点。这个过程就是利用决策树进行分类的过程，利用几个变量（每个变量对应一个问题）来判断所属的类别（最后每个叶子会对应一个类别）。

具体描述如下：

1）树以代表训练样本的单个结点开始。

2）如果样本都在同一个类．则该结点成为树叶，并用该类标记。

3）否则，算法选择最有分类能力的属性作为决策树的当前结点．

4）根据当前决策结点属性取值的不同，将训练样本数据集tlI分为若干子集，每

个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到的一个

子集，重复进行先前步骤，递4I形成每个划分样本上的决策树。一旦一个属

性出现在一个结点上，就不必在该结点的任何后代考虑它。

5）递归划分步骤仅当下列条件之一成立时停止：

①给定结点的所有样本属于同一类。

②没有剩余属性可以用来进一步划分样本．在这种情况下．使用多数表决，

将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，

同时也可以存放该结点样木的类别分布，

③如果某一分枝tc，七砰如恤卜a*没有样本，则以样本的多数类创建一个树叶。