信息科学与技术学院学士学位论文
第四，执行数据流。
图2-3所示为我们用软件设计出来的一个简单的数据流。
图2-3一个简单的数据流例子
16
信息科学与技术学院学士学位论文
3 决策树算法的研究
3.1决策树算法的概述
3.1.1什么是决策树
决策树是就是类似于一棵树，并且这棵树里头包含着我们需要的决策信息。我们通过使用决策树的相关算法，可以根据我们的目的对我们收集的数据进行分类，最后找出对于我们的需求有意义的信息。在决策树中有父节点和子节点，相邻两层节点表达的是一种映射的关系：父节点代表属性，子节点代表属性的值。下面我根据一对母女对话的例子来向大家展示一棵简单的决策树。 假设一位母亲给自己的女儿介绍对象，她们之间有以下对话： 女儿：那个人多少岁？ 母亲：27。
女儿：长的好看吗？ 母亲：长相很好。 女儿：收入怎么样？ 母亲：中等水平以上。 女儿：是公务员吗？ 母亲：是，在检察院上班。 女儿：那好，我去见见。
假设女儿选择对象的标准是：男方年龄不得超过30岁、长相中等以上、收入很高或者中等以上、必须为公务员。那么根据上面一对母女的对话以及女儿择偶的标准我们可以构造出一棵简单的分类决策树，如图3-1所示。
17
信息科学与技术学院学士学位论文
图3-1简单分类决策树
3.1.2决策树算法的提出及发展
第一种决策树算法产生于上个世纪，至今已有60年左右。一个叫Quinlan的人提出了ID3算法[6]，他当时研究这个新算法的目的是因为使用一般的方法建立的决策树树的深度太大，所以他想使用新的方法限制树的深度，但是他疏忽了决策树树分枝有可能太多的问题。后来有人研究出了C4.5算法，该算法是在ID3算法基础上进行了改进。后来相继出现了不少的分类算法，其中SPARINT[7]算法的出现使得决策树挖掘在内存方面的问题得到了一定的改善，因为它通过改变算法的数据结构从而有效的减少了数据需要完全保留在内存中才可以被软件使用的弊端。
到了20世纪90年代后，越来越多对数据挖掘感兴趣的学者自发的加入决策树算法研究队列。由于早前数据挖掘技术应用的领域相对较窄，不能够满足人们对数据挖掘更高的需求。所以很多学者对提高决策树算法的效率进行了更深入的研究。如今越来越多的学者或者研究人员热衷于把决策树算法运用的更广泛，因此我们可以使用的基于决策树算法的挖掘工具越来越多了。
18
信息科学与技术学院学士学位论文
3.1.3决策树算法的主要思想
我们知道分类预测包含了分类和回归这两个重要的含义。决策树算法属于分类预测中的一种非常经典的数据挖掘算法。在实际应用挖掘工具时，当选中的输出变量作为分类型时，则挖掘出来的分类模型被称为分类模型；当我们的输出变量为连续数值型时，则挖掘出来的分类模型被称为回归模型。决策树的算法就是建立分类模型或者回归模型，因在展示分析所得结论类似一棵倒置的树，所以被称为决策树。一棵决策树只有一个根节点（在树的最上层），若干的叶节点（在树的最下层）。决策树有以下特点：
（1）决策树的每个节点都有一定量的样本，从根节点开始往下各节点样本量逐级减少，这体现了决策树算法挖掘是对数据进行不断分组的的过程。
（2）有两种类型的决策树，使用的是哪种类型的树取决于输出变量的类型，分类型的输出变量用分类回归树，而且预测值是这个样本输出变量值的众数类别。 （3）决策树算法的分类预测是基于逻辑的。 3.1.4决策树的核心问题
构建决策树的核心过程[8]主要有以下两个：第一，决策树的生长过程；第二，决策树的修剪过程。
图3-2为比较常见的决策树生长过程图。从图中可以得出决策树生长过程其实是对我们收集的数据不断分组的过程，并且每个分枝是在分组的过程中逐渐生成的。在分组的过程中，如果某组数据对于我们的分组不再有帮助的时候，相应的分枝就不会再生长了，直到剩下的数据中所有的分组都不再有意义的时候，决策树才停止生长。所以我们知道当前数据对分组是否有意义很大程度决定了我们的决策树生长的是否茂盛。
决策树最后生长停止并得到了一棵完整的决策树，但是并不表示这是一棵最佳的分类预测树，因为该决策树有着“精确过度”的特征。我们知道完整的决策树很可能失去一般代表性，这样的树是不适用与分类预测的。在数据挖局中这种现象被称作为“过拟合”，需要通过对决策树进行相应的修剪才能解决。非传统的决策树
19
信息科学与技术学院学士学位论文
算法具有两种修剪方法，其中包括对正在进行生长树修剪和对生长完成的树修剪。第一种是在决策树生长的过程中限制其从分生长，而第二种则是在决策树生长结束后再进行修剪以减少树的子叶。
是
确定根节点分枝准则 长出一层枝 在某枝中重新确定分枝准则 是 差异减少显著 否 达到叶节点 否 均达到叶节点 决策树生长图3-2 决策树生长过程图
3.2决策树基本算法的介绍
在介绍下面算法前先给介绍信息熵和信息增益这两个基本概念。信息熵是信息论中比较基本的概念，这个概念理解起来比较抽象。信息熵是用来度量一组信息是否很乱，也可以说是对系统有序化的度量。信息论是在1948年被香农[9]（CE.Shannon）提出来的，它的主要目的是为了解决信息传递过程中遇到的问题。我们通过理解这个概念知道一个系统如果越有秩序，那么它的熵就会越低。信息增益（information gain），即前后信息的差值。信息增益这个概念被用于决策树的分类，主要的作用是决策树在进行属性选择划分时把这个参数的取值作为判断的标准。
20