数据挖掘中决策树算法的探讨及实现

目录引言................................................................................11.概述.............................................................................11.1数据挖掘概述.................................................................11.1.1定义......................................................................................................................................11.1.2数据挖掘的功能...................................................................................................................11.1.3数据挖掘常用技术...............................................................................................................21.2决策树概述...................................................................21.2.１定义.....................................................................................................................................21.2.2四要素.................................................................................................................................21.2.3基于决策树分类模型的特点：..........................................................................................32．经典的决策树算法简介.............................................................32.1ID3(Iterative3)算法.......................................................32.2C4.5算法...................................................................42.3PUBLIC算法.................................................................42.4SLIQ算法...................................................................42.5SPRINT算法.................................................................53．用ID3算法生成决策树.............................................................53.1构造决策树流程.............................................................53.2决策树结构.................................................................53.3决策树的生成算法描述.......................................................63.3.1算法架构..............................................................................................................................63.3.2算法描述..............................................................................................................................74.用ID3算法生成决策树代码实现......................................................74.1本文工作.....................................................................74.2树的节点结构.................................................................74.3实现算法所用的函数...........................................................84.4算法输入.....................................................................84.5生成的决策树结构.............................................................94.6程序代码....................................................................115.小结.............................................................................21致谢...............................................................................21参考文献...........................................................................22英文翻译...........................................................................221数据挖掘中决策树算法的探讨及实现学生姓名:赵云鹏指导教师：梁晓玲摘要：现代世界是一个驱动的世界，我们被数据所包围，数据挖掘技术变成了决策者们的热门话题，数据挖掘是当前涉及统计学、人工智能、数据库等热门学科的研究领域，数据挖掘是从数据中提取人们感兴趣的、隐藏的、可用的知识，并表示成人们可以理解的形式。决策树算法是数据挖掘中特别热门的领域，通过对数据挖掘中决策树的分类算法的学习，论文中用C语言实现了ID3算法。关键字：数据挖掘；决策树；算法；ID3正文引言目前，我们现在已经生活在一个网络化的时代，通信、计算机和网络技术正改变着整个人类和社会，我们的生活被大量的数据包围，我们如何从浩如烟海的数据中找出所需的信息来，供人们的特定需求使用，成了我们最难解决的问题之一，而此时数据挖掘应运而生，数据挖掘就是从大量的数据中挖掘出有用的信息。1.概述1.1数据挖掘概述1.1.1定义数据挖掘（DataMining）就是对观测到的数据集（经常是庞大的、不完全的、有噪声的、模糊的、随机的）进行分析，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识，目的是发现未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结数据。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查找个别的记录，或通过因特网的搜索引擎查找特定的Web页面，则是信息检索领域的任务。虽然这些任务是重要的，可能涉及使用复杂的算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明显特征来创建索引结构，从而有效地组织和检索信息。尽管如此，数据挖掘技术也已用来增强信息检索系统的能力。1.1.2数据挖掘的功能数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下五类功能：(1）自动预测趋势和行为数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它可预测的问题包括预报破产以及认定对指定事件最可能作出反应的群体。2(2)关联分析数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。(3)聚类数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统的模式识别方法和数学分类学。80年代初，Mchalski提出了概念聚类技术，其要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术的某些片面性。(4)概念描述概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。(5)偏差检测数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是：寻找观测结果与参照值之间有意义的差别。1.1.3数据挖掘常用技术(1)人工神经网络(2)决策树(3)遗传算法(4)近邻算法(5)规则推导1.2决策树概述1.2.１定义决策树方法是一种逼近离散函数值的方法，是人们为了进行一项决策而进行的一系列的判断过程的树形图。决策树一般都是自上而下的来生成的，每个决策或事件都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。1.2.2四要素决策树的构成有四个要素：(1)决策结点；(2)方案枝；(3)状态结点；(4)概率枝。如图所示：3图1.四要素总之，决策树一般由方块结点、圆形结点、方案枝、概率枝等组成，方块结点称为决策结点，由结点引出若干条细支，每条细支代表一个方案，称为方案枝；圆形结点称为状态结点，由状态结点引出若干条细支，表示不同的自然状态，称为概率枝。每条概率枝代表一种自然状态。在每条细枝上标明客观状态的内容和其出现概率。在概率枝的最末稍标明该方案在该自然状态下所达到的结果。这样由左向右，由简到繁展开，组成一个树状网络图。1.2.3基于