文档介绍：I
摘要
随着信息科技的高速发展，人们对于积累的海量数据量的处理工作也日益增重，需求是发明之母，数据挖掘技术就是为了顺应这种需求而发展起来的一种数据处理技术。
数据挖掘技术又称数据库中的知识发现，是从一个大规模的数据库的数据中有效tabases，简称：KDD）中的一个步骤。数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系性（属于Associationrulelearning）的信息的过程。数据挖掘通常与计算机科学有关，并通过统计、在线分析处理、情报检索、
6
5
数据挖掘是通过分析每个数据，从大量数据中寻找其规律的技术，主要有数据准备、规律寻找和规律表示3个步骤。数据准备是从相关的数据源中选取所需的数据并整合成用于数据挖掘的数据集；规律寻找是用某种方法将数据集所含的规律找出来；规律表示是尽可能以用户可理解的方式（如可视化）将找出的规律表示出来。
决策树是判定给定样本与某种属性相关联的决策过程的一种表示方法，从数据中生成分类器的一个特别有效的方法是生成一棵决策树，该方法广泛应用与数据挖掘和机器学****等领域，用来解释用分类相关的问题，决策树表示法是应用最广泛的逻辑方法之一。目前生成决策树方法的算法主要有三种：CART算法、。，是发展比较完善的一种决策树算法。
决策树算法背景知识及研究现状
决策树，顾名思义就是一个类似于流程图的树型结构。—个决策树由根结点、分支和叶结点构成。树的最高层节点称为根结点，是整个决策树的开始。与根结点相连的不同分支，对应这个属性的不同取值，根据不同的回答转向相应的分支，在新到达的结点处做同样的分支判断，持续这一过程直到到达某个叶结点。在决策树中，每个内部结点表示一个测试，该结点的每个分支表示该测试的一个结果，每个叶结点表示一个类别。例如公司需要预测某位客人是否要买计算机，,从中可以看到决策树的基本组成部分：根结点、分支和叶结点。
年龄
6
决策树算法广泛应用于各个领域，已经有了广泛的应用并且有许多成熟的系统，如语音识别、医疗诊断、模式识别和专家系统等。
目前，决策树技术面临的挑战表现在以下几个方面：
可扩展性亟待提高。在大型数据集中，能从中快速而准确地发现隐藏于其中的主要分类规则，即认为算法具有良好的可扩展性。数据挖掘面临的数据往往是海量的，对实时性要求较高的决策场所，数据挖掘方法的主动性和快速性显得日益重要。
适应多数据类型和容噪性。随着计算机网络和信息的社会化，数据挖掘的对象已不单是关系数据库模型，而是分布、异构的多类型数据库，数据的非结构化程度、噪声等现象越来越突出，这也是决策树技术面临的困难问题。
决策树方法的递增性。数据挖掘出来的知识，只是相对于某一时间的某些数据，新的数据可能使发现的新知识与原来的知识冲突。因此，设计具有递增性决策树挖掘方法，也是实用化的基本要求之一。
第三章决策树算法
CLS算法是早期的决策树学****算法，是许多决策树学****算法的基础。
CLS基本思想：从一棵空决策树开始，选择某一属性作为测试属性。该测试属性对应决
策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。
例1：、头发颜色与所属人种之间的关系：
人员
眼睛颜色
头发颜色
所属人种
1
黑色
黑色
黄种人
2
蓝色
金色
白种人
7
3
灰色
金色
白种人
4
蓝色
红色
白种人
5
灰色
红色
白种人
6
黑色
金色
混血
7
灰色
黑色
混血
8
蓝色
黑色
混血
，选择“眼睛颜色”为测试属性，可将该样本划分为相应的子
根据“眼睛颜色”所划分的子集中的样本不属于同一类，所以选择新的测试属性“头发
颜色”对各个子集进行划分，，所得的样本属于同一类，决策树构建完成。
8
3・2ID3算法
ID3算法是决策树学****算法中最具有影响和最为典型的算法，它的基本思想是，利用信息熵原理，选择信息增益最大的属性作为分类属性。
Shannon1948年提出的信息论理论。事件a的信息量I(a)可如下度