本科生课程论文---文献综述题目：数据挖掘决策树ID3算法优化姓名：程健勇学号：221000328学院：数计（软件）学院专业：软件工程年级：2010教师：朱文兴2011年6月14日数据挖掘决策树ID3算法优化摘要：数据挖掘，也可以称为数据库中的知识发现(KnowledgeDiscoveryinDatabase，KDD)，是从大量数据中提取出可信、新颖、有效并能被人理解的模式的高级处理过程。决策树算法是数据挖掘中的一个比较活跃的研究领域,是对分类问题进行深入分析的一种方法,但构造最优决策树是一个NP困难问题。文中着重介绍了ID3算法的基本思想,然后讨论了决策树算法中的难点问题,针对ID3算法中所存在的不足,提出了一种利用优化法的思想来改进ID3的算法。关键字：数据挖掘，决策树算法，ID3算法。数据挖掘随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的日益普及,人们面临着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝藏为人类服务，业已成为广大信息科技工作者所重点关注的焦点之一。为有效解决这一问题，自二十世纪80年代开始，数据挖掘技术逐步发展起来。数据挖掘[1]，简单地讲就是从大量数据中挖掘或抽取出知识，它是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从大量数据中提炼有价值的信息，为决策提供支持。数据挖掘，又称为数据库中的知识发现，简称KDD，是一个从大量数据中抽取出未知的、有价值的模式或规律的复杂过程。典型的KDD过程包括:数据准备、数据清洗、数据集成、数据转换、数据挖掘、模式评估和知识表现六个环节。尽管数据挖掘只是整个知识发现过程的一个重要步骤，但是已经在工业界、媒体和数据库研究领域中，广义的表示为整个知识发掘过程。数据挖掘的目标是从大量数据中，发现隐藏于其后的规律或数据间的关系，从而服务于决策。利用数据挖掘技术可以帮助获得决策所需的多种知识。在许多情况下，用户并不知道数据中存在着哪些有价值的知识，因此对于一个数据挖掘系统而言，它应该能够同时搜索发现多种模式的知识，以满足用户的期望和实际需要。而本文主要讨论研究其中的决策树算法-包括ID3算法的优化研究，从数据挖掘决策树算法的许多研究资料中发现了许多不足之处，因此又参考了其他材料对其进行深入优化研究。决策树算法决策树算法是一种逼近离散函数值的方法，其分类精度高，成的模式简单，对噪声数据有很好的健壮性，因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。决策树方法最早产生于上世纪60年代，到70年代末。由JRossQuinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量缺值处理、剪枝技术。派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。说到决策树的构造方法，只是简单介绍一下。通过分析已有的数据训练集形成一系列规则，并运用规则对未知的数据进行预测的决策，以下为构造决策树的过程[2]：（1）寻找最初的分裂属性。将整个训练集作为产生决策树的集合，训练集每个记录已分类。在决定哪个属性是目前最好的分类属性时，一般的做法是穷尽现有的全部属性，对每个属性分裂的好坏进行量化，计算出最好的一个分裂。(2)重复步骤(1)，直至每个叶节点内的记录都属于同一类，并增长到一棵完整的树。作为分类器，决策树是一颗有向、无环树。树中的根节点没有父节点，所有其他节点都有且只有1个父节点；1个父节点可以有1～2个或没有子节点。如果节点没有子节点，称其为叶节点（LeafNode）；其他的称为内部节点（InternalNode）。每个叶节点都对应一个类别标识C的值；每个内部节点都对应一个用于分割数据集的属性Xi，称为分割属性（SplittingAttribute）；每个内部节点都有一个分割判断规则qj(SplittingPredicate)；如果Xi是连续属性，那么qj的形式为Xi小于等于xi，其中xi属于dom(Xi)，xi就是节点n的分割点（SplitPoint）；如果Xi是离散属性，那么qj的形式为xi属于Yi，其中Yi属于dom(Xi)，Yi就成为节点n的分割子集（SplitSubset）。节点n的分割属性和分割判断规则组成了节点n的分割标准（SplittingCriterion）。而本文主要研究决策树算法中的ID3算法及其优化。3ID3算法决策树方法[3]的起源是概念学习系统(ConceptLearningSystem,CLS),然后发展到ID3方法而为高峰。Quinlan提出的ID3算法通过对一个例子集进行学习生成一棵决策树,现假设一个例子仅属于两种分类之一:正