决策树分类算法学号：*********** 学生所在学院：软件工程学院***************教师所在学院：软件工程学院2015年11月12软件1班决策树分类算法葛强强12软件1班摘要：决策树方法是数据挖掘中一种重要的分类方法，决策树是一个类似流程图的树型结构，其中树的每个内部结点代表对一个属性的测试，其分支代表测试的结果，而树的每个叶结点代表一个类别。

通过决策树模型对一条记录进行分类，就是通过按照模型中属性测试结果从根到叶找到一条路径，最后叶节点的属性值就是该记录的分类结果。

关键词：数据挖掘，分类，决策树近年来，随着数据库和数据仓库技术的广泛应用以及计算机技术的快速发展，人们利用信息技术搜集数据的能力大幅度提高，大量数据库被用于商业管理、政府办公、科学研究和工程开发等。

面对海量的存储数据，如何从中有效地发现有价值的信息或知识，是一项非常艰巨的任务。

数据挖掘就是为了应对这种要求而产生并迅速发展起来的。

数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用的信息，提取的知识表示为概念、规则、规律、模式等形式。

分类在数据挖掘中是一项非常重要的任务。

分类的目的是学会一个分类函数或分类模型，把数据库中的数据项映射到给定类别中的某个类别。

分类可用于预测，预测的目的是从历史数据记录中自动推导出对给定数据的趋势描述，从而能对未来数据进行预测。

分类算法最知名的是决策树方法，决策树是用于分类的一种树结构。

1决策树介绍决策树（decisiontree）技术是用于分类和预测的主要技术，决策树学习是一种典型的以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。

它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性判断从该节点向下的分支，在决策树的叶节点得到结论。

所以从根到叶节点就对应着一条合取规则，整棵树就对应着一组析取表达式规则。

把决策树当成一个布尔函数。

函数的输入为物体或情况的一切属性（property），输出为”是”或“否”的决策值。

在决策树中，每个树枝节点对应着一个有关某项属性的测试，每个树叶节点对应着一个布尔函数值，树中的每个分支，代表测试属性其中一个可能的值。

最为典型的决策树学习系统是ID3，它起源于概念学习系统CLS，最后又演化为能处理连续属性的C4．5（C5．0）等。

它是一种指导的学习方法，该方法先根据训练子集形成决策树。

如果该树不能对所有给出的训练子集正确分类，那么选择一些其它的训练子集加入到原来的子集中，重复该过程一直到时形成正确的决策集。

当经过一批训练实例集的训练产生一棵决策树，决策树可以根据属性的取值对一个未知实例集进行分类。

使用决策树对实例进行分类的时候，由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。

决策树是应用非常广泛的分类方法，目前有多种决策树方法，如ID3，C4．5，PUBLIC，CART，CN2，SLIQ，SPRINT等。

大多数已开发的决策树是一种核心算法的变体，下面先介绍一下决策树分类的基本思想决策树构造与剪枝，然后详细介绍ID3和C4．5算法及决策树算法的分析及改进等。

2决策树构造与剪枝决策树分类算法通常分为两个步骤，决策树生成和决策树剪枝。

2．1决策树构造决策树构造算法的输入是一组带有类别标记的例子，构造的结果是一棵二叉树或多叉树。

二叉树的内部结点（非叶子结点）一般表示为一个逻辑判断，如形式为（ai=vi）的逻辑判断，其中ai是属性，vi是该属性的某个值。

树的边是逻辑判断的分支结果。

多叉树的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。

树的叶子结点都是类别标记。

构造决策树的方法是采用自上而下的递归构造。

以多叉树为例，它的构造思路是，以代表训练样本的单个结点开始建树，如果样本都在同一个类，则将其作为叶子结点，节点内容即是该类别标记。

否则，根据某种策略选择一个属性，按照属性和各个取值，把例子集合划分为若干子集合，使得每个子集上的所有例子在该属性上具有同样的属性值。

然后再依次递归处理各个子集。

这种思路实际上就是“分而治之”的道理。

二叉树同理，差别仅在于要如何选择好的逻辑判断。

构造好的决策树的关键在于如何选择好的逻辑判断或属性。

对于同样的一组例子，可以有很多决策树符合这组例子。

研究结果表明，一般情况下，树越小则树的预测能力越强。

要构造尽可能小的决策树，关键在于选择合适的产生分支的属性。

属性选择依赖于对各种例子子集的不纯度（Impurity）度量方法。

不纯度度量方法包括信息增益（InformationGain）、信息增益比（GainRa-tio）、Gini-index、距离度量、x2统计、证据权重、最小描述长度等。

不同的度量由不同的效果，特别是对于多值属性，选择合适的度量方法对于结果的影响是很大的。

ID3，C4．5，C5．0算法使用信息增益的概念来构造决策树，而CART算法x则使用Gini-in-dex，其中每个分类的决定都与前面所选择的目标分类相关。

2．2决策树的剪枝数据挖掘的对象是现实世界的数据，这些数据一般不可能是完美的，可能某些属性字段上缺值；可能缺少必须的数据而造成数据不完整；可能数据不准确、含有噪声甚至是错误的，所以要讨论噪声问题。

基本的决策树构造算法没有考虑噪声，生成的决策树完全与训练例子拟合。

有噪声情况下，完全拟合将导致过分拟合，即对训练数据的完全拟合反而不具有很好的预测性能。

剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。

1）两种基本的剪枝策略。

①前期剪枝（Forward-Pruning）是在树的生长过程完成前就进行剪枝。

在树的生长过程中，决定是继续对不纯的训练子集进行划分还是停机。

例如某些有效统计量达到某个预先设定的阈值时，节点不再继续分裂，内部节点成为一个叶子节点。

叶子节点取子集中频率最大的类作为自己的标识，或者可能仅仅存储这些实例的概率分布函数。

前期剪枝会引起树在不完全成熟之前停止工作，即树可能在不应停止的时候而停止扩展，或称之为horizon效应，而且，选取一个适当的阈值是困难的。

较高的阈值可能导致过分简化的树，而较低的阈值可能使树简化的太少。

即使这样，预先修剪对大规模的实际应用还是值得研究的，因为它相当高效。

人们有望在未来的算法中解决horizon效应。

②后期剪枝（Post-Pruning）是当决策树的生长过程完成之后再进行剪枝。

它是一种拟合-化简（Fitting-and-simplifying）的两阶段方法。

首先生成与训练数据完全拟合的一棵决策树，然后由下向上从树的叶子开始剪枝，逐步向根的方向剪。

剪枝时要用到一个测试数据集合，如果存在某个叶子剪去后测试集上的准确度或其它测度不降低（不变得更坏），则剪去该叶子，否则停机。

如果节点的子树不应按某种规则被修剪，则由下向上的评价规则将使该节点避免被按同一规则修剪。

与此相对的是自上向下的策略，即从根开始依次修剪节点，直到无法修剪为止。

这样作的风险在于，按某种规则剪掉了某个节点，但其子类是不应按这一规则被剪掉的。

2）对树进行修剪优化时应遵循的原则。

①最小描述长度原则（MDL）。

它的思想是最简单的解释是期望的，做法是对决策树进行二进位编码。

编码所需二进位最少的树即为“最佳剪枝树”。

②期望错误率最小原则。

它的思想是选择期望错误率最小的子树剪枝，即对树中的内部节点计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍。

③奥卡姆剃刀原则。

如无必要，勿增实体。

即“在与观察相容的理论中，应当选择最简单的一个”，决策树越小就越容易被理解，其存储与传输的代价也就越小。

3 ID3算法ID3算法是1986年Quinlan提出的一个著名决策树生成方法，是目前引用率很高的一种算法。

ID3算法是运用信息熵理论，选择当前样本集中最大信息增益的属性值作为测试属性；样本集的划分则依据测试属性值进行，测试属性有多少不同取值就将样本集划分为多少子样本集，同时，决策树上相应于该样本集的节点长出新的叶子节点。

由于决策树的结构越简单越能从本质的层次上概括事物的规律，期望非叶节点到达后代节点的平均路径总是最短，即生成的决策树的平均深度最小，这就要求在每个节点选择好的划分。

系统的不确定性越小，信息的传递就越充分。

ID3算法根据信息理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量：信息增益值越大，不确定性越小。

因此，算法在每个非叶节点选择信息增益最大的属性作为测试属性。

ID3算法将对挖掘样本集分为训练样本集和测试样本集，决策树的构建是在对训练样本集的学习上产生的，决策树生成之后，再运用测试样本集对树进行后剪技，将分类预测准确率不符合条件的叶节点剪去。

1）信息理论（Informaitontheory）和熵（Entro-py）。

信息论是C．EShannon为解决信息传递（通信）过程问题而建立的理论，一个传递信息的系统是由发送端和接收端以及连接两者的通道三者组成。

熵是对事件对应的属性的不确定性的度量。

一个属性的熵值越小、子集划分的纯度越高，熵值熵越大，它蕴含的不确定信息越大，约有利于数据的分类。

2）信息增益（InformmationGain）。

信息增益基于信息论中熵（Entropy）的概念，是指期望信息或者信息熵的有效减少量（通常用“字节”衡量），根据它能够确定在什么样的层次上选择什么样的变量来分类。

ID3总是选择具有最高信息增益（或最大熵）的属性作为当前结点的测试属性。

该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。

信息增益计算如下：设S是s个训练样本数据集，S中类标识属性具有m个不同值，定义m个不同类Ci （i=1，2，3…，m）。

设si是类Ci中的样本数。

对一个给定的样本分类所需的期望信息由下式得出：I（s1，s2，…，sm）=－m∑i=1 pilb（pi）其中pi是任意样本属于Ci的概率，一般可用si/s来估计。

设属性A具有n个不同值｛a1，a2，…，an｝，可以用属性A将S划分为n个子集｛S1，S2，…，Sn｝，其中Sj包含S中这样一些样本，它们在A上具有值aj。

如果A作为测试属性，则这些子集对应于由包含集合S的结点生长出来的分支。

设sij是子集Sj中类Ci的样本数。

根据由A划分成子集的熵由下式给出：E（A）=－n∑j=1 s1j+s2j+…+smjsI（s1j，s2j，…，smj）根据上面的期望信息计算公式，对于给定的子集Sj，其期望信息由下式计算：I（s1j，s2j，…，smj）=－m∑i=1 pijlb（pij）其中（pij=sij|sj|）对属性A作为决策分类属性的度量值即信息增益可以由下面的公式得到：Gain（A）=I（s1，s2，…，sm）－E（A）3）ID3算法的分析。