数据挖掘决策树ID3算法优化

《数据挖掘决策树ID3算法优化》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、本科生课程论文…文献综述题目：数据挖掘决策树ID3算法优化姓名：程健境学号：221000328学院：数计（软件）学院专业：软件T程年级：2010教师：朱文兴2011年6月14日数据挖掘决策树ID3算法优化摘要：数据挖掘，也可以称为数据库中的知识发现(KnowledgeDiscoveryinDatabase,KDD),是从大量数据屮提取出可信、新颖、有效并能被人理解的模式的高级处理过程。决策树算法是数据挖掘中的一个比较活跃的研究领域,是对分类问题进行深入分析的一种方法，但构造最优决策树是一个NP困难问题。文中着垂介绍了ID3算法

2、的基木思想，然后讨论了决策树算法中的难点问题，针对ID3算法中所存在的不足，提出了一种利用优化法的思想来改进ID3的算法。关键字：数据挖掘，决策树算法，ID3算法。1数据挖掘随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的日益普及,人们血临着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝藏为人类服务，业己成为广人信息科技工作者所重点关注的焦点之一。为有效解决这一问题，自二十世纪80年代开始，数据挖掘技术逐步发展起来。数据挖掘[1],简单地讲就是从大量数据屮挖掘或抽取出知识，它是一门交叉学科，它把人们对数据的应用从

3、低层次的简单杏询，提升到从大量数据屮提炼有价值的信息，为决策提供支持。数据挖掘，乂称为数据库屮的知识发现，简称KDD,是一个从大量数据屮抽取出未知的、有价值的模式或规律的复杂过程。典型的KDD过程包括:数据准备、数据清洗、数据集成、数据转换、数据挖掘、模式评估和知识表现六个环节。尽管数据挖掘只是整个知识发现过程的一个重要步骤，但是已经在工业界、媒体和数据库研究领域中，广义的表示为整个知识发掘过程。数据挖掘的目标是从犬量数据屮，发现隐藏于其后的规律或数据间的关系，从而服务于决策。利用数据挖掘技术可以帮助获得决策所需的多种知识。在

4、许多情况下，用户并不知道数据中存在着哪些有价值的知识，因此对于一个数据挖掘系统而言，它应该能够同时搜索发现多种模式的知识，以满足用户的期望和实际需要。而本文主要讨论研究其中的决策树算法-包括ID3算法的优化研究，从数据挖掘决策树算法的许多研究资料屮发现了许多不足Z处，因此乂参考了其他材料对其进行深入优化研究。2决策树算法决策树算法是一种逼近离散函数值的方法，其分类精度高，成的模式简单，对噪声数据有很好的健壮性，因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘屮受到研究者的广泛关注。决策树方法最早产生于上世纪60年代，到70

5、年代末。由JRossQuinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量缺值处理、剪枝技术。派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。说到决策树的构造方法，只是简单介绍一下。通过分析已有的数据训练集形成一系列规则，并运用规则对未知的数据进行预测的决策，以下为构造决策树的过程［2］：(1)寻找最初的分裂属性。将整个训练集作为产生决策树的集合，训练集每个记录已分类。在决定哪个属性是目前最好的分类属性时，一般的做法是穷尽

6、现有的全部属性，对每个属性分裂的好坏进行量化，计算出最好的一个分裂。(2)重复步骤(1),直至每个叶节点内的记录都属于同一类，并增长到一•棵完整的树。作为分类器，决策树是一颗有向、无环树。树中的根节点没有父节点，所有其他节点都有且只有1个父节点；1个父节点可以有1〜2个或没有子节点。如果节点没有子节点，称其为叶节点(LeafNode)；其他的称为内部节点(InternalNode)。每个叶节点都对应一个类别标识C的值；每个内部节点都对应一个用于分割数据集的属性Xi,称为分割属性(SplittingAttribute)；每个内部

7、节点都有一个分割判断规则qj(SplittingPredicate)；如果Xi是连续属性,那么①的形式为Xi小于等于Xi，其中Xi属于dom(Xi),Xi就是节点n的分割点(SplitPoint)；如果心是离散属性,那么qj的形式为Xi属于丫“其中Yi属于doni(Xi),Y：就成为节点n的分割子集(SplitSubset)o糕、n的分割属性和分割判断规则组成了节点n的分割标准(SplittingCriterion)o而本文主要研究决策树算法中的JLD3算法及其优化。3ID3算法决策树方法的起源是概念学习系统(ConceptL

8、earningSystem,CLS)，然后发展到ID3方法而为高峰。Quinlan提出的TD3算法通过对一个例子集进行学习生成一棵决策树，现假设一个例子仅属于两种分类之一:正例，即符合被学习的H标概念的例子;反例，即不符合目标概念的例子。另外，假设例子的所有属性都是离散属性。